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