1*7c478bd9Sstevel@tonic-gate /*
2*7c478bd9Sstevel@tonic-gate * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
3*7c478bd9Sstevel@tonic-gate *
4*7c478bd9Sstevel@tonic-gate * All rights reserved.
5*7c478bd9Sstevel@tonic-gate *
6*7c478bd9Sstevel@tonic-gate * Permission is hereby granted, free of charge, to any person obtaining a
7*7c478bd9Sstevel@tonic-gate * copy of this software and associated documentation files (the
8*7c478bd9Sstevel@tonic-gate * "Software"), to deal in the Software without restriction, including
9*7c478bd9Sstevel@tonic-gate * without limitation the rights to use, copy, modify, merge, publish,
10*7c478bd9Sstevel@tonic-gate * distribute, and/or sell copies of the Software, and to permit persons
11*7c478bd9Sstevel@tonic-gate * to whom the Software is furnished to do so, provided that the above
12*7c478bd9Sstevel@tonic-gate * copyright notice(s) and this permission notice appear in all copies of
13*7c478bd9Sstevel@tonic-gate * the Software and that both the above copyright notice(s) and this
14*7c478bd9Sstevel@tonic-gate * permission notice appear in supporting documentation.
15*7c478bd9Sstevel@tonic-gate *
16*7c478bd9Sstevel@tonic-gate * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17*7c478bd9Sstevel@tonic-gate * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18*7c478bd9Sstevel@tonic-gate * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
19*7c478bd9Sstevel@tonic-gate * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
20*7c478bd9Sstevel@tonic-gate * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
21*7c478bd9Sstevel@tonic-gate * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
22*7c478bd9Sstevel@tonic-gate * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
23*7c478bd9Sstevel@tonic-gate * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
24*7c478bd9Sstevel@tonic-gate * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
25*7c478bd9Sstevel@tonic-gate *
26*7c478bd9Sstevel@tonic-gate * Except as contained in this notice, the name of a copyright holder
27*7c478bd9Sstevel@tonic-gate * shall not be used in advertising or otherwise to promote the sale, use
28*7c478bd9Sstevel@tonic-gate * or other dealings in this Software without prior written authorization
29*7c478bd9Sstevel@tonic-gate * of the copyright holder.
30*7c478bd9Sstevel@tonic-gate */
31*7c478bd9Sstevel@tonic-gate
32*7c478bd9Sstevel@tonic-gate #include <stdio.h>
33*7c478bd9Sstevel@tonic-gate #include <stdlib.h>
34*7c478bd9Sstevel@tonic-gate #include <errno.h>
35*7c478bd9Sstevel@tonic-gate
36*7c478bd9Sstevel@tonic-gate #include "freelist.h"
37*7c478bd9Sstevel@tonic-gate
38*7c478bd9Sstevel@tonic-gate typedef struct FreeListBlock FreeListBlock;
39*7c478bd9Sstevel@tonic-gate struct FreeListBlock {
40*7c478bd9Sstevel@tonic-gate FreeListBlock *next; /* The next block in the list */
41*7c478bd9Sstevel@tonic-gate char *nodes; /* The array of free-list nodes */
42*7c478bd9Sstevel@tonic-gate };
43*7c478bd9Sstevel@tonic-gate
44*7c478bd9Sstevel@tonic-gate struct FreeList {
45*7c478bd9Sstevel@tonic-gate size_t node_size; /* The size of a free-list node */
46*7c478bd9Sstevel@tonic-gate unsigned blocking_factor; /* The number of nodes per block */
47*7c478bd9Sstevel@tonic-gate long nbusy; /* The number of nodes that are in use */
48*7c478bd9Sstevel@tonic-gate long ntotal; /* The total number of nodes in the free list */
49*7c478bd9Sstevel@tonic-gate FreeListBlock *block; /* The head of the list of free-list blocks */
50*7c478bd9Sstevel@tonic-gate void *free_list; /* The free-list of nodes */
51*7c478bd9Sstevel@tonic-gate };
52*7c478bd9Sstevel@tonic-gate
53*7c478bd9Sstevel@tonic-gate static FreeListBlock *_new_FreeListBlock(FreeList *fl);
54*7c478bd9Sstevel@tonic-gate static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl);
55*7c478bd9Sstevel@tonic-gate static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block);
56*7c478bd9Sstevel@tonic-gate
57*7c478bd9Sstevel@tonic-gate /*.......................................................................
58*7c478bd9Sstevel@tonic-gate * Allocate a new free-list from blocks of 'blocking_factor' objects of size
59*7c478bd9Sstevel@tonic-gate * node_size.
60*7c478bd9Sstevel@tonic-gate *
61*7c478bd9Sstevel@tonic-gate * Input:
62*7c478bd9Sstevel@tonic-gate * node_size size_t The size of the free-list nodes to be returned
63*7c478bd9Sstevel@tonic-gate * by _new_FreeListNode(). Use sizeof() to
64*7c478bd9Sstevel@tonic-gate * determine this.
65*7c478bd9Sstevel@tonic-gate * blocking_factor unsigned The number of objects of size 'object_size'
66*7c478bd9Sstevel@tonic-gate * to allocate per block.
67*7c478bd9Sstevel@tonic-gate * Output:
68*7c478bd9Sstevel@tonic-gate * return FreeList * The new freelist, or NULL on error.
69*7c478bd9Sstevel@tonic-gate */
_new_FreeList(size_t node_size,unsigned blocking_factor)70*7c478bd9Sstevel@tonic-gate FreeList *_new_FreeList(size_t node_size, unsigned blocking_factor)
71*7c478bd9Sstevel@tonic-gate {
72*7c478bd9Sstevel@tonic-gate FreeList *fl; /* The new free-list container */
73*7c478bd9Sstevel@tonic-gate /*
74*7c478bd9Sstevel@tonic-gate * When a free-list node is on the free-list, it is used as a (void *)
75*7c478bd9Sstevel@tonic-gate * link field. Roundup node_size to a mulitple of the size of a void
76*7c478bd9Sstevel@tonic-gate * pointer. This, plus the fact that the array of nodes is obtained via
77*7c478bd9Sstevel@tonic-gate * malloc, which returns memory suitably aligned for any object, will
78*7c478bd9Sstevel@tonic-gate * ensure that the first sizeof(void *) bytes of each node will be
79*7c478bd9Sstevel@tonic-gate * suitably aligned to use as a (void *) link pointer.
80*7c478bd9Sstevel@tonic-gate */
81*7c478bd9Sstevel@tonic-gate node_size = sizeof(void *) *
82*7c478bd9Sstevel@tonic-gate ((node_size + sizeof(void *) - 1) / sizeof(void *));
83*7c478bd9Sstevel@tonic-gate /*
84*7c478bd9Sstevel@tonic-gate * Enfore a minimum block size.
85*7c478bd9Sstevel@tonic-gate */
86*7c478bd9Sstevel@tonic-gate if(blocking_factor < 1)
87*7c478bd9Sstevel@tonic-gate blocking_factor = 1;
88*7c478bd9Sstevel@tonic-gate /*
89*7c478bd9Sstevel@tonic-gate * Allocate the container of the free list.
90*7c478bd9Sstevel@tonic-gate */
91*7c478bd9Sstevel@tonic-gate fl = (FreeList *) malloc(sizeof(FreeList));
92*7c478bd9Sstevel@tonic-gate if(!fl) {
93*7c478bd9Sstevel@tonic-gate errno = ENOMEM;
94*7c478bd9Sstevel@tonic-gate return NULL;
95*7c478bd9Sstevel@tonic-gate };
96*7c478bd9Sstevel@tonic-gate /*
97*7c478bd9Sstevel@tonic-gate * Before attempting any operation that might fail, initialize the
98*7c478bd9Sstevel@tonic-gate * container at least up to the point at which it can safely be passed
99*7c478bd9Sstevel@tonic-gate * to _del_FreeList().
100*7c478bd9Sstevel@tonic-gate */
101*7c478bd9Sstevel@tonic-gate fl->node_size = node_size;
102*7c478bd9Sstevel@tonic-gate fl->blocking_factor = blocking_factor;
103*7c478bd9Sstevel@tonic-gate fl->nbusy = 0;
104*7c478bd9Sstevel@tonic-gate fl->ntotal = 0;
105*7c478bd9Sstevel@tonic-gate fl->block = NULL;
106*7c478bd9Sstevel@tonic-gate fl->free_list = NULL;
107*7c478bd9Sstevel@tonic-gate /*
108*7c478bd9Sstevel@tonic-gate * Allocate the first block of memory.
109*7c478bd9Sstevel@tonic-gate */
110*7c478bd9Sstevel@tonic-gate fl->block = _new_FreeListBlock(fl);
111*7c478bd9Sstevel@tonic-gate if(!fl->block) {
112*7c478bd9Sstevel@tonic-gate errno = ENOMEM;
113*7c478bd9Sstevel@tonic-gate return _del_FreeList(fl, 1);
114*7c478bd9Sstevel@tonic-gate };
115*7c478bd9Sstevel@tonic-gate /*
116*7c478bd9Sstevel@tonic-gate * Add the new list of nodes to the free-list.
117*7c478bd9Sstevel@tonic-gate */
118*7c478bd9Sstevel@tonic-gate fl->free_list = fl->block->nodes;
119*7c478bd9Sstevel@tonic-gate /*
120*7c478bd9Sstevel@tonic-gate * Return the free-list for use.
121*7c478bd9Sstevel@tonic-gate */
122*7c478bd9Sstevel@tonic-gate return fl;
123*7c478bd9Sstevel@tonic-gate }
124*7c478bd9Sstevel@tonic-gate
125*7c478bd9Sstevel@tonic-gate /*.......................................................................
126*7c478bd9Sstevel@tonic-gate * Re-thread a freelist to reclaim all allocated nodes.
127*7c478bd9Sstevel@tonic-gate * This function should not be called unless if it is known that none
128*7c478bd9Sstevel@tonic-gate * of the currently allocated nodes are still being used.
129*7c478bd9Sstevel@tonic-gate *
130*7c478bd9Sstevel@tonic-gate * Input:
131*7c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to be reset, or NULL.
132*7c478bd9Sstevel@tonic-gate */
_rst_FreeList(FreeList * fl)133*7c478bd9Sstevel@tonic-gate void _rst_FreeList(FreeList *fl)
134*7c478bd9Sstevel@tonic-gate {
135*7c478bd9Sstevel@tonic-gate if(fl) {
136*7c478bd9Sstevel@tonic-gate FreeListBlock *block;
137*7c478bd9Sstevel@tonic-gate /*
138*7c478bd9Sstevel@tonic-gate * Re-thread the nodes of each block into individual free-lists.
139*7c478bd9Sstevel@tonic-gate */
140*7c478bd9Sstevel@tonic-gate for(block=fl->block; block; block=block->next)
141*7c478bd9Sstevel@tonic-gate _thread_FreeListBlock(fl, block);
142*7c478bd9Sstevel@tonic-gate /*
143*7c478bd9Sstevel@tonic-gate * Link all of the block freelists into one large freelist.
144*7c478bd9Sstevel@tonic-gate */
145*7c478bd9Sstevel@tonic-gate fl->free_list = NULL;
146*7c478bd9Sstevel@tonic-gate for(block=fl->block; block; block=block->next) {
147*7c478bd9Sstevel@tonic-gate /*
148*7c478bd9Sstevel@tonic-gate * Locate the last node of the current block.
149*7c478bd9Sstevel@tonic-gate */
150*7c478bd9Sstevel@tonic-gate char *last_node = block->nodes + fl->node_size *
151*7c478bd9Sstevel@tonic-gate (fl->blocking_factor - 1);
152*7c478bd9Sstevel@tonic-gate /*
153*7c478bd9Sstevel@tonic-gate * Make the link-field of the last node point to the first
154*7c478bd9Sstevel@tonic-gate * node of the current freelist, then make the first node of the
155*7c478bd9Sstevel@tonic-gate * new block the start of the freelist.
156*7c478bd9Sstevel@tonic-gate */
157*7c478bd9Sstevel@tonic-gate *(void **)last_node = fl->free_list;
158*7c478bd9Sstevel@tonic-gate fl->free_list = block->nodes;
159*7c478bd9Sstevel@tonic-gate };
160*7c478bd9Sstevel@tonic-gate /*
161*7c478bd9Sstevel@tonic-gate * All allocated nodes have now been returned to the freelist.
162*7c478bd9Sstevel@tonic-gate */
163*7c478bd9Sstevel@tonic-gate fl->nbusy = 0;
164*7c478bd9Sstevel@tonic-gate };
165*7c478bd9Sstevel@tonic-gate }
166*7c478bd9Sstevel@tonic-gate
167*7c478bd9Sstevel@tonic-gate /*.......................................................................
168*7c478bd9Sstevel@tonic-gate * Delete a free-list.
169*7c478bd9Sstevel@tonic-gate *
170*7c478bd9Sstevel@tonic-gate * Input:
171*7c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to be deleted, or NULL.
172*7c478bd9Sstevel@tonic-gate * force int If force==0 then _del_FreeList() will complain
173*7c478bd9Sstevel@tonic-gate * and refuse to delete the free-list if any
174*7c478bd9Sstevel@tonic-gate * of nodes have not been returned to the free-list.
175*7c478bd9Sstevel@tonic-gate * If force!=0 then _del_FreeList() will not check
176*7c478bd9Sstevel@tonic-gate * whether any nodes are still in use and will
177*7c478bd9Sstevel@tonic-gate * always delete the list.
178*7c478bd9Sstevel@tonic-gate * Output:
179*7c478bd9Sstevel@tonic-gate * return FreeList * Always NULL (even if the list couldn't be
180*7c478bd9Sstevel@tonic-gate * deleted).
181*7c478bd9Sstevel@tonic-gate */
_del_FreeList(FreeList * fl,int force)182*7c478bd9Sstevel@tonic-gate FreeList *_del_FreeList(FreeList *fl, int force)
183*7c478bd9Sstevel@tonic-gate {
184*7c478bd9Sstevel@tonic-gate if(fl) {
185*7c478bd9Sstevel@tonic-gate /*
186*7c478bd9Sstevel@tonic-gate * Check whether any nodes are in use.
187*7c478bd9Sstevel@tonic-gate */
188*7c478bd9Sstevel@tonic-gate if(!force && _busy_FreeListNodes(fl) != 0) {
189*7c478bd9Sstevel@tonic-gate errno = EBUSY;
190*7c478bd9Sstevel@tonic-gate return NULL;
191*7c478bd9Sstevel@tonic-gate };
192*7c478bd9Sstevel@tonic-gate /*
193*7c478bd9Sstevel@tonic-gate * Delete the list blocks.
194*7c478bd9Sstevel@tonic-gate */
195*7c478bd9Sstevel@tonic-gate {
196*7c478bd9Sstevel@tonic-gate FreeListBlock *next = fl->block;
197*7c478bd9Sstevel@tonic-gate while(next) {
198*7c478bd9Sstevel@tonic-gate FreeListBlock *block = next;
199*7c478bd9Sstevel@tonic-gate next = block->next;
200*7c478bd9Sstevel@tonic-gate block = _del_FreeListBlock(block);
201*7c478bd9Sstevel@tonic-gate };
202*7c478bd9Sstevel@tonic-gate };
203*7c478bd9Sstevel@tonic-gate fl->block = NULL;
204*7c478bd9Sstevel@tonic-gate fl->free_list = NULL;
205*7c478bd9Sstevel@tonic-gate /*
206*7c478bd9Sstevel@tonic-gate * Discard the container.
207*7c478bd9Sstevel@tonic-gate */
208*7c478bd9Sstevel@tonic-gate free(fl);
209*7c478bd9Sstevel@tonic-gate };
210*7c478bd9Sstevel@tonic-gate return NULL;
211*7c478bd9Sstevel@tonic-gate }
212*7c478bd9Sstevel@tonic-gate
213*7c478bd9Sstevel@tonic-gate /*.......................................................................
214*7c478bd9Sstevel@tonic-gate * Allocate a new object from a free-list.
215*7c478bd9Sstevel@tonic-gate *
216*7c478bd9Sstevel@tonic-gate * Input:
217*7c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to return an object from.
218*7c478bd9Sstevel@tonic-gate * Output:
219*7c478bd9Sstevel@tonic-gate * return void * A new object of the size that was specified via
220*7c478bd9Sstevel@tonic-gate * the node_size argument of _new_FreeList() when
221*7c478bd9Sstevel@tonic-gate * the free-list was created, or NULL if there
222*7c478bd9Sstevel@tonic-gate * is insufficient memory, or 'fl' is NULL.
223*7c478bd9Sstevel@tonic-gate */
_new_FreeListNode(FreeList * fl)224*7c478bd9Sstevel@tonic-gate void *_new_FreeListNode(FreeList *fl)
225*7c478bd9Sstevel@tonic-gate {
226*7c478bd9Sstevel@tonic-gate void *node; /* The node to be returned */
227*7c478bd9Sstevel@tonic-gate /*
228*7c478bd9Sstevel@tonic-gate * Check arguments.
229*7c478bd9Sstevel@tonic-gate */
230*7c478bd9Sstevel@tonic-gate if(!fl)
231*7c478bd9Sstevel@tonic-gate return NULL;
232*7c478bd9Sstevel@tonic-gate /*
233*7c478bd9Sstevel@tonic-gate * If the free-list has been exhausted extend it by allocating
234*7c478bd9Sstevel@tonic-gate * another block of nodes.
235*7c478bd9Sstevel@tonic-gate */
236*7c478bd9Sstevel@tonic-gate if(!fl->free_list) {
237*7c478bd9Sstevel@tonic-gate FreeListBlock *block = _new_FreeListBlock(fl);
238*7c478bd9Sstevel@tonic-gate if(!block)
239*7c478bd9Sstevel@tonic-gate return NULL;
240*7c478bd9Sstevel@tonic-gate /*
241*7c478bd9Sstevel@tonic-gate * Prepend the new block to the list of free-list blocks.
242*7c478bd9Sstevel@tonic-gate */
243*7c478bd9Sstevel@tonic-gate block->next = fl->block;
244*7c478bd9Sstevel@tonic-gate fl->block = block;
245*7c478bd9Sstevel@tonic-gate /*
246*7c478bd9Sstevel@tonic-gate * Add the new list of nodes to the free-list.
247*7c478bd9Sstevel@tonic-gate */
248*7c478bd9Sstevel@tonic-gate fl->free_list = fl->block->nodes;
249*7c478bd9Sstevel@tonic-gate };
250*7c478bd9Sstevel@tonic-gate /*
251*7c478bd9Sstevel@tonic-gate * Remove and return a node from the front of the free list.
252*7c478bd9Sstevel@tonic-gate */
253*7c478bd9Sstevel@tonic-gate node = fl->free_list;
254*7c478bd9Sstevel@tonic-gate fl->free_list = *(void **)node;
255*7c478bd9Sstevel@tonic-gate /*
256*7c478bd9Sstevel@tonic-gate * Record the loss of a node from the free-list.
257*7c478bd9Sstevel@tonic-gate */
258*7c478bd9Sstevel@tonic-gate fl->nbusy++;
259*7c478bd9Sstevel@tonic-gate /*
260*7c478bd9Sstevel@tonic-gate * Return the node.
261*7c478bd9Sstevel@tonic-gate */
262*7c478bd9Sstevel@tonic-gate return node;
263*7c478bd9Sstevel@tonic-gate }
264*7c478bd9Sstevel@tonic-gate
265*7c478bd9Sstevel@tonic-gate /*.......................................................................
266*7c478bd9Sstevel@tonic-gate * Return an object to the free-list that it was allocated from.
267*7c478bd9Sstevel@tonic-gate *
268*7c478bd9Sstevel@tonic-gate * Input:
269*7c478bd9Sstevel@tonic-gate * fl FreeList * The free-list from which the object was taken.
270*7c478bd9Sstevel@tonic-gate * object void * The node to be returned.
271*7c478bd9Sstevel@tonic-gate * Output:
272*7c478bd9Sstevel@tonic-gate * return void * Always NULL.
273*7c478bd9Sstevel@tonic-gate */
_del_FreeListNode(FreeList * fl,void * object)274*7c478bd9Sstevel@tonic-gate void *_del_FreeListNode(FreeList *fl, void *object)
275*7c478bd9Sstevel@tonic-gate {
276*7c478bd9Sstevel@tonic-gate /*
277*7c478bd9Sstevel@tonic-gate * Check arguments.
278*7c478bd9Sstevel@tonic-gate */
279*7c478bd9Sstevel@tonic-gate if(!fl)
280*7c478bd9Sstevel@tonic-gate return NULL;
281*7c478bd9Sstevel@tonic-gate /*
282*7c478bd9Sstevel@tonic-gate * Return the node to the head of the free list.
283*7c478bd9Sstevel@tonic-gate */
284*7c478bd9Sstevel@tonic-gate if(object) {
285*7c478bd9Sstevel@tonic-gate *(void **)object = fl->free_list;
286*7c478bd9Sstevel@tonic-gate fl->free_list = object;
287*7c478bd9Sstevel@tonic-gate /*
288*7c478bd9Sstevel@tonic-gate * Record the return of the node to the free-list.
289*7c478bd9Sstevel@tonic-gate */
290*7c478bd9Sstevel@tonic-gate fl->nbusy--;
291*7c478bd9Sstevel@tonic-gate };
292*7c478bd9Sstevel@tonic-gate return NULL;
293*7c478bd9Sstevel@tonic-gate }
294*7c478bd9Sstevel@tonic-gate
295*7c478bd9Sstevel@tonic-gate /*.......................................................................
296*7c478bd9Sstevel@tonic-gate * Return a count of the number of nodes that are currently allocated.
297*7c478bd9Sstevel@tonic-gate *
298*7c478bd9Sstevel@tonic-gate * Input:
299*7c478bd9Sstevel@tonic-gate * fl FreeList * The list to count wrt, or NULL.
300*7c478bd9Sstevel@tonic-gate * Output:
301*7c478bd9Sstevel@tonic-gate * return long The number of nodes (or 0 if fl==NULL).
302*7c478bd9Sstevel@tonic-gate */
_busy_FreeListNodes(FreeList * fl)303*7c478bd9Sstevel@tonic-gate long _busy_FreeListNodes(FreeList *fl)
304*7c478bd9Sstevel@tonic-gate {
305*7c478bd9Sstevel@tonic-gate return fl ? fl->nbusy : 0;
306*7c478bd9Sstevel@tonic-gate }
307*7c478bd9Sstevel@tonic-gate
308*7c478bd9Sstevel@tonic-gate /*.......................................................................
309*7c478bd9Sstevel@tonic-gate * Query the number of allocated nodes in the freelist which are
310*7c478bd9Sstevel@tonic-gate * currently unused.
311*7c478bd9Sstevel@tonic-gate *
312*7c478bd9Sstevel@tonic-gate * Input:
313*7c478bd9Sstevel@tonic-gate * fl FreeList * The list to count wrt, or NULL.
314*7c478bd9Sstevel@tonic-gate * Output:
315*7c478bd9Sstevel@tonic-gate * return long The number of unused nodes (or 0 if fl==NULL).
316*7c478bd9Sstevel@tonic-gate */
_idle_FreeListNodes(FreeList * fl)317*7c478bd9Sstevel@tonic-gate long _idle_FreeListNodes(FreeList *fl)
318*7c478bd9Sstevel@tonic-gate {
319*7c478bd9Sstevel@tonic-gate return fl ? (fl->ntotal - fl->nbusy) : 0;
320*7c478bd9Sstevel@tonic-gate }
321*7c478bd9Sstevel@tonic-gate
322*7c478bd9Sstevel@tonic-gate /*.......................................................................
323*7c478bd9Sstevel@tonic-gate * Allocate a new list of free-list nodes. On return the nodes will
324*7c478bd9Sstevel@tonic-gate * be linked together as a list starting with the node at the lowest
325*7c478bd9Sstevel@tonic-gate * address and ending with a NULL next pointer.
326*7c478bd9Sstevel@tonic-gate *
327*7c478bd9Sstevel@tonic-gate * Input:
328*7c478bd9Sstevel@tonic-gate * fl FreeList * The free-list to allocate the list for.
329*7c478bd9Sstevel@tonic-gate * Output:
330*7c478bd9Sstevel@tonic-gate * return FreeListBlock * The new linked block of free-list nodes,
331*7c478bd9Sstevel@tonic-gate * or NULL on error.
332*7c478bd9Sstevel@tonic-gate */
_new_FreeListBlock(FreeList * fl)333*7c478bd9Sstevel@tonic-gate static FreeListBlock *_new_FreeListBlock(FreeList *fl)
334*7c478bd9Sstevel@tonic-gate {
335*7c478bd9Sstevel@tonic-gate FreeListBlock *block; /* The new block to be returned */
336*7c478bd9Sstevel@tonic-gate /*
337*7c478bd9Sstevel@tonic-gate * Allocate the container.
338*7c478bd9Sstevel@tonic-gate */
339*7c478bd9Sstevel@tonic-gate block = (FreeListBlock *) malloc(sizeof(FreeListBlock));
340*7c478bd9Sstevel@tonic-gate if(!block)
341*7c478bd9Sstevel@tonic-gate return NULL;
342*7c478bd9Sstevel@tonic-gate /*
343*7c478bd9Sstevel@tonic-gate * Before attempting any operation that might fail, initialize the
344*7c478bd9Sstevel@tonic-gate * container at least up to the point at which it can safely be passed
345*7c478bd9Sstevel@tonic-gate * to _del_FreeListBlock().
346*7c478bd9Sstevel@tonic-gate */
347*7c478bd9Sstevel@tonic-gate block->next = NULL;
348*7c478bd9Sstevel@tonic-gate block->nodes = NULL;
349*7c478bd9Sstevel@tonic-gate /*
350*7c478bd9Sstevel@tonic-gate * Allocate the block of nodes.
351*7c478bd9Sstevel@tonic-gate */
352*7c478bd9Sstevel@tonic-gate block->nodes = (char *) malloc(fl->node_size * fl->blocking_factor);
353*7c478bd9Sstevel@tonic-gate if(!block->nodes)
354*7c478bd9Sstevel@tonic-gate return _del_FreeListBlock(block);
355*7c478bd9Sstevel@tonic-gate /*
356*7c478bd9Sstevel@tonic-gate * Initialize the block as a linked list of FreeListNode's.
357*7c478bd9Sstevel@tonic-gate */
358*7c478bd9Sstevel@tonic-gate _thread_FreeListBlock(fl, block);
359*7c478bd9Sstevel@tonic-gate /*
360*7c478bd9Sstevel@tonic-gate * Update the record of the number of nodes in the freelist.
361*7c478bd9Sstevel@tonic-gate */
362*7c478bd9Sstevel@tonic-gate fl->ntotal += fl->blocking_factor;
363*7c478bd9Sstevel@tonic-gate return block;
364*7c478bd9Sstevel@tonic-gate }
365*7c478bd9Sstevel@tonic-gate
366*7c478bd9Sstevel@tonic-gate /*.......................................................................
367*7c478bd9Sstevel@tonic-gate * Link each node of a freelist block to the node that follows it.
368*7c478bd9Sstevel@tonic-gate *
369*7c478bd9Sstevel@tonic-gate * Input:
370*7c478bd9Sstevel@tonic-gate * fl FreeList * The freelist that contains the block.
371*7c478bd9Sstevel@tonic-gate * block FreeListBlock * The block to be threaded.
372*7c478bd9Sstevel@tonic-gate */
_thread_FreeListBlock(FreeList * fl,FreeListBlock * block)373*7c478bd9Sstevel@tonic-gate static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block)
374*7c478bd9Sstevel@tonic-gate {
375*7c478bd9Sstevel@tonic-gate char *mem = block->nodes;
376*7c478bd9Sstevel@tonic-gate int i;
377*7c478bd9Sstevel@tonic-gate for(i=0; i<fl->blocking_factor - 1; i++, mem += fl->node_size)
378*7c478bd9Sstevel@tonic-gate *(void **)mem = mem + fl->node_size; /* Link to the next node */
379*7c478bd9Sstevel@tonic-gate *(void **)mem = NULL; /* Terminate the list */
380*7c478bd9Sstevel@tonic-gate }
381*7c478bd9Sstevel@tonic-gate
382*7c478bd9Sstevel@tonic-gate /*.......................................................................
383*7c478bd9Sstevel@tonic-gate * Delete a free-list block.
384*7c478bd9Sstevel@tonic-gate *
385*7c478bd9Sstevel@tonic-gate * Input:
386*7c478bd9Sstevel@tonic-gate * fl FreeListBlock * The block to be deleted, or NULL.
387*7c478bd9Sstevel@tonic-gate * Output:
388*7c478bd9Sstevel@tonic-gate * return FreeListBlock * Always NULL.
389*7c478bd9Sstevel@tonic-gate */
_del_FreeListBlock(FreeListBlock * fl)390*7c478bd9Sstevel@tonic-gate static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl)
391*7c478bd9Sstevel@tonic-gate {
392*7c478bd9Sstevel@tonic-gate if(fl) {
393*7c478bd9Sstevel@tonic-gate fl->next = NULL;
394*7c478bd9Sstevel@tonic-gate if(fl->nodes)
395*7c478bd9Sstevel@tonic-gate free(fl->nodes);
396*7c478bd9Sstevel@tonic-gate fl->nodes = NULL;
397*7c478bd9Sstevel@tonic-gate free(fl);
398*7c478bd9Sstevel@tonic-gate };
399*7c478bd9Sstevel@tonic-gate return NULL;
400*7c478bd9Sstevel@tonic-gate }
401