2 * Copyright © 2019 Intel Corporation
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:
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
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
24 #ifndef _UTIL_SPARSE_ARRAY_H
25 #define _UTIL_SPARSE_ARRAY_H
29 #include "c11/threads.h"
38 struct util_sparse_array_node
;
40 /** A thread-safe automatically growing sparse array data structure
42 * This data structure has the following very nice properties:
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).
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.
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.
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.
68 struct util_sparse_array
{
70 unsigned node_size_log2
;
75 void util_sparse_array_init(struct util_sparse_array
*arr
,
76 size_t elem_size
, size_t node_size
);
78 void util_sparse_array_finish(struct util_sparse_array
*arr
);
80 void *util_sparse_array_get(struct util_sparse_array
*arr
, uint64_t idx
);
82 void util_sparse_array_validate(struct util_sparse_array
*arr
);
84 /** A thread-safe free list for use with struct util_sparse_array
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
94 __attribute__((aligned(8)))
96 util_sparse_array_free_list
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.
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.
108 /** The array backing this free list */
109 struct util_sparse_array
*arr
;
111 /** Sentinel value to indicate the end of the list
113 * This value must never be passed into util_sparse_array_free_list_push.
117 /** Offset into the array element at which to find the "next" value
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.
122 uint32_t next_offset
;
125 void util_sparse_array_free_list_init(struct util_sparse_array_free_list
*fl
,
126 struct util_sparse_array
*arr
,
128 uint32_t next_offset
);
130 void util_sparse_array_free_list_push(struct util_sparse_array_free_list
*fl
,
131 uint32_t *items
, unsigned num_items
);
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
);
140 #endif /* _UTIL_SPARSE_ARRAY_H */