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