src/pool.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2000 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 #include <config.h>
  21 #include "pool.h"
  22 #include <stdlib.h>
  23 #include "alloc.h"
  24 #include "command.h"
  25 #include "error.h"
  26 #include "size_max.h"
  27 #include "str.h"
  28
  29 /* Fast, low-overhead memory block suballocator. */
  30 struct pool
  31   {
  32     struct pool *parent;        /* Pool of which this pool is a subpool. */
  33     struct pool_block *blocks;  /* Blocks owned by the pool. */
  34     struct pool_gizmo *gizmos;  /* Other stuff owned by the pool. */
  35   };
  36
  37 /* Pool block. */
  38 struct pool_block
  39   {
  40     struct pool_block *prev;
  41     struct pool_block *next;
  42     size_t ofs;
  43   };
  44
  45 /* Gizmo types. */
  46 enum
  47   {
  48     POOL_GIZMO_MALLOC,
  49     POOL_GIZMO_FILE,
  50     POOL_GIZMO_SUBPOOL,
  51     POOL_GIZMO_REGISTERED,
  52   };
  53
  54 /* Pool routines can maintain objects (`gizmos') as well as doing
  55    suballocation.
  56    This structure is used to keep track of them. */
  57 struct pool_gizmo
  58   {
  59     struct pool *pool;
  60     struct pool_gizmo *prev;
  61     struct pool_gizmo *next;
  62
  63     long serial;                /* Serial number. */
  64     int type;                   /* Type of this gizmo. */
  65
  66     /* Type-dependent info. */
  67     union
  68       {
  69         FILE *file;             /* POOL_GIZMO_FILE. */
  70         struct pool *subpool;   /* POOL_GIZMO_SUBPOOL. */
  71
  72         /* POOL_GIZMO_REGISTERED. */
  73         struct
  74           {
  75             void (*free) (void *p);
  76             void *p;
  77           }
  78         registered;
  79       }
  80     p;
  81   };
  82
  83 /* Rounds X up to the next multiple of Y. */
  84 #ifndef ROUND_UP
  85 #define ROUND_UP(X, Y)                          \
  86         (((X) + ((Y) - 1)) / (Y) * (Y))
  87 #endif
  88
  89 /* Types that provide typically useful alignment sizes. */
  90 union align
  91   {
  92     void *op;
  93     void (*fp) (void);
  94     long l;
  95     double d;
  96   };
  97
  98 /* This should be the alignment size used by malloc().  The size of
  99    the union above is correct, if not optimal, in all known cases. */
 100 #define ALIGN_SIZE sizeof (union align)
 101
 102 /* DISCRETE_BLOCKS may be declared as nonzero to prevent
 103    suballocation of blocks.  This is useful under memory
 104    debuggers like Checker or valgrind because it allows the
 105    source location of bugs to be more accurately pinpointed.
 106
 107    On the other hand, if we're testing the library, then we want to
 108    test the library's real functionality, not its crippled, slow,
 109    simplified functionality. */
 110 /*#define DISCRETE_BLOCKS 1*/
 111
 112 /* Size of each block allocated in the pool, in bytes.
 113    Should be at least 1k. */
 114 #ifndef BLOCK_SIZE
 115 #define BLOCK_SIZE 1024
 116 #endif
 117
 118 /* Maximum size of a suballocated block.  Larger blocks are allocated
 119    directly with malloc() to avoid memory wastage at the end of a
 120    suballocation block. */
 121 #ifndef MAX_SUBALLOC
 122 #define MAX_SUBALLOC 64
 123 #endif
 124
 125 /* Sizes of some structures with alignment padding included. */
 126 #define POOL_BLOCK_SIZE ROUND_UP (sizeof (struct pool_block), ALIGN_SIZE)
 127 #define POOL_GIZMO_SIZE ROUND_UP (sizeof (struct pool_gizmo), ALIGN_SIZE)
 128 #define POOL_SIZE ROUND_UP (sizeof (struct pool), ALIGN_SIZE)
 129
 130 /* Serial number used to keep track of gizmos for mark/release. */
 131 static long serial = 0;
 132
 133 /* Prototypes. */
 134 static void add_gizmo (struct pool *, struct pool_gizmo *);
 135 static void free_gizmo (struct pool_gizmo *);
 136 static void free_all_gizmos (struct pool *pool);
 137 static void delete_gizmo (struct pool *, struct pool_gizmo *);
 138 static void check_gizmo (struct pool *, struct pool_gizmo *);
 139 \f
 140 /* General routines. */
 141
 142 /* Creates and returns a new memory pool, which allows malloc()'d
 143    blocks to be suballocated in a time- and space-efficient manner.
 144    The entire contents of the memory pool are freed at once.
 145
 146    In addition, other objects can be associated with a memory pool.
 147    These are released when the pool is destroyed. */
 148 struct pool *
 149 pool_create (void)
 150 {
 151   struct pool_block *block;
 152   struct pool *pool;
 153
 154   block = xmalloc (BLOCK_SIZE);
 155   block->prev = block->next = block;
 156   block->ofs = POOL_BLOCK_SIZE + POOL_SIZE;
 157
 158   pool = (struct pool *) (((char *) block) + POOL_BLOCK_SIZE);
 159   pool->parent = NULL;
 160   pool->blocks = block;
 161   pool->gizmos = NULL;
 162
 163   return pool;
 164 }
 165
 166 /* Creates a pool, allocates a block STRUCT_SIZE bytes in
 167    length from it, stores the pool's address at offset
 168    POOL_MEMBER_OFFSET within the block, and returns the allocated
 169    block.
 170
 171    Meant for use indirectly via pool_create_container(). */
 172 void *
 173 pool_create_at_offset (size_t struct_size, size_t pool_member_offset)
 174 {
 175   struct pool *pool;
 176   char *struct_;
 177
 178   assert (struct_size >= sizeof pool);
 179   assert (pool_member_offset <= struct_size - sizeof pool);
 180
 181   pool = pool_create ();
 182   struct_ = pool_alloc (pool, struct_size);
 183   *(struct pool **) (struct_ + pool_member_offset) = pool;
 184   return struct_;
 185 }
 186
 187 /* Destroy the specified pool, including all subpools. */
 188 void
 189 pool_destroy (struct pool *pool)
 190 {
 191   if (pool == NULL)
 192     return;
 193
 194   /* Remove this pool from its parent's list of gizmos. */
 195   if (pool->parent)
 196     delete_gizmo (pool->parent, (void *) (((char *) pool) + POOL_SIZE));
 197
 198   free_all_gizmos (pool);
 199
 200   /* Free all the memory. */
 201   {
 202     struct pool_block *cur, *next;
 203
 204     pool->blocks->prev->next = NULL;
 205     for (cur = pool->blocks; cur; cur = next)
 206       {
 207         next = cur->next;
 208         free (cur);
 209       }
 210   }
 211 }
 212
 213 /* Release all the memory and gizmos in POOL.
 214    Blocks are not given back with free() but kept for later
 215    allocations.  To give back memory, use a subpool instead. */
 216 void
 217 pool_clear (struct pool *pool)
 218 {
 219   free_all_gizmos (pool);
 220
 221   /* Zero out block sizes. */
 222   {
 223     struct pool_block *cur;
 224
 225     cur = pool->blocks;
 226     do
 227       {
 228         cur->ofs = POOL_BLOCK_SIZE;
 229         if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
 230           {
 231             cur->ofs += POOL_SIZE;
 232             if (pool->parent != NULL)
 233               cur->ofs += POOL_GIZMO_SIZE;
 234           }
 235         cur = cur->next;
 236       }
 237     while (cur != pool->blocks);
 238   }
 239 }
 240 \f
 241 /* Suballocation routines. */
 242
 243 /* Allocates a memory region AMT bytes in size from POOL and returns a
 244    pointer to the region's start.
 245    The region is properly aligned for storing any object. */
 246 void *
 247 pool_alloc (struct pool *pool, size_t amt)
 248 {
 249   assert (pool != NULL);
 250
 251   if (amt == 0)
 252     return NULL;
 253
 254 #ifndef DISCRETE_BLOCKS
 255   if (amt <= MAX_SUBALLOC)
 256     {
 257       /* If there is space in this block, take it. */
 258       struct pool_block *b = pool->blocks;
 259       b->ofs = ROUND_UP (b->ofs, ALIGN_SIZE);
 260       if (b->ofs + amt <= BLOCK_SIZE)
 261         {
 262           void *const p = ((char *) b) + b->ofs;
 263           b->ofs += amt;
 264           return p;
 265         }
 266
 267       /* No space in this block, so we must make other
 268          arrangements. */
 269       if (b->next->ofs == 0)
 270         {
 271           /* The next block is empty.  Use it. */
 272           b = b->next;
 273           b->ofs = POOL_BLOCK_SIZE;
 274           if ((char *) b + POOL_BLOCK_SIZE == (char *) pool)
 275             b->ofs += POOL_SIZE;
 276         }
 277       else
 278         {
 279           /* Create a new block at the start of the list. */
 280           b = xmalloc (BLOCK_SIZE);
 281           b->next = pool->blocks;
 282           b->prev = pool->blocks->prev;
 283           b->ofs = POOL_BLOCK_SIZE;
 284           pool->blocks->prev->next = b;
 285           pool->blocks->prev = b;
 286         }
 287       pool->blocks = b;
 288
 289       /* Allocate space from B. */
 290       b->ofs += amt;
 291       return ((char *) b) + b->ofs - amt;
 292     }
 293   else
 294 #endif
 295     return pool_malloc (pool, amt);
 296 }
 297
 298 /* Allocates a memory region AMT bytes in size from POOL and
 299    returns a pointer to the region's start.  The region is not
 300    necessarily aligned, so it is most suitable for storing
 301    strings. */
 302 void *
 303 pool_alloc_unaligned (struct pool *pool, size_t amt)
 304 {
 305   assert (pool != NULL);
 306
 307 #ifndef DISCRETE_BLOCKS
 308   /* Strings need not be aligned on any boundary, but some
 309      operations may be more efficient when they are.  However,
 310      that's only going to help with reasonably long strings. */
 311   if (amt < ALIGN_SIZE)
 312     {
 313       if (amt == 0)
 314         return NULL;
 315       else
 316         {
 317           struct pool_block *const b = pool->blocks;
 318
 319           if (b->ofs + amt <= BLOCK_SIZE)
 320             {
 321               void *p = ((char *) b) + b->ofs;
 322               b->ofs += amt;
 323               return p;
 324             }
 325         }
 326     }
 327 #endif
 328
 329   return pool_alloc (pool, amt);
 330 }
 331
 332 /* Allocates a memory region N * S bytes in size from POOL and
 333    returns a pointer to the region's start.
 334    N must be nonnegative, S must be positive.
 335    Terminates the program if the memory cannot be obtained,
 336    including the case where N * S overflows the range of size_t. */
 337 void *
 338 pool_nalloc (struct pool *pool, size_t n, size_t s)
 339 {
 340   if (xalloc_oversized (n, s))
 341     xalloc_die ();
 342   return pool_alloc (pool, n * s);
 343 }
 344
 345 /* Allocates SIZE bytes in POOL, copies BUFFER into it, and
 346    returns the new copy. */
 347 void *
 348 pool_clone (struct pool *pool, const void *buffer, size_t size)
 349 {
 350   void *block = pool_alloc (pool, size);
 351   memcpy (block, buffer, size);
 352   return block;
 353 }
 354
 355 /* Allocates SIZE bytes of unaligned data in POOL, copies BUFFER
 356    into it, and returns the new copy. */
 357 void *
 358 pool_clone_unaligned (struct pool *pool, const void *buffer, size_t size)
 359 {
 360   void *block = pool_alloc_unaligned (pool, size);
 361   memcpy (block, buffer, size);
 362   return block;
 363 }
 364
 365 /* Duplicates null-terminated STRING, within POOL, and returns a
 366    pointer to the duplicate.  For use only with strings, because
 367    the returned pointere may not be aligned properly for other
 368    types. */
 369 char *
 370 pool_strdup (struct pool *pool, const char *string)
 371 {
 372   return pool_clone_unaligned (pool, string, strlen (string) + 1);
 373 }
 374 \f
 375 /* Standard allocation routines. */
 376
 377 /* Allocates AMT bytes using malloc(), to be managed by POOL, and
 378    returns a pointer to the beginning of the block.
 379    If POOL is a null pointer, then allocates a normal memory block
 380    with xmalloc().  */
 381 void *
 382 pool_malloc (struct pool *pool, size_t amt)
 383 {
 384   if (pool != NULL)
 385     {
 386       if (amt != 0)
 387         {
 388           struct pool_gizmo *g = xmalloc (amt + POOL_GIZMO_SIZE);
 389           g->type = POOL_GIZMO_MALLOC;
 390           add_gizmo (pool, g);
 391
 392           return ((char *) g) + POOL_GIZMO_SIZE;
 393         }
 394       else
 395         return NULL;
 396     }
 397   else
 398     return xmalloc (amt);
 399 }
 400
 401 /* Allocates and returns N elements of S bytes each, to be
 402    managed by POOL.
 403    If POOL is a null pointer, then allocates a normal memory block
 404    with malloc().
 405    N must be nonnegative, S must be positive.
 406    Terminates the program if the memory cannot be obtained,
 407    including the case where N * S overflows the range of size_t. */
 408 void *
 409 pool_nmalloc (struct pool *pool, size_t n, size_t s)
 410 {
 411   if (xalloc_oversized (n, s))
 412     xalloc_die ();
 413   return pool_malloc (pool, n * s);
 414 }
 415
 416 /* Changes the allocation size of the specified memory block P managed
 417    by POOL to AMT bytes and returns a pointer to the beginning of the
 418    block.
 419    If POOL is a null pointer, then the block is reallocated in the
 420    usual way with realloc(). */
 421 void *
 422 pool_realloc (struct pool *pool, void *p, size_t amt)
 423 {
 424   if (pool != NULL)
 425     {
 426       if (p != NULL)
 427         {
 428           if (amt != 0)
 429             {
 430               struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
 431               check_gizmo (pool, g);
 432
 433               g = xrealloc (g, amt + POOL_GIZMO_SIZE);
 434               if (g->next)
 435                 g->next->prev = g;
 436               if (g->prev)
 437                 g->prev->next = g;
 438               else
 439                 pool->gizmos = g;
 440               check_gizmo (pool, g);
 441
 442               return ((char *) g) + POOL_GIZMO_SIZE;
 443             }
 444           else
 445             {
 446               pool_free (pool, p);
 447               return NULL;
 448             }
 449         }
 450       else
 451         return pool_malloc (pool, amt);
 452     }
 453   else
 454     return xrealloc (p, amt);
 455 }
 456
 457 /* Changes the allocation size of the specified memory block P
 458    managed by POOL to N * S bytes and returns a pointer to the
 459    beginning of the block.
 460    N must be nonnegative, S must be positive.
 461    If POOL is a null pointer, then the block is reallocated in
 462    the usual way with xrealloc().
 463    Terminates the program if the memory cannot be obtained,
 464    including the case where N * S overflows the range of size_t. */
 465 void *
 466 pool_nrealloc (struct pool *pool, void *p, size_t n, size_t s)
 467 {
 468   if (xalloc_oversized (n, s))
 469     xalloc_die ();
 470   return pool_realloc (pool, p, n * s);
 471 }
 472
 473 /* If P is null, allocate a block of at least *PN such objects;
 474    otherwise, reallocate P so that it contains more than *PN
 475    objects each of S bytes.  *PN must be nonzero unless P is
 476    null, and S must be nonzero.  Set *PN to the new number of
 477    objects, and return the pointer to the new block.  *PN is
 478    never set to zero, and the returned pointer is never null.
 479
 480    The block returned is managed by POOL.  If POOL is a null
 481    pointer, then the block is reallocated in the usual way with
 482    x2nrealloc().
 483
 484    Terminates the program if the memory cannot be obtained,
 485    including the case where the memory required overflows the
 486    range of size_t.
 487
 488    Repeated reallocations are guaranteed to make progress, either by
 489    allocating an initial block with a nonzero size, or by allocating a
 490    larger block.
 491
 492    In the following implementation, nonzero sizes are doubled so that
 493    repeated reallocations have O(N log N) overall cost rather than
 494    O(N**2) cost, but the specification for this function does not
 495    guarantee that sizes are doubled.
 496
 497    Here is an example of use:
 498
 499      int *p = NULL;
 500      struct pool *pool;
 501      size_t used = 0;
 502      size_t allocated = 0;
 503
 504      void
 505      append_int (int value)
 506        {
 507          if (used == allocated)
 508            p = pool_2nrealloc (pool, p, &allocated, sizeof *p);
 509          p[used++] = value;
 510        }
 511
 512    This causes x2nrealloc to allocate a block of some nonzero size the
 513    first time it is called.
 514
 515    To have finer-grained control over the initial size, set *PN to a
 516    nonzero value before calling this function with P == NULL.  For
 517    example:
 518
 519      int *p = NULL;
 520      struct pool *pool;
 521      size_t used = 0;
 522      size_t allocated = 0;
 523      size_t allocated1 = 1000;
 524
 525      void
 526      append_int (int value)
 527        {
 528          if (used == allocated)
 529            {
 530              p = pool_2nrealloc (pool, p, &allocated1, sizeof *p);
 531              allocated = allocated1;
 532            }
 533          p[used++] = value;
 534        }
 535
 536    This function implementation is from gnulib. */
 537 void *
 538 pool_2nrealloc (struct pool *pool, void *p, size_t *pn, size_t s)
 539 {
 540   size_t n = *pn;
 541
 542   if (p == NULL)
 543     {
 544       if (n == 0)
 545         {
 546           /* The approximate size to use for initial small allocation
 547              requests, when the invoking code specifies an old size of
 548              zero.  64 bytes is the largest "small" request for the
 549              GNU C library malloc.  */
 550           enum { DEFAULT_MXFAST = 64 };
 551
 552           n = DEFAULT_MXFAST / s;
 553           n += !n;
 554         }
 555     }
 556   else
 557     {
 558       if (SIZE_MAX / 2 / s < n)
 559         xalloc_die ();
 560       n *= 2;
 561     }
 562
 563   *pn = n;
 564   return pool_realloc (pool, p, n * s);
 565 }
 566
 567 /* Frees block P managed by POOL.
 568    If POOL is a null pointer, then the block is freed as usual with
 569    free(). */
 570 void
 571 pool_free (struct pool *pool, void *p)
 572 {
 573   if (pool != NULL && p != NULL)
 574     {
 575       struct pool_gizmo *g = (void *) (((char *) p) - POOL_GIZMO_SIZE);
 576       check_gizmo (pool, g);
 577       delete_gizmo (pool, g);
 578       free (g);
 579     }
 580   else
 581     free (p);
 582 }
 583 \f
 584 /* Gizmo allocations. */
 585
 586 /* Creates and returns a pool as a subpool of POOL.
 587    The subpool will be destroyed automatically when POOL is destroyed.
 588    It may also be destroyed explicitly in advance. */
 589 struct pool *
 590 pool_create_subpool (struct pool *pool)
 591 {
 592   struct pool *subpool;
 593   struct pool_gizmo *g;
 594
 595   assert (pool != NULL);
 596   subpool = pool_create ();
 597   subpool->parent = pool;
 598
 599   g = (void *) (((char *) subpool->blocks) + subpool->blocks->ofs);
 600   subpool->blocks->ofs += POOL_GIZMO_SIZE;
 601
 602   g->type = POOL_GIZMO_SUBPOOL;
 603   g->p.subpool = subpool;
 604
 605   add_gizmo (pool, g);
 606
 607   return subpool;
 608 }
 609
 610 /* Makes SUBPOOL a subpool of POOL.
 611    SUBPOOL must not already have a parent pool.
 612    The subpool will be destroyed automatically when POOL is destroyed.
 613    It may also be destroyed explicitly in advance. */
 614 void
 615 pool_add_subpool (struct pool *pool, struct pool *subpool)
 616 {
 617   struct pool_gizmo *g;
 618
 619   assert (pool != NULL);
 620   assert (subpool != NULL);
 621   assert (subpool->parent == NULL);
 622
 623   g = pool_alloc (subpool, sizeof *g);
 624   g->type = POOL_GIZMO_SUBPOOL;
 625   g->p.subpool = subpool;
 626   add_gizmo (pool, g);
 627
 628   subpool->parent = pool;
 629 }
 630
 631 /* Opens file FILENAME with mode MODE and returns a handle to it
 632    if successful or a null pointer if not.
 633    The file will be closed automatically when POOL is destroyed, or it
 634    may be closed explicitly in advance using pool_fclose. */
 635 FILE *
 636 pool_fopen (struct pool *pool, const char *filename, const char *mode)
 637 {
 638   FILE *f;
 639
 640   assert (pool && filename && mode);
 641   f = fopen (filename, mode);
 642   if (f == NULL)
 643     return NULL;
 644
 645   {
 646     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
 647     g->type = POOL_GIZMO_FILE;
 648     g->p.file = f;
 649     add_gizmo (pool, g);
 650   }
 651
 652   return f;
 653 }
 654
 655 /* Closes file FILE managed by POOL. */
 656 int
 657 pool_fclose (struct pool *pool, FILE *file)
 658 {
 659   assert (pool && file);
 660   if (fclose (file) == EOF)
 661     return EOF;
 662
 663   {
 664     struct pool_gizmo *g;
 665
 666     for (g = pool->gizmos; g; g = g->next)
 667       if (g->type == POOL_GIZMO_FILE && g->p.file == file)
 668         {
 669           delete_gizmo (pool, g);
 670           break;
 671         }
 672   }
 673
 674   return 0;
 675 }
 676 \f
 677 /* Registers FREE to be called with argument P.
 678    P should be unique among those registered in POOL so that it can be
 679    uniquely identified by pool_unregister().
 680    If not unregistered, FREE will be called with argument P when POOL
 681    is destroyed. */
 682 void
 683 pool_register (struct pool *pool, void (*free) (void *), void *p)
 684 {
 685   assert (pool && free && p);
 686
 687   {
 688     struct pool_gizmo *g = pool_alloc (pool, sizeof *g);
 689     g->type = POOL_GIZMO_REGISTERED;
 690     g->p.registered.free = free;
 691     g->p.registered.p = p;
 692     add_gizmo (pool, g);
 693   }
 694 }
 695
 696 /* Unregisters previously registered P from POOL.
 697    Returns nonzero only if P was found to be registered in POOL. */
 698 int
 699 pool_unregister (struct pool *pool, void *p)
 700 {
 701   assert (pool && p);
 702
 703   {
 704     struct pool_gizmo *g;
 705
 706     for (g = pool->gizmos; g; g = g->next)
 707       if (g->type == POOL_GIZMO_REGISTERED && g->p.registered.p == p)
 708         {
 709           delete_gizmo (pool, g);
 710           return 1;
 711         }
 712   }
 713
 714   return 0;
 715 }
 716 \f
 717 /* Partial freeing. */
 718
 719 /* Notes the state of POOL into MARK so that it may be restored
 720    by a call to pool_release(). */
 721 void
 722 pool_mark (struct pool *pool, struct pool_mark *mark)
 723 {
 724   assert (pool && mark);
 725
 726   mark->block = pool->blocks;
 727   mark->ofs = pool->blocks->ofs;
 728
 729   mark->serial = serial;
 730 }
 731
 732 /* Restores to POOL the state recorded in MARK.
 733    Emptied blocks are not given back with free() but kept for
 734    later allocations.  To get that behavior, use a subpool
 735    instead. */
 736 void
 737 pool_release (struct pool *pool, const struct pool_mark *mark)
 738 {
 739   assert (pool && mark);
 740
 741   {
 742     struct pool_gizmo *cur, *next;
 743
 744     for (cur = pool->gizmos; cur && cur->serial >= mark->serial; cur = next)
 745       {
 746         next = cur->next;
 747         free_gizmo (cur);
 748       }
 749
 750     if (cur != NULL)
 751       {
 752         cur->prev = NULL;
 753         pool->gizmos = cur;
 754       }
 755     else
 756       pool->gizmos = NULL;
 757   }
 758
 759   {
 760     struct pool_block *cur;
 761
 762     for (cur = pool->blocks; cur != mark->block; cur = cur->next)
 763       {
 764         cur->ofs = POOL_BLOCK_SIZE;
 765         if ((char *) cur + POOL_BLOCK_SIZE == (char *) pool)
 766           {
 767             cur->ofs += POOL_SIZE;
 768             if (pool->parent != NULL)
 769               cur->ofs += POOL_GIZMO_SIZE;
 770           }
 771       }
 772     pool->blocks = mark->block;
 773     pool->blocks->ofs = mark->ofs;
 774   }
 775 }
 776 \f
 777 /* Private functions. */
 778
 779 /* Adds GIZMO at the beginning of POOL's gizmo list. */
 780 static void
 781 add_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
 782 {
 783   assert (pool && gizmo);
 784
 785   gizmo->pool = pool;
 786   gizmo->next = pool->gizmos;
 787   gizmo->prev = NULL;
 788   if (pool->gizmos)
 789     pool->gizmos->prev = gizmo;
 790   pool->gizmos = gizmo;
 791
 792   gizmo->serial = serial++;
 793
 794   check_gizmo (pool, gizmo);
 795 }
 796
 797 /* Removes GIZMO from POOL's gizmo list. */
 798 static void
 799 delete_gizmo (struct pool *pool, struct pool_gizmo *gizmo)
 800 {
 801   assert (pool && gizmo);
 802
 803   check_gizmo (pool, gizmo);
 804
 805   if (gizmo->prev)
 806     gizmo->prev->next = gizmo->next;
 807   else
 808     pool->gizmos = gizmo->next;
 809   if (gizmo->next)
 810     gizmo->next->prev = gizmo->prev;
 811 }
 812
 813 /* Frees any of GIZMO's internal state.
 814    GIZMO's data must not be referenced after calling this function. */
 815 static void
 816 free_gizmo (struct pool_gizmo *gizmo)
 817 {
 818   assert (gizmo != NULL);
 819
 820   switch (gizmo->type)
 821     {
 822     case POOL_GIZMO_MALLOC:
 823       free (gizmo);
 824       break;
 825     case POOL_GIZMO_FILE:
 826       fclose (gizmo->p.file);   /* Ignore errors. */
 827       break;
 828     case POOL_GIZMO_SUBPOOL:
 829       gizmo->p.subpool->parent = NULL;
 830       pool_destroy (gizmo->p.subpool);
 831       break;
 832     case POOL_GIZMO_REGISTERED:
 833       gizmo->p.registered.free (gizmo->p.registered.p);
 834       break;
 835     default:
 836       assert (0);
 837     }
 838 }
 839
 840 /* Free all the gizmos in POOL. */
 841 static void
 842 free_all_gizmos (struct pool *pool)
 843 {
 844   struct pool_gizmo *cur, *next;
 845
 846   for (cur = pool->gizmos; cur; cur = next)
 847     {
 848       next = cur->next;
 849       free_gizmo (cur);
 850     }
 851   pool->gizmos = NULL;
 852 }
 853
 854 static void
 855 check_gizmo (struct pool *p, struct pool_gizmo *g)
 856 {
 857   assert (g->pool == p);
 858   assert (g->next == NULL || g->next->prev == g);
 859   assert ((g->prev != NULL && g->prev->next == g)
 860           || (g->prev == NULL && p->gizmos == g));
 861
 862 }
 863 \f
 864 /* Self-test routine. */
 865
 866 #include <errno.h>
 867 #include <stdio.h>
 868 #include <stdlib.h>
 869 #include <string.h>
 870 #include <time.h>
 871
 872 #define N_ITERATIONS 8192
 873 #define N_FILES 16
 874
 875 /* Self-test routine.
 876    This is not exhaustive, but it can be useful. */
 877 int
 878 cmd_debug_pool (void)
 879 {
 880   int seed = time (0) * 257 % 32768;
 881
 882   for (;;)
 883     {
 884       struct pool *pool;
 885       struct pool_mark m1, m2;
 886       FILE *files[N_FILES];
 887       int cur_file;
 888       long i;
 889
 890       printf ("Random number seed: %d\n", seed);
 891       srand (seed++);
 892
 893       printf ("Creating pool...\n");
 894       pool = pool_create ();
 895
 896       printf ("Marking pool state...\n");
 897       pool_mark (pool, &m1);
 898
 899       printf ("    Populating pool with random-sized small objects...\n");
 900       for (i = 0; i < N_ITERATIONS; i++)
 901         {
 902           size_t size = rand () % MAX_SUBALLOC;
 903           void *p = pool_alloc (pool, size);
 904           memset (p, 0, size);
 905         }
 906
 907       printf ("    Marking pool state...\n");
 908       pool_mark (pool, &m2);
 909
 910       printf ("       Populating pool with random-sized small "
 911               "and large objects...\n");
 912       for (i = 0; i < N_ITERATIONS; i++)
 913         {
 914           size_t size = rand () % (2 * MAX_SUBALLOC);
 915           void *p = pool_alloc (pool, size);
 916           memset (p, 0, size);
 917         }
 918
 919       printf ("    Releasing pool state...\n");
 920       pool_release (pool, &m2);
 921
 922       printf ("    Populating pool with random objects and gizmos...\n");
 923       for (i = 0; i < N_FILES; i++)
 924         files[i] = NULL;
 925       cur_file = 0;
 926       for (i = 0; i < N_ITERATIONS; i++)
 927         {
 928           int type = rand () % 32;
 929
 930           if (type == 0)
 931             {
 932               if (files[cur_file] != NULL
 933                   && EOF == pool_fclose (pool, files[cur_file]))
 934                 printf ("error on fclose: %s\n", strerror (errno));
 935
 936               files[cur_file] = pool_fopen (pool, "/dev/null", "r");
 937
 938               if (++cur_file >= N_FILES)
 939                 cur_file = 0;
 940             }
 941           else if (type == 1)
 942             pool_create_subpool (pool);
 943           else
 944             {
 945               size_t size = rand () % (2 * MAX_SUBALLOC);
 946               void *p = pool_alloc (pool, size);
 947               memset (p, 0, size);
 948             }
 949         }
 950
 951       printf ("Releasing pool state...\n");
 952       pool_release (pool, &m1);
 953
 954       printf ("Destroying pool...\n");
 955       pool_destroy (pool);
 956
 957       putchar ('\n');
 958     }
 959
 960   return CMD_SUCCESS;
 961 }
 962