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 implements a splay tree that does not support duplicates.
16 : The code to support a splay tree that does not allow duplicates is much simpler
17 : than the code to support a multimap implementation. This implementation is
18 : based on the following source.
19 :
20 : 1. Daniel Sleator, Carnegie Mellon University. Sleator's implementation of a
21 : topdown splay tree was instrumental in starting things off, but required
22 : extensive modification. I had to update parent and child tracking, and
23 : unite the left and right cases for fun. See the code for a generalizable
24 : strategy to eliminate symmetric left and right cases for any binary tree
25 : code. https://www.link.cs.cmu.edu/splay/
26 :
27 : Because this is a self-optimizing data structure it may benefit from many
28 : constant time queries for frequently accessed elements. */
29 : /** C23 provided headers. */
30 : #include <stddef.h>
31 :
32 : /** CCC provided headers. */
33 : #include "ccc/adaptive_map.h"
34 : #include "ccc/configuration.h"
35 : #include "ccc/private/private_adaptive_map.h"
36 : #include "ccc/types.h"
37 :
38 : /** @internal Instead of thinking about left and right consider only links
39 : in the abstract sense. Put them in an array and then flip
40 : this enum and left and right code paths can be united into one */
41 : enum Link {
42 : L = 0,
43 : R,
44 : };
45 :
46 : #define INORDER R
47 : #define INORDER_REVERSE L
48 :
49 : enum {
50 : LR = 2,
51 : };
52 :
53 : /*======================= Prototypes ===========================*/
54 :
55 : static struct CCC_Adaptive_map_entry
56 : entry(struct CCC_Adaptive_map *, void const *);
57 : static void init_node(struct CCC_Adaptive_map_node *);
58 : static void swap(void *, void *, void *, size_t);
59 : static void
60 : link(struct CCC_Adaptive_map_node *, enum Link, struct CCC_Adaptive_map_node *);
61 : static CCC_Tribool is_empty(struct CCC_Adaptive_map const *);
62 : static CCC_Tribool contains(struct CCC_Adaptive_map *, void const *);
63 : static CCC_Tribool validate(struct CCC_Adaptive_map const *);
64 : static void *struct_base(
65 : struct CCC_Adaptive_map const *, struct CCC_Adaptive_map_node const *
66 : );
67 : static void *find(struct CCC_Adaptive_map *, void const *);
68 : static void *erase(struct CCC_Adaptive_map *, void const *);
69 : static void *allocate_insert(
70 : struct CCC_Adaptive_map *,
71 : struct CCC_Adaptive_map_node *,
72 : CCC_Allocator const *
73 : );
74 : static void *insert(struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *);
75 : static void *connect_new_root(
76 : struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *, CCC_Order
77 : );
78 : static void *max(struct CCC_Adaptive_map const *);
79 : static void *min(struct CCC_Adaptive_map const *);
80 : static void *key_in_slot(struct CCC_Adaptive_map const *, void const *);
81 : static void *
82 : key_from_node(struct CCC_Adaptive_map const *, CCC_Adaptive_map_node const *);
83 : static CCC_Range
84 : equal_range(struct CCC_Adaptive_map *, void const *, void const *, enum Link);
85 : static struct CCC_Adaptive_map_node *
86 : remove_from_tree(struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *);
87 : static struct CCC_Adaptive_map_node const *next(
88 : struct CCC_Adaptive_map const *,
89 : struct CCC_Adaptive_map_node const *,
90 : enum Link
91 : );
92 : static struct CCC_Adaptive_map_node *
93 : splay(struct CCC_Adaptive_map *, struct CCC_Adaptive_map_node *, void const *);
94 : static struct CCC_Adaptive_map_node *
95 : elem_in_slot(struct CCC_Adaptive_map const *, void const *);
96 : static CCC_Order order(
97 : struct CCC_Adaptive_map const *,
98 : void const *,
99 : struct CCC_Adaptive_map_node const *
100 : );
101 :
102 : /*======================= Map Interface =========================*/
103 :
104 : CCC_Tribool
105 7 : CCC_adaptive_map_is_empty(CCC_Adaptive_map const *const map) {
106 7 : if (!map) {
107 1 : return CCC_TRIBOOL_ERROR;
108 : }
109 6 : return is_empty(map);
110 7 : }
111 :
112 : CCC_Count
113 122 : CCC_adaptive_map_count(CCC_Adaptive_map const *const map) {
114 122 : if (!map) {
115 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
116 : }
117 121 : return (CCC_Count){.count = map->count};
118 122 : }
119 :
120 : CCC_Tribool
121 12 : CCC_adaptive_map_contains(CCC_Adaptive_map *const map, void const *const key) {
122 12 : if (!map || !key) {
123 2 : return CCC_TRIBOOL_ERROR;
124 : }
125 10 : return contains(map, key);
126 12 : }
127 :
128 : CCC_Adaptive_map_entry
129 1117 : CCC_adaptive_map_entry(CCC_Adaptive_map *const map, void const *const key) {
130 1117 : if (!map || !key) {
131 4 : return (CCC_Adaptive_map_entry){
132 2 : .entry = {.status = CCC_ENTRY_ARGUMENT_ERROR},
133 : };
134 : }
135 1115 : return entry(map, key);
136 1117 : }
137 :
138 : void *
139 341 : CCC_adaptive_map_insert_entry(
140 : CCC_Adaptive_map_entry const *const entry,
141 : CCC_Adaptive_map_node *const type_intruder,
142 : CCC_Allocator const *const allocator
143 : ) {
144 341 : if (!entry || !type_intruder || !allocator) {
145 3 : return NULL;
146 : }
147 338 : if (entry->entry.status == CCC_ENTRY_OCCUPIED) {
148 103 : if (entry->entry.type) {
149 103 : *type_intruder = *elem_in_slot(entry->map, entry->entry.type);
150 103 : (void)memcpy(
151 103 : entry->entry.type,
152 103 : struct_base(entry->map, type_intruder),
153 103 : entry->map->sizeof_type
154 : );
155 103 : }
156 103 : return entry->entry.type;
157 : }
158 235 : return allocate_insert(entry->map, type_intruder, allocator);
159 341 : }
160 :
161 : void *
162 263 : CCC_adaptive_map_or_insert(
163 : CCC_Adaptive_map_entry const *const entry,
164 : CCC_Adaptive_map_node *const type_intruder,
165 : CCC_Allocator const *const allocator
166 : ) {
167 263 : if (!entry || !type_intruder || !allocator) {
168 3 : return NULL;
169 : }
170 260 : if (entry->entry.status & CCC_ENTRY_OCCUPIED) {
171 153 : return entry->entry.type;
172 : }
173 107 : return allocate_insert(entry->map, type_intruder, allocator);
174 263 : }
175 :
176 : CCC_Adaptive_map_entry *
177 112 : CCC_adaptive_map_and_modify(
178 : CCC_Adaptive_map_entry *const entry, CCC_Modifier const *const modifier
179 : ) {
180 112 : if (!entry || !modifier) {
181 2 : return NULL;
182 : }
183 110 : if (modifier->modify && (entry->entry.status & CCC_ENTRY_OCCUPIED)
184 110 : && entry->entry.type) {
185 168 : modifier->modify((CCC_Arguments){
186 56 : .type = entry->entry.type,
187 56 : .context = modifier->context,
188 : });
189 56 : }
190 110 : return entry;
191 112 : }
192 :
193 : CCC_Entry
194 629 : CCC_adaptive_map_swap_entry(
195 : CCC_Adaptive_map *const map,
196 : CCC_Adaptive_map_node *const type_intruder,
197 : CCC_Adaptive_map_node *const temp_intruder,
198 : CCC_Allocator const *const allocator
199 : ) {
200 629 : if (!map || !type_intruder || !temp_intruder || !allocator) {
201 4 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
202 : }
203 625 : void *const found = find(map, key_from_node(map, type_intruder));
204 625 : if (found) {
205 6 : assert(map->root != NULL);
206 6 : *type_intruder = *map->root;
207 6 : void *const any_struct = struct_base(map, type_intruder);
208 6 : void *const in_tree = struct_base(map, map->root);
209 6 : void *const old_val = struct_base(map, temp_intruder);
210 6 : swap(old_val, in_tree, any_struct, map->sizeof_type);
211 12 : type_intruder->branch[L] = type_intruder->branch[R]
212 12 : = type_intruder->parent = NULL;
213 12 : temp_intruder->branch[L] = temp_intruder->branch[R]
214 12 : = temp_intruder->parent = NULL;
215 12 : return (CCC_Entry){
216 6 : .type = old_val,
217 : .status = CCC_ENTRY_OCCUPIED,
218 : };
219 6 : }
220 619 : void *const inserted = allocate_insert(map, type_intruder, allocator);
221 619 : if (!inserted) {
222 1 : return (CCC_Entry){
223 : .type = NULL,
224 : .status = CCC_ENTRY_INSERT_ERROR,
225 : };
226 : }
227 618 : return (CCC_Entry){
228 : .type = NULL,
229 : .status = CCC_ENTRY_VACANT,
230 : };
231 629 : }
232 :
233 : CCC_Entry
234 20 : CCC_adaptive_map_try_insert(
235 : CCC_Adaptive_map *const map,
236 : CCC_Adaptive_map_node *const type_intruder,
237 : CCC_Allocator const *const allocator
238 : ) {
239 20 : if (!map || !type_intruder || !allocator) {
240 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
241 : }
242 17 : void *const found = find(map, key_from_node(map, type_intruder));
243 17 : if (found) {
244 8 : assert(map->root != NULL);
245 16 : return (CCC_Entry){
246 8 : .type = struct_base(map, map->root),
247 : .status = CCC_ENTRY_OCCUPIED,
248 : };
249 : }
250 9 : void *const inserted = allocate_insert(map, type_intruder, allocator);
251 9 : if (!inserted) {
252 1 : return (CCC_Entry){
253 : .type = NULL,
254 : .status = CCC_ENTRY_INSERT_ERROR,
255 : };
256 : }
257 16 : return (CCC_Entry){
258 8 : .type = inserted,
259 : .status = CCC_ENTRY_VACANT,
260 : };
261 20 : }
262 :
263 : CCC_Entry
264 634 : CCC_adaptive_map_insert_or_assign(
265 : CCC_Adaptive_map *const map,
266 : CCC_Adaptive_map_node *const type_intruder,
267 : CCC_Allocator const *const allocator
268 : ) {
269 634 : if (!map || !type_intruder || !allocator) {
270 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
271 : }
272 631 : void *const found = find(map, key_from_node(map, type_intruder));
273 631 : if (found) {
274 75 : *type_intruder = *elem_in_slot(map, found);
275 75 : assert(map->root != NULL);
276 75 : memcpy(found, struct_base(map, type_intruder), map->sizeof_type);
277 150 : return (CCC_Entry){
278 75 : .type = found,
279 : .status = CCC_ENTRY_OCCUPIED,
280 : };
281 : }
282 556 : void *const inserted = allocate_insert(map, type_intruder, allocator);
283 556 : if (!inserted) {
284 1 : return (CCC_Entry){
285 : .type = NULL,
286 : .status = CCC_ENTRY_INSERT_ERROR,
287 : };
288 : }
289 1110 : return (CCC_Entry){
290 555 : .type = inserted,
291 : .status = CCC_ENTRY_VACANT,
292 : };
293 634 : }
294 :
295 : CCC_Entry
296 202 : CCC_adaptive_map_remove_key_value(
297 : CCC_Adaptive_map *const map,
298 : CCC_Adaptive_map_node *const type_output_intruder,
299 : CCC_Allocator const *const allocator
300 : ) {
301 202 : if (!map || !type_output_intruder || !allocator) {
302 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
303 : }
304 199 : void *const n = erase(map, key_from_node(map, type_output_intruder));
305 199 : if (!n) {
306 3 : return (CCC_Entry){
307 : .type = NULL,
308 : .status = CCC_ENTRY_VACANT,
309 : };
310 : }
311 196 : if (allocator->allocate) {
312 180 : void *const any_struct = struct_base(map, type_output_intruder);
313 180 : memcpy(any_struct, n, map->sizeof_type);
314 540 : allocator->allocate((CCC_Allocator_arguments){
315 180 : .input = n,
316 : .bytes = 0,
317 180 : .context = allocator->context,
318 : });
319 360 : return (CCC_Entry){
320 180 : .type = any_struct,
321 : .status = CCC_ENTRY_OCCUPIED,
322 : };
323 180 : }
324 32 : return (CCC_Entry){
325 16 : .type = n,
326 : .status = CCC_ENTRY_OCCUPIED,
327 : };
328 202 : }
329 :
330 : CCC_Entry
331 222 : CCC_adaptive_map_remove_entry(
332 : CCC_Adaptive_map_entry *const e, CCC_Allocator const *const allocator
333 : ) {
334 222 : if (!e || !allocator) {
335 2 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
336 : }
337 220 : if (e->entry.status == CCC_ENTRY_OCCUPIED && e->entry.type) {
338 210 : void *const erased = erase(e->map, key_in_slot(e->map, e->entry.type));
339 210 : assert(erased);
340 210 : if (allocator->allocate) {
341 582 : allocator->allocate((CCC_Allocator_arguments){
342 194 : .input = erased,
343 : .bytes = 0,
344 194 : .context = allocator->context,
345 : });
346 194 : return (CCC_Entry){
347 : .type = NULL,
348 : .status = CCC_ENTRY_OCCUPIED,
349 : };
350 : }
351 32 : return (CCC_Entry){
352 16 : .type = erased,
353 : .status = CCC_ENTRY_OCCUPIED,
354 : };
355 210 : }
356 10 : return (CCC_Entry){
357 : .type = NULL,
358 : .status = CCC_ENTRY_VACANT,
359 : };
360 222 : }
361 :
362 : void *
363 17 : CCC_adaptive_map_get_key_value(
364 : CCC_Adaptive_map *const map, void const *const key
365 : ) {
366 17 : if (!map || !key) {
367 2 : return NULL;
368 : }
369 15 : return find(map, key);
370 17 : }
371 :
372 : void *
373 26 : CCC_adaptive_map_unwrap(CCC_Adaptive_map_entry const *const e) {
374 26 : if (!e) {
375 1 : return NULL;
376 : }
377 25 : return e->entry.status == CCC_ENTRY_OCCUPIED ? e->entry.type : NULL;
378 26 : }
379 :
380 : CCC_Tribool
381 2 : CCC_adaptive_map_insert_error(CCC_Adaptive_map_entry const *const e) {
382 2 : if (!e) {
383 1 : return CCC_TRIBOOL_ERROR;
384 : }
385 1 : return (e->entry.status & CCC_ENTRY_INSERT_ERROR) != 0;
386 2 : }
387 :
388 : CCC_Tribool
389 29 : CCC_adaptive_map_occupied(CCC_Adaptive_map_entry const *const e) {
390 29 : if (!e) {
391 1 : return CCC_TRIBOOL_ERROR;
392 : }
393 28 : return (e->entry.status & CCC_ENTRY_OCCUPIED) != 0;
394 29 : }
395 :
396 : CCC_Entry_status
397 2 : CCC_adaptive_map_entry_status(CCC_Adaptive_map_entry const *const e) {
398 2 : return e ? e->entry.status : CCC_ENTRY_ARGUMENT_ERROR;
399 : }
400 :
401 : void *
402 10 : CCC_adaptive_map_begin(CCC_Adaptive_map const *const map) {
403 10 : return map ? min(map) : NULL;
404 : }
405 :
406 : void *
407 3 : CCC_adaptive_map_reverse_begin(CCC_Adaptive_map const *const map) {
408 3 : return map ? max(map) : NULL;
409 : }
410 :
411 : void *
412 277 : CCC_adaptive_map_end(CCC_Adaptive_map const *const) {
413 277 : return NULL;
414 : }
415 :
416 : void *
417 140 : CCC_adaptive_map_reverse_end(CCC_Adaptive_map const *const) {
418 140 : return NULL;
419 : }
420 :
421 : void *
422 491 : CCC_adaptive_map_next(
423 : CCC_Adaptive_map const *const map,
424 : CCC_Adaptive_map_node const *const iterator_intruder
425 : ) {
426 491 : if (!map || !iterator_intruder) {
427 2 : return NULL;
428 : }
429 978 : struct CCC_Adaptive_map_node const *n
430 489 : = next(map, iterator_intruder, INORDER);
431 489 : return n == NULL ? NULL : struct_base(map, n);
432 491 : }
433 :
434 : void *
435 162 : CCC_adaptive_map_reverse_next(
436 : CCC_Adaptive_map const *const map,
437 : CCC_Adaptive_map_node const *const iterator_intruder
438 : ) {
439 162 : if (!map || !iterator_intruder) {
440 2 : return NULL;
441 : }
442 320 : struct CCC_Adaptive_map_node const *n
443 160 : = next(map, iterator_intruder, INORDER_REVERSE);
444 160 : return n == NULL ? NULL : struct_base(map, n);
445 162 : }
446 :
447 : CCC_Range
448 8 : CCC_adaptive_map_equal_range(
449 : CCC_Adaptive_map *const map,
450 : void const *const begin_key,
451 : void const *const end_key
452 : ) {
453 8 : if (!map || !begin_key || !end_key) {
454 3 : return (CCC_Range){};
455 : }
456 5 : return equal_range(map, begin_key, end_key, INORDER);
457 8 : }
458 :
459 : CCC_Range_reverse
460 8 : CCC_adaptive_map_equal_range_reverse(
461 : CCC_Adaptive_map *const map,
462 : void const *const reverse_begin_key,
463 : void const *const reverse_end_key
464 : )
465 :
466 : {
467 8 : if (!map || !reverse_begin_key || !reverse_end_key) {
468 3 : return (CCC_Range_reverse){};
469 : }
470 5 : CCC_Range const range
471 5 : = equal_range(map, reverse_begin_key, reverse_end_key, INORDER_REVERSE);
472 15 : return (CCC_Range_reverse){
473 5 : .reverse_begin = range.begin,
474 5 : .reverse_end = range.end,
475 : };
476 8 : }
477 :
478 : /** This is a linear time constant space deletion of tree nodes via left
479 : rotations so element fields are modified during progression of deletes. */
480 : CCC_Result
481 16 : CCC_adaptive_map_clear(
482 : CCC_Adaptive_map *const map,
483 : CCC_Destructor const *const destructor,
484 : CCC_Allocator const *const allocator
485 : ) {
486 16 : if (!map || !allocator || !destructor) {
487 3 : return CCC_RESULT_ARGUMENT_ERROR;
488 : }
489 13 : struct CCC_Adaptive_map_node *node = map->root;
490 1071 : while (node != NULL) {
491 1058 : if (node->branch[L] != NULL) {
492 517 : struct CCC_Adaptive_map_node *const l = node->branch[L];
493 517 : node->branch[L] = l->branch[R];
494 517 : l->branch[R] = node;
495 517 : node = l;
496 : continue;
497 517 : }
498 541 : struct CCC_Adaptive_map_node *const next = node->branch[R];
499 541 : node->branch[L] = node->branch[R] = NULL;
500 541 : node->parent = NULL;
501 541 : void *const del = struct_base(map, node);
502 541 : if (destructor->destroy) {
503 48 : destructor->destroy((CCC_Arguments){
504 16 : .type = del,
505 16 : .context = destructor->context,
506 : });
507 16 : }
508 541 : if (allocator->allocate) {
509 1623 : (void)allocator->allocate((CCC_Allocator_arguments){
510 541 : .input = del,
511 : .bytes = 0,
512 541 : .context = allocator->context,
513 : });
514 541 : }
515 541 : node = next;
516 541 : }
517 13 : map->count = 0;
518 13 : map->root = NULL;
519 13 : return CCC_RESULT_OK;
520 16 : }
521 :
522 : CCC_Tribool
523 1753 : CCC_adaptive_map_validate(CCC_Adaptive_map const *const map) {
524 1753 : if (!map) {
525 1 : return CCC_TRIBOOL_ERROR;
526 : }
527 1752 : return validate(map);
528 1753 : }
529 :
530 : /*========================== Private Interface ============================*/
531 :
532 : struct CCC_Adaptive_map_entry
533 98 : CCC_private_adaptive_map_entry(
534 : struct CCC_Adaptive_map *const t, void const *const key
535 : ) {
536 98 : return entry(t, key);
537 98 : }
538 :
539 : void *
540 196 : CCC_private_adaptive_map_insert(
541 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *n
542 : ) {
543 196 : return insert(t, n);
544 : }
545 :
546 : void *
547 87 : CCC_private_adaptive_map_key_in_slot(
548 : struct CCC_Adaptive_map const *const t, void const *const slot
549 : ) {
550 87 : return key_in_slot(t, slot);
551 : }
552 :
553 : struct CCC_Adaptive_map_node *
554 214 : CCC_private_adaptive_map_node_in_slot(
555 : struct CCC_Adaptive_map const *const t, void const *slot
556 : ) {
557 214 : return elem_in_slot(t, slot);
558 : }
559 :
560 : /*====================== Static Splay Tree Helpers ========================*/
561 :
562 : static struct CCC_Adaptive_map_entry
563 1213 : entry(struct CCC_Adaptive_map *const t, void const *const key) {
564 1213 : void *const found = find(t, key);
565 1213 : if (found) {
566 1947 : return (struct CCC_Adaptive_map_entry){
567 649 : .map = t,
568 1298 : .entry = {
569 649 : .type = found,
570 : .status = CCC_ENTRY_OCCUPIED,
571 : },
572 : };
573 : }
574 1692 : return (struct CCC_Adaptive_map_entry){
575 564 : .map = t,
576 1128 : .entry = {
577 564 : .type = found,
578 : .status = CCC_ENTRY_VACANT,
579 : },
580 : };
581 1213 : }
582 :
583 : static inline void *
584 93024 : key_from_node(
585 : struct CCC_Adaptive_map const *const t, CCC_Adaptive_map_node const *const n
586 : ) {
587 93024 : return n ? (char *)struct_base(t, n) + t->key_offset : NULL;
588 : }
589 :
590 : static inline void *
591 297 : key_in_slot(struct CCC_Adaptive_map const *const t, void const *const slot) {
592 297 : return slot ? (char *)slot + t->key_offset : NULL;
593 : }
594 :
595 : static inline struct CCC_Adaptive_map_node *
596 1878 : elem_in_slot(struct CCC_Adaptive_map const *const t, void const *const slot) {
597 :
598 1878 : return slot ? (struct CCC_Adaptive_map_node *)((char *)slot
599 1878 : + t->type_intruder_offset)
600 : : NULL;
601 : }
602 :
603 : static inline void
604 3208 : init_node(struct CCC_Adaptive_map_node *const n) {
605 3208 : n->branch[L] = NULL;
606 3208 : n->branch[R] = NULL;
607 3208 : n->parent = NULL;
608 3208 : }
609 :
610 : static inline CCC_Tribool
611 3658 : is_empty(struct CCC_Adaptive_map const *const t) {
612 3658 : return !t->count || !t->root;
613 : }
614 :
615 : static void *
616 3 : max(struct CCC_Adaptive_map const *const t) {
617 3 : if (!t->count) {
618 0 : return NULL;
619 : }
620 3 : struct CCC_Adaptive_map_node *m = t->root;
621 29 : for (; m->branch[R] != NULL; m = m->branch[R]) {}
622 3 : return struct_base(t, m);
623 3 : }
624 :
625 : static void *
626 9 : min(struct CCC_Adaptive_map const *t) {
627 9 : if (!t->count) {
628 1 : return NULL;
629 : }
630 8 : struct CCC_Adaptive_map_node *m = t->root;
631 40 : for (; m->branch[L] != NULL; m = m->branch[L]) {}
632 8 : return struct_base(t, m);
633 9 : }
634 :
635 : static struct CCC_Adaptive_map_node const *
636 656 : next(
637 : struct CCC_Adaptive_map const *const t [[maybe_unused]],
638 : struct CCC_Adaptive_map_node const *n,
639 : enum Link const traversal
640 : ) {
641 656 : if (!n) {
642 0 : return NULL;
643 : }
644 656 : assert(t->root->parent == NULL);
645 656 : if (n->branch[traversal] != NULL) {
646 619 : for (n = n->branch[traversal]; n->branch[!traversal] != NULL;
647 286 : n = n->branch[!traversal]) {}
648 333 : return n;
649 : }
650 632 : for (; n->parent && n->parent->branch[!traversal] != n; n = n->parent) {}
651 323 : return n->parent;
652 656 : }
653 :
654 : static CCC_Range
655 10 : equal_range(
656 : struct CCC_Adaptive_map *const t,
657 : void const *const begin_key,
658 : void const *const end_key,
659 : enum Link const traversal
660 : ) {
661 10 : if (!t->count) {
662 2 : return (CCC_Range){};
663 : }
664 : /* As with most BST code the cases are perfectly symmetrical. If we
665 : are seeking an increasing or decreasing range we need to make sure
666 : we follow the [inclusive, exclusive) range rule. This means double
667 : checking we don't need to progress to the next greatest or next
668 : lesser element depending on the direction we are traversing. */
669 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
670 8 : struct CCC_Adaptive_map_node const *b = splay(t, t->root, begin_key);
671 8 : if (order(t, begin_key, b) == les_or_grt[traversal]) {
672 2 : b = next(t, b, traversal);
673 2 : }
674 8 : struct CCC_Adaptive_map_node const *e = splay(t, t->root, end_key);
675 8 : if (order(t, end_key, e) != les_or_grt[!traversal]) {
676 5 : e = next(t, e, traversal);
677 5 : }
678 24 : return (CCC_Range){
679 8 : .begin = b == NULL ? NULL : struct_base(t, b),
680 8 : .end = e == NULL ? NULL : struct_base(t, e),
681 : };
682 10 : }
683 :
684 : static void *
685 2501 : find(struct CCC_Adaptive_map *const t, void const *const key) {
686 2501 : if (t->root == NULL) {
687 61 : return NULL;
688 : }
689 2440 : t->root = splay(t, t->root, key);
690 2440 : return order(t, key, t->root) == CCC_ORDER_EQUAL ? struct_base(t, t->root)
691 : : NULL;
692 2501 : }
693 :
694 : static CCC_Tribool
695 10 : contains(struct CCC_Adaptive_map *const t, void const *const key) {
696 10 : t->root = splay(t, t->root, key);
697 10 : return order(t, key, t->root) == CCC_ORDER_EQUAL;
698 : }
699 :
700 : static void *
701 1526 : allocate_insert(
702 : struct CCC_Adaptive_map *const t,
703 : struct CCC_Adaptive_map_node *out_handle,
704 : CCC_Allocator const *const allocator
705 : ) {
706 1526 : init_node(out_handle);
707 1526 : CCC_Order root_order = CCC_ORDER_ERROR;
708 1526 : if (!is_empty(t)) {
709 1492 : void const *const key = key_from_node(t, out_handle);
710 1492 : t->root = splay(t, t->root, key);
711 1492 : root_order = order(t, key, t->root);
712 1492 : if (CCC_ORDER_EQUAL == root_order) {
713 0 : return NULL;
714 : }
715 1492 : }
716 1526 : if (allocator->allocate) {
717 4473 : void *const node = allocator->allocate((CCC_Allocator_arguments){
718 : .input = NULL,
719 1491 : .bytes = t->sizeof_type,
720 1491 : .context = allocator->context,
721 : });
722 1491 : if (!node) {
723 5 : return NULL;
724 : }
725 1486 : (void)memcpy(node, struct_base(t, out_handle), t->sizeof_type);
726 1486 : out_handle = elem_in_slot(t, node);
727 1486 : init_node(out_handle);
728 1491 : }
729 1521 : if (is_empty(t)) {
730 34 : t->root = out_handle;
731 34 : t->count = 1;
732 34 : return struct_base(t, out_handle);
733 : }
734 1487 : assert(root_order != CCC_ORDER_ERROR);
735 1487 : t->count++;
736 1487 : return connect_new_root(t, out_handle, root_order);
737 1526 : }
738 :
739 : static void *
740 196 : insert(
741 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *const n
742 : ) {
743 196 : init_node(n);
744 196 : if (is_empty(t)) {
745 12 : t->root = n;
746 12 : t->count = 1;
747 12 : return struct_base(t, n);
748 : }
749 184 : void const *const key = key_from_node(t, n);
750 184 : t->root = splay(t, t->root, key);
751 184 : CCC_Order const root_order = order(t, key, t->root);
752 184 : if (CCC_ORDER_EQUAL == root_order) {
753 0 : return NULL;
754 : }
755 184 : t->count++;
756 184 : return connect_new_root(t, n, root_order);
757 196 : }
758 :
759 : static void *
760 1671 : connect_new_root(
761 : struct CCC_Adaptive_map *const t,
762 : struct CCC_Adaptive_map_node *const new_root,
763 : CCC_Order const order_result
764 : ) {
765 1671 : assert(new_root);
766 1671 : enum Link const dir = CCC_ORDER_GREATER == order_result;
767 1671 : link(new_root, dir, t->root->branch[dir]);
768 1671 : link(new_root, !dir, t->root);
769 1671 : t->root->branch[dir] = NULL;
770 1671 : t->root = new_root;
771 1671 : t->root->parent = NULL;
772 3342 : return struct_base(t, new_root);
773 1671 : }
774 :
775 : static void *
776 409 : erase(struct CCC_Adaptive_map *const t, void const *const key) {
777 409 : if (is_empty(t)) {
778 1 : return NULL;
779 : }
780 408 : struct CCC_Adaptive_map_node *ret = splay(t, t->root, key);
781 408 : CCC_Order const found = order(t, key, ret);
782 408 : if (found != CCC_ORDER_EQUAL) {
783 2 : return NULL;
784 : }
785 406 : ret = remove_from_tree(t, ret);
786 406 : ret->branch[L] = ret->branch[R] = ret->parent = NULL;
787 406 : t->count--;
788 406 : return struct_base(t, ret);
789 409 : }
790 :
791 : static struct CCC_Adaptive_map_node *
792 406 : remove_from_tree(
793 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *const ret
794 : ) {
795 406 : if (ret->branch[L] == NULL) {
796 84 : t->root = ret->branch[R];
797 84 : if (t->root) {
798 77 : t->root->parent = NULL;
799 77 : }
800 84 : } else {
801 322 : t->root = splay(t, ret->branch[L], key_from_node(t, ret));
802 322 : link(t->root, R, ret->branch[R]);
803 : }
804 406 : return ret;
805 : }
806 :
807 : /** Adopts D. Sleator technique for splaying. Notable to this method is the
808 : general improvement to the tree that occurs because we always splay the key
809 : to the root, OR the next closest value to the key to the root. This has
810 : interesting performance implications for real data sets.
811 :
812 : This implementation has been modified to unite the left and right symmetries
813 : and manage the parent pointers. Parent pointers are not usual for splay trees
814 : but are necessary for a clean iteration API. */
815 : static struct CCC_Adaptive_map_node *
816 4872 : splay(
817 : struct CCC_Adaptive_map *const t,
818 : struct CCC_Adaptive_map_node *root,
819 : void const *const key
820 : ) {
821 4872 : assert(root);
822 : /* Splaying brings the key element up to the root. The zigzag fixes of
823 : splaying repair the tree and we remember the roots of these changes in
824 : this helper tree. At the end, make the root pick up these modified left
825 : and right helpers. The nil node should NULL initialized to start. */
826 4872 : struct CCC_Adaptive_map_node nil = {};
827 4872 : struct CCC_Adaptive_map_node *left_right_subtrees[LR] = {&nil, &nil};
828 11213 : for (;;) {
829 11213 : CCC_Order const root_order = order(t, key, root);
830 11213 : enum Link const order_link = CCC_ORDER_GREATER == root_order;
831 11213 : struct CCC_Adaptive_map_node *const child = root->branch[order_link];
832 11213 : if (CCC_ORDER_EQUAL == root_order || child == NULL) {
833 4226 : break;
834 : }
835 6987 : CCC_Order const child_order = order(t, key, child);
836 6987 : enum Link const child_order_link = CCC_ORDER_GREATER == child_order;
837 : /* A straight line would form from root->child->key. An opportunity
838 : to splay and heal the tree arises. */
839 6987 : if (CCC_ORDER_EQUAL != child_order && order_link == child_order_link) {
840 4177 : root->branch[order_link] = child->branch[!order_link];
841 4177 : if (child->branch[!order_link]) {
842 2066 : child->branch[!order_link]->parent = root;
843 2066 : }
844 4177 : child->branch[!order_link] = root;
845 4177 : root->parent = child;
846 4177 : root = child;
847 4177 : if (root->branch[order_link] == NULL) {
848 646 : break;
849 : }
850 3531 : }
851 6341 : left_right_subtrees[!order_link]->branch[order_link] = root;
852 6341 : root->parent = left_right_subtrees[!order_link];
853 6341 : left_right_subtrees[!order_link] = root;
854 6341 : root = root->branch[order_link];
855 11213 : }
856 4872 : left_right_subtrees[L]->branch[R] = root->branch[L];
857 4872 : if (left_right_subtrees[L] != &nil && root->branch[L]) {
858 415 : root->branch[L]->parent = left_right_subtrees[L];
859 415 : }
860 4872 : left_right_subtrees[R]->branch[L] = root->branch[R];
861 4872 : if (left_right_subtrees[R] != &nil && root->branch[R]) {
862 384 : root->branch[R]->parent = left_right_subtrees[R];
863 384 : }
864 4872 : root->branch[L] = nil.branch[R];
865 4872 : if (nil.branch[R]) {
866 4521 : nil.branch[R]->parent = root;
867 4521 : }
868 4872 : root->branch[R] = nil.branch[L];
869 4872 : if (nil.branch[L]) {
870 2611 : nil.branch[L]->parent = root;
871 2611 : }
872 4872 : root->parent = NULL;
873 4872 : t->root = root;
874 9744 : return root;
875 4872 : }
876 :
877 : static inline void *
878 211267 : struct_base(
879 : struct CCC_Adaptive_map const *const t,
880 : struct CCC_Adaptive_map_node const *const n
881 : ) {
882 : /* Link is the first field of the struct and is an array so no need to get
883 : pointer address of [0] element of array. That's the same as just the
884 : array field. */
885 211267 : return n ? ((char *)n->branch) - t->type_intruder_offset : NULL;
886 : }
887 :
888 : static inline CCC_Order
889 112304 : order(
890 : struct CCC_Adaptive_map const *const t,
891 : void const *const key,
892 : struct CCC_Adaptive_map_node const *const node
893 : ) {
894 449216 : return t->comparator.compare((CCC_Key_comparator_arguments){
895 112304 : .key_left = key,
896 112304 : .type_right = struct_base(t, node),
897 112304 : .context = t->comparator.context,
898 : });
899 : }
900 :
901 : static inline void
902 6 : swap(void *const temp, void *const a, void *const b, size_t sizeof_type) {
903 6 : if (a == b || !a || !b) {
904 0 : return;
905 : }
906 6 : (void)memcpy(temp, a, sizeof_type);
907 6 : (void)memcpy(a, b, sizeof_type);
908 6 : (void)memcpy(b, temp, sizeof_type);
909 12 : }
910 :
911 : static inline void
912 3664 : link(
913 : struct CCC_Adaptive_map_node *const parent,
914 : enum Link const dir,
915 : struct CCC_Adaptive_map_node *const subtree
916 : ) {
917 3664 : if (parent) {
918 3664 : parent->branch[dir] = subtree;
919 3664 : }
920 3664 : if (subtree) {
921 2716 : subtree->parent = parent;
922 2716 : }
923 3664 : }
924 :
925 : /* NOLINTBEGIN(*misc-no-recursion) */
926 :
927 : /* ====================== Debugging ====================== */
928 :
929 : /** @internal Validate binary tree invariants with ranges. Use a recursive
930 : method that does not rely upon the implementation of iterators or any other
931 : possibly buggy implementation. A pure functional range check will provide the
932 : most reliable check regardless of implementation changes throughout code base.
933 : */
934 : struct Tree_range {
935 : struct CCC_Adaptive_map_node const *low;
936 : struct CCC_Adaptive_map_node const *root;
937 : struct CCC_Adaptive_map_node const *high;
938 : };
939 :
940 : /** @internal */
941 : struct Parent_status {
942 : CCC_Tribool correct;
943 : struct CCC_Adaptive_map_node const *parent;
944 : };
945 :
946 : static size_t
947 118882 : recursive_count(
948 : struct CCC_Adaptive_map const *const t,
949 : struct CCC_Adaptive_map_node const *const r
950 : ) {
951 118882 : if (r == NULL) {
952 60317 : return 0;
953 : }
954 117130 : return 1 + recursive_count(t, r->branch[R])
955 58565 : + recursive_count(t, r->branch[L]);
956 118882 : }
957 :
958 : static CCC_Tribool
959 118882 : are_subtrees_valid(
960 : struct CCC_Adaptive_map const *const t,
961 : struct Tree_range const r,
962 : struct CCC_Adaptive_map_node const *const nil
963 : ) {
964 118882 : if (r.root == nil) {
965 60317 : return CCC_TRUE;
966 : }
967 58565 : if (r.low != nil
968 58565 : && order(t, key_from_node(t, r.low), r.root) != CCC_ORDER_LESSER) {
969 0 : return CCC_FALSE;
970 : }
971 58565 : if (r.high != nil
972 58565 : && order(t, key_from_node(t, r.high), r.root) != CCC_ORDER_GREATER) {
973 0 : return CCC_FALSE;
974 : }
975 117130 : return are_subtrees_valid(
976 58565 : t,
977 234260 : (struct Tree_range){
978 58565 : .low = r.low,
979 58565 : .root = r.root->branch[L],
980 58565 : .high = r.root,
981 : },
982 58565 : nil
983 : )
984 58565 : && are_subtrees_valid(
985 58565 : t,
986 234260 : (struct Tree_range){
987 58565 : .low = r.root,
988 58565 : .root = r.root->branch[R],
989 58565 : .high = r.high,
990 : },
991 58565 : nil
992 : );
993 118882 : }
994 :
995 : static CCC_Tribool
996 118882 : is_parent_correct(
997 : struct CCC_Adaptive_map const *const t,
998 : struct CCC_Adaptive_map_node const *const parent,
999 : struct CCC_Adaptive_map_node const *const root
1000 : ) {
1001 118882 : if (root == NULL) {
1002 60317 : return CCC_TRUE;
1003 : }
1004 58565 : if (root->parent != parent) {
1005 0 : return CCC_FALSE;
1006 : }
1007 117130 : return is_parent_correct(t, root, root->branch[L])
1008 58565 : && is_parent_correct(t, root, root->branch[R]);
1009 118882 : }
1010 :
1011 : /** Validate tree prefers to use recursion to examine the tree over the provided
1012 : iterators of any implementation so as to avoid using a flawed implementation of
1013 : such iterators. This should help be more sure that the implementation is correct
1014 : because it follows the truth of the provided pointers with its own stack as
1015 : backtracking information. */
1016 : static CCC_Tribool
1017 1752 : validate(struct CCC_Adaptive_map const *const t) {
1018 1752 : if (!are_subtrees_valid(
1019 1752 : t,
1020 3504 : (struct Tree_range){
1021 : .low = NULL,
1022 1752 : .root = t->root,
1023 : .high = NULL,
1024 : },
1025 : NULL
1026 : )) {
1027 0 : return CCC_FALSE;
1028 : }
1029 1752 : if (!is_parent_correct(t, NULL, t->root)) {
1030 0 : return CCC_FALSE;
1031 : }
1032 1752 : if (recursive_count(t, t->root) != t->count) {
1033 0 : return CCC_FALSE;
1034 : }
1035 1752 : return CCC_TRUE;
1036 1752 : }
1037 :
1038 : /* NOLINTEND(*misc-no-recursion) */
|
