17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
3*1da57d55SToomas Soome *
47c478bd9Sstevel@tonic-gate * All rights reserved.
5*1da57d55SToomas Soome *
67c478bd9Sstevel@tonic-gate * Permission is hereby granted, free of charge, to any person obtaining a
77c478bd9Sstevel@tonic-gate * copy of this software and associated documentation files (the
87c478bd9Sstevel@tonic-gate * "Software"), to deal in the Software without restriction, including
97c478bd9Sstevel@tonic-gate * without limitation the rights to use, copy, modify, merge, publish,
107c478bd9Sstevel@tonic-gate * distribute, and/or sell copies of the Software, and to permit persons
117c478bd9Sstevel@tonic-gate * to whom the Software is furnished to do so, provided that the above
127c478bd9Sstevel@tonic-gate * copyright notice(s) and this permission notice appear in all copies of
137c478bd9Sstevel@tonic-gate * the Software and that both the above copyright notice(s) and this
147c478bd9Sstevel@tonic-gate * permission notice appear in supporting documentation.
15*1da57d55SToomas Soome *
167c478bd9Sstevel@tonic-gate * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
177c478bd9Sstevel@tonic-gate * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
187c478bd9Sstevel@tonic-gate * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
197c478bd9Sstevel@tonic-gate * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
207c478bd9Sstevel@tonic-gate * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
217c478bd9Sstevel@tonic-gate * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
227c478bd9Sstevel@tonic-gate * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
237c478bd9Sstevel@tonic-gate * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
247c478bd9Sstevel@tonic-gate * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
25*1da57d55SToomas Soome *
267c478bd9Sstevel@tonic-gate * Except as contained in this notice, the name of a copyright holder
277c478bd9Sstevel@tonic-gate * shall not be used in advertising or otherwise to promote the sale, use
287c478bd9Sstevel@tonic-gate * or other dealings in this Software without prior written authorization
297c478bd9Sstevel@tonic-gate * of the copyright holder.
307c478bd9Sstevel@tonic-gate */
317c478bd9Sstevel@tonic-gate
327c478bd9Sstevel@tonic-gate #include <stdio.h>
337c478bd9Sstevel@tonic-gate #include <stdlib.h>
347c478bd9Sstevel@tonic-gate #include <errno.h>
357c478bd9Sstevel@tonic-gate
367c478bd9Sstevel@tonic-gate #include "freelist.h"
377c478bd9Sstevel@tonic-gate
387c478bd9Sstevel@tonic-gate typedef struct FreeListBlock FreeListBlock;
397c478bd9Sstevel@tonic-gate struct FreeListBlock {
407c478bd9Sstevel@tonic-gate FreeListBlock *next; /* The next block in the list */
417c478bd9Sstevel@tonic-gate char *nodes; /* The array of free-list nodes */
427c478bd9Sstevel@tonic-gate };
437c478bd9Sstevel@tonic-gate
447c478bd9Sstevel@tonic-gate struct FreeList {
457c478bd9Sstevel@tonic-gate size_t node_size; /* The size of a free-list node */
467c478bd9Sstevel@tonic-gate unsigned blocking_factor; /* The number of nodes per block */
477c478bd9Sstevel@tonic-gate long nbusy; /* The number of nodes that are in use */
487c478bd9Sstevel@tonic-gate long ntotal; /* The total number of nodes in the free list */
497c478bd9Sstevel@tonic-gate FreeListBlock *block; /* The head of the list of free-list blocks */
507c478bd9Sstevel@tonic-gate void *free_list; /* The free-list of nodes */
517c478bd9Sstevel@tonic-gate };
527c478bd9Sstevel@tonic-gate
537c478bd9Sstevel@tonic-gate static FreeListBlock *_new_FreeListBlock(FreeList *fl);
547c478bd9Sstevel@tonic-gate static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl);
557c478bd9Sstevel@tonic-gate static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block);
567c478bd9Sstevel@tonic-gate
577c478bd9Sstevel@tonic-gate /*.......................................................................
587c478bd9Sstevel@tonic-gate * Allocate a new free-list from blocks of 'blocking_factor' objects of size
597c478bd9Sstevel@tonic-gate * node_size.
607c478bd9Sstevel@tonic-gate *
617c478bd9Sstevel@tonic-gate * Input:
627c478bd9Sstevel@tonic-gate * node_size size_t The size of the free-list nodes to be returned
637c478bd9Sstevel@tonic-gate * by _new_FreeListNode(). Use sizeof() to
647c478bd9Sstevel@tonic-gate * determine this.
657c478bd9Sstevel@tonic-gate * blocking_factor unsigned The number of objects of size 'object_size'
667c478bd9Sstevel@tonic-gate * to allocate per block.
677c478bd9Sstevel@tonic-gate * Output:
687c478bd9Sstevel@tonic-gate * return FreeList * The new freelist, or NULL on error.
697c478bd9Sstevel@tonic-gate */
_new_FreeList(size_t node_size,unsigned blocking_factor)707c478bd9Sstevel@tonic-gate FreeList *_new_FreeList(size_t node_size, unsigned blocking_factor)
717c478bd9Sstevel@tonic-gate {
727c478bd9Sstevel@tonic-gate FreeList *fl; /* The new free-list container */
737c478bd9Sstevel@tonic-gate /*
747c478bd9Sstevel@tonic-gate * When a free-list node is on the free-list, it is used as a (void *)
757c478bd9Sstevel@tonic-gate * link field. Roundup node_size to a mulitple of the size of a void
767c478bd9Sstevel@tonic-gate * pointer. This, plus the fact that the array of nodes is obtained via
777c478bd9Sstevel@tonic-gate * malloc, which returns memory suitably aligned for any object, will
787c478bd9Sstevel@tonic-gate * ensure that the first sizeof(void *) bytes of each node will be
797c478bd9Sstevel@tonic-gate * suitably aligned to use as a (void *) link pointer.
807c478bd9Sstevel@tonic-gate */
817c478bd9Sstevel@tonic-gate node_size = sizeof(void *) *
827c478bd9Sstevel@tonic-gate ((node_size + sizeof(void *) - 1) / sizeof(void *));
837c478bd9Sstevel@tonic-gate /*
847c478bd9Sstevel@tonic-gate * Enfore a minimum block size.
857c478bd9Sstevel@tonic-gate */
867c478bd9Sstevel@tonic-gate if(blocking_factor < 1)
877c478bd9Sstevel@tonic-gate blocking_factor = 1;
887c478bd9Sstevel@tonic-gate /*
897c478bd9Sstevel@tonic-gate * Allocate the container of the free list.
907c478bd9Sstevel@tonic-gate */
917c478bd9Sstevel@tonic-gate fl = (FreeList *) malloc(sizeof(FreeList));
927c478bd9Sstevel@tonic-gate if(!fl) {
937c478bd9Sstevel@tonic-gate errno = ENOMEM;
947c478bd9Sstevel@tonic-gate return NULL;
957c478bd9Sstevel@tonic-gate };
967c478bd9Sstevel@tonic-gate /*
977c478bd9Sstevel@tonic-gate * Before attempting any operation that might fail, initialize the
987c478bd9Sstevel@tonic-gate * container at least up to the point at which it can safely be passed
997c478bd9Sstevel@tonic-gate * to _del_FreeList().
1007c478bd9Sstevel@tonic-gate */
1017c478bd9Sstevel@tonic-gate fl->node_size = node_size;
1027c478bd9Sstevel@tonic-gate fl->blocking_factor = blocking_factor;
1037c478bd9Sstevel@tonic-gate fl->nbusy = 0;
1047c478bd9Sstevel@tonic-gate fl->ntotal = 0;
1057c478bd9Sstevel@tonic-gate fl->block = NULL;
1067c478bd9Sstevel@tonic-gate fl->free_list = NULL;
1077c478bd9Sstevel@tonic-gate /*
1087c478bd9Sstevel@tonic-gate * Allocate the first block of memory.
1097c478bd9Sstevel@tonic-gate */
1107c478bd9Sstevel@tonic-gate fl->block = _new_FreeListBlock(fl);
1117c478bd9Sstevel@tonic-gate if(!fl->block) {
1127c478bd9Sstevel@tonic-gate errno = ENOMEM;
1137c478bd9Sstevel@tonic-gate return _del_FreeList(fl, 1);
1147c478bd9Sstevel@tonic-gate };
1157c478bd9Sstevel@tonic-gate /*
1167c478bd9Sstevel@tonic-gate * Add the new list of nodes to the free-list.
1177c478bd9Sstevel@tonic-gate */
1187c478bd9Sstevel@tonic-gate fl->free_list = fl->block->nodes;
1197c478bd9Sstevel@tonic-gate /*
1207c478bd9Sstevel@tonic-gate * Return the free-list for use.
1217c478bd9Sstevel@tonic-gate */
1227c478bd9Sstevel@tonic-gate return fl;
1237c478bd9Sstevel@tonic-gate }
1247c478bd9Sstevel@tonic-gate
1257c478bd9Sstevel@tonic-gate /*.......................................................................
1267c478bd9Sstevel@tonic-gate * Re-thread a freelist to reclaim all allocated nodes.
1277c478bd9Sstevel@tonic-gate * This function should not be called unless if it is known that none
1287c478bd9Sstevel@tonic-gate * of the currently allocated nodes are still being used.
1297c478bd9Sstevel@tonic-gate *
1307c478bd9Sstevel@tonic-gate * Input:
1317c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to be reset, or NULL.
1327c478bd9Sstevel@tonic-gate */
_rst_FreeList(FreeList * fl)1337c478bd9Sstevel@tonic-gate void _rst_FreeList(FreeList *fl)
1347c478bd9Sstevel@tonic-gate {
1357c478bd9Sstevel@tonic-gate if(fl) {
1367c478bd9Sstevel@tonic-gate FreeListBlock *block;
1377c478bd9Sstevel@tonic-gate /*
1387c478bd9Sstevel@tonic-gate * Re-thread the nodes of each block into individual free-lists.
1397c478bd9Sstevel@tonic-gate */
1407c478bd9Sstevel@tonic-gate for(block=fl->block; block; block=block->next)
1417c478bd9Sstevel@tonic-gate _thread_FreeListBlock(fl, block);
1427c478bd9Sstevel@tonic-gate /*
1437c478bd9Sstevel@tonic-gate * Link all of the block freelists into one large freelist.
1447c478bd9Sstevel@tonic-gate */
1457c478bd9Sstevel@tonic-gate fl->free_list = NULL;
1467c478bd9Sstevel@tonic-gate for(block=fl->block; block; block=block->next) {
1477c478bd9Sstevel@tonic-gate /*
1487c478bd9Sstevel@tonic-gate * Locate the last node of the current block.
1497c478bd9Sstevel@tonic-gate */
1507c478bd9Sstevel@tonic-gate char *last_node = block->nodes + fl->node_size *
1517c478bd9Sstevel@tonic-gate (fl->blocking_factor - 1);
1527c478bd9Sstevel@tonic-gate /*
1537c478bd9Sstevel@tonic-gate * Make the link-field of the last node point to the first
1547c478bd9Sstevel@tonic-gate * node of the current freelist, then make the first node of the
155*1da57d55SToomas Soome * new block the start of the freelist.
1567c478bd9Sstevel@tonic-gate */
1577c478bd9Sstevel@tonic-gate *(void **)last_node = fl->free_list;
1587c478bd9Sstevel@tonic-gate fl->free_list = block->nodes;
1597c478bd9Sstevel@tonic-gate };
1607c478bd9Sstevel@tonic-gate /*
1617c478bd9Sstevel@tonic-gate * All allocated nodes have now been returned to the freelist.
1627c478bd9Sstevel@tonic-gate */
1637c478bd9Sstevel@tonic-gate fl->nbusy = 0;
1647c478bd9Sstevel@tonic-gate };
1657c478bd9Sstevel@tonic-gate }
1667c478bd9Sstevel@tonic-gate
1677c478bd9Sstevel@tonic-gate /*.......................................................................
1687c478bd9Sstevel@tonic-gate * Delete a free-list.
1697c478bd9Sstevel@tonic-gate *
1707c478bd9Sstevel@tonic-gate * Input:
1717c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to be deleted, or NULL.
1727c478bd9Sstevel@tonic-gate * force int If force==0 then _del_FreeList() will complain
1737c478bd9Sstevel@tonic-gate * and refuse to delete the free-list if any
1747c478bd9Sstevel@tonic-gate * of nodes have not been returned to the free-list.
1757c478bd9Sstevel@tonic-gate * If force!=0 then _del_FreeList() will not check
1767c478bd9Sstevel@tonic-gate * whether any nodes are still in use and will
1777c478bd9Sstevel@tonic-gate * always delete the list.
1787c478bd9Sstevel@tonic-gate * Output:
1797c478bd9Sstevel@tonic-gate * return FreeList * Always NULL (even if the list couldn't be
1807c478bd9Sstevel@tonic-gate * deleted).
1817c478bd9Sstevel@tonic-gate */
_del_FreeList(FreeList * fl,int force)1827c478bd9Sstevel@tonic-gate FreeList *_del_FreeList(FreeList *fl, int force)
1837c478bd9Sstevel@tonic-gate {
1847c478bd9Sstevel@tonic-gate if(fl) {
1857c478bd9Sstevel@tonic-gate /*
1867c478bd9Sstevel@tonic-gate * Check whether any nodes are in use.
1877c478bd9Sstevel@tonic-gate */
1887c478bd9Sstevel@tonic-gate if(!force && _busy_FreeListNodes(fl) != 0) {
1897c478bd9Sstevel@tonic-gate errno = EBUSY;
1907c478bd9Sstevel@tonic-gate return NULL;
1917c478bd9Sstevel@tonic-gate };
1927c478bd9Sstevel@tonic-gate /*
1937c478bd9Sstevel@tonic-gate * Delete the list blocks.
1947c478bd9Sstevel@tonic-gate */
1957c478bd9Sstevel@tonic-gate {
1967c478bd9Sstevel@tonic-gate FreeListBlock *next = fl->block;
1977c478bd9Sstevel@tonic-gate while(next) {
1987c478bd9Sstevel@tonic-gate FreeListBlock *block = next;
1997c478bd9Sstevel@tonic-gate next = block->next;
2007c478bd9Sstevel@tonic-gate block = _del_FreeListBlock(block);
2017c478bd9Sstevel@tonic-gate };
2027c478bd9Sstevel@tonic-gate };
2037c478bd9Sstevel@tonic-gate fl->block = NULL;
2047c478bd9Sstevel@tonic-gate fl->free_list = NULL;
2057c478bd9Sstevel@tonic-gate /*
2067c478bd9Sstevel@tonic-gate * Discard the container.
2077c478bd9Sstevel@tonic-gate */
2087c478bd9Sstevel@tonic-gate free(fl);
2097c478bd9Sstevel@tonic-gate };
2107c478bd9Sstevel@tonic-gate return NULL;
2117c478bd9Sstevel@tonic-gate }
2127c478bd9Sstevel@tonic-gate
2137c478bd9Sstevel@tonic-gate /*.......................................................................
2147c478bd9Sstevel@tonic-gate * Allocate a new object from a free-list.
2157c478bd9Sstevel@tonic-gate *
2167c478bd9Sstevel@tonic-gate * Input:
2177c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to return an object from.
2187c478bd9Sstevel@tonic-gate * Output:
2197c478bd9Sstevel@tonic-gate * return void * A new object of the size that was specified via
2207c478bd9Sstevel@tonic-gate * the node_size argument of _new_FreeList() when
2217c478bd9Sstevel@tonic-gate * the free-list was created, or NULL if there
2227c478bd9Sstevel@tonic-gate * is insufficient memory, or 'fl' is NULL.
2237c478bd9Sstevel@tonic-gate */
_new_FreeListNode(FreeList * fl)2247c478bd9Sstevel@tonic-gate void *_new_FreeListNode(FreeList *fl)
2257c478bd9Sstevel@tonic-gate {
2267c478bd9Sstevel@tonic-gate void *node; /* The node to be returned */
2277c478bd9Sstevel@tonic-gate /*
2287c478bd9Sstevel@tonic-gate * Check arguments.
2297c478bd9Sstevel@tonic-gate */
2307c478bd9Sstevel@tonic-gate if(!fl)
2317c478bd9Sstevel@tonic-gate return NULL;
2327c478bd9Sstevel@tonic-gate /*
2337c478bd9Sstevel@tonic-gate * If the free-list has been exhausted extend it by allocating
2347c478bd9Sstevel@tonic-gate * another block of nodes.
2357c478bd9Sstevel@tonic-gate */
2367c478bd9Sstevel@tonic-gate if(!fl->free_list) {
2377c478bd9Sstevel@tonic-gate FreeListBlock *block = _new_FreeListBlock(fl);
2387c478bd9Sstevel@tonic-gate if(!block)
2397c478bd9Sstevel@tonic-gate return NULL;
2407c478bd9Sstevel@tonic-gate /*
2417c478bd9Sstevel@tonic-gate * Prepend the new block to the list of free-list blocks.
2427c478bd9Sstevel@tonic-gate */
2437c478bd9Sstevel@tonic-gate block->next = fl->block;
2447c478bd9Sstevel@tonic-gate fl->block = block;
2457c478bd9Sstevel@tonic-gate /*
2467c478bd9Sstevel@tonic-gate * Add the new list of nodes to the free-list.
2477c478bd9Sstevel@tonic-gate */
2487c478bd9Sstevel@tonic-gate fl->free_list = fl->block->nodes;
2497c478bd9Sstevel@tonic-gate };
2507c478bd9Sstevel@tonic-gate /*
2517c478bd9Sstevel@tonic-gate * Remove and return a node from the front of the free list.
2527c478bd9Sstevel@tonic-gate */
2537c478bd9Sstevel@tonic-gate node = fl->free_list;
2547c478bd9Sstevel@tonic-gate fl->free_list = *(void **)node;
2557c478bd9Sstevel@tonic-gate /*
2567c478bd9Sstevel@tonic-gate * Record the loss of a node from the free-list.
2577c478bd9Sstevel@tonic-gate */
2587c478bd9Sstevel@tonic-gate fl->nbusy++;
2597c478bd9Sstevel@tonic-gate /*
2607c478bd9Sstevel@tonic-gate * Return the node.
2617c478bd9Sstevel@tonic-gate */
2627c478bd9Sstevel@tonic-gate return node;
2637c478bd9Sstevel@tonic-gate }
2647c478bd9Sstevel@tonic-gate
2657c478bd9Sstevel@tonic-gate /*.......................................................................
2667c478bd9Sstevel@tonic-gate * Return an object to the free-list that it was allocated from.
2677c478bd9Sstevel@tonic-gate *
2687c478bd9Sstevel@tonic-gate * Input:
2697c478bd9Sstevel@tonic-gate * fl FreeList * The free-list from which the object was taken.
2707c478bd9Sstevel@tonic-gate * object void * The node to be returned.
2717c478bd9Sstevel@tonic-gate * Output:
2727c478bd9Sstevel@tonic-gate * return void * Always NULL.
2737c478bd9Sstevel@tonic-gate */
_del_FreeListNode(FreeList * fl,void * object)2747c478bd9Sstevel@tonic-gate void *_del_FreeListNode(FreeList *fl, void *object)
2757c478bd9Sstevel@tonic-gate {
2767c478bd9Sstevel@tonic-gate /*
2777c478bd9Sstevel@tonic-gate * Check arguments.
2787c478bd9Sstevel@tonic-gate */
2797c478bd9Sstevel@tonic-gate if(!fl)
2807c478bd9Sstevel@tonic-gate return NULL;
2817c478bd9Sstevel@tonic-gate /*
2827c478bd9Sstevel@tonic-gate * Return the node to the head of the free list.
2837c478bd9Sstevel@tonic-gate */
2847c478bd9Sstevel@tonic-gate if(object) {
2857c478bd9Sstevel@tonic-gate *(void **)object = fl->free_list;
2867c478bd9Sstevel@tonic-gate fl->free_list = object;
2877c478bd9Sstevel@tonic-gate /*
2887c478bd9Sstevel@tonic-gate * Record the return of the node to the free-list.
2897c478bd9Sstevel@tonic-gate */
2907c478bd9Sstevel@tonic-gate fl->nbusy--;
2917c478bd9Sstevel@tonic-gate };
2927c478bd9Sstevel@tonic-gate return NULL;
2937c478bd9Sstevel@tonic-gate }
2947c478bd9Sstevel@tonic-gate
2957c478bd9Sstevel@tonic-gate /*.......................................................................
2967c478bd9Sstevel@tonic-gate * Return a count of the number of nodes that are currently allocated.
2977c478bd9Sstevel@tonic-gate *
2987c478bd9Sstevel@tonic-gate * Input:
2997c478bd9Sstevel@tonic-gate * fl FreeList * The list to count wrt, or NULL.
3007c478bd9Sstevel@tonic-gate * Output:
3017c478bd9Sstevel@tonic-gate * return long The number of nodes (or 0 if fl==NULL).
3027c478bd9Sstevel@tonic-gate */
_busy_FreeListNodes(FreeList * fl)3037c478bd9Sstevel@tonic-gate long _busy_FreeListNodes(FreeList *fl)
3047c478bd9Sstevel@tonic-gate {
3057c478bd9Sstevel@tonic-gate return fl ? fl->nbusy : 0;
3067c478bd9Sstevel@tonic-gate }
3077c478bd9Sstevel@tonic-gate
3087c478bd9Sstevel@tonic-gate /*.......................................................................
3097c478bd9Sstevel@tonic-gate * Query the number of allocated nodes in the freelist which are
3107c478bd9Sstevel@tonic-gate * currently unused.
3117c478bd9Sstevel@tonic-gate *
3127c478bd9Sstevel@tonic-gate * Input:
3137c478bd9Sstevel@tonic-gate * fl FreeList * The list to count wrt, or NULL.
3147c478bd9Sstevel@tonic-gate * Output:
3157c478bd9Sstevel@tonic-gate * return long The number of unused nodes (or 0 if fl==NULL).
3167c478bd9Sstevel@tonic-gate */
_idle_FreeListNodes(FreeList * fl)3177c478bd9Sstevel@tonic-gate long _idle_FreeListNodes(FreeList *fl)
3187c478bd9Sstevel@tonic-gate {
3197c478bd9Sstevel@tonic-gate return fl ? (fl->ntotal - fl->nbusy) : 0;
3207c478bd9Sstevel@tonic-gate }
3217c478bd9Sstevel@tonic-gate
3227c478bd9Sstevel@tonic-gate /*.......................................................................
3237c478bd9Sstevel@tonic-gate * Allocate a new list of free-list nodes. On return the nodes will
3247c478bd9Sstevel@tonic-gate * be linked together as a list starting with the node at the lowest
3257c478bd9Sstevel@tonic-gate * address and ending with a NULL next pointer.
3267c478bd9Sstevel@tonic-gate *
3277c478bd9Sstevel@tonic-gate * Input:
3287c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to allocate the list for.
3297c478bd9Sstevel@tonic-gate * Output:
3307c478bd9Sstevel@tonic-gate * return FreeListBlock * The new linked block of free-list nodes,
3317c478bd9Sstevel@tonic-gate * or NULL on error.
3327c478bd9Sstevel@tonic-gate */
_new_FreeListBlock(FreeList * fl)3337c478bd9Sstevel@tonic-gate static FreeListBlock *_new_FreeListBlock(FreeList *fl)
3347c478bd9Sstevel@tonic-gate {
3357c478bd9Sstevel@tonic-gate FreeListBlock *block; /* The new block to be returned */
3367c478bd9Sstevel@tonic-gate /*
3377c478bd9Sstevel@tonic-gate * Allocate the container.
3387c478bd9Sstevel@tonic-gate */
3397c478bd9Sstevel@tonic-gate block = (FreeListBlock *) malloc(sizeof(FreeListBlock));
3407c478bd9Sstevel@tonic-gate if(!block)
3417c478bd9Sstevel@tonic-gate return NULL;
3427c478bd9Sstevel@tonic-gate /*
3437c478bd9Sstevel@tonic-gate * Before attempting any operation that might fail, initialize the
3447c478bd9Sstevel@tonic-gate * container at least up to the point at which it can safely be passed
3457c478bd9Sstevel@tonic-gate * to _del_FreeListBlock().
3467c478bd9Sstevel@tonic-gate */
3477c478bd9Sstevel@tonic-gate block->next = NULL;
3487c478bd9Sstevel@tonic-gate block->nodes = NULL;
3497c478bd9Sstevel@tonic-gate /*
3507c478bd9Sstevel@tonic-gate * Allocate the block of nodes.
3517c478bd9Sstevel@tonic-gate */
3527c478bd9Sstevel@tonic-gate block->nodes = (char *) malloc(fl->node_size * fl->blocking_factor);
3537c478bd9Sstevel@tonic-gate if(!block->nodes)
3547c478bd9Sstevel@tonic-gate return _del_FreeListBlock(block);
3557c478bd9Sstevel@tonic-gate /*
3567c478bd9Sstevel@tonic-gate * Initialize the block as a linked list of FreeListNode's.
3577c478bd9Sstevel@tonic-gate */
3587c478bd9Sstevel@tonic-gate _thread_FreeListBlock(fl, block);
3597c478bd9Sstevel@tonic-gate /*
3607c478bd9Sstevel@tonic-gate * Update the record of the number of nodes in the freelist.
3617c478bd9Sstevel@tonic-gate */
3627c478bd9Sstevel@tonic-gate fl->ntotal += fl->blocking_factor;
3637c478bd9Sstevel@tonic-gate return block;
3647c478bd9Sstevel@tonic-gate }
3657c478bd9Sstevel@tonic-gate
3667c478bd9Sstevel@tonic-gate /*.......................................................................
3677c478bd9Sstevel@tonic-gate * Link each node of a freelist block to the node that follows it.
3687c478bd9Sstevel@tonic-gate *
3697c478bd9Sstevel@tonic-gate * Input:
3707c478bd9Sstevel@tonic-gate * fl FreeList * The freelist that contains the block.
3717c478bd9Sstevel@tonic-gate * block FreeListBlock * The block to be threaded.
3727c478bd9Sstevel@tonic-gate */
_thread_FreeListBlock(FreeList * fl,FreeListBlock * block)3737c478bd9Sstevel@tonic-gate static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block)
3747c478bd9Sstevel@tonic-gate {
3757c478bd9Sstevel@tonic-gate char *mem = block->nodes;
3767c478bd9Sstevel@tonic-gate int i;
3777c478bd9Sstevel@tonic-gate for(i=0; i<fl->blocking_factor - 1; i++, mem += fl->node_size)
3787c478bd9Sstevel@tonic-gate *(void **)mem = mem + fl->node_size; /* Link to the next node */
3797c478bd9Sstevel@tonic-gate *(void **)mem = NULL; /* Terminate the list */
3807c478bd9Sstevel@tonic-gate }
3817c478bd9Sstevel@tonic-gate
3827c478bd9Sstevel@tonic-gate /*.......................................................................
3837c478bd9Sstevel@tonic-gate * Delete a free-list block.
3847c478bd9Sstevel@tonic-gate *
3857c478bd9Sstevel@tonic-gate * Input:
3867c478bd9Sstevel@tonic-gate * fl FreeListBlock * The block to be deleted, or NULL.
3877c478bd9Sstevel@tonic-gate * Output:
3887c478bd9Sstevel@tonic-gate * return FreeListBlock * Always NULL.
3897c478bd9Sstevel@tonic-gate */
_del_FreeListBlock(FreeListBlock * fl)3907c478bd9Sstevel@tonic-gate static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl)
3917c478bd9Sstevel@tonic-gate {
3927c478bd9Sstevel@tonic-gate if(fl) {
3937c478bd9Sstevel@tonic-gate fl->next = NULL;
3947c478bd9Sstevel@tonic-gate if(fl->nodes)
3957c478bd9Sstevel@tonic-gate free(fl->nodes);
3967c478bd9Sstevel@tonic-gate fl->nodes = NULL;
3977c478bd9Sstevel@tonic-gate free(fl);
3987c478bd9Sstevel@tonic-gate };
3997c478bd9Sstevel@tonic-gate return NULL;
4007c478bd9Sstevel@tonic-gate }
401