src/libpspp/ll.c

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