Re: [PATCH] string-list: make compare function compatible with qsort(3)
Am 21.12.2016 um 17:12 schrieb Jeff King: On Wed, Dec 21, 2016 at 10:36:41AM +0100, René Scharfe wrote: One shortcoming is that the comparison function is restricted to working with the string members of items; util is inaccessible to it. Another one is that the value of cmp is passed in a global variable to cmp_items(), making string_list_sort() non-reentrant. I think this approach is OK for string_list, but it doesn't help the general case that wants qsort_s() to actually access global data. I don't know how common that is in our codebase, though. So I'm fine with it, but I think we might eventually need to revisit the qsort_s() thing anyway. I have to admit I didn't even consider the possibility that the pattern of accessing global variables in qsort(1) compare functions could have spread. And indeed, at least ref-filter.c::compare_refs() and worktree.c::compare_worktree() so that as well. The latter uses fspathcmp(), which is OK as ignore_case is only set once when reading the config, but the first one looks, well, interesting. Perhaps a single ref filter per program is enough? Anyway, that's a good enough argument for me for adding that newfangled C11 function after all.. Btw.: Found with git grep 'QSORT.*;$' | sed 's/.* /int /; s/);//' | sort -u | git grep -Ww -f- and git grep -A1 'QSORT.*,$' Remove the intermediate layer, i.e. cmp_items(), make the comparison functions compatible with qsort(3) and pass them pointers to full items. This allows comparisons to also take the util member into account, and avoids the need to pass the real comparison function to an intermediate function, removing the need for a global function. I'm not sure if access to the util field is really of any value, after looking at it in: http://public-inbox.org/git/20161125171546.fa3zpapbjngjc...@sigill.intra.peff.net/ Though note that if we do take this patch, there are probably one or two spots that could switch from QSORT() to string_list_sort(). Yes, but as you noted in that thread there is not much point in doing that; the only net win is that we can pass a list as a single pointer instead of as base pointer and element count -- the special compare function needs to be specified anyway (once), somehow. René
Re: [PATCH] string-list: make compare function compatible with qsort(3)
Junio C Hamano writes: > I do agree that non-reentrancy is an issue that is worth solving, > though. I sounded overly negative, but I do not think of any way other than this patch to solve the reentrancy issue without using qsort_s(). Between the two, my preference is still the latter, but I could be persuaded, I would guess.
Re: [PATCH] string-list: make compare function compatible with qsort(3)
René Scharfe writes: > The cmp member of struct string_list points to a comparison function > that is used for sorting and searching of list items. It takes two > string pointers -- like strcmp(3), which is in fact the default; > cmp_items() provides a qsort(3) compatible interface by passing the > string members of two struct string_list_item pointers to cmp. > > One shortcoming is that the comparison function is restricted to working > with the string members of items; util is inaccessible to it. Another > one is that the value of cmp is passed in a global variable to > cmp_items(), making string_list_sort() non-reentrant. I think it is insane to make util accessible to the comparison function in the first place. A string-list is primarily a table of strings that can be used to quickly look up a string in it (or detect absense of it), and optionally set and get the data associated to that string. If you allow the comparison function to take anything other than the string itself into account, you can no longer binary search unless you force callers to specify what to put in util when a string is added to the table, and you also remove the ability to modify util once a string is added to the table. The string-list API exposes the "append without sorting and then sort before starting to look up efficiently with a binary search", and I think that is its biggest misdesign. Such an optimization would have been hidden from callers in a correctly designed API by making sure sorting happens lazily when a function that wants to see a sorted nature of the list for the first time, but somehow we ended up with an API with separate functions _insert() and _append() with an explicit _sort(). It then leads to unsorted_*_lookup() and similar mess, that imply that a string-list can be used not as a look-up table but just an unordered bag of items. In our attempt to make it serve as these two quite different things, it has become good API for neither of its two uses. The caller is forced to know when the list is not sorted and unsorted_* variant must be used, for example. "Perhaps it makes it even more flexible if we made util available to ordering decision" is a line of thinking that makes it even worse. I do agree that non-reentrancy is an issue that is worth solving, though.
Re: [PATCH] string-list: make compare function compatible with qsort(3)
On Wed, Dec 21, 2016 at 10:36:41AM +0100, René Scharfe wrote: > One shortcoming is that the comparison function is restricted to working > with the string members of items; util is inaccessible to it. Another > one is that the value of cmp is passed in a global variable to > cmp_items(), making string_list_sort() non-reentrant. I think this approach is OK for string_list, but it doesn't help the general case that wants qsort_s() to actually access global data. I don't know how common that is in our codebase, though. So I'm fine with it, but I think we might eventually need to revisit the qsort_s() thing anyway. > Remove the intermediate layer, i.e. cmp_items(), make the comparison > functions compatible with qsort(3) and pass them pointers to full items. > This allows comparisons to also take the util member into account, and > avoids the need to pass the real comparison function to an intermediate > function, removing the need for a global function. I'm not sure if access to the util field is really of any value, after looking at it in: http://public-inbox.org/git/20161125171546.fa3zpapbjngjc...@sigill.intra.peff.net/ Though note that if we do take this patch, there are probably one or two spots that could switch from QSORT() to string_list_sort(). -Peff
