xref: /titanic_51/usr/src/lib/libtecla/common/freelist.c (revision 5a7763bf3e9db4cfe6cb523b096cb74af71e3793)
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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