Mesa (master): util/idalloc: add lowest_free_idx to avoid iterating from 0

[GitLab Mirror]

Module: Mesa
Branch: master
Commit: 553d3719337f8698cf152d5932e60722a3745d34
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=553d3719337f8698cf152d5932e60722a3745d34

Author: Pierre-Eric Pelloux-Prayer <pierre-eric.pelloux-prayer at amd.com>
Date:   Mon Sep  7 15:15:50 2020 +0200

util/idalloc: add lowest_free_idx to avoid iterating from 0

lowest_free_idx is a conservative estimation of the lowest index
where a free id can be found.

Reviewed-by: Marek Olšák <marek.olsak at amd.com>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/6600>

---

 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 f08ec476a30..b5d886d200a 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 d78a0d4bb45..bd86e26195f 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