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