PSPP-BUG: Bug in ll_insert_ordered

[John Darrington]

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))

Otherwise the comment ought to read something like:

 /* Inserts NEW_ELEM in the proper position in R0...R1_{-1}, which
 must ... */



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.

J'


-- 
Pgp Public key ID: 1024D/2DE827B3 
fingerprint = 8797 A26D 0854 2EAB 0285  A290 8A67 719C 2DE8 27B3
See http://pgp.mit.edu or any PGP keyserver for public key.

signature.asc
Description: Digital signature