src/libpspp/llx.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 /* External, circular doubly linked list. */
  18
  19 /* These library routines have no external dependencies, other
  20    than ll.c and the standard C library.
  21
  22    If you add routines in this file, please add a corresponding
  23    test to llx-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/llx.h"
  32 #include "libpspp/compiler.h"
  33 #include <assert.h>
  34 #include <stdlib.h>
  35
  36 /* Destroys LIST and frees all of its nodes using MANAGER.
  37    If DESTRUCTOR is non-null, each node in the list will be
  38    passed to it in list order, with AUX as auxiliary data, before
  39    that node is destroyed. */
  40 void
  41 llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux,
  42              const struct llx_manager *manager)
  43 {
  44   struct llx *llx, *next;
  45
  46   for (llx = llx_head (list); llx != llx_null (list); llx = next)
  47     {
  48       next = llx_next (llx);
  49       if (destructor != NULL)
  50         destructor (llx_data (llx), aux);
  51       manager->release (llx, manager->aux);
  52     }
  53 }
  54
  55 /* Returns the number of nodes in LIST (not counting the null
  56    node).  Executes in O(n) time in the length of the list. */
  57 size_t
  58 llx_count (const struct llx_list *list)
  59 {
  60   return llx_count_range (llx_head (list), llx_null (list));
  61 }
  62
  63 /* Inserts DATA at the head of LIST.
  64    Returns the new node (allocated with MANAGER), or a null
  65    pointer if memory allocation failed. */
  66 struct llx *
  67 llx_push_head (struct llx_list *list, void *data,
  68                const struct llx_manager *manager)
  69 {
  70   return llx_insert (llx_head (list), data, manager);
  71 }
  72
  73 /* Inserts DATA at the tail of LIST.
  74    Returns the new node (allocated with MANAGER), or a null
  75    pointer if memory allocation failed. */
  76 struct llx *
  77 llx_push_tail (struct llx_list *list, void *data,
  78                const struct llx_manager *manager)
  79 {
  80   return llx_insert (llx_null (list), data, manager);
  81 }
  82
  83 /* Removes the first node in LIST, which must not be empty,
  84    and returns the data that the node contained.
  85    Frees the node removed with MANAGER. */
  86 void *
  87 llx_pop_head (struct llx_list *list, const struct llx_manager *manager)
  88 {
  89   struct llx *llx = llx_from_ll (ll_head (&list->ll_list));
  90   void *data = llx_data (llx);
  91   llx_remove (llx, manager);
  92   return data;
  93 }
  94
  95 /* Removes the last node in LIST, which must not be empty,
  96    and returns the data that the node contained.
  97    Frees the node removed with MANAGER. */
  98 void *
  99 llx_pop_tail (struct llx_list *list, const struct llx_manager *manager)
 100 {
 101   struct llx *llx = llx_from_ll (ll_tail (&list->ll_list));
 102   void *data = llx_data (llx);
 103   llx_remove (llx, manager);
 104   return data;
 105 }
 106
 107 /* Inserts DATA before BEFORE.
 108    Returns the new node (allocated with MANAGER), or a null
 109    pointer if memory allocation failed. */
 110 struct llx *
 111 llx_insert (struct llx *before, void *data, const struct llx_manager *manager)
 112 {
 113   struct llx *llx = manager->allocate (manager->aux);
 114   if (llx != NULL)
 115     {
 116       llx->data = data;
 117       ll_insert (&before->ll, &llx->ll);
 118     }
 119   return llx;
 120 }
 121
 122 /* Removes R0...R1 from their current list
 123    and inserts them just before BEFORE. */
 124 void
 125 llx_splice (struct llx *before, struct llx *r0, struct llx *r1)
 126 {
 127   ll_splice (&before->ll, &r0->ll, &r1->ll);
 128 }
 129
 130 /* Exchanges the positions of A and B,
 131    which may be in the same list or different lists. */
 132 void
 133 llx_swap (struct llx *a, struct llx *b)
 134 {
 135   ll_swap (&a->ll, &b->ll);
 136 }
 137
 138 /* Exchanges the positions of A0...A1 and B0...B1,
 139    which may be in the same list or different lists but must not
 140    overlap. */
 141 void
 142 llx_swap_range (struct llx *a0, struct llx *a1,
 143                 struct llx *b0, struct llx *b1)
 144 {
 145   ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll);
 146 }
 147
 148 /* Removes LLX from its list
 149    and returns the node that formerly followed it.
 150    Frees the node removed with MANAGER. */
 151 struct llx *
 152 llx_remove (struct llx *llx, const struct llx_manager *manager)
 153 {
 154   struct llx *next = llx_next (llx);
 155   ll_remove (&llx->ll);
 156   manager->release (llx, manager->aux);
 157   return next;
 158 }
 159
 160 /* Removes R0...R1 from their list.
 161    Frees the removed nodes with MANAGER. */
 162 void
 163 llx_remove_range (struct llx *r0, struct llx *r1,
 164                   const struct llx_manager *manager)
 165 {
 166   struct llx *llx;
 167
 168   for (llx = r0; llx != r1; )
 169     llx = llx_remove (llx, manager);
 170 }
 171
 172 /* Removes from R0...R1 all the nodes that equal TARGET
 173    according to COMPARE given auxiliary data AUX.
 174    Frees the removed nodes with MANAGER.
 175    Returns the number of nodes removed. */
 176 size_t
 177 llx_remove_equal (struct llx *r0, struct llx *r1, const void *target,
 178                   llx_compare_func *compare, void *aux,
 179                   const struct llx_manager *manager)
 180 {
 181   struct llx *x;
 182   size_t count;
 183
 184   count = 0;
 185   for (x = r0; x != r1; )
 186     if (compare (llx_data (x), target, aux) == 0)
 187       {
 188         x = llx_remove (x, manager);
 189         count++;
 190       }
 191     else
 192       x = llx_next (x);
 193
 194   return count;
 195 }
 196
 197 /* Removes from R0...R1 all the nodes for which PREDICATE returns
 198    true given auxiliary data AUX.
 199    Frees the removed nodes with MANAGER.
 200    Returns the number of nodes removed. */
 201 size_t
 202 llx_remove_if (struct llx *r0, struct llx *r1,
 203                llx_predicate_func *predicate, void *aux,
 204                const struct llx_manager *manager)
 205 {
 206   struct llx *x;
 207   size_t count;
 208
 209   count = 0;
 210   for (x = r0; x != r1; )
 211     if (predicate (llx_data (x), aux))
 212       {
 213         x = llx_remove (x, manager);
 214         count++;
 215       }
 216     else
 217       x = llx_next (x);
 218
 219   return count;
 220 }
 221
 222 /* Returns the first node in R0...R1 that has data TARGET.
 223    Returns NULL if no node in R0...R1 equals TARGET. */
 224 struct llx *
 225 llx_find (const struct llx *r0, const struct llx *r1, const void *target)
 226 {
 227   const struct llx *x;
 228
 229   for (x = r0; x != r1; x = llx_next (x))
 230     if (llx_data (x) == target)
 231       return CONST_CAST (struct llx *, x);
 232
 233   return NULL;
 234 }
 235
 236 /* Returns the first node in R0...R1 that equals TARGET
 237    according to COMPARE given auxiliary data AUX.
 238    Returns R1 if no node in R0...R1 equals TARGET. */
 239 struct llx *
 240 llx_find_equal (const struct llx *r0, const struct llx *r1,
 241                 const void *target,
 242                 llx_compare_func *compare, void *aux)
 243 {
 244   const struct llx *x;
 245
 246   for (x = r0; x != r1; x = llx_next (x))
 247     if (compare (llx_data (x), target, aux) == 0)
 248       break;
 249   return CONST_CAST (struct llx *, x);
 250 }
 251
 252 /* Returns the first node in R0...R1 for which PREDICATE returns
 253    true given auxiliary data AUX.
 254    Returns R1 if PREDICATE does not return true for any node in
 255    R0...R1 . */
 256 struct llx *
 257 llx_find_if (const struct llx *r0, const struct llx *r1,
 258              llx_predicate_func *predicate, void *aux)
 259 {
 260   const struct llx *x;
 261
 262   for (x = r0; x != r1; x = llx_next (x))
 263     if (predicate (llx_data (x), aux))
 264       break;
 265   return CONST_CAST (struct llx *, x);
 266 }
 267
 268 /* Compares each pair of adjacent nodes in R0...R1
 269    using COMPARE with auxiliary data AUX
 270    and returns the first node of the first pair that compares
 271    equal.
 272    Returns R1 if no pair compares equal. */
 273 struct llx *
 274 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
 275                          llx_compare_func *compare, void *aux)
 276 {
 277   if (r0 != r1)
 278     {
 279       const struct llx *x, *y;
 280
 281       for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
 282         if (compare (llx_data (x), llx_data (y), aux) == 0)
 283           return CONST_CAST (struct llx *, x);
 284     }
 285
 286   return CONST_CAST (struct llx *, r1);
 287 }
 288
 289 /* Returns the number of nodes in R0...R1.
 290    Executes in O(n) time in the return value. */
 291 size_t
 292 llx_count_range (const struct llx *r0, const struct llx *r1)
 293 {
 294   return ll_count_range (&r0->ll, &r1->ll);
 295 }
 296
 297 /* Counts and returns the number of nodes in R0...R1 that equal
 298    TARGET according to COMPARE given auxiliary data AUX. */
 299 size_t
 300 llx_count_equal (const struct llx *r0, const struct llx *r1,
 301                  const void *target,
 302                  llx_compare_func *compare, void *aux)
 303 {
 304   const struct llx *x;
 305   size_t count;
 306
 307   count = 0;
 308   for (x = r0; x != r1; x = llx_next (x))
 309     if (compare (llx_data (x), target, aux) == 0)
 310       count++;
 311   return count;
 312 }
 313
 314 /* Counts and returns the number of nodes in R0...R1 for which
 315    PREDICATE returns true given auxiliary data AUX. */
 316 size_t
 317 llx_count_if (const struct llx *r0, const struct llx *r1,
 318               llx_predicate_func *predicate, void *aux)
 319 {
 320   const struct llx *x;
 321   size_t count;
 322
 323   count = 0;
 324   for (x = r0; x != r1; x = llx_next (x))
 325     if (predicate (llx_data (x), aux))
 326       count++;
 327   return count;
 328 }
 329
 330 /* Returns the greatest node in R0...R1 according to COMPARE
 331    given auxiliary data AUX.
 332    Returns the first of multiple, equal maxima. */
 333 struct llx *
 334 llx_max (const struct llx *r0, const struct llx *r1,
 335          llx_compare_func *compare, void *aux)
 336 {
 337   const struct llx *max = r0;
 338   if (r0 != r1)
 339     {
 340       struct llx *x;
 341
 342       for (x = llx_next (r0); x != r1; x = llx_next (x))
 343         if (compare (llx_data (x), llx_data (max), aux) > 0)
 344           max = x;
 345     }
 346   return CONST_CAST (struct llx *, max);
 347 }
 348
 349 /* Returns the least node in R0...R1 according to COMPARE given
 350    auxiliary data AUX.
 351    Returns the first of multiple, equal minima. */
 352 struct llx *
 353 llx_min (const struct llx *r0, const struct llx *r1,
 354          llx_compare_func *compare, void *aux)
 355 {
 356   const struct llx *min = r0;
 357   if (r0 != r1)
 358     {
 359       struct llx *x;
 360
 361       for (x = llx_next (r0); x != r1; x = llx_next (x))
 362         if (compare (llx_data (x), llx_data (min), aux) < 0)
 363           min = x;
 364     }
 365   return CONST_CAST (struct llx *, min);
 366 }
 367
 368 /* Lexicographically compares A0...A1 to B0...B1.
 369    Returns negative if A0...A1 < B0...B1,
 370    zero if A0...A1 == B0...B1, and
 371    positive if A0...A1 > B0...B1
 372    according to COMPARE given auxiliary data AUX. */
 373 int
 374 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
 375                                   const struct llx *b0, const struct llx *b1,
 376                                   llx_compare_func *compare, void *aux)
 377 {
 378   for (;;)
 379     if (b0 == b1)
 380       return a0 != a1;
 381     else if (a0 == a1)
 382       return -1;
 383     else
 384       {
 385         int cmp = compare (llx_data (a0), llx_data (b0), aux);
 386         if (cmp != 0)
 387           return cmp;
 388
 389         a0 = llx_next (a0);
 390         b0 = llx_next (b0);
 391       }
 392 }
 393
 394 /* Calls ACTION with auxiliary data AUX
 395    for every node in R0...R1 in order. */
 396 void
 397 llx_apply (struct llx *r0, struct llx *r1,
 398            llx_action_func *action, void *aux)
 399 {
 400   struct llx *llx;
 401
 402   for (llx = r0; llx != r1; llx = llx_next (llx))
 403     action (llx_data (llx), aux);
 404 }
 405
 406 /* Reverses the order of nodes R0...R1. */
 407 void
 408 llx_reverse (struct llx *r0, struct llx *r1)
 409 {
 410   ll_reverse (&r0->ll, &r1->ll);
 411 }
 412
 413 /* Arranges R0...R1 into the lexicographically next greater
 414    permutation.  Returns true if successful.
 415    If R0...R1 is already the lexicographically greatest
 416    permutation of its elements (i.e. ordered from greatest to
 417    smallest), arranges them into the lexicographically least
 418    permutation (i.e. ordered from smallest to largest) and
 419    returns false.
 420    COMPARE with auxiliary data AUX is used to compare nodes. */
 421 bool
 422 llx_next_permutation (struct llx *r0, struct llx *r1,
 423                       llx_compare_func *compare, void *aux)
 424 {
 425   if (r0 != r1)
 426     {
 427       struct llx *i = llx_prev (r1);
 428       while (i != r0)
 429         {
 430           i = llx_prev (i);
 431           if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
 432             {
 433               struct llx *j;
 434               for (j = llx_prev (r1);
 435                    compare (llx_data (i), llx_data (j), aux) >= 0;
 436                    j = llx_prev (j))
 437                 continue;
 438               llx_swap (i, j);
 439               llx_reverse (llx_next (j), r1);
 440               return true;
 441             }
 442         }
 443
 444       llx_reverse (r0, r1);
 445     }
 446
 447   return false;
 448 }
 449
 450 /* Arranges R0...R1 into the lexicographically next lesser
 451    permutation.  Returns true if successful.
 452    If R0...R1 is already the lexicographically least
 453    permutation of its elements (i.e. ordered from smallest to
 454    greatest), arranges them into the lexicographically greatest
 455    permutation (i.e. ordered from largest to smallest) and
 456    returns false.
 457    COMPARE with auxiliary data AUX is used to compare nodes. */
 458 bool
 459 llx_prev_permutation (struct llx *r0, struct llx *r1,
 460                       llx_compare_func *compare, void *aux)
 461 {
 462   if (r0 != r1)
 463     {
 464       struct llx *i = llx_prev (r1);
 465       while (i != r0)
 466         {
 467           i = llx_prev (i);
 468           if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
 469             {
 470               struct llx *j;
 471               for (j = llx_prev (r1);
 472                    compare (llx_data (i), llx_data (j), aux) <= 0;
 473                    j = llx_prev (j))
 474                 continue;
 475               llx_swap (i, j);
 476               llx_reverse (llx_next (j), r1);
 477               return true;
 478             }
 479         }
 480
 481       llx_reverse (r0, r1);
 482     }
 483
 484   return false;
 485 }
 486
 487 /* Sorts R0...R1 into ascending order
 488    according to COMPARE given auxiliary data AUX.
 489    In use, keep in mind that R0 may move during the sort, so that
 490    afterward R0...R1 may denote a different range.
 491    (On the other hand, R1 is fixed in place.)
 492    Runs in O(n lg n) time in the number of nodes in the range. */
 493 void
 494 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
 495 {
 496   struct llx *pre_r0;
 497   size_t output_run_cnt;
 498
 499   if (r0 == r1 || llx_next (r0) == r1)
 500     return;
 501
 502   pre_r0 = llx_prev (r0);
 503   do
 504     {
 505       struct llx *a0 = llx_next (pre_r0);
 506       for (output_run_cnt = 1; ; output_run_cnt++)
 507         {
 508           struct llx *a1 = llx_find_run (a0, r1, compare, aux);
 509           struct llx *a2 = llx_find_run (a1, r1, compare, aux);
 510           if (a1 == a2)
 511             break;
 512
 513           a0 = llx_merge (a0, a1, a1, a2, compare, aux);
 514         }
 515     }
 516   while (output_run_cnt > 1);
 517 }
 518
 519 /* Finds the extent of a run of nodes of increasing value
 520    starting at R0 and extending no farther than R1.
 521    Returns the first node in R0...R1 that is less than the
 522    preceding node, or R1 if R0...R1 are arranged in nondecreasing
 523    order. */
 524 struct llx *
 525 llx_find_run (const struct llx *r0, const struct llx *r1,
 526               llx_compare_func *compare, void *aux)
 527 {
 528   if (r0 != r1)
 529     {
 530       do
 531         {
 532           r0 = llx_next (r0);
 533         }
 534       while (r0 != r1 && compare (llx_data (llx_prev (r0)),
 535                                   llx_data (r0), aux) <= 0);
 536     }
 537
 538   return CONST_CAST (struct llx *, r0);
 539 }
 540
 541 /* Merges B0...B1 into A0...A1 according to COMPARE given
 542    auxiliary data AUX.
 543    The ranges may be in the same list or different lists, but
 544    must not overlap.
 545    The merge is "stable" if A0...A1 is considered to precede
 546    B0...B1, regardless of their actual ordering.
 547    Runs in O(n) time in the total number of nodes in the ranges. */
 548 struct llx *
 549 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
 550            llx_compare_func *compare, void *aux)
 551 {
 552   if (a0 != a1 && b0 != b1)
 553     {
 554       a1 = llx_prev (a1);
 555       b1 = llx_prev (b1);
 556       for (;;)
 557         if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
 558           {
 559             if (a0 == a1)
 560               {
 561                 llx_splice (llx_next (a0), b0, llx_next (b1));
 562                 return llx_next (b1);
 563               }
 564             a0 = llx_next (a0);
 565           }
 566         else
 567           {
 568             if (b0 != b1)
 569               {
 570                 struct llx *x = b0;
 571                 b0 = llx_next (b0);
 572                 llx_splice (a0, x, b0);
 573               }
 574             else
 575               {
 576                 llx_splice (a0, b0, llx_next (b0));
 577                 return llx_next (a1);
 578               }
 579           }
 580     }
 581   else
 582     {
 583       llx_splice (a0, b0, b1);
 584       return b1;
 585     }
 586 }
 587
 588 /* Returns true if R0...R1 is sorted in ascending order according
 589    to COMPARE given auxiliary data AUX,
 590    false otherwise. */
 591 bool
 592 llx_is_sorted (const struct llx *r0, const struct llx *r1,
 593                llx_compare_func *compare, void *aux)
 594 {
 595   return llx_find_run (r0, r1, compare, aux) == r1;
 596 }
 597
 598 /* Removes all but the first in each group of sequential
 599    duplicates in R0...R1.  Duplicates are determined using
 600    COMPARE given auxiliary data AUX.  Removed duplicates are
 601    inserted before DUPS if it is nonnull; otherwise, the removed
 602    duplicates are freed with MANAGER.
 603    Only sequential duplicates are removed.  llx_sort() may be used
 604    to bring duplicates together, or llx_sort_unique() can do both
 605    at once. */
 606 size_t
 607 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 608             llx_compare_func *compare, void *aux,
 609             const struct llx_manager *manager)
 610 {
 611   size_t count = 0;
 612
 613   if (r0 != r1)
 614     {
 615       struct llx *x = r0;
 616       for (;;)
 617         {
 618           struct llx *y = llx_next (x);
 619           if (y == r1)
 620             {
 621               count++;
 622               break;
 623             }
 624
 625           if (compare (llx_data (x), llx_data (y), aux) == 0)
 626             {
 627               if (dups != NULL)
 628                 llx_splice (dups, y, llx_next (y));
 629               else
 630                 llx_remove (y, manager);
 631             }
 632           else
 633             {
 634               x = y;
 635               count++;
 636             }
 637         }
 638     }
 639
 640   return count;
 641 }
 642
 643 /* Sorts R0...R1 and removes duplicates.
 644    Removed duplicates are inserted before DUPS if it is nonnull;
 645    otherwise, the removed duplicates are freed with MANAGER.
 646    Comparisons are made with COMPARE given auxiliary data AUX.
 647    In use, keep in mind that R0 may move during the sort, so that
 648    afterward R0...R1 may denote a different range.
 649    (On the other hand, R1 is fixed in place.)
 650    Runs in O(n lg n) time in the number of nodes in the range. */
 651 void
 652 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 653                  llx_compare_func *compare, void *aux,
 654                  const struct llx_manager *manager)
 655 {
 656   struct llx *pre_r0 = llx_prev (r0);
 657   llx_sort (r0, r1, compare, aux);
 658   llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
 659 }
 660
 661 /* Inserts DATA in the proper position in R0...R1, which must
 662    be sorted according to COMPARE given auxiliary data AUX.
 663    If DATA is equal to one or more existing nodes in R0...R1,
 664    then it is inserted after the existing nodes it equals.
 665    Returns the new node (allocated with MANAGER), or a null
 666    pointer if memory allocation failed.
 667    Runs in O(n) time in the number of nodes in the range. */
 668 struct llx *
 669 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
 670                     llx_compare_func *compare, void *aux,
 671                     const struct llx_manager *manager)
 672 {
 673   struct llx *x;
 674
 675   for (x = r0; x != r1; x = llx_next (x))
 676     if (compare (llx_data (x), data, aux) > 0)
 677       break;
 678   return llx_insert (x, data, manager);
 679 }
 680
 681 /* Partitions R0...R1 into those nodes for which PREDICATE given
 682    auxiliary data AUX returns true, followed by those for which
 683    PREDICATE returns false.
 684    Returns the first node in the "false" group, or R1 if
 685    PREDICATE is true for every node in R0...R1.
 686    The partition is "stable" in that the nodes in each group
 687    retain their original relative order.
 688    Runs in O(n) time in the number of nodes in the range. */
 689 struct llx *
 690 llx_partition (struct llx *r0, struct llx *r1,
 691                llx_predicate_func *predicate, void *aux)
 692 {
 693   struct llx *t0, *t1;
 694
 695   for (;;)
 696     {
 697       if (r0 == r1)
 698         return r0;
 699       else if (!predicate (llx_data (r0), aux))
 700         break;
 701
 702       r0 = llx_next (r0);
 703     }
 704
 705   for (t0 = r0;; t0 = t1)
 706     {
 707       do
 708         {
 709           t0 = llx_next (t0);
 710           if (t0 == r1)
 711             return r0;
 712         }
 713       while (!predicate (llx_data (t0), aux));
 714
 715       t1 = t0;
 716       do
 717         {
 718           t1 = llx_next (t1);
 719           if (t1 == r1)
 720             {
 721               llx_splice (r0, t0, t1);
 722               return r0;
 723             }
 724         }
 725       while (predicate (llx_data (t1), aux));
 726
 727       llx_splice (r0, t0, t1);
 728     }
 729 }
 730
 731 /* Verifies that R0...R1 is parititioned into a sequence of nodes
 732    for which PREDICATE given auxiliary data AUX returns true,
 733    followed by those for which PREDICATE returns false.
 734    Returns a null pointer if R0...R1 is not partitioned this way.
 735    Otherwise, returns the first node in the "false" group, or R1
 736    if PREDICATE is true for every node in R0...R1. */
 737 struct llx *
 738 llx_find_partition (const struct llx *r0, const struct llx *r1,
 739                     llx_predicate_func *predicate, void *aux)
 740 {
 741   const struct llx *partition, *x;
 742
 743   for (partition = r0; partition != r1; partition = llx_next (partition))
 744     if (!predicate (llx_data (partition), aux))
 745       break;
 746
 747   for (x = partition; x != r1; x = llx_next (x))
 748     if (predicate (llx_data (x), aux))
 749       return NULL;
 750
 751   return CONST_CAST (struct llx *, partition);
 752 }
 753 \f
 754 /* Allocates and returns a node using malloc. */
 755 static struct llx *
 756 malloc_allocate_node (void *aux UNUSED)
 757 {
 758   return malloc (sizeof (struct llx));
 759 }
 760
 761 /* Releases node LLX with free. */
 762 static void
 763 malloc_release_node (struct llx *llx, void *aux UNUSED)
 764 {
 765   free (llx);
 766 }
 767
 768 /* Manager that uses the standard malloc and free routines. */
 769 const struct llx_manager llx_malloc_mgr =
 770   {
 771     malloc_allocate_node,
 772     malloc_release_node,
 773     NULL,
 774   };