lkml.org 
[lkml]   [2019]   [Apr]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH 0/5] simple sort swap function usage improvements
    From
    Date
    [trimming cc list]

    On 30/03/2019 18.16, George Spelvin wrote:
    > Great work; that is indeed a logical follow-on.
    >
    > Reviewed by: George Spelvin <lkml@sdf.org>
    >
    > I you feel even more ambitious, you could try impementing Rasmus
    > Villemoes' idea of having generic *compare* functions. (It's on
    > my to-do list, but I haven't made meaningful progress yet, and I'm
    > happy to pawn it off.)
    >
    > A significant fraction of the time, the sort key is a 4- or 8-byte
    > integer field in a structure at a small offset from the base or
    > list_head.
    >
    > A function pointer < 4096 could be interpreted as encoding:
    > - Key size (1 bit)
    > - Key signedness (1 bit)
    > - Sort direction (1 bit)
    > - Offset (9 bits; +/-256 words = +/-1024 bytes, or 0..511 words from start)
    >
    > With the correct level of preprocessor hackery,
    > SIMPLE_CMP_ASCENDING(struct type, key_field)
    > SIMPLE_LIST_CMP_ASCENDING(struct type, list_field, key_field)
    > SIMPLE_CMP_DESCENDING(struct type, key_field)
    > SIMPLE_LIST_CMP_DESCENDING(struct type, list_field, key_field)

    So, first of all, I don't think there's any reason to do the descending
    thing, at least until there's a (or better, a handful) of potential users.

    Second, I don't think the user should be concerned with the encoding,
    and I'd avoid the shouting, even if it happens to be implemented as
    macros because of the need to do type inspection. So I'd do

    sort_by_key(base, count, key)

    where base must be of type "struct foo *" and key must be the name of a
    member of struct foo. [I think most would be just fine with the default
    swap - if not, that could be added, or we could add another macro also
    taking a swap argument.] So this would expand to

    sort(base, count, sizeof(*base), the-encoding-stuff, NULL)

    Similarly, for list_sort, I'd do

    list_sort_by_key(head, type, list-member, key-member)

    which would expand to

    list_sort((long)offset_diff, head, encode typeof(type->key));

    The latter is the easier one to do because we have the context argument
    that goes unused in the case of a trivial comparison function. The
    former would be just as easy if we decide that we only care about the
    majority which are happy with the default swap function, because in that
    case the offsetof(type, key) could go in the swap argument, and the cmp
    argument would just be the same as for list_sort. Having the two share
    the logic for "key is one of the types we support, or build bug" would
    be good. Perhaps the two tiny list_sort.h and sort.h headers should be
    squashed.

    Rasmus

    \
     
     \ /
      Last update: 2019-04-01 23:08    [W:3.897 / U:0.172 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site