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 /* Allocator of IDs (e.g. OpenGL object IDs), or simply an allocator of 29 * numbers. 30 * 31 * The allocator uses a bit array to track allocated IDs. 32 */ 33 34 #ifndef U_IDALLOC_H 35 #define U_IDALLOC_H 36 37 #include <inttypes.h> 38 #include <stdbool.h> 39 #include "simple_mtx.h" 40 #include "bitscan.h" 41 42 #ifdef __cplusplus 43 extern "C" { 44 #endif 45 46 struct util_idalloc 47 { 48 uint32_t *data; 49 unsigned num_elements; /* number of allocated elements of "data" */ 50 unsigned num_set_elements; /* the last non-zero element of "data" + 1 */ 51 unsigned lowest_free_idx; 52 }; 53 54 void 55 util_idalloc_init(struct util_idalloc *buf, unsigned initial_num_ids); 56 57 void 58 util_idalloc_fini(struct util_idalloc *buf); 59 60 unsigned 61 util_idalloc_alloc(struct util_idalloc *buf); 62 63 unsigned 64 util_idalloc_alloc_range(struct util_idalloc *buf, unsigned num); 65 66 void 67 util_idalloc_free(struct util_idalloc *buf, unsigned id); 68 69 void 70 util_idalloc_reserve(struct util_idalloc *buf, unsigned id); 71 72 #define util_idalloc_foreach(buf, id) \ 73 for (uint32_t _i = 0, _mask = (buf)->num_set_elements ? (buf)->data[0] : 0, id, \ 74 _count = (buf)->num_used; \ 75 _i < _count; _mask = ++_i < _count ? (buf)->data[_i] : 0) \ 76 while (_mask) \ 77 if ((id = _i * 32 + u_bit_scan(&_mask)), true) 78 79 /* This allows freeing IDs while iterating, excluding ID=0. */ 80 #define util_idalloc_foreach_no_zero_safe(buf, id) \ 81 for (uint32_t _i = 0, _bit, id, _count = (buf)->num_set_elements, \ 82 _mask = _count ? (buf)->data[0] & ~0x1 : 0; \ 83 _i < _count; _mask = ++_i < _count ? (buf)->data[_i] : 0) \ 84 while (_mask) \ 85 if ((_bit = u_bit_scan(&_mask), id = _i * 32 + _bit), \ 86 (buf)->data[_i] & BITFIELD_BIT(_bit)) 87 88 /* Thread-safe variant. */ 89 struct util_idalloc_mt { 90 struct util_idalloc buf; 91 simple_mtx_t mutex; 92 bool skip_zero; 93 }; 94 95 void 96 util_idalloc_mt_init(struct util_idalloc_mt *buf, 97 unsigned initial_num_ids, bool skip_zero); 98 99 void 100 util_idalloc_mt_init_tc(struct util_idalloc_mt *buf); 101 102 void 103 util_idalloc_mt_fini(struct util_idalloc_mt *buf); 104 105 unsigned 106 util_idalloc_mt_alloc(struct util_idalloc_mt *buf); 107 108 void 109 util_idalloc_mt_free(struct util_idalloc_mt *buf, unsigned id); 110 111 /* util_idalloc_sparse: The 32-bit ID range is divided into separately managed 112 * segments. This reduces virtual memory usage when IDs are sparse. 113 * It's done by layering util_idalloc_sparse on top of util_idalloc. 114 * 115 * If the last ID is allocated: 116 * - "util_idalloc" occupies 512 MB of virtual memory 117 * - "util_idalloc_sparse" occupies only 512 KB of virtual memory 118 */ 119 struct util_idalloc_sparse { 120 struct util_idalloc segment[1024]; 121 }; 122 123 #define UTIL_IDALLOC_MAX_IDS_PER_SEGMENT(buf) \ 124 ((uint32_t)(BITFIELD64_BIT(32) / ARRAY_SIZE((buf)->segment))) 125 126 #define UTIL_IDALLOC_MAX_ELEMS_PER_SEGMENT(buf) \ 127 (UTIL_IDALLOC_MAX_IDS_PER_SEGMENT(buf) / 32) 128 129 void 130 util_idalloc_sparse_init(struct util_idalloc_sparse *buf); 131 132 void 133 util_idalloc_sparse_fini(struct util_idalloc_sparse *buf); 134 135 unsigned 136 util_idalloc_sparse_alloc(struct util_idalloc_sparse *buf); 137 138 unsigned 139 util_idalloc_sparse_alloc_range(struct util_idalloc_sparse *buf, unsigned num); 140 141 void 142 util_idalloc_sparse_free(struct util_idalloc_sparse *buf, unsigned id); 143 144 void 145 util_idalloc_sparse_reserve(struct util_idalloc_sparse *buf, unsigned id); 146 147 /* This allows freeing IDs while iterating, excluding ID=0. */ 148 #define util_idalloc_sparse_foreach_no_zero_safe(buf, id) \ 149 for (uint32_t _s = 0; _s < ARRAY_SIZE((buf)->segment); _s++) \ 150 for (uint32_t _i = 0, _bit, id, _count = (buf)->segment[_s].num_set_elements, \ 151 _mask = _count ? (buf)->segment[_s].data[0] & ~0x1 : 0; \ 152 _i < _count; _mask = ++_i < _count ? (buf)->segment[_s].data[_i] : 0) \ 153 while (_mask) \ 154 if ((_bit = u_bit_scan(&_mask), id = _s * UTIL_IDALLOC_MAX_IDS_PER_SEGMENT(buf) + _i * 32 + _bit), \ 155 (buf)->segment[_s].data[_i] & BITFIELD_BIT(_bit)) 156 157 #ifdef __cplusplus 158 } 159 #endif 160 161 #endif /* U_IDALLOC_H */ 162