{"thread":{"id":"64105","subject":"[PATCH 2/4] string-list: replace negative index encoding with \"exact_match\" parameter","startedAt":"2025-09-07T16:40:36Z","lastAt":"2025-09-15T12:24:39Z","messageCount":3,"participants":["shejialuo","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"525714","messageId":"aL21gazVeyHMeG-s@ArchLinux","threadId":"64105","inReplyTo":null,"subject":"[PATCH 2/4] string-list: replace negative index encoding with \"exact_match\" parameter","fromName":"shejialuo","fromEmail":"shejialuo@gmail.com","sentAt":"2025-09-07T16:40:33Z","receivedAt":"2025-09-07T16:40:36Z","isPatch":true,"sender":{"key":"shejialuo@gmail.com","avatar":"https://avatars.githubusercontent.com/u/56911263?v=4"},"body":"We would return negative index to indicate exact match by converting the\noriginal positive index to be \"-1 - index\" in\n\"string_list_find_insert_index\", which requires callers to decode this\ninformation.\n\nThis is bad due to the following reasons:\n\n1. The callers need to convert the negative index back to the original\n   positive value, which requires the callers to understand the detail\n   of the function.\n2. As we have to return negative index, we need to specify the return\n   type to be `int` instead of `size_t`, which would cause sign compare\n   warnings.\n\nRefactor \"string_list_find_insert_index\" to use an output parameter\n\"exact_match\" for indicating the exact match rather than encoding\nthrough negative return values.\n\nSigned-off-by: shejialuo <shejialuo@gmail.com>\n---\n add-interactive.c | 7 ++++---\n mailmap.c         | 7 +++----\n refs.c            | 2 +-\n string-list.c     | 8 ++------\n string-list.h     | 2 +-\n 5 files changed, 11 insertions(+), 15 deletions(-)\n\ndiff --git a/add-interactive.c b/add-interactive.c\nindex 3e692b47ec..9a42b3b38b 100644\n--- a/add-interactive.c\n+++ b/add-interactive.c\n@@ -221,7 +221,8 @@ static void find_unique_prefixes(struct prefix_item_list *list)\n \n static ssize_t find_unique(const char *string, struct prefix_item_list *list)\n {\n-\tint index = string_list_find_insert_index(&list->sorted, string, 1);\n+\tint exact_match;\n+\tint index = string_list_find_insert_index(&list->sorted, string, &exact_match);\n \tstruct string_list_item *item;\n \n \tif (list->items.nr != list->sorted.nr)\n@@ -229,8 +230,8 @@ static ssize_t find_unique(const char *string, struct prefix_item_list *list)\n \t\t    \" vs %\"PRIuMAX\")\",\n \t\t    (uintmax_t)list->items.nr, (uintmax_t)list->sorted.nr);\n \n-\tif (index < 0)\n-\t\titem = list->sorted.items[-1 - index].util;\n+\tif (exact_match)\n+\t\titem = list->sorted.items[index].util;\n \telse if (index > 0 &&\n \t\t starts_with(list->sorted.items[index - 1].string, string))\n \t\treturn -1;\ndiff --git a/mailmap.c b/mailmap.c\nindex 56c72102d9..253517cdf6 100644\n--- a/mailmap.c\n+++ b/mailmap.c\n@@ -243,10 +243,9 @@ void clear_mailmap(struct string_list *map)\n static struct string_list_item *lookup_prefix(struct string_list *map,\n \t\t\t\t\t      const char *string, size_t len)\n {\n-\tint i = string_list_find_insert_index(map, string, 1);\n-\tif (i < 0) {\n-\t\t/* exact match */\n-\t\ti = -1 - i;\n+\tint exact_match;\n+\tint i = string_list_find_insert_index(map, string, &exact_match);\n+\tif (exact_match) {\n \t\tif (!string[len])\n \t\t\treturn &map->items[i];\n \t\t/*\ndiff --git a/refs.c b/refs.c\nindex 4ff55cf24f..f1ff5bf846 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -1699,7 +1699,7 @@ const char *find_descendant_ref(const char *dirname,\n \t * with dirname (remember, dirname includes the trailing\n \t * slash) and is not in skip, then we have a conflict.\n \t */\n-\tfor (pos = string_list_find_insert_index(extras, dirname, 0);\n+\tfor (pos = string_list_find_insert_index(extras, dirname, NULL);\n \t     pos < extras->nr; pos++) {\n \t\tconst char *extra_refname = extras->items[pos].string;\n \ndiff --git a/string-list.c b/string-list.c\nindex bf358d1a5c..224bc182ff 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -92,13 +92,9 @@ int string_list_has_string(const struct string_list *list, const char *string)\n }\n \n int string_list_find_insert_index(const struct string_list *list, const char *string,\n-\t\t\t\t  int negative_existing_index)\n+\t\t\t\t  int *exact_match)\n {\n-\tint exact_match;\n-\tint index = get_entry_index(list, string, &exact_match);\n-\tif (exact_match)\n-\t\tindex = -1 - (negative_existing_index ? index : 0);\n-\treturn index;\n+\treturn get_entry_index(list, string, exact_match);\n }\n \n struct string_list_item *string_list_lookup(struct string_list *list, const char *string)\ndiff --git a/string-list.h b/string-list.h\nindex 2b438c7733..03c7009472 100644\n--- a/string-list.h\n+++ b/string-list.h\n@@ -174,7 +174,7 @@ void string_list_remove_empty_items(struct string_list *list, int free_util);\n /** Determine if the string_list has a given string or not. */\n int string_list_has_string(const struct string_list *list, const char *string);\n int string_list_find_insert_index(const struct string_list *list, const char *string,\n-\t\t\t\t  int negative_existing_index);\n+\t\t\t\t  int *exact_match);\n \n /**\n  * Insert a new element to the string_list. The returned pointer can\n-- \n2.51.0\n\n"},{"id":"525863","messageId":"xmqqv7lsx4rb.fsf@gitster.g","threadId":"64105","inReplyTo":"aL21gazVeyHMeG-s@ArchLinux","subject":"Re: [PATCH 2/4] string-list: replace negative index encoding with \"exact_match\" parameter","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-09-08T16:56:08Z","receivedAt":"2025-09-08T16:56:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"shejialuo <shejialuo@gmail.com> writes:\n\n> We would return negative index to indicate exact match by converting the\n> original positive index to be \"-1 - index\" in\n> \"string_list_find_insert_index\", which requires callers to decode this\n> information.\n>\n> This is bad due to the following reasons:\n>\n> 1. The callers need to convert the negative index back to the original\n>    positive value, which requires the callers to understand the detail\n>    of the function.\n\nThat has pretty much been the convention so far, not convincing that\nit is \"bad\" at all.\n\n> 2. As we have to return negative index, we need to specify the return\n>    type to be `int` instead of `size_t`, which would cause sign compare\n>    warnings.\n\nThat sounds more like the tail wagging the dog.\n\nConstruct your argument the other way around, perhaps?\n\n - We NEED to be able to use the full range of size_t to express the\n   index in the array string_list holds for SUCH AND SUCH REASONS.\n   But string_list_find_insert_index() uses \"int\", which may not be\n   large enough to cover the range size_t covers.\n\n - In addition, in order to signal that the returned value for a\n   query is about an existing entry in the array, or a location that\n   an entry would be inserted at, we use a signed int and use the\n   bog standard \"-1 - index\" encoding for this purpose.  This\n   further halves the range of valid array index.\n\n - To allow us to use the full range of size_t, use full size_t for\n   the index, and have a separate bit to tell if that index is about\n   an existing entry, or where the queried entry would be stored at\n   if we inserted it.\n\nYour argument does not justify the first point, your desire to use\nsize_t in the first place, and that is what makes it sound\nbackwards, I think..\n"},{"id":"526358","messageId":"aMgFjTqYRB4A9v_4@ArchLinux","threadId":"64105","inReplyTo":"xmqqv7lsx4rb.fsf@gitster.g","subject":"Re: [PATCH 2/4] string-list: replace negative index encoding with \"exact_match\" parameter","fromName":"shejialuo","fromEmail":"shejialuo@gmail.com","sentAt":"2025-09-15T12:24:45Z","receivedAt":"2025-09-15T12:24:39Z","isPatch":true,"sender":{"key":"shejialuo@gmail.com","avatar":"https://avatars.githubusercontent.com/u/56911263?v=4"},"body":"On Mon, Sep 08, 2025 at 09:56:08AM -0700, Junio C Hamano wrote:\n> shejialuo <shejialuo@gmail.com> writes:\n> \n> > We would return negative index to indicate exact match by converting the\n> > original positive index to be \"-1 - index\" in\n> > \"string_list_find_insert_index\", which requires callers to decode this\n> > information.\n> >\n> > This is bad due to the following reasons:\n> >\n> > 1. The callers need to convert the negative index back to the original\n> >    positive value, which requires the callers to understand the detail\n> >    of the function.\n> \n> That has pretty much been the convention so far, not convincing that\n> it is \"bad\" at all.\n> \n\nGood point, I somehow like to use the words containing emotion, which is\nnot suitable. And after googling, I realize that this is the convention.\n\n> > 2. As we have to return negative index, we need to specify the return\n> >    type to be `int` instead of `size_t`, which would cause sign compare\n> >    warnings.\n> \n> That sounds more like the tail wagging the dog.\n> \n> Construct your argument the other way around, perhaps?\n> \n>  - We NEED to be able to use the full range of size_t to express the\n>    index in the array string_list holds for SUCH AND SUCH REASONS.\n>    But string_list_find_insert_index() uses \"int\", which may not be\n>    large enough to cover the range size_t covers.\n> \n>  - In addition, in order to signal that the returned value for a\n>    query is about an existing entry in the array, or a location that\n>    an entry would be inserted at, we use a signed int and use the\n>    bog standard \"-1 - index\" encoding for this purpose.  This\n>    further halves the range of valid array index.\n> \n>  - To allow us to use the full range of size_t, use full size_t for\n>    the index, and have a separate bit to tell if that index is about\n>    an existing entry, or where the queried entry would be stored at\n>    if we inserted it.\n> \n> Your argument does not justify the first point, your desire to use\n> size_t in the first place, and that is what makes it sound\n> backwards, I think..\n\nThanks for the suggestion, I will improve this in the next version.\n\nThanks,\nJialuo\n"}]}