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 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 empty(map);
110 7 : }
111 :
112 : CCC_Count
113 123 : CCC_adaptive_map_count(CCC_Adaptive_map const *const map) {
114 123 : if (!map) {
115 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
116 : }
117 122 : return (CCC_Count){.count = map->size};
118 123 : }
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 1115 : CCC_adaptive_map_entry(CCC_Adaptive_map *const map, void const *const key) {
130 1115 : if (!map || !key) {
131 4 : return (CCC_Adaptive_map_entry){
132 2 : .entry = {.status = CCC_ENTRY_ARGUMENT_ERROR},
133 : };
134 : }
135 1113 : return entry(map, key);
136 1115 : }
137 :
138 : void *
139 339 : 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 339 : if (!entry || !type_intruder || !allocator) {
145 3 : return NULL;
146 : }
147 336 : 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 233 : return allocate_insert(entry->map, type_intruder, allocator);
159 339 : }
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 69 : *type_intruder = *elem_in_slot(map, found);
275 69 : assert(map->root != NULL);
276 69 : memcpy(found, struct_base(map, type_intruder), map->sizeof_type);
277 138 : return (CCC_Entry){
278 69 : .type = found,
279 : .status = CCC_ENTRY_OCCUPIED,
280 : };
281 : }
282 562 : void *const inserted = allocate_insert(map, type_intruder, allocator);
283 562 : if (!inserted) {
284 1 : return (CCC_Entry){
285 : .type = NULL,
286 : .status = CCC_ENTRY_INSERT_ERROR,
287 : };
288 : }
289 1122 : return (CCC_Entry){
290 561 : .type = inserted,
291 : .status = CCC_ENTRY_VACANT,
292 : };
293 634 : }
294 :
295 : CCC_Entry
296 200 : 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 200 : if (!map || !type_output_intruder || !allocator) {
302 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
303 : }
304 197 : void *const n = erase(map, key_from_node(map, type_output_intruder));
305 197 : if (!n) {
306 3 : return (CCC_Entry){
307 : .type = NULL,
308 : .status = CCC_ENTRY_VACANT,
309 : };
310 : }
311 194 : if (allocator->allocate) {
312 178 : void *const any_struct = struct_base(map, type_output_intruder);
313 178 : memcpy(any_struct, n, map->sizeof_type);
314 534 : allocator->allocate((CCC_Allocator_arguments){
315 178 : .input = n,
316 : .bytes = 0,
317 178 : .context = allocator->context,
318 : });
319 356 : return (CCC_Entry){
320 178 : .type = any_struct,
321 : .status = CCC_ENTRY_OCCUPIED,
322 : };
323 178 : }
324 32 : return (CCC_Entry){
325 16 : .type = n,
326 : .status = CCC_ENTRY_OCCUPIED,
327 : };
328 200 : }
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 283 : CCC_adaptive_map_end(CCC_Adaptive_map const *const) {
413 283 : return NULL;
414 : }
415 :
416 : void *
417 146 : CCC_adaptive_map_reverse_end(CCC_Adaptive_map const *const) {
418 146 : return NULL;
419 : }
420 :
421 : void *
422 501 : CCC_adaptive_map_next(
423 : CCC_Adaptive_map const *const map,
424 : CCC_Adaptive_map_node const *const iterator_intruder
425 : ) {
426 501 : if (!map || !iterator_intruder) {
427 2 : return NULL;
428 : }
429 998 : struct CCC_Adaptive_map_node const *n
430 499 : = next(map, iterator_intruder, INORDER);
431 499 : return n == NULL ? NULL : struct_base(map, n);
432 501 : }
433 :
434 : void *
435 168 : CCC_adaptive_map_reverse_next(
436 : CCC_Adaptive_map const *const map,
437 : CCC_Adaptive_map_node const *const iterator_intruder
438 : ) {
439 168 : if (!map || !iterator_intruder) {
440 2 : return NULL;
441 : }
442 332 : struct CCC_Adaptive_map_node const *n
443 166 : = next(map, iterator_intruder, INORDER_REVERSE);
444 166 : return n == NULL ? NULL : struct_base(map, n);
445 168 : }
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 1059 : while (node != NULL) {
491 1046 : if (node->branch[L] != NULL) {
492 505 : struct CCC_Adaptive_map_node *const l = node->branch[L];
493 505 : node->branch[L] = l->branch[R];
494 505 : l->branch[R] = node;
495 505 : node = l;
496 : continue;
497 505 : }
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 : return CCC_RESULT_OK;
518 16 : }
519 :
520 : CCC_Tribool
521 1751 : CCC_adaptive_map_validate(CCC_Adaptive_map const *const map) {
522 1751 : if (!map) {
523 1 : return CCC_TRIBOOL_ERROR;
524 : }
525 1750 : return validate(map);
526 1751 : }
527 :
528 : /*========================== Private Interface ============================*/
529 :
530 : struct CCC_Adaptive_map_entry
531 98 : CCC_private_adaptive_map_entry(
532 : struct CCC_Adaptive_map *const t, void const *const key
533 : ) {
534 98 : return entry(t, key);
535 98 : }
536 :
537 : void *
538 196 : CCC_private_adaptive_map_insert(
539 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *n
540 : ) {
541 196 : return insert(t, n);
542 : }
543 :
544 : void *
545 87 : CCC_private_adaptive_map_key_in_slot(
546 : struct CCC_Adaptive_map const *const t, void const *const slot
547 : ) {
548 87 : return key_in_slot(t, slot);
549 : }
550 :
551 : struct CCC_Adaptive_map_node *
552 214 : CCC_private_adaptive_map_node_in_slot(
553 : struct CCC_Adaptive_map const *const t, void const *slot
554 : ) {
555 214 : return elem_in_slot(t, slot);
556 : }
557 :
558 : /*====================== Static Splay Tree Helpers ========================*/
559 :
560 : static struct CCC_Adaptive_map_entry
561 1211 : entry(struct CCC_Adaptive_map *const t, void const *const key) {
562 1211 : void *const found = find(t, key);
563 1211 : if (found) {
564 1947 : return (struct CCC_Adaptive_map_entry){
565 649 : .map = t,
566 1298 : .entry = {
567 649 : .type = found,
568 : .status = CCC_ENTRY_OCCUPIED,
569 : },
570 : };
571 : }
572 1686 : return (struct CCC_Adaptive_map_entry){
573 562 : .map = t,
574 1124 : .entry = {
575 562 : .type = found,
576 : .status = CCC_ENTRY_VACANT,
577 : },
578 : };
579 1211 : }
580 :
581 : static inline void *
582 92535 : key_from_node(
583 : struct CCC_Adaptive_map const *const t, CCC_Adaptive_map_node const *const n
584 : ) {
585 92535 : return n ? (char *)struct_base(t, n) + t->key_offset : NULL;
586 : }
587 :
588 : static inline void *
589 297 : key_in_slot(struct CCC_Adaptive_map const *const t, void const *const slot) {
590 297 : return slot ? (char *)slot + t->key_offset : NULL;
591 : }
592 :
593 : static inline struct CCC_Adaptive_map_node *
594 1876 : elem_in_slot(struct CCC_Adaptive_map const *const t, void const *const slot) {
595 :
596 1876 : return slot ? (struct CCC_Adaptive_map_node *)((char *)slot
597 1876 : + t->type_intruder_offset)
598 : : NULL;
599 : }
600 :
601 : static inline void
602 3216 : init_node(struct CCC_Adaptive_map_node *const n) {
603 3216 : n->branch[L] = NULL;
604 3216 : n->branch[R] = NULL;
605 3216 : n->parent = NULL;
606 3216 : }
607 :
608 : static inline CCC_Tribool
609 3664 : empty(struct CCC_Adaptive_map const *const t) {
610 3664 : return !t->size || !t->root || t->root == NULL;
611 : }
612 :
613 : static void *
614 3 : max(struct CCC_Adaptive_map const *const t) {
615 3 : if (!t->size) {
616 0 : return NULL;
617 : }
618 3 : struct CCC_Adaptive_map_node *m = t->root;
619 17 : for (; m->branch[R] != NULL; m = m->branch[R]) {}
620 3 : return struct_base(t, m);
621 3 : }
622 :
623 : static void *
624 9 : min(struct CCC_Adaptive_map const *t) {
625 9 : if (!t->size) {
626 1 : return NULL;
627 : }
628 8 : struct CCC_Adaptive_map_node *m = t->root;
629 72 : for (; m->branch[L] != NULL; m = m->branch[L]) {}
630 8 : return struct_base(t, m);
631 9 : }
632 :
633 : static struct CCC_Adaptive_map_node const *
634 672 : next(
635 : struct CCC_Adaptive_map const *const t [[maybe_unused]],
636 : struct CCC_Adaptive_map_node const *n,
637 : enum Link const traversal
638 : ) {
639 672 : if (!n) {
640 0 : return NULL;
641 : }
642 672 : assert(t->root->parent == NULL);
643 : /* The node is a parent, backtracked to, or the end. */
644 672 : if (n->branch[traversal] != NULL) {
645 : /* The goal is to get far left/right ASAP in any traversal. */
646 614 : for (n = n->branch[traversal]; n->branch[!traversal] != NULL;
647 289 : n = n->branch[!traversal]) {}
648 325 : return n;
649 : }
650 : /* This is how to return internal nodes on the way back up from a leaf. */
651 650 : for (; n->parent && n->parent->branch[!traversal] != n; n = n->parent) {}
652 347 : return n->parent;
653 672 : }
654 :
655 : static CCC_Range
656 10 : equal_range(
657 : struct CCC_Adaptive_map *const t,
658 : void const *const begin_key,
659 : void const *const end_key,
660 : enum Link const traversal
661 : ) {
662 10 : if (!t->size) {
663 2 : return (CCC_Range){};
664 : }
665 : /* As with most BST code the cases are perfectly symmetrical. If we
666 : are seeking an increasing or decreasing range we need to make sure
667 : we follow the [inclusive, exclusive) range rule. This means double
668 : checking we don't need to progress to the next greatest or next
669 : lesser element depending on the direction we are traversing. */
670 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
671 8 : struct CCC_Adaptive_map_node const *b = splay(t, t->root, begin_key);
672 8 : if (order(t, begin_key, b) == les_or_grt[traversal]) {
673 2 : b = next(t, b, traversal);
674 2 : }
675 8 : struct CCC_Adaptive_map_node const *e = splay(t, t->root, end_key);
676 8 : if (order(t, end_key, e) != les_or_grt[!traversal]) {
677 5 : e = next(t, e, traversal);
678 5 : }
679 24 : return (CCC_Range){
680 8 : .begin = b == NULL ? NULL : struct_base(t, b),
681 8 : .end = e == NULL ? NULL : struct_base(t, e),
682 : };
683 10 : }
684 :
685 : static void *
686 2499 : find(struct CCC_Adaptive_map *const t, void const *const key) {
687 2499 : if (t->root == NULL) {
688 61 : return NULL;
689 : }
690 2438 : t->root = splay(t, t->root, key);
691 2438 : return order(t, key, t->root) == CCC_ORDER_EQUAL ? struct_base(t, t->root)
692 : : NULL;
693 2499 : }
694 :
695 : static CCC_Tribool
696 10 : contains(struct CCC_Adaptive_map *const t, void const *const key) {
697 10 : t->root = splay(t, t->root, key);
698 10 : return order(t, key, t->root) == CCC_ORDER_EQUAL;
699 : }
700 :
701 : static void *
702 1530 : allocate_insert(
703 : struct CCC_Adaptive_map *const t,
704 : struct CCC_Adaptive_map_node *out_handle,
705 : CCC_Allocator const *const allocator
706 : ) {
707 1530 : init_node(out_handle);
708 1530 : CCC_Order root_order = CCC_ORDER_ERROR;
709 1530 : if (!empty(t)) {
710 1496 : void const *const key = key_from_node(t, out_handle);
711 1496 : t->root = splay(t, t->root, key);
712 1496 : root_order = order(t, key, t->root);
713 1496 : if (CCC_ORDER_EQUAL == root_order) {
714 0 : return NULL;
715 : }
716 1496 : }
717 1530 : if (allocator->allocate) {
718 4485 : void *const node = allocator->allocate((CCC_Allocator_arguments){
719 : .input = NULL,
720 1495 : .bytes = t->sizeof_type,
721 1495 : .context = allocator->context,
722 : });
723 1495 : if (!node) {
724 5 : return NULL;
725 : }
726 1490 : (void)memcpy(node, struct_base(t, out_handle), t->sizeof_type);
727 1490 : out_handle = elem_in_slot(t, node);
728 1490 : init_node(out_handle);
729 1495 : }
730 1525 : if (empty(t)) {
731 34 : t->root = out_handle;
732 34 : t->size = 1;
733 34 : return struct_base(t, out_handle);
734 : }
735 1491 : assert(root_order != CCC_ORDER_ERROR);
736 1491 : t->size++;
737 1491 : return connect_new_root(t, out_handle, root_order);
738 1530 : }
739 :
740 : static void *
741 196 : insert(
742 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *const n
743 : ) {
744 196 : init_node(n);
745 196 : if (empty(t)) {
746 12 : t->root = n;
747 12 : t->size = 1;
748 12 : return struct_base(t, n);
749 : }
750 184 : void const *const key = key_from_node(t, n);
751 184 : t->root = splay(t, t->root, key);
752 184 : CCC_Order const root_order = order(t, key, t->root);
753 184 : if (CCC_ORDER_EQUAL == root_order) {
754 0 : return NULL;
755 : }
756 184 : t->size++;
757 184 : return connect_new_root(t, n, root_order);
758 196 : }
759 :
760 : static void *
761 1675 : connect_new_root(
762 : struct CCC_Adaptive_map *const t,
763 : struct CCC_Adaptive_map_node *const new_root,
764 : CCC_Order const order_result
765 : ) {
766 1675 : assert(new_root);
767 1675 : enum Link const dir = CCC_ORDER_GREATER == order_result;
768 1675 : link(new_root, dir, t->root->branch[dir]);
769 1675 : link(new_root, !dir, t->root);
770 1675 : t->root->branch[dir] = NULL;
771 1675 : t->root = new_root;
772 1675 : t->root->parent = NULL;
773 3350 : return struct_base(t, new_root);
774 1675 : }
775 :
776 : static void *
777 407 : erase(struct CCC_Adaptive_map *const t, void const *const key) {
778 407 : if (empty(t)) {
779 1 : return NULL;
780 : }
781 406 : struct CCC_Adaptive_map_node *ret = splay(t, t->root, key);
782 406 : CCC_Order const found = order(t, key, ret);
783 406 : if (found != CCC_ORDER_EQUAL) {
784 2 : return NULL;
785 : }
786 404 : ret = remove_from_tree(t, ret);
787 404 : ret->branch[L] = ret->branch[R] = ret->parent = NULL;
788 404 : t->size--;
789 404 : return struct_base(t, ret);
790 407 : }
791 :
792 : static struct CCC_Adaptive_map_node *
793 404 : remove_from_tree(
794 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *const ret
795 : ) {
796 404 : if (ret->branch[L] == NULL) {
797 67 : t->root = ret->branch[R];
798 67 : if (t->root) {
799 60 : t->root->parent = NULL;
800 60 : }
801 67 : } else {
802 337 : t->root = splay(t, ret->branch[L], key_from_node(t, ret));
803 337 : link(t->root, R, ret->branch[R]);
804 : }
805 404 : return ret;
806 : }
807 :
808 : /** Adopts D. Sleator technique for splaying. Notable to this method is the
809 : general improvement to the tree that occurs because we always splay the key
810 : to the root, OR the next closest value to the key to the root. This has
811 : interesting performance implications for real data sets.
812 :
813 : This implementation has been modified to unite the left and right symmetries
814 : and manage the parent pointers. Parent pointers are not usual for splay trees
815 : but are necessary for a clean iteration API. */
816 : static struct CCC_Adaptive_map_node *
817 4887 : splay(
818 : struct CCC_Adaptive_map *const t,
819 : struct CCC_Adaptive_map_node *root,
820 : void const *const key
821 : ) {
822 4887 : assert(root);
823 : /* Splaying brings the key element up to the root. The zigzag fixes of
824 : splaying repair the tree and we remember the roots of these changes in
825 : this helper tree. At the end, make the root pick up these modified left
826 : and right helpers. The nil node should NULL initialized to start. */
827 4887 : struct CCC_Adaptive_map_node nil = {};
828 4887 : struct CCC_Adaptive_map_node *left_right_subtrees[LR] = {&nil, &nil};
829 11344 : for (;;) {
830 11344 : CCC_Order const root_order = order(t, key, root);
831 11344 : enum Link const order_link = CCC_ORDER_GREATER == root_order;
832 11344 : struct CCC_Adaptive_map_node *const child = root->branch[order_link];
833 11344 : if (CCC_ORDER_EQUAL == root_order || child == NULL) {
834 4244 : break;
835 : }
836 7100 : CCC_Order const child_order = order(t, key, child);
837 7100 : enum Link const child_order_link = CCC_ORDER_GREATER == child_order;
838 : /* A straight line would form from root->child->key. An opportunity
839 : to splay and heal the tree arises. */
840 7100 : if (CCC_ORDER_EQUAL != child_order && order_link == child_order_link) {
841 4187 : root->branch[order_link] = child->branch[!order_link];
842 4187 : if (child->branch[!order_link]) {
843 2052 : child->branch[!order_link]->parent = root;
844 2052 : }
845 4187 : child->branch[!order_link] = root;
846 4187 : root->parent = child;
847 4187 : root = child;
848 4187 : if (root->branch[order_link] == NULL) {
849 643 : break;
850 : }
851 3544 : }
852 6457 : left_right_subtrees[!order_link]->branch[order_link] = root;
853 6457 : root->parent = left_right_subtrees[!order_link];
854 6457 : left_right_subtrees[!order_link] = root;
855 6457 : root = root->branch[order_link];
856 11344 : }
857 4887 : left_right_subtrees[L]->branch[R] = root->branch[L];
858 4887 : if (left_right_subtrees[L] != &nil && root->branch[L]) {
859 418 : root->branch[L]->parent = left_right_subtrees[L];
860 418 : }
861 4887 : left_right_subtrees[R]->branch[L] = root->branch[R];
862 4887 : if (left_right_subtrees[R] != &nil && root->branch[R]) {
863 363 : root->branch[R]->parent = left_right_subtrees[R];
864 363 : }
865 4887 : root->branch[L] = nil.branch[R];
866 4887 : if (nil.branch[R]) {
867 4549 : nil.branch[R]->parent = root;
868 4549 : }
869 4887 : root->branch[R] = nil.branch[L];
870 4887 : if (nil.branch[L]) {
871 2605 : nil.branch[L]->parent = root;
872 2605 : }
873 4887 : root->parent = NULL;
874 4887 : t->root = root;
875 9774 : return root;
876 4887 : }
877 :
878 : static inline void *
879 210524 : struct_base(
880 : struct CCC_Adaptive_map const *const t,
881 : struct CCC_Adaptive_map_node const *const n
882 : ) {
883 : /* Link is the first field of the struct and is an array so no need to get
884 : pointer address of [0] element of array. That's the same as just the
885 : array field. */
886 210524 : return n ? ((char *)n->branch) - t->type_intruder_offset : NULL;
887 : }
888 :
889 : static inline CCC_Order
890 112042 : order(
891 : struct CCC_Adaptive_map const *const t,
892 : void const *const key,
893 : struct CCC_Adaptive_map_node const *const node
894 : ) {
895 448168 : return t->comparator.compare((CCC_Key_comparator_arguments){
896 112042 : .key_left = key,
897 112042 : .type_right = struct_base(t, node),
898 112042 : .context = t->comparator.context,
899 : });
900 : }
901 :
902 : static inline void
903 6 : swap(void *const temp, void *const a, void *const b, size_t sizeof_type) {
904 6 : if (a == b || !a || !b) {
905 0 : return;
906 : }
907 6 : (void)memcpy(temp, a, sizeof_type);
908 6 : (void)memcpy(a, b, sizeof_type);
909 6 : (void)memcpy(b, temp, sizeof_type);
910 12 : }
911 :
912 : static inline void
913 3687 : link(
914 : struct CCC_Adaptive_map_node *const parent,
915 : enum Link const dir,
916 : struct CCC_Adaptive_map_node *const subtree
917 : ) {
918 3687 : if (parent) {
919 3687 : parent->branch[dir] = subtree;
920 3687 : }
921 3687 : if (subtree) {
922 2735 : subtree->parent = parent;
923 2735 : }
924 3687 : }
925 :
926 : /* NOLINTBEGIN(*misc-no-recursion) */
927 :
928 : /* ====================== Debugging ====================== */
929 :
930 : /** @internal Validate binary tree invariants with ranges. Use a recursive
931 : method that does not rely upon the implementation of iterators or any other
932 : possibly buggy implementation. A pure functional range check will provide the
933 : most reliable check regardless of implementation changes throughout code base.
934 : */
935 : struct Tree_range {
936 : struct CCC_Adaptive_map_node const *low;
937 : struct CCC_Adaptive_map_node const *root;
938 : struct CCC_Adaptive_map_node const *high;
939 : };
940 :
941 : /** @internal */
942 : struct Parent_status {
943 : CCC_Tribool correct;
944 : struct CCC_Adaptive_map_node const *parent;
945 : };
946 :
947 : static size_t
948 118894 : recursive_count(
949 : struct CCC_Adaptive_map const *const t,
950 : struct CCC_Adaptive_map_node const *const r
951 : ) {
952 118894 : if (r == NULL) {
953 60322 : return 0;
954 : }
955 117144 : return 1 + recursive_count(t, r->branch[R])
956 58572 : + recursive_count(t, r->branch[L]);
957 118894 : }
958 :
959 : static CCC_Tribool
960 118894 : are_subtrees_valid(
961 : struct CCC_Adaptive_map const *const t,
962 : struct Tree_range const r,
963 : struct CCC_Adaptive_map_node const *const nil
964 : ) {
965 118894 : if (r.root == nil) {
966 60322 : return CCC_TRUE;
967 : }
968 58572 : if (r.low != nil
969 58572 : && order(t, key_from_node(t, r.low), r.root) != CCC_ORDER_LESSER) {
970 0 : return CCC_FALSE;
971 : }
972 58572 : if (r.high != nil
973 58572 : && order(t, key_from_node(t, r.high), r.root) != CCC_ORDER_GREATER) {
974 0 : return CCC_FALSE;
975 : }
976 117144 : return are_subtrees_valid(
977 58572 : t,
978 234288 : (struct Tree_range){
979 58572 : .low = r.low,
980 58572 : .root = r.root->branch[L],
981 58572 : .high = r.root,
982 : },
983 58572 : nil
984 : )
985 58572 : && are_subtrees_valid(
986 58572 : t,
987 234288 : (struct Tree_range){
988 58572 : .low = r.root,
989 58572 : .root = r.root->branch[R],
990 58572 : .high = r.high,
991 : },
992 58572 : nil
993 : );
994 118894 : }
995 :
996 : static CCC_Tribool
997 118894 : is_parent_correct(
998 : struct CCC_Adaptive_map const *const t,
999 : struct CCC_Adaptive_map_node const *const parent,
1000 : struct CCC_Adaptive_map_node const *const root
1001 : ) {
1002 118894 : if (root == NULL) {
1003 60322 : return CCC_TRUE;
1004 : }
1005 58572 : if (root->parent != parent) {
1006 0 : return CCC_FALSE;
1007 : }
1008 117144 : return is_parent_correct(t, root, root->branch[L])
1009 58572 : && is_parent_correct(t, root, root->branch[R]);
1010 118894 : }
1011 :
1012 : /* Validate tree prefers to use recursion to examine the tree over the
1013 : provided iterators of any implementation so as to avoid using a
1014 : flawed implementation of such iterators. This should help be more
1015 : sure that the implementation is correct because it follows the
1016 : truth of the provided pointers with its own stack as backtracking
1017 : information. */
1018 : static CCC_Tribool
1019 1750 : validate(struct CCC_Adaptive_map const *const t) {
1020 1750 : if (!are_subtrees_valid(
1021 1750 : t,
1022 3500 : (struct Tree_range){
1023 : .low = NULL,
1024 1750 : .root = t->root,
1025 : .high = NULL,
1026 : },
1027 : NULL
1028 : )) {
1029 0 : return CCC_FALSE;
1030 : }
1031 1750 : if (!is_parent_correct(t, NULL, t->root)) {
1032 0 : return CCC_FALSE;
1033 : }
1034 1750 : if (recursive_count(t, t->root) != t->size) {
1035 0 : return CCC_FALSE;
1036 : }
1037 1750 : return CCC_TRUE;
1038 1750 : }
1039 :
1040 : /* NOLINTEND(*misc-no-recursion) */
|
