1 /************************************************************************** 2 * 3 * Copyright 2017 Valve Corporation 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, sub license, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial portions 16 * of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 21 * IN NO EVENT SHALL THE AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR 22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 * 26 **************************************************************************/ 27 28 /** 29 * @file 30 * A simple allocator that allocates and release "numbers". 31 * 32 * @author Samuel Pitoiset <samuel.pitoiset (at) gmail.com> 33 */ 34 35 #include "util/u_idalloc.h" 36 #include "util/u_math.h" 37 #include "util/u_memory.h" 38 39 void 40 util_idalloc_init(struct util_idalloc *buf) 41 { 42 memset(buf, 0, sizeof(*buf)); 43 } 44 45 void 46 util_idalloc_fini(struct util_idalloc *buf) 47 { 48 if (buf->data) 49 free(buf->data); 50 } 51 52 void 53 util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements) 54 { 55 new_num_elements = align(new_num_elements, 32); 56 57 if (new_num_elements > buf->num_elements) { 58 unsigned i; 59 60 buf->data = realloc(buf->data, 61 (new_num_elements / 32) * sizeof(*buf->data)); 62 63 for (i = buf->num_elements / 32; i < new_num_elements / 32; i++) 64 buf->data[i] = 0; 65 buf->num_elements = new_num_elements; 66 } 67 } 68 69 unsigned 70 util_idalloc_alloc(struct util_idalloc *buf) 71 { 72 unsigned num_elements = buf->num_elements; 73 74 for (unsigned i = 0; i < num_elements / 32; i++) { 75 if (buf->data[i] == 0xffffffff) 76 continue; 77 78 unsigned bit = ffs(~buf->data[i]) - 1; 79 buf->data[i] |= 1u << bit; 80 return i * 32 + bit; 81 } 82 83 /* No slots available, resize and return the first free. */ 84 util_idalloc_resize(buf, num_elements * 2); 85 86 buf->data[num_elements / 32] |= 1 << (num_elements % 32); 87 88 return num_elements; 89 } 90 91 void 92 util_idalloc_free(struct util_idalloc *buf, unsigned id) 93 { 94 assert(id < buf->num_elements); 95 buf->data[id / 32] &= ~(1 << (id % 32)); 96 } 97