pintos-os.org Git - pspp/blob - src/libpspp/llx.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2006 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 "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 equals TARGET
 223    according to COMPARE given auxiliary data AUX.
 224    Returns R1 if no node in R0...R1 equals TARGET. */
 225 struct llx *
 226 llx_find_equal (const struct llx *r0, const struct llx *r1,
 227                 const void *target,
 228                 llx_compare_func *compare, void *aux)
 229 {
 230   const struct llx *x;
 231
 232   for (x = r0; x != r1; x = llx_next (x))
 233     if (compare (llx_data (x), target, aux) == 0)
 234       break;
 235   return (struct llx *) x;
 236 }
 237
 238 /* Returns the first node in R0...R1 for which PREDICATE returns
 239    true given auxiliary data AUX.
 240    Returns R1 if PREDICATE does not return true for any node in
 241    R0...R1 . */
 242 struct llx *
 243 llx_find_if (const struct llx *r0, const struct llx *r1,
 244              llx_predicate_func *predicate, void *aux)
 245 {
 246   const struct llx *x;
 247
 248   for (x = r0; x != r1; x = llx_next (x))
 249     if (predicate (llx_data (x), aux))
 250       break;
 251   return (struct llx *) x;
 252 }
 253
 254 /* Compares each pair of adjacent nodes in R0...R1
 255    using COMPARE with auxiliary data AUX
 256    and returns the first node of the first pair that compares
 257    equal.
 258    Returns R1 if no pair compares equal. */
 259 struct llx *
 260 llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1,
 261                          llx_compare_func *compare, void *aux)
 262 {
 263   if (r0 != r1)
 264     {
 265       const struct llx *x, *y;
 266
 267       for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y))
 268         if (compare (llx_data (x), llx_data (y), aux) == 0)
 269           return (struct llx *) x;
 270     }
 271
 272   return (struct llx *) r1;
 273 }
 274
 275 /* Returns the number of nodes in R0...R1.
 276    Executes in O(n) time in the return value. */
 277 size_t
 278 llx_count_range (const struct llx *r0, const struct llx *r1)
 279 {
 280   return ll_count_range (&r0->ll, &r1->ll);
 281 }
 282
 283 /* Counts and returns the number of nodes in R0...R1 that equal
 284    TARGET according to COMPARE given auxiliary data AUX. */
 285 size_t
 286 llx_count_equal (const struct llx *r0, const struct llx *r1,
 287                  const void *target,
 288                  llx_compare_func *compare, void *aux)
 289 {
 290   const struct llx *x;
 291   size_t count;
 292
 293   count = 0;
 294   for (x = r0; x != r1; x = llx_next (x))
 295     if (compare (llx_data (x), target, aux) == 0)
 296       count++;
 297   return count;
 298 }
 299
 300 /* Counts and returns the number of nodes in R0...R1 for which
 301    PREDICATE returns true given auxiliary data AUX. */
 302 size_t
 303 llx_count_if (const struct llx *r0, const struct llx *r1,
 304               llx_predicate_func *predicate, void *aux)
 305 {
 306   const struct llx *x;
 307   size_t count;
 308
 309   count = 0;
 310   for (x = r0; x != r1; x = llx_next (x))
 311     if (predicate (llx_data (x), aux))
 312       count++;
 313   return count;
 314 }
 315
 316 /* Returns the greatest node in R0...R1 according to COMPARE
 317    given auxiliary data AUX.
 318    Returns the first of multiple, equal maxima. */
 319 struct llx *
 320 llx_max (const struct llx *r0, const struct llx *r1,
 321          llx_compare_func *compare, void *aux)
 322 {
 323   const struct llx *max = r0;
 324   if (r0 != r1)
 325     {
 326       struct llx *x;
 327
 328       for (x = llx_next (r0); x != r1; x = llx_next (x))
 329         if (compare (llx_data (x), llx_data (max), aux) > 0)
 330           max = x;
 331     }
 332   return (struct llx *) max;
 333 }
 334
 335 /* Returns the least node in R0...R1 according to COMPARE given
 336    auxiliary data AUX.
 337    Returns the first of multiple, equal minima. */
 338 struct llx *
 339 llx_min (const struct llx *r0, const struct llx *r1,
 340          llx_compare_func *compare, void *aux)
 341 {
 342   const struct llx *min = r0;
 343   if (r0 != r1)
 344     {
 345       struct llx *x;
 346
 347       for (x = llx_next (r0); x != r1; x = llx_next (x))
 348         if (compare (llx_data (x), llx_data (min), aux) < 0)
 349           min = x;
 350     }
 351   return (struct llx *) min;
 352 }
 353
 354 /* Lexicographically compares A0...A1 to B0...B1.
 355    Returns negative if A0...A1 < B0...B1,
 356    zero if A0...A1 == B0...B1, and
 357    positive if A0...A1 > B0...B1
 358    according to COMPARE given auxiliary data AUX. */
 359 int
 360 llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1,
 361                                   const struct llx *b0, const struct llx *b1,
 362                                   llx_compare_func *compare, void *aux)
 363 {
 364   for (;;)
 365     if (b0 == b1)
 366       return a0 != a1;
 367     else if (a0 == a1)
 368       return -1;
 369     else
 370       {
 371         int cmp = compare (llx_data (a0), llx_data (b0), aux);
 372         if (cmp != 0)
 373           return cmp;
 374
 375         a0 = llx_next (a0);
 376         b0 = llx_next (b0);
 377       }
 378 }
 379
 380 /* Calls ACTION with auxiliary data AUX
 381    for every node in R0...R1 in order. */
 382 void
 383 llx_apply (struct llx *r0, struct llx *r1,
 384            llx_action_func *action, void *aux)
 385 {
 386   struct llx *llx;
 387
 388   for (llx = r0; llx != r1; llx = llx_next (llx))
 389     action (llx_data (llx), aux);
 390 }
 391
 392 /* Reverses the order of nodes R0...R1. */
 393 void
 394 llx_reverse (struct llx *r0, struct llx *r1)
 395 {
 396   ll_reverse (&r0->ll, &r1->ll);
 397 }
 398
 399 /* Arranges R0...R1 into the lexicographically next greater
 400    permutation.  Returns true if successful.
 401    If R0...R1 is already the lexicographically greatest
 402    permutation of its elements (i.e. ordered from greatest to
 403    smallest), arranges them into the lexicographically least
 404    permutation (i.e. ordered from smallest to largest) and
 405    returns false.
 406    COMPARE with auxiliary data AUX is used to compare nodes. */
 407 bool
 408 llx_next_permutation (struct llx *r0, struct llx *r1,
 409                       llx_compare_func *compare, void *aux)
 410 {
 411   if (r0 != r1)
 412     {
 413       struct llx *i = llx_prev (r1);
 414       while (i != r0)
 415         {
 416           i = llx_prev (i);
 417           if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0)
 418             {
 419               struct llx *j;
 420               for (j = llx_prev (r1);
 421                    compare (llx_data (i), llx_data (j), aux) >= 0;
 422                    j = llx_prev (j))
 423                 continue;
 424               llx_swap (i, j);
 425               llx_reverse (llx_next (j), r1);
 426               return true;
 427             }
 428         }
 429
 430       llx_reverse (r0, r1);
 431     }
 432
 433   return false;
 434 }
 435
 436 /* Arranges R0...R1 into the lexicographically next lesser
 437    permutation.  Returns true if successful.
 438    If R0...R1 is already the lexicographically least
 439    permutation of its elements (i.e. ordered from smallest to
 440    greatest), arranges them into the lexicographically greatest
 441    permutation (i.e. ordered from largest to smallest) and
 442    returns false.
 443    COMPARE with auxiliary data AUX is used to compare nodes. */
 444 bool
 445 llx_prev_permutation (struct llx *r0, struct llx *r1,
 446                       llx_compare_func *compare, void *aux)
 447 {
 448   if (r0 != r1)
 449     {
 450       struct llx *i = llx_prev (r1);
 451       while (i != r0)
 452         {
 453           i = llx_prev (i);
 454           if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0)
 455             {
 456               struct llx *j;
 457               for (j = llx_prev (r1);
 458                    compare (llx_data (i), llx_data (j), aux) <= 0;
 459                    j = llx_prev (j))
 460                 continue;
 461               llx_swap (i, j);
 462               llx_reverse (llx_next (j), r1);
 463               return true;
 464             }
 465         }
 466
 467       llx_reverse (r0, r1);
 468     }
 469
 470   return false;
 471 }
 472
 473 /* Sorts R0...R1 into ascending order
 474    according to COMPARE given auxiliary data AUX.
 475    In use, keep in mind that R0 may move during the sort, so that
 476    afterward R0...R1 may denote a different range.
 477    (On the other hand, R1 is fixed in place.)
 478    Runs in O(n lg n) time in the number of nodes in the range. */
 479 void
 480 llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux)
 481 {
 482   struct llx *pre_r0;
 483   size_t output_run_cnt;
 484
 485   if (r0 == r1 || llx_next (r0) == r1)
 486     return;
 487
 488   pre_r0 = llx_prev (r0);
 489   do
 490     {
 491       struct llx *a0 = llx_next (pre_r0);
 492       for (output_run_cnt = 1; ; output_run_cnt++)
 493         {
 494           struct llx *a1 = llx_find_run (a0, r1, compare, aux);
 495           struct llx *a2 = llx_find_run (a1, r1, compare, aux);
 496           if (a1 == a2)
 497             break;
 498
 499           a0 = llx_merge (a0, a1, a1, a2, compare, aux);
 500         }
 501     }
 502   while (output_run_cnt > 1);
 503 }
 504
 505 /* Finds the extent of a run of nodes of increasing value
 506    starting at R0 and extending no farther than R1.
 507    Returns the first node in R0...R1 that is less than the
 508    preceding node, or R1 if R0...R1 are arranged in nondecreasing
 509    order. */
 510 struct llx *
 511 llx_find_run (const struct llx *r0, const struct llx *r1,
 512               llx_compare_func *compare, void *aux)
 513 {
 514   if (r0 != r1)
 515     {
 516       do
 517         {
 518           r0 = llx_next (r0);
 519         }
 520       while (r0 != r1 && compare (llx_data (llx_prev (r0)),
 521                                   llx_data (r0), aux) <= 0);
 522     }
 523
 524   return (struct llx *) r0;
 525 }
 526
 527 /* Merges B0...B1 into A0...A1 according to COMPARE given
 528    auxiliary data AUX.
 529    The ranges may be in the same list or different lists, but
 530    must not overlap.
 531    The merge is "stable" if A0...A1 is considered to precede
 532    B0...B1, regardless of their actual ordering.
 533    Runs in O(n) time in the total number of nodes in the ranges. */
 534 struct llx *
 535 llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1,
 536            llx_compare_func *compare, void *aux)
 537 {
 538   if (a0 != a1 && b0 != b1)
 539     {
 540       a1 = llx_prev (a1);
 541       b1 = llx_prev (b1);
 542       for (;;)
 543         if (compare (llx_data (a0), llx_data (b0), aux) <= 0)
 544           {
 545             if (a0 == a1)
 546               {
 547                 llx_splice (llx_next (a0), b0, llx_next (b1));
 548                 return llx_next (b1);
 549               }
 550             a0 = llx_next (a0);
 551           }
 552         else
 553           {
 554             if (b0 != b1)
 555               {
 556                 struct llx *x = b0;
 557                 b0 = llx_next (b0);
 558                 llx_splice (a0, x, b0);
 559               }
 560             else
 561               {
 562                 llx_splice (a0, b0, llx_next (b0));
 563                 return llx_next (a1);
 564               }
 565           }
 566     }
 567   else
 568     {
 569       llx_splice (a0, b0, b1);
 570       return b1;
 571     }
 572 }
 573
 574 /* Returns true if R0...R1 is sorted in ascending order according
 575    to COMPARE given auxiliary data AUX,
 576    false otherwise. */
 577 bool
 578 llx_is_sorted (const struct llx *r0, const struct llx *r1,
 579                llx_compare_func *compare, void *aux)
 580 {
 581   return llx_find_run (r0, r1, compare, aux) == r1;
 582 }
 583
 584 /* Removes all but the first in each group of sequential
 585    duplicates in R0...R1.  Duplicates are determined using
 586    COMPARE given auxiliary data AUX.  Removed duplicates are
 587    inserted before DUPS if it is nonnull; otherwise, the removed
 588    duplicates are freed with MANAGER.
 589    Only sequential duplicates are removed.  llx_sort() may be used
 590    to bring duplicates together, or llx_sort_unique() can do both
 591    at once. */
 592 size_t
 593 llx_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 594             llx_compare_func *compare, void *aux,
 595             const struct llx_manager *manager)
 596 {
 597   size_t count = 0;
 598
 599   if (r0 != r1)
 600     {
 601       struct llx *x = r0;
 602       for (;;)
 603         {
 604           struct llx *y = llx_next (x);
 605           if (y == r1)
 606             {
 607               count++;
 608               break;
 609             }
 610
 611           if (compare (llx_data (x), llx_data (y), aux) == 0)
 612             {
 613               if (dups != NULL)
 614                 llx_splice (dups, y, llx_next (y));
 615               else
 616                 llx_remove (y, manager);
 617             }
 618           else
 619             {
 620               x = y;
 621               count++;
 622             }
 623         }
 624     }
 625
 626   return count;
 627 }
 628
 629 /* Sorts R0...R1 and removes duplicates.
 630    Removed duplicates are inserted before DUPS if it is nonnull;
 631    otherwise, the removed duplicates are freed with MANAGER.
 632    Comparisons are made with COMPARE given auxiliary data AUX.
 633    In use, keep in mind that R0 may move during the sort, so that
 634    afterward R0...R1 may denote a different range.
 635    (On the other hand, R1 is fixed in place.)
 636    Runs in O(n lg n) time in the number of nodes in the range. */
 637 void
 638 llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups,
 639                  llx_compare_func *compare, void *aux,
 640                  const struct llx_manager *manager)
 641 {
 642   struct llx *pre_r0 = llx_prev (r0);
 643   llx_sort (r0, r1, compare, aux);
 644   llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager);
 645 }
 646
 647 /* Inserts DATA in the proper position in R0...R1, which must
 648    be sorted according to COMPARE given auxiliary data AUX.
 649    If DATA is equal to one or more existing nodes in R0...R1,
 650    then it is inserted after the existing nodes it equals.
 651    Returns the new node (allocated with MANAGER), or a null
 652    pointer if memory allocation failed.
 653    Runs in O(n) time in the number of nodes in the range. */
 654 struct llx *
 655 llx_insert_ordered (struct llx *r0, struct llx *r1, void *data,
 656                     llx_compare_func *compare, void *aux,
 657                     const struct llx_manager *manager)
 658 {
 659   struct llx *x;
 660
 661   for (x = r0; x != r1; x = llx_next (x))
 662     if (compare (llx_data (x), data, aux) > 0)
 663       break;
 664   return llx_insert (x, data, manager);
 665 }
 666
 667 /* Partitions R0...R1 into those nodes for which PREDICATE given
 668    auxiliary data AUX returns true, followed by those for which
 669    PREDICATE returns false.
 670    Returns the first node in the "false" group, or R1 if
 671    PREDICATE is true for every node in R0...R1.
 672    The partition is "stable" in that the nodes in each group
 673    retain their original relative order.
 674    Runs in O(n) time in the number of nodes in the range. */
 675 struct llx *
 676 llx_partition (struct llx *r0, struct llx *r1,
 677                llx_predicate_func *predicate, void *aux)
 678 {
 679   struct llx *t0, *t1;
 680
 681   for (;;)
 682     {
 683       if (r0 == r1)
 684         return r0;
 685       else if (!predicate (llx_data (r0), aux))
 686         break;
 687
 688       r0 = llx_next (r0);
 689     }
 690
 691   for (t0 = r0;; t0 = t1)
 692     {
 693       do
 694         {
 695           t0 = llx_next (t0);
 696           if (t0 == r1)
 697             return r0;
 698         }
 699       while (!predicate (llx_data (t0), aux));
 700
 701       t1 = t0;
 702       do
 703         {
 704           t1 = llx_next (t1);
 705           if (t1 == r1)
 706             {
 707               llx_splice (r0, t0, t1);
 708               return r0;
 709             }
 710         }
 711       while (predicate (llx_data (t1), aux));
 712
 713       llx_splice (r0, t0, t1);
 714     }
 715 }
 716
 717 /* Verifies that R0...R1 is parititioned into a sequence of nodes
 718    for which PREDICATE given auxiliary data AUX returns true,
 719    followed by those for which PREDICATE returns false.
 720    Returns a null pointer if R0...R1 is not partitioned this way.
 721    Otherwise, returns the first node in the "false" group, or R1
 722    if PREDICATE is true for every node in R0...R1. */
 723 struct llx *
 724 llx_find_partition (const struct llx *r0, const struct llx *r1,
 725                     llx_predicate_func *predicate, void *aux)
 726 {
 727   const struct llx *partition, *x;
 728
 729   for (partition = r0; partition != r1; partition = llx_next (partition))
 730     if (!predicate (llx_data (partition), aux))
 731       break;
 732
 733   for (x = partition; x != r1; x = llx_next (x))
 734     if (predicate (llx_data (x), aux))
 735       return NULL;
 736
 737   return (struct llx *) partition;
 738 }
 739 \f
 740 /* Allocates and returns a node using malloc. */
 741 static struct llx *
 742 malloc_allocate_node (void *aux UNUSED)
 743 {
 744   return malloc (sizeof (struct llx));
 745 }
 746
 747 /* Releases node LLX with free. */
 748 static void
 749 malloc_release_node (struct llx *llx, void *aux UNUSED)
 750 {
 751   free (llx);
 752 }
 753
 754 /* Manager that uses the standard malloc and free routines. */
 755 const struct llx_manager llx_malloc_mgr =
 756   {
 757     malloc_allocate_node,
 758     malloc_release_node,
 759     NULL,
 760   };