summaryrefslogtreecommitdiff
path: root/blt/src/bltPool.c
diff options
context:
space:
mode:
Diffstat (limited to 'blt/src/bltPool.c')
-rw-r--r--blt/src/bltPool.c458
1 files changed, 458 insertions, 0 deletions
diff --git a/blt/src/bltPool.c b/blt/src/bltPool.c
new file mode 100644
index 00000000000..fed2743ec47
--- /dev/null
+++ b/blt/src/bltPool.c
@@ -0,0 +1,458 @@
+/*
+ * 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);
+}
+
View Lorry Controller Status