1 /* 2 * Copyright © 2019 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 */ 23 24 #ifndef _UTIL_SPARSE_ARRAY_H 25 #define _UTIL_SPARSE_ARRAY_H 26 27 #include <stdint.h> 28 29 #include "c11/threads.h" 30 #include "macros.h" 31 #include "u_atomic.h" 32 #include "u_math.h" 33 34 #ifdef __cplusplus 35 extern "C" { 36 #endif 37 38 struct util_sparse_array_node; 39 40 /** A thread-safe automatically growing sparse array data structure 41 * 42 * This data structure has the following very nice properties: 43 * 44 * 1. Accessing an element is basically constant time. Technically, it's 45 * O(log_b n) where the base b is the node size and n is the maximum 46 * index. However, node sizes are expected to be fairly large and the 47 * index is a uint64_t so, if your node size is 256, it's O(8). 48 * 49 * 2. The data stored in the array is never moved in memory. Instead, the 50 * data structure only ever grows and new nodes are added as-needed. This 51 * means it's safe to store a pointer to something stored in the sparse 52 * array without worrying about a realloc invalidating it. 53 * 54 * 3. The data structure is thread-safe. No guarantees are made about the 55 * data stored in the sparse array but it is safe to call 56 * util_sparse_array_get(arr, idx) from as many threads as you'd like and 57 * we guarantee that two calls to util_sparse_array_get(arr, idx) with the 58 * same array and index will always return the same pointer regardless 59 * contention between threads. 60 * 61 * 4. The data structure is lock-free. All manipulations of the tree are 62 * done by a careful use of atomics to maintain thread safety and no locks 63 * are ever taken other than those taken implicitly by calloc(). If no 64 * allocation is required, util_sparse_array_get(arr, idx) does a simple 65 * walk over the tree should be efficient even in the case where many 66 * threads are accessing the sparse array at once. 67 */ 68 struct util_sparse_array { 69 size_t elem_size; 70 unsigned node_size_log2; 71 72 uintptr_t root; 73 }; 74 75 void util_sparse_array_init(struct util_sparse_array *arr, 76 size_t elem_size, size_t node_size); 77 78 void util_sparse_array_finish(struct util_sparse_array *arr); 79 80 void *util_sparse_array_get(struct util_sparse_array *arr, uint64_t idx); 81 82 void util_sparse_array_validate(struct util_sparse_array *arr); 83 84 /** A thread-safe free list for use with struct util_sparse_array 85 * 86 * This data structure provides an easy way to manage a singly linked list of 87 * "free" elements backed by a util_sparse_array. The list supports only two 88 * operations: push and pop both of which are thread-safe and lock-free. T 89 */ 90 struct 91 #ifdef _MSC_VER 92 __declspec(align(8)) 93 #else 94 __attribute__((aligned(8))) 95 #endif 96 util_sparse_array_free_list 97 { 98 /** Head of the list 99 * 100 * The bottom 64 bits of this value are the index to the next free element 101 * or the sentinel value if the list is empty. 102 * 103 * We want this element to be 8-byte aligned. Otherwise, the performance 104 * of atomic operations on it will be aweful on 32-bit platforms. 105 */ 106 uint64_t head; 107 108 /** The array backing this free list */ 109 struct util_sparse_array *arr; 110 111 /** Sentinel value to indicate the end of the list 112 * 113 * This value must never be passed into util_sparse_array_free_list_push. 114 */ 115 uint32_t sentinel; 116 117 /** Offset into the array element at which to find the "next" value 118 * 119 * The assumption is that there is some uint32_t "next" value embedded in 120 * the array element for use in the free list. This is its offset. 121 */ 122 uint32_t next_offset; 123 }; 124 125 void util_sparse_array_free_list_init(struct util_sparse_array_free_list *fl, 126 struct util_sparse_array *arr, 127 uint32_t sentinel, 128 uint32_t next_offset); 129 130 void util_sparse_array_free_list_push(struct util_sparse_array_free_list *fl, 131 uint32_t *items, unsigned num_items); 132 133 uint32_t util_sparse_array_free_list_pop_idx(struct util_sparse_array_free_list *fl); 134 void *util_sparse_array_free_list_pop_elem(struct util_sparse_array_free_list *fl); 135 136 #ifdef __cplusplus 137 } /* extern C */ 138 #endif 139 140 #endif /* _UTIL_SPARSE_ARRAY_H */ 141