From 553d3719337f8698cf152d5932e60722a3745d34 Mon Sep 17 00:00:00 2001 From: Pierre-Eric Pelloux-Prayer Date: Mon, 7 Sep 2020 15:15:50 +0200 Subject: [PATCH] util/idalloc: add lowest_free_idx to avoid iterating from 0 MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit lowest_free_idx is a conservative estimation of the lowest index where a free id can be found. Reviewed-by: Marek Olšák Part-of: --- src/util/u_idalloc.c | 9 +++++++-- src/util/u_idalloc.h | 1 + 2 files changed, 8 insertions(+), 2 deletions(-) diff --git a/src/util/u_idalloc.c b/src/util/u_idalloc.c index f08ec47..b5d886d 100644 --- a/src/util/u_idalloc.c +++ b/src/util/u_idalloc.c @@ -71,18 +71,21 @@ util_idalloc_alloc(struct util_idalloc *buf) { unsigned num_elements = buf->num_elements; - for (unsigned i = 0; i < num_elements / 32; i++) { + for (unsigned i = buf->lowest_free_idx; i < num_elements / 32; i++) { if (buf->data[i] == 0xffffffff) continue; unsigned bit = ffs(~buf->data[i]) - 1; buf->data[i] |= 1u << bit; + buf->lowest_free_idx = i; return i * 32 + bit; } /* No slots available, resize and return the first free. */ util_idalloc_resize(buf, num_elements * 2); + buf->lowest_free_idx = num_elements / 32; + buf->data[num_elements / 32] |= 1 << (num_elements % 32); return num_elements; @@ -92,7 +95,9 @@ void util_idalloc_free(struct util_idalloc *buf, unsigned id) { assert(id < buf->num_elements); - buf->data[id / 32] &= ~(1 << (id % 32)); + unsigned idx = id / 32; + buf->lowest_free_idx = MIN2(idx, buf->lowest_free_idx); + buf->data[idx] &= ~(1 << (id % 32)); } void diff --git a/src/util/u_idalloc.h b/src/util/u_idalloc.h index d78a0d4..bd86e26 100644 --- a/src/util/u_idalloc.h +++ b/src/util/u_idalloc.h @@ -38,6 +38,7 @@ struct util_idalloc { uint32_t *data; unsigned num_elements; + unsigned lowest_free_idx; }; void -- 2.7.4