source: trunk/kitgen/8.x/blt/generic/bltPool.c

/*
 * bltPool.c --
 *
 * Copyright 2001 Silicon Metrics, Inc.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that the copyright notice and warranty
 * disclaimer appear in supporting documentation, and that the names
 * of Lucent Technologies any of their entities not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.
 *
 * Silicon Metrics disclaims all warranties with regard to this
 * software, including all implied warranties of merchantability and
 * fitness.  In no event shall Lucent Technologies be liable for any
 * special, indirect or consequential damages or any damages
 * whatsoever resulting from loss of use, data or profits, whether in
 * an action of contract, negligence or other tortuous action, arising
 * out of or in connection with the use or performance of this
 * software.
 */

#include "bltInt.h"
#include "bltPool.h"

/*
 * Blt_Pool --
 *
 *      Implements a pool memory allocator. 
 *
 *        + It's faster allocating memory since malloc/free are called
 *          only a fraction of the normal times.  Fixed size items can 
 *          be reused without deallocating/reallocating memory.
 *        + You don't have the extra 8-16 byte overhead per malloc. 
 *        - Memory is freed only when the entire pool is destroyed.
 *        - Memory is allocated in chunks. More memory is allocated 
 *          than used.  
 *        0 Depending upon allocation/deallocation patterns, locality
 *          may be improved or degraded.
 *
 *      The pool is a chain of malloc'ed blocks.
 *
 *             +---------+  +---------+  +---------+  
 *       NULL<-| nextPtr |<-| nextPtr |<-| nextPtr |<- headPtr
 *             |---------|  |---------|  |---------|  
 *             | chunk1  |  | chunk2  |  | chunk3  |  
 *             +---------+  |         |  |         |  
 *                          +---------+  |         |  
 *                                       |         |  
 *                                       |         |  
 *                                       +---------+  
 *
 *      Each chunk contains an integral number of fixed size items.
 *      The number of items doubles until a maximum size is reached
 *      (each subsequent new chunk will be the maximum).  Chunks
 *      are allocated only when needed (no more space is available
 *      in the last chunk).
 *
 *      The chain of blocks is only freed when the entire pool is
 *      destroyed.  
 *
 *      A freelist of unused items also maintained. Each freed item
 *      is prepended to a free list.  Before allocating new chunks
 *      the freelist is examined to see if an unused items exist.
 *
 *               chunk1       chunk2       chunk3
 *            +---------+  +---------+  +---------+  
 *      NULL<-| unused  |  |         |  |         |
 *            +----^----+  +---------+  +---------+  
 *            | unused  |<-| unused  |<-| unused  |       
 *            +---------+  +---------+  +----^----+  
 *            |         |  |         |  | unused  |
 *            +---------+  |         |  +----^----+
 *                         |         |  |    |    |
 *                         +---------+  +----|----+
 *                                      | usused  |<- freePtr
 *                                      +---------+  
 */

#define POOL_MAX_CHUNK_SIZE      ((1<<16) - sizeof(Blt_PoolChain))

#ifndef ALIGN
#define ALIGN(a) \
        (((size_t)a + (sizeof(void *) - 1)) & (~(sizeof(void *) - 1)))
#endif /* ALIGN */

static Blt_PoolAllocProc VariablePoolAllocItem;
static Blt_PoolFreeProc  VariablePoolFreeItem;
static Blt_PoolAllocProc FixedPoolAllocItem;
static Blt_PoolFreeProc  FixedPoolFreeItem;
static Blt_PoolAllocProc StringPoolAllocItem;
static Blt_PoolFreeProc  StringPoolFreeItem;

/*
 *----------------------------------------------------------------------
 *
 * VariablePoolAllocItem --
 *
 *      Returns a new item.  First check if there is any more space 
 *      left in the current chunk.  If there isn't then next check
 *      the free list for unused items.  Finally allocate a new 
 *      chunk and return its first item.
 *
 * Results:
 *      Returns a new (possible reused) item.
 *
 * Side Effects:
 *      A new memory chunk may be allocated.
 *
 *----------------------------------------------------------------------
 */
static void *
VariablePoolAllocItem(poolPtr, size)
    struct Blt_PoolStruct *poolPtr;
    size_t size;                /* Number of bytes to allocate. */
{
    Blt_PoolChain *chainPtr;
    void *memPtr;

    size = ALIGN(size);
    if (size >= POOL_MAX_CHUNK_SIZE) {
        /* 
         * Handle oversized requests by allocating a chunk to hold the
         * single item and immediately placing it into the in-use list.
         */
        chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + size);
        if (poolPtr->headPtr == NULL) {
            poolPtr->headPtr = chainPtr;
        } else {
            chainPtr->nextPtr = poolPtr->headPtr->nextPtr;
            poolPtr->headPtr->nextPtr = chainPtr;
        }
        memPtr = (void *)chainPtr;
    } else {
        if (poolPtr->bytesLeft >= size) {
            poolPtr->bytesLeft -= size;
            memPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
        } else {
            poolPtr->waste += poolPtr->bytesLeft;
            /* Create a new block of items and prepend it to the in-use list */
            poolPtr->bytesLeft = POOL_MAX_CHUNK_SIZE;
            /* Allocate the requested chunk size, plus the header */
            chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + poolPtr->bytesLeft);
            chainPtr->nextPtr = poolPtr->headPtr;
            poolPtr->headPtr = chainPtr;
            /* Peel off a new item. */
            poolPtr->bytesLeft -= size;
            memPtr = (char *)(chainPtr + 1) + poolPtr->bytesLeft;
        }
    }
    return memPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * VariablePoolFreeItem --
 *
 *      Placeholder for freeProc routine.  The pool memory is 
 *      not reclaimed or freed until the entire pool is released.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
static void
VariablePoolFreeItem(poolPtr, item) 
    struct Blt_PoolStruct *poolPtr;
    void *item;
{
    /* Does nothing */
}

/*
 *----------------------------------------------------------------------
 *
 * StringPoolAllocItem --
 *
 *      Returns a new item.  First check if there is any more space 
 *      left in the current chunk.  If there isn't then next check
 *      the free list for unused items.  Finally allocate a new 
 *      chunk and return its first item.
 *
 * Results:
 *      Returns a new (possible reused) item.
 *
 * Side Effects:
 *      A new memory chunk may be allocated.
 *
 *----------------------------------------------------------------------
 */
static void *
StringPoolAllocItem(poolPtr, size)
    struct Blt_PoolStruct *poolPtr;
    size_t size;                /* Number of bytes to allocate. */
{
    Blt_PoolChain *chainPtr;
    void *memPtr;

    if (size >= POOL_MAX_CHUNK_SIZE) {
        /* 
         * Handle oversized requests by allocating a chunk to hold the
         * single item and immediately placing it into the in-use list.
         */
        chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + size);
        if (poolPtr->headPtr == NULL) {
            poolPtr->headPtr = chainPtr;
        } else {
            chainPtr->nextPtr = poolPtr->headPtr->nextPtr;
            poolPtr->headPtr->nextPtr = chainPtr;
        }
        memPtr = (void *)chainPtr;
    } else {
        if (poolPtr->bytesLeft >= size) {
            poolPtr->bytesLeft -= size;
            memPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
        } else {
            poolPtr->waste += poolPtr->bytesLeft;
            /* Create a new block of items and prepend it to the
             * in-use list */
            poolPtr->bytesLeft = POOL_MAX_CHUNK_SIZE;
            /* Allocate the requested chunk size, plus the header */
            chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + poolPtr->bytesLeft);
            chainPtr->nextPtr = poolPtr->headPtr;
            poolPtr->headPtr = chainPtr;
            /* Peel off a new item. */
            poolPtr->bytesLeft -= size;
            memPtr = (char *)(chainPtr + 1) + poolPtr->bytesLeft;
        }
    }
    return memPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * StringPoolFreeItem --
 *
 *      Placeholder for freeProc routine.  String pool memory is 
 *      not reclaimed or freed until the entire pool is released.
 *
 * Results:
 *      None.
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
static void
StringPoolFreeItem(poolPtr, item) 
    struct Blt_PoolStruct *poolPtr;
    void *item;
{
    /* Does nothing */
}

/*
 *       The fixed size pool is a chain of malloc'ed blocks.
 *
 *             +---------+  +---------+  +---------+  
 *       NULL<-| nextPtr |<-| nextPtr |<-| nextPtr |<- headPtr
 *             |---------|  |---------|  |---------|  
 *             | chunk1  |  | chunk2  |  | chunk3  |  
 *             +---------+  |         |  |         |  
 *                          +---------+  |         |  
 *                                       |         |  
 *                                       |         |  
 *                                       +---------+  
 *
 *      Each chunk contains an integral number of fixed size items.
 *      The number of items doubles until a maximum size is reached
 *      (each subsequent new chunk will be the maximum).  Chunks
 *      are allocated only when needed (no more space is available
 *      in the last chunk).
 *
 *      The chain of blocks is only freed when the entire pool is
 *      destroyed.  
 *
 *      A freelist of unused items also maintained. Each freed item
 *      is prepended to a free list.  Before allocating new chunks
 *      the freelist is examined to see if an unused items exist.
 *
 *               chunk1       chunk2       chunk3
 *            +---------+  +---------+  +---------+  
 *      NULL<-| unused  |  |         |  |         |
 *            +----^----+  +---------+  +---------+  
 *            | unused  |<-| unused  |<-| unused  |       
 *            +---------+  +---------+  +----^----+  
 *            |         |  |         |  | unused  |
 *            +---------+  |         |  +----^----+
 *                         |         |  |    |    |
 *                         +---------+  +----|----+
 *                                      | usused  |<- freePtr
 *                                      +---------+  
 */

/*
 *----------------------------------------------------------------------
 *
 * FixedPoolFreeItem --
 *
 *      Returns a new item.  First check if there is any more space 
 *      left in the current chunk.  If there isn't then next check
 *      the free list for unused items.  Finally allocate a new 
 *      chunk and return its first item.
 *
 * Results:
 *      Returns a new (possible reused) item.
 *
 * Side Effects:
 *      A new memory chunk may be allocated.
 *
 *----------------------------------------------------------------------
 */
static void *
FixedPoolAllocItem(poolPtr, size)
    struct Blt_PoolStruct *poolPtr;
    size_t size;
{
    Blt_PoolChain *chainPtr;
    void *newPtr;

    size = ALIGN(size);
    if (poolPtr->itemSize == 0) {
        poolPtr->itemSize = size;
    }
    assert(size == poolPtr->itemSize);

    if (poolPtr->bytesLeft > 0) {
        poolPtr->bytesLeft -= poolPtr->itemSize;
        newPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
    } else if (poolPtr->freePtr != NULL) { /* Reuse from the free list. */
        /* Reuse items on the free list */
        chainPtr = poolPtr->freePtr;
        poolPtr->freePtr = chainPtr->nextPtr;
        newPtr = (void *)chainPtr;
    } else {                    /* Allocate another block. */
        
        /* Create a new block of items and prepend it to the in-use list */
        poolPtr->bytesLeft = poolPtr->itemSize * (1 << poolPtr->poolSize);
        if (poolPtr->bytesLeft < POOL_MAX_CHUNK_SIZE) {
            poolPtr->poolSize++; /* Keep doubling the size of the new 
                                  * chunk up to a maximum size. */
        }
        /* Allocate the requested chunk size, plus the header */
        chainPtr = Blt_Malloc(sizeof(Blt_PoolChain) + poolPtr->bytesLeft);
        chainPtr->nextPtr = poolPtr->headPtr;
        poolPtr->headPtr = chainPtr;

        /* Peel off a new item. */
        poolPtr->bytesLeft -= poolPtr->itemSize;
        newPtr = (char *)(poolPtr->headPtr + 1) + poolPtr->bytesLeft;
    }
    return newPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * FixedPoolFreeItem --
 *
 *      Frees an item.  The actual memory is not freed.  The item
 *      instead is prepended to a freelist where it may be reclaimed
 *      and used again.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      Item is placed on the pool's free list.
 *
 *----------------------------------------------------------------------
 */
static void
FixedPoolFreeItem(poolPtr, item) 
    struct Blt_PoolStruct *poolPtr;
    void *item;
{
    Blt_PoolChain *chainPtr = (Blt_PoolChain *)item;
    
    /* Prepend the newly deallocated item to the free list. */
    chainPtr->nextPtr = poolPtr->freePtr;
    poolPtr->freePtr = chainPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_PoolCreate --
 *
 *      Creates a new memory pool for fixed-size/variable-size/string
 *      items.  
 *
 * Results:
 *      Returns a pointer to the newly allocated pool.
 *
 *---------------------------------------------------------------------- 
 */

Blt_Pool
Blt_PoolCreate(type)
    int type;
{
    struct Blt_PoolStruct *poolPtr;

    poolPtr = Blt_Malloc(sizeof(struct Blt_PoolStruct));
    switch (type) {
    case BLT_VARIABLE_SIZE_ITEMS:
        poolPtr->allocProc = VariablePoolAllocItem;
        poolPtr->freeProc = VariablePoolFreeItem;
        break;
    case BLT_FIXED_SIZE_ITEMS:
        poolPtr->allocProc = FixedPoolAllocItem;
        poolPtr->freeProc = FixedPoolFreeItem;
        break;
    case BLT_STRING_ITEMS:
        poolPtr->allocProc = StringPoolAllocItem;
        poolPtr->freeProc = StringPoolFreeItem;
        break;
    }
    poolPtr->headPtr = poolPtr->freePtr = NULL;
    poolPtr->waste = poolPtr->bytesLeft = 0;
    poolPtr->poolSize = poolPtr->itemSize = 0;
    return poolPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_PoolDestroy --
 *
 *      Destroys the given memory pool.  The chain of allocated blocks
 *      are freed.  The is the only time that memory is actually freed.
 *
 * Results:
 *      None.
 *
 * Side Effects:
 *      All memory used by the pool is freed.
 *
 *----------------------------------------------------------------------
 */
void  
Blt_PoolDestroy(poolPtr)
    struct Blt_PoolStruct *poolPtr;
{
    register Blt_PoolChain *chainPtr, *nextPtr;
    
    for (chainPtr = poolPtr->headPtr; chainPtr != NULL; chainPtr = nextPtr) {
        nextPtr = chainPtr->nextPtr;
        Blt_Free(chainPtr);
    }
    Blt_Free(poolPtr);
}