summaryrefslogtreecommitdiffstats
path: root/libtecla-1.6.3/freelist.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtecla-1.6.3/freelist.c')
-rw-r--r--libtecla-1.6.3/freelist.c400
1 files changed, 400 insertions, 0 deletions
diff --git a/libtecla-1.6.3/freelist.c b/libtecla-1.6.3/freelist.c
new file mode 100644
index 0000000..d539639
--- /dev/null
+++ b/libtecla-1.6.3/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 <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+
+#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; i<fl->blocking_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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-26 01:31:24 +0000