summaryrefslogtreecommitdiff
path: root/src/util/sparse_array.h
AgeCommit message (Collapse)AuthorFilesLines
2022-06-14util: use c11 alignas instead of rolling our ownErik Faye-Lund1-8/+2
Due to how alignas is defined, it itsn't allowed to use it on a struct, it needs to be used on the first member instead. So move the declaration in those cases. This still leaves the ALIGN16 macro using compiler-specific directives, because it's a lot of work to untangle the above. This probably deserves its own MR. Reviewed-by: Jesse Natalie <jenatali@microsoft.com> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/16908>
2020-03-20util/sparse_array: Stash the node level in the node pointerJason Ekstrand1-1/+1
This reworks the data structure a bit and, in my view, simplifies it. Instead of each node having a header which has the node level in it, we use the bottom 6 bits of the pointer for that. This requires us to allocate with the os_malloc/free_aligned helpers (which call into posix_memalign on Linux) but cache-line aligning our allocations is actually probably a good thing given that we're doing atomics on them. The primary advantages to doing this is that it changes the number of memory accesses per tree level from 2 to 1 when walking the tree because we no longer have to look at node->level. Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com> Tested-by: Marge Bot <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228>
2019-10-31util: Add a free list structure for use with util_sparse_arrayJason Ekstrand1-0/+52
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>
2019-10-31util: Add a util_sparse_array data structureJason Ekstrand1-0/+88
Reviewed-by: Lionel Landwerlin <lionel.g.landwerlin@intel.com>