string-list: replace negative index encoding with "exact_match" parameter

PATCH In review shejialuo 2 participants 3 messages Sep 7, 2025 – Sep 15, 2025

Share & tools

shejialuo

author

2025-09-07 16:40 UTC #0 lore raw

PATCH 2/4 string-list: replace negative index encoding with "exact_match" parameter

We would return negative index to indicate exact match by converting the original positive index to be "-1 - index" in "string_list_find_insert_index", which requires callers to decode this information.

This is bad due to the following reasons:

1. The callers need to convert the negative index back to the original positive value, which requires the callers to understand the detail of the function.
2. As we have to return negative index, we need to specify the return type to be int instead of size_t, which would cause sign compare warnings.

Refactor "string_list_find_insert_index" to use an output parameter "exact_match" for indicating the exact match rather than encoding through negative return values.

Signed-off-by shejialuo <[email protected]>

---
 add-interactive.c | 7 ++++---
 mailmap.c         | 7 +++----
 refs.c            | 2 +-
 string-list.c     | 8 ++------
 string-list.h     | 2 +-
 5 files changed, 11 insertions(+), 15 deletions(-)

add-interactive.c +4 -3

index 3e692b47ec..9a42b3b38b 100644
@@ -221,7 +221,8 @@ static void find_unique_prefixes(struct prefix_item_list *list)
 
 static ssize_t find_unique(const char *string, struct prefix_item_list *list)
 {
-	int index = string_list_find_insert_index(&list->sorted, string, 1);
+	int exact_match;
+	int index = string_list_find_insert_index(&list->sorted, string, &exact_match);
 	struct string_list_item *item;
 
 	if (list->items.nr != list->sorted.nr)

@@ -229,8 +230,8 @@ static ssize_t find_unique(const char *string, struct prefix_item_list *list)
 		    " vs %"PRIuMAX")",
 		    (uintmax_t)list->items.nr, (uintmax_t)list->sorted.nr);
 
-	if (index < 0)
-		item = list->sorted.items[-1 - index].util;
+	if (exact_match)
+		item = list->sorted.items[index].util;
 	else if (index > 0 &&
 		 starts_with(list->sorted.items[index - 1].string, string))
 		return -1;

mailmap.c +3 -4

index 56c72102d9..253517cdf6 100644
@@ -243,10 +243,9 @@ void clear_mailmap(struct string_list *map)
 static struct string_list_item *lookup_prefix(struct string_list *map,
 					      const char *string, size_t len)
 {
-	int i = string_list_find_insert_index(map, string, 1);
-	if (i < 0) {
-		/* exact match */
-		i = -1 - i;
+	int exact_match;
+	int i = string_list_find_insert_index(map, string, &exact_match);
+	if (exact_match) {
 		if (!string[len])
 			return &map->items[i];
 		/*

refs.c +1 -1

index 4ff55cf24f..f1ff5bf846 100644
@@ -1699,7 +1699,7 @@ const char *find_descendant_ref(const char *dirname,
 	 * with dirname (remember, dirname includes the trailing
 	 * slash) and is not in skip, then we have a conflict.
 	 */
-	for (pos = string_list_find_insert_index(extras, dirname, 0);
+	for (pos = string_list_find_insert_index(extras, dirname, NULL);
 	     pos < extras->nr; pos++) {
 		const char *extra_refname = extras->items[pos].string;

string-list.c +2 -6

index bf358d1a5c..224bc182ff 100644
@@ -92,13 +92,9 @@ int string_list_has_string(const struct string_list *list, const char *string)
 }
 
 int string_list_find_insert_index(const struct string_list *list, const char *string,
-				  int negative_existing_index)
+				  int *exact_match)
 {
-	int exact_match;
-	int index = get_entry_index(list, string, &exact_match);
-	if (exact_match)
-		index = -1 - (negative_existing_index ? index : 0);
-	return index;
+	return get_entry_index(list, string, exact_match);
 }
 
 struct string_list_item *string_list_lookup(struct string_list *list, const char *string)

string-list.h +1 -1

index 2b438c7733..03c7009472 100644
@@ -174,7 +174,7 @@ void string_list_remove_empty_items(struct string_list *list, int free_util);
 /** Determine if the string_list has a given string or not. */
 int string_list_has_string(const struct string_list *list, const char *string);
 int string_list_find_insert_index(const struct string_list *list, const char *string,
-				  int negative_existing_index);
+				  int *exact_match);
 
 /**
  * Insert a new element to the string_list. The returned pointer can

Signature · 1 line

2.51.0

Junio C Hamano

2025-09-08 16:56 UTC #1 lore raw

Quoted 10 lines · shejialuo

We would return negative index to indicate exact match by converting the original positive index to be "-1 - index" in "string_list_find_insert_index", which requires callers to decode this information.
This is bad due to the following reasons:
1. The callers need to convert the negative index back to the original positive value, which requires the callers to understand the detail of the function.

That has pretty much been the convention so far, not convincing that it is "bad" at all.

Quoted 3 lines

2. As we have to return negative index, we need to specify the return type to be int instead of size_t, which would cause sign compare warnings.

That sounds more like the tail wagging the dog.

Construct your argument the other way around, perhaps?

- We NEED to be able to use the full range of size_t to express the index in the array string_list holds for SUCH AND SUCH REASONS. But string_list_find_insert_index() uses "int", which may not be large enough to cover the range size_t covers.

- In addition, in order to signal that the returned value for a query is about an existing entry in the array, or a location that an entry would be inserted at, we use a signed int and use the bog standard "-1 - index" encoding for this purpose. This further halves the range of valid array index.

- To allow us to use the full range of size_t, use full size_t for the index, and have a separate bit to tell if that index is about an existing entry, or where the queried entry would be stored at if we inserted it.

Your argument does not justify the first point, your desire to use size_t in the first place, and that is what makes it sound backwards, I think..

shejialuo

author

2025-09-15 12:24 UTC #2 lore raw

Quoted 7 lines · Junio C Hamano

Quoted 5 lines · shejialuo
We would return negative index to indicate exact match by converting the original positive index to be "-1 - index" in "string_list_find_insert_index", which requires callers to decode this information.

Quoted 9 lines

Quoted 5 lines
This is bad due to the following reasons:
1. The callers need to convert the negative index back to the original positive value, which requires the callers to understand the detail of the function.
That has pretty much been the convention so far, not convincing that it is "bad" at all.

Good point, I somehow like to use the words containing emotion, which is not suitable. And after googling, I realize that this is the convention.

Quoted 19 lines

Quoted 3 lines
2. As we have to return negative index, we need to specify the return type to be int instead of size_t, which would cause sign compare warnings.
That sounds more like the tail wagging the dog.
Construct your argument the other way around, perhaps?
- We NEED to be able to use the full range of size_t to express the index in the array string_list holds for SUCH AND SUCH REASONS. But string_list_find_insert_index() uses "int", which may not be large enough to cover the range size_t covers.
- In addition, in order to signal that the returned value for a query is about an existing entry in the array, or a location that an entry would be inserted at, we use a signed int and use the bog standard "-1 - index" encoding for this purpose. This further halves the range of valid array index.

Quoted 8 lines

- To allow us to use the full range of size_t, use full size_t for the index, and have a separate bit to tell if that index is about an existing entry, or where the queried entry would be stored at if we inserted it.
Your argument does not justify the first point, your desire to use size_t in the first place, and that is what makes it sound backwards, I think..

Thanks for the suggestion, I will improve this in the next version.

Thanks,
Jialuo