From bc8510c4ea9da320e263b2eecd11a7b309b0e11e Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Wed, 27 May 2015 13:47:55 -0700 Subject: Add libtecla 1.6.3 --- libtecla/freelist.c | 400 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 400 insertions(+) create mode 100644 libtecla/freelist.c (limited to 'libtecla/freelist.c') diff --git a/libtecla/freelist.c b/libtecla/freelist.c new file mode 100644 index 0000000..d539639 --- /dev/null +++ b/libtecla/freelist.c @@ -0,0 +1,400 @@ +/* + * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2012 by Martin C. Shepherd. + * + * All rights reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, and/or sell copies of the Software, and to permit persons + * to whom the Software is furnished to do so, provided that the above + * copyright notice(s) and this permission notice appear in all copies of + * the Software and that both the above copyright notice(s) and this + * permission notice appear in supporting documentation. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT + * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR + * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR 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 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION + * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * Except as contained in this notice, the name of a copyright holder + * shall not be used in advertising or otherwise to promote the sale, use + * or other dealings in this Software without prior written authorization + * of the copyright holder. + */ + +#include +#include +#include + +#include "freelist.h" + +typedef struct FreeListBlock FreeListBlock; +struct FreeListBlock { + FreeListBlock *next; /* The next block in the list */ + char *nodes; /* The array of free-list nodes */ +}; + +struct FreeList { + size_t node_size; /* The size of a free-list node */ + unsigned blocking_factor; /* The number of nodes per block */ + long nbusy; /* The number of nodes that are in use */ + long ntotal; /* The total number of nodes in the free list */ + FreeListBlock *block; /* The head of the list of free-list blocks */ + void *free_list; /* The free-list of nodes */ +}; + +static FreeListBlock *_new_FreeListBlock(FreeList *fl); +static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl); +static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block); + +/*....................................................................... + * Allocate a new free-list from blocks of 'blocking_factor' objects of size + * node_size. + * + * Input: + * node_size size_t The size of the free-list nodes to be returned + * by _new_FreeListNode(). Use sizeof() to + * determine this. + * blocking_factor unsigned The number of objects of size 'object_size' + * to allocate per block. + * Output: + * return FreeList * The new freelist, or NULL on error. + */ +FreeList *_new_FreeList(size_t node_size, unsigned blocking_factor) +{ + FreeList *fl; /* The new free-list container */ +/* + * When a free-list node is on the free-list, it is used as a (void *) + * link field. Roundup node_size to a mulitple of the size of a void + * pointer. This, plus the fact that the array of nodes is obtained via + * malloc, which returns memory suitably aligned for any object, will + * ensure that the first sizeof(void *) bytes of each node will be + * suitably aligned to use as a (void *) link pointer. + */ + node_size = sizeof(void *) * + ((node_size + sizeof(void *) - 1) / sizeof(void *)); +/* + * Enfore a minimum block size. + */ + if(blocking_factor < 1) + blocking_factor = 1; +/* + * Allocate the container of the free list. + */ + fl = (FreeList *) malloc(sizeof(FreeList)); + if(!fl) { + errno = ENOMEM; + return NULL; + }; +/* + * Before attempting any operation that might fail, initialize the + * container at least up to the point at which it can safely be passed + * to _del_FreeList(). + */ + fl->node_size = node_size; + fl->blocking_factor = blocking_factor; + fl->nbusy = 0; + fl->ntotal = 0; + fl->block = NULL; + fl->free_list = NULL; +/* + * Allocate the first block of memory. + */ + fl->block = _new_FreeListBlock(fl); + if(!fl->block) { + errno = ENOMEM; + return _del_FreeList(fl, 1); + }; +/* + * Add the new list of nodes to the free-list. + */ + fl->free_list = fl->block->nodes; +/* + * Return the free-list for use. + */ + return fl; +} + +/*....................................................................... + * Re-thread a freelist to reclaim all allocated nodes. + * This function should not be called unless if it is known that none + * of the currently allocated nodes are still being used. + * + * Input: + * fl FreeList * The free-list to be reset, or NULL. + */ +void _rst_FreeList(FreeList *fl) +{ + if(fl) { + FreeListBlock *block; +/* + * Re-thread the nodes of each block into individual free-lists. + */ + for(block=fl->block; block; block=block->next) + _thread_FreeListBlock(fl, block); +/* + * Link all of the block freelists into one large freelist. + */ + fl->free_list = NULL; + for(block=fl->block; block; block=block->next) { +/* + * Locate the last node of the current block. + */ + char *last_node = block->nodes + fl->node_size * + (fl->blocking_factor - 1); +/* + * Make the link-field of the last node point to the first + * node of the current freelist, then make the first node of the + * new block the start of the freelist. + */ + *(void **)last_node = fl->free_list; + fl->free_list = block->nodes; + }; +/* + * All allocated nodes have now been returned to the freelist. + */ + fl->nbusy = 0; + }; +} + +/*....................................................................... + * Delete a free-list. + * + * Input: + * fl FreeList * The free-list to be deleted, or NULL. + * force int If force==0 then _del_FreeList() will complain + * and refuse to delete the free-list if any + * of nodes have not been returned to the free-list. + * If force!=0 then _del_FreeList() will not check + * whether any nodes are still in use and will + * always delete the list. + * Output: + * return FreeList * Always NULL (even if the list couldn't be + * deleted). + */ +FreeList *_del_FreeList(FreeList *fl, int force) +{ + if(fl) { +/* + * Check whether any nodes are in use. + */ + if(!force && _busy_FreeListNodes(fl) != 0) { + errno = EBUSY; + return NULL; + }; +/* + * Delete the list blocks. + */ + { + FreeListBlock *next = fl->block; + while(next) { + FreeListBlock *block = next; + next = block->next; + block = _del_FreeListBlock(block); + }; + }; + fl->block = NULL; + fl->free_list = NULL; +/* + * Discard the container. + */ + free(fl); + }; + return NULL; +} + +/*....................................................................... + * Allocate a new object from a free-list. + * + * Input: + * fl FreeList * The free-list to return an object from. + * Output: + * return void * A new object of the size that was specified via + * the node_size argument of _new_FreeList() when + * the free-list was created, or NULL if there + * is insufficient memory, or 'fl' is NULL. + */ +void *_new_FreeListNode(FreeList *fl) +{ + void *node; /* The node to be returned */ +/* + * Check arguments. + */ + if(!fl) + return NULL; +/* + * If the free-list has been exhausted extend it by allocating + * another block of nodes. + */ + if(!fl->free_list) { + FreeListBlock *block = _new_FreeListBlock(fl); + if(!block) + return NULL; +/* + * Prepend the new block to the list of free-list blocks. + */ + block->next = fl->block; + fl->block = block; +/* + * Add the new list of nodes to the free-list. + */ + fl->free_list = fl->block->nodes; + }; +/* + * Remove and return a node from the front of the free list. + */ + node = fl->free_list; + fl->free_list = *(void **)node; +/* + * Record the loss of a node from the free-list. + */ + fl->nbusy++; +/* + * Return the node. + */ + return node; +} + +/*....................................................................... + * Return an object to the free-list that it was allocated from. + * + * Input: + * fl FreeList * The free-list from which the object was taken. + * object void * The node to be returned. + * Output: + * return void * Always NULL. + */ +void *_del_FreeListNode(FreeList *fl, void *object) +{ +/* + * Check arguments. + */ + if(!fl) + return NULL; +/* + * Return the node to the head of the free list. + */ + if(object) { + *(void **)object = fl->free_list; + fl->free_list = object; +/* + * Record the return of the node to the free-list. + */ + fl->nbusy--; + }; + return NULL; +} + +/*....................................................................... + * Return a count of the number of nodes that are currently allocated. + * + * Input: + * fl FreeList * The list to count wrt, or NULL. + * Output: + * return long The number of nodes (or 0 if fl==NULL). + */ +long _busy_FreeListNodes(FreeList *fl) +{ + return fl ? fl->nbusy : 0; +} + +/*....................................................................... + * Query the number of allocated nodes in the freelist which are + * currently unused. + * + * Input: + * fl FreeList * The list to count wrt, or NULL. + * Output: + * return long The number of unused nodes (or 0 if fl==NULL). + */ +long _idle_FreeListNodes(FreeList *fl) +{ + return fl ? (fl->ntotal - fl->nbusy) : 0; +} + +/*....................................................................... + * Allocate a new list of free-list nodes. On return the nodes will + * be linked together as a list starting with the node at the lowest + * address and ending with a NULL next pointer. + * + * Input: + * fl FreeList * The free-list to allocate the list for. + * Output: + * return FreeListBlock * The new linked block of free-list nodes, + * or NULL on error. + */ +static FreeListBlock *_new_FreeListBlock(FreeList *fl) +{ + FreeListBlock *block; /* The new block to be returned */ +/* + * Allocate the container. + */ + block = (FreeListBlock *) malloc(sizeof(FreeListBlock)); + if(!block) + return NULL; +/* + * Before attempting any operation that might fail, initialize the + * container at least up to the point at which it can safely be passed + * to _del_FreeListBlock(). + */ + block->next = NULL; + block->nodes = NULL; +/* + * Allocate the block of nodes. + */ + block->nodes = (char *) malloc(fl->node_size * fl->blocking_factor); + if(!block->nodes) + return _del_FreeListBlock(block); +/* + * Initialize the block as a linked list of FreeListNode's. + */ + _thread_FreeListBlock(fl, block); +/* + * Update the record of the number of nodes in the freelist. + */ + fl->ntotal += fl->blocking_factor; + return block; +} + +/*....................................................................... + * Link each node of a freelist block to the node that follows it. + * + * Input: + * fl FreeList * The freelist that contains the block. + * block FreeListBlock * The block to be threaded. + */ +static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block) +{ + char *mem = block->nodes; + int i; + for(i=0; iblocking_factor - 1; i++, mem += fl->node_size) + *(void **)mem = mem + fl->node_size; /* Link to the next node */ + *(void **)mem = NULL; /* Terminate the list */ +} + +/*....................................................................... + * Delete a free-list block. + * + * Input: + * fl FreeListBlock * The block to be deleted, or NULL. + * Output: + * return FreeListBlock * Always NULL. + */ +static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl) +{ + if(fl) { + fl->next = NULL; + if(fl->nodes) + free(fl->nodes); + fl->nodes = NULL; + free(fl); + }; + return NULL; +} -- cgit v1.2.3