1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019-2020 Broadcom
8 #define BITALLOC_MAX_LEVELS 6
10 /* Finds the first bit set plus 1, equivalent to gcc __builtin_ffs */
12 ba_ffs(bitalloc_word_t v)
14 int c; /* c will be the number of zero bits on the right plus 1 */
34 ba_init(struct bitalloc *pool, int size)
36 bitalloc_word_t *mem = (bitalloc_word_t *)pool;
42 if (size < 1 || size > BITALLOC_MAX_SIZE)
47 i < (int)(BITALLOC_SIZEOF(size) / sizeof(bitalloc_word_t));
54 /* Embed number of words of next level, after each level */
55 int words[BITALLOC_MAX_LEVELS];
59 words[0] = (size + 31) / 32;
60 while (words[lev] > 1) {
62 words[lev] = (words[lev - 1] + 31) / 32;
67 pool->storage[offset++] = words[--lev];
70 /* Free the entire pool */
71 for (i = 0; i < size; i++)
78 ba_alloc_helper(struct bitalloc *pool,
85 bitalloc_word_t *storage = &pool->storage[offset];
86 int loc = ba_ffs(storage[index]);
94 if (pool->size > size) {
95 r = ba_alloc_helper(pool,
102 r = index * 32 + loc;
108 storage[index] &= ~(1 << loc);
109 *clear = (storage[index] == 0);
116 ba_alloc(struct bitalloc *pool)
120 return ba_alloc_helper(pool, 0, 1, 32, 0, &clear);
124 ba_alloc_index_helper(struct bitalloc *pool,
131 bitalloc_word_t *storage = &pool->storage[offset];
135 if (pool->size > size)
136 r = ba_alloc_index_helper(pool,
143 r = 1; /* Check if already allocated */
146 *index = *index / 32;
149 r = (storage[*index] & (1 << loc)) ? 0 : -1;
157 storage[*index] &= ~(1 << loc);
158 *clear = (storage[*index] == 0);
165 ba_alloc_index(struct bitalloc *pool, int index)
168 int index_copy = index;
170 if (index < 0 || index >= (int)pool->size)
173 if (ba_alloc_index_helper(pool, 0, 1, 32, &index_copy, &clear) >= 0)
180 ba_inuse_helper(struct bitalloc *pool,
186 bitalloc_word_t *storage = &pool->storage[offset];
190 if (pool->size > size)
191 r = ba_inuse_helper(pool,
197 r = 1; /* Check if in use */
200 *index = *index / 32;
203 r = (storage[*index] & (1 << loc)) ? -1 : 0;
209 ba_inuse(struct bitalloc *pool, int index)
211 if (index < 0 || index >= (int)pool->size)
214 return ba_inuse_helper(pool, 0, 1, 32, &index) == 0;
218 ba_free_helper(struct bitalloc *pool,
224 bitalloc_word_t *storage = &pool->storage[offset];
228 if (pool->size > size)
229 r = ba_free_helper(pool,
235 r = 1; /* Check if already free */
238 *index = *index / 32;
241 r = (storage[*index] & (1 << loc)) ? -1 : 0;
247 storage[*index] |= (1 << loc);
253 ba_free(struct bitalloc *pool, int index)
255 if (index < 0 || index >= (int)pool->size)
258 return ba_free_helper(pool, 0, 1, 32, &index);
262 ba_inuse_free(struct bitalloc *pool, int index)
264 if (index < 0 || index >= (int)pool->size)
267 return ba_free_helper(pool, 0, 1, 32, &index) + 1;
271 ba_free_count(struct bitalloc *pool)
273 return (int)pool->free_count;
276 int ba_inuse_count(struct bitalloc *pool)
278 return (int)(pool->size) - (int)(pool->free_count);
282 ba_find_next_helper(struct bitalloc *pool,
289 bitalloc_word_t *storage = &pool->storage[offset];
290 int loc, r, bottom = 0;
292 if (pool->size > size)
293 r = ba_find_next_helper(pool,
300 bottom = 1; /* Bottom of tree */
303 *index = *index / 32;
306 int bit_index = *index * 32;
308 loc = ba_ffs(~storage[*index] & ((bitalloc_word_t)-1 << loc));
311 r = (bit_index + loc);
312 if (r >= (int)pool->size)
315 /* Loop over array at bottom of tree */
319 while ((int)pool->size > bit_index) {
320 loc = ba_ffs(~storage[*index]);
324 r = (bit_index + loc);
325 if (r >= (int)pool->size)
335 if (r >= 0 && (free)) {
338 storage[*index] |= (1 << loc);
345 ba_find_next_inuse(struct bitalloc *pool, int index)
348 index >= (int)pool->size ||
349 pool->free_count == pool->size)
352 return ba_find_next_helper(pool, 0, 1, 32, &index, 0);
356 ba_find_next_inuse_free(struct bitalloc *pool, int index)
359 index >= (int)pool->size ||
360 pool->free_count == pool->size)
363 return ba_find_next_helper(pool, 0, 1, 32, &index, 1);