util/src/TclTk/blt2.5/generic/bltPool.c

   1 /*
   2  * bltPool.c --
   3  *
   4  * Copyright 2001 Silicon Metrics, Inc.
   5  *
   6  * Permission to use, copy, modify, and distribute this software and
   7  * its documentation for any purpose and without fee is hereby
   8  * granted, provided that the above copyright notice appear in all
   9  * copies and that both that the copyright notice and warranty
  10  * disclaimer appear in supporting documentation, and that the names
  11  * of Lucent Technologies any of their entities not be used in
  12  * advertising or publicity pertaining to distribution of the software
  13  * without specific, written prior permission.
  14  *
  15  * Silicon Metrics disclaims all warranties with regard to this
  16  * software, including all implied warranties of merchantability and
  17  * fitness.  In no event shall Lucent Technologies be liable for any
  18  * special, indirect or consequential damages or any damages
  19  * whatsoever resulting from loss of use, data or profits, whether in
  20  * an action of contract, negligence or other tortuous action, arising
  21  * out of or in connection with the use or performance of this
  22  * software.
  23  */
  24
  25 #include "bltInt.h"
  26 #include "bltPool.h"
  27
  28 /*
  29  * Blt_Pool --
  30  *
  31  *      Implements a pool memory allocator.
  32  *
  33  *        + It's faster allocating memory since malloc/free are called
  34  *          only a fraction of the normal times.  Fixed size items can
  35  *          be reused without deallocating/reallocating memory.
  36  *        + You don't have the extra 8-16 byte overhead per malloc.
  37  *        - Memory is freed only when the entire pool is destroyed.
  38  *        - Memory is allocated in chunks. More memory is allocated
  39  *          than used.
  40  *        0 Depending upon allocation/deallocation patterns, locality
  41  *          may be improved or degraded.
  42  *
  43  *      The pool is a chain of malloc'ed blocks.
  44  *
  45  *             +---------+  +---------+  +---------+
  46  *       NULL<-| nextPtr |<-| nextPtr |<-| nextPtr |<- headPtr
  47  *             |---------|  |---------|  |---------|
  48  *             | chunk1  |  | chunk2  |  | chunk3  |
  49  *             +---------+  |         |  |         |
  50  *                          +---------+  |         |
  51  *                                       |         |
  52  *                                       |         |
  53  *                                       +---------+
  54  *
  55  *      Each chunk contains an integral number of fixed size items.
  56  *      The number of items doubles until a maximum size is reached
  57  *      (each subsequent new chunk will be the maximum).  Chunks
  58  *      are allocated only when needed (no more space is available
  59  *      in the last chunk).
  60  *
  61  *      The chain of blocks is only freed when the entire pool is
  62  *      destroyed.
  63  *
  64  *      A freelist of unused items also maintained. Each freed item
  65  *      is prepended to a free list.  Before allocating new chunks
  66  *      the freelist is examined to see if an unused items exist.
  67  *
  68  *               chunk1       chunk2       chunk3
  69  *            +---------+  +---------+  +---------+
  70  *      NULL<-| unused  |  |         |  |         |
  71  *            +----^----+  +---------+  +---------+
  72  *            | unused  |<-| unused  |<-| unused  |
  73  *            +---------+  +---------+  +----^----+
  74  *            |         |  |         |  | unused  |
  75  *            +---------+  |         |  +----^----+
  76  *                         |         |  |    |    |
  77  *                         +---------+  +----|----+
  78  *                                      | usused  |<- freePtr
  79  *                                      +---------+
  80  */
  81
  82 #define POOL_MAX_CHUNK_SIZE      ((1<<16) - sizeof(Blt_PoolChain))
  83
  84 #ifndef ALIGN
  85 #define ALIGN(a) \
  86         (((size_t)a + (sizeof(void *) - 1)) & (~(sizeof(void *) - 1)))
  87 #endif /* ALIGN */
  88
  89 static Blt_PoolAllocProc VariablePoolAllocItem;
  90 static Blt_PoolFreeProc  VariablePoolFreeItem;
  91 static Blt_PoolAllocProc FixedPoolAllocItem;
  92 static Blt_PoolFreeProc  FixedPoolFreeItem;
  93 static Blt_PoolAllocProc StringPoolAllocItem;
  94 static Blt_PoolFreeProc  StringPoolFreeItem;
  95
  96 /*
  97  *----------------------------------------------------------------------
  98  *
  99  * VariablePoolAllocItem --
 100  *
 101  *      Returns a new item.  First check if there is any more space
 102  *      left in the current chunk.  If there isn't then next check
 103  *      the free list for unused items.  Finally allocate a new
 104  *      chunk and return its first item.
 105  *
 106  * Results:
 107  *      Returns a new (possible reused) item.
 108  *
 109  * Side Effects:
 110  *      A new memory chunk may be allocated.
 111  *
 112  *----------------------------------------------------------------------
 113  */
 114 static void *
 115 VariablePoolAllocItem(poolPtr, size)
 116     struct Blt_PoolStruct *poolPtr;
 117     size_t size;                /* Number of bytes to allocate. */
 118 {
 119     Blt_PoolChain *chainPtr;
 120     void *memPtr;
 121
 122     size = ALIGN(size);
 123     if (size >= POOL_MAX_CHUNK_SIZE) {
 124         /*
 125          * Handle oversized requests by allocating a chunk to hold the
 126          * single item and immediately placing it into the in-use list.
 127          */
 128         chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + size);
 129         if (poolPtr->headPtr == NULL) {
 130             poolPtr->headPtr = chainPtr;
 131         } else {
 132             chainPtr->nextPtr = poolPtr->headPtr->nextPtr;
 133             poolPtr->headPtr->nextPtr = chainPtr;
 134         }
 135         memPtr = (void *)chainPtr;
 136     } else {
 137         if (poolPtr->bytesLeft >= size) {
 138             poolPtr->bytesLeft -= size;
 139             memPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
 140         } else {
 141             poolPtr->waste += poolPtr->bytesLeft;
 142             /* Create a new block of items and prepend it to the in-use list */
 143             poolPtr->bytesLeft = POOL_MAX_CHUNK_SIZE;
 144             /* Allocate the requested chunk size, plus the header */
 145             chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + poolPtr->bytesLeft);
 146             chainPtr->nextPtr = poolPtr->headPtr;
 147             poolPtr->headPtr = chainPtr;
 148             /* Peel off a new item. */
 149             poolPtr->bytesLeft -= size;
 150             memPtr = (char *)(chainPtr + 1) + poolPtr->bytesLeft;
 151         }
 152     }
 153     return memPtr;
 154 }
 155
 156 /*
 157  *----------------------------------------------------------------------
 158  *
 159  * VariablePoolFreeItem --
 160  *
 161  *      Placeholder for freeProc routine.  The pool memory is
 162  *      not reclaimed or freed until the entire pool is released.
 163  *
 164  * Results:
 165  *      None.
 166  *
 167  *----------------------------------------------------------------------
 168  */
 169 /*ARGSUSED*/
 170 static void
 171 VariablePoolFreeItem(poolPtr, item)
 172     struct Blt_PoolStruct *poolPtr;
 173     void *item;
 174 {
 175     /* Does nothing */
 176 }
 177
 178 /*
 179  *----------------------------------------------------------------------
 180  *
 181  * StringPoolAllocItem --
 182  *
 183  *      Returns a new item.  First check if there is any more space
 184  *      left in the current chunk.  If there isn't then next check
 185  *      the free list for unused items.  Finally allocate a new
 186  *      chunk and return its first item.
 187  *
 188  * Results:
 189  *      Returns a new (possible reused) item.
 190  *
 191  * Side Effects:
 192  *      A new memory chunk may be allocated.
 193  *
 194  *----------------------------------------------------------------------
 195  */
 196 static void *
 197 StringPoolAllocItem(poolPtr, size)
 198     struct Blt_PoolStruct *poolPtr;
 199     size_t size;                /* Number of bytes to allocate. */
 200 {
 201     Blt_PoolChain *chainPtr;
 202     void *memPtr;
 203
 204     if (size >= POOL_MAX_CHUNK_SIZE) {
 205         /*
 206          * Handle oversized requests by allocating a chunk to hold the
 207          * single item and immediately placing it into the in-use list.
 208          */
 209         chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + size);
 210         if (poolPtr->headPtr == NULL) {
 211             poolPtr->headPtr = chainPtr;
 212         } else {
 213             chainPtr->nextPtr = poolPtr->headPtr->nextPtr;
 214             poolPtr->headPtr->nextPtr = chainPtr;
 215         }
 216         memPtr = (void *)chainPtr;
 217     } else {
 218         if (poolPtr->bytesLeft >= size) {
 219             poolPtr->bytesLeft -= size;
 220             memPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
 221         } else {
 222             poolPtr->waste += poolPtr->bytesLeft;
 223             /* Create a new block of items and prepend it to the
 224              * in-use list */
 225             poolPtr->bytesLeft = POOL_MAX_CHUNK_SIZE;
 226             /* Allocate the requested chunk size, plus the header */
 227             chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + poolPtr->bytesLeft);
 228             chainPtr->nextPtr = poolPtr->headPtr;
 229             poolPtr->headPtr = chainPtr;
 230             /* Peel off a new item. */
 231             poolPtr->bytesLeft -= size;
 232             memPtr = (char *)(chainPtr + 1) + poolPtr->bytesLeft;
 233         }
 234     }
 235     return memPtr;
 236 }
 237
 238 /*
 239  *----------------------------------------------------------------------
 240  *
 241  * StringPoolFreeItem --
 242  *
 243  *      Placeholder for freeProc routine.  String pool memory is
 244  *      not reclaimed or freed until the entire pool is released.
 245  *
 246  * Results:
 247  *      None.
 248  *
 249  *----------------------------------------------------------------------
 250  */
 251 /*ARGSUSED*/
 252 static void
 253 StringPoolFreeItem(poolPtr, item)
 254     struct Blt_PoolStruct *poolPtr;
 255     void *item;
 256 {
 257     /* Does nothing */
 258 }
 259
 260 /*
 261  *       The fixed size pool is a chain of malloc'ed blocks.
 262  *
 263  *             +---------+  +---------+  +---------+
 264  *       NULL<-| nextPtr |<-| nextPtr |<-| nextPtr |<- headPtr
 265  *             |---------|  |---------|  |---------|
 266  *             | chunk1  |  | chunk2  |  | chunk3  |
 267  *             +---------+  |         |  |         |
 268  *                          +---------+  |         |
 269  *                                       |         |
 270  *                                       |         |
 271  *                                       +---------+
 272  *
 273  *      Each chunk contains an integral number of fixed size items.
 274  *      The number of items doubles until a maximum size is reached
 275  *      (each subsequent new chunk will be the maximum).  Chunks
 276  *      are allocated only when needed (no more space is available
 277  *      in the last chunk).
 278  *
 279  *      The chain of blocks is only freed when the entire pool is
 280  *      destroyed.
 281  *
 282  *      A freelist of unused items also maintained. Each freed item
 283  *      is prepended to a free list.  Before allocating new chunks
 284  *      the freelist is examined to see if an unused items exist.
 285  *
 286  *               chunk1       chunk2       chunk3
 287  *            +---------+  +---------+  +---------+
 288  *      NULL<-| unused  |  |         |  |         |
 289  *            +----^----+  +---------+  +---------+
 290  *            | unused  |<-| unused  |<-| unused  |
 291  *            +---------+  +---------+  +----^----+
 292  *            |         |  |         |  | unused  |
 293  *            +---------+  |         |  +----^----+
 294  *                         |         |  |    |    |
 295  *                         +---------+  +----|----+
 296  *                                      | usused  |<- freePtr
 297  *                                      +---------+
 298  */
 299
 300 /*
 301  *----------------------------------------------------------------------
 302  *
 303  * FixedPoolFreeItem --
 304  *
 305  *      Returns a new item.  First check if there is any more space
 306  *      left in the current chunk.  If there isn't then next check
 307  *      the free list for unused items.  Finally allocate a new
 308  *      chunk and return its first item.
 309  *
 310  * Results:
 311  *      Returns a new (possible reused) item.
 312  *
 313  * Side Effects:
 314  *      A new memory chunk may be allocated.
 315  *
 316  *----------------------------------------------------------------------
 317  */
 318 static void *
 319 FixedPoolAllocItem(poolPtr, size)
 320     struct Blt_PoolStruct *poolPtr;
 321     size_t size;
 322 {
 323     Blt_PoolChain *chainPtr;
 324     void *newPtr;
 325
 326     size = ALIGN(size);
 327     if (poolPtr->itemSize == 0) {
 328         poolPtr->itemSize = size;
 329     }
 330     assert(size == poolPtr->itemSize);
 331
 332     if (poolPtr->bytesLeft > 0) {
 333         poolPtr->bytesLeft -= poolPtr->itemSize;
 334         newPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
 335     } else if (poolPtr->freePtr != NULL) { /* Reuse from the free list. */
 336         /* Reuse items on the free list */
 337         chainPtr = poolPtr->freePtr;
 338         poolPtr->freePtr = chainPtr->nextPtr;
 339         newPtr = (void *)chainPtr;
 340     } else {                    /* Allocate another block. */
 341
 342         /* Create a new block of items and prepend it to the in-use list */
 343         poolPtr->bytesLeft = poolPtr->itemSize * (1 << poolPtr->poolSize);
 344         if (poolPtr->bytesLeft < POOL_MAX_CHUNK_SIZE) {
 345             poolPtr->poolSize++; /* Keep doubling the size of the new
 346                                   * chunk up to a maximum size. */
 347         }
 348         /* Allocate the requested chunk size, plus the header */
 349         chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + poolPtr->bytesLeft);
 350         chainPtr->nextPtr = poolPtr->headPtr;
 351         poolPtr->headPtr = chainPtr;
 352
 353         /* Peel off a new item. */
 354         poolPtr->bytesLeft -= poolPtr->itemSize;
 355         newPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
 356     }
 357     return newPtr;
 358 }
 359
 360 /*
 361  *----------------------------------------------------------------------
 362  *
 363  * FixedPoolFreeItem --
 364  *
 365  *      Frees an item.  The actual memory is not freed.  The item
 366  *      instead is prepended to a freelist where it may be reclaimed
 367  *      and used again.
 368  *
 369  * Results:
 370  *      None.
 371  *
 372  * Side Effects:
 373  *      Item is placed on the pool's free list.
 374  *
 375  *----------------------------------------------------------------------
 376  */
 377 static void
 378 FixedPoolFreeItem(poolPtr, item)
 379     struct Blt_PoolStruct *poolPtr;
 380     void *item;
 381 {
 382     Blt_PoolChain *chainPtr = (Blt_PoolChain *)item;
 383
 384     /* Prepend the newly deallocated item to the free list. */
 385     chainPtr->nextPtr = poolPtr->freePtr;
 386     poolPtr->freePtr = chainPtr;
 387 }
 388
 389 /*
 390  *----------------------------------------------------------------------
 391  *
 392  * Blt_PoolCreate --
 393  *
 394  *      Creates a new memory pool for fixed-size/variable-size/string
 395  *      items.
 396  *
 397  * Results:
 398  *      Returns a pointer to the newly allocated pool.
 399  *
 400  *----------------------------------------------------------------------
 401  */
 402
 403 Blt_Pool
 404 Blt_PoolCreate(type)
 405     int type;
 406 {
 407     struct Blt_PoolStruct *poolPtr;
 408
 409     poolPtr = Blt_Malloc(sizeof(struct Blt_PoolStruct));
 410     switch (type) {
 411     case BLT_VARIABLE_SIZE_ITEMS:
 412         poolPtr->allocProc = VariablePoolAllocItem;
 413         poolPtr->freeProc = VariablePoolFreeItem;
 414         break;
 415     case BLT_FIXED_SIZE_ITEMS:
 416         poolPtr->allocProc = FixedPoolAllocItem;
 417         poolPtr->freeProc = FixedPoolFreeItem;
 418         break;
 419     case BLT_STRING_ITEMS:
 420         poolPtr->allocProc = StringPoolAllocItem;
 421         poolPtr->freeProc = StringPoolFreeItem;
 422         break;
 423     }
 424     poolPtr->headPtr = poolPtr->freePtr = NULL;
 425     poolPtr->waste = poolPtr->bytesLeft = 0;
 426     poolPtr->poolSize = poolPtr->itemSize = 0;
 427     return poolPtr;
 428 }
 429
 430 /*
 431  *----------------------------------------------------------------------
 432  *
 433  * Blt_PoolDestroy --
 434  *
 435  *      Destroys the given memory pool.  The chain of allocated blocks
 436  *      are freed.  The is the only time that memory is actually freed.
 437  *
 438  * Results:
 439  *      None.
 440  *
 441  * Side Effects:
 442  *      All memory used by the pool is freed.
 443  *
 444  *----------------------------------------------------------------------
 445  */
 446 void
 447 Blt_PoolDestroy(poolPtr)
 448     struct Blt_PoolStruct *poolPtr;
 449 {
 450     register Blt_PoolChain *chainPtr, *nextPtr;
 451
 452     for (chainPtr = poolPtr->headPtr; chainPtr != NULL; chainPtr = nextPtr) {
 453         nextPtr = chainPtr->nextPtr;
 454         Blt_Free(chainPtr);
 455     }
 456     Blt_Free(poolPtr);
 457 }
 458