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