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
40typedef struct FreeListBlock FreeListBlock;
41struct FreeListBlock {
42  FreeListBlock *next;   /* The next block in the list */
43  char *nodes;           /* The array of free-list nodes */
44};
45
46struct 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
55static FreeListBlock *_new_FreeListBlock(FreeList *fl);
56static FreeListBlock *_del_FreeListBlock(FreeListBlock *fl);
57static 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 */
72FreeList *_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 */
135void _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 */
184FreeList *_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 */
226void *_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 */
276void *_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 */
305long _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 */
319long _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 */
335static 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 */
375static 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 */
392static 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