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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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