src/libpspp/llx.c

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