src/libpspp/ll.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2006, 2009 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* Embedded, circular doubly linked list. */
  18
  19 /* These library routines have no external dependencies other
  20    than the standard C library.
  21
  22    If you add routines in this file, please add a corresponding
  23    test to ll-test.c.  This test program should achieve 100%
  24    coverage of lines and branches in this code, as reported by
  25    "gcov -b". */
  26
  27 #ifdef HAVE_CONFIG_H
  28 #include <config.h>
  29 #endif
  30
  31 #include <libpspp/ll.h>
  32 #include <assert.h>
  33
  34 /* Returns the number of nodes in LIST (not counting the null
  35    node).  Executes in O(n) time in the length of the list. */
  36 size_t
  37 ll_count (const struct ll_list *list)
  38 {
  39   return ll_count_range (ll_head (list), ll_null (list));
  40 }
  41
  42 /* Removes R0...R1 from their current list
  43    and inserts them just before BEFORE. */
  44 void
  45 ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
  46 {
  47   if (before != r0 && r0 != r1)
  48     {
  49       /* Change exclusive range to inclusive. */
  50       r1 = ll_prev (r1);
  51
  52       /* Remove R0...R1 from its list. */
  53       r0->prev->next = r1->next;
  54       r1->next->prev = r0->prev;
  55
  56       /* Insert R0...R1 before BEFORE. */
  57       r0->prev = before->prev;
  58       r1->next = before;
  59       before->prev->next = r0;
  60       before->prev = r1;
  61     }
  62 }
  63
  64 /* Exchanges the positions of A and B,
  65    which may be in the same list or different lists. */
  66 void
  67 ll_swap (struct ll *a, struct ll *b)
  68 {
  69   if (a != b)
  70     {
  71       if (ll_next (a) != b)
  72         {
  73           struct ll *a_next = ll_remove (a);
  74           struct ll *b_next = ll_remove (b);
  75           ll_insert (b_next, a);
  76           ll_insert (a_next, b);
  77         }
  78       else
  79         {
  80           ll_remove (b);
  81           ll_insert (a, b);
  82         }
  83     }
  84 }
  85
  86 /* Exchanges the positions of A0...A1 and B0...B1,
  87    which may be in the same list or different lists but must not
  88    overlap. */
  89 void
  90 ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
  91 {
  92   if (a0 == a1 || a1 == b0)
  93     ll_splice (a0, b0, b1);
  94   else if (b0 == b1 || b1 == a0)
  95     ll_splice (b0, a0, a1);
  96   else
  97     {
  98       struct ll *x0 = ll_prev (a0), *x1 = a1;
  99       struct ll *y0 = ll_prev (b0), *y1 = b1;
 100       a1 = ll_prev (a1);
 101       b1 = ll_prev (b1);
 102       x0->next = b0;
 103       b0->prev = x0;
 104       b1->next = x1;
 105       x1->prev = b1;
 106       y0->next = a0;
 107       a0->prev = y0;
 108       a1->next = y1;
 109       y1->prev = a1;
 110     }
 111 }
 112
 113 /* Removes from R0...R1 all the nodes that equal TARGET
 114    according to COMPARE given auxiliary data AUX.
 115    Returns the number of nodes removed. */
 116 size_t
 117 ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
 118                  ll_compare_func *compare, void *aux)
 119 {
 120   struct ll *x;
 121   size_t count;
 122
 123   count = 0;
 124   for (x = r0; x != r1; )
 125     if (compare (x, target, aux) == 0)
 126       {
 127         x = ll_remove (x);
 128         count++;
 129       }
 130     else
 131       x = ll_next (x);
 132
 133   return count;
 134 }
 135
 136 /* Removes from R0...R1 all the nodes for which PREDICATE returns
 137    true given auxiliary data AUX.
 138    Returns the number of nodes removed. */
 139 size_t
 140 ll_remove_if (struct ll *r0, struct ll *r1,
 141               ll_predicate_func *predicate, void *aux)
 142 {
 143   struct ll *x;
 144   size_t count;
 145
 146   count = 0;
 147   for (x = r0; x != r1; )
 148     if (predicate (x, aux))
 149       {
 150         x = ll_remove (x);
 151         count++;
 152       }
 153     else
 154       x = ll_next (x);
 155
 156   return count;
 157 }
 158
 159 /* Returns the first node in R0...R1 that equals TARGET
 160    according to COMPARE given auxiliary data AUX.
 161    Returns R1 if no node in R0...R1 equals TARGET. */
 162 struct ll *
 163 ll_find_equal (const struct ll *r0, const struct ll *r1,
 164                const struct ll *target,
 165                ll_compare_func *compare, void *aux)
 166 {
 167   const struct ll *x;
 168
 169   for (x = r0; x != r1; x = ll_next (x))
 170     if (compare (x, target, aux) == 0)
 171       break;
 172   return CONST_CAST (struct ll *, x);
 173 }
 174
 175 /* Returns the first node in R0...R1 for which PREDICATE returns
 176    true given auxiliary data AUX.
 177    Returns R1 if PREDICATE does not return true for any node in
 178    R0...R1. */
 179 struct ll *
 180 ll_find_if (const struct ll *r0, const struct ll *r1,
 181             ll_predicate_func *predicate, void *aux)
 182 {
 183   const struct ll *x;
 184
 185   for (x = r0; x != r1; x = ll_next (x))
 186     if (predicate (x, aux))
 187       break;
 188   return CONST_CAST (struct ll *, x);
 189 }
 190
 191 /* Compares each pair of adjacent nodes in R0...R1
 192    using COMPARE with auxiliary data AUX
 193    and returns the first node of the first pair that compares
 194    equal.
 195    Returns R1 if no pair compares equal. */
 196 struct ll *
 197 ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
 198                         ll_compare_func *compare, void *aux)
 199 {
 200   if (r0 != r1)
 201     {
 202       const struct ll *x, *y;
 203
 204       for (x = r0, y = ll_next (x); y != r1; x = y, y = ll_next (y))
 205         if (compare (x, y, aux) == 0)
 206           return CONST_CAST (struct ll *, x);
 207     }
 208
 209   return CONST_CAST (struct ll *, r1);
 210 }
 211
 212 /* Returns the number of nodes in R0...R1.
 213    Executes in O(n) time in the return value. */
 214 size_t
 215 ll_count_range (const struct ll *r0, const struct ll *r1)
 216 {
 217   const struct ll *x;
 218   size_t count;
 219
 220   count = 0;
 221   for (x = r0; x != r1; x = ll_next (x))
 222     count++;
 223   return count;
 224 }
 225
 226 /* Counts and returns the number of nodes in R0...R1 that equal
 227    TARGET according to COMPARE given auxiliary data AUX. */
 228 size_t
 229 ll_count_equal (const struct ll *r0, const struct ll *r1,
 230                 const struct ll *target,
 231                 ll_compare_func *compare, void *aux)
 232 {
 233   const struct ll *x;
 234   size_t count;
 235
 236   count = 0;
 237   for (x = r0; x != r1; x = ll_next (x))
 238     if (compare (x, target, aux) == 0)
 239       count++;
 240   return count;
 241 }
 242
 243 /* Counts and returns the number of nodes in R0...R1 for which
 244    PREDICATE returns true given auxiliary data AUX. */
 245 size_t
 246 ll_count_if (const struct ll *r0, const struct ll *r1,
 247              ll_predicate_func *predicate, void *aux)
 248 {
 249   const struct ll *x;
 250   size_t count;
 251
 252   count = 0;
 253   for (x = r0; x != r1; x = ll_next (x))
 254     if (predicate (x, aux))
 255       count++;
 256   return count;
 257 }
 258
 259 /* Returns the greatest node in R0...R1 according to COMPARE
 260    given auxiliary data AUX.
 261    Returns the first of multiple, equal maxima. */
 262 struct ll *
 263 ll_max (const struct ll *r0, const struct ll *r1,
 264         ll_compare_func *compare, void *aux)
 265 {
 266   const struct ll *max = r0;
 267   if (r0 != r1)
 268     {
 269       const struct ll *x;
 270
 271       for (x = ll_next (r0); x != r1; x = ll_next (x))
 272         if (compare (x, max, aux) > 0)
 273           max = x;
 274     }
 275   return CONST_CAST (struct ll *, max);
 276 }
 277
 278 /* Returns the least node in R0...R1 according to COMPARE given
 279    auxiliary data AUX.
 280    Returns the first of multiple, equal minima. */
 281 struct ll *
 282 ll_min (const struct ll *r0, const struct ll *r1,
 283         ll_compare_func *compare, void *aux)
 284 {
 285   const struct ll *min = r0;
 286   if (r0 != r1)
 287     {
 288       const struct ll *x;
 289
 290       for (x = ll_next (r0); x != r1; x = ll_next (x))
 291         if (compare (x, min, aux) < 0)
 292           min = x;
 293     }
 294   return CONST_CAST (struct ll *, min);
 295 }
 296
 297 /* Lexicographically compares A0...A1 to B0...B1.
 298    Returns negative if A0...A1 < B0...B1,
 299    zero if A0...A1 == B0...B1, and
 300    positive if A0...A1 > B0...B1
 301    according to COMPARE given auxiliary data AUX. */
 302 int
 303 ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
 304                                  const struct ll *b0, const struct ll *b1,
 305                                  ll_compare_func *compare, void *aux)
 306 {
 307   for (;;)
 308     if (b0 == b1)
 309       return a0 != a1;
 310     else if (a0 == a1)
 311       return -1;
 312     else
 313       {
 314         int cmp = compare (a0, b0, aux);
 315         if (cmp != 0)
 316           return cmp;
 317
 318         a0 = ll_next (a0);
 319         b0 = ll_next (b0);
 320       }
 321 }
 322
 323 /* Calls ACTION with auxiliary data AUX
 324    for every node in R0...R1 in order. */
 325 void
 326 ll_apply (struct ll *r0, struct ll *r1, ll_action_func *action, void *aux)
 327 {
 328   struct ll *ll;
 329
 330   for (ll = r0; ll != r1; ll = ll_next (ll))
 331     action (ll, aux);
 332 }
 333
 334 /* Reverses the order of nodes R0...R1. */
 335 void
 336 ll_reverse (struct ll *r0, struct ll *r1)
 337 {
 338   if (r0 != r1 && ll_next (r0) != r1)
 339     {
 340       struct ll *ll;
 341
 342       for (ll = r0; ll != r1; ll = ll->prev)
 343         {
 344           struct ll *tmp = ll->next;
 345           ll->next = ll->prev;
 346           ll->prev = tmp;
 347         }
 348       r0->next->next = r1->prev;
 349       r1->prev->prev = r0->next;
 350       r0->next = r1;
 351       r1->prev = r0;
 352     }
 353 }
 354
 355 /* Arranges R0...R1 into the lexicographically next greater
 356    permutation.  Returns true if successful.
 357    If R0...R1 is already the lexicographically greatest
 358    permutation of its elements (i.e. ordered from greatest to
 359    smallest), arranges them into the lexicographically least
 360    permutation (i.e. ordered from smallest to largest) and
 361    returns false.
 362    COMPARE with auxiliary data AUX is used to compare nodes. */
 363 bool
 364 ll_next_permutation (struct ll *r0, struct ll *r1,
 365                      ll_compare_func *compare, void *aux)
 366 {
 367   if (r0 != r1)
 368     {
 369       struct ll *i = ll_prev (r1);
 370       while (i != r0)
 371         {
 372           i = ll_prev (i);
 373           if (compare (i, ll_next (i), aux) < 0)
 374             {
 375               struct ll *j;
 376               for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
 377                 continue;
 378               ll_swap (i, j);
 379               ll_reverse (ll_next (j), r1);
 380               return true;
 381             }
 382         }
 383
 384       ll_reverse (r0, r1);
 385     }
 386
 387   return false;
 388 }
 389
 390 /* Arranges R0...R1 into the lexicographically next lesser
 391    permutation.  Returns true if successful.
 392    If R0...R1 is already the lexicographically least
 393    permutation of its elements (i.e. ordered from smallest to
 394    greatest), arranges them into the lexicographically greatest
 395    permutation (i.e. ordered from largest to smallest) and
 396    returns false.
 397    COMPARE with auxiliary data AUX is used to compare nodes. */
 398 bool
 399 ll_prev_permutation (struct ll *r0, struct ll *r1,
 400                      ll_compare_func *compare, void *aux)
 401 {
 402   if (r0 != r1)
 403     {
 404       struct ll *i = ll_prev (r1);
 405       while (i != r0)
 406         {
 407           i = ll_prev (i);
 408           if (compare (i, ll_next (i), aux) > 0)
 409             {
 410               struct ll *j;
 411               for (j = ll_prev (r1); compare (i, j, aux) <= 0; j = ll_prev (j))
 412                 continue;
 413               ll_swap (i, j);
 414               ll_reverse (ll_next (j), r1);
 415               return true;
 416             }
 417         }
 418
 419       ll_reverse (r0, r1);
 420     }
 421
 422   return false;
 423 }
 424
 425 /* Sorts R0...R1 into ascending order
 426    according to COMPARE given auxiliary data AUX.
 427    In use, keep in mind that R0 may move during the sort, so that
 428    afterward R0...R1 may denote a different range.
 429    (On the other hand, R1 is fixed in place.)
 430    The sort is stable; that is, it will not change the relative
 431    order of nodes that compare equal.
 432    Runs in O(n lg n) time in the number of nodes in the range. */
 433 void
 434 ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux)
 435 {
 436   struct ll *pre_r0;
 437   size_t output_run_cnt;
 438
 439   if (r0 == r1 || ll_next (r0) == r1)
 440     return;
 441
 442   pre_r0 = ll_prev (r0);
 443   do
 444     {
 445       struct ll *a0 = ll_next (pre_r0);
 446       for (output_run_cnt = 1; ; output_run_cnt++)
 447         {
 448           struct ll *a1 = ll_find_run (a0, r1, compare, aux);
 449           struct ll *a2 = ll_find_run (a1, r1, compare, aux);
 450           if (a1 == a2)
 451             break;
 452
 453           a0 = ll_merge (a0, a1, a1, a2, compare, aux);
 454         }
 455     }
 456   while (output_run_cnt > 1);
 457 }
 458
 459 /* Finds the extent of a run of nodes of increasing value
 460    starting at R0 and extending no farther than R1.
 461    Returns the first node in R0...R1 that is less than the
 462    preceding node, or R1 if R0...R1 are arranged in nondecreasing
 463    order. */
 464 struct ll *
 465 ll_find_run (const struct ll *r0, const struct ll *r1,
 466              ll_compare_func *compare, void *aux)
 467 {
 468   if (r0 != r1)
 469     {
 470       do
 471         {
 472           r0 = ll_next (r0);
 473         }
 474       while (r0 != r1 && compare (ll_prev (r0), r0, aux) <= 0);
 475     }
 476
 477   return CONST_CAST (struct ll *, r0);
 478 }
 479
 480 /* Merges B0...B1 into A0...A1 according to COMPARE given
 481    auxiliary data AUX.
 482    The ranges may be in the same list or different lists, but
 483    must not overlap.
 484    Returns the end of the merged range.
 485    The merge is "stable" if A0...A1 is considered to precede
 486    B0...B1, regardless of their actual ordering.
 487    Runs in O(n) time in the total number of nodes in the ranges. */
 488 struct ll *
 489 ll_merge (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1,
 490           ll_compare_func *compare, void *aux)
 491 {
 492   if (a0 != a1 && b0 != b1)
 493     {
 494       a1 = ll_prev (a1);
 495       b1 = ll_prev (b1);
 496       for (;;)
 497         if (compare (a0, b0, aux) <= 0)
 498           {
 499             if (a0 == a1)
 500               {
 501                 ll_splice (ll_next (a0), b0, ll_next (b1));
 502                 return ll_next (b1);
 503               }
 504             a0 = ll_next (a0);
 505           }
 506         else
 507           {
 508             if (b0 != b1)
 509               {
 510                 struct ll *x = b0;
 511                 b0 = ll_remove (b0);
 512                 ll_insert (a0, x);
 513               }
 514             else
 515               {
 516                 ll_splice (a0, b0, ll_next (b0));
 517                 return ll_next (a1);
 518               }
 519           }
 520     }
 521   else
 522     {
 523       ll_splice (a0, b0, b1);
 524       return b1;
 525     }
 526 }
 527
 528 /* Returns true if R0...R1 is sorted in ascending order according
 529    to COMPARE given auxiliary data AUX, false otherwise. */
 530 bool
 531 ll_is_sorted (const struct ll *r0, const struct ll *r1,
 532               ll_compare_func *compare, void *aux)
 533 {
 534   return ll_find_run (r0, r1, compare, aux) == r1;
 535 }
 536
 537 /* Removes all but the first in each group of sequential
 538    duplicates in R0...R1.  Duplicates are determined using
 539    COMPARE given auxiliary data AUX.  Removed duplicates are
 540    inserted before DUPS if it is nonnull; otherwise, their
 541    identities are lost.
 542    Only sequential duplicates are removed.  ll_sort() may be used
 543    to bring duplicates together, or ll_sort_unique() can do both
 544    at once. */
 545 size_t
 546 ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
 547            ll_compare_func *compare, void *aux)
 548 {
 549   size_t count = 0;
 550
 551   if (r0 != r1)
 552     {
 553       struct ll *x = r0;
 554       for (;;)
 555         {
 556           struct ll *y = ll_next (x);
 557           if (y == r1)
 558             {
 559               count++;
 560               break;
 561             }
 562
 563           if (compare (x, y, aux) == 0)
 564             {
 565               ll_remove (y);
 566               if (dups != NULL)
 567                 ll_insert (dups, y);
 568             }
 569           else
 570             {
 571               x = y;
 572               count++;
 573             }
 574         }
 575     }
 576
 577   return count;
 578 }
 579
 580 /* Sorts R0...R1 and removes duplicates.
 581    Removed duplicates are inserted before DUPS if it is nonnull;
 582    otherwise, their identities are lost.
 583    Comparisons are made with COMPARE given auxiliary data AUX.
 584    In use, keep in mind that R0 may move during the sort, so that
 585    afterward R0...R1 may denote a different range.
 586    (On the other hand, R1 is fixed in place.)
 587    Runs in O(n lg n) time in the number of nodes in the range. */
 588 void
 589 ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
 590                 ll_compare_func *compare, void *aux)
 591 {
 592   struct ll *pre_r0 = ll_prev (r0);
 593   ll_sort (r0, r1, compare, aux);
 594   ll_unique (ll_next (pre_r0), r1, dups, compare, aux);
 595 }
 596
 597 /* Inserts NEW_ELEM in the proper position in R0...R1, which must
 598    be sorted according to COMPARE given auxiliary data AUX.
 599    If NEW_ELEM is equal to one or more existing nodes in R0...R1,
 600    then it is inserted after the existing nodes it equals.
 601    Runs in O(n) time in the number of nodes in the range. */
 602 void
 603 ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
 604                    ll_compare_func *compare, void *aux)
 605 {
 606   struct ll *x;
 607
 608   for (x = r0; x != r1; x = ll_next (x))
 609     if (compare (x, new_elem, aux) > 0)
 610       break;
 611   ll_insert (x, new_elem);
 612 }
 613
 614 /* Partitions R0...R1 into those nodes for which PREDICATE given
 615    auxiliary data AUX returns true, followed by those for which
 616    PREDICATE returns false.
 617    Returns the first node in the "false" group, or R1 if
 618    PREDICATE is true for every node in R0...R1.
 619    The partition is "stable" in that the nodes in each group
 620    retain their original relative order.
 621    Runs in O(n) time in the number of nodes in the range. */
 622 struct ll *
 623 ll_partition (struct ll *r0, struct ll *r1,
 624               ll_predicate_func *predicate, void *aux)
 625 {
 626   struct ll *t0, *t1;
 627
 628   for (;;)
 629     {
 630       if (r0 == r1)
 631         return r0;
 632       else if (!predicate (r0, aux))
 633         break;
 634
 635       r0 = ll_next (r0);
 636     }
 637
 638   for (t0 = r0;; t0 = t1)
 639     {
 640       do
 641         {
 642           t0 = ll_next (t0);
 643           if (t0 == r1)
 644             return r0;
 645         }
 646       while (!predicate (t0, aux));
 647
 648       t1 = t0;
 649       do
 650         {
 651           t1 = ll_next (t1);
 652           if (t1 == r1)
 653             {
 654               ll_splice (r0, t0, t1);
 655               return r0;
 656             }
 657         }
 658       while (predicate (t1, aux));
 659
 660       ll_splice (r0, t0, t1);
 661     }
 662 }
 663
 664 /* Verifies that R0...R1 is parititioned into a sequence of nodes
 665    for which PREDICATE given auxiliary data AUX returns true,
 666    followed by those for which PREDICATE returns false.
 667    Returns a null pointer if R0...R1 is not partitioned this way.
 668    Otherwise, returns the first node in the "false" group, or R1
 669    if PREDICATE is true for every node in R0...R1. */
 670 struct ll *
 671 ll_find_partition (const struct ll *r0, const struct ll *r1,
 672                    ll_predicate_func *predicate, void *aux)
 673 {
 674   const struct ll *partition, *x;
 675
 676   for (partition = r0; partition != r1; partition = ll_next (partition))
 677     if (!predicate (partition, aux))
 678       break;
 679
 680   for (x = partition; x != r1; x = ll_next (x))
 681     if (predicate (x, aux))
 682       return NULL;
 683
 684   return CONST_CAST (struct ll *, partition);
 685 }
 686 \f