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 78 : *type_intruder = *q.found;
216 78 : void *const found = struct_base(map, q.found);
217 78 : void *const any_struct = struct_base(map, type_intruder);
218 78 : void *const old_val = struct_base(map, temp_intruder);
219 78 : swap(old_val, found, any_struct, map->sizeof_type);
220 156 : type_intruder->branch[L] = type_intruder->branch[R]
221 156 : = type_intruder->parent = NULL;
222 156 : temp_intruder->branch[L] = temp_intruder->branch[R]
223 156 : = temp_intruder->parent = NULL;
224 156 : return (CCC_Entry){
225 78 : .type = old_val,
226 : .status = CCC_ENTRY_OCCUPIED,
227 : };
228 78 : }
229 930 : if (!maybe_allocate_insert(
230 930 : 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 929 : 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 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 202 : 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 202 : if (!map || !type_output_intruder || !allocator) {
407 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
408 : }
409 199 : struct Query const q = find(map, key_from_node(map, type_output_intruder));
410 199 : if (q.last_order != CCC_ORDER_EQUAL) {
411 3 : return (CCC_Entry){
412 : .type = NULL,
413 : .status = CCC_ENTRY_VACANT,
414 : };
415 : }
416 196 : void *const removed = remove_fixup(map, q.found);
417 196 : if (allocator->allocate) {
418 80 : void *const any_struct = struct_base(map, type_output_intruder);
419 80 : memcpy(any_struct, removed, map->sizeof_type);
420 240 : allocator->allocate((CCC_Allocator_arguments){
421 80 : .input = removed,
422 : .bytes = 0,
423 80 : .context = allocator->context,
424 : });
425 160 : return (CCC_Entry){
426 80 : .type = any_struct,
427 : .status = CCC_ENTRY_OCCUPIED,
428 : };
429 80 : }
430 232 : return (CCC_Entry){
431 116 : .type = removed,
432 : .status = CCC_ENTRY_OCCUPIED,
433 : };
434 202 : }
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 491 : CCC_tree_map_next(
493 : CCC_Tree_map const *const map,
494 : CCC_Tree_map_node const *const iterator_intruder
495 : ) {
496 491 : if (!map || !iterator_intruder) {
497 2 : return NULL;
498 : }
499 978 : struct CCC_Tree_map_node const *const n
500 489 : = next(map, iterator_intruder, INORDER);
501 489 : if (n == NULL) {
502 9 : return NULL;
503 : }
504 480 : return struct_base(map, n);
505 491 : }
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 277 : CCC_tree_map_end(CCC_Tree_map const *const) {
518 277 : return NULL;
519 : }
520 :
521 : void *
522 140 : CCC_tree_map_reverse_end(CCC_Tree_map const *const) {
523 140 : return NULL;
524 : }
525 :
526 : void *
527 162 : CCC_tree_map_reverse_next(
528 : CCC_Tree_map const *const map,
529 : CCC_Tree_map_node const *const iterator_intruder
530 : ) {
531 162 : if (!map || !iterator_intruder) {
532 2 : return NULL;
533 : }
534 320 : struct CCC_Tree_map_node const *const n
535 160 : = next(map, iterator_intruder, INORDER_REVERSE);
536 160 : return (n == NULL) ? NULL : struct_base(map, n);
537 162 : }
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 122 : CCC_tree_map_count(CCC_Tree_map const *const map) {
570 122 : if (!map) {
571 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
572 : }
573 121 : return (CCC_Count){.count = map->count};
574 122 : }
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 1933 : CCC_tree_map_validate(CCC_Tree_map const *map) {
586 1933 : if (!map) {
587 1 : return CCC_TRIBOOL_ERROR;
588 : }
589 1932 : return validate(map);
590 1933 : }
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 : map->count = 0;
632 13 : map->root = NULL;
633 13 : return CCC_RESULT_OK;
634 16 : }
635 :
636 : /*========================= Private Interface ============================*/
637 :
638 : struct CCC_Tree_map_entry
639 98 : CCC_private_tree_map_entry(
640 : struct CCC_Tree_map const *const map, void const *const key
641 : ) {
642 98 : return entry(map, key);
643 98 : }
644 :
645 : void *
646 196 : CCC_private_tree_map_insert(
647 : struct CCC_Tree_map *const map,
648 : struct CCC_Tree_map_node *const parent,
649 : CCC_Order const last_order,
650 : struct CCC_Tree_map_node *const type_output_intruder
651 : ) {
652 196 : return insert(map, parent, last_order, type_output_intruder);
653 : }
654 :
655 : void *
656 87 : CCC_private_tree_map_key_in_slot(
657 : struct CCC_Tree_map const *const map, void const *const slot
658 : ) {
659 87 : return key_in_slot(map, slot);
660 : }
661 :
662 : struct CCC_Tree_map_node *
663 410 : CCC_private_tree_map_node_in_slot(
664 : struct CCC_Tree_map const *const map, void const *const slot
665 : ) {
666 410 : return elem_in_slot(map, slot);
667 : }
668 :
669 : /*========================= Static Helpers ============================*/
670 :
671 : static struct CCC_Tree_map_node *
672 161 : min_max_from(struct CCC_Tree_map_node *start, enum Link const dir) {
673 161 : if (start == NULL) {
674 1 : return start;
675 : }
676 383 : for (; start->branch[dir] != NULL; start = start->branch[dir]) {}
677 160 : return start;
678 161 : }
679 :
680 : static struct CCC_Tree_map_entry
681 1303 : entry(struct CCC_Tree_map const *const map, void const *const key) {
682 1303 : struct Query const q = find(map, key);
683 1303 : if (CCC_ORDER_EQUAL == q.last_order) {
684 2776 : return (struct CCC_Tree_map_entry){
685 694 : .map = (struct CCC_Tree_map *)map,
686 694 : .last_order = q.last_order,
687 1388 : .entry = {
688 694 : .type = struct_base(map, q.found),
689 : .status = CCC_ENTRY_OCCUPIED,
690 : },
691 : };
692 : }
693 2436 : return (struct CCC_Tree_map_entry){
694 609 : .map = (struct CCC_Tree_map *)map,
695 609 : .last_order = q.last_order,
696 1218 : .entry = {
697 609 : .type = struct_base(map, q.parent),
698 : .status = CCC_ENTRY_VACANT | CCC_ENTRY_NO_UNWRAP,
699 : },
700 : };
701 1303 : }
702 :
703 : static void *
704 1571 : maybe_allocate_insert(
705 : struct CCC_Tree_map *const map,
706 : struct CCC_Tree_map_node *const parent,
707 : CCC_Order const last_order,
708 : struct CCC_Tree_map_node *type_output_intruder,
709 : CCC_Allocator const *const allocator
710 : ) {
711 1571 : if (allocator->allocate) {
712 4185 : void *const new = allocator->allocate((CCC_Allocator_arguments){
713 : .input = NULL,
714 1395 : .bytes = map->sizeof_type,
715 1395 : .context = allocator->context,
716 : });
717 1395 : if (!new) {
718 5 : return NULL;
719 : }
720 1390 : memcpy(new, struct_base(map, type_output_intruder), map->sizeof_type);
721 1390 : type_output_intruder = elem_in_slot(map, new);
722 1395 : }
723 1566 : return insert(map, parent, last_order, type_output_intruder);
724 1571 : }
725 :
726 : static void *
727 1762 : insert(
728 : struct CCC_Tree_map *const map,
729 : struct CCC_Tree_map_node *const parent,
730 : CCC_Order const last_order,
731 : struct CCC_Tree_map_node *const type_output_intruder
732 : ) {
733 1762 : init_node(map, type_output_intruder);
734 1762 : if (!map->count) {
735 46 : map->root = type_output_intruder;
736 46 : ++map->count;
737 46 : return struct_base(map, type_output_intruder);
738 : }
739 1716 : assert(last_order == CCC_ORDER_GREATER || last_order == CCC_ORDER_LESSER);
740 1716 : CCC_Tribool rank_rule_break = CCC_FALSE;
741 1716 : if (parent) {
742 : rank_rule_break
743 1716 : = parent->branch[L] == NULL && parent->branch[R] == NULL;
744 1716 : parent->branch[CCC_ORDER_GREATER == last_order] = type_output_intruder;
745 1716 : }
746 1716 : type_output_intruder->parent = parent;
747 1716 : if (rank_rule_break) {
748 1536 : insert_fixup(map, parent, type_output_intruder);
749 1536 : }
750 1716 : ++map->count;
751 1716 : return struct_base(map, type_output_intruder);
752 1762 : }
753 :
754 : static struct Query
755 2996 : find(struct CCC_Tree_map const *const map, void const *const key) {
756 2996 : struct CCC_Tree_map_node const *parent = NULL;
757 2996 : struct Query q = {
758 : .last_order = CCC_ORDER_ERROR,
759 2996 : .found = map->root,
760 : };
761 15951 : while (q.found != NULL) {
762 14039 : q.last_order = order(map, key, q.found);
763 14039 : if (CCC_ORDER_EQUAL == q.last_order) {
764 1084 : return q;
765 : }
766 12955 : parent = q.found;
767 12955 : q.found = q.found->branch[CCC_ORDER_GREATER == q.last_order];
768 : }
769 : /* Type punning here OK as both union members have same type and size. */
770 1912 : q.parent = (struct CCC_Tree_map_node *)parent;
771 1912 : return q;
772 2996 : }
773 :
774 : static struct CCC_Tree_map_node *
775 656 : next(
776 : struct CCC_Tree_map const *const map [[maybe_unused]],
777 : struct CCC_Tree_map_node const *n,
778 : enum Link const traversal
779 : ) {
780 656 : if (!n) {
781 0 : return NULL;
782 : }
783 656 : assert(map->root->parent == NULL);
784 656 : if (n->branch[traversal]) {
785 563 : for (n = n->branch[traversal]; n->branch[!traversal];
786 230 : n = n->branch[!traversal]) {}
787 333 : return (struct CCC_Tree_map_node *)n;
788 : }
789 653 : for (; n->parent && n->parent->branch[!traversal] != n; n = n->parent) {}
790 323 : return n->parent;
791 656 : }
792 :
793 : static CCC_Range
794 10 : equal_range(
795 : struct CCC_Tree_map const *const map,
796 : void const *const begin_key,
797 : void const *const end_key,
798 : enum Link const traversal
799 : ) {
800 10 : if (!map->count) {
801 2 : return (CCC_Range){};
802 : }
803 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
804 8 : struct Query b = find(map, begin_key);
805 8 : if (b.last_order == les_or_grt[traversal]) {
806 2 : b.found = next(map, b.found, traversal);
807 2 : }
808 8 : struct Query e = find(map, end_key);
809 8 : if (e.last_order != les_or_grt[!traversal]) {
810 5 : e.found = next(map, e.found, traversal);
811 5 : }
812 24 : return (CCC_Range){
813 8 : .begin = b.found == NULL ? NULL : struct_base(map, b.found),
814 8 : .end = e.found == NULL ? NULL : struct_base(map, e.found),
815 : };
816 10 : }
817 :
818 : static inline void
819 1762 : init_node(
820 : struct CCC_Tree_map *const map [[maybe_unused]],
821 : struct CCC_Tree_map_node *const e
822 : ) {
823 1762 : assert(e != NULL);
824 1762 : assert(map != NULL);
825 1762 : e->branch[L] = e->branch[R] = e->parent = NULL;
826 1762 : e->parity = 0;
827 1762 : }
828 :
829 : static inline void
830 78 : swap(void *const temp, void *const a, void *const b, size_t const sizeof_type) {
831 78 : if (a == b || !a || !b) {
832 0 : return;
833 : }
834 78 : (void)memcpy(temp, a, sizeof_type);
835 78 : (void)memcpy(a, b, sizeof_type);
836 78 : (void)memcpy(b, temp, sizeof_type);
837 156 : }
838 :
839 : static inline CCC_Order
840 128231 : order(
841 : struct CCC_Tree_map const *const map,
842 : void const *const key,
843 : struct CCC_Tree_map_node const *const node
844 : ) {
845 512924 : return map->comparator.compare((CCC_Key_comparator_arguments){
846 128231 : .key_left = key,
847 128231 : .type_right = struct_base(map, node),
848 128231 : .context = map->comparator.context,
849 : });
850 : }
851 :
852 : static inline void *
853 250575 : struct_base(
854 : struct CCC_Tree_map const *const map,
855 : struct CCC_Tree_map_node const *const e
856 : ) {
857 250575 : return e ? ((char *)e->branch) - map->type_intruder_offset : NULL;
858 : }
859 :
860 : static inline void *
861 115754 : key_from_node(
862 : struct CCC_Tree_map const *const map,
863 : struct CCC_Tree_map_node const *const node
864 : ) {
865 115754 : return node ? (char *)struct_base(map, node) + map->key_offset : NULL;
866 : }
867 :
868 : static inline void *
869 87 : key_in_slot(struct CCC_Tree_map const *const map, void const *const slot) {
870 87 : return slot ? (char *)slot + map->key_offset : NULL;
871 : }
872 :
873 : static inline struct CCC_Tree_map_node *
874 2458 : elem_in_slot(struct CCC_Tree_map const *const map, void const *const slot) {
875 2458 : return slot ? (struct CCC_Tree_map_node *)((char *)slot
876 2439 : + map->type_intruder_offset)
877 : : NULL;
878 : }
879 :
880 : /*======================= WAVL Tree Maintenance =========================*/
881 :
882 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
883 : Sen, and Tarjan (Fig. 2. pg 7). Assumes x's parent z is not null. */
884 : static void
885 1536 : insert_fixup(
886 : struct CCC_Tree_map *const map,
887 : struct CCC_Tree_map_node *z,
888 : struct CCC_Tree_map_node *x
889 : ) {
890 1536 : assert(z);
891 1536 : do {
892 2850 : promote(z);
893 2850 : x = z;
894 2850 : z = z->parent;
895 2850 : if (z == NULL) {
896 186 : return;
897 : }
898 2664 : } while (is_01_parent(x, z, sibling_of(x)));
899 :
900 1350 : if (!is_02_parent(x, z, sibling_of(x))) {
901 317 : return;
902 : }
903 1033 : assert(x != NULL);
904 1033 : assert(is_0_child(z, x));
905 1033 : enum Link const p_to_x_dir = z->branch[R] == x;
906 1033 : struct CCC_Tree_map_node *const y = x->branch[!p_to_x_dir];
907 1033 : if (y == NULL || is_2_child(z, y)) {
908 912 : rotate(map, z, x, y, !p_to_x_dir);
909 912 : demote(z);
910 912 : } else {
911 121 : assert(is_1_child(z, y));
912 121 : double_rotate(map, z, x, y, p_to_x_dir);
913 121 : promote(y);
914 121 : demote(x);
915 121 : demote(z);
916 : }
917 2569 : }
918 :
919 : static void *
920 406 : remove_fixup(
921 : struct CCC_Tree_map *const map, struct CCC_Tree_map_node *const remove
922 : ) {
923 406 : struct CCC_Tree_map_node *y = NULL;
924 406 : struct CCC_Tree_map_node *x = NULL;
925 406 : struct CCC_Tree_map_node *p_of_xy = NULL;
926 406 : CCC_Tribool two_child = CCC_FALSE;
927 406 : if (remove->branch[L] == NULL || remove->branch[R] == NULL) {
928 257 : y = remove;
929 257 : p_of_xy = y->parent;
930 257 : x = y->branch[y->branch[L] == NULL];
931 257 : if (x) {
932 84 : x->parent = y->parent;
933 84 : }
934 257 : if (p_of_xy == NULL) {
935 10 : map->root = x;
936 10 : } else {
937 247 : p_of_xy->branch[p_of_xy->branch[R] == y] = x;
938 : }
939 257 : two_child = is_2_child(p_of_xy, y);
940 257 : } else {
941 149 : y = min_max_from(remove->branch[R], L);
942 149 : p_of_xy = y->parent;
943 149 : x = y->branch[y->branch[L] == NULL];
944 149 : if (x) {
945 42 : x->parent = y->parent;
946 42 : }
947 :
948 : /* Save if check and improve readability by assuming this is true. */
949 149 : assert(p_of_xy != NULL);
950 :
951 149 : two_child = is_2_child(p_of_xy, y);
952 149 : p_of_xy->branch[p_of_xy->branch[R] == y] = x;
953 149 : transplant(map, remove, y);
954 149 : if (remove == p_of_xy) {
955 53 : p_of_xy = y;
956 53 : }
957 : }
958 :
959 406 : if (p_of_xy != NULL) {
960 396 : if (two_child) {
961 200 : assert(p_of_xy != NULL);
962 200 : rebalance_3_child(map, p_of_xy, x);
963 396 : } else if (x == NULL && p_of_xy->branch[L] == p_of_xy->branch[R]) {
964 68 : assert(p_of_xy != NULL);
965 136 : CCC_Tribool const demote_makes_3_child
966 68 : = is_2_child(p_of_xy->parent, p_of_xy);
967 68 : demote(p_of_xy);
968 68 : if (demote_makes_3_child) {
969 39 : rebalance_3_child(map, p_of_xy->parent, p_of_xy);
970 39 : }
971 68 : }
972 396 : assert(!is_leaf(p_of_xy) || !parity(p_of_xy));
973 396 : }
974 406 : remove->branch[L] = remove->branch[R] = remove->parent = NULL;
975 406 : remove->parity = 0;
976 406 : --map->count;
977 812 : return struct_base(map, remove);
978 406 : }
979 :
980 : /** Follows the specification in the "Rank-Balanced Trees" paper by Haeupler,
981 : Sen, and Tarjan (Fig. 3. pg 8). */
982 : static void
983 239 : rebalance_3_child(
984 : struct CCC_Tree_map *const map,
985 : struct CCC_Tree_map_node *z,
986 : struct CCC_Tree_map_node *x
987 : ) {
988 239 : CCC_Tribool made_3_child = CCC_TRUE;
989 432 : while (z && made_3_child) {
990 295 : assert(z->branch[L] == x || z->branch[R] == x);
991 295 : struct CCC_Tree_map_node *const g = z->parent;
992 295 : struct CCC_Tree_map_node *const y = z->branch[z->branch[L] == x];
993 295 : made_3_child = g != NULL && is_2_child(g, z);
994 295 : if (is_2_child(z, y)) {
995 153 : demote(z);
996 295 : } else if (y && is_22_parent(y->branch[L], y, y->branch[R])) {
997 40 : demote(z);
998 40 : demote(y);
999 142 : } else if (y) {
1000 102 : assert(is_1_child(z, y));
1001 102 : assert(is_3_child(z, x));
1002 102 : assert(!is_2_child(z, y));
1003 102 : assert(!is_22_parent(y->branch[L], y, y->branch[R]));
1004 102 : enum Link const z_to_x_dir = z->branch[R] == x;
1005 102 : struct CCC_Tree_map_node *const w = y->branch[!z_to_x_dir];
1006 102 : if (is_1_child(y, w)) {
1007 70 : rotate(map, z, y, y->branch[z_to_x_dir], z_to_x_dir);
1008 70 : promote(y);
1009 70 : demote(z);
1010 70 : if (is_leaf(z)) {
1011 21 : demote(z);
1012 21 : }
1013 70 : } else {
1014 : /* w is a 2-child and v will be a 1-child. */
1015 32 : struct CCC_Tree_map_node *const v = y->branch[z_to_x_dir];
1016 32 : assert(is_2_child(y, w));
1017 32 : assert(is_1_child(y, v));
1018 32 : double_rotate(map, z, y, v, !z_to_x_dir);
1019 32 : double_promote(v);
1020 32 : demote(y);
1021 32 : double_demote(z);
1022 : /* Optional "Rebalancing with Promotion," defined as follows:
1023 : if node z is a non-leaf 1,1 node, we promote it;
1024 : otherwise, if y is a non-leaf 1,1 node, we promote it.
1025 : (See Figure 4.) (Haeupler et. al. 2014, 17).
1026 : This reduces constants in some of theorems mentioned in the
1027 : paper but may not be worth doing. Rotations stay at 2 worst
1028 : case. Should revisit after more performance testing. */
1029 32 : if (!is_leaf(z)
1030 32 : && is_11_parent(z->branch[L], z, z->branch[R])) {
1031 9 : promote(z);
1032 32 : } else if (!is_leaf(y)
1033 23 : && is_11_parent(y->branch[L], y, y->branch[R])) {
1034 5 : promote(y);
1035 5 : }
1036 32 : }
1037 : /* Returning here confirms O(1) rotations for re-balance. */
1038 : return;
1039 102 : }
1040 193 : x = z;
1041 193 : z = g;
1042 295 : }
1043 239 : }
1044 :
1045 : static void
1046 149 : transplant(
1047 : struct CCC_Tree_map *const map,
1048 : struct CCC_Tree_map_node *const remove,
1049 : struct CCC_Tree_map_node *const replacement
1050 : ) {
1051 149 : assert(remove != NULL);
1052 149 : assert(replacement != NULL);
1053 149 : replacement->parent = remove->parent;
1054 149 : if (remove->parent == NULL) {
1055 18 : map->root = replacement;
1056 18 : } else {
1057 131 : remove->parent->branch[remove->parent->branch[R] == remove]
1058 262 : = replacement;
1059 : }
1060 149 : if (remove->branch[R]) {
1061 117 : remove->branch[R]->parent = replacement;
1062 117 : }
1063 149 : if (remove->branch[L]) {
1064 149 : remove->branch[L]->parent = replacement;
1065 149 : }
1066 149 : replacement->branch[R] = remove->branch[R];
1067 149 : replacement->branch[L] = remove->branch[L];
1068 149 : replacement->parity
1069 298 : = (typeof((struct CCC_Tree_map_node){}.parity))parity(remove);
1070 149 : }
1071 :
1072 : /** A single rotation is symmetric. Here is the right case. Lowercase are nodes
1073 : and uppercase are arbitrary subtrees.
1074 : z x
1075 : ╭──┴──╮ ╭──┴──╮
1076 : x C A z
1077 : ╭─┴─╮ -> ╭─┴─╮
1078 : A y y C
1079 : │ │
1080 : B B
1081 :
1082 : Taking a link as input allows us to code both symmetrical cases at once. */
1083 : static void
1084 982 : rotate(
1085 : struct CCC_Tree_map *const map,
1086 : struct CCC_Tree_map_node *const z,
1087 : struct CCC_Tree_map_node *const x,
1088 : struct CCC_Tree_map_node *const y,
1089 : enum Link const dir
1090 : ) {
1091 982 : assert(z != NULL);
1092 982 : struct CCC_Tree_map_node *const g = z->parent;
1093 982 : x->parent = g;
1094 982 : if (g == NULL) {
1095 136 : map->root = x;
1096 136 : } else {
1097 846 : g->branch[g->branch[R] == z] = x;
1098 : }
1099 982 : x->branch[dir] = z;
1100 982 : z->parent = x;
1101 982 : z->branch[!dir] = y;
1102 982 : if (y) {
1103 421 : y->parent = z;
1104 421 : }
1105 982 : }
1106 :
1107 : /** A double rotation shouldn't actually be two calls to rotate because that
1108 : would invoke pointless memory writes. Here is an example of double right.
1109 : Lowercase are nodes and uppercase are arbitrary subtrees.
1110 :
1111 : z y
1112 : ╭──┴──╮ ╭──┴──╮
1113 : x D x z
1114 : ╭─┴─╮ -> ╭─┴─╮ ╭─┴─╮
1115 : A y A B C D
1116 : ╭─┴─╮
1117 : B C
1118 :
1119 : Taking a link as input allows us to code both symmetrical cases at once. */
1120 : static void
1121 153 : double_rotate(
1122 : struct CCC_Tree_map *const map,
1123 : struct CCC_Tree_map_node *const z,
1124 : struct CCC_Tree_map_node *const x,
1125 : struct CCC_Tree_map_node *const y,
1126 : enum Link const dir
1127 : ) {
1128 153 : assert(z != NULL);
1129 153 : assert(x != NULL);
1130 153 : assert(y != NULL);
1131 153 : struct CCC_Tree_map_node *const g = z->parent;
1132 153 : y->parent = g;
1133 153 : if (g == NULL) {
1134 6 : map->root = y;
1135 6 : } else {
1136 147 : g->branch[g->branch[R] == z] = y;
1137 : }
1138 153 : x->branch[!dir] = y->branch[dir];
1139 153 : if (y->branch[dir]) {
1140 49 : y->branch[dir]->parent = x;
1141 49 : }
1142 153 : y->branch[dir] = x;
1143 153 : x->parent = y;
1144 :
1145 153 : z->branch[dir] = y->branch[!dir];
1146 153 : if (y->branch[!dir]) {
1147 47 : y->branch[!dir]->parent = z;
1148 47 : }
1149 153 : y->branch[!dir] = z;
1150 153 : z->parent = y;
1151 153 : }
1152 :
1153 : /* Returns the parity of a node either 0 or 1. A NULL node has a parity of 1 aka
1154 : CCC_TRUE. */
1155 : static inline CCC_Tribool
1156 22072 : parity(struct CCC_Tree_map_node const *const x) {
1157 22072 : return x ? (CCC_Tribool)x->parity : CCC_TRUE;
1158 : }
1159 :
1160 : /* Returns true for rank difference 0 (rule break) between the parent and node.
1161 : p
1162 : 1╭─╯
1163 : x */
1164 : [[maybe_unused]] static inline CCC_Tribool
1165 1033 : is_0_child(
1166 : struct CCC_Tree_map_node const *const p,
1167 : struct CCC_Tree_map_node const *const x
1168 : ) {
1169 1033 : return parity(p) == parity(x);
1170 : }
1171 :
1172 : /* Returns true for rank difference 1 between the parent and node.
1173 : p
1174 : 1/
1175 : x*/
1176 : static inline CCC_Tribool
1177 357 : is_1_child(
1178 : struct CCC_Tree_map_node const *const p,
1179 : struct CCC_Tree_map_node const *const x
1180 : ) {
1181 357 : return parity(p) != parity(x);
1182 : }
1183 :
1184 : /* Returns true for rank difference 2 between the parent and node.
1185 : p
1186 : 2╭─╯
1187 : x */
1188 : static inline CCC_Tribool
1189 1656 : is_2_child(
1190 : struct CCC_Tree_map_node const *const p,
1191 : struct CCC_Tree_map_node const *const x
1192 : ) {
1193 1656 : return parity(p) == parity(x);
1194 : }
1195 :
1196 : /* Returns true for rank difference 3 between the parent and node.
1197 : p
1198 : 3╭─╯
1199 : x */
1200 : [[maybe_unused]] static inline CCC_Tribool
1201 102 : is_3_child(
1202 : struct CCC_Tree_map_node const *const p,
1203 : struct CCC_Tree_map_node const *const x
1204 : ) {
1205 102 : return parity(p) != parity(x);
1206 : }
1207 :
1208 : /* Returns true if a parent is a 0,1 or 1,0 node, which is not allowed. Either
1209 : child may be the sentinel node which has a parity of 1 and rank -1.
1210 : p
1211 : 0╭─┴─╮1
1212 : x y */
1213 : static inline CCC_Tribool
1214 2664 : is_01_parent(
1215 : struct CCC_Tree_map_node const *const x,
1216 : struct CCC_Tree_map_node const *const p,
1217 : struct CCC_Tree_map_node const *const y
1218 : ) {
1219 4920 : return (!parity(x) && !parity(p) && parity(y))
1220 2664 : || (parity(x) && parity(p) && !parity(y));
1221 : }
1222 :
1223 : /* Returns true if a parent is a 1,1 node. Either child may be the sentinel
1224 : node which has a parity of 1 and rank -1.
1225 : p
1226 : 1╭─┴─╮1
1227 : x y */
1228 : static inline CCC_Tribool
1229 23 : is_11_parent(
1230 : struct CCC_Tree_map_node const *const x,
1231 : struct CCC_Tree_map_node const *const p,
1232 : struct CCC_Tree_map_node const *const y
1233 : ) {
1234 33 : return (!parity(x) && parity(p) && !parity(y))
1235 23 : || (parity(x) && !parity(p) && parity(y));
1236 : }
1237 :
1238 : /* Returns true if a parent is a 0,2 or 2,0 node, which is not allowed. Either
1239 : child may be the sentinel node which has a parity of 1 and rank -1.
1240 : p
1241 : 0╭─┴─╮2
1242 : x y */
1243 : static inline CCC_Tribool
1244 1350 : is_02_parent(
1245 : struct CCC_Tree_map_node const *const x,
1246 : struct CCC_Tree_map_node const *const p,
1247 : struct CCC_Tree_map_node const *const y
1248 : ) {
1249 1350 : return (parity(x) == parity(p)) && (parity(p) == parity(y));
1250 : }
1251 :
1252 : /* Returns true if a parent is a 2,2 or 2,2 node, which is allowed. 2,2 nodes
1253 : are allowed in a WAVL tree but the absence of any 2,2 nodes is the exact
1254 : equivalent of a normal AVL tree which can occur if only insertions occur
1255 : for a WAVL tree. Either child may be the sentinel node which has a parity of
1256 : 1 and rank -1.
1257 : p
1258 : 2╭─┴─╮2
1259 : x y */
1260 : static inline CCC_Tribool
1261 244 : is_22_parent(
1262 : struct CCC_Tree_map_node const *const x,
1263 : struct CCC_Tree_map_node const *const p,
1264 : struct CCC_Tree_map_node const *const y
1265 : ) {
1266 244 : return (parity(x) == parity(p)) && (parity(p) == parity(y));
1267 : }
1268 :
1269 : static inline void
1270 4633 : promote(struct CCC_Tree_map_node *const x) {
1271 4633 : if (x) {
1272 4633 : x->parity = !x->parity;
1273 4633 : }
1274 4633 : }
1275 :
1276 : static inline void
1277 1578 : demote(struct CCC_Tree_map_node *const x) {
1278 1578 : promote(x);
1279 1578 : }
1280 :
1281 : /* One could imagine non-parity based rank tracking making this function
1282 : meaningful, but two parity changes are the same as a no-op. Leave for
1283 : clarity of what the code is meant to do through certain sections. */
1284 : static inline void
1285 32 : double_promote(struct CCC_Tree_map_node *const) {
1286 32 : }
1287 :
1288 : /* One could imagine non-parity based rank tracking making this function
1289 : meaningful, but two parity changes are the same as a no-op. Leave for
1290 : clarity of what the code is meant to do through certain sections. */
1291 : static inline void
1292 32 : double_demote(struct CCC_Tree_map_node *const) {
1293 32 : }
1294 :
1295 : static inline CCC_Tribool
1296 521 : is_leaf(struct CCC_Tree_map_node const *const x) {
1297 521 : return x->branch[L] == NULL && x->branch[R] == NULL;
1298 : }
1299 :
1300 : static inline struct CCC_Tree_map_node *
1301 4014 : sibling_of(struct CCC_Tree_map_node const *const x) {
1302 4014 : if (x->parent == NULL) {
1303 0 : return NULL;
1304 : }
1305 : /* We want the sibling so we need the truthy value to be opposite of x. */
1306 4014 : return x->parent->branch[x->parent->branch[L] == x];
1307 4014 : }
1308 :
1309 : /*=========================== Validation ===============================*/
1310 :
1311 : /* NOLINTBEGIN(*misc-no-recursion) */
1312 :
1313 : /** @internal */
1314 : struct Tree_range {
1315 : struct CCC_Tree_map_node const *low;
1316 : struct CCC_Tree_map_node const *root;
1317 : struct CCC_Tree_map_node const *high;
1318 : };
1319 :
1320 : static size_t
1321 134002 : recursive_count(
1322 : struct CCC_Tree_map const *const map,
1323 : struct CCC_Tree_map_node const *const r
1324 : ) {
1325 134002 : if (r == NULL) {
1326 67967 : return 0;
1327 : }
1328 132070 : return 1 + recursive_count(map, r->branch[R])
1329 66035 : + recursive_count(map, r->branch[L]);
1330 134002 : }
1331 :
1332 : static CCC_Tribool
1333 134002 : are_subtrees_valid(struct CCC_Tree_map const *t, struct Tree_range const r) {
1334 134002 : if (!r.root) {
1335 67967 : return CCC_TRUE;
1336 : }
1337 66035 : if (r.low
1338 66035 : && order(t, key_from_node(t, r.low), r.root) != CCC_ORDER_LESSER) {
1339 0 : return CCC_FALSE;
1340 : }
1341 66035 : if (r.high
1342 66035 : && order(t, key_from_node(t, r.high), r.root) != CCC_ORDER_GREATER) {
1343 0 : return CCC_FALSE;
1344 : }
1345 132070 : return are_subtrees_valid(
1346 66035 : t,
1347 264140 : (struct Tree_range){
1348 66035 : .low = r.low,
1349 66035 : .root = r.root->branch[L],
1350 66035 : .high = r.root,
1351 : }
1352 : )
1353 66035 : && are_subtrees_valid(
1354 66035 : t,
1355 264140 : (struct Tree_range){
1356 66035 : .low = r.root,
1357 66035 : .root = r.root->branch[R],
1358 66035 : .high = r.high,
1359 : }
1360 : );
1361 134002 : }
1362 :
1363 : static CCC_Tribool
1364 134002 : is_storing_parent(
1365 : struct CCC_Tree_map const *const t,
1366 : struct CCC_Tree_map_node const *const parent,
1367 : struct CCC_Tree_map_node const *const root
1368 : ) {
1369 134002 : if (root == NULL) {
1370 67967 : return CCC_TRUE;
1371 : }
1372 66035 : if (root->parent != parent) {
1373 0 : return CCC_FALSE;
1374 : }
1375 132070 : return is_storing_parent(t, root, root->branch[L])
1376 66035 : && is_storing_parent(t, root, root->branch[R]);
1377 134002 : }
1378 :
1379 : static CCC_Tribool
1380 1932 : validate(struct CCC_Tree_map const *const map) {
1381 1932 : if (!are_subtrees_valid(
1382 1932 : map,
1383 3864 : (struct Tree_range){
1384 : .low = NULL,
1385 1932 : .root = map->root,
1386 : .high = NULL,
1387 : }
1388 : )) {
1389 0 : return CCC_FALSE;
1390 : }
1391 1932 : if (recursive_count(map, map->root) != map->count) {
1392 0 : return CCC_FALSE;
1393 : }
1394 1932 : if (!is_storing_parent(map, NULL, map->root)) {
1395 0 : return CCC_FALSE;
1396 : }
1397 1932 : return CCC_TRUE;
1398 1932 : }
1399 :
1400 : /* NOLINTEND(*misc-no-recursion) */
1401 :
1402 : /* Below you will find the required license for code that inspired the
1403 : implementation of a WAVL tree in this repository for some map containers.
1404 :
1405 : The original repository can be found here:
1406 :
1407 : https://github.com/pvachon/wavl_tree
1408 :
1409 : The original implementation has be changed to eliminate left and right cases
1410 : and work within the C Container Collection memory framework.
1411 :
1412 : Redistribution and use in source and binary forms, with or without
1413 : modification, are permitted provided that the following conditions are met:
1414 :
1415 : 1. Redistributions of source code must retain the above copyright notice, this
1416 : list of conditions and the following disclaimer.
1417 :
1418 : 2. Redistributions in binary form must reproduce the above copyright notice,
1419 : this list of conditions and the following disclaimer in the documentation
1420 : and/or other materials provided with the distribution.
1421 :
1422 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1423 : AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1424 : IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1425 : DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
1426 : FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1427 : DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
1428 : SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
1429 : CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
1430 : OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1431 : OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
|
