src/libpspp/ll.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    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, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 /* Embedded, circular doubly linked list. */
  20
  21 /* These library routines have no external dependencies other
  22    than the standard C library.
  23
  24    If you add routines in this file, please add a corresponding
  25    test to ll-test.c.  This test program should achieve 100%
  26    coverage of lines and branches in this code, as reported by
  27    "gcov -b". */
  28
  29 #ifdef HAVE_CONFIG_H
  30 #include <config.h>
  31 #endif
  32
  33 #include <libpspp/ll.h>
  34 #include <assert.h>
  35
  36 /* Returns the number of nodes in LIST (not counting the null
  37    node).  Executes in O(n) time in the length of the list. */
  38 size_t
  39 ll_count (const struct ll_list *list)
  40 {
  41   return ll_count_range (ll_head (list), ll_null (list));
  42 }
  43
  44 /* Removes R0...R1 from their current list
  45    and inserts them just before BEFORE. */
  46 void
  47 ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
  48 {
  49   if (before != r0 && r0 != r1)
  50     {
  51       /* Change exclusive range to inclusive. */
  52       r1 = ll_prev (r1);
  53
  54       /* Remove R0...R1 from its list. */
  55       r0->prev->next = r1->next;
  56       r1->next->prev = r0->prev;
  57
  58       /* Insert R0...R1 before BEFORE. */
  59       r0->prev = before->prev;
  60       r1->next = before;
  61       before->prev->next = r0;
  62       before->prev = r1;
  63     }
  64 }
  65
  66 /* Exchanges the positions of A and B,
  67    which may be in the same list or different lists. */
  68 void
  69 ll_swap (struct ll *a, struct ll *b)
  70 {
  71   if (a != b)
  72     {
  73       if (ll_next (a) != b)
  74         {
  75           struct ll *a_next = ll_remove (a);
  76           struct ll *b_next = ll_remove (b);
  77           ll_insert (b_next, a);
  78           ll_insert (a_next, b);
  79         }
  80       else
  81         {
  82           ll_remove (b);
  83           ll_insert (a, b);
  84         }
  85     }
  86 }
  87
  88 /* Exchanges the positions of A0...A1 and B0...B1,
  89    which may be in the same list or different lists but must not
  90    overlap. */
  91 void
  92 ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
  93 {
  94   if (a0 == a1 || a1 == b0)
  95     ll_splice (a0, b0, b1);
  96   else if (b0 == b1 || b1 == a0)
  97     ll_splice (b0, a0, a1);
  98   else
  99     {
 100       struct ll *x0 = ll_prev (a0), *x1 = a1;
 101       struct ll *y0 = ll_prev (b0), *y1 = b1;
 102       a1 = ll_prev (a1);
 103       b1 = ll_prev (b1);
 104       x0->next = b0;
 105       b0->prev = x0;
 106       b1->next = x1;
 107       x1->prev = b1;
 108       y0->next = a0;
 109       a0->prev = y0;
 110       a1->next = y1;
 111       y1->prev = a1;
 112     }
 113 }
 114
 115 /* Removes from R0...R1 all the nodes that equal TARGET
 116    according to COMPARE given auxiliary data AUX.
 117    Returns the number of nodes removed. */
 118 size_t
 119 ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
 120                  ll_compare_func *compare, void *aux)
 121 {
 122   struct ll *x;
 123   size_t count;
 124
 125   count = 0;
 126   for (x = r0; x != r1; )
 127     if (compare (x, target, aux) == 0)
 128       {
 129         x = ll_remove (x);
 130         count++;
 131       }
 132     else
 133       x = ll_next (x);
 134
 135   return count;
 136 }
 137
 138 /* Removes from R0...R1 all the nodes for which PREDICATE returns
 139    true given auxiliary data AUX.
 140    Returns the number of nodes removed. */
 141 size_t
 142 ll_remove_if (struct ll *r0, struct ll *r1,
 143               ll_predicate_func *predicate, void *aux)
 144 {
 145   struct ll *x;
 146   size_t count;
 147
 148   count = 0;
 149   for (x = r0; x != r1; )
 150     if (predicate (x, aux))
 151       {
 152         x = ll_remove (x);
 153         count++;
 154       }
 155     else
 156       x = ll_next (x);
 157
 158   return count;
 159 }
 160
 161 /* Returns the first node in R0...R1 that equals TARGET
 162    according to COMPARE given auxiliary data AUX.
 163    Returns R1 if no node in R0...R1 equals TARGET. */
 164 struct ll *
 165 ll_find_equal (const struct ll *r0, const struct ll *r1,
 166                const struct ll *target,
 167                ll_compare_func *compare, void *aux)
 168 {
 169   const struct ll *x;
 170
 171   for (x = r0; x != r1; x = ll_next (x))
 172     if (compare (x, target, aux) == 0)
 173       break;
 174   return (struct ll *) x;
 175 }
 176
 177 /* Returns the first node in R0...R1 for which PREDICATE returns
 178    true given auxiliary data AUX.
 179    Returns R1 if PREDICATE does not return true for any node in
 180    R0...R1. */
 181 struct ll *
 182 ll_find_if (const struct ll *r0, const struct ll *r1,
 183             ll_predicate_func *predicate, void *aux)
 184 {
 185   const struct ll *x;
 186
 187   for (x = r0; x != r1; x = ll_next (x))
 188     if (predicate (x, aux))
 189       break;
 190   return (struct ll *) x;
 191 }
 192
 193 /* Compares each pair of adjacent nodes in R0...R1
 194    using COMPARE with auxiliary data AUX
 195    and returns the first node of the first pair that compares
 196    equal.
 197    Returns R1 if no pair compares equal. */
 198 struct ll *
 199 ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
 200                         ll_compare_func *compare, void *aux)
 201 {
 202   if (r0 != r1)
 203     {
 204       const struct ll *x, *y;
 205
 206       for (x = r0, y = ll_next (x); y != r1; x = y, y = ll_next (y))
 207         if (compare (x, y, aux) == 0)
 208           return (struct ll *) x;
 209     }
 210
 211   return (struct ll *) r1;
 212 }
 213
 214 /* Returns the number of nodes in R0...R1.
 215    Executes in O(n) time in the return value. */
 216 size_t
 217 ll_count_range (const struct ll *r0, const struct ll *r1)
 218 {
 219   const struct ll *x;
 220   size_t count;
 221
 222   count = 0;
 223   for (x = r0; x != r1; x = ll_next (x))
 224     count++;
 225   return count;
 226 }
 227
 228 /* Counts and returns the number of nodes in R0...R1 that equal
 229    TARGET according to COMPARE given auxiliary data AUX. */
 230 size_t
 231 ll_count_equal (const struct ll *r0, const struct ll *r1,
 232                 const struct ll *target,
 233                 ll_compare_func *compare, void *aux)
 234 {
 235   const struct ll *x;
 236   size_t count;
 237
 238   count = 0;
 239   for (x = r0; x != r1; x = ll_next (x))
 240     if (compare (x, target, aux) == 0)
 241       count++;
 242   return count;
 243 }
 244
 245 /* Counts and returns the number of nodes in R0...R1 for which
 246    PREDICATE returns true given auxiliary data AUX. */
 247 size_t
 248 ll_count_if (const struct ll *r0, const struct ll *r1,
 249              ll_predicate_func *predicate, void *aux)
 250 {
 251   const struct ll *x;
 252   size_t count;
 253
 254   count = 0;
 255   for (x = r0; x != r1; x = ll_next (x))
 256     if (predicate (x, aux))
 257       count++;
 258   return count;
 259 }
 260
 261 /* Returns the greatest node in R0...R1 according to COMPARE
 262    given auxiliary data AUX.
 263    Returns the first of multiple, equal maxima. */
 264 struct ll *
 265 ll_max (const struct ll *r0, const struct ll *r1,
 266         ll_compare_func *compare, void *aux)
 267 {
 268   const struct ll *max = r0;
 269   if (r0 != r1)
 270     {
 271       const struct ll *x;
 272
 273       for (x = ll_next (r0); x != r1; x = ll_next (x))
 274         if (compare (x, max, aux) > 0)
 275           max = x;
 276     }
 277   return (struct ll *) max;
 278 }
 279
 280 /* Returns the least node in R0...R1 according to COMPARE given
 281    auxiliary data AUX.
 282    Returns the first of multiple, equal minima. */
 283 struct ll *
 284 ll_min (const struct ll *r0, const struct ll *r1,
 285         ll_compare_func *compare, void *aux)
 286 {
 287   const struct ll *min = r0;
 288   if (r0 != r1)
 289     {
 290       const struct ll *x;
 291
 292       for (x = ll_next (r0); x != r1; x = ll_next (x))
 293         if (compare (x, min, aux) < 0)
 294           min = x;
 295     }
 296   return (struct ll *) min;
 297 }
 298
 299 /* Lexicographically compares A0...A1 to B0...B1.
 300    Returns negative if A0...A1 < B0...B1,
 301    zero if A0...A1 == B0...B1, and
 302    positive if A0...A1 > B0...B1
 303    according to COMPARE given auxiliary data AUX. */
 304 int
 305 ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
 306                                  const struct ll *b0, const struct ll *b1,
 307                                  ll_compare_func *compare, void *aux)
 308 {
 309   for (;;)
 310     if (b0 == b1)
 311       return a0 != a1;
 312     else if (a0 == a1)
 313       return -1;
 314     else
 315       {
 316         int cmp = compare (a0, b0, aux);
 317         if (cmp != 0)
 318           return cmp;
 319
 320         a0 = ll_next (a0);
 321         b0 = ll_next (b0);
 322       }
 323 }
 324
 325 /* Calls ACTION with auxiliary data AUX
 326    for every node in R0...R1 in order. */
 327 void
 328 ll_apply (struct ll *r0, struct ll *r1, ll_action_func *action, void *aux)
 329 {
 330   struct ll *ll;
 331
 332   for (ll = r0; ll != r1; ll = ll_next (ll))
 333     action (ll, aux);
 334 }
 335
 336 /* Reverses the order of nodes R0...R1. */
 337 void
 338 ll_reverse (struct ll *r0, struct ll *r1)
 339 {
 340   if (r0 != r1 && ll_next (r0) != r1)
 341     {
 342       struct ll *ll;
 343
 344       for (ll = r0; ll != r1; ll = ll->prev)
 345         {
 346           struct ll *tmp = ll->next;
 347           ll->next = ll->prev;
 348           ll->prev = tmp;
 349         }
 350       r0->next->next = r1->prev;
 351       r1->prev->prev = r0->next;
 352       r0->next = r1;
 353       r1->prev = r0;
 354     }
 355 }
 356
 357 /* Arranges R0...R1 into the lexicographically next greater
 358    permutation.  Returns true if successful.
 359    If R0...R1 is already the lexicographically greatest
 360    permutation of its elements (i.e. ordered from greatest to
 361    smallest), arranges them into the lexicographically least
 362    permutation (i.e. ordered from smallest to largest) and
 363    returns false.
 364    COMPARE with auxiliary data AUX is used to compare nodes. */
 365 bool
 366 ll_next_permutation (struct ll *r0, struct ll *r1,
 367                      ll_compare_func *compare, void *aux)
 368 {
 369   if (r0 != r1)
 370     {
 371       struct ll *i = ll_prev (r1);
 372       while (i != r0)
 373         {
 374           i = ll_prev (i);
 375           if (compare (i, ll_next (i), aux) < 0)
 376             {
 377               struct ll *j;
 378               for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j))
 379                 continue;
 380               ll_swap (i, j);
 381               ll_reverse (ll_next (j), r1);
 382               return true;
 383             }
 384         }
 385
 386       ll_reverse (r0, r1);
 387     }
 388
 389   return false;
 390 }
 391
 392 /* Arranges R0...R1 into the lexicographically next lesser
 393    permutation.  Returns true if successful.
 394    If R0...R1 is already the lexicographically least
 395    permutation of its elements (i.e. ordered from smallest to
 396    greatest), arranges them into the lexicographically greatest
 397    permutation (i.e. ordered from largest to smallest) and
 398    returns false.
 399    COMPARE with auxiliary data AUX is used to compare nodes. */
 400 bool
 401 ll_prev_permutation (struct ll *r0, struct ll *r1,
 402                      ll_compare_func *compare, void *aux)
 403 {
 404   if (r0 != r1)
 405     {
 406       struct ll *i = ll_prev (r1);
 407       while (i != r0)
 408         {
 409           i = ll_prev (i);
 410           if (compare (i, ll_next (i), aux) > 0)
 411             {
 412               struct ll *j;
 413               for (j = ll_prev (r1); compare (i, j, aux) <= 0; j = ll_prev (j))
 414                 continue;
 415               ll_swap (i, j);
 416               ll_reverse (ll_next (j), r1);
 417               return true;
 418             }
 419         }
 420
 421       ll_reverse (r0, r1);
 422     }
 423
 424   return false;
 425 }
 426
 427 /* Sorts R0...R1 into ascending order
 428    according to COMPARE given auxiliary data AUX.
 429    In use, keep in mind that R0 may move during the sort, so that
 430    afterward R0...R1 may denote a different range.
 431    (On the other hand, R1 is fixed in place.)
 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 (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 (struct ll *) partition;
 685 }
 686 \f