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