Re: PSPP-BUG: Bug in ll_insert_ordered

[Ben Pfaff]

John Darrington <address@hidden> writes:

> From src/libpspp/ll.c :
>
> /* Inserts NEW_ELEM in the proper position in R0...R1, which must
>    be sorted according to COMPARE given auxiliary data AUX.
>    If NEW_ELEM is equal to one or more existing nodes in R0...R1,
>    then it is inserted after the existing nodes it equals.
>    Runs in O(n) time in the number of nodes in the range. */
> void
> ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
>                    ll_compare_func *compare, void *aux)
> {
>   struct ll *x;
>
>   for (x = r0; x != r1; x = ll_next (x))
>     if (compare (x, new_elem, aux) > 0)
>       break;
>
>   ll_insert (x, new_elem);
> }
>
>
> The comment here doesn't agree with the code.
>
> If R1 is supposed to be an inclusive limit, the loop condition should be
>
>   for (x = r0; x != ll_next (r1); x = ll_next (x))

R1 is not supposed to be an inclusive limit.  The ll.h header
says:

   Many list functions take ranges of nodes as arguments.  Ranges
   are "half-open"; that is, R0...R1 includes R0 but not R1.  A
   range whose endpoints are the same (e.g. R0...R0) contains no
   nodes at all.

> As a side issue, it would be really convenient if R0 and R1 were
> permitted to be NULL, so as to allow insertion into an empty list.

This is already possible:
    ll_insert_ordered (ll_head (list), ll_null (list), new_elem,
                       compare, aux);
-- 
Only wimps use tape backup: _real_ men just upload their important stuff
on ftp, and let the rest of the world mirror it ;)
        -- Linus Torvalds