src/libpspp/llx.c

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