{"thread":{"id":"44747","subject":"[PATCH] string-list: make compare function compatible with qsort(3)","startedAt":"2016-12-21T09:37:17Z","lastAt":"2016-12-29T13:54:15Z","messageCount":5,"participants":["René Scharfe","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"308196","messageId":"c7bac0b7-c555-162f-7880-0355831cee48@web.de","threadId":"44747","inReplyTo":null,"subject":"[PATCH] string-list: make compare function compatible with qsort(3)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-21T09:36:41Z","receivedAt":"2016-12-21T09:37:17Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The cmp member of struct string_list points to a comparison function\nthat is used for sorting and searching of list items.  It takes two\nstring pointers -- like strcmp(3), which is in fact the default;\ncmp_items() provides a qsort(3) compatible interface by passing the\nstring members of two struct string_list_item pointers to cmp.\n\nOne shortcoming is that the comparison function is restricted to working\nwith the string members of items; util is inaccessible to it.  Another\none is that the value of cmp is passed in a global variable to\ncmp_items(), making string_list_sort() non-reentrant.\n\nRemove the intermediate layer, i.e. cmp_items(), make the comparison\nfunctions compatible with qsort(3) and pass them pointers to full items.\nThis allows comparisons to also take the util member into account, and\navoids the need to pass the real comparison function to an intermediate\nfunction, removing the need for a global function.\n\nA downside is that comparison functions take void pointers now and each\nof them needs to cast its arguments to struct string_list_item pointers,\nweakening type safety and adding some repetitive code.  Programmers are\nused to that, however, as that's par for the course with qsort(3).\n\nAlso two unsightly casts are added that remove the const qualifiers of\nstrings while building the structs to pass to the comparison function as\nsearch keys.  It should be safe, though, as we only ever use them for\nreading.\n\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\nAlternative approach to the qsort_s()-based series \"string-list: make\nstring_list_sort() reentrant\".\n\n Documentation/technical/api-string-list.txt |  6 +++--\n builtin/mailsplit.c                         |  5 +++-\n mailmap.c                                   |  5 ++--\n merge-recursive.c                           |  4 ++-\n string-list.c                               | 39 +++++++++++++++--------------\n string-list.h                               |  4 +--\n tmp-objdir.c                                |  4 ++-\n 7 files changed, 39 insertions(+), 28 deletions(-)\n\ndiff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt\nindex c08402b12..39eac59c7 100644\n--- a/Documentation/technical/api-string-list.txt\n+++ b/Documentation/technical/api-string-list.txt\n@@ -205,5 +205,7 @@ Represents the list itself.\n   You should not tamper with it.\n . Setting the `strdup_strings` member to 1 will strdup() the strings\n   before adding them, see above.\n-. The `compare_strings_fn` member is used to specify a custom compare\n-  function, otherwise `strcmp()` is used as the default function.\n+. The `cmp` member is used to specify a custom compare function. It has\n+  the same signature as the one for qsort(1) and is passed two pointers\n+  to `struct string_list_item`. If it's NULL then the `string` members\n+  are compared with `strcmp(1)`; this is the default.\ndiff --git a/builtin/mailsplit.c b/builtin/mailsplit.c\nindex 30681681c..4e72e3128 100644\n--- a/builtin/mailsplit.c\n+++ b/builtin/mailsplit.c\n@@ -147,8 +147,11 @@ static int populate_maildir_list(struct string_list *list, const char *path)\n \treturn ret;\n }\n \n-static int maildir_filename_cmp(const char *a, const char *b)\n+static int maildir_filename_cmp(const void *one, const void *two)\n {\n+\tconst struct string_list_item *item_one = one, *item_two = two;\n+\tconst char *a = item_one->string, *b = item_two->string;\n+\n \twhile (*a && *b) {\n \t\tif (isdigit(*a) && isdigit(*b)) {\n \t\t\tlong int na, nb;\ndiff --git a/mailmap.c b/mailmap.c\nindex c1a79c100..5290b5153 100644\n--- a/mailmap.c\n+++ b/mailmap.c\n@@ -61,9 +61,10 @@ static void free_mailmap_entry(void *p, const char *s)\n  * namemap.cmp until we know no systems that matter have such an\n  * \"unusual\" string.h.\n  */\n-static int namemap_cmp(const char *a, const char *b)\n+static int namemap_cmp(const void *one, const void *two)\n {\n-\treturn strcasecmp(a, b);\n+\tconst struct string_list_item *item_one = one, *item_two = two;\n+\treturn strcasecmp(item_one->string, item_two->string);\n }\n \n static void add_mapping(struct string_list *map,\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex d32720944..4683ba43f 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -390,8 +390,10 @@ static struct string_list *get_unmerged(void)\n \treturn unmerged;\n }\n \n-static int string_list_df_name_compare(const char *one, const char *two)\n+static int string_list_df_name_compare(const void *a, const void *b)\n {\n+\tconst struct string_list_item *item_a = a, *item_b = b;\n+\tconst char *one = item_a->string, *two = item_b->string;\n \tint onelen = strlen(one);\n \tint twolen = strlen(two);\n \t/*\ndiff --git a/string-list.c b/string-list.c\nindex 8c83cac18..c583a04ee 100644\n--- a/string-list.c\n+++ b/string-list.c\n@@ -7,17 +7,26 @@ void string_list_init(struct string_list *list, int strdup_strings)\n \tlist->strdup_strings = strdup_strings;\n }\n \n+static int string_list_item_strcmp(const void *one, const void *two)\n+{\n+\tconst struct string_list_item *item_one = one, *item_two = two;\n+\treturn strcmp(item_one->string, item_two->string);\n+}\n+\n /* if there is no exact match, point to the index where the entry could be\n  * inserted */\n static int get_entry_index(const struct string_list *list, const char *string,\n \t\tint *exact_match)\n {\n \tint left = -1, right = list->nr;\n-\tcompare_strings_fn cmp = list->cmp ? list->cmp : strcmp;\n+\tcompare_fn_t cmp = list->cmp ? list->cmp : string_list_item_strcmp;\n+\tstruct string_list_item key = { NULL };\n+\n+\tkey.string = (char *)string;\n \n \twhile (left + 1 < right) {\n \t\tint middle = (left + right) / 2;\n-\t\tint compare = cmp(string, list->items[middle].string);\n+\t\tint compare = cmp(&key, &list->items[middle]);\n \t\tif (compare < 0)\n \t\t\tright = middle;\n \t\telse if (compare > 0)\n@@ -94,11 +103,11 @@ struct string_list_item *string_list_lookup(struct string_list *list, const char\n \n void string_list_remove_duplicates(struct string_list *list, int free_util)\n {\n+\tcompare_fn_t cmp = list->cmp ? list->cmp : string_list_item_strcmp;\n \tif (list->nr > 1) {\n \t\tint src, dst;\n-\t\tcompare_strings_fn cmp = list->cmp ? list->cmp : strcmp;\n \t\tfor (src = dst = 1; src < list->nr; src++) {\n-\t\t\tif (!cmp(list->items[dst - 1].string, list->items[src].string)) {\n+\t\t\tif (!cmp(&list->items[dst - 1], &list->items[src])) {\n \t\t\t\tif (list->strdup_strings)\n \t\t\t\t\tfree(list->items[src].string);\n \t\t\t\tif (free_util)\n@@ -211,31 +220,23 @@ struct string_list_item *string_list_append(struct string_list *list,\n \t\t\tlist->strdup_strings ? xstrdup(string) : (char *)string);\n }\n \n-/* Yuck */\n-static compare_strings_fn compare_for_qsort;\n-\n-/* Only call this from inside string_list_sort! */\n-static int cmp_items(const void *a, const void *b)\n-{\n-\tconst struct string_list_item *one = a;\n-\tconst struct string_list_item *two = b;\n-\treturn compare_for_qsort(one->string, two->string);\n-}\n-\n void string_list_sort(struct string_list *list)\n {\n-\tcompare_for_qsort = list->cmp ? list->cmp : strcmp;\n-\tQSORT(list->items, list->nr, cmp_items);\n+\tcompare_fn_t cmp = list->cmp ? list->cmp : string_list_item_strcmp;\n+\tQSORT(list->items, list->nr, cmp);\n }\n \n struct string_list_item *unsorted_string_list_lookup(struct string_list *list,\n \t\t\t\t\t\t     const char *string)\n {\n \tstruct string_list_item *item;\n-\tcompare_strings_fn cmp = list->cmp ? list->cmp : strcmp;\n+\tcompare_fn_t cmp = list->cmp ? list->cmp : string_list_item_strcmp;\n+\tstruct string_list_item key = { NULL };\n+\n+\tkey.string = (char *)string;\n \n \tfor_each_string_list_item(item, list)\n-\t\tif (!cmp(string, item->string))\n+\t\tif (!cmp(&key, item))\n \t\t\treturn item;\n \treturn NULL;\n }\ndiff --git a/string-list.h b/string-list.h\nindex d3809a141..073025ddc 100644\n--- a/string-list.h\n+++ b/string-list.h\n@@ -6,13 +6,13 @@ struct string_list_item {\n \tvoid *util;\n };\n \n-typedef int (*compare_strings_fn)(const char *, const char *);\n+typedef int (*compare_fn_t)(const void *, const void *);\n \n struct string_list {\n \tstruct string_list_item *items;\n \tunsigned int nr, alloc;\n \tunsigned int strdup_strings:1;\n-\tcompare_strings_fn cmp; /* NULL uses strcmp() */\n+\tcompare_fn_t cmp; /* NULL uses strcmp() on ->string */\n };\n \n #define STRING_LIST_INIT_NODUP { NULL, 0, 0, 0, NULL }\ndiff --git a/tmp-objdir.c b/tmp-objdir.c\nindex 64435f23a..b6209b199 100644\n--- a/tmp-objdir.c\n+++ b/tmp-objdir.c\n@@ -173,8 +173,10 @@ static int pack_copy_priority(const char *name)\n \treturn 4;\n }\n \n-static int pack_copy_cmp(const char *a, const char *b)\n+static int pack_copy_cmp(const void *one, const void *two)\n {\n+\tconst struct string_list_item *item_one = one, *item_two = two;\n+\tconst char *a = item_one->string, *b = item_two->string;\n \treturn pack_copy_priority(a) - pack_copy_priority(b);\n }\n \n-- \n2.11.0\n\n"},{"id":"308200","messageId":"20161221161220.x3qkcwmuangcdc2l@sigill.intra.peff.net","threadId":"44747","inReplyTo":"c7bac0b7-c555-162f-7880-0355831cee48@web.de","subject":"Re: [PATCH] string-list: make compare function compatible with qsort(3)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-12-21T16:12:20Z","receivedAt":"2016-12-21T16:39:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 21, 2016 at 10:36:41AM +0100, René Scharfe wrote:\n\n> One shortcoming is that the comparison function is restricted to working\n> with the string members of items; util is inaccessible to it.  Another\n> one is that the value of cmp is passed in a global variable to\n> cmp_items(), making string_list_sort() non-reentrant.\n\nI think this approach is OK for string_list, but it doesn't help the\ngeneral case that wants qsort_s() to actually access global data. I\ndon't know how common that is in our codebase, though.\n\nSo I'm fine with it, but I think we might eventually need to revisit the\nqsort_s() thing anyway.\n\n> Remove the intermediate layer, i.e. cmp_items(), make the comparison\n> functions compatible with qsort(3) and pass them pointers to full items.\n> This allows comparisons to also take the util member into account, and\n> avoids the need to pass the real comparison function to an intermediate\n> function, removing the need for a global function.\n\nI'm not sure if access to the util field is really of any value, after\nlooking at it in:\n\n  http://public-inbox.org/git/20161125171546.fa3zpapbjngjcl26@sigill.intra.peff.net/\n\nThough note that if we do take this patch, there are probably one or two\nspots that could switch from QSORT() to string_list_sort().\n\n-Peff\n"},{"id":"308208","messageId":"xmqqy3z9i24x.fsf@gitster.mtv.corp.google.com","threadId":"44747","inReplyTo":"c7bac0b7-c555-162f-7880-0355831cee48@web.de","subject":"Re: [PATCH] string-list: make compare function compatible with qsort(3)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-21T18:10:54Z","receivedAt":"2016-12-21T18:11:04Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> The cmp member of struct string_list points to a comparison function\n> that is used for sorting and searching of list items.  It takes two\n> string pointers -- like strcmp(3), which is in fact the default;\n> cmp_items() provides a qsort(3) compatible interface by passing the\n> string members of two struct string_list_item pointers to cmp.\n>\n> One shortcoming is that the comparison function is restricted to working\n> with the string members of items; util is inaccessible to it.  Another\n> one is that the value of cmp is passed in a global variable to\n> cmp_items(), making string_list_sort() non-reentrant.\n\nI think it is insane to make util accessible to the comparison\nfunction in the first place.\n\nA string-list is primarily a table of strings that can be used to\nquickly look up a string in it (or detect absense of it), and\noptionally set and get the data associated to that string.  If you\nallow the comparison function to take anything other than the string\nitself into account, you can no longer binary search unless you\nforce callers to specify what to put in util when a string is added\nto the table, and you also remove the ability to modify util once a\nstring is added to the table.\n\nThe string-list API exposes the \"append without sorting and then\nsort before starting to look up efficiently with a binary search\",\nand I think that is its biggest misdesign.  Such an optimization\nwould have been hidden from callers in a correctly designed API by\nmaking sure sorting happens lazily when a function that wants to see\na sorted nature of the list for the first time, but somehow we ended\nup with an API with separate functions _insert() and _append() with\nan explicit _sort().  It then leads to unsorted_*_lookup() and\nsimilar mess, that imply that a string-list can be used not as a\nlook-up table but just an unordered bag of items.  In our attempt to\nmake it serve as these two quite different things, it has become\ngood API for neither of its two uses.  The caller is forced to know\nwhen the list is not sorted and unsorted_* variant must be used, for\nexample.  \"Perhaps it makes it even more flexible if we made util\navailable to ordering decision\" is a line of thinking that makes it\neven worse.\n\nI do agree that non-reentrancy is an issue that is worth solving,\nthough.\n\n"},{"id":"308214","messageId":"xmqqd1glhuwh.fsf@gitster.mtv.corp.google.com","threadId":"44747","inReplyTo":"xmqqy3z9i24x.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] string-list: make compare function compatible with qsort(3)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2016-12-21T20:47:10Z","receivedAt":"2016-12-21T20:47:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> I do agree that non-reentrancy is an issue that is worth solving,\n> though.\n\nI sounded overly negative, but I do not think of any way other than\nthis patch to solve the reentrancy issue without using qsort_s().\nBetween the two, my preference is still the latter, but I could be\npersuaded, I would guess.\n\n"},{"id":"308492","messageId":"43c3d83e-80f1-64ea-2ba5-7540b8dd4910@web.de","threadId":"44747","inReplyTo":"20161221161220.x3qkcwmuangcdc2l@sigill.intra.peff.net","subject":"Re: [PATCH] string-list: make compare function compatible with qsort(3)","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2016-12-29T13:53:54Z","receivedAt":"2016-12-29T13:54:15Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 21.12.2016 um 17:12 schrieb Jeff King:\n> On Wed, Dec 21, 2016 at 10:36:41AM +0100, René Scharfe wrote:\n>\n>> One shortcoming is that the comparison function is restricted to working\n>> with the string members of items; util is inaccessible to it.  Another\n>> one is that the value of cmp is passed in a global variable to\n>> cmp_items(), making string_list_sort() non-reentrant.\n>\n> I think this approach is OK for string_list, but it doesn't help the\n> general case that wants qsort_s() to actually access global data. I\n> don't know how common that is in our codebase, though.\n>\n> So I'm fine with it, but I think we might eventually need to revisit the\n> qsort_s() thing anyway.\n\nI have to admit I didn't even consider the possibility that the pattern \nof accessing global variables in qsort(1) compare functions could have \nspread.\n\nAnd indeed, at least ref-filter.c::compare_refs() and \nworktree.c::compare_worktree() so that as well.  The latter uses \nfspathcmp(), which is OK as ignore_case is only set once when reading \nthe config, but the first one looks, well, interesting.  Perhaps a \nsingle ref filter per program is enough?\n\nAnyway, that's a good enough argument for me for adding that newfangled \nC11 function after all..\n\nBtw.: Found with\n\n   git grep 'QSORT.*;$' |\n   sed 's/.* /int /; s/);//' |\n   sort -u |\n   git grep -Ww -f-\n\nand\n\n   git grep -A1 'QSORT.*,$'\n\n>> Remove the intermediate layer, i.e. cmp_items(), make the comparison\n>> functions compatible with qsort(3) and pass them pointers to full items.\n>> This allows comparisons to also take the util member into account, and\n>> avoids the need to pass the real comparison function to an intermediate\n>> function, removing the need for a global function.\n>\n> I'm not sure if access to the util field is really of any value, after\n> looking at it in:\n>\n>   http://public-inbox.org/git/20161125171546.fa3zpapbjngjcl26@sigill.intra.peff.net/\n>\n> Though note that if we do take this patch, there are probably one or two\n> spots that could switch from QSORT() to string_list_sort().\n\nYes, but as you noted in that thread there is not much point in doing \nthat; the only net win is that we can pass a list as a single pointer \ninstead of as base pointer and element count -- the special compare \nfunction needs to be specified anyway (once), somehow.\n\nRené\n"}]}