Re: [PATCH] string-list: make compare function compatible with qsort(3)

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



René Scharfe <l.s.r@xxxxxx> 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.





[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]