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