src/libpspp/ll.c

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