[PATCH v3] wt-status: avoid repeated insertion for untracked paths

[Sahitya Chandra <sahityajb@gmail.com>]

wt_status_collect_untracked() copies entries from dir.entries and
dir.ignored into string_lists using string_list_insert(). At first glance
this seems quadratic, because inserting into the sorted list may shift the
backing array, incurring O(n) work for each insert.

In practice, though, the entries in the dir struct are already sorted, so
we should not have to shift the array and only pay the O(log n) lookup cost
for each insertion. But this is subtle and depends on the behavior of
fill_directory().

Collect the entries with string_list_append() instead, then sort and
deduplicate each list once with string_list_sort_u(). This preserves the
sorted, duplicate-free result while making the collection strategy explicit.

Signed-off-by: Sahitya Chandra <sahityajb@gmail.com>
---
Changes since v2:
- Reword the commit message to explain the quadratic concern while noting
  that the current sorted input avoids array shifts in practice.

 wt-status.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/wt-status.c b/wt-status.c
index 58461e02f8..57772c7501 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -832,14 +832,16 @@ static void wt_status_collect_untracked(struct wt_status *s)
 	for (i = 0; i < dir.nr; i++) {
 		struct dir_entry *ent = dir.entries[i];
 		if (index_name_is_other(istate, ent->name, ent->len))
-			string_list_insert(&s->untracked, ent->name);
+			string_list_append(&s->untracked, ent->name);
 	}
+	string_list_sort_u(&s->untracked, 0);
 
 	for (i = 0; i < dir.ignored_nr; i++) {
 		struct dir_entry *ent = dir.ignored[i];
 		if (index_name_is_other(istate, ent->name, ent->len))
-			string_list_insert(&s->ignored, ent->name);
+			string_list_append(&s->ignored, ent->name);
 	}
+	string_list_sort_u(&s->ignored, 0);
 
 	dir_clear(&dir);
 

base-commit: 41365c2a9ba347870b80881c0d67454edd22fd49
-- 
2.43.0