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"
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 94 : *type_intruder = *q.found;
216 94 : void *const found = struct_base(map, q.found);
217 94 : void *const any_struct = struct_base(map, type_intruder);
218 94 : void *const old_val = struct_base(map, temp_intruder);
219 94 : swap(old_val, found, any_struct, map->sizeof_type);
220 188 : type_intruder->branch[L] = type_intruder->branch[R]
221 188 : = type_intruder->parent = NULL;
222 188 : temp_intruder->branch[L] = temp_intruder->branch[R]
223 188 : = temp_intruder->parent = NULL;
224 188 : return (CCC_Entry){
225 94 : .type = old_val,
226 : .status = CCC_ENTRY_OCCUPIED,
227 : };
228 94 : }
229 914 : if (!maybe_allocate_insert(
230 914 : 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 913 : 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 1202 : CCC_tree_map_entry(CCC_Tree_map const *const map, void const *const key) {
310 1202 : if (!map || !key) {
311 4 : return (CCC_Tree_map_entry){
312 2 : .entry = {.status = CCC_ENTRY_ARGUMENT_ERROR},
313 : };
314 : }
315 1200 : return entry(map, key);
316 1202 : }
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 336 : 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 336 : if (!entry || !type_intruder || !allocator) {
346 3 : return NULL;
347 : }
348 333 : 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 230 : return maybe_allocate_insert(
358 230 : entry->map,
359 230 : elem_in_slot(entry->map, entry->entry.type),
360 230 : entry->last_order,
361 230 : type_intruder,
362 230 : allocator
363 : );
364 336 : }
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 462 : allocator->allocate((CCC_Allocator_arguments){
380 154 : .input = erased,
381 : .bytes = 0,
382 154 : .context = allocator->context,
383 : });
384 154 : return (CCC_Entry){
385 : .type = NULL,
386 : .status = CCC_ENTRY_OCCUPIED,
387 : };
388 : }
389 112 : return (CCC_Entry){
390 56 : .type = erased,
391 : .status = CCC_ENTRY_OCCUPIED,
392 : };
393 210 : }
394 10 : return (CCC_Entry){
395 : .type = NULL,
396 : .status = CCC_ENTRY_VACANT,
397 : };
398 222 : }
399 :
400 : CCC_Entry
401 197 : CCC_tree_map_remove_key_value(
402 : CCC_Tree_map *const map,
403 : CCC_Tree_map_node *const type_output_intruder,
404 : CCC_Allocator const *const allocator
405 : ) {
406 197 : if (!map || !type_output_intruder || !allocator) {
407 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
408 : }
409 194 : struct Query const q = find(map, key_from_node(map, type_output_intruder));
410 194 : if (q.last_order != CCC_ORDER_EQUAL) {
411 3 : return (CCC_Entry){
412 : .type = NULL,
413 : .status = CCC_ENTRY_VACANT,
414 : };
415 : }
416 191 : void *const removed = remove_fixup(map, q.found);
417 191 : if (allocator->allocate) {
418 75 : void *const any_struct = struct_base(map, type_output_intruder);
419 75 : memcpy(any_struct, removed, map->sizeof_type);
420 225 : allocator->allocate((CCC_Allocator_arguments){
421 75 : .input = removed,
422 : .bytes = 0,
423 75 : .context = allocator->context,
424 : });
425 150 : return (CCC_Entry){
426 75 : .type = any_struct,
427 : .status = CCC_ENTRY_OCCUPIED,
428 : };
429 75 : }
430 232 : return (CCC_Entry){
431 116 : .type = removed,
432 : .status = CCC_ENTRY_OCCUPIED,
433 : };
434 197 : }
435 :
436 : CCC_Tree_map_entry *
437 112 : CCC_tree_map_and_modify(
438 : CCC_Tree_map_entry *e, CCC_Modifier const *const modifier
439 : ) {
440 112 : if (!e || !modifier) {
441 2 : return NULL;
442 : }
443 110 : if (modifier->modify && e->entry.status & CCC_ENTRY_OCCUPIED
444 110 : && e->entry.type) {
445 168 : modifier->modify((CCC_Arguments){
446 56 : .type = e->entry.type,
447 56 : .context = modifier->context,
448 : });
449 56 : }
450 110 : return e;
451 112 : }
452 :
453 : void *
454 26 : CCC_tree_map_unwrap(CCC_Tree_map_entry const *const e) {
455 26 : if (e && e->entry.status & CCC_ENTRY_OCCUPIED) {
456 15 : return e->entry.type;
457 : }
458 11 : return NULL;
459 26 : }
460 :
461 : CCC_Tribool
462 119 : CCC_tree_map_occupied(CCC_Tree_map_entry const *const e) {
463 119 : if (!e) {
464 1 : return CCC_TRIBOOL_ERROR;
465 : }
466 118 : return (e->entry.status & CCC_ENTRY_OCCUPIED) != 0;
467 119 : }
468 :
469 : CCC_Tribool
470 2 : CCC_tree_map_insert_error(CCC_Tree_map_entry const *const e) {
471 2 : if (!e) {
472 1 : return CCC_TRIBOOL_ERROR;
473 : }
474 1 : return (e->entry.status & CCC_ENTRY_INSERT_ERROR) != 0;
475 2 : }
476 :
477 : CCC_Entry_status
478 2 : CCC_tree_map_entry_status(CCC_Tree_map_entry const *const e) {
479 2 : return e ? e->entry.status : CCC_ENTRY_ARGUMENT_ERROR;
480 : }
481 :
482 : void *
483 10 : CCC_tree_map_begin(CCC_Tree_map const *map) {
484 10 : if (!map) {
485 1 : return NULL;
486 : }
487 9 : struct CCC_Tree_map_node *const m = min_max_from(map->root, L);
488 9 : return m == NULL ? NULL : struct_base(map, m);
489 10 : }
490 :
491 : void *
492 454 : CCC_tree_map_next(
493 : CCC_Tree_map const *const map,
494 : CCC_Tree_map_node const *const iterator_intruder
495 : ) {
496 454 : if (!map || !iterator_intruder) {
497 2 : return NULL;
498 : }
499 904 : struct CCC_Tree_map_node const *const n
500 452 : = next(map, iterator_intruder, INORDER);
501 452 : if (n == NULL) {
502 9 : return NULL;
503 : }
504 443 : return struct_base(map, n);
505 454 : }
506 :
507 : void *
508 4 : CCC_tree_map_reverse_begin(CCC_Tree_map const *const map) {
509 4 : if (!map) {
510 1 : return NULL;
511 : }
512 3 : struct CCC_Tree_map_node *const m = min_max_from(map->root, R);
513 3 : return m == NULL ? NULL : struct_base(map, m);
514 4 : }
515 :
516 : void *
517 261 : CCC_tree_map_end(CCC_Tree_map const *const) {
518 261 : return NULL;
519 : }
520 :
521 : void *
522 124 : CCC_tree_map_reverse_end(CCC_Tree_map const *const) {
523 124 : return NULL;
524 : }
525 :
526 : void *
527 146 : CCC_tree_map_reverse_next(
528 : CCC_Tree_map const *const map,
529 : CCC_Tree_map_node const *const iterator_intruder
530 : ) {
531 146 : if (!map || !iterator_intruder) {
532 2 : return NULL;
533 : }
534 288 : struct CCC_Tree_map_node const *const n
535 144 : = next(map, iterator_intruder, INORDER_REVERSE);
536 144 : return (n == NULL) ? NULL : struct_base(map, n);
537 146 : }
538 :
539 : CCC_Range
540 8 : CCC_tree_map_equal_range(
541 : CCC_Tree_map const *const map,
542 : void const *const begin_key,
543 : void const *const end_key
544 : ) {
545 8 : if (!map || !begin_key || !end_key) {
546 3 : return (CCC_Range){};
547 : }
548 5 : return equal_range(map, begin_key, end_key, INORDER);
549 8 : }
550 :
551 : CCC_Range_reverse
552 8 : CCC_tree_map_equal_range_reverse(
553 : CCC_Tree_map const *const map,
554 : void const *const reverse_begin_key,
555 : void const *const reverse_end_key
556 : ) {
557 8 : if (!map || !reverse_begin_key || !reverse_end_key) {
558 3 : return (CCC_Range_reverse){};
559 : }
560 5 : CCC_Range const range
561 5 : = equal_range(map, reverse_begin_key, reverse_end_key, INORDER_REVERSE);
562 15 : return (CCC_Range_reverse){
563 5 : .reverse_begin = range.begin,
564 5 : .reverse_end = range.end,
565 : };
566 8 : }
567 :
568 : CCC_Count
569 123 : CCC_tree_map_count(CCC_Tree_map const *const map) {
570 123 : if (!map) {
571 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
572 : }
573 122 : return (CCC_Count){.count = map->count};
574 123 : }
575 :
576 : CCC_Tribool
577 7 : CCC_tree_map_is_empty(CCC_Tree_map const *const map) {
578 7 : if (!map) {
579 1 : return CCC_TRIBOOL_ERROR;
580 : }
581 6 : return !map->count;
582 7 : }
583 :
584 : CCC_Tribool
585 1928 : CCC_tree_map_validate(CCC_Tree_map const *map) {
586 1928 : if (!map) {
587 1 : return CCC_TRIBOOL_ERROR;
588 : }
589 1927 : return validate(map);
590 1928 : }
591 :
592 : /** This is a linear time constant space deletion of tree nodes via left
593 : rotations so element fields are modified during progression of deletes. */
594 : CCC_Result
595 16 : CCC_tree_map_clear(
596 : CCC_Tree_map *const map,
597 : CCC_Destructor const *const destructor,
598 : CCC_Allocator const *const allocator
599 : ) {
600 16 : if (!map || !destructor || !allocator) {
601 3 : return CCC_RESULT_ARGUMENT_ERROR;
602 : }
603 13 : struct CCC_Tree_map_node *node = map->root;
604 1129 : while (node != NULL) {
605 1116 : if (node->branch[L] != NULL) {
606 530 : struct CCC_Tree_map_node *const left = node->branch[L];
607 530 : node->branch[L] = left->branch[R];
608 530 : left->branch[R] = node;
609 530 : node = left;
610 : continue;
611 530 : }
612 586 : struct CCC_Tree_map_node *const next = node->branch[R];
613 586 : node->branch[L] = node->branch[R] = NULL;
614 586 : node->parent = NULL;
615 586 : void *const type = struct_base(map, node);
616 586 : if (destructor->destroy) {
617 48 : destructor->destroy((CCC_Arguments){
618 16 : .type = type,
619 16 : .context = destructor->context,
620 : });
621 16 : }
622 586 : if (allocator->allocate) {
623 1758 : (void)allocator->allocate((CCC_Allocator_arguments){
624 586 : .input = type,
625 : .bytes = 0,
626 586 : .context = allocator->context,
627 : });
628 586 : }
629 586 : node = next;
630 586 : }
631 13 : return CCC_RESULT_OK;
632 16 : }
633 :
634 : /*========================= Private Interface ============================*/
635 :
636 : struct CCC_Tree_map_entry
637 98 : CCC_private_tree_map_entry(
638 : struct CCC_Tree_map const *const map, void const *const key
639 : ) {
640 98 : return entry(map, key);
641 98 : }
642 :
643 : void *
644 196 : CCC_private_tree_map_insert(
645 : struct CCC_Tree_map *const map,
646 : struct CCC_Tree_map_node *const parent,
647 : CCC_Order const last_order,
648 : struct CCC_Tree_map_node *const type_output_intruder
649 : ) {
650 196 : return insert(map, parent, last_order, type_output_intruder);
651 : }
652 :
653 : void *
654 87 : CCC_private_tree_map_key_in_slot(
655 : struct CCC_Tree_map const *const map, void const *const slot
656 : ) {
657 87 : return key_in_slot(map, slot);
658 : }
659 :
660 : struct CCC_Tree_map_node *
661 410 : CCC_private_tree_map_node_in_slot(
662 : struct CCC_Tree_map const *const map, void const *const slot
663 : ) {
664 410 : return elem_in_slot(map, slot);
665 : }
666 :
667 : /*========================= Static Helpers ============================*/
668 :
669 : static struct CCC_Tree_map_node *
670 159 : min_max_from(struct CCC_Tree_map_node *start, enum Link const dir) {
671 159 : if (start == NULL) {
672 1 : return start;
673 : }
674 362 : for (; start->branch[dir] != NULL; start = start->branch[dir]) {}
675 158 : return start;
676 159 : }
677 :
678 : static struct CCC_Tree_map_entry
679 1298 : entry(struct CCC_Tree_map const *const map, void const *const key) {
680 1298 : struct Query const q = find(map, key);
681 1298 : if (CCC_ORDER_EQUAL == q.last_order) {
682 2776 : return (struct CCC_Tree_map_entry){
683 694 : .map = (struct CCC_Tree_map *)map,
684 694 : .last_order = q.last_order,
685 1388 : .entry = {
686 694 : .type = struct_base(map, q.found),
687 : .status = CCC_ENTRY_OCCUPIED,
688 : },
689 : };
690 : }
691 2416 : return (struct CCC_Tree_map_entry){
692 604 : .map = (struct CCC_Tree_map *)map,
693 604 : .last_order = q.last_order,
694 1208 : .entry = {
695 604 : .type = struct_base(map, q.parent),
696 : .status = CCC_ENTRY_VACANT | CCC_ENTRY_NO_UNWRAP,
697 : },
698 : };
699 1298 : }
700 :
701 : static void *
702 1550 : maybe_allocate_insert(
703 : struct CCC_Tree_map *const map,
704 : struct CCC_Tree_map_node *const parent,
705 : CCC_Order const last_order,
706 : struct CCC_Tree_map_node *type_output_intruder,
707 : CCC_Allocator const *const allocator
708 : ) {
709 1550 : if (allocator->allocate) {
710 4122 : void *const new = allocator->allocate((CCC_Allocator_arguments){
711 : .input = NULL,
712 1374 : .bytes = map->sizeof_type,
713 1374 : .context = allocator->context,
714 : });
715 1374 : if (!new) {
716 5 : return NULL;
717 : }
718 1369 : memcpy(new, struct_base(map, type_output_intruder), map->sizeof_type);
719 1369 : type_output_intruder = elem_in_slot(map, new);
720 1374 : }
721 1545 : return insert(map, parent, last_order, type_output_intruder);
722 1550 : }
723 :
724 : static void *
725 1741 : insert(
726 : struct CCC_Tree_map *const map,
727 : struct CCC_Tree_map_node *const parent,
728 : CCC_Order const last_order,
729 : struct CCC_Tree_map_node *const type_output_intruder
730 : ) {
731 1741 : init_node(map, type_output_intruder);
732 1741 : if (!map->count) {
733 46 : map->root = type_output_intruder;
734 46 : ++map->count;
735 46 : return struct_base(map, type_output_intruder);
736 : }
737 1695 : assert(last_order == CCC_ORDER_GREATER || last_order == CCC_ORDER_LESSER);
738 1695 : CCC_Tribool rank_rule_break = CCC_FALSE;
739 1695 : if (parent) {
740 : rank_rule_break
741 1695 : = parent->branch[L] == NULL && parent->branch[R] == NULL;
742 1695 : parent->branch[CCC_ORDER_GREATER == last_order] = type_output_intruder;
743 1695 : }
744 1695 : type_output_intruder->parent = parent;
745 1695 : if (rank_rule_break) {
746 1498 : insert_fixup(map, parent, type_output_intruder);
747 1498 : }
748 1695 : ++map->count;
749 1695 : return struct_base(map, type_output_intruder);
750 1741 : }
751 :
752 : static struct Query
753 2986 : find(struct CCC_Tree_map const *const map, void const *const key) {
754 2986 : struct CCC_Tree_map_node const *parent = NULL;
755 2986 : struct Query q = {
756 : .last_order = CCC_ORDER_ERROR,
757 2986 : .found = map->root,
758 : };
759 15751 : while (q.found != NULL) {
760 13860 : q.last_order = order(map, key, q.found);
761 13860 : if (CCC_ORDER_EQUAL == q.last_order) {
762 1095 : return q;
763 : }
764 12765 : parent = q.found;
765 12765 : q.found = q.found->branch[CCC_ORDER_GREATER == q.last_order];
766 : }
767 : /* Type punning here OK as both union members have same type and size. */
768 1891 : q.parent = (struct CCC_Tree_map_node *)parent;
769 1891 : return q;
770 2986 : }
771 :
772 : static struct CCC_Tree_map_node *
773 603 : next(
774 : struct CCC_Tree_map const *const map [[maybe_unused]],
775 : struct CCC_Tree_map_node const *n,
776 : enum Link const traversal
777 : ) {
778 603 : if (!n) {
779 0 : return NULL;
780 : }
781 603 : assert(map->root->parent == NULL);
782 603 : if (n->branch[traversal]) {
783 : /* The goal is to get far left/right ASAP in any traversal. */
784 522 : for (n = n->branch[traversal]; n->branch[!traversal];
785 213 : n = n->branch[!traversal]) {}
786 309 : return (struct CCC_Tree_map_node *)n;
787 : }
788 600 : for (; n->parent && n->parent->branch[!traversal] != n; n = n->parent) {}
789 294 : return n->parent;
790 603 : }
791 :
792 : static CCC_Range
793 10 : equal_range(
794 : struct CCC_Tree_map const *const map,
795 : void const *const begin_key,
796 : void const *const end_key,
797 : enum Link const traversal
798 : ) {
799 10 : if (!map->count) {
800 2 : return (CCC_Range){};
801 : }
802 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
803 8 : struct Query b = find(map, begin_key);
804 8 : if (b.last_order == les_or_grt[traversal]) {
805 2 : b.found = next(map, b.found, traversal);
806 2 : }
807 8 : struct Query e = find(map, end_key);
808 8 : if (e.last_order != les_or_grt[!traversal]) {
809 5 : e.found = next(map, e.found, traversal);
810 5 : }
811 24 : return (CCC_Range){
812 8 : .begin = b.found == NULL ? NULL : struct_base(map, b.found),
813 8 : .end = e.found == NULL ? NULL : struct_base(map, e.found),
814 : };
815 10 : }
816 :
817 : static inline void
818 1741 : init_node(
819 : struct CCC_Tree_map *const map [[maybe_unused]],
820 : struct CCC_Tree_map_node *const e
821 : ) {
822 1741 : assert(e != NULL);
823 1741 : assert(map != NULL);
824 1741 : e->branch[L] = e->branch[R] = e->parent = NULL;
825 1741 : e->parity = 0;
826 1741 : }
827 :
828 : static inline void
829 94 : swap(void *const temp, void *const a, void *const b, size_t const sizeof_type) {
830 94 : if (a == b || !a || !b) {
831 0 : return;
832 : }
833 94 : (void)memcpy(temp, a, sizeof_type);
834 94 : (void)memcpy(a, b, sizeof_type);
835 94 : (void)memcpy(b, temp, sizeof_type);
836 188 : }
837 :
838 : static inline CCC_Order
839 125237 : order(
840 : struct CCC_Tree_map const *const map,
841 : void const *const key,
842 : struct CCC_Tree_map_node const *const node
843 : ) {
844 500948 : return map->comparator.compare((CCC_Key_comparator_arguments){
845 125237 : .key_left = key,
846 125237 : .type_right = struct_base(map, node),
847 125237 : .context = map->comparator.context,
848 : });
849 : }
850 :
851 : static inline void *
852 244699 : struct_base(
853 : struct CCC_Tree_map const *const map,
854 : struct CCC_Tree_map_node const *const e
855 : ) {
856 244699 : return e ? ((char *)e->branch) - map->type_intruder_offset : NULL;
857 : }
858 :
859 : static inline void *
860 112934 : key_from_node(
861 : struct CCC_Tree_map const *const map,
862 : struct CCC_Tree_map_node const *const node
863 : ) {
864 112934 : return node ? (char *)struct_base(map, node) + map->key_offset : NULL;
865 : }
866 :
867 : static inline void *
868 87 : key_in_slot(struct CCC_Tree_map const *const map, void const *const slot) {
869 87 : return slot ? (char *)slot + map->key_offset : NULL;
870 : }
871 :
872 : static inline struct CCC_Tree_map_node *
873 2432 : elem_in_slot(struct CCC_Tree_map const *const map, void const *const slot) {
874 2432 : return slot ? (struct CCC_Tree_map_node *)((char *)slot
875 2413 : + map->type_intruder_offset)
876 : : NULL;
877 : }
878 :
879 : /*======================= WAVL Tree Maintenance =========================*/
880 :
881 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
882 : Sen, and Tarjan (Fig. 2. pg 7). Assumes x's parent z is not null. */
883 : static void
884 1498 : insert_fixup(
885 : struct CCC_Tree_map *const map,
886 : struct CCC_Tree_map_node *z,
887 : struct CCC_Tree_map_node *x
888 : ) {
889 1498 : assert(z);
890 1498 : do {
891 2780 : promote(z);
892 2780 : x = z;
893 2780 : z = z->parent;
894 2780 : if (z == NULL) {
895 186 : return;
896 : }
897 2594 : } while (is_01_parent(x, z, sibling_of(x)));
898 :
899 1312 : if (!is_02_parent(x, z, sibling_of(x))) {
900 336 : return;
901 : }
902 976 : assert(x != NULL);
903 976 : assert(is_0_child(z, x));
904 976 : enum Link const p_to_x_dir = z->branch[R] == x;
905 976 : struct CCC_Tree_map_node *const y = x->branch[!p_to_x_dir];
906 976 : if (y == NULL || is_2_child(z, y)) {
907 877 : rotate(map, z, x, y, !p_to_x_dir);
908 877 : demote(z);
909 877 : } else {
910 99 : assert(is_1_child(z, y));
911 99 : double_rotate(map, z, x, y, p_to_x_dir);
912 99 : promote(y);
913 99 : demote(x);
914 99 : demote(z);
915 : }
916 2474 : }
917 :
918 : static void *
919 401 : remove_fixup(
920 : struct CCC_Tree_map *const map, struct CCC_Tree_map_node *const remove
921 : ) {
922 401 : struct CCC_Tree_map_node *y = NULL;
923 401 : struct CCC_Tree_map_node *x = NULL;
924 401 : struct CCC_Tree_map_node *p_of_xy = NULL;
925 401 : CCC_Tribool two_child = CCC_FALSE;
926 401 : if (remove->branch[L] == NULL || remove->branch[R] == NULL) {
927 254 : y = remove;
928 254 : p_of_xy = y->parent;
929 254 : x = y->branch[y->branch[L] == NULL];
930 254 : if (x) {
931 92 : x->parent = y->parent;
932 92 : }
933 254 : if (p_of_xy == NULL) {
934 10 : map->root = x;
935 10 : } else {
936 244 : p_of_xy->branch[p_of_xy->branch[R] == y] = x;
937 : }
938 254 : two_child = is_2_child(p_of_xy, y);
939 254 : } else {
940 147 : y = min_max_from(remove->branch[R], L);
941 147 : p_of_xy = y->parent;
942 147 : x = y->branch[y->branch[L] == NULL];
943 147 : if (x) {
944 38 : x->parent = y->parent;
945 38 : }
946 :
947 : /* Save if check and improve readability by assuming this is true. */
948 147 : assert(p_of_xy != NULL);
949 :
950 147 : two_child = is_2_child(p_of_xy, y);
951 147 : p_of_xy->branch[p_of_xy->branch[R] == y] = x;
952 147 : transplant(map, remove, y);
953 147 : if (remove == p_of_xy) {
954 62 : p_of_xy = y;
955 62 : }
956 : }
957 :
958 401 : if (p_of_xy != NULL) {
959 391 : if (two_child) {
960 210 : assert(p_of_xy != NULL);
961 210 : rebalance_3_child(map, p_of_xy, x);
962 391 : } else if (x == NULL && p_of_xy->branch[L] == p_of_xy->branch[R]) {
963 64 : assert(p_of_xy != NULL);
964 128 : CCC_Tribool const demote_makes_3_child
965 64 : = is_2_child(p_of_xy->parent, p_of_xy);
966 64 : demote(p_of_xy);
967 64 : if (demote_makes_3_child) {
968 36 : rebalance_3_child(map, p_of_xy->parent, p_of_xy);
969 36 : }
970 64 : }
971 391 : assert(!is_leaf(p_of_xy) || !parity(p_of_xy));
972 391 : }
973 401 : remove->branch[L] = remove->branch[R] = remove->parent = NULL;
974 401 : remove->parity = 0;
975 401 : --map->count;
976 802 : return struct_base(map, remove);
977 401 : }
978 :
979 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
980 : Sen, and Tarjan (Fig. 3. pg 8). */
981 : static void
982 246 : rebalance_3_child(
983 : struct CCC_Tree_map *const map,
984 : struct CCC_Tree_map_node *z,
985 : struct CCC_Tree_map_node *x
986 : ) {
987 246 : CCC_Tribool made_3_child = CCC_TRUE;
988 454 : while (z && made_3_child) {
989 311 : assert(z->branch[L] == x || z->branch[R] == x);
990 311 : struct CCC_Tree_map_node *const g = z->parent;
991 311 : struct CCC_Tree_map_node *const y = z->branch[z->branch[L] == x];
992 311 : made_3_child = g != NULL && is_2_child(g, z);
993 311 : if (is_2_child(z, y)) {
994 183 : demote(z);
995 311 : } else if (y && is_22_parent(y->branch[L], y, y->branch[R])) {
996 25 : demote(z);
997 25 : demote(y);
998 128 : } else if (y) {
999 103 : assert(is_1_child(z, y));
1000 103 : assert(is_3_child(z, x));
1001 103 : assert(!is_2_child(z, y));
1002 103 : assert(!is_22_parent(y->branch[L], y, y->branch[R]));
1003 103 : enum Link const z_to_x_dir = z->branch[R] == x;
1004 103 : struct CCC_Tree_map_node *const w = y->branch[!z_to_x_dir];
1005 103 : if (is_1_child(y, w)) {
1006 81 : rotate(map, z, y, y->branch[z_to_x_dir], z_to_x_dir);
1007 81 : promote(y);
1008 81 : demote(z);
1009 81 : if (is_leaf(z)) {
1010 24 : demote(z);
1011 24 : }
1012 81 : } else {
1013 : /* w is a 2-child and v will be a 1-child. */
1014 22 : struct CCC_Tree_map_node *const v = y->branch[z_to_x_dir];
1015 22 : assert(is_2_child(y, w));
1016 22 : assert(is_1_child(y, v));
1017 22 : double_rotate(map, z, y, v, !z_to_x_dir);
1018 22 : double_promote(v);
1019 22 : demote(y);
1020 22 : double_demote(z);
1021 : /* Optional "Rebalancing with Promotion," defined as follows:
1022 : if node z is a non-leaf 1,1 node, we promote it;
1023 : otherwise, if y is a non-leaf 1,1 node, we promote it.
1024 : (See Figure 4.) (Haeupler et. al. 2014, 17).
1025 : This reduces constants in some of theorems mentioned in the
1026 : paper but may not be worth doing. Rotations stay at 2 worst
1027 : case. Should revisit after more performance testing. */
1028 22 : if (!is_leaf(z)
1029 22 : && is_11_parent(z->branch[L], z, z->branch[R])) {
1030 2 : promote(z);
1031 22 : } else if (!is_leaf(y)
1032 20 : && is_11_parent(y->branch[L], y, y->branch[R])) {
1033 5 : promote(y);
1034 5 : }
1035 22 : }
1036 : /* Returning here confirms O(1) rotations for re-balance. */
1037 : return;
1038 103 : }
1039 208 : x = z;
1040 208 : z = g;
1041 311 : }
1042 246 : }
1043 :
1044 : static void
1045 147 : transplant(
1046 : struct CCC_Tree_map *const map,
1047 : struct CCC_Tree_map_node *const remove,
1048 : struct CCC_Tree_map_node *const replacement
1049 : ) {
1050 147 : assert(remove != NULL);
1051 147 : assert(replacement != NULL);
1052 147 : replacement->parent = remove->parent;
1053 147 : if (remove->parent == NULL) {
1054 18 : map->root = replacement;
1055 18 : } else {
1056 129 : remove->parent->branch[remove->parent->branch[R] == remove]
1057 258 : = replacement;
1058 : }
1059 147 : if (remove->branch[R]) {
1060 104 : remove->branch[R]->parent = replacement;
1061 104 : }
1062 147 : if (remove->branch[L]) {
1063 147 : remove->branch[L]->parent = replacement;
1064 147 : }
1065 147 : replacement->branch[R] = remove->branch[R];
1066 147 : replacement->branch[L] = remove->branch[L];
1067 147 : replacement->parity
1068 294 : = (typeof((struct CCC_Tree_map_node){}.parity))parity(remove);
1069 147 : }
1070 :
1071 : /** A single rotation is symmetric. Here is the right case. Lowercase are nodes
1072 : and uppercase are arbitrary subtrees.
1073 : z x
1074 : ╭──┴──╮ ╭──┴──╮
1075 : x C A z
1076 : ╭─┴─╮ -> ╭─┴─╮
1077 : A y y C
1078 : │ │
1079 : B B
1080 :
1081 : Taking a link as input allows us to code both symmetrical cases at once. */
1082 : static void
1083 958 : rotate(
1084 : struct CCC_Tree_map *const map,
1085 : struct CCC_Tree_map_node *const z,
1086 : struct CCC_Tree_map_node *const x,
1087 : struct CCC_Tree_map_node *const y,
1088 : enum Link const dir
1089 : ) {
1090 958 : assert(z != NULL);
1091 958 : struct CCC_Tree_map_node *const g = z->parent;
1092 958 : x->parent = g;
1093 958 : if (g == NULL) {
1094 127 : map->root = x;
1095 127 : } else {
1096 831 : g->branch[g->branch[R] == z] = x;
1097 : }
1098 958 : x->branch[dir] = z;
1099 958 : z->parent = x;
1100 958 : z->branch[!dir] = y;
1101 958 : if (y) {
1102 417 : y->parent = z;
1103 417 : }
1104 958 : }
1105 :
1106 : /** A double rotation shouldn't actually be two calls to rotate because that
1107 : would invoke pointless memory writes. Here is an example of double right.
1108 : Lowercase are nodes and uppercase are arbitrary subtrees.
1109 :
1110 : z y
1111 : ╭──┴──╮ ╭──┴──╮
1112 : x D x z
1113 : ╭─┴─╮ -> ╭─┴─╮ ╭─┴─╮
1114 : A y A B C D
1115 : ╭─┴─╮
1116 : B C
1117 :
1118 : Taking a link as input allows us to code both symmetrical cases at once. */
1119 : static void
1120 121 : double_rotate(
1121 : struct CCC_Tree_map *const map,
1122 : struct CCC_Tree_map_node *const z,
1123 : struct CCC_Tree_map_node *const x,
1124 : struct CCC_Tree_map_node *const y,
1125 : enum Link const dir
1126 : ) {
1127 121 : assert(z != NULL);
1128 121 : assert(x != NULL);
1129 121 : assert(y != NULL);
1130 121 : struct CCC_Tree_map_node *const g = z->parent;
1131 121 : y->parent = g;
1132 121 : if (g == NULL) {
1133 7 : map->root = y;
1134 7 : } else {
1135 114 : g->branch[g->branch[R] == z] = y;
1136 : }
1137 121 : x->branch[!dir] = y->branch[dir];
1138 121 : if (y->branch[dir]) {
1139 33 : y->branch[dir]->parent = x;
1140 33 : }
1141 121 : y->branch[dir] = x;
1142 121 : x->parent = y;
1143 :
1144 121 : z->branch[dir] = y->branch[!dir];
1145 121 : if (y->branch[!dir]) {
1146 34 : y->branch[!dir]->parent = z;
1147 34 : }
1148 121 : y->branch[!dir] = z;
1149 121 : z->parent = y;
1150 121 : }
1151 :
1152 : /* Returns the parity of a node either 0 or 1. A NULL node has a parity of 1 aka
1153 : CCC_TRUE. */
1154 : static inline CCC_Tribool
1155 21243 : parity(struct CCC_Tree_map_node const *const x) {
1156 21243 : return x ? (CCC_Tribool)x->parity : CCC_TRUE;
1157 : }
1158 :
1159 : /* Returns true for rank difference 0 (rule break) between the parent and node.
1160 : p
1161 : 1╭─╯
1162 : x */
1163 : [[maybe_unused]] static inline CCC_Tribool
1164 976 : is_0_child(
1165 : struct CCC_Tree_map_node const *const p,
1166 : struct CCC_Tree_map_node const *const x
1167 : ) {
1168 976 : return parity(p) == parity(x);
1169 : }
1170 :
1171 : /* Returns true for rank difference 1 between the parent and node.
1172 : p
1173 : 1/
1174 : x*/
1175 : static inline CCC_Tribool
1176 327 : is_1_child(
1177 : struct CCC_Tree_map_node const *const p,
1178 : struct CCC_Tree_map_node const *const x
1179 : ) {
1180 327 : return parity(p) != parity(x);
1181 : }
1182 :
1183 : /* Returns true for rank difference 2 between the parent and node.
1184 : p
1185 : 2╭─╯
1186 : x */
1187 : static inline CCC_Tribool
1188 1638 : is_2_child(
1189 : struct CCC_Tree_map_node const *const p,
1190 : struct CCC_Tree_map_node const *const x
1191 : ) {
1192 1638 : return parity(p) == parity(x);
1193 : }
1194 :
1195 : /* Returns true for rank difference 3 between the parent and node.
1196 : p
1197 : 3╭─╯
1198 : x */
1199 : [[maybe_unused]] static inline CCC_Tribool
1200 103 : is_3_child(
1201 : struct CCC_Tree_map_node const *const p,
1202 : struct CCC_Tree_map_node const *const x
1203 : ) {
1204 103 : return parity(p) != parity(x);
1205 : }
1206 :
1207 : /* Returns true if a parent is a 0,1 or 1,0 node, which is not allowed. Either
1208 : child may be the sentinel node which has a parity of 1 and rank -1.
1209 : p
1210 : 0╭─┴─╮1
1211 : x y */
1212 : static inline CCC_Tribool
1213 2594 : is_01_parent(
1214 : struct CCC_Tree_map_node const *const x,
1215 : struct CCC_Tree_map_node const *const p,
1216 : struct CCC_Tree_map_node const *const y
1217 : ) {
1218 4785 : return (!parity(x) && !parity(p) && parity(y))
1219 2594 : || (parity(x) && parity(p) && !parity(y));
1220 : }
1221 :
1222 : /* Returns true if a parent is a 1,1 node. Either child may be the sentinel
1223 : node which has a parity of 1 and rank -1.
1224 : p
1225 : 1╭─┴─╮1
1226 : x y */
1227 : static inline CCC_Tribool
1228 12 : is_11_parent(
1229 : struct CCC_Tree_map_node const *const x,
1230 : struct CCC_Tree_map_node const *const p,
1231 : struct CCC_Tree_map_node const *const y
1232 : ) {
1233 18 : return (!parity(x) && parity(p) && !parity(y))
1234 12 : || (parity(x) && !parity(p) && parity(y));
1235 : }
1236 :
1237 : /* Returns true if a parent is a 0,2 or 2,0 node, which is not allowed. Either
1238 : child may be the sentinel node which has a parity of 1 and rank -1.
1239 : p
1240 : 0╭─┴─╮2
1241 : x y */
1242 : static inline CCC_Tribool
1243 1312 : is_02_parent(
1244 : struct CCC_Tree_map_node const *const x,
1245 : struct CCC_Tree_map_node const *const p,
1246 : struct CCC_Tree_map_node const *const y
1247 : ) {
1248 1312 : return (parity(x) == parity(p)) && (parity(p) == parity(y));
1249 : }
1250 :
1251 : /* Returns true if a parent is a 2,2 or 2,2 node, which is allowed. 2,2 nodes
1252 : are allowed in a WAVL tree but the absence of any 2,2 nodes is the exact
1253 : equivalent of a normal AVL tree which can occur if only insertions occur
1254 : for a WAVL tree. Either child may be the sentinel node which has a parity of
1255 : 1 and rank -1.
1256 : p
1257 : 2╭─┴─╮2
1258 : x y */
1259 : static inline CCC_Tribool
1260 231 : is_22_parent(
1261 : struct CCC_Tree_map_node const *const x,
1262 : struct CCC_Tree_map_node const *const p,
1263 : struct CCC_Tree_map_node const *const y
1264 : ) {
1265 231 : return (parity(x) == parity(p)) && (parity(p) == parity(y));
1266 : }
1267 :
1268 : static inline void
1269 4466 : promote(struct CCC_Tree_map_node *const x) {
1270 4466 : if (x) {
1271 4466 : x->parity = !x->parity;
1272 4466 : }
1273 4466 : }
1274 :
1275 : static inline void
1276 1499 : demote(struct CCC_Tree_map_node *const x) {
1277 1499 : promote(x);
1278 1499 : }
1279 :
1280 : /* One could imagine non-parity based rank tracking making this function
1281 : meaningful, but two parity changes are the same as a no-op. Leave for
1282 : clarity of what the code is meant to do through certain sections. */
1283 : static inline void
1284 22 : double_promote(struct CCC_Tree_map_node *const) {
1285 22 : }
1286 :
1287 : /* One could imagine non-parity based rank tracking making this function
1288 : meaningful, but two parity changes are the same as a no-op. Leave for
1289 : clarity of what the code is meant to do through certain sections. */
1290 : static inline void
1291 22 : double_demote(struct CCC_Tree_map_node *const) {
1292 22 : }
1293 :
1294 : static inline CCC_Tribool
1295 514 : is_leaf(struct CCC_Tree_map_node const *const x) {
1296 514 : return x->branch[L] == NULL && x->branch[R] == NULL;
1297 : }
1298 :
1299 : static inline struct CCC_Tree_map_node *
1300 3906 : sibling_of(struct CCC_Tree_map_node const *const x) {
1301 3906 : if (x->parent == NULL) {
1302 0 : return NULL;
1303 : }
1304 : /* We want the sibling so we need the truthy value to be opposite of x. */
1305 3906 : return x->parent->branch[x->parent->branch[L] == x];
1306 3906 : }
1307 :
1308 : /*=========================== Validation ===============================*/
1309 :
1310 : /* NOLINTBEGIN(*misc-no-recursion) */
1311 :
1312 : /** @internal */
1313 : struct Tree_range {
1314 : struct CCC_Tree_map_node const *low;
1315 : struct CCC_Tree_map_node const *root;
1316 : struct CCC_Tree_map_node const *high;
1317 : };
1318 :
1319 : static size_t
1320 131079 : recursive_count(
1321 : struct CCC_Tree_map const *const map,
1322 : struct CCC_Tree_map_node const *const r
1323 : ) {
1324 131079 : if (r == NULL) {
1325 66503 : return 0;
1326 : }
1327 129152 : return 1 + recursive_count(map, r->branch[R])
1328 64576 : + recursive_count(map, r->branch[L]);
1329 131079 : }
1330 :
1331 : static CCC_Tribool
1332 131079 : are_subtrees_valid(struct CCC_Tree_map const *t, struct Tree_range const r) {
1333 131079 : if (!r.root) {
1334 66503 : return CCC_TRUE;
1335 : }
1336 64576 : if (r.low
1337 64576 : && order(t, key_from_node(t, r.low), r.root) != CCC_ORDER_LESSER) {
1338 0 : return CCC_FALSE;
1339 : }
1340 64576 : if (r.high
1341 64576 : && order(t, key_from_node(t, r.high), r.root) != CCC_ORDER_GREATER) {
1342 0 : return CCC_FALSE;
1343 : }
1344 129152 : return are_subtrees_valid(
1345 64576 : t,
1346 258304 : (struct Tree_range){
1347 64576 : .low = r.low,
1348 64576 : .root = r.root->branch[L],
1349 64576 : .high = r.root,
1350 : }
1351 : )
1352 64576 : && are_subtrees_valid(
1353 64576 : t,
1354 258304 : (struct Tree_range){
1355 64576 : .low = r.root,
1356 64576 : .root = r.root->branch[R],
1357 64576 : .high = r.high,
1358 : }
1359 : );
1360 131079 : }
1361 :
1362 : static CCC_Tribool
1363 131079 : is_storing_parent(
1364 : struct CCC_Tree_map const *const t,
1365 : struct CCC_Tree_map_node const *const parent,
1366 : struct CCC_Tree_map_node const *const root
1367 : ) {
1368 131079 : if (root == NULL) {
1369 66503 : return CCC_TRUE;
1370 : }
1371 64576 : if (root->parent != parent) {
1372 0 : return CCC_FALSE;
1373 : }
1374 129152 : return is_storing_parent(t, root, root->branch[L])
1375 64576 : && is_storing_parent(t, root, root->branch[R]);
1376 131079 : }
1377 :
1378 : static CCC_Tribool
1379 1927 : validate(struct CCC_Tree_map const *const map) {
1380 1927 : if (!are_subtrees_valid(
1381 1927 : map,
1382 3854 : (struct Tree_range){
1383 : .low = NULL,
1384 1927 : .root = map->root,
1385 : .high = NULL,
1386 : }
1387 : )) {
1388 0 : return CCC_FALSE;
1389 : }
1390 1927 : if (recursive_count(map, map->root) != map->count) {
1391 0 : return CCC_FALSE;
1392 : }
1393 1927 : if (!is_storing_parent(map, NULL, map->root)) {
1394 0 : return CCC_FALSE;
1395 : }
1396 1927 : return CCC_TRUE;
1397 1927 : }
1398 :
1399 : /* NOLINTEND(*misc-no-recursion) */
1400 :
1401 : /* Below you will find the required license for code that inspired the
1402 : implementation of a WAVL tree in this repository for some map containers.
1403 :
1404 : The original repository can be found here:
1405 :
1406 : https://github.com/pvachon/wavl_tree
1407 :
1408 : The original implementation has be changed to eliminate left and right cases
1409 : and work within the C Container Collection memory framework.
1410 :
1411 : Redistribution and use in source and binary forms, with or without
1412 : modification, are permitted provided that the following conditions are met:
1413 :
1414 : 1. Redistributions of source code must retain the above copyright notice, this
1415 : list of conditions and the following disclaimer.
1416 :
1417 : 2. Redistributions in binary form must reproduce the above copyright notice,
1418 : this list of conditions and the following disclaimer in the documentation
1419 : and/or other materials provided with the distribution.
1420 :
1421 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1422 : AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1423 : IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1424 : DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
1425 : FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1426 : DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
1427 : SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1428 : CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
1429 : OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1430 : OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
|
