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