diff options
-rw-r--r-- | src/gallium/auxiliary/Makefile.sources | 2 | ||||
-rw-r--r-- | src/gallium/auxiliary/util/u_idalloc.c | 96 | ||||
-rw-r--r-- | src/gallium/auxiliary/util/u_idalloc.h | 62 |
3 files changed, 160 insertions, 0 deletions
diff --git a/src/gallium/auxiliary/Makefile.sources b/src/gallium/auxiliary/Makefile.sources index 2adc60ca657..1b0eeb99581 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 00000000000..26104552e57 --- /dev/null +++ b/src/gallium/auxiliary/util/u_idalloc.c @@ -0,0 +1,96 @@ +/************************************************************************** + * + * 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 <[email protected]> + */ + +#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 / 32; i++) { + if (buf->data[i] == 0xffffffff) + continue; + + unsigned bit = ffs(~buf->data[i]) - 1; + buf->data[i] |= 1u << bit; + return i * 32 + bit; + } + + /* 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 00000000000..82469e94d82 --- /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 */ |