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