summaryrefslogtreecommitdiff
path: root/libtecla-1.4.1/freelist.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtecla-1.4.1/freelist.c')
-rw-r--r--libtecla-1.4.1/freelist.c393
1 files changed, 0 insertions, 393 deletions
diff --git a/libtecla-1.4.1/freelist.c b/libtecla-1.4.1/freelist.c
deleted file mode 100644
index 4fe0472..0000000
--- a/libtecla-1.4.1/freelist.c
+++ /dev/null
@@ -1,393 +0,0 @@
-/*
- * Copyright (c) 2000, 2001 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 "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 */
- 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:
- * caller const char * The name of the calling function, for use in
- * error messages, or NULL to not report errors
- * to stderr.
- * 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(const char *caller, 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) {
- if(caller)
- fprintf(stderr, "_new_FreeList (%s): Insufficient memory.\n", caller);
- 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->block = NULL;
- fl->free_list = NULL;
-/*
- * Allocate the first block of memory.
- */
- fl->block = _new_FreeListBlock(fl);
- if(!fl->block) {
- if(caller)
- fprintf(stderr, "_new_FreeList (%s): Insufficient memory.\n", caller);
- return _del_FreeList(caller, 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:
- * caller const char * The name of the calling function, for use in
- * error messages, or NULL if error messages
- * shouldn't be reported to stderr.
- * 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(const char *caller, FreeList *fl, int force)
-{
- if(fl) {
-/*
- * Check whether any nodes are in use.
- */
- if(!force && _busy_FreeListNodes(fl) != 0) {
- if(caller)
- fprintf(stderr, "_del_FreeList (%s): %ld nodes are still in use.\n",
- caller, _busy_FreeListNodes(fl));
- 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:
- * caller const char * The name of the calling function, for use in
- * error messages, or NULL to not report errors
- * to stderr.
- * 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;
-}
-
-/*.......................................................................
- * 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);
- 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-05-17 13:50:55 +0000