d73b129ea26f7404bc13ce6dcefe9687c06ed8c5
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 #include "sparse_array.h"
26 struct util_sparse_array_node
{
33 util_sparse_array_init(struct util_sparse_array
*arr
,
34 size_t elem_size
, size_t node_size
)
36 memset(arr
, 0, sizeof(*arr
));
37 arr
->elem_size
= elem_size
;
38 arr
->node_size_log2
= util_logbase2_64(node_size
);
39 assert(node_size
>= 2 && node_size
== (1ull << arr
->node_size_log2
));
43 _util_sparse_array_node_data(struct util_sparse_array_node
*node
)
49 _util_sparse_array_node_finish(struct util_sparse_array
*arr
,
50 struct util_sparse_array_node
*node
)
52 if (node
->level
> 0) {
53 struct util_sparse_array_node
**children
=
54 _util_sparse_array_node_data(node
);
55 size_t node_size
= 1ull << arr
->node_size_log2
;
56 for (size_t i
= 0; i
< node_size
; i
++) {
57 if (children
[i
] != NULL
)
58 _util_sparse_array_node_finish(arr
, children
[i
]);
66 util_sparse_array_finish(struct util_sparse_array
*arr
)
69 _util_sparse_array_node_finish(arr
, arr
->root
);
72 static inline struct util_sparse_array_node
*
73 _util_sparse_array_alloc_node(struct util_sparse_array
*arr
,
76 size_t size
= sizeof(struct util_sparse_array_node
);
78 size
+= arr
->elem_size
<< arr
->node_size_log2
;
80 size
+= sizeof(struct util_sparse_array_node
*) << arr
->node_size_log2
;
83 struct util_sparse_array_node
*node
= calloc(1, size
);
89 static inline struct util_sparse_array_node
*
90 _util_sparse_array_set_or_free_node(struct util_sparse_array_node
**node_ptr
,
91 struct util_sparse_array_node
*cmp_node
,
92 struct util_sparse_array_node
*node
)
94 struct util_sparse_array_node
*prev_node
=
95 p_atomic_cmpxchg(node_ptr
, cmp_node
, node
);
97 if (prev_node
!= cmp_node
) {
98 /* We lost the race. Free this one and return the one that was already
109 util_sparse_array_get(struct util_sparse_array
*arr
, uint64_t idx
)
111 struct util_sparse_array_node
*root
= p_atomic_read(&arr
->root
);
112 if (unlikely(root
== NULL
)) {
113 unsigned root_level
= 0;
114 uint64_t idx_iter
= idx
>> arr
->node_size_log2
;
116 idx_iter
>>= arr
->node_size_log2
;
119 struct util_sparse_array_node
*new_root
=
120 _util_sparse_array_alloc_node(arr
, root_level
);
121 root
= _util_sparse_array_set_or_free_node(&arr
->root
, NULL
, new_root
);
125 uint64_t root_idx
= idx
>> (root
->level
* arr
->node_size_log2
);
126 if (likely(root_idx
< (1ull << arr
->node_size_log2
)))
129 /* In this case, we have a root but its level is low enough that the
130 * requested index is out-of-bounds.
132 struct util_sparse_array_node
*new_root
=
133 _util_sparse_array_alloc_node(arr
, root
->level
+ 1);
135 struct util_sparse_array_node
**new_root_children
=
136 _util_sparse_array_node_data(new_root
);
137 new_root_children
[0] = root
;
139 /* We only add one at a time instead of the whole tree because it's
140 * easier to ensure correctness of both the tree building and the
141 * clean-up path. Because we're only adding one node we never have to
142 * worry about trying to free multiple things without freeing the old
145 root
= _util_sparse_array_set_or_free_node(&arr
->root
, root
, new_root
);
148 struct util_sparse_array_node
*node
= root
;
149 while (node
->level
> 0) {
150 uint64_t child_idx
= (idx
>> (node
->level
* arr
->node_size_log2
)) &
151 ((1ull << arr
->node_size_log2
) - 1);
153 struct util_sparse_array_node
**children
=
154 _util_sparse_array_node_data(node
);
155 struct util_sparse_array_node
*child
=
156 p_atomic_read(&children
[child_idx
]);
158 if (unlikely(child
== NULL
)) {
159 child
= _util_sparse_array_alloc_node(arr
, node
->level
- 1);
160 child
= _util_sparse_array_set_or_free_node(&children
[child_idx
],
167 uint64_t elem_idx
= idx
& ((1ull << arr
->node_size_log2
) - 1);
168 return (void *)((char *)_util_sparse_array_node_data(node
) +
169 (elem_idx
* arr
->elem_size
));
173 validate_node_level(struct util_sparse_array
*arr
,
174 struct util_sparse_array_node
*node
,
177 assert(node
->level
== level
);
179 if (node
->level
> 0) {
180 struct util_sparse_array_node
**children
=
181 _util_sparse_array_node_data(node
);
182 size_t node_size
= 1ull << arr
->node_size_log2
;
183 for (size_t i
= 0; i
< node_size
; i
++) {
184 if (children
[i
] != NULL
)
185 validate_node_level(arr
, children
[i
], level
- 1);
191 util_sparse_array_validate(struct util_sparse_array
*arr
)
193 validate_node_level(arr
, arr
->root
, arr
->root
->level
);