40 util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements)  in util_idalloc_resize()  argument
42    if (new_num_elements > buf->num_elements) {  in util_idalloc_resize()
43       buf->data = realloc(buf->data, new_num_elements * sizeof(*buf->data));  in util_idalloc_resize()
44       memset(&buf->data[buf->num_elements], 0,  in util_idalloc_resize()
45              (new_num_elements - buf->num_elements) * sizeof(*buf->data));  in util_idalloc_resize()
46       buf->num_elements = new_num_elements;  in util_idalloc_resize()
51 util_idalloc_init(struct util_idalloc *buf, unsigned initial_num_ids)  in util_idalloc_init()  argument
53    memset(buf, 0, sizeof(*buf));  in util_idalloc_init()
55    util_idalloc_resize(buf, DIV_ROUND_UP(initial_num_ids, 32));  in util_idalloc_init()
59 util_idalloc_fini(struct util_idalloc *buf)  in util_idalloc_fini()  argument
61    if (buf->data)  in util_idalloc_fini()
62       free(buf->data);  in util_idalloc_fini()
66 util_idalloc_alloc(struct util_idalloc *buf)  in util_idalloc_alloc()  argument
68    unsigned num_elements = buf->num_elements;  in util_idalloc_alloc()
70    for (unsigned i = buf->lowest_free_idx; i < num_elements; i++) {  in util_idalloc_alloc()
71       if (buf->data[i] == 0xffffffff)  in util_idalloc_alloc()
74       unsigned bit = ffs(~buf->data[i]) - 1;  in util_idalloc_alloc()
75       buf->data[i] |= 1u << bit;  in util_idalloc_alloc()
76       buf->lowest_free_idx = i;  in util_idalloc_alloc()
81    util_idalloc_resize(buf, MAX2(num_elements, 1) * 2);  in util_idalloc_alloc()
83    buf->lowest_free_idx = num_elements;  in util_idalloc_alloc()
84    buf->data[num_elements] |= 1;  in util_idalloc_alloc()
89 find_free_block(struct util_idalloc *buf, unsigned start)  in find_free_block()  argument
91    for (unsigned i = start; i < buf->num_elements; i++) {  in find_free_block()
92       if (!buf->data[i])  in find_free_block()
95    return buf->num_elements;  in find_free_block()
100 util_idalloc_alloc_range(struct util_idalloc *buf, unsigned num)  in util_idalloc_alloc_range()  argument
103       return util_idalloc_alloc(buf);  in util_idalloc_alloc_range()
106    unsigned num_elements = buf->num_elements;  in util_idalloc_alloc_range()
107    unsigned base = find_free_block(buf, buf->lowest_free_idx);  in util_idalloc_alloc_range()
112            i < num_elements && i - base < num_alloc && !buf->data[i]; i++);  in util_idalloc_alloc_range()
121       base = !buf->data[i] ? i : i + 1;  in util_idalloc_alloc_range()
125    util_idalloc_resize(buf, num_elements * 2 + num_alloc);  in util_idalloc_alloc_range()
130       buf->data[i] = 0xffffffff;  in util_idalloc_alloc_range()
132       buf->data[base + num_alloc - 1] |= BITFIELD_MASK(num % 32);  in util_idalloc_alloc_range()
134    if (buf->lowest_free_idx == base)  in util_idalloc_alloc_range()
135       buf->lowest_free_idx = base + num / 32;  in util_idalloc_alloc_range()
139       assert(util_idalloc_exists(buf, base * 32 + i));  in util_idalloc_alloc_range()
145 util_idalloc_free(struct util_idalloc *buf, unsigned id)  in util_idalloc_free()  argument
147    assert(id / 32 < buf->num_elements);  in util_idalloc_free()
149    buf->lowest_free_idx = MIN2(idx, buf->lowest_free_idx);  in util_idalloc_free()
150    buf->data[idx] &= ~(1 << (id % 32));  in util_idalloc_free()
154 util_idalloc_reserve(struct util_idalloc *buf, unsigned id)  in util_idalloc_reserve()  argument
156    if (id / 32 >= buf->num_elements)  in util_idalloc_reserve()
157       util_idalloc_resize(buf, (id / 32 + 1) * 2);  in util_idalloc_reserve()
158    buf->data[id / 32] |= 1u << (id % 32);  in util_idalloc_reserve()
162 util_idalloc_mt_init(struct util_idalloc_mt *buf,  in util_idalloc_mt_init()  argument
165    simple_mtx_init(&buf->mutex, mtx_plain);  in util_idalloc_mt_init()
166    util_idalloc_init(&buf->buf, initial_num_ids);  in util_idalloc_mt_init()
167    buf->skip_zero = skip_zero;  in util_idalloc_mt_init()
170       ASSERTED unsigned zero = util_idalloc_alloc(&buf->buf);  in util_idalloc_mt_init()
177 util_idalloc_mt_init_tc(struct util_idalloc_mt *buf)  in util_idalloc_mt_init_tc()  argument
179    util_idalloc_mt_init(buf, 1 << 16, true);  in util_idalloc_mt_init_tc()
183 util_idalloc_mt_fini(struct util_idalloc_mt *buf)  in util_idalloc_mt_fini()  argument
185    util_idalloc_fini(&buf->buf);  in util_idalloc_mt_fini()
186    simple_mtx_destroy(&buf->mutex);  in util_idalloc_mt_fini()
190 util_idalloc_mt_alloc(struct util_idalloc_mt *buf)  in util_idalloc_mt_alloc()  argument
192    simple_mtx_lock(&buf->mutex);  in util_idalloc_mt_alloc()
193    unsigned id = util_idalloc_alloc(&buf->buf);  in util_idalloc_mt_alloc()
194    simple_mtx_unlock(&buf->mutex);  in util_idalloc_mt_alloc()
199 util_idalloc_mt_free(struct util_idalloc_mt *buf, unsigned id)  in util_idalloc_mt_free()  argument
201    if (id == 0 && buf->skip_zero)  in util_idalloc_mt_free()
204    simple_mtx_lock(&buf->mutex);  in util_idalloc_mt_free()
205    util_idalloc_free(&buf->buf, id);  in util_idalloc_mt_free()
206    simple_mtx_unlock(&buf->mutex);  in util_idalloc_mt_free()