[Top][All Lists]

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

Re: PSPP-BUG: Bug in ll_insert_ordered

From: Ben Pfaff
Subject: Re: PSPP-BUG: Bug in ll_insert_ordered
Date: Sun, 27 Jul 2008 10:23:51 -0700
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux)

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

   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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]