+++ /dev/null
-/*
- * 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);
-}
-
OSDN Git Service
