Re: Sorting linked lists

[David Kastrup <dak at gnu dot org>]

Joseph Myers <joseph@codesourcery.com> writes:

> On Fri, 6 Nov 2015, David Kastrup wrote:
>
>> The glibc manual does not really show _any_ catering for linked lists as
>> a data structure, but one does not really need more of an identifying
>
> There's search.h and insque / remque, but that's pretty limited and may 
> not be relevant here.

Can't find insque/remque in the 2.19 Info files, but at least the gist
of search.h suggests sticking to the typedef

     int comparison_fn_t (const void *, const void *);

for the comparison function.

The Opengroup specs talk about insque/remque:

    The insque() and remque() functions shall manipulate queues built
    from doubly-linked lists. The queue can be either circular or
    linear. An application using insque() or remque() shall ensure it
    defines a structure in which the first two members of the structure
    are pointers to the same type of structure, and any further members
    are application-specific. The first member of the structure is a
    forward pointer to the next entry in the queue. The second member is
    a backward pointer to the previous entry in the queue. If the queue
    is linear, the queue is terminated with null pointers. The names of
    the structure and of the pointer members are not subject to any
    special restriction.

That's actually rather appalling as an interface.  It does have the
advantage that the actual operation does not require an "offsetof"
parameter for accessing the link, so there is no cost in execution time
for not using something akin to a C++ template or Ada generic.

However, it also means that if you have several orthogonally linked
lists connecting the same structure, you need different accessor
functions for every way of going through the list since the various
pointers don't point to the start of the next structure but to their
respective own link.

-- 
David Kastrup