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 a realtime ordered map. The added
16 : realtime 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, pmapises O(lg N) search, insert, and remove as a true
21 : upper bound, inclusive. This is achieved through a Weak AVL (WAVL) tree
22 : that is derived from the following two sources.
23 :
24 : [1] Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan, 2014.
25 : Rank-Balanced Trees, J.ACM Transactions on Algorithms 11, 4, Article 0
26 : (June 2015), 24 pages.
27 : https://sidsen.azurewebsites.net//papers/rb-trees-talg.pdf
28 :
29 : [2] Phil Vachon (pvachon) https://github.com/pvachon/wavl_tree
30 : This implementation is heavily influential throughout. However there have
31 : been some major adjustments and simplifications. Namely, the allocation has
32 : been adjusted to accommodate this library's ability to be an allocating or
33 : non-allocating container. All left-right symmetric cases have been united
34 : into one and I chose to tackle rotations and deletions slightly differently,
35 : shortening the code significantly. A few other changes and improvements
36 : suggested by the authors of the original paper are implemented. See the required
37 : license at the bottom of the file for BSD-2-Clause compliance.
38 :
39 : Overall a WAVL tree is quite impressive for it's simplicity and purported
40 : improvements over AVL and Red-Black trees. The rank framework is intuitive
41 : and flexible in how it can be implemented.
42 :
43 : Excuse the mathematical variable naming in the WAVL implementation. It is
44 : easiest to check work against the research paper if we use the exact same names
45 : that appear in the paper. We could choose to describe the nodes in terms of
46 : their tree lineage but that changes with rotations so a symbolic representation
47 : is fine. */
48 : /** C23 provided headers. */
49 : #include <stddef.h>
50 :
51 : /** CCC provided headers. */
52 : #include "ccc/configuration.h" /* IWYU pragma: keep */
53 : #include "ccc/private/private_tree_map.h"
54 : #include "ccc/tree_map.h"
55 : #include "ccc/types.h"
56 :
57 : /** @internal */
58 : enum Link {
59 : L = 0,
60 : R,
61 : };
62 :
63 : #define INORDER R
64 : #define INORDER_REVERSE L
65 :
66 : /** @internal This will utilize safe type punning in C. Both union fields have
67 : the same type and when obtaining an entry we either have the desired element
68 : or its parent. Preserving the known parent is what makes the Entry Interface
69 : No further look ups are required for insertions, modification, or removal. */
70 : struct Query {
71 : CCC_Order last_order;
72 : union {
73 : struct CCC_Tree_map_node *found;
74 : struct CCC_Tree_map_node *parent;
75 : };
76 : };
77 :
78 : /*============================== Prototypes ==============================*/
79 :
80 : static void init_node(struct CCC_Tree_map *, struct CCC_Tree_map_node *);
81 : static CCC_Order order(
82 : struct CCC_Tree_map const *, void const *, struct CCC_Tree_map_node const *
83 : );
84 : static void *
85 : struct_base(struct CCC_Tree_map const *, struct CCC_Tree_map_node const *);
86 : static struct Query find(struct CCC_Tree_map const *, void const *);
87 : static void swap(void *, void *, void *, size_t);
88 : static void *maybe_allocate_insert(
89 : struct CCC_Tree_map *,
90 : struct CCC_Tree_map_node *,
91 : CCC_Order,
92 : struct CCC_Tree_map_node *,
93 : CCC_Allocator const *
94 : );
95 : static void *remove_fixup(struct CCC_Tree_map *, struct CCC_Tree_map_node *);
96 : static void insert_fixup(
97 : struct CCC_Tree_map *,
98 : struct CCC_Tree_map_node *,
99 : struct CCC_Tree_map_node *
100 : );
101 : static void transplant(
102 : struct CCC_Tree_map *,
103 : struct CCC_Tree_map_node *,
104 : struct CCC_Tree_map_node *
105 : );
106 : static CCC_Tribool parity(struct CCC_Tree_map_node const *);
107 : static void rebalance_3_child(
108 : struct CCC_Tree_map *,
109 : struct CCC_Tree_map_node *,
110 : struct CCC_Tree_map_node *
111 : );
112 : static CCC_Tribool
113 : is_0_child(struct CCC_Tree_map_node const *, struct CCC_Tree_map_node const *);
114 : static CCC_Tribool
115 : is_1_child(struct CCC_Tree_map_node const *, struct CCC_Tree_map_node const *);
116 : static CCC_Tribool
117 : is_2_child(struct CCC_Tree_map_node const *, struct CCC_Tree_map_node const *);
118 : static CCC_Tribool
119 : is_3_child(struct CCC_Tree_map_node const *, struct CCC_Tree_map_node const *);
120 : static CCC_Tribool is_01_parent(
121 : struct CCC_Tree_map_node const *,
122 : struct CCC_Tree_map_node const *,
123 : struct CCC_Tree_map_node const *
124 : );
125 : static CCC_Tribool is_11_parent(
126 : struct CCC_Tree_map_node const *,
127 : struct CCC_Tree_map_node const *,
128 : struct CCC_Tree_map_node const *
129 : );
130 : static CCC_Tribool is_02_parent(
131 : struct CCC_Tree_map_node const *,
132 : struct CCC_Tree_map_node const *,
133 : struct CCC_Tree_map_node const *
134 : );
135 : static CCC_Tribool is_22_parent(
136 : struct CCC_Tree_map_node const *,
137 : struct CCC_Tree_map_node const *,
138 : struct CCC_Tree_map_node const *
139 : );
140 : static CCC_Tribool is_leaf(struct CCC_Tree_map_node const *);
141 : static struct CCC_Tree_map_node *sibling_of(struct CCC_Tree_map_node const *);
142 : static void promote(struct CCC_Tree_map_node *);
143 : static void demote(struct CCC_Tree_map_node *);
144 : static void double_promote(struct CCC_Tree_map_node *);
145 : static void double_demote(struct CCC_Tree_map_node *);
146 :
147 : static void rotate(
148 : struct CCC_Tree_map *,
149 : struct CCC_Tree_map_node *,
150 : struct CCC_Tree_map_node *,
151 : struct CCC_Tree_map_node *,
152 : enum Link
153 : );
154 : static void double_rotate(
155 : struct CCC_Tree_map *,
156 : struct CCC_Tree_map_node *,
157 : struct CCC_Tree_map_node *,
158 : struct CCC_Tree_map_node *,
159 : enum Link
160 : );
161 : static CCC_Tribool validate(struct CCC_Tree_map const *);
162 : static struct CCC_Tree_map_node *
163 : next(struct CCC_Tree_map const *, struct CCC_Tree_map_node const *, enum Link);
164 : static struct CCC_Tree_map_node *
165 : min_max_from(struct CCC_Tree_map_node *, enum Link);
166 : static CCC_Range
167 : equal_range(struct CCC_Tree_map const *, void const *, void const *, enum Link);
168 : static struct CCC_Tree_map_entry
169 : entry(struct CCC_Tree_map const *, void const *);
170 : static void *insert(
171 : struct CCC_Tree_map *,
172 : struct CCC_Tree_map_node *,
173 : CCC_Order,
174 : struct CCC_Tree_map_node *
175 : );
176 : static void *
177 : key_from_node(struct CCC_Tree_map const *, struct CCC_Tree_map_node const *);
178 : static void *key_in_slot(struct CCC_Tree_map const *, void const *);
179 : static struct CCC_Tree_map_node *
180 : elem_in_slot(struct CCC_Tree_map const *, void const *);
181 :
182 : /*============================== Interface ==============================*/
183 :
184 : CCC_Tribool
185 102 : CCC_tree_map_contains(CCC_Tree_map const *const map, void const *const key) {
186 102 : if (!map || !key) {
187 2 : return CCC_TRIBOOL_ERROR;
188 : }
189 100 : return CCC_ORDER_EQUAL == find(map, key).last_order;
190 102 : }
191 :
192 : void *
193 17 : CCC_tree_map_get_key_value(
194 : CCC_Tree_map const *const map, void const *const key
195 : ) {
196 17 : if (!map || !key) {
197 2 : return NULL;
198 : }
199 15 : struct Query const q = find(map, key);
200 15 : return (CCC_ORDER_EQUAL == q.last_order) ? struct_base(map, q.found) : NULL;
201 17 : }
202 :
203 : CCC_Entry
204 1012 : CCC_tree_map_swap_entry(
205 : CCC_Tree_map *const map,
206 : CCC_Tree_map_node *const type_intruder,
207 : CCC_Tree_map_node *const temp_intruder,
208 : CCC_Allocator const *const allocator
209 : ) {
210 1012 : if (!map || !type_intruder || !allocator || !temp_intruder) {
211 4 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
212 : }
213 1008 : struct Query const q = find(map, key_from_node(map, type_intruder));
214 1008 : if (CCC_ORDER_EQUAL == q.last_order) {
215 87 : *type_intruder = *q.found;
216 87 : void *const found = struct_base(map, q.found);
217 87 : void *const any_struct = struct_base(map, type_intruder);
218 87 : void *const old_val = struct_base(map, temp_intruder);
219 87 : swap(old_val, found, any_struct, map->sizeof_type);
220 174 : type_intruder->branch[L] = type_intruder->branch[R]
221 174 : = type_intruder->parent = NULL;
222 174 : temp_intruder->branch[L] = temp_intruder->branch[R]
223 174 : = temp_intruder->parent = NULL;
224 174 : return (CCC_Entry){
225 87 : .type = old_val,
226 : .status = CCC_ENTRY_OCCUPIED,
227 : };
228 87 : }
229 921 : if (!maybe_allocate_insert(
230 921 : map, q.parent, q.last_order, type_intruder, allocator
231 : )) {
232 1 : return (CCC_Entry){
233 : .type = NULL,
234 : .status = CCC_ENTRY_INSERT_ERROR,
235 : };
236 : }
237 920 : return (CCC_Entry){
238 : .type = NULL,
239 : .status = CCC_ENTRY_VACANT,
240 : };
241 1012 : }
242 :
243 : CCC_Entry
244 110 : CCC_tree_map_try_insert(
245 : CCC_Tree_map *const map,
246 : CCC_Tree_map_node *const type_intruder,
247 : CCC_Allocator const *const allocator
248 : ) {
249 110 : if (!map || !type_intruder || !allocator) {
250 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
251 : }
252 107 : struct Query const q = find(map, key_from_node(map, type_intruder));
253 107 : if (CCC_ORDER_EQUAL == q.last_order) {
254 106 : return (CCC_Entry){
255 53 : .type = struct_base(map, q.found),
256 : .status = CCC_ENTRY_OCCUPIED,
257 : };
258 : }
259 108 : void *const inserted = maybe_allocate_insert(
260 54 : map, q.parent, q.last_order, type_intruder, allocator
261 : );
262 54 : if (!inserted) {
263 1 : return (CCC_Entry){
264 : .type = NULL,
265 : .status = CCC_ENTRY_INSERT_ERROR,
266 : };
267 : }
268 106 : return (CCC_Entry){
269 53 : .type = inserted,
270 : .status = CCC_ENTRY_VACANT,
271 : };
272 110 : }
273 :
274 : CCC_Entry
275 251 : CCC_tree_map_insert_or_assign(
276 : CCC_Tree_map *const map,
277 : CCC_Tree_map_node *const type_intruder,
278 : CCC_Allocator const *const allocator
279 : ) {
280 251 : if (!map || !type_intruder || !allocator) {
281 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
282 : }
283 248 : struct Query const q = find(map, key_from_node(map, type_intruder));
284 248 : if (CCC_ORDER_EQUAL == q.last_order) {
285 3 : void *const found = struct_base(map, q.found);
286 3 : *type_intruder = *elem_in_slot(map, found);
287 3 : memcpy(found, struct_base(map, type_intruder), map->sizeof_type);
288 6 : return (CCC_Entry){
289 3 : .type = found,
290 : .status = CCC_ENTRY_OCCUPIED,
291 : };
292 3 : }
293 490 : void *const inserted = maybe_allocate_insert(
294 245 : map, q.parent, q.last_order, type_intruder, allocator
295 : );
296 245 : if (!inserted) {
297 1 : return (CCC_Entry){
298 : .type = NULL,
299 : .status = CCC_ENTRY_INSERT_ERROR,
300 : };
301 : }
302 488 : return (CCC_Entry){
303 244 : .type = inserted,
304 : .status = CCC_ENTRY_VACANT,
305 : };
306 251 : }
307 :
308 : CCC_Tree_map_entry
309 1207 : CCC_tree_map_entry(CCC_Tree_map const *const map, void const *const key) {
310 1207 : if (!map || !key) {
311 4 : return (CCC_Tree_map_entry){
312 2 : .entry = {.status = CCC_ENTRY_ARGUMENT_ERROR},
313 : };
314 : }
315 1205 : return entry(map, key);
316 1207 : }
317 :
318 : void *
319 263 : CCC_tree_map_or_insert(
320 : CCC_Tree_map_entry const *const entry,
321 : CCC_Tree_map_node *const type_intruder,
322 : CCC_Allocator const *const allocator
323 : ) {
324 263 : if (!entry || !type_intruder || !allocator) {
325 3 : return NULL;
326 : }
327 260 : if (entry->entry.status == CCC_ENTRY_OCCUPIED) {
328 153 : return entry->entry.type;
329 : }
330 107 : return maybe_allocate_insert(
331 107 : entry->map,
332 107 : elem_in_slot(entry->map, entry->entry.type),
333 107 : entry->last_order,
334 107 : type_intruder,
335 107 : allocator
336 : );
337 263 : }
338 :
339 : void *
340 341 : CCC_tree_map_insert_entry(
341 : CCC_Tree_map_entry const *const entry,
342 : CCC_Tree_map_node *const type_intruder,
343 : CCC_Allocator const *const allocator
344 : ) {
345 341 : if (!entry || !type_intruder || !allocator) {
346 3 : return NULL;
347 : }
348 338 : if (entry->entry.status == CCC_ENTRY_OCCUPIED) {
349 103 : *type_intruder = *elem_in_slot(entry->map, entry->entry.type);
350 103 : memcpy(
351 103 : entry->entry.type,
352 103 : struct_base(entry->map, type_intruder),
353 103 : entry->map->sizeof_type
354 : );
355 103 : return entry->entry.type;
356 : }
357 235 : return maybe_allocate_insert(
358 235 : entry->map,
359 235 : elem_in_slot(entry->map, entry->entry.type),
360 235 : entry->last_order,
361 235 : type_intruder,
362 235 : allocator
363 : );
364 341 : }
365 :
366 : CCC_Entry
367 222 : CCC_tree_map_remove_entry(
368 : CCC_Tree_map_entry const *const entry, CCC_Allocator const *const allocator
369 : ) {
370 222 : if (!entry || !allocator) {
371 2 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
372 : }
373 220 : if (entry->entry.status == CCC_ENTRY_OCCUPIED) {
374 420 : void *const erased = remove_fixup(
375 210 : entry->map, elem_in_slot(entry->map, entry->entry.type)
376 : );
377 210 : assert(erased);
378 210 : if (allocator->allocate) {
379 616 : allocator->allocate((CCC_Allocator_arguments){
380 154 : .input = erased,
381 : .bytes = 0,
382 154 : .alignment = entry->map->alignof_type,
383 154 : .context = allocator->context,
384 : });
385 154 : return (CCC_Entry){
386 : .type = NULL,
387 : .status = CCC_ENTRY_OCCUPIED,
388 : };
389 : }
390 112 : return (CCC_Entry){
391 56 : .type = erased,
392 : .status = CCC_ENTRY_OCCUPIED,
393 : };
394 210 : }
395 10 : return (CCC_Entry){
396 : .type = NULL,
397 : .status = CCC_ENTRY_VACANT,
398 : };
399 222 : }
400 :
401 : CCC_Entry
402 202 : CCC_tree_map_remove_key_value(
403 : CCC_Tree_map *const map,
404 : CCC_Tree_map_node *const type_output_intruder,
405 : CCC_Allocator const *const allocator
406 : ) {
407 202 : if (!map || !type_output_intruder || !allocator) {
408 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
409 : }
410 199 : struct Query const q = find(map, key_from_node(map, type_output_intruder));
411 199 : if (q.last_order != CCC_ORDER_EQUAL) {
412 3 : return (CCC_Entry){
413 : .type = NULL,
414 : .status = CCC_ENTRY_VACANT,
415 : };
416 : }
417 196 : void *const removed = remove_fixup(map, q.found);
418 196 : if (allocator->allocate) {
419 80 : void *const any_struct = struct_base(map, type_output_intruder);
420 80 : memcpy(any_struct, removed, map->sizeof_type);
421 320 : allocator->allocate((CCC_Allocator_arguments){
422 80 : .input = removed,
423 : .bytes = 0,
424 80 : .alignment = map->alignof_type,
425 80 : .context = allocator->context,
426 : });
427 160 : return (CCC_Entry){
428 80 : .type = any_struct,
429 : .status = CCC_ENTRY_OCCUPIED,
430 : };
431 80 : }
432 232 : return (CCC_Entry){
433 116 : .type = removed,
434 : .status = CCC_ENTRY_OCCUPIED,
435 : };
436 202 : }
437 :
438 : CCC_Tree_map_entry *
439 112 : CCC_tree_map_and_modify(
440 : CCC_Tree_map_entry *e, CCC_Modifier const *const modifier
441 : ) {
442 112 : if (!e || !modifier) {
443 2 : return NULL;
444 : }
445 110 : if (modifier->modify && e->entry.status & CCC_ENTRY_OCCUPIED
446 110 : && e->entry.type) {
447 168 : modifier->modify((CCC_Arguments){
448 56 : .type = e->entry.type,
449 56 : .context = modifier->context,
450 : });
451 56 : }
452 110 : return e;
453 112 : }
454 :
455 : void *
456 26 : CCC_tree_map_unwrap(CCC_Tree_map_entry const *const e) {
457 26 : if (e && e->entry.status & CCC_ENTRY_OCCUPIED) {
458 15 : return e->entry.type;
459 : }
460 11 : return NULL;
461 26 : }
462 :
463 : CCC_Tribool
464 119 : CCC_tree_map_occupied(CCC_Tree_map_entry const *const e) {
465 119 : if (!e) {
466 1 : return CCC_TRIBOOL_ERROR;
467 : }
468 118 : return (e->entry.status & CCC_ENTRY_OCCUPIED) != 0;
469 119 : }
470 :
471 : CCC_Tribool
472 2 : CCC_tree_map_insert_error(CCC_Tree_map_entry const *const e) {
473 2 : if (!e) {
474 1 : return CCC_TRIBOOL_ERROR;
475 : }
476 1 : return (e->entry.status & CCC_ENTRY_INSERT_ERROR) != 0;
477 2 : }
478 :
479 : CCC_Entry_status
480 2 : CCC_tree_map_entry_status(CCC_Tree_map_entry const *const e) {
481 2 : return e ? e->entry.status : CCC_ENTRY_ARGUMENT_ERROR;
482 : }
483 :
484 : void *
485 10 : CCC_tree_map_begin(CCC_Tree_map const *map) {
486 10 : if (!map) {
487 1 : return NULL;
488 : }
489 9 : struct CCC_Tree_map_node *const m = min_max_from(map->root, L);
490 9 : return m == NULL ? NULL : struct_base(map, m);
491 10 : }
492 :
493 : void *
494 473 : CCC_tree_map_next(
495 : CCC_Tree_map const *const map,
496 : CCC_Tree_map_node const *const iterator_intruder
497 : ) {
498 473 : if (!map || !iterator_intruder) {
499 2 : return NULL;
500 : }
501 942 : struct CCC_Tree_map_node const *const n
502 471 : = next(map, iterator_intruder, INORDER);
503 471 : if (n == NULL) {
504 9 : return NULL;
505 : }
506 462 : return struct_base(map, n);
507 473 : }
508 :
509 : void *
510 4 : CCC_tree_map_reverse_begin(CCC_Tree_map const *const map) {
511 4 : if (!map) {
512 1 : return NULL;
513 : }
514 3 : struct CCC_Tree_map_node *const m = min_max_from(map->root, R);
515 3 : return m == NULL ? NULL : struct_base(map, m);
516 4 : }
517 :
518 : void *
519 268 : CCC_tree_map_end(CCC_Tree_map const *const) {
520 268 : return NULL;
521 : }
522 :
523 : void *
524 131 : CCC_tree_map_reverse_end(CCC_Tree_map const *const) {
525 131 : return NULL;
526 : }
527 :
528 : void *
529 153 : CCC_tree_map_reverse_next(
530 : CCC_Tree_map const *const map,
531 : CCC_Tree_map_node const *const iterator_intruder
532 : ) {
533 153 : if (!map || !iterator_intruder) {
534 2 : return NULL;
535 : }
536 302 : struct CCC_Tree_map_node const *const n
537 151 : = next(map, iterator_intruder, INORDER_REVERSE);
538 151 : return (n == NULL) ? NULL : struct_base(map, n);
539 153 : }
540 :
541 : CCC_Range
542 8 : CCC_tree_map_equal_range(
543 : CCC_Tree_map const *const map,
544 : void const *const begin_key,
545 : void const *const end_key
546 : ) {
547 8 : if (!map || !begin_key || !end_key) {
548 3 : return (CCC_Range){};
549 : }
550 5 : return equal_range(map, begin_key, end_key, INORDER);
551 8 : }
552 :
553 : CCC_Range_reverse
554 8 : CCC_tree_map_equal_range_reverse(
555 : CCC_Tree_map const *const map,
556 : void const *const reverse_begin_key,
557 : void const *const reverse_end_key
558 : ) {
559 8 : if (!map || !reverse_begin_key || !reverse_end_key) {
560 3 : return (CCC_Range_reverse){};
561 : }
562 5 : CCC_Range const range
563 5 : = equal_range(map, reverse_begin_key, reverse_end_key, INORDER_REVERSE);
564 15 : return (CCC_Range_reverse){
565 5 : .reverse_begin = range.begin,
566 5 : .reverse_end = range.end,
567 : };
568 8 : }
569 :
570 : CCC_Count
571 122 : CCC_tree_map_count(CCC_Tree_map const *const map) {
572 122 : if (!map) {
573 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
574 : }
575 121 : return (CCC_Count){.count = map->count};
576 122 : }
577 :
578 : CCC_Tribool
579 7 : CCC_tree_map_is_empty(CCC_Tree_map const *const map) {
580 7 : if (!map) {
581 1 : return CCC_TRIBOOL_ERROR;
582 : }
583 6 : return !map->count;
584 7 : }
585 :
586 : CCC_Tribool
587 1933 : CCC_tree_map_validate(CCC_Tree_map const *map) {
588 1933 : if (!map) {
589 1 : return CCC_TRIBOOL_ERROR;
590 : }
591 1932 : return validate(map);
592 1933 : }
593 :
594 : /** This is a linear time constant space deletion of tree nodes via left
595 : rotations so element fields are modified during progression of deletes. */
596 : CCC_Result
597 16 : CCC_tree_map_clear(
598 : CCC_Tree_map *const map,
599 : CCC_Destructor const *const destructor,
600 : CCC_Allocator const *const allocator
601 : ) {
602 16 : if (!map || !destructor || !allocator) {
603 3 : return CCC_RESULT_ARGUMENT_ERROR;
604 : }
605 13 : struct CCC_Tree_map_node *node = map->root;
606 1128 : while (node != NULL) {
607 1115 : if (node->branch[L] != NULL) {
608 529 : struct CCC_Tree_map_node *const left = node->branch[L];
609 529 : node->branch[L] = left->branch[R];
610 529 : left->branch[R] = node;
611 529 : node = left;
612 : continue;
613 529 : }
614 586 : struct CCC_Tree_map_node *const next = node->branch[R];
615 586 : node->branch[L] = node->branch[R] = NULL;
616 586 : node->parent = NULL;
617 586 : void *const type = struct_base(map, node);
618 586 : if (destructor->destroy) {
619 48 : destructor->destroy((CCC_Arguments){
620 16 : .type = type,
621 16 : .context = destructor->context,
622 : });
623 16 : }
624 586 : if (allocator->allocate) {
625 2344 : (void)allocator->allocate((CCC_Allocator_arguments){
626 586 : .input = type,
627 : .bytes = 0,
628 586 : .alignment = map->alignof_type,
629 586 : .context = allocator->context,
630 : });
631 586 : }
632 586 : node = next;
633 586 : }
634 13 : map->count = 0;
635 13 : map->root = NULL;
636 13 : return CCC_RESULT_OK;
637 16 : }
638 :
639 : /*========================= Private Interface ============================*/
640 :
641 : struct CCC_Tree_map_entry
642 98 : CCC_private_tree_map_entry(
643 : struct CCC_Tree_map const *const map, void const *const key
644 : ) {
645 98 : return entry(map, key);
646 98 : }
647 :
648 : void *
649 196 : CCC_private_tree_map_insert(
650 : struct CCC_Tree_map *const map,
651 : struct CCC_Tree_map_node *const parent,
652 : CCC_Order const last_order,
653 : struct CCC_Tree_map_node *const type_output_intruder
654 : ) {
655 196 : return insert(map, parent, last_order, type_output_intruder);
656 : }
657 :
658 : void *
659 87 : CCC_private_tree_map_key_in_slot(
660 : struct CCC_Tree_map const *const map, void const *const slot
661 : ) {
662 87 : return key_in_slot(map, slot);
663 : }
664 :
665 : struct CCC_Tree_map_node *
666 410 : CCC_private_tree_map_node_in_slot(
667 : struct CCC_Tree_map const *const map, void const *const slot
668 : ) {
669 410 : return elem_in_slot(map, slot);
670 : }
671 :
672 : /*========================= Static Helpers ============================*/
673 :
674 : static struct CCC_Tree_map_node *
675 161 : min_max_from(struct CCC_Tree_map_node *start, enum Link const dir) {
676 161 : if (start == NULL) {
677 1 : return start;
678 : }
679 357 : for (; start->branch[dir] != NULL; start = start->branch[dir]) {}
680 160 : return start;
681 161 : }
682 :
683 : static struct CCC_Tree_map_entry
684 1303 : entry(struct CCC_Tree_map const *const map, void const *const key) {
685 1303 : struct Query const q = find(map, key);
686 1303 : if (CCC_ORDER_EQUAL == q.last_order) {
687 2776 : return (struct CCC_Tree_map_entry){
688 694 : .map = (struct CCC_Tree_map *)map,
689 694 : .last_order = q.last_order,
690 1388 : .entry = {
691 694 : .type = struct_base(map, q.found),
692 : .status = CCC_ENTRY_OCCUPIED,
693 : },
694 : };
695 : }
696 2436 : return (struct CCC_Tree_map_entry){
697 609 : .map = (struct CCC_Tree_map *)map,
698 609 : .last_order = q.last_order,
699 1218 : .entry = {
700 609 : .type = struct_base(map, q.parent),
701 : .status = CCC_ENTRY_VACANT | CCC_ENTRY_NO_UNWRAP,
702 : },
703 : };
704 1303 : }
705 :
706 : static void *
707 1562 : maybe_allocate_insert(
708 : struct CCC_Tree_map *const map,
709 : struct CCC_Tree_map_node *const parent,
710 : CCC_Order const last_order,
711 : struct CCC_Tree_map_node *type_output_intruder,
712 : CCC_Allocator const *const allocator
713 : ) {
714 1562 : if (allocator->allocate) {
715 5544 : void *const new = allocator->allocate((CCC_Allocator_arguments){
716 : .input = NULL,
717 1386 : .bytes = map->sizeof_type,
718 1386 : .alignment = map->alignof_type,
719 1386 : .context = allocator->context,
720 : });
721 1386 : if (!new) {
722 5 : return NULL;
723 : }
724 1381 : memcpy(new, struct_base(map, type_output_intruder), map->sizeof_type);
725 1381 : type_output_intruder = elem_in_slot(map, new);
726 1386 : }
727 1557 : return insert(map, parent, last_order, type_output_intruder);
728 1562 : }
729 :
730 : static void *
731 1753 : insert(
732 : struct CCC_Tree_map *const map,
733 : struct CCC_Tree_map_node *const parent,
734 : CCC_Order const last_order,
735 : struct CCC_Tree_map_node *const type_output_intruder
736 : ) {
737 1753 : init_node(map, type_output_intruder);
738 1753 : if (!map->count) {
739 46 : map->root = type_output_intruder;
740 46 : ++map->count;
741 46 : return struct_base(map, type_output_intruder);
742 : }
743 1707 : assert(last_order == CCC_ORDER_GREATER || last_order == CCC_ORDER_LESSER);
744 1707 : CCC_Tribool rank_rule_break = CCC_FALSE;
745 1707 : if (parent) {
746 : rank_rule_break
747 1707 : = parent->branch[L] == NULL && parent->branch[R] == NULL;
748 1707 : parent->branch[CCC_ORDER_GREATER == last_order] = type_output_intruder;
749 1707 : }
750 1707 : type_output_intruder->parent = parent;
751 1707 : if (rank_rule_break) {
752 1516 : insert_fixup(map, parent, type_output_intruder);
753 1516 : }
754 1707 : ++map->count;
755 1707 : return struct_base(map, type_output_intruder);
756 1753 : }
757 :
758 : static struct Query
759 2996 : find(struct CCC_Tree_map const *const map, void const *const key) {
760 2996 : struct CCC_Tree_map_node const *parent = NULL;
761 2996 : struct Query q = {
762 : .last_order = CCC_ORDER_ERROR,
763 2996 : .found = map->root,
764 : };
765 15893 : while (q.found != NULL) {
766 13990 : q.last_order = order(map, key, q.found);
767 13990 : if (CCC_ORDER_EQUAL == q.last_order) {
768 1093 : return q;
769 : }
770 12897 : parent = q.found;
771 12897 : q.found = q.found->branch[CCC_ORDER_GREATER == q.last_order];
772 : }
773 : /* Type punning here OK as both union members have same type and size. */
774 1903 : q.parent = (struct CCC_Tree_map_node *)parent;
775 1903 : return q;
776 2996 : }
777 :
778 : static struct CCC_Tree_map_node *
779 629 : next(
780 : struct CCC_Tree_map const *const map [[maybe_unused]],
781 : struct CCC_Tree_map_node const *n,
782 : enum Link const traversal
783 : ) {
784 629 : if (!n) {
785 0 : return NULL;
786 : }
787 629 : assert(map->root->parent == NULL);
788 629 : if (n->branch[traversal]) {
789 540 : for (n = n->branch[traversal]; n->branch[!traversal];
790 218 : n = n->branch[!traversal]) {}
791 322 : return (struct CCC_Tree_map_node *)n;
792 : }
793 624 : for (; n->parent && n->parent->branch[!traversal] != n; n = n->parent) {}
794 307 : return n->parent;
795 629 : }
796 :
797 : static CCC_Range
798 10 : equal_range(
799 : struct CCC_Tree_map const *const map,
800 : void const *const begin_key,
801 : void const *const end_key,
802 : enum Link const traversal
803 : ) {
804 10 : if (!map->count) {
805 2 : return (CCC_Range){};
806 : }
807 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
808 8 : struct Query b = find(map, begin_key);
809 8 : if (b.last_order == les_or_grt[traversal]) {
810 2 : b.found = next(map, b.found, traversal);
811 2 : }
812 8 : struct Query e = find(map, end_key);
813 8 : if (e.last_order != les_or_grt[!traversal]) {
814 5 : e.found = next(map, e.found, traversal);
815 5 : }
816 24 : return (CCC_Range){
817 8 : .begin = b.found == NULL ? NULL : struct_base(map, b.found),
818 8 : .end = e.found == NULL ? NULL : struct_base(map, e.found),
819 : };
820 10 : }
821 :
822 : static inline void
823 1753 : init_node(
824 : struct CCC_Tree_map *const map [[maybe_unused]],
825 : struct CCC_Tree_map_node *const e
826 : ) {
827 1753 : assert(e != NULL);
828 1753 : assert(map != NULL);
829 1753 : e->branch[L] = e->branch[R] = e->parent = NULL;
830 1753 : e->parity = 0;
831 1753 : }
832 :
833 : static inline void
834 87 : swap(void *const temp, void *const a, void *const b, size_t const sizeof_type) {
835 87 : if (a == b || !a || !b) {
836 0 : return;
837 : }
838 87 : (void)memcpy(temp, a, sizeof_type);
839 87 : (void)memcpy(a, b, sizeof_type);
840 87 : (void)memcpy(b, temp, sizeof_type);
841 174 : }
842 :
843 : static inline CCC_Order
844 126505 : order(
845 : struct CCC_Tree_map const *const map,
846 : void const *const key,
847 : struct CCC_Tree_map_node const *const node
848 : ) {
849 506020 : return map->comparator.compare((CCC_Key_comparator_arguments){
850 126505 : .key_left = key,
851 126505 : .type_right = struct_base(map, node),
852 126505 : .context = map->comparator.context,
853 : });
854 : }
855 :
856 : static inline void *
857 247154 : struct_base(
858 : struct CCC_Tree_map const *const map,
859 : struct CCC_Tree_map_node const *const e
860 : ) {
861 247154 : return e ? ((char *)e->branch) - map->type_intruder_offset : NULL;
862 : }
863 :
864 : static inline void *
865 114077 : key_from_node(
866 : struct CCC_Tree_map const *const map,
867 : struct CCC_Tree_map_node const *const node
868 : ) {
869 114077 : return node ? (char *)struct_base(map, node) + map->key_offset : NULL;
870 : }
871 :
872 : static inline void *
873 87 : key_in_slot(struct CCC_Tree_map const *const map, void const *const slot) {
874 87 : return slot ? (char *)slot + map->key_offset : NULL;
875 : }
876 :
877 : static inline struct CCC_Tree_map_node *
878 2449 : elem_in_slot(struct CCC_Tree_map const *const map, void const *const slot) {
879 2449 : return slot ? (struct CCC_Tree_map_node *)((char *)slot
880 2430 : + map->type_intruder_offset)
881 : : NULL;
882 : }
883 :
884 : /*======================= WAVL Tree Maintenance =========================*/
885 :
886 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
887 : Sen, and Tarjan (Fig. 2. pg 7). Assumes x's parent z is not null. */
888 : static void
889 1516 : insert_fixup(
890 : struct CCC_Tree_map *const map,
891 : struct CCC_Tree_map_node *z,
892 : struct CCC_Tree_map_node *x
893 : ) {
894 1516 : assert(z);
895 1516 : do {
896 2801 : promote(z);
897 2801 : x = z;
898 2801 : z = z->parent;
899 2801 : if (z == NULL) {
900 187 : return;
901 : }
902 2614 : } while (is_01_parent(x, z, sibling_of(x)));
903 :
904 1329 : if (!is_02_parent(x, z, sibling_of(x))) {
905 338 : return;
906 : }
907 991 : assert(x != NULL);
908 991 : assert(is_0_child(z, x));
909 991 : enum Link const p_to_x_dir = z->branch[R] == x;
910 991 : struct CCC_Tree_map_node *const y = x->branch[!p_to_x_dir];
911 991 : if (y == NULL || is_2_child(z, y)) {
912 900 : rotate(map, z, x, y, !p_to_x_dir);
913 900 : demote(z);
914 900 : } else {
915 91 : assert(is_1_child(z, y));
916 91 : double_rotate(map, z, x, y, p_to_x_dir);
917 91 : promote(y);
918 91 : demote(x);
919 91 : demote(z);
920 : }
921 2507 : }
922 :
923 : static void *
924 406 : remove_fixup(
925 : struct CCC_Tree_map *const map, struct CCC_Tree_map_node *const remove
926 : ) {
927 406 : struct CCC_Tree_map_node *y = NULL;
928 406 : struct CCC_Tree_map_node *x = NULL;
929 406 : struct CCC_Tree_map_node *p_of_xy = NULL;
930 406 : CCC_Tribool two_child = CCC_FALSE;
931 406 : if (remove->branch[L] == NULL || remove->branch[R] == NULL) {
932 257 : y = remove;
933 257 : p_of_xy = y->parent;
934 257 : x = y->branch[y->branch[L] == NULL];
935 257 : if (x) {
936 98 : x->parent = y->parent;
937 98 : }
938 257 : if (p_of_xy == NULL) {
939 10 : map->root = x;
940 10 : } else {
941 247 : p_of_xy->branch[p_of_xy->branch[R] == y] = x;
942 : }
943 257 : two_child = is_2_child(p_of_xy, y);
944 257 : } else {
945 149 : y = min_max_from(remove->branch[R], L);
946 149 : p_of_xy = y->parent;
947 149 : x = y->branch[y->branch[L] == NULL];
948 149 : if (x) {
949 38 : x->parent = y->parent;
950 38 : }
951 :
952 : /* Save if check and improve readability by assuming this is true. */
953 149 : assert(p_of_xy != NULL);
954 :
955 149 : two_child = is_2_child(p_of_xy, y);
956 149 : p_of_xy->branch[p_of_xy->branch[R] == y] = x;
957 149 : transplant(map, remove, y);
958 149 : if (remove == p_of_xy) {
959 63 : p_of_xy = y;
960 63 : }
961 : }
962 :
963 406 : if (p_of_xy != NULL) {
964 396 : if (two_child) {
965 207 : assert(p_of_xy != NULL);
966 207 : rebalance_3_child(map, p_of_xy, x);
967 396 : } else if (x == NULL && p_of_xy->branch[L] == p_of_xy->branch[R]) {
968 60 : assert(p_of_xy != NULL);
969 120 : CCC_Tribool const demote_makes_3_child
970 60 : = is_2_child(p_of_xy->parent, p_of_xy);
971 60 : demote(p_of_xy);
972 60 : if (demote_makes_3_child) {
973 32 : rebalance_3_child(map, p_of_xy->parent, p_of_xy);
974 32 : }
975 60 : }
976 396 : assert(!is_leaf(p_of_xy) || !parity(p_of_xy));
977 396 : }
978 406 : remove->branch[L] = remove->branch[R] = remove->parent = NULL;
979 406 : remove->parity = 0;
980 406 : --map->count;
981 812 : return struct_base(map, remove);
982 406 : }
983 :
984 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
985 : Sen, and Tarjan (Fig. 3. pg 8). */
986 : static void
987 239 : rebalance_3_child(
988 : struct CCC_Tree_map *const map,
989 : struct CCC_Tree_map_node *z,
990 : struct CCC_Tree_map_node *x
991 : ) {
992 239 : CCC_Tribool made_3_child = CCC_TRUE;
993 440 : while (z && made_3_child) {
994 295 : assert(z->branch[L] == x || z->branch[R] == x);
995 295 : struct CCC_Tree_map_node *const g = z->parent;
996 295 : struct CCC_Tree_map_node *const y = z->branch[z->branch[L] == x];
997 295 : made_3_child = g != NULL && is_2_child(g, z);
998 295 : if (is_2_child(z, y)) {
999 168 : demote(z);
1000 295 : } else if (y && is_22_parent(y->branch[L], y, y->branch[R])) {
1001 33 : demote(z);
1002 33 : demote(y);
1003 127 : } else if (y) {
1004 94 : assert(is_1_child(z, y));
1005 94 : assert(is_3_child(z, x));
1006 94 : assert(!is_2_child(z, y));
1007 94 : assert(!is_22_parent(y->branch[L], y, y->branch[R]));
1008 94 : enum Link const z_to_x_dir = z->branch[R] == x;
1009 94 : struct CCC_Tree_map_node *const w = y->branch[!z_to_x_dir];
1010 94 : if (is_1_child(y, w)) {
1011 65 : rotate(map, z, y, y->branch[z_to_x_dir], z_to_x_dir);
1012 65 : promote(y);
1013 65 : demote(z);
1014 65 : if (is_leaf(z)) {
1015 19 : demote(z);
1016 19 : }
1017 65 : } else {
1018 : /* w is a 2-child and v will be a 1-child. */
1019 29 : struct CCC_Tree_map_node *const v = y->branch[z_to_x_dir];
1020 29 : assert(is_2_child(y, w));
1021 29 : assert(is_1_child(y, v));
1022 29 : double_rotate(map, z, y, v, !z_to_x_dir);
1023 29 : double_promote(v);
1024 29 : demote(y);
1025 29 : double_demote(z);
1026 : /* Optional "Rebalancing with Promotion," defined as follows:
1027 : if node z is a non-leaf 1,1 node, we promote it;
1028 : otherwise, if y is a non-leaf 1,1 node, we promote it.
1029 : (See Figure 4.) (Haeupler et. al. 2014, 17).
1030 : This reduces constants in some of theorems mentioned in the
1031 : paper but may not be worth doing. Rotations stay at 2 worst
1032 : case. Should revisit after more performance testing. */
1033 29 : if (!is_leaf(z)
1034 29 : && is_11_parent(z->branch[L], z, z->branch[R])) {
1035 9 : promote(z);
1036 29 : } else if (!is_leaf(y)
1037 20 : && is_11_parent(y->branch[L], y, y->branch[R])) {
1038 3 : promote(y);
1039 3 : }
1040 29 : }
1041 : /* Returning here confirms O(1) rotations for re-balance. */
1042 : return;
1043 94 : }
1044 201 : x = z;
1045 201 : z = g;
1046 295 : }
1047 239 : }
1048 :
1049 : static void
1050 149 : transplant(
1051 : struct CCC_Tree_map *const map,
1052 : struct CCC_Tree_map_node *const remove,
1053 : struct CCC_Tree_map_node *const replacement
1054 : ) {
1055 149 : assert(remove != NULL);
1056 149 : assert(replacement != NULL);
1057 149 : replacement->parent = remove->parent;
1058 149 : if (remove->parent == NULL) {
1059 17 : map->root = replacement;
1060 17 : } else {
1061 132 : remove->parent->branch[remove->parent->branch[R] == remove]
1062 264 : = replacement;
1063 : }
1064 149 : if (remove->branch[R]) {
1065 108 : remove->branch[R]->parent = replacement;
1066 108 : }
1067 149 : if (remove->branch[L]) {
1068 149 : remove->branch[L]->parent = replacement;
1069 149 : }
1070 149 : replacement->branch[R] = remove->branch[R];
1071 149 : replacement->branch[L] = remove->branch[L];
1072 149 : replacement->parity
1073 298 : = (typeof((struct CCC_Tree_map_node){}.parity))parity(remove);
1074 149 : }
1075 :
1076 : /** A single rotation is symmetric. Here is the right case. Lowercase are nodes
1077 : and uppercase are arbitrary subtrees.
1078 : z x
1079 : ╭──┴──╮ ╭──┴──╮
1080 : x C A z
1081 : ╭─┴─╮ -> ╭─┴─╮
1082 : A y y C
1083 : │ │
1084 : B B
1085 :
1086 : Taking a link as input allows us to code both symmetrical cases at once. */
1087 : static void
1088 965 : rotate(
1089 : struct CCC_Tree_map *const map,
1090 : struct CCC_Tree_map_node *const z,
1091 : struct CCC_Tree_map_node *const x,
1092 : struct CCC_Tree_map_node *const y,
1093 : enum Link const dir
1094 : ) {
1095 965 : assert(z != NULL);
1096 965 : struct CCC_Tree_map_node *const g = z->parent;
1097 965 : x->parent = g;
1098 965 : if (g == NULL) {
1099 127 : map->root = x;
1100 127 : } else {
1101 838 : g->branch[g->branch[R] == z] = x;
1102 : }
1103 965 : x->branch[dir] = z;
1104 965 : z->parent = x;
1105 965 : z->branch[!dir] = y;
1106 965 : if (y) {
1107 407 : y->parent = z;
1108 407 : }
1109 965 : }
1110 :
1111 : /** A double rotation shouldn't actually be two calls to rotate because that
1112 : would invoke pointless memory writes. Here is an example of double right.
1113 : Lowercase are nodes and uppercase are arbitrary subtrees.
1114 :
1115 : z y
1116 : ╭──┴──╮ ╭──┴──╮
1117 : x D x z
1118 : ╭─┴─╮ -> ╭─┴─╮ ╭─┴─╮
1119 : A y A B C D
1120 : ╭─┴─╮
1121 : B C
1122 :
1123 : Taking a link as input allows us to code both symmetrical cases at once. */
1124 : static void
1125 120 : double_rotate(
1126 : struct CCC_Tree_map *const map,
1127 : struct CCC_Tree_map_node *const z,
1128 : struct CCC_Tree_map_node *const x,
1129 : struct CCC_Tree_map_node *const y,
1130 : enum Link const dir
1131 : ) {
1132 120 : assert(z != NULL);
1133 120 : assert(x != NULL);
1134 120 : assert(y != NULL);
1135 120 : struct CCC_Tree_map_node *const g = z->parent;
1136 120 : y->parent = g;
1137 120 : if (g == NULL) {
1138 5 : map->root = y;
1139 5 : } else {
1140 115 : g->branch[g->branch[R] == z] = y;
1141 : }
1142 120 : x->branch[!dir] = y->branch[dir];
1143 120 : if (y->branch[dir]) {
1144 35 : y->branch[dir]->parent = x;
1145 35 : }
1146 120 : y->branch[dir] = x;
1147 120 : x->parent = y;
1148 :
1149 120 : z->branch[dir] = y->branch[!dir];
1150 120 : if (y->branch[!dir]) {
1151 32 : y->branch[!dir]->parent = z;
1152 32 : }
1153 120 : y->branch[!dir] = z;
1154 120 : z->parent = y;
1155 120 : }
1156 :
1157 : /* Returns the parity of a node either 0 or 1. A NULL node has a parity of 1 aka
1158 : CCC_TRUE. */
1159 : static inline CCC_Tribool
1160 21293 : parity(struct CCC_Tree_map_node const *const x) {
1161 21293 : return x ? (CCC_Tribool)x->parity : CCC_TRUE;
1162 : }
1163 :
1164 : /* Returns true for rank difference 0 (rule break) between the parent and node.
1165 : p
1166 : 1╭─╯
1167 : x */
1168 : [[maybe_unused]] static inline CCC_Tribool
1169 991 : is_0_child(
1170 : struct CCC_Tree_map_node const *const p,
1171 : struct CCC_Tree_map_node const *const x
1172 : ) {
1173 991 : return parity(p) == parity(x);
1174 : }
1175 :
1176 : /* Returns true for rank difference 1 between the parent and node.
1177 : p
1178 : 1/
1179 : x*/
1180 : static inline CCC_Tribool
1181 308 : is_1_child(
1182 : struct CCC_Tree_map_node const *const p,
1183 : struct CCC_Tree_map_node const *const x
1184 : ) {
1185 308 : return parity(p) != parity(x);
1186 : }
1187 :
1188 : /* Returns true for rank difference 2 between the parent and node.
1189 : p
1190 : 2╭─╯
1191 : x */
1192 : static inline CCC_Tribool
1193 1598 : is_2_child(
1194 : struct CCC_Tree_map_node const *const p,
1195 : struct CCC_Tree_map_node const *const x
1196 : ) {
1197 1598 : return parity(p) == parity(x);
1198 : }
1199 :
1200 : /* Returns true for rank difference 3 between the parent and node.
1201 : p
1202 : 3╭─╯
1203 : x */
1204 : [[maybe_unused]] static inline CCC_Tribool
1205 94 : is_3_child(
1206 : struct CCC_Tree_map_node const *const p,
1207 : struct CCC_Tree_map_node const *const x
1208 : ) {
1209 94 : return parity(p) != parity(x);
1210 : }
1211 :
1212 : /* Returns true if a parent is a 0,1 or 1,0 node, which is not allowed. Either
1213 : child may be the sentinel node which has a parity of 1 and rank -1.
1214 : p
1215 : 0╭─┴─╮1
1216 : x y */
1217 : static inline CCC_Tribool
1218 2614 : is_01_parent(
1219 : struct CCC_Tree_map_node const *const x,
1220 : struct CCC_Tree_map_node const *const p,
1221 : struct CCC_Tree_map_node const *const y
1222 : ) {
1223 4827 : return (!parity(x) && !parity(p) && parity(y))
1224 2614 : || (parity(x) && parity(p) && !parity(y));
1225 : }
1226 :
1227 : /* Returns true if a parent is a 1,1 node. Either child may be the sentinel
1228 : node which has a parity of 1 and rank -1.
1229 : p
1230 : 1╭─┴─╮1
1231 : x y */
1232 : static inline CCC_Tribool
1233 21 : is_11_parent(
1234 : struct CCC_Tree_map_node const *const x,
1235 : struct CCC_Tree_map_node const *const p,
1236 : struct CCC_Tree_map_node const *const y
1237 : ) {
1238 31 : return (!parity(x) && parity(p) && !parity(y))
1239 21 : || (parity(x) && !parity(p) && parity(y));
1240 : }
1241 :
1242 : /* Returns true if a parent is a 0,2 or 2,0 node, which is not allowed. Either
1243 : child may be the sentinel node which has a parity of 1 and rank -1.
1244 : p
1245 : 0╭─┴─╮2
1246 : x y */
1247 : static inline CCC_Tribool
1248 1329 : is_02_parent(
1249 : struct CCC_Tree_map_node const *const x,
1250 : struct CCC_Tree_map_node const *const p,
1251 : struct CCC_Tree_map_node const *const y
1252 : ) {
1253 1329 : return (parity(x) == parity(p)) && (parity(p) == parity(y));
1254 : }
1255 :
1256 : /* Returns true if a parent is a 2,2 or 2,2 node, which is allowed. 2,2 nodes
1257 : are allowed in a WAVL tree but the absence of any 2,2 nodes is the exact
1258 : equivalent of a normal AVL tree which can occur if only insertions occur
1259 : for a WAVL tree. Either child may be the sentinel node which has a parity of
1260 : 1 and rank -1.
1261 : p
1262 : 2╭─┴─╮2
1263 : x y */
1264 : static inline CCC_Tribool
1265 221 : is_22_parent(
1266 : struct CCC_Tree_map_node const *const x,
1267 : struct CCC_Tree_map_node const *const p,
1268 : struct CCC_Tree_map_node const *const y
1269 : ) {
1270 221 : return (parity(x) == parity(p)) && (parity(p) == parity(y));
1271 : }
1272 :
1273 : static inline void
1274 4458 : promote(struct CCC_Tree_map_node *const x) {
1275 4458 : if (x) {
1276 4458 : x->parity = !x->parity;
1277 4458 : }
1278 4458 : }
1279 :
1280 : static inline void
1281 1489 : demote(struct CCC_Tree_map_node *const x) {
1282 1489 : promote(x);
1283 1489 : }
1284 :
1285 : /* One could imagine non-parity based rank tracking making this function
1286 : meaningful, but two parity changes are the same as a no-op. Leave for
1287 : clarity of what the code is meant to do through certain sections. */
1288 : static inline void
1289 29 : double_promote(struct CCC_Tree_map_node *const) {
1290 29 : }
1291 :
1292 : /* One could imagine non-parity based rank tracking making this function
1293 : meaningful, but two parity changes are the same as a no-op. Leave for
1294 : clarity of what the code is meant to do through certain sections. */
1295 : static inline void
1296 29 : double_demote(struct CCC_Tree_map_node *const) {
1297 29 : }
1298 :
1299 : static inline CCC_Tribool
1300 510 : is_leaf(struct CCC_Tree_map_node const *const x) {
1301 510 : return x->branch[L] == NULL && x->branch[R] == NULL;
1302 : }
1303 :
1304 : static inline struct CCC_Tree_map_node *
1305 3943 : sibling_of(struct CCC_Tree_map_node const *const x) {
1306 3943 : if (x->parent == NULL) {
1307 0 : return NULL;
1308 : }
1309 : /* We want the sibling so we need the truthy value to be opposite of x. */
1310 3943 : return x->parent->branch[x->parent->branch[L] == x];
1311 3943 : }
1312 :
1313 : /*=========================== Validation ===============================*/
1314 :
1315 : /* NOLINTBEGIN(*misc-no-recursion) */
1316 :
1317 : /** @internal */
1318 : struct Tree_range {
1319 : struct CCC_Tree_map_node const *low;
1320 : struct CCC_Tree_map_node const *root;
1321 : struct CCC_Tree_map_node const *high;
1322 : };
1323 :
1324 : static size_t
1325 132232 : recursive_count(
1326 : struct CCC_Tree_map const *const map,
1327 : struct CCC_Tree_map_node const *const r
1328 : ) {
1329 132232 : if (r == NULL) {
1330 67082 : return 0;
1331 : }
1332 130300 : return 1 + recursive_count(map, r->branch[R])
1333 65150 : + recursive_count(map, r->branch[L]);
1334 132232 : }
1335 :
1336 : static CCC_Tribool
1337 132232 : are_subtrees_valid(struct CCC_Tree_map const *t, struct Tree_range const r) {
1338 132232 : if (!r.root) {
1339 67082 : return CCC_TRUE;
1340 : }
1341 65150 : if (r.low
1342 65150 : && order(t, key_from_node(t, r.low), r.root) != CCC_ORDER_LESSER) {
1343 0 : return CCC_FALSE;
1344 : }
1345 65150 : if (r.high
1346 65150 : && order(t, key_from_node(t, r.high), r.root) != CCC_ORDER_GREATER) {
1347 0 : return CCC_FALSE;
1348 : }
1349 130300 : return are_subtrees_valid(
1350 65150 : t,
1351 260600 : (struct Tree_range){
1352 65150 : .low = r.low,
1353 65150 : .root = r.root->branch[L],
1354 65150 : .high = r.root,
1355 : }
1356 : )
1357 65150 : && are_subtrees_valid(
1358 65150 : t,
1359 260600 : (struct Tree_range){
1360 65150 : .low = r.root,
1361 65150 : .root = r.root->branch[R],
1362 65150 : .high = r.high,
1363 : }
1364 : );
1365 132232 : }
1366 :
1367 : static CCC_Tribool
1368 132232 : is_storing_parent(
1369 : struct CCC_Tree_map const *const t,
1370 : struct CCC_Tree_map_node const *const parent,
1371 : struct CCC_Tree_map_node const *const root
1372 : ) {
1373 132232 : if (root == NULL) {
1374 67082 : return CCC_TRUE;
1375 : }
1376 65150 : if (root->parent != parent) {
1377 0 : return CCC_FALSE;
1378 : }
1379 130300 : return is_storing_parent(t, root, root->branch[L])
1380 65150 : && is_storing_parent(t, root, root->branch[R]);
1381 132232 : }
1382 :
1383 : static CCC_Tribool
1384 1932 : validate(struct CCC_Tree_map const *const map) {
1385 1932 : if (!are_subtrees_valid(
1386 1932 : map,
1387 3864 : (struct Tree_range){
1388 : .low = NULL,
1389 1932 : .root = map->root,
1390 : .high = NULL,
1391 : }
1392 : )) {
1393 0 : return CCC_FALSE;
1394 : }
1395 1932 : if (recursive_count(map, map->root) != map->count) {
1396 0 : return CCC_FALSE;
1397 : }
1398 1932 : if (!is_storing_parent(map, NULL, map->root)) {
1399 0 : return CCC_FALSE;
1400 : }
1401 1932 : return CCC_TRUE;
1402 1932 : }
1403 :
1404 : /* NOLINTEND(*misc-no-recursion) */
1405 :
1406 : /* Below you will find the required license for code that inspired the
1407 : implementation of a WAVL tree in this repository for some map containers.
1408 :
1409 : The original repository can be found here:
1410 :
1411 : https://github.com/pvachon/wavl_tree
1412 :
1413 : The original implementation has be changed to eliminate left and right cases
1414 : and work within the C Container Collection memory framework.
1415 :
1416 : Redistribution and use in source and binary forms, with or without
1417 : modification, are permitted provided that the following conditions are met:
1418 :
1419 : 1. Redistributions of source code must retain the above copyright notice, this
1420 : list of conditions and the following disclaimer.
1421 :
1422 : 2. Redistributions in binary form must reproduce the above copyright notice,
1423 : this list of conditions and the following disclaimer in the documentation
1424 : and/or other materials provided with the distribution.
1425 :
1426 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1427 : AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1428 : IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1429 : DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
1430 : FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1431 : DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
1432 : SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1433 : CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
1434 : OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1435 : OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
|
