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