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 #include <stdio.h>
33 #include <stdlib.h>
34 #include <errno.h>
35
36 #include "freelist.h"
37
38 typedef struct FreeListBlock FreeListBlock;
39 struct FreeListBlock {
40 FreeListBlock *next; /* The next block in the list */
41 char *nodes; /* The array of free-list nodes */
42 };
43
44 struct FreeList {
45 size_t node_size; /* The size of a free-list node */
46 unsigned blocking_factor; /* The number of nodes per block */
47 long nbusy; /* The number of nodes that are in use */
48 long ntotal; /* The total number of nodes in the free list */
49 FreeListBlock *block; /* The head of the list of free-list blocks */
50 void *free_list; /* The free-list of nodes */
51 };
52
53 static FreeListBlock *_new_FreeListBlock(FreeList *fl);
54 static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl);
55 static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block);
56
57 /*.......................................................................
58 * Allocate a new free-list from blocks of 'blocking_factor' objects of size
59 * node_size.
60 *
61 * Input:
62 * node_size size_t The size of the free-list nodes to be returned
63 * by _new_FreeListNode(). Use sizeof() to
64 * determine this.
65 * blocking_factor unsigned The number of objects of size 'object_size'
66 * to allocate per block.
67 * Output:
68 * return FreeList * The new freelist, or NULL on error.
69 */
_new_FreeList(size_t node_size,unsigned blocking_factor)70 FreeList *_new_FreeList(size_t node_size, unsigned blocking_factor)
71 {
72 FreeList *fl; /* The new free-list container */
73 /*
74 * When a free-list node is on the free-list, it is used as a (void *)
75 * link field. Roundup node_size to a mulitple of the size of a void
76 * pointer. This, plus the fact that the array of nodes is obtained via
77 * malloc, which returns memory suitably aligned for any object, will
78 * ensure that the first sizeof(void *) bytes of each node will be
79 * suitably aligned to use as a (void *) link pointer.
80 */
81 node_size = sizeof(void *) *
82 ((node_size + sizeof(void *) - 1) / sizeof(void *));
83 /*
84 * Enfore a minimum block size.
85 */
86 if(blocking_factor < 1)
87 blocking_factor = 1;
88 /*
89 * Allocate the container of the free list.
90 */
91 fl = (FreeList *) malloc(sizeof(FreeList));
92 if(!fl) {
93 errno = ENOMEM;
94 return NULL;
95 };
96 /*
97 * Before attempting any operation that might fail, initialize the
98 * container at least up to the point at which it can safely be passed
99 * to _del_FreeList().
100 */
101 fl->node_size = node_size;
102 fl->blocking_factor = blocking_factor;
103 fl->nbusy = 0;
104 fl->ntotal = 0;
105 fl->block = NULL;
106 fl->free_list = NULL;
107 /*
108 * Allocate the first block of memory.
109 */
110 fl->block = _new_FreeListBlock(fl);
111 if(!fl->block) {
112 errno = ENOMEM;
113 return _del_FreeList(fl, 1);
114 };
115 /*
116 * Add the new list of nodes to the free-list.
117 */
118 fl->free_list = fl->block->nodes;
119 /*
120 * Return the free-list for use.
121 */
122 return fl;
123 }
124
125 /*.......................................................................
126 * Re-thread a freelist to reclaim all allocated nodes.
127 * This function should not be called unless if it is known that none
128 * of the currently allocated nodes are still being used.
129 *
130 * Input:
131 * fl FreeList * The free-list to be reset, or NULL.
132 */
_rst_FreeList(FreeList * fl)133 void _rst_FreeList(FreeList *fl)
134 {
135 if(fl) {
136 FreeListBlock *block;
137 /*
138 * Re-thread the nodes of each block into individual free-lists.
139 */
140 for(block=fl->block; block; block=block->next)
141 _thread_FreeListBlock(fl, block);
142 /*
143 * Link all of the block freelists into one large freelist.
144 */
145 fl->free_list = NULL;
146 for(block=fl->block; block; block=block->next) {
147 /*
148 * Locate the last node of the current block.
149 */
150 char *last_node = block->nodes + fl->node_size *
151 (fl->blocking_factor - 1);
152 /*
153 * Make the link-field of the last node point to the first
154 * node of the current freelist, then make the first node of the
155 * new block the start of the freelist.
156 */
157 *(void **)last_node = fl->free_list;
158 fl->free_list = block->nodes;
159 };
160 /*
161 * All allocated nodes have now been returned to the freelist.
162 */
163 fl->nbusy = 0;
164 };
165 }
166
167 /*.......................................................................
168 * Delete a free-list.
169 *
170 * Input:
171 * fl FreeList * The free-list to be deleted, or NULL.
172 * force int If force==0 then _del_FreeList() will complain
173 * and refuse to delete the free-list if any
174 * of nodes have not been returned to the free-list.
175 * If force!=0 then _del_FreeList() will not check
176 * whether any nodes are still in use and will
177 * always delete the list.
178 * Output:
179 * return FreeList * Always NULL (even if the list couldn't be
180 * deleted).
181 */
_del_FreeList(FreeList * fl,int force)182 FreeList *_del_FreeList(FreeList *fl, int force)
183 {
184 if(fl) {
185 /*
186 * Check whether any nodes are in use.
187 */
188 if(!force && _busy_FreeListNodes(fl) != 0) {
189 errno = EBUSY;
190 return NULL;
191 };
192 /*
193 * Delete the list blocks.
194 */
195 {
196 FreeListBlock *next = fl->block;
197 while(next) {
198 FreeListBlock *block = next;
199 next = block->next;
200 block = _del_FreeListBlock(block);
201 };
202 };
203 fl->block = NULL;
204 fl->free_list = NULL;
205 /*
206 * Discard the container.
207 */
208 free(fl);
209 };
210 return NULL;
211 }
212
213 /*.......................................................................
214 * Allocate a new object from a free-list.
215 *
216 * Input:
217 * fl FreeList * The free-list to return an object from.
218 * Output:
219 * return void * A new object of the size that was specified via
220 * the node_size argument of _new_FreeList() when
221 * the free-list was created, or NULL if there
222 * is insufficient memory, or 'fl' is NULL.
223 */
_new_FreeListNode(FreeList * fl)224 void *_new_FreeListNode(FreeList *fl)
225 {
226 void *node; /* The node to be returned */
227 /*
228 * Check arguments.
229 */
230 if(!fl)
231 return NULL;
232 /*
233 * If the free-list has been exhausted extend it by allocating
234 * another block of nodes.
235 */
236 if(!fl->free_list) {
237 FreeListBlock *block = _new_FreeListBlock(fl);
238 if(!block)
239 return NULL;
240 /*
241 * Prepend the new block to the list of free-list blocks.
242 */
243 block->next = fl->block;
244 fl->block = block;
245 /*
246 * Add the new list of nodes to the free-list.
247 */
248 fl->free_list = fl->block->nodes;
249 };
250 /*
251 * Remove and return a node from the front of the free list.
252 */
253 node = fl->free_list;
254 fl->free_list = *(void **)node;
255 /*
256 * Record the loss of a node from the free-list.
257 */
258 fl->nbusy++;
259 /*
260 * Return the node.
261 */
262 return node;
263 }
264
265 /*.......................................................................
266 * Return an object to the free-list that it was allocated from.
267 *
268 * Input:
269 * fl FreeList * The free-list from which the object was taken.
270 * object void * The node to be returned.
271 * Output:
272 * return void * Always NULL.
273 */
_del_FreeListNode(FreeList * fl,void * object)274 void *_del_FreeListNode(FreeList *fl, void *object)
275 {
276 /*
277 * Check arguments.
278 */
279 if(!fl)
280 return NULL;
281 /*
282 * Return the node to the head of the free list.
283 */
284 if(object) {
285 *(void **)object = fl->free_list;
286 fl->free_list = object;
287 /*
288 * Record the return of the node to the free-list.
289 */
290 fl->nbusy--;
291 };
292 return NULL;
293 }
294
295 /*.......................................................................
296 * Return a count of the number of nodes that are currently allocated.
297 *
298 * Input:
299 * fl FreeList * The list to count wrt, or NULL.
300 * Output:
301 * return long The number of nodes (or 0 if fl==NULL).
302 */
_busy_FreeListNodes(FreeList * fl)303 long _busy_FreeListNodes(FreeList *fl)
304 {
305 return fl ? fl->nbusy : 0;
306 }
307
308 /*.......................................................................
309 * Query the number of allocated nodes in the freelist which are
310 * currently unused.
311 *
312 * Input:
313 * fl FreeList * The list to count wrt, or NULL.
314 * Output:
315 * return long The number of unused nodes (or 0 if fl==NULL).
316 */
_idle_FreeListNodes(FreeList * fl)317 long _idle_FreeListNodes(FreeList *fl)
318 {
319 return fl ? (fl->ntotal - fl->nbusy) : 0;
320 }
321
322 /*.......................................................................
323 * Allocate a new list of free-list nodes. On return the nodes will
324 * be linked together as a list starting with the node at the lowest
325 * address and ending with a NULL next pointer.
326 *
327 * Input:
328 * fl FreeList * The free-list to allocate the list for.
329 * Output:
330 * return FreeListBlock * The new linked block of free-list nodes,
331 * or NULL on error.
332 */
_new_FreeListBlock(FreeList * fl)333 static FreeListBlock *_new_FreeListBlock(FreeList *fl)
334 {
335 FreeListBlock *block; /* The new block to be returned */
336 /*
337 * Allocate the container.
338 */
339 block = (FreeListBlock *) malloc(sizeof(FreeListBlock));
340 if(!block)
341 return NULL;
342 /*
343 * Before attempting any operation that might fail, initialize the
344 * container at least up to the point at which it can safely be passed
345 * to _del_FreeListBlock().
346 */
347 block->next = NULL;
348 block->nodes = NULL;
349 /*
350 * Allocate the block of nodes.
351 */
352 block->nodes = (char *) malloc(fl->node_size * fl->blocking_factor);
353 if(!block->nodes)
354 return _del_FreeListBlock(block);
355 /*
356 * Initialize the block as a linked list of FreeListNode's.
357 */
358 _thread_FreeListBlock(fl, block);
359 /*
360 * Update the record of the number of nodes in the freelist.
361 */
362 fl->ntotal += fl->blocking_factor;
363 return block;
364 }
365
366 /*.......................................................................
367 * Link each node of a freelist block to the node that follows it.
368 *
369 * Input:
370 * fl FreeList * The freelist that contains the block.
371 * block FreeListBlock * The block to be threaded.
372 */
_thread_FreeListBlock(FreeList * fl,FreeListBlock * block)373 static void _thread_FreeListBlock(FreeList *fl, FreeListBlock *block)
374 {
375 char *mem = block->nodes;
376 int i;
377 for(i=0; i<fl->blocking_factor - 1; i++, mem += fl->node_size)
378 *(void **)mem = mem + fl->node_size; /* Link to the next node */
379 *(void **)mem = NULL; /* Terminate the list */
380 }
381
382 /*.......................................................................
383 * Delete a free-list block.
384 *
385 * Input:
386 * fl FreeListBlock * The block to be deleted, or NULL.
387 * Output:
388 * return FreeListBlock * Always NULL.
389 */
_del_FreeListBlock(FreeListBlock * fl)390 static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl)
391 {
392 if(fl) {
393 fl->next = NULL;
394 if(fl->nodes)
395 free(fl->nodes);
396 fl->nodes = NULL;
397 free(fl);
398 };
399 return NULL;
400 }
401