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