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    The sort is stable; that is, it will not change the relative
 433    order of nodes that compare equal.
 434    Runs in O(n lg n) time in the number of nodes in the range. */
 435 void
 436 ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux)
 437 {
 438   struct ll *pre_r0;
 439   size_t output_run_cnt;
 440
 441   if (r0 == r1 || ll_next (r0) == r1)
 442     return;
 443
 444   pre_r0 = ll_prev (r0);
 445   do
 446     {
 447       struct ll *a0 = ll_next (pre_r0);
 448       for (output_run_cnt = 1; ; output_run_cnt++)
 449         {
 450           struct ll *a1 = ll_find_run (a0, r1, compare, aux);
 451           struct ll *a2 = ll_find_run (a1, r1, compare, aux);
 452           if (a1 == a2)
 453             break;
 454
 455           a0 = ll_merge (a0, a1, a1, a2, compare, aux);
 456         }
 457     }
 458   while (output_run_cnt > 1);
 459 }
 460
 461 /* Finds the extent of a run of nodes of increasing value
 462    starting at R0 and extending no farther than R1.
 463    Returns the first node in R0...R1 that is less than the
 464    preceding node, or R1 if R0...R1 are arranged in nondecreasing
 465    order. */
 466 struct ll *
 467 ll_find_run (const struct ll *r0, const struct ll *r1,
 468              ll_compare_func *compare, void *aux)
 469 {
 470   if (r0 != r1)
 471     {
 472       do
 473         {
 474           r0 = ll_next (r0);
 475         }
 476       while (r0 != r1 && compare (ll_prev (r0), r0, aux) <= 0);
 477     }
 478
 479   return (struct ll *) r0;
 480 }
 481
 482 /* Merges B0...B1 into A0...A1 according to COMPARE given
 483    auxiliary data AUX.
 484    The ranges may be in the same list or different lists, but
 485    must not overlap.
 486    Returns the end of the merged range.
 487    The merge is "stable" if A0...A1 is considered to precede
 488    B0...B1, regardless of their actual ordering.
 489    Runs in O(n) time in the total number of nodes in the ranges. */
 490 struct ll *
 491 ll_merge (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1,
 492           ll_compare_func *compare, void *aux)
 493 {
 494   if (a0 != a1 && b0 != b1)
 495     {
 496       a1 = ll_prev (a1);
 497       b1 = ll_prev (b1);
 498       for (;;)
 499         if (compare (a0, b0, aux) <= 0)
 500           {
 501             if (a0 == a1)
 502               {
 503                 ll_splice (ll_next (a0), b0, ll_next (b1));
 504                 return ll_next (b1);
 505               }
 506             a0 = ll_next (a0);
 507           }
 508         else
 509           {
 510             if (b0 != b1)
 511               {
 512                 struct ll *x = b0;
 513                 b0 = ll_remove (b0);
 514                 ll_insert (a0, x);
 515               }
 516             else
 517               {
 518                 ll_splice (a0, b0, ll_next (b0));
 519                 return ll_next (a1);
 520               }
 521           }
 522     }
 523   else
 524     {
 525       ll_splice (a0, b0, b1);
 526       return b1;
 527     }
 528 }
 529
 530 /* Returns true if R0...R1 is sorted in ascending order according
 531    to COMPARE given auxiliary data AUX, false otherwise. */
 532 bool
 533 ll_is_sorted (const struct ll *r0, const struct ll *r1,
 534               ll_compare_func *compare, void *aux)
 535 {
 536   return ll_find_run (r0, r1, compare, aux) == r1;
 537 }
 538
 539 /* Removes all but the first in each group of sequential
 540    duplicates in R0...R1.  Duplicates are determined using
 541    COMPARE given auxiliary data AUX.  Removed duplicates are
 542    inserted before DUPS if it is nonnull; otherwise, their
 543    identities are lost.
 544    Only sequential duplicates are removed.  ll_sort() may be used
 545    to bring duplicates together, or ll_sort_unique() can do both
 546    at once. */
 547 size_t
 548 ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
 549            ll_compare_func *compare, void *aux)
 550 {
 551   size_t count = 0;
 552
 553   if (r0 != r1)
 554     {
 555       struct ll *x = r0;
 556       for (;;)
 557         {
 558           struct ll *y = ll_next (x);
 559           if (y == r1)
 560             {
 561               count++;
 562               break;
 563             }
 564
 565           if (compare (x, y, aux) == 0)
 566             {
 567               ll_remove (y);
 568               if (dups != NULL)
 569                 ll_insert (dups, y);
 570             }
 571           else
 572             {
 573               x = y;
 574               count++;
 575             }
 576         }
 577     }
 578
 579   return count;
 580 }
 581
 582 /* Sorts R0...R1 and removes duplicates.
 583    Removed duplicates are inserted before DUPS if it is nonnull;
 584    otherwise, their identities are lost.
 585    Comparisons are made with COMPARE given auxiliary data AUX.
 586    In use, keep in mind that R0 may move during the sort, so that
 587    afterward R0...R1 may denote a different range.
 588    (On the other hand, R1 is fixed in place.)
 589    Runs in O(n lg n) time in the number of nodes in the range. */
 590 void
 591 ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
 592                 ll_compare_func *compare, void *aux)
 593 {
 594   struct ll *pre_r0 = ll_prev (r0);
 595   ll_sort (r0, r1, compare, aux);
 596   ll_unique (ll_next (pre_r0), r1, dups, compare, aux);
 597 }
 598
 599 /* Inserts NEW_ELEM in the proper position in R0...R1, which must
 600    be sorted according to COMPARE given auxiliary data AUX.
 601    If NEW_ELEM is equal to one or more existing nodes in R0...R1,
 602    then it is inserted after the existing nodes it equals.
 603    Runs in O(n) time in the number of nodes in the range. */
 604 void
 605 ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
 606                    ll_compare_func *compare, void *aux)
 607 {
 608   struct ll *x;
 609
 610   for (x = r0; x != r1; x = ll_next (x))
 611     if (compare (x, new_elem, aux) > 0)
 612       break;
 613   ll_insert (x, new_elem);
 614 }
 615
 616 /* Partitions R0...R1 into those nodes for which PREDICATE given
 617    auxiliary data AUX returns true, followed by those for which
 618    PREDICATE returns false.
 619    Returns the first node in the "false" group, or R1 if
 620    PREDICATE is true for every node in R0...R1.
 621    The partition is "stable" in that the nodes in each group
 622    retain their original relative order.
 623    Runs in O(n) time in the number of nodes in the range. */
 624 struct ll *
 625 ll_partition (struct ll *r0, struct ll *r1,
 626               ll_predicate_func *predicate, void *aux)
 627 {
 628   struct ll *t0, *t1;
 629
 630   for (;;)
 631     {
 632       if (r0 == r1)
 633         return r0;
 634       else if (!predicate (r0, aux))
 635         break;
 636
 637       r0 = ll_next (r0);
 638     }
 639
 640   for (t0 = r0;; t0 = t1)
 641     {
 642       do
 643         {
 644           t0 = ll_next (t0);
 645           if (t0 == r1)
 646             return r0;
 647         }
 648       while (!predicate (t0, aux));
 649
 650       t1 = t0;
 651       do
 652         {
 653           t1 = ll_next (t1);
 654           if (t1 == r1)
 655             {
 656               ll_splice (r0, t0, t1);
 657               return r0;
 658             }
 659         }
 660       while (predicate (t1, aux));
 661
 662       ll_splice (r0, t0, t1);
 663     }
 664 }
 665
 666 /* Verifies that R0...R1 is parititioned into a sequence of nodes
 667    for which PREDICATE given auxiliary data AUX returns true,
 668    followed by those for which PREDICATE returns false.
 669    Returns a null pointer if R0...R1 is not partitioned this way.
 670    Otherwise, returns the first node in the "false" group, or R1
 671    if PREDICATE is true for every node in R0...R1. */
 672 struct ll *
 673 ll_find_partition (const struct ll *r0, const struct ll *r1,
 674                    ll_predicate_func *predicate, void *aux)
 675 {
 676   const struct ll *partition, *x;
 677
 678   for (partition = r0; partition != r1; partition = ll_next (partition))
 679     if (!predicate (partition, aux))
 680       break;
 681
 682   for (x = partition; x != r1; x = ll_next (x))
 683     if (predicate (x, aux))
 684       return NULL;
 685
 686   return (struct ll *) partition;
 687 }
 688 \f