On Fri, Aug 11, 2017 at 10:55 AM, Samuel Pitoiset <samuel.pitoi...@gmail.com> wrote: > Will be used for allocating bindless descriptor slots for > RadeonSI. > > v2 - change the interface (remove lock/unlock) > - make a non-inline implementation > > Signed-off-by: Samuel Pitoiset <samuel.pitoi...@gmail.com> > --- > src/gallium/auxiliary/Makefile.sources | 2 + > src/gallium/auxiliary/util/u_idalloc.c | 94 > ++++++++++++++++++++++++++++++++++ > src/gallium/auxiliary/util/u_idalloc.h | 62 ++++++++++++++++++++++ > 3 files changed, 158 insertions(+) > create mode 100644 src/gallium/auxiliary/util/u_idalloc.c > create mode 100644 src/gallium/auxiliary/util/u_idalloc.h > > diff --git a/src/gallium/auxiliary/Makefile.sources > b/src/gallium/auxiliary/Makefile.sources > index 9ae8e6c8ca..7d5f9e7899 100644 > --- a/src/gallium/auxiliary/Makefile.sources > +++ b/src/gallium/auxiliary/Makefile.sources > @@ -253,6 +253,8 @@ C_SOURCES := \ > util/u_hash_table.h \ > util/u_helpers.c \ > util/u_helpers.h \ > + util/u_idalloc.c \ > + util/u_idalloc.h \ > util/u_index_modify.c \ > util/u_index_modify.h \ > util/u_inlines.h \ > diff --git a/src/gallium/auxiliary/util/u_idalloc.c > b/src/gallium/auxiliary/util/u_idalloc.c > new file mode 100644 > index 0000000000..61b0e0cc49 > --- /dev/null > +++ b/src/gallium/auxiliary/util/u_idalloc.c > @@ -0,0 +1,94 @@ > +/************************************************************************** > + * > + * Copyright 2017 Valve Corporation > + * All Rights Reserved. > + * > + * Permission is hereby granted, free of charge, to any person obtaining a > + * copy of this software and associated documentation files (the > + * "Software"), to deal in the Software without restriction, including > + * without limitation the rights to use, copy, modify, merge, publish, > + * distribute, sub license, and/or sell copies of the Software, and to > + * permit persons to whom the Software is furnished to do so, subject to > + * the following conditions: > + * > + * The above copyright notice and this permission notice (including the > + * next paragraph) shall be included in all copies or substantial portions > + * of the Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS > + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF > + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. > + * IN NO EVENT SHALL THE AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR > + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, > + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE > + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. > + * > + **************************************************************************/ > + > +/** > + * @file > + * A simple allocator that allocates and release "numbers". > + * > + * @author Samuel Pitoiset <samuel.pitoi...@gmail.com> > + */ > + > +#include "util/u_idalloc.h" > +#include "util/u_math.h" > +#include "util/u_memory.h" > + > +void > +util_idalloc_init(struct util_idalloc *buf) > +{ > + memset(buf, 0, sizeof(*buf)); > +} > + > +void > +util_idalloc_fini(struct util_idalloc *buf) > +{ > + if (buf->data) > + free(buf->data); > +} > + > +void > +util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements) > +{ > + new_num_elements = align(new_num_elements, 32); > + > + if (new_num_elements > buf->num_elements) { > + unsigned i; > + > + buf->data = realloc(buf->data, > + (new_num_elements / 32) * sizeof(*buf->data)); > + > + for (i = buf->num_elements / 32; i < new_num_elements / 32; i++) > + buf->data[i] = 0; > + buf->num_elements = new_num_elements; > + } > +} > + > +unsigned > +util_idalloc_alloc(struct util_idalloc *buf) > +{ > + unsigned num_elements = buf->num_elements; > + > + for (unsigned i = 0; i < num_elements; i++) { > + if (!(buf->data[i / 32] & (1 << (i % 32)))) { > + buf->data[i / 32] |= 1 << (i % 32); > + return i; > + } > + }
This is faster: for (unsigned i = 0; i < num_elements / 32; i++) { if (buf->data[i] == 0xffffffff) continue; unsigned bit = ffs(~buf->data[i]) - 1; but->data[i] |= 1u << bit; return i * 32 + bit; } If you replace the loop with mine, the patch is: Reviewed-by: Marek Olšák <marek.ol...@amd.com> Marek > + > + /* No slots available, resize and return the first free. */ > + util_idalloc_resize(buf, num_elements * 2); > + > + buf->data[num_elements / 32] |= 1 << (num_elements % 32); > + > + return num_elements; > +} > + > +void > +util_idalloc_free(struct util_idalloc *buf, unsigned id) > +{ > + assert(id < buf->num_elements); > + buf->data[id / 32] &= ~(1 << (id % 32)); > +} > diff --git a/src/gallium/auxiliary/util/u_idalloc.h > b/src/gallium/auxiliary/util/u_idalloc.h > new file mode 100644 > index 0000000000..82469e94d8 > --- /dev/null > +++ b/src/gallium/auxiliary/util/u_idalloc.h > @@ -0,0 +1,62 @@ > +/************************************************************************** > + * > + * Copyright 2017 Valve Corporation > + * All Rights Reserved. > + * > + * Permission is hereby granted, free of charge, to any person obtaining a > + * copy of this software and associated documentation files (the > + * "Software"), to deal in the Software without restriction, including > + * without limitation the rights to use, copy, modify, merge, publish, > + * distribute, sub license, and/or sell copies of the Software, and to > + * permit persons to whom the Software is furnished to do so, subject to > + * the following conditions: > + * > + * The above copyright notice and this permission notice (including the > + * next paragraph) shall be included in all copies or substantial portions > + * of the Software. > + * > + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS > + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF > + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. > + * IN NO EVENT SHALL THE AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR > + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, > + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE > + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. > + * > + **************************************************************************/ > + > +#ifndef U_IDALLOC_H > +#define U_IDALLOC_H > + > +#include <inttypes.h> > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +struct util_idalloc > +{ > + uint32_t *data; > + unsigned num_elements; > +}; > + > +void > +util_idalloc_init(struct util_idalloc *buf); > + > +void > +util_idalloc_fini(struct util_idalloc *buf); > + > +void > +util_idalloc_resize(struct util_idalloc *buf, unsigned new_num_elements); > + > +unsigned > +util_idalloc_alloc(struct util_idalloc *buf); > + > +void > +util_idalloc_free(struct util_idalloc *buf, unsigned id); > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* U_IDALLOC_H */ > -- > 2.14.0 > > _______________________________________________ > mesa-dev mailing list > mesa-dev@lists.freedesktop.org > https://lists.freedesktop.org/mailman/listinfo/mesa-dev _______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev