Line data Source code
1 : /** Copyright 2025 Alexander G. Lopez
2 :
3 : Licensed under the Apache License, Version 2.0 (the "License");
4 : you may not use this file except in compliance with the License.
5 : You may obtain a copy of the License at
6 :
7 : http://www.apache.org/licenses/LICENSE-2.0
8 :
9 : Unless required by applicable law or agreed to in writing, software
10 : distributed under the License is distributed on an "AS IS" BASIS,
11 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : See the License for the specific language governing permissions and
13 : limitations under the License.
14 :
15 : This file contains my implementation of an array tree ordered map. The added
16 : tree prefix is to indicate that this map meets specific run time bounds
17 : that can be relied upon consistently. This is may not be the case if a map
18 : is implemented with some self-optimizing data structure like a Splay Tree.
19 :
20 : This map, however, promises O(lg N) search, insert, and remove as a true
21 : upper bound, inclusive. This guarantee does not consider the cost of resizing
22 : the underlying Struct of Arrays layout. For the strict bound to be met the user
23 : should reserve space for the needed nodes through the API. Performance could
24 : still be strong with a more dynamic approach, however, The runtime bound is
25 : achieved through a Weak AVL (WAVL) tree that is derived from the following two
26 : sources.
27 :
28 : [1] Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan, 2014.
29 : Rank-Balanced Trees, J.ACM Transactions on Algorithms 11, 4, Article 0
30 : (June 2015), 24 pages.
31 : https://sidsen.azurewebsites.net//papers/rb-trees-talg.pdf
32 :
33 : [2] Phil Vachon (pvachon) https://github.com/pvachon/wavl_tree
34 : This implementation is heavily influential throughout. However there have
35 : been some major adjustments and simplifications. Namely, the allocation has
36 : been adjusted to accommodate this library's ability to be an allocating or
37 : non-allocating container. All left-right symmetric cases have been united
38 : into one and I chose to tackle rotations and deletions slightly differently,
39 : shortening the code significantly. A few other changes and improvements
40 : suggested by the authors of the original paper are implemented. Finally, the
41 : data structure has been placed into an array with relative indices rather
42 : than pointers. See the required license at the bottom of the file for
43 : BSD-2-Clause compliance.
44 :
45 : Overall a WAVL tree is quite impressive for it's simplicity and purported
46 : improvements over AVL and Red-Black trees. The rank framework is intuitive
47 : and flexible in how it can be implemented.
48 :
49 : Sorry for the symbol heavy math variable terminology in the WAVL section. It
50 : is easiest to check work against the research paper if the variable names
51 : remain the same. Rotations change lineage so there is no less terse approach
52 : to that section, in my opinion. */
53 : /** C23 provided headers. */
54 : #include <limits.h>
55 : #include <stdalign.h>
56 : #include <stddef.h>
57 : #include <stdint.h>
58 :
59 : /** CCC provided headers. */
60 : #include "ccc/array_tree_map.h"
61 : #include "ccc/configuration.h" /* IWYU pragma: keep */
62 : #include "ccc/private/private_array_tree_map.h"
63 : #include "ccc/types.h"
64 :
65 : /*========================== Type Declarations ===========================*/
66 :
67 : /** @internal */
68 : enum Link : uint8_t {
69 : L = 0,
70 : R,
71 : };
72 :
73 : /** @internal To make insertions and removals more efficient we can remember the
74 : last node encountered on the search for the requested node. It will either be
75 : the correct node or the parent of the missing node if it is not found. This
76 : means insertions will not need a second search of the tree and we can insert
77 : immediately by adding the child. */
78 : struct Query {
79 : /** The last branch direction we took to the found or missing node. */
80 : CCC_Order last_order;
81 : union {
82 : /** The node was found so here is its index in the array. */
83 : size_t found;
84 : /** The node was not found so here is its direct parent. */
85 : size_t parent;
86 : };
87 : };
88 :
89 : #define INORDER R
90 : #define INORDER_REVERSE L
91 :
92 : enum : uint8_t {
93 : INSERT_ROOT_COUNT = 2,
94 : };
95 :
96 : /** @internal A block of parity bits. */
97 : typedef typeof(*(struct CCC_Array_tree_map){}.parity) Parity_block;
98 :
99 : enum : size_t {
100 : /** @internal Test capacity. */
101 : TCAP = 3,
102 : /* @internal Alignment of node type. */
103 : ALIGNOF_NODE = alignof(struct CCC_Array_tree_map_node),
104 : /** @internal Size of node type. */
105 : SIZEOF_NODE = sizeof(struct CCC_Array_tree_map_node),
106 : /** @internal Alignment of parity block. */
107 : ALIGNOF_PARITY = alignof(Parity_block),
108 : /** @internal Size of parity block. */
109 : SIZEOF_PARITY = sizeof(Parity_block),
110 : /** @internal The number of bits in a block of parity bits. */
111 : PARITY_BLOCK_BITS = SIZEOF_PARITY * CHAR_BIT,
112 : /** @internal Hand calculated log2 of block bits for a fast shift rather
113 : than division. No reasonable compile time calculation for this in C. */
114 : PARITY_BLOCK_BITS_LOG2 = 5,
115 : };
116 : static_assert(
117 : PARITY_BLOCK_BITS >> PARITY_BLOCK_BITS_LOG2 == 1,
118 : "hand coded log2 of parity block bits is always correct"
119 : );
120 :
121 : /*======================== Data Alignment Test ==========================*/
122 :
123 : /** @internal A macro version of the runtime alignment operations we perform
124 : for calculating bytes. This way we can use in static assert. The user data type
125 : may not be the same alignment as the nodes and therefore the nodes array must
126 : start at next aligned byte. Similarly the parity array may not be on an aligned
127 : byte after the nodes array, though in the current implementation it is.
128 : Regardless, we always ensure the position is correct with respect to power of
129 : two alignments in C. */
130 : #define roundup(bytes_to_round, alignment) \
131 : (((bytes_to_round) + (alignment) - 1) & ~((alignment) - 1))
132 :
133 : /** @internal This is a static fixed size map exclusive to this translation unit
134 : used to ensure assumptions about data layout are correct. The following static
135 : asserts must be true in order to support the Struct of Array style layout we
136 : use for the data, nodes, and parity arrays. It is important that in our user
137 : code when we set the positions of the nodes and parity pointers relative to the
138 : data pointer the positions are correct regardless of if our backing storage is
139 : a fixed map or heap allocation.
140 :
141 : Use an int because that will force the nodes array to be wary of
142 : where to start. The nodes are 8 byte aligned but an int is 4. This means the
143 : nodes need to start after 4 byte buffer of padding at end of data array. */
144 : static __auto_type const static_data_nodes_parity_layout_test
145 : = CCC_private_array_tree_map_storage_for((int const[TCAP]){});
146 : /** Some assumptions in the code assume that parity array is last so ensure that
147 : is the case here. Also good to assume user data comes first. */
148 : static_assert(
149 : ((char const *)static_data_nodes_parity_layout_test.data
150 : < (char const *)static_data_nodes_parity_layout_test.nodes),
151 : "The order of the arrays in a Struct of Arrays map is user data "
152 : "first, nodes second."
153 : );
154 : static_assert(
155 : ((char const *)static_data_nodes_parity_layout_test.nodes
156 : < (char const *)static_data_nodes_parity_layout_test.parity),
157 : "The order of the arrays in a Struct of Arrays map is internal "
158 : "nodes second, parity third."
159 : );
160 : static_assert(
161 : (char const *)static_data_nodes_parity_layout_test.data
162 : < (char const *)static_data_nodes_parity_layout_test.parity,
163 : "The order of the arrays in a Struct of Arrays map is data, then "
164 : "nodes, then parity."
165 : );
166 : /** We don't care about the alignment or padding after the parity array because
167 : we never need to set or move any pointers to that position. The alignment is
168 : important for the nodes and parity pointer to be set to the correct aligned
169 : positions and so that we allocate enough bytes for our single allocation if
170 : the map is dynamic and not a fixed type. */
171 : static_assert(
172 : (char const *)&static_data_nodes_parity_layout_test
173 : .parity[CCC_private_array_tree_map_blocks(TCAP)]
174 : - (char const *)&static_data_nodes_parity_layout_test.data[0]
175 : == roundup(
176 : (sizeof(*static_data_nodes_parity_layout_test.data) * TCAP),
177 : ALIGNOF_NODE
178 : ) + roundup((SIZEOF_NODE * TCAP), ALIGNOF_PARITY)
179 : + (SIZEOF_PARITY * CCC_private_array_tree_map_blocks(TCAP)),
180 : "The pointer difference in bytes between end of parity bit array and start "
181 : "of user data array must be the same as the total bytes we assume to be "
182 : "stored in that range. Alignment of user data must be considered."
183 : );
184 : static_assert(
185 : (char const *)&static_data_nodes_parity_layout_test.data
186 : + roundup(
187 : (sizeof(*static_data_nodes_parity_layout_test.data) * TCAP),
188 : ALIGNOF_NODE
189 : )
190 : == (char const *)&static_data_nodes_parity_layout_test.nodes,
191 : "The start of the nodes array must begin at the next aligned "
192 : "byte given alignment of a node."
193 : );
194 : static_assert(
195 : (char const *)&static_data_nodes_parity_layout_test.parity
196 : == ((char const *)&static_data_nodes_parity_layout_test.data
197 : + roundup(
198 : (sizeof(*static_data_nodes_parity_layout_test.data) * TCAP),
199 : ALIGNOF_NODE
200 : )
201 : + roundup((SIZEOF_NODE * TCAP), ALIGNOF_PARITY)),
202 : "The start of the parity array must begin at the next aligned byte given "
203 : "alignment of both the data and nodes array."
204 : );
205 : static_assert(
206 : ALIGNOF_NODE >= ALIGNOF_PARITY,
207 : "Parity bit array is always aligned after node array without any special "
208 : "alignment or padding considerations."
209 : );
210 :
211 : /*============================== Prototypes ==============================*/
212 :
213 : static void insert(struct CCC_Array_tree_map *, size_t, CCC_Order, size_t);
214 : static CCC_Result
215 : resize(struct CCC_Array_tree_map *, size_t, CCC_Allocator const *);
216 : static void
217 : resize_struct_of_arrays(struct CCC_Array_tree_map const *, void *, size_t);
218 : static size_t data_bytes(size_t, size_t);
219 : static size_t nodes_bytes(size_t);
220 : static size_t parities_bytes(size_t);
221 : static struct CCC_Array_tree_map_node *
222 : nodes_base_address(size_t, void const *, size_t);
223 : static Parity_block *parities_base_address(size_t, void const *, size_t);
224 : static size_t maybe_allocate_insert(
225 : struct CCC_Array_tree_map *,
226 : size_t,
227 : CCC_Order,
228 : void const *,
229 : CCC_Allocator const *
230 : );
231 : static size_t remove_fixup(struct CCC_Array_tree_map *, size_t);
232 : static size_t allocate_slot(struct CCC_Array_tree_map *, CCC_Allocator const *);
233 : static void
234 : delete_nodes(struct CCC_Array_tree_map const *, CCC_Destructor const *);
235 : static void *key_at(struct CCC_Array_tree_map const *, size_t);
236 : static void *key_in_slot(struct CCC_Array_tree_map const *, void const *);
237 : static struct CCC_Array_tree_map_node *
238 : node_at(struct CCC_Array_tree_map const *, size_t);
239 : static void *data_at(struct CCC_Array_tree_map const *, size_t);
240 : static struct Query find(struct CCC_Array_tree_map const *, void const *);
241 : static struct CCC_Array_tree_map_handle
242 : handle(struct CCC_Array_tree_map const *, void const *);
243 : static CCC_Handle_range equal_range(
244 : struct CCC_Array_tree_map const *, void const *, void const *, enum Link
245 : );
246 : static CCC_Order
247 : order_nodes(struct CCC_Array_tree_map const *, void const *, size_t);
248 : static size_t sibling_of(struct CCC_Array_tree_map const *, size_t);
249 : static size_t next(struct CCC_Array_tree_map const *, size_t, enum Link);
250 : static size_t
251 : min_max_from(struct CCC_Array_tree_map const *, size_t, enum Link);
252 : static size_t
253 : branch_index(struct CCC_Array_tree_map const *, size_t, enum Link);
254 : static size_t parent_index(struct CCC_Array_tree_map const *, size_t);
255 : static size_t *
256 : branch_pointer(struct CCC_Array_tree_map const *, size_t, enum Link);
257 : static size_t *parent_pointer(struct CCC_Array_tree_map const *, size_t);
258 : static CCC_Tribool
259 : is_0_child(struct CCC_Array_tree_map const *, size_t, size_t);
260 : static CCC_Tribool
261 : is_1_child(struct CCC_Array_tree_map const *, size_t, size_t);
262 : static CCC_Tribool
263 : is_2_child(struct CCC_Array_tree_map const *, size_t, size_t);
264 : static CCC_Tribool
265 : is_3_child(struct CCC_Array_tree_map const *, size_t, size_t);
266 : static CCC_Tribool
267 : is_01_parent(struct CCC_Array_tree_map const *, size_t, size_t, size_t);
268 : static CCC_Tribool
269 : is_11_parent(struct CCC_Array_tree_map const *, size_t, size_t, size_t);
270 : static CCC_Tribool
271 : is_02_parent(struct CCC_Array_tree_map const *, size_t, size_t, size_t);
272 : static CCC_Tribool
273 : is_22_parent(struct CCC_Array_tree_map const *, size_t, size_t, size_t);
274 : static CCC_Tribool is_leaf(struct CCC_Array_tree_map const *, size_t);
275 : static CCC_Tribool parity(struct CCC_Array_tree_map const *, size_t);
276 : static void set_parity(struct CCC_Array_tree_map const *, size_t, CCC_Tribool);
277 : static size_t total_bytes(size_t, size_t);
278 : static size_t block_count(size_t);
279 : static CCC_Tribool validate(struct CCC_Array_tree_map const *);
280 : static void init_node(struct CCC_Array_tree_map const *, size_t);
281 : static void insert_fixup(struct CCC_Array_tree_map *, size_t, size_t);
282 : static void rebalance_3_child(struct CCC_Array_tree_map *, size_t, size_t);
283 : static void transplant(struct CCC_Array_tree_map *, size_t, size_t);
284 : static void promote(struct CCC_Array_tree_map const *, size_t);
285 : static void demote(struct CCC_Array_tree_map const *, size_t);
286 : static void double_promote(struct CCC_Array_tree_map const *, size_t);
287 : static void double_demote(struct CCC_Array_tree_map const *, size_t);
288 : static void
289 : rotate(struct CCC_Array_tree_map *, size_t, size_t, size_t, enum Link);
290 : static void
291 : double_rotate(struct CCC_Array_tree_map *, size_t, size_t, size_t, enum Link);
292 : static void swap(void *, size_t, void *, void *);
293 : static size_t max_size_t(size_t, size_t);
294 :
295 : /*============================== Interface ==============================*/
296 :
297 : void *
298 16783 : CCC_array_tree_map_at(
299 : CCC_Array_tree_map const *const map, CCC_Handle_index const index
300 : ) {
301 16783 : if (!map || !index) {
302 13 : return NULL;
303 : }
304 16770 : return data_at(map, index);
305 16783 : }
306 :
307 : CCC_Tribool
308 66 : CCC_array_tree_map_contains(
309 : CCC_Array_tree_map const *const map, void const *const key
310 : ) {
311 66 : if (!map || !key) {
312 2 : return CCC_TRIBOOL_ERROR;
313 : }
314 64 : return CCC_ORDER_EQUAL == find(map, key).last_order;
315 66 : }
316 :
317 : CCC_Handle_index
318 2017 : CCC_array_tree_map_get_key_value(
319 : CCC_Array_tree_map const *const map, void const *const key
320 : ) {
321 2017 : if (!map || !key) {
322 2 : return 0;
323 : }
324 2015 : struct Query const q = find(map, key);
325 2015 : return (CCC_ORDER_EQUAL == q.last_order) ? q.found : 0;
326 2017 : }
327 :
328 : CCC_Handle
329 3598 : CCC_array_tree_map_swap_handle(
330 : CCC_Array_tree_map *const map,
331 : void *const type_output,
332 : CCC_Allocator const *const allocator
333 : ) {
334 3598 : if (!map || !type_output || !allocator) {
335 3 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
336 : }
337 3595 : struct Query const q = find(map, key_in_slot(map, type_output));
338 3595 : if (CCC_ORDER_EQUAL == q.last_order) {
339 834 : void *const slot = data_at(map, q.found);
340 834 : void *const temp = data_at(map, 0);
341 834 : swap(temp, map->sizeof_type, type_output, slot);
342 1668 : return (CCC_Handle){
343 834 : .index = q.found,
344 : .status = CCC_ENTRY_OCCUPIED,
345 : };
346 834 : }
347 5522 : size_t const i = maybe_allocate_insert(
348 2761 : map, q.parent, q.last_order, type_output, allocator
349 : );
350 2761 : if (!i) {
351 1 : return (CCC_Handle){
352 : .index = 0,
353 : .status = CCC_ENTRY_INSERT_ERROR,
354 : };
355 : }
356 5520 : return (CCC_Handle){
357 2760 : .index = i,
358 : .status = CCC_ENTRY_VACANT,
359 : };
360 3598 : }
361 :
362 : CCC_Handle
363 225 : CCC_array_tree_map_try_insert(
364 : CCC_Array_tree_map *const map,
365 : void const *const type,
366 : CCC_Allocator const *const allocator
367 : ) {
368 225 : if (!map || !type || !allocator) {
369 4 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
370 : }
371 221 : struct Query const q = find(map, key_in_slot(map, type));
372 221 : if (CCC_ORDER_EQUAL == q.last_order) {
373 90 : return (CCC_Handle){
374 45 : .index = q.found,
375 : .status = CCC_ENTRY_OCCUPIED,
376 : };
377 : }
378 352 : size_t const i
379 176 : = maybe_allocate_insert(map, q.parent, q.last_order, type, allocator);
380 176 : if (!i) {
381 1 : return (CCC_Handle){
382 : .index = 0,
383 : .status = CCC_ENTRY_INSERT_ERROR,
384 : };
385 : }
386 350 : return (CCC_Handle){
387 175 : .index = i,
388 : .status = CCC_ENTRY_VACANT,
389 : };
390 225 : }
391 :
392 : CCC_Handle
393 2006 : CCC_array_tree_map_insert_or_assign(
394 : CCC_Array_tree_map *const map,
395 : void const *const type,
396 : CCC_Allocator const *const allocator
397 : ) {
398 2006 : if (!map || !type || !allocator) {
399 3 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
400 : }
401 2003 : struct Query const q = find(map, key_in_slot(map, type));
402 2003 : if (CCC_ORDER_EQUAL == q.last_order) {
403 3 : void *const found = data_at(map, q.found);
404 3 : (void)memcpy(found, type, map->sizeof_type);
405 6 : return (CCC_Handle){
406 3 : .index = q.found,
407 : .status = CCC_ENTRY_OCCUPIED,
408 : };
409 3 : }
410 4000 : size_t const i
411 2000 : = maybe_allocate_insert(map, q.parent, q.last_order, type, allocator);
412 2000 : if (!i) {
413 3 : return (CCC_Handle){
414 : .index = 0,
415 : .status = CCC_ENTRY_INSERT_ERROR,
416 : };
417 : }
418 3994 : return (CCC_Handle){
419 1997 : .index = i,
420 : .status = CCC_ENTRY_VACANT,
421 : };
422 2006 : }
423 :
424 : CCC_Array_tree_map_handle *
425 112 : CCC_array_tree_map_and_modify(
426 : CCC_Array_tree_map_handle *const handle, CCC_Modifier const *const modifier
427 : ) {
428 112 : if (!handle || !modifier) {
429 2 : return NULL;
430 : }
431 110 : if (modifier->modify && handle->status & CCC_ENTRY_OCCUPIED
432 110 : && handle->index > 0) {
433 168 : modifier->modify((CCC_Arguments){
434 56 : .type = data_at(handle->map, handle->index),
435 56 : modifier->context,
436 : });
437 56 : }
438 110 : return handle;
439 112 : }
440 :
441 : CCC_Handle_index
442 262 : CCC_array_tree_map_or_insert(
443 : CCC_Array_tree_map_handle const *const h,
444 : void const *const type,
445 : CCC_Allocator const *const allocator
446 : ) {
447 262 : if (!h || !type || !allocator) {
448 3 : return 0;
449 : }
450 259 : if (h->status == CCC_ENTRY_OCCUPIED) {
451 153 : return h->index;
452 : }
453 106 : return maybe_allocate_insert(
454 106 : h->map, h->index, h->last_order, type, allocator
455 : );
456 262 : }
457 :
458 : CCC_Handle_index
459 8381 : CCC_array_tree_map_insert_handle(
460 : CCC_Array_tree_map_handle const *const h,
461 : void const *const type,
462 : CCC_Allocator const *const allocator
463 : ) {
464 8381 : if (!h || !type || !allocator) {
465 3 : return 0;
466 : }
467 8378 : if (h->status == CCC_ENTRY_OCCUPIED) {
468 3105 : void *const slot = data_at(h->map, h->index);
469 3105 : if (slot != type) {
470 3105 : (void)memcpy(slot, type, h->map->sizeof_type);
471 3105 : }
472 3105 : return h->index;
473 3105 : }
474 5273 : return maybe_allocate_insert(
475 5273 : h->map, h->index, h->last_order, type, allocator
476 : );
477 8381 : }
478 :
479 : CCC_Array_tree_map_handle
480 13044 : CCC_array_tree_map_handle(
481 : CCC_Array_tree_map const *const map, void const *const key
482 : ) {
483 13044 : if (!map || !key) {
484 2 : return (CCC_Array_tree_map_handle){
485 : .status = CCC_ENTRY_ARGUMENT_ERROR,
486 : };
487 : }
488 13042 : return handle(map, key);
489 13044 : }
490 :
491 : CCC_Handle
492 55 : CCC_array_tree_map_remove_handle(CCC_Array_tree_map_handle const *const h) {
493 55 : if (!h) {
494 1 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
495 : }
496 54 : if (h->status == CCC_ENTRY_OCCUPIED) {
497 44 : size_t const ret = remove_fixup(h->map, h->index);
498 88 : return (CCC_Handle){
499 44 : .index = ret,
500 : .status = CCC_ENTRY_OCCUPIED,
501 : };
502 44 : }
503 10 : return (CCC_Handle){
504 : .index = 0,
505 : .status = CCC_ENTRY_VACANT,
506 : };
507 55 : }
508 :
509 : CCC_Handle
510 2309 : CCC_array_tree_map_remove_key_value(
511 : CCC_Array_tree_map *const map, void *const type_output
512 : ) {
513 2309 : if (!map || !type_output) {
514 2 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
515 : }
516 2307 : struct Query const q = find(map, key_in_slot(map, type_output));
517 2307 : if (q.last_order != CCC_ORDER_EQUAL) {
518 3 : return (CCC_Handle){
519 : .index = 0,
520 : .status = CCC_ENTRY_VACANT,
521 : };
522 : }
523 2304 : size_t const removed = remove_fixup(map, q.found);
524 2304 : assert(removed);
525 2304 : void const *const r = data_at(map, removed);
526 2304 : if (type_output != r) {
527 2304 : (void)memcpy(type_output, r, map->sizeof_type);
528 2304 : }
529 2304 : return (CCC_Handle){
530 : .index = 0,
531 : .status = CCC_ENTRY_OCCUPIED,
532 : };
533 2309 : }
534 :
535 : CCC_Handle_range
536 8 : CCC_array_tree_map_equal_range(
537 : CCC_Array_tree_map const *const map,
538 : void const *const begin_key,
539 : void const *const end_key
540 : ) {
541 8 : if (!map || !begin_key || !end_key) {
542 3 : return (CCC_Handle_range){};
543 : }
544 5 : return equal_range(map, begin_key, end_key, INORDER);
545 8 : }
546 :
547 : CCC_Handle_range_reverse
548 8 : CCC_array_tree_map_equal_range_reverse(
549 : CCC_Array_tree_map const *const map,
550 : void const *const reverse_begin_key,
551 : void const *const reverse_end_key
552 : ) {
553 8 : if (!map || !reverse_begin_key || !reverse_end_key) {
554 3 : return (CCC_Handle_range_reverse){};
555 : }
556 5 : CCC_Handle_range const range
557 5 : = equal_range(map, reverse_begin_key, reverse_end_key, INORDER_REVERSE);
558 15 : return (CCC_Handle_range_reverse){
559 5 : .reverse_begin = range.begin,
560 5 : .reverse_end = range.end,
561 : };
562 8 : }
563 :
564 : CCC_Handle_index
565 16 : CCC_array_tree_map_unwrap(CCC_Array_tree_map_handle const *const h) {
566 16 : if (h && h->status & CCC_ENTRY_OCCUPIED && h->index > 0) {
567 15 : return h->index;
568 : }
569 1 : return 0;
570 16 : }
571 :
572 : CCC_Tribool
573 3 : CCC_array_tree_map_insert_error(CCC_Array_tree_map_handle const *const h) {
574 3 : if (!h) {
575 2 : return CCC_TRIBOOL_ERROR;
576 : }
577 1 : return (h->status & CCC_ENTRY_INSERT_ERROR) != 0;
578 3 : }
579 :
580 : CCC_Tribool
581 84 : CCC_array_tree_map_occupied(CCC_Array_tree_map_handle const *const h) {
582 84 : if (!h) {
583 1 : return CCC_TRIBOOL_ERROR;
584 : }
585 83 : return (h->status & CCC_ENTRY_OCCUPIED) != 0;
586 84 : }
587 :
588 : CCC_Handle_status
589 2 : CCC_array_tree_map_handle_status(CCC_Array_tree_map_handle const *const h) {
590 2 : return h ? h->status : CCC_ENTRY_ARGUMENT_ERROR;
591 : }
592 :
593 : CCC_Tribool
594 31 : CCC_array_tree_map_is_empty(CCC_Array_tree_map const *const map) {
595 31 : if (!map) {
596 1 : return CCC_TRIBOOL_ERROR;
597 : }
598 30 : return !CCC_array_tree_map_count(map).count;
599 31 : }
600 :
601 : CCC_Count
602 184 : CCC_array_tree_map_count(CCC_Array_tree_map const *const map) {
603 184 : if (!map) {
604 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
605 : }
606 183 : if (!map->count) {
607 24 : return (CCC_Count){.count = 0};
608 : }
609 : /* The root slot is occupied at 0 but don't don't tell user. */
610 318 : return (CCC_Count){
611 159 : .count = map->count - 1,
612 : };
613 184 : }
614 :
615 : CCC_Count
616 13 : CCC_array_tree_map_capacity(CCC_Array_tree_map const *const map) {
617 13 : if (!map) {
618 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
619 : }
620 24 : return (CCC_Count){
621 12 : .count = map->capacity,
622 : };
623 13 : }
624 :
625 : CCC_Handle_index
626 17 : CCC_array_tree_map_begin(CCC_Array_tree_map const *const map) {
627 17 : if (!map || !map->capacity) {
628 3 : return 0;
629 : }
630 14 : size_t const n = min_max_from(map, map->root, L);
631 14 : return n;
632 17 : }
633 :
634 : CCC_Handle_index
635 3 : CCC_array_tree_map_reverse_begin(CCC_Array_tree_map const *const map) {
636 3 : if (!map || !map->capacity) {
637 1 : return 0;
638 : }
639 2 : size_t const n = min_max_from(map, map->root, R);
640 2 : return n;
641 3 : }
642 :
643 : CCC_Handle_index
644 3021 : CCC_array_tree_map_next(
645 : CCC_Array_tree_map const *const map, CCC_Handle_index iterator
646 : ) {
647 3021 : if (!map || !iterator || !map->capacity) {
648 1 : return 0;
649 : }
650 3020 : size_t const n = next(map, iterator, INORDER);
651 3020 : return n;
652 3021 : }
653 :
654 : CCC_Handle_index
655 1296 : CCC_array_tree_map_reverse_next(
656 : CCC_Array_tree_map const *const map, CCC_Handle_index iterator
657 : ) {
658 1296 : if (!map || !iterator || !map->capacity) {
659 1 : return 0;
660 : }
661 1295 : size_t const n = next(map, iterator, INORDER_REVERSE);
662 1295 : return n;
663 1296 : }
664 :
665 : CCC_Handle_index
666 4295 : CCC_array_tree_map_end(CCC_Array_tree_map const *const) {
667 4295 : return 0;
668 : }
669 :
670 : CCC_Handle_index
671 4 : CCC_array_tree_map_reverse_end(CCC_Array_tree_map const *const) {
672 4 : return 0;
673 : }
674 :
675 : CCC_Result
676 16 : CCC_array_tree_map_reserve(
677 : CCC_Array_tree_map *const map,
678 : size_t const to_add,
679 : CCC_Allocator const *const allocator
680 : ) {
681 16 : if (!map || !to_add || !allocator || !allocator->allocate) {
682 3 : return CCC_RESULT_ARGUMENT_ERROR;
683 : }
684 13 : size_t const needed = map->count + to_add + (map->count == 0);
685 13 : if (needed <= map->capacity) {
686 1 : return CCC_RESULT_OK;
687 : }
688 12 : size_t const old_count = map->count;
689 12 : size_t old_cap = map->capacity;
690 12 : CCC_Result const r = resize(map, needed, allocator);
691 12 : if (r != CCC_RESULT_OK) {
692 1 : return r;
693 : }
694 11 : set_parity(map, 0, CCC_TRUE);
695 11 : if (!old_cap) {
696 11 : map->count = 1;
697 11 : }
698 11 : old_cap = old_count ? old_cap : 0;
699 11 : size_t const new_cap = map->capacity;
700 11 : size_t prev = 0;
701 11 : size_t i = new_cap;
702 1509 : while (i--) {
703 1509 : if (i <= old_cap) {
704 11 : break;
705 : }
706 1498 : node_at(map, i)->next_free = prev;
707 1498 : prev = i;
708 : }
709 11 : if (!map->free_list) {
710 11 : map->free_list = prev;
711 11 : }
712 11 : return CCC_RESULT_OK;
713 16 : }
714 :
715 : CCC_Result
716 7 : CCC_array_tree_map_copy(
717 : CCC_Array_tree_map *const destination,
718 : CCC_Array_tree_map const *const source,
719 : CCC_Allocator const *const allocator
720 : ) {
721 7 : if (!destination || !source || !allocator || source == destination
722 6 : || (destination->capacity < source->capacity && !allocator->allocate)) {
723 2 : return CCC_RESULT_ARGUMENT_ERROR;
724 : }
725 5 : if (!source->capacity) {
726 1 : return CCC_RESULT_OK;
727 : }
728 4 : if (destination->capacity < source->capacity) {
729 3 : CCC_Result const r = resize(destination, source->capacity, allocator);
730 3 : if (r != CCC_RESULT_OK) {
731 1 : return r;
732 : }
733 3 : } else {
734 : /* Might not be necessary but not worth finding out. Do every time. */
735 1 : destination->nodes = nodes_base_address(
736 1 : destination->sizeof_type, destination->data, destination->capacity
737 : );
738 1 : destination->parity = parities_base_address(
739 1 : destination->sizeof_type, destination->data, destination->capacity
740 : );
741 : }
742 3 : if (!destination->data || !source->data) {
743 1 : return CCC_RESULT_ARGUMENT_ERROR;
744 : }
745 2 : resize_struct_of_arrays(source, destination->data, destination->capacity);
746 2 : destination->free_list = source->free_list;
747 2 : destination->root = source->root;
748 2 : destination->count = source->count;
749 2 : destination->comparator = source->comparator;
750 2 : destination->sizeof_type = source->sizeof_type;
751 2 : destination->key_offset = source->key_offset;
752 2 : return CCC_RESULT_OK;
753 7 : }
754 :
755 : CCC_Result
756 2 : CCC_array_tree_map_clear(
757 : CCC_Array_tree_map *const map, CCC_Destructor const *const destructor
758 : ) {
759 2 : if (!map || !destructor) {
760 1 : return CCC_RESULT_ARGUMENT_ERROR;
761 : }
762 1 : if (destructor->destroy) {
763 1 : delete_nodes(map, destructor);
764 1 : }
765 1 : map->count = 1;
766 1 : map->root = 0;
767 1 : return CCC_RESULT_OK;
768 2 : }
769 :
770 : CCC_Result
771 21 : CCC_array_tree_map_clear_and_free(
772 : CCC_Array_tree_map *const map,
773 : CCC_Destructor const *const destructor,
774 : CCC_Allocator const *const allocator
775 : ) {
776 21 : if (!map || !destructor || !allocator || !allocator->allocate) {
777 3 : return CCC_RESULT_ARGUMENT_ERROR;
778 : }
779 18 : if (destructor->destroy) {
780 1 : delete_nodes(map, destructor);
781 1 : }
782 18 : map->root = 0;
783 18 : map->count = 0;
784 18 : map->capacity = 0;
785 72 : (void)allocator->allocate((CCC_Allocator_arguments){
786 18 : .input = map->data,
787 : .bytes = 0,
788 18 : .alignment = max_size_t(ALIGNOF_NODE, map->alignof_type),
789 18 : .context = allocator->context,
790 : });
791 18 : map->data = NULL;
792 18 : map->nodes = NULL;
793 18 : map->parity = NULL;
794 18 : return CCC_RESULT_OK;
795 21 : }
796 :
797 : CCC_Tribool
798 9906 : CCC_array_tree_map_validate(CCC_Array_tree_map const *const map) {
799 9906 : if (!map) {
800 1 : return CCC_TRIBOOL_ERROR;
801 : }
802 9905 : return validate(map);
803 9906 : }
804 :
805 : /*======================== Private Interface ==============================*/
806 :
807 : void
808 144 : CCC_private_array_tree_map_insert(
809 : struct CCC_Array_tree_map *const map,
810 : size_t const parent_i,
811 : CCC_Order const last_order,
812 : size_t const elem_i
813 : ) {
814 144 : insert(map, parent_i, last_order, elem_i);
815 144 : }
816 :
817 : struct CCC_Array_tree_map_handle
818 48 : CCC_private_array_tree_map_handle(
819 : struct CCC_Array_tree_map const *const map, void const *const key
820 : ) {
821 48 : return handle(map, key);
822 48 : }
823 :
824 : void *
825 2207 : CCC_private_array_tree_map_data_at(
826 : struct CCC_Array_tree_map const *const map, size_t const slot
827 : ) {
828 2207 : return data_at(map, slot);
829 : }
830 :
831 : void *
832 36 : CCC_private_array_tree_map_key_at(
833 : struct CCC_Array_tree_map const *const map, size_t const slot
834 : ) {
835 36 : return key_at(map, slot);
836 : }
837 :
838 : size_t
839 146 : CCC_private_array_tree_map_allocate_slot(
840 : struct CCC_Array_tree_map *const map, CCC_Allocator const *const allocator
841 : ) {
842 146 : return allocate_slot(map, allocator);
843 : }
844 :
845 : /*========================== Static Helpers ==============================*/
846 :
847 : static size_t
848 10316 : maybe_allocate_insert(
849 : struct CCC_Array_tree_map *const map,
850 : size_t const parent,
851 : CCC_Order const last_order,
852 : void const *const user_type,
853 : CCC_Allocator const *const allocator
854 : ) {
855 10316 : size_t const node = allocate_slot(map, allocator);
856 10316 : if (!node) {
857 8 : return 0;
858 : }
859 10308 : (void)memcpy(data_at(map, node), user_type, map->sizeof_type);
860 10308 : insert(map, parent, last_order, node);
861 10308 : return node;
862 10316 : }
863 :
864 : static size_t
865 10462 : allocate_slot(
866 : struct CCC_Array_tree_map *const map, CCC_Allocator const *const allocator
867 : ) {
868 : /* The end sentinel node will always be at 0. This also means once
869 : initialized the internal size for implementer is always at least 1. */
870 10462 : size_t const old_count = map->count;
871 10462 : size_t old_cap = map->capacity;
872 10462 : if (!old_count || old_count == old_cap) {
873 84 : assert(!map->free_list);
874 84 : if (old_count == old_cap) {
875 39 : if (resize(
876 39 : map, max_size_t(old_cap * 2, PARITY_BLOCK_BITS), allocator
877 : )
878 39 : != CCC_RESULT_OK) {
879 10 : return 0;
880 : }
881 29 : } else {
882 45 : map->nodes = nodes_base_address(
883 45 : map->sizeof_type, map->data, map->capacity
884 : );
885 45 : map->parity = parities_base_address(
886 45 : map->sizeof_type, map->data, map->capacity
887 : );
888 : }
889 74 : old_cap = old_count ? old_cap : 1;
890 74 : size_t const new_cap = map->capacity;
891 74 : size_t prev = 0;
892 16970 : for (size_t i = new_cap - 1; i >= old_cap; prev = i, --i) {
893 16896 : node_at(map, i)->next_free = prev;
894 16896 : }
895 74 : map->free_list = prev;
896 74 : map->count = max_size_t(old_count, 1);
897 74 : set_parity(map, 0, CCC_TRUE);
898 74 : }
899 10452 : assert(map->free_list);
900 10452 : ++map->count;
901 10452 : size_t const slot = map->free_list;
902 10452 : map->free_list = node_at(map, slot)->next_free;
903 10452 : return slot;
904 10462 : }
905 :
906 : static CCC_Result
907 54 : resize(
908 : struct CCC_Array_tree_map *const map,
909 : size_t const new_capacity,
910 : CCC_Allocator const *const allocator
911 : ) {
912 54 : if (!allocator->allocate) {
913 9 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
914 : }
915 180 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
916 : .input = NULL,
917 45 : .bytes = total_bytes(map->sizeof_type, new_capacity),
918 45 : .alignment = max_size_t(ALIGNOF_NODE, map->alignof_type),
919 45 : .context = allocator->context,
920 : });
921 45 : if (!new_data) {
922 3 : return CCC_RESULT_ALLOCATOR_ERROR;
923 : }
924 42 : resize_struct_of_arrays(map, new_data, new_capacity);
925 42 : map->nodes = nodes_base_address(map->sizeof_type, new_data, new_capacity);
926 42 : map->parity
927 84 : = parities_base_address(map->sizeof_type, new_data, new_capacity);
928 168 : allocator->allocate((CCC_Allocator_arguments){
929 42 : .input = map->data,
930 : .bytes = 0,
931 42 : .alignment = max_size_t(ALIGNOF_NODE, map->alignof_type),
932 42 : .context = allocator->context,
933 : });
934 42 : map->data = new_data;
935 42 : map->capacity = new_capacity;
936 42 : return CCC_RESULT_OK;
937 54 : }
938 :
939 : static void
940 10452 : insert(
941 : struct CCC_Array_tree_map *const map,
942 : size_t const parent_i,
943 : CCC_Order const last_order,
944 : size_t const elem_i
945 : ) {
946 10452 : struct CCC_Array_tree_map_node *elem = node_at(map, elem_i);
947 10452 : init_node(map, elem_i);
948 10452 : if (map->count == INSERT_ROOT_COUNT) {
949 61 : map->root = elem_i;
950 61 : return;
951 : }
952 10391 : assert(last_order == CCC_ORDER_GREATER || last_order == CCC_ORDER_LESSER);
953 10391 : CCC_Tribool rank_rule_break = CCC_FALSE;
954 10391 : if (parent_i) {
955 10391 : struct CCC_Array_tree_map_node *parent = node_at(map, parent_i);
956 10391 : rank_rule_break = !parent->branch[L] && !parent->branch[R];
957 10391 : parent->branch[CCC_ORDER_GREATER == last_order] = elem_i;
958 10391 : }
959 10391 : elem->parent = parent_i;
960 10391 : if (rank_rule_break) {
961 9390 : insert_fixup(map, parent_i, elem_i);
962 9390 : }
963 10452 : }
964 :
965 : static struct CCC_Array_tree_map_handle
966 13090 : handle(struct CCC_Array_tree_map const *const map, void const *const key) {
967 13090 : struct Query const q = find(map, key);
968 13090 : if (CCC_ORDER_EQUAL == q.last_order) {
969 30056 : return (struct CCC_Array_tree_map_handle){
970 7514 : .map = (struct CCC_Array_tree_map *)map,
971 7514 : .last_order = q.last_order,
972 7514 : .index = q.found,
973 : .status = CCC_ENTRY_OCCUPIED,
974 : };
975 : }
976 22304 : return (struct CCC_Array_tree_map_handle){
977 5576 : .map = (struct CCC_Array_tree_map *)map,
978 5576 : .last_order = q.last_order,
979 5576 : .index = q.parent,
980 : .status = CCC_ENTRY_NO_UNWRAP | CCC_ENTRY_VACANT,
981 : };
982 13090 : }
983 :
984 : static struct Query
985 23311 : find(struct CCC_Array_tree_map const *const map, void const *const key) {
986 23311 : size_t parent = 0;
987 23311 : struct Query q = {
988 : .last_order = CCC_ORDER_ERROR,
989 23311 : .found = map->root,
990 : };
991 199091 : while (q.found) {
992 188522 : q.last_order = order_nodes(map, key, q.found);
993 188522 : if (CCC_ORDER_EQUAL == q.last_order) {
994 12742 : return q;
995 : }
996 175780 : parent = q.found;
997 175780 : q.found = branch_index(map, q.found, CCC_ORDER_GREATER == q.last_order);
998 : }
999 : /* Type punning here OK as both union members have same type and size. */
1000 10569 : q.parent = parent;
1001 10569 : return q;
1002 23311 : }
1003 :
1004 : static size_t
1005 4322 : next(
1006 : struct CCC_Array_tree_map const *const map,
1007 : size_t n,
1008 : enum Link const traversal
1009 : ) {
1010 4322 : if (!n) {
1011 0 : return 0;
1012 : }
1013 4322 : assert(!parent_index(map, map->root));
1014 4322 : if (branch_index(map, n, traversal)) {
1015 5644 : for (n = branch_index(map, n, traversal);
1016 5644 : branch_index(map, n, !traversal);
1017 3321 : n = branch_index(map, n, !traversal)) {}
1018 2323 : return n;
1019 : }
1020 1999 : size_t p = parent_index(map, n);
1021 3859 : for (; p && branch_index(map, p, !traversal) != n;
1022 1860 : n = p, p = parent_index(map, p)) {}
1023 1999 : return p;
1024 4322 : }
1025 :
1026 : static CCC_Handle_range
1027 10 : equal_range(
1028 : struct CCC_Array_tree_map const *const map,
1029 : void const *const begin_key,
1030 : void const *const end_key,
1031 : enum Link const traversal
1032 : ) {
1033 10 : if (CCC_array_tree_map_is_empty(map)) {
1034 2 : return (CCC_Handle_range){};
1035 : }
1036 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
1037 8 : struct Query b = find(map, begin_key);
1038 8 : if (b.last_order == les_or_grt[traversal]) {
1039 2 : b.found = next(map, b.found, traversal);
1040 2 : }
1041 8 : struct Query e = find(map, end_key);
1042 8 : if (e.last_order != les_or_grt[!traversal]) {
1043 5 : e.found = next(map, e.found, traversal);
1044 5 : }
1045 24 : return (CCC_Handle_range){
1046 8 : .begin = b.found,
1047 8 : .end = e.found,
1048 : };
1049 10 : }
1050 :
1051 : static size_t
1052 1082 : min_max_from(
1053 : struct CCC_Array_tree_map const *const map,
1054 : size_t start,
1055 : enum Link const dir
1056 : ) {
1057 1082 : if (!start) {
1058 1 : return 0;
1059 : }
1060 3554 : for (; branch_index(map, start, dir);
1061 2473 : start = branch_index(map, start, dir)) {}
1062 1081 : return start;
1063 1082 : }
1064 :
1065 : /** Deletes all nodes in the tree by calling destructor function on them in
1066 : linear time and constant space. This function modifies nodes as it deletes the
1067 : tree elements. Assumes the destructor function is non-null.
1068 :
1069 : This function does not update any count or capacity fields of the map, it
1070 : simply calls the destructor on each node and removes the nodes references to
1071 : other tree elements. */
1072 : static void
1073 2 : delete_nodes(
1074 : struct CCC_Array_tree_map const *const map,
1075 : CCC_Destructor const *const destructor
1076 : ) {
1077 2 : size_t node = map->root;
1078 28 : while (node) {
1079 26 : struct CCC_Array_tree_map_node *const e = node_at(map, node);
1080 26 : if (e->branch[L]) {
1081 11 : size_t const left = e->branch[L];
1082 11 : e->branch[L] = node_at(map, left)->branch[R];
1083 11 : node_at(map, left)->branch[R] = node;
1084 11 : node = left;
1085 : continue;
1086 11 : }
1087 15 : size_t const next = e->branch[R];
1088 15 : e->branch[L] = e->branch[R] = 0;
1089 15 : e->parent = 0;
1090 45 : destructor->destroy((CCC_Arguments){
1091 15 : .type = data_at(map, node),
1092 15 : .context = destructor->context,
1093 : });
1094 15 : node = next;
1095 26 : }
1096 2 : }
1097 :
1098 : static inline CCC_Order
1099 7041103 : order_nodes(
1100 : struct CCC_Array_tree_map const *const map,
1101 : void const *const key,
1102 : size_t const node
1103 : ) {
1104 28164412 : return map->comparator.compare((CCC_Key_comparator_arguments){
1105 7041103 : .key_left = key,
1106 7041103 : .type_right = data_at(map, node),
1107 7041103 : .context = map->comparator.context,
1108 : });
1109 : }
1110 :
1111 : /** Calculates the number of bytes needed for user data INCLUDING any bytes we
1112 : need to add to the end of the array such that the following nodes array starts
1113 : on an aligned byte boundary given the alignment requirements of a node. This
1114 : means the value returned from this function may or may not be slightly larger
1115 : then the raw size of just user elements if rounding up must occur. */
1116 : static inline size_t
1117 351 : data_bytes(size_t const sizeof_type, size_t const capacity) {
1118 351 : return ((sizeof_type * capacity) + ALIGNOF_NODE - 1) & ~(ALIGNOF_NODE - 1);
1119 : }
1120 :
1121 : /** Calculates the number of bytes needed for the nodes array INCLUDING any
1122 : bytes we need to add to the end of the array such that the following parity bit
1123 : array starts on an aligned byte boundary given the alignment requirements of
1124 : a parity block. This means the value returned from this function may or may not
1125 : be slightly larger then the raw size of just the nodes array if rounding up must
1126 : occur. */
1127 : static inline size_t
1128 211 : nodes_bytes(size_t const capacity) {
1129 422 : return ((SIZEOF_NODE * capacity) + ALIGNOF_PARITY - 1)
1130 211 : & ~(ALIGNOF_PARITY - 1);
1131 : }
1132 :
1133 : /** Calculates the number of bytes needed for the parity block bit array. No
1134 : rounding up or alignment concerns need apply because this is the last array
1135 : in the allocation. */
1136 : static inline size_t
1137 71 : parities_bytes(size_t const capacity) {
1138 71 : return SIZEOF_PARITY * block_count(capacity);
1139 : }
1140 :
1141 : /** Calculates the number of bytes needed for all arrays in the Struct of Arrays
1142 : map design INCLUDING any extra padding bytes that need to be added between the
1143 : data and node arrays and the node and parity arrays. Padding might be needed if
1144 : the alignment of the type in next array that follows a preceding array is
1145 : different from the preceding array. In that case it is the preceding array's
1146 : responsibility to add padding bytes to its end such that the next array begins
1147 : on an aligned byte boundary for its own type. This means that the bytes returned
1148 : by this function may be greater than summing the (sizeof(type) * capacity) for
1149 : each array in the conceptual struct. */
1150 : static inline size_t
1151 45 : total_bytes(size_t const sizeof_type, size_t const capacity) {
1152 90 : return data_bytes(sizeof_type, capacity) + nodes_bytes(capacity)
1153 45 : + parities_bytes(capacity);
1154 : }
1155 :
1156 : /** Returns the base of the node array relative to the data base pointer. This
1157 : positions is guaranteed to be the first aligned byte given the alignment of the
1158 : node type after the data array. The data array has added any necessary padding
1159 : after it to ensure that the base of the node array is aligned for its type. */
1160 : static inline struct CCC_Array_tree_map_node *
1161 140 : nodes_base_address(
1162 : size_t const sizeof_type, void const *const data, size_t const capacity
1163 : ) {
1164 280 : return (struct CCC_Array_tree_map_node *)((char *)data
1165 140 : + data_bytes(
1166 140 : sizeof_type, capacity
1167 : ));
1168 : }
1169 :
1170 : /** Returns the base of the parity array relative to the data base pointer. This
1171 : positions is guaranteed to be the first aligned byte given the alignment of the
1172 : parity block type after the data and node arrays. The node array has added any
1173 : necessary padding after it to ensure that the base of the parity block array is
1174 : aligned for its type. */
1175 : static inline Parity_block *
1176 140 : parities_base_address(
1177 : size_t const sizeof_type, void const *const data, size_t const capacity
1178 : ) {
1179 280 : return (Parity_block *)((char *)data + data_bytes(sizeof_type, capacity)
1180 140 : + nodes_bytes(capacity));
1181 : }
1182 :
1183 : /** Copies over the Struct of Arrays contained within the one contiguous
1184 : allocation of the map to the new memory provided. Assumes the new_data pointer
1185 : points to the base of an allocation that has been allocated with sufficient
1186 : bytes to support the user data, nodes, and parity arrays for the provided new
1187 : capacity. */
1188 : static inline void
1189 44 : resize_struct_of_arrays(
1190 : struct CCC_Array_tree_map const *const source,
1191 : void *const destination_data_base,
1192 : size_t const destination_capacity
1193 : ) {
1194 44 : if (!source->data) {
1195 18 : return;
1196 : }
1197 26 : assert(destination_capacity >= source->capacity);
1198 26 : size_t const sizeof_type = source->sizeof_type;
1199 : /* Each section of the allocation "grows" when we re-size so one copy would
1200 : not work. Instead each component is copied over allowing each to grow. */
1201 26 : (void)memcpy(
1202 26 : destination_data_base,
1203 26 : source->data,
1204 26 : data_bytes(sizeof_type, source->capacity)
1205 : );
1206 26 : (void)memcpy(
1207 26 : nodes_base_address(
1208 26 : sizeof_type, destination_data_base, destination_capacity
1209 : ),
1210 26 : nodes_base_address(sizeof_type, source->data, source->capacity),
1211 26 : nodes_bytes(source->capacity)
1212 : );
1213 26 : (void)memcpy(
1214 26 : parities_base_address(
1215 26 : sizeof_type, destination_data_base, destination_capacity
1216 : ),
1217 26 : parities_base_address(sizeof_type, source->data, source->capacity),
1218 26 : parities_bytes(source->capacity)
1219 : );
1220 70 : }
1221 :
1222 : static inline void
1223 10452 : init_node(struct CCC_Array_tree_map const *const map, size_t const node) {
1224 10452 : set_parity(map, node, CCC_FALSE);
1225 10452 : struct CCC_Array_tree_map_node *const e = node_at(map, node);
1226 10452 : e->branch[L] = e->branch[R] = e->parent = 0;
1227 10452 : }
1228 :
1229 : static inline void
1230 834 : swap(void *const temp, size_t const sizeof_type, void *const a, void *const b) {
1231 834 : if (a == b || !a || !b) {
1232 0 : return;
1233 : }
1234 834 : (void)memcpy(temp, a, sizeof_type);
1235 834 : (void)memcpy(a, b, sizeof_type);
1236 834 : (void)memcpy(b, temp, sizeof_type);
1237 1668 : }
1238 :
1239 : static inline struct CCC_Array_tree_map_node *
1240 29408597 : node_at(struct CCC_Array_tree_map const *const map, size_t const i) {
1241 29408597 : return &map->nodes[i];
1242 : }
1243 :
1244 : static inline void *
1245 13930156 : data_at(struct CCC_Array_tree_map const *const map, size_t const i) {
1246 13930156 : return (char *)map->data + (map->sizeof_type * i);
1247 : }
1248 :
1249 : static inline Parity_block *
1250 182601 : block_at(struct CCC_Array_tree_map const *const map, size_t const i) {
1251 : static_assert(
1252 : (typeof(i))~((typeof(i))0) >= (typeof(i))0,
1253 : "shifting to avoid division with power of 2 divisor is only "
1254 : "defined for unsigned types"
1255 : );
1256 182601 : return &map->parity[i >> PARITY_BLOCK_BITS_LOG2];
1257 : }
1258 :
1259 : static inline Parity_block
1260 182601 : bit_on(size_t const i) {
1261 : static_assert(
1262 : (PARITY_BLOCK_BITS & (PARITY_BLOCK_BITS - 1)) == 0,
1263 : "the number of bits in a block is always a power of two, "
1264 : "avoiding modulo operations."
1265 : );
1266 182601 : return ((Parity_block)1) << (i & (PARITY_BLOCK_BITS - 1));
1267 : }
1268 :
1269 : static inline size_t
1270 21282958 : branch_index(
1271 : struct CCC_Array_tree_map const *const map,
1272 : size_t const parent,
1273 : enum Link const dir
1274 : ) {
1275 21282958 : return node_at(map, parent)->branch[dir];
1276 : }
1277 :
1278 : static inline size_t
1279 3571461 : parent_index(struct CCC_Array_tree_map const *const map, size_t const child) {
1280 3571461 : return node_at(map, child)->parent;
1281 : }
1282 :
1283 : static inline CCC_Tribool
1284 141740 : parity(struct CCC_Array_tree_map const *const map, size_t const node) {
1285 141740 : return (*block_at(map, node) & bit_on(node)) != 0;
1286 : }
1287 :
1288 : static inline void
1289 11603 : set_parity(
1290 : struct CCC_Array_tree_map const *const map,
1291 : size_t const node,
1292 : CCC_Tribool const status
1293 : ) {
1294 11603 : if (status) {
1295 472 : *block_at(map, node) |= bit_on(node);
1296 472 : } else {
1297 11131 : *block_at(map, node) &= ~bit_on(node);
1298 : }
1299 11603 : }
1300 :
1301 : static inline size_t
1302 71 : block_count(size_t const node_count) {
1303 : static_assert(
1304 : (typeof(node_count))~((typeof(node_count))0) >= (typeof(node_count))0,
1305 : "shifting to avoid division with power of 2 divisor is only "
1306 : "defined for unsigned types"
1307 : );
1308 71 : return (node_count + (PARITY_BLOCK_BITS - 1)) >> PARITY_BLOCK_BITS_LOG2;
1309 : }
1310 :
1311 : static inline size_t *
1312 3129 : branch_pointer(
1313 : struct CCC_Array_tree_map const *t,
1314 : size_t const node,
1315 : enum Link const branch
1316 : ) {
1317 3129 : return &node_at(t, node)->branch[branch];
1318 : }
1319 :
1320 : static inline size_t *
1321 12965 : parent_pointer(struct CCC_Array_tree_map const *t, size_t const node) {
1322 :
1323 12965 : return &node_at(t, node)->parent;
1324 : }
1325 :
1326 : static inline void *
1327 6852617 : key_at(struct CCC_Array_tree_map const *const map, size_t const i) {
1328 6852617 : return (char *)data_at(map, i) + map->key_offset;
1329 : }
1330 :
1331 : static void *
1332 8126 : key_in_slot(struct CCC_Array_tree_map const *t, void const *const user_struct) {
1333 8126 : return (char *)user_struct + t->key_offset;
1334 : }
1335 :
1336 : /*======================= WAVL Tree Maintenance =========================*/
1337 :
1338 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
1339 : Sen, and Tarjan (Fig. 2. pg 7). Assumes x's parent z is not null. */
1340 : static void
1341 9390 : insert_fixup(struct CCC_Array_tree_map *const map, size_t z, size_t x) {
1342 9390 : assert(z);
1343 9390 : do {
1344 18562 : promote(map, z);
1345 18562 : x = z;
1346 18562 : z = parent_index(map, z);
1347 18562 : if (!z) {
1348 271 : return;
1349 : }
1350 18291 : } while (is_01_parent(map, x, z, sibling_of(map, x)));
1351 :
1352 9119 : if (!is_02_parent(map, x, z, sibling_of(map, x))) {
1353 3601 : return;
1354 : }
1355 5518 : assert(x);
1356 5518 : assert(is_0_child(map, z, x));
1357 5518 : enum Link const p_to_x_dir = branch_index(map, z, R) == x;
1358 5518 : size_t const y = branch_index(map, x, !p_to_x_dir);
1359 5518 : if (!y || is_2_child(map, z, y)) {
1360 4656 : rotate(map, z, x, y, !p_to_x_dir);
1361 4656 : demote(map, z);
1362 4656 : } else {
1363 862 : assert(is_1_child(map, z, y));
1364 862 : double_rotate(map, z, x, y, p_to_x_dir);
1365 862 : promote(map, y);
1366 862 : demote(map, x);
1367 862 : demote(map, z);
1368 : }
1369 14908 : }
1370 :
1371 : static size_t
1372 2348 : remove_fixup(struct CCC_Array_tree_map *const map, size_t const remove) {
1373 2348 : size_t y = 0;
1374 2348 : size_t x = 0;
1375 2348 : size_t p = 0;
1376 2348 : CCC_Tribool two_child = CCC_FALSE;
1377 2348 : if (!branch_index(map, remove, R) || !branch_index(map, remove, L)) {
1378 1282 : y = remove;
1379 1282 : p = parent_index(map, y);
1380 1282 : x = branch_index(map, y, !branch_index(map, y, L));
1381 1282 : *parent_pointer(map, x) = parent_index(map, y);
1382 1282 : if (!p) {
1383 18 : map->root = x;
1384 18 : } else {
1385 1264 : *branch_pointer(map, p, branch_index(map, p, R) == y) = x;
1386 : }
1387 1282 : two_child = is_2_child(map, p, y);
1388 1282 : } else {
1389 1066 : y = min_max_from(map, branch_index(map, remove, R), L);
1390 1066 : p = parent_index(map, y);
1391 1066 : x = branch_index(map, y, !branch_index(map, y, L));
1392 1066 : *parent_pointer(map, x) = parent_index(map, y);
1393 :
1394 : /* Save if check and improve readability by assuming this is true. */
1395 1066 : assert(p);
1396 :
1397 1066 : two_child = is_2_child(map, p, y);
1398 1066 : *branch_pointer(map, p, branch_index(map, p, R) == y) = x;
1399 1066 : transplant(map, remove, y);
1400 1066 : if (remove == p) {
1401 277 : p = y;
1402 277 : }
1403 : }
1404 :
1405 2348 : if (p) {
1406 2330 : if (two_child) {
1407 1434 : assert(p);
1408 1434 : rebalance_3_child(map, p, x);
1409 2330 : } else if (!x && branch_index(map, p, L) == branch_index(map, p, R)) {
1410 340 : assert(p);
1411 680 : CCC_Tribool const demote_makes_3_child
1412 340 : = is_2_child(map, parent_index(map, p), p);
1413 340 : demote(map, p);
1414 340 : if (demote_makes_3_child) {
1415 142 : rebalance_3_child(map, parent_index(map, p), p);
1416 142 : }
1417 340 : }
1418 2330 : assert(!is_leaf(map, p) || !parity(map, p));
1419 2330 : }
1420 2348 : node_at(map, remove)->next_free = map->free_list;
1421 2348 : map->free_list = remove;
1422 2348 : --map->count;
1423 4696 : return remove;
1424 2348 : }
1425 :
1426 : static void
1427 1066 : transplant(
1428 : struct CCC_Array_tree_map *const map,
1429 : size_t const remove,
1430 : size_t const replacement
1431 : ) {
1432 1066 : assert(remove);
1433 1066 : assert(replacement);
1434 1066 : *parent_pointer(map, replacement) = parent_index(map, remove);
1435 1066 : if (!parent_index(map, remove)) {
1436 267 : map->root = replacement;
1437 267 : } else {
1438 799 : size_t const p = parent_index(map, remove);
1439 799 : *branch_pointer(map, p, branch_index(map, p, R) == remove)
1440 1598 : = replacement;
1441 799 : }
1442 1066 : struct CCC_Array_tree_map_node *const remove_r = node_at(map, remove);
1443 1066 : struct CCC_Array_tree_map_node *const replace_r = node_at(map, replacement);
1444 1066 : *parent_pointer(map, remove_r->branch[R]) = replacement;
1445 1066 : *parent_pointer(map, remove_r->branch[L]) = replacement;
1446 1066 : replace_r->branch[R] = remove_r->branch[R];
1447 1066 : replace_r->branch[L] = remove_r->branch[L];
1448 1066 : set_parity(map, replacement, parity(map, remove));
1449 1066 : }
1450 :
1451 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
1452 : Sen, and Tarjan (Fig. 3. pg 8). */
1453 : static void
1454 1576 : rebalance_3_child(struct CCC_Array_tree_map *const map, size_t z, size_t x) {
1455 1576 : CCC_Tribool made_3_child = CCC_TRUE;
1456 2935 : while (z && made_3_child) {
1457 2155 : assert(branch_index(map, z, L) == x || branch_index(map, z, R) == x);
1458 2155 : size_t const g = parent_index(map, z);
1459 2155 : size_t const y = branch_index(map, z, branch_index(map, z, L) == x);
1460 2155 : made_3_child = g && is_2_child(map, g, z);
1461 2155 : if (is_2_child(map, z, y)) {
1462 1191 : demote(map, z);
1463 2155 : } else if (y
1464 964 : && is_22_parent(
1465 964 : map, branch_index(map, y, L), y, branch_index(map, y, R)
1466 : )) {
1467 168 : demote(map, z);
1468 168 : demote(map, y);
1469 964 : } else if (y) {
1470 : /* p(x) is 1,3, y is not a 2,2 parent, and x is 3-child.*/
1471 796 : assert(is_1_child(map, z, y));
1472 796 : assert(is_3_child(map, z, x));
1473 796 : assert(!is_2_child(map, z, y));
1474 796 : assert(!is_22_parent(
1475 796 : map, branch_index(map, y, L), y, branch_index(map, y, R)
1476 : ));
1477 796 : enum Link const z_to_x_dir = branch_index(map, z, R) == x;
1478 796 : size_t const w = branch_index(map, y, !z_to_x_dir);
1479 796 : if (is_1_child(map, y, w)) {
1480 553 : rotate(map, z, y, branch_index(map, y, z_to_x_dir), z_to_x_dir);
1481 553 : promote(map, y);
1482 553 : demote(map, z);
1483 553 : if (is_leaf(map, z)) {
1484 144 : demote(map, z);
1485 144 : }
1486 553 : } else {
1487 : /* w is a 2-child and v will be a 1-child. */
1488 243 : size_t const v = branch_index(map, y, z_to_x_dir);
1489 243 : assert(is_2_child(map, y, w));
1490 243 : assert(is_1_child(map, y, v));
1491 243 : double_rotate(map, z, y, v, !z_to_x_dir);
1492 243 : double_promote(map, v);
1493 243 : demote(map, y);
1494 243 : double_demote(map, z);
1495 : /* Optional "Rebalancing with Promotion," defined as follows:
1496 : if node z is a non-leaf 1,1 node, we promote it;
1497 : otherwise, if y is a non-leaf 1,1 node, we promote it.
1498 : (See Figure 4.) (Haeupler et. al. 2014, 17).
1499 : This reduces constants in some of theorems mentioned in the
1500 : paper but may not be worth doing. Rotations stay at 2 worst
1501 : case. Should revisit after more performance testing. */
1502 243 : if (!is_leaf(map, z)
1503 243 : && is_11_parent(
1504 110 : map, branch_index(map, z, L), z, branch_index(map, z, R)
1505 : )) {
1506 62 : promote(map, z);
1507 243 : } else if (!is_leaf(map, y)
1508 181 : && is_11_parent(
1509 48 : map,
1510 48 : branch_index(map, y, L),
1511 48 : y,
1512 48 : branch_index(map, y, R)
1513 : )) {
1514 32 : promote(map, y);
1515 32 : }
1516 243 : }
1517 : /* Returning here confirms O(1) rotations for re-balance. */
1518 : return;
1519 796 : }
1520 1359 : x = z;
1521 1359 : z = g;
1522 2155 : }
1523 1576 : }
1524 :
1525 : /** A single rotation is symmetric. Here is the right case. Lowercase are nodes
1526 : and uppercase are arbitrary subtrees.
1527 : z x
1528 : ╭──┴──╮ ╭──┴──╮
1529 : x C A z
1530 : ╭─┴─╮ -> ╭─┴─╮
1531 : A y y C
1532 : │ │
1533 : B B
1534 : Using a link allows both cases to be coded at once. */
1535 : static void
1536 5209 : rotate(
1537 : struct CCC_Array_tree_map *const map,
1538 : size_t const z,
1539 : size_t const x,
1540 : size_t const y,
1541 : enum Link const dir
1542 : ) {
1543 5209 : assert(z);
1544 5209 : struct CCC_Array_tree_map_node *const z_r = node_at(map, z);
1545 5209 : struct CCC_Array_tree_map_node *const x_r = node_at(map, x);
1546 5209 : size_t const g = parent_index(map, z);
1547 5209 : x_r->parent = g;
1548 5209 : if (!g) {
1549 163 : map->root = x;
1550 163 : } else {
1551 5046 : struct CCC_Array_tree_map_node *const g_r = node_at(map, g);
1552 5046 : g_r->branch[g_r->branch[R] == z] = x;
1553 5046 : }
1554 5209 : x_r->branch[dir] = z;
1555 5209 : z_r->parent = x;
1556 5209 : z_r->branch[!dir] = y;
1557 5209 : *parent_pointer(map, y) = z;
1558 5209 : }
1559 :
1560 : /** A double rotation shouldn't actually be two calls to rotate because that
1561 : would invoke pointless memory writes. Here is an example of double right.
1562 : Lowercase are nodes and uppercase are arbitrary subtrees.
1563 :
1564 : z y
1565 : ╭──┴──╮ ╭──┴──╮
1566 : x D x z
1567 : ╭─┴─╮ -> ╭─┴─╮ ╭─┴─╮
1568 : A y A B C D
1569 : ╭─┴─╮
1570 : B C
1571 :
1572 : Taking a link as input allows us to code both symmetrical cases at once. */
1573 : static void
1574 1105 : double_rotate(
1575 : struct CCC_Array_tree_map *const map,
1576 : size_t const z,
1577 : size_t const x,
1578 : size_t const y,
1579 : enum Link const dir
1580 : ) {
1581 1105 : assert(z && x && y);
1582 1105 : struct CCC_Array_tree_map_node *const z_r = node_at(map, z);
1583 1105 : struct CCC_Array_tree_map_node *const x_r = node_at(map, x);
1584 1105 : struct CCC_Array_tree_map_node *const y_r = node_at(map, y);
1585 1105 : size_t const g = z_r->parent;
1586 1105 : y_r->parent = g;
1587 1105 : if (!g) {
1588 6 : map->root = y;
1589 6 : } else {
1590 1099 : struct CCC_Array_tree_map_node *const g_r = node_at(map, g);
1591 1099 : g_r->branch[g_r->branch[R] == z] = y;
1592 1099 : }
1593 1105 : x_r->branch[!dir] = y_r->branch[dir];
1594 1105 : *parent_pointer(map, y_r->branch[dir]) = x;
1595 1105 : y_r->branch[dir] = x;
1596 1105 : x_r->parent = y;
1597 :
1598 1105 : z_r->branch[dir] = y_r->branch[!dir];
1599 1105 : *parent_pointer(map, y_r->branch[!dir]) = z;
1600 1105 : y_r->branch[!dir] = z;
1601 1105 : z_r->parent = y;
1602 1105 : }
1603 :
1604 : /** Returns true for rank difference 0 (rule break) between the parent and node.
1605 : p
1606 : 0╭─╯
1607 : x */
1608 : [[maybe_unused]] static inline CCC_Tribool
1609 5518 : is_0_child(
1610 : struct CCC_Array_tree_map const *const map, size_t const p, size_t const x
1611 : ) {
1612 5518 : return p && parity(map, p) == parity(map, x);
1613 : }
1614 :
1615 : /** Returns true for rank difference 1 between the parent and node.
1616 : p
1617 : 1╭─╯
1618 : x */
1619 : static inline CCC_Tribool
1620 2697 : is_1_child(
1621 : struct CCC_Array_tree_map const *const map, size_t const p, size_t const x
1622 : ) {
1623 2697 : return p && parity(map, p) != parity(map, x);
1624 : }
1625 :
1626 : /** Returns true for rank difference 2 between the parent and node.
1627 : p
1628 : 2╭─╯
1629 : x */
1630 : static inline CCC_Tribool
1631 10410 : is_2_child(
1632 : struct CCC_Array_tree_map const *const map, size_t const p, size_t const x
1633 : ) {
1634 10410 : return p && parity(map, p) == parity(map, x);
1635 : }
1636 :
1637 : /** Returns true for rank difference 3 between the parent and node.
1638 : p
1639 : 3╭─╯
1640 : x */
1641 : [[maybe_unused]] static inline CCC_Tribool
1642 796 : is_3_child(
1643 : struct CCC_Array_tree_map const *const map, size_t const p, size_t const x
1644 : ) {
1645 796 : return p && parity(map, p) != parity(map, x);
1646 : }
1647 :
1648 : /** Returns true if a parent is a 0,1 or 1,0 node, which is not allowed. Either
1649 : child may be the sentinel node which has a parity of 1 and rank -1.
1650 : p
1651 : 0╭─┴─╮1
1652 : x y */
1653 : static inline CCC_Tribool
1654 18291 : is_01_parent(
1655 : struct CCC_Array_tree_map const *const map,
1656 : size_t const x,
1657 : size_t const p,
1658 : size_t const y
1659 : ) {
1660 18291 : assert(p);
1661 33513 : return (!parity(map, x) && !parity(map, p) && parity(map, y))
1662 18291 : || (parity(map, x) && parity(map, p) && !parity(map, y));
1663 : }
1664 :
1665 : /** Returns true if a parent is a 1,1 node. Either child may be the sentinel
1666 : node which has a parity of 1 and rank -1.
1667 : p
1668 : 1╭─┴─╮1
1669 : x y */
1670 : static inline CCC_Tribool
1671 158 : is_11_parent(
1672 : struct CCC_Array_tree_map const *const map,
1673 : size_t const x,
1674 : size_t const p,
1675 : size_t const y
1676 : ) {
1677 158 : assert(p);
1678 240 : return (!parity(map, x) && parity(map, p) && !parity(map, y))
1679 158 : || (parity(map, x) && !parity(map, p) && parity(map, y));
1680 : }
1681 :
1682 : /** Returns true if a parent is a 0,2 or 2,0 node, which is not allowed. Either
1683 : child may be the sentinel node which has a parity of 1 and rank -1.
1684 : p
1685 : 0╭─┴─╮2
1686 : x y */
1687 : static inline CCC_Tribool
1688 9119 : is_02_parent(
1689 : struct CCC_Array_tree_map const *const map,
1690 : size_t const x,
1691 : size_t const p,
1692 : size_t const y
1693 : ) {
1694 9119 : assert(p);
1695 14637 : return (parity(map, x) == parity(map, p))
1696 9119 : && (parity(map, p) == parity(map, y));
1697 : }
1698 :
1699 : /* Returns true if a parent is a 2,2 node, which is allowed. 2,2 nodes are
1700 : allowed in a WAVL tree but the absence of any 2,2 nodes is the exact equivalent
1701 : of a normal AVL tree which can occur if only insertions occur for a WAVL tree.
1702 : Either child may be the sentinel node which has a parity of 1 and rank -1.
1703 : p
1704 : 2╭─┴─╮2
1705 : x y */
1706 : static inline CCC_Tribool
1707 1760 : is_22_parent(
1708 : struct CCC_Array_tree_map const *const map,
1709 : size_t const x,
1710 : size_t const p,
1711 : size_t const y
1712 : ) {
1713 1760 : assert(p);
1714 2480 : return (parity(map, x) == parity(map, p))
1715 1760 : && (parity(map, p) == parity(map, y));
1716 : }
1717 :
1718 : static inline void
1719 29258 : promote(struct CCC_Array_tree_map const *const map, size_t const x) {
1720 29258 : if (x) {
1721 29258 : *block_at(map, x) ^= bit_on(x);
1722 29258 : }
1723 29258 : }
1724 :
1725 : static inline void
1726 9187 : demote(struct CCC_Array_tree_map const *const map, size_t const x) {
1727 9187 : promote(map, x);
1728 9187 : }
1729 :
1730 : /** Parity based ranks mean this is no-op but leave in case implementation ever
1731 : changes. Also, makes clear what sections of code are trying to do. */
1732 : static inline void
1733 243 : double_promote(struct CCC_Array_tree_map const *const, size_t const) {
1734 243 : }
1735 :
1736 : /** Parity based ranks mean this is no-op but leave in case implementation ever
1737 : changes. Also, makes clear what sections of code are trying to do. */
1738 : static inline void
1739 243 : double_demote(struct CCC_Array_tree_map const *const, size_t const) {
1740 243 : }
1741 :
1742 : static inline CCC_Tribool
1743 3307 : is_leaf(struct CCC_Array_tree_map const *const map, size_t const x) {
1744 3307 : return !branch_index(map, x, L) && !branch_index(map, x, R);
1745 : }
1746 :
1747 : static inline size_t
1748 27410 : sibling_of(struct CCC_Array_tree_map const *const map, size_t const x) {
1749 27410 : size_t const p = parent_index(map, x);
1750 27410 : assert(p);
1751 : /* We want the sibling so we need the truthy value to be opposite of x. */
1752 54820 : return node_at(map, p)->branch[branch_index(map, p, L) == x];
1753 27410 : }
1754 :
1755 : static inline size_t
1756 218 : max_size_t(size_t const a, size_t const b) {
1757 218 : return a > b ? a : b;
1758 : }
1759 :
1760 : /*=========================== Validation ===============================*/
1761 :
1762 : /* NOLINTBEGIN(*misc-no-recursion) */
1763 :
1764 : /** @internal */
1765 : struct Tree_range {
1766 : size_t low;
1767 : size_t root;
1768 : size_t high;
1769 : };
1770 :
1771 : static size_t
1772 7013564 : recursive_count(struct CCC_Array_tree_map const *const map, size_t const r) {
1773 7013564 : if (!r) {
1774 3511729 : return 0;
1775 : }
1776 7003670 : return 1 + recursive_count(map, branch_index(map, r, R))
1777 3501835 : + recursive_count(map, branch_index(map, r, L));
1778 7013564 : }
1779 :
1780 : static CCC_Tribool
1781 7013564 : are_subtrees_valid(
1782 : struct CCC_Array_tree_map const *t, struct Tree_range const r
1783 : ) {
1784 7013564 : if (!r.root) {
1785 3511729 : return CCC_TRUE;
1786 : }
1787 3501835 : if (r.low && order_nodes(t, key_at(t, r.low), r.root) != CCC_ORDER_LESSER) {
1788 0 : return CCC_FALSE;
1789 : }
1790 3501835 : if (r.high
1791 3501835 : && order_nodes(t, key_at(t, r.high), r.root) != CCC_ORDER_GREATER) {
1792 0 : return CCC_FALSE;
1793 : }
1794 7003670 : return are_subtrees_valid(
1795 3501835 : t,
1796 14007340 : (struct Tree_range){
1797 3501835 : .low = r.low,
1798 3501835 : .root = branch_index(t, r.root, L),
1799 3501835 : .high = r.root,
1800 : }
1801 : )
1802 3501835 : && are_subtrees_valid(
1803 3501835 : t,
1804 14007340 : (struct Tree_range){
1805 3501835 : .low = r.root,
1806 3501835 : .root = branch_index(t, r.root, R),
1807 3501835 : .high = r.high,
1808 : }
1809 : );
1810 7013564 : }
1811 :
1812 : static CCC_Tribool
1813 7013564 : is_storing_parent(
1814 : struct CCC_Array_tree_map const *const map,
1815 : size_t const p,
1816 : size_t const root
1817 : ) {
1818 7013564 : if (!root) {
1819 3511729 : return CCC_TRUE;
1820 : }
1821 3501835 : if (parent_index(map, root) != p) {
1822 0 : return CCC_FALSE;
1823 : }
1824 7003670 : return is_storing_parent(map, root, branch_index(map, root, L))
1825 3501835 : && is_storing_parent(map, root, branch_index(map, root, R));
1826 7013564 : }
1827 :
1828 : static CCC_Tribool
1829 9894 : is_free_list_valid(struct CCC_Array_tree_map const *const map) {
1830 9894 : if (!map->count) {
1831 0 : return CCC_TRUE;
1832 : }
1833 9894 : size_t list_count = 0;
1834 9894 : size_t cur_free_index = map->free_list;
1835 4436021 : while (cur_free_index && list_count < map->capacity) {
1836 4426127 : cur_free_index = node_at(map, cur_free_index)->next_free;
1837 4426127 : ++list_count;
1838 : }
1839 9894 : if (cur_free_index) {
1840 0 : return CCC_FALSE;
1841 : }
1842 9894 : if (list_count + map->count != map->capacity) {
1843 0 : return CCC_FALSE;
1844 : }
1845 9894 : return CCC_TRUE;
1846 9894 : }
1847 :
1848 : static inline CCC_Tribool
1849 9905 : validate(struct CCC_Array_tree_map const *const map) {
1850 9905 : if (!map->capacity) {
1851 7 : return CCC_TRUE;
1852 : }
1853 9898 : if (map->data && (!map->nodes || !map->parity)) {
1854 4 : return CCC_TRUE;
1855 : }
1856 9894 : if (!map->data) {
1857 0 : return CCC_TRUE;
1858 : }
1859 9894 : if (!map->count && !parity(map, 0)) {
1860 0 : return CCC_FALSE;
1861 : }
1862 9894 : if (!are_subtrees_valid(map, (struct Tree_range){.root = map->root})) {
1863 0 : return CCC_FALSE;
1864 : }
1865 9894 : size_t const size = recursive_count(map, map->root);
1866 9894 : if (size && size != map->count - 1) {
1867 0 : return CCC_FALSE;
1868 : }
1869 9894 : if (!is_storing_parent(map, 0, map->root)) {
1870 0 : return CCC_FALSE;
1871 : }
1872 9894 : if (!is_free_list_valid(map)) {
1873 0 : return CCC_FALSE;
1874 : }
1875 9894 : return CCC_TRUE;
1876 9905 : }
1877 :
1878 : /* NOLINTEND(*misc-no-recursion) */
1879 :
1880 : /* Below you will find the required license for code that inspired the
1881 : implementation of a WAVL tree in this repository for some map containers.
1882 :
1883 : The original repository can be found here:
1884 :
1885 : https://github.com/pvachon/wavl_tree
1886 :
1887 : The original implementation has be changed to eliminate left and right cases,
1888 : simplify deletion, and work within the C Container Collection memory framework.
1889 :
1890 : Redistribution and use in source and binary forms, with or without
1891 : modification, are permitted provided that the following conditions are met:
1892 :
1893 : 1. Redistributions of source code must retain the above copyright notice, this
1894 : list of conditions and the following disclaimer.
1895 :
1896 : 2. Redistributions in binary form must reproduce the above copyright notice,
1897 : this list of conditions and the following disclaimer in the documentation
1898 : and/or other materials provided with the distribution.
1899 :
1900 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1901 : AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1902 : IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1903 : DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
1904 : FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1905 : DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
1906 : SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1907 : CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
1908 : OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1909 : OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
|
