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/configuration.h" /* IWYU pragma: keep */
34 : #include "ccc/specialized/adaptive_map.h"
35 : #include "ccc/specialized/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 *, size_t, void *, void *);
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 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, map->sizeof_type, in_tree, any_struct);
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 84 : *type_intruder = *elem_in_slot(map, found);
275 84 : assert(map->root != NULL);
276 84 : memcpy(found, struct_base(map, type_intruder), map->sizeof_type);
277 168 : return (CCC_Entry){
278 84 : .type = found,
279 : .status = CCC_ENTRY_OCCUPIED,
280 : };
281 : }
282 547 : void *const inserted = allocate_insert(map, type_intruder, allocator);
283 547 : if (!inserted) {
284 1 : return (CCC_Entry){
285 : .type = NULL,
286 : .status = CCC_ENTRY_INSERT_ERROR,
287 : };
288 : }
289 1092 : return (CCC_Entry){
290 546 : .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 712 : allocator->allocate((CCC_Allocator_arguments){
315 178 : .input = n,
316 : .bytes = 0,
317 178 : .alignment = map->alignof_type,
318 178 : .context = allocator->context,
319 : });
320 356 : return (CCC_Entry){
321 178 : .type = any_struct,
322 : .status = CCC_ENTRY_OCCUPIED,
323 : };
324 178 : }
325 32 : return (CCC_Entry){
326 16 : .type = n,
327 : .status = CCC_ENTRY_OCCUPIED,
328 : };
329 200 : }
330 :
331 : CCC_Entry
332 222 : CCC_adaptive_map_remove_entry(
333 : CCC_Adaptive_map_entry *const e, CCC_Allocator const *const allocator
334 : ) {
335 222 : if (!e || !allocator) {
336 2 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
337 : }
338 220 : if (e->entry.status == CCC_ENTRY_OCCUPIED && e->entry.type) {
339 210 : void *const erased = erase(e->map, key_in_slot(e->map, e->entry.type));
340 210 : assert(erased);
341 210 : if (allocator->allocate) {
342 776 : allocator->allocate((CCC_Allocator_arguments){
343 194 : .input = erased,
344 : .bytes = 0,
345 194 : .alignment = e->map->alignof_type,
346 194 : .context = allocator->context,
347 : });
348 194 : return (CCC_Entry){
349 : .type = NULL,
350 : .status = CCC_ENTRY_OCCUPIED,
351 : };
352 : }
353 32 : return (CCC_Entry){
354 16 : .type = erased,
355 : .status = CCC_ENTRY_OCCUPIED,
356 : };
357 210 : }
358 10 : return (CCC_Entry){
359 : .type = NULL,
360 : .status = CCC_ENTRY_VACANT,
361 : };
362 222 : }
363 :
364 : void *
365 17 : CCC_adaptive_map_get_key_value(
366 : CCC_Adaptive_map *const map, void const *const key
367 : ) {
368 17 : if (!map || !key) {
369 2 : return NULL;
370 : }
371 15 : return find(map, key);
372 17 : }
373 :
374 : void *
375 26 : CCC_adaptive_map_unwrap(CCC_Adaptive_map_entry const *const e) {
376 26 : if (!e) {
377 1 : return NULL;
378 : }
379 25 : return e->entry.status == CCC_ENTRY_OCCUPIED ? e->entry.type : NULL;
380 26 : }
381 :
382 : CCC_Tribool
383 2 : CCC_adaptive_map_insert_error(CCC_Adaptive_map_entry const *const e) {
384 2 : if (!e) {
385 1 : return CCC_TRIBOOL_ERROR;
386 : }
387 1 : return (e->entry.status & CCC_ENTRY_INSERT_ERROR) != 0;
388 2 : }
389 :
390 : CCC_Tribool
391 29 : CCC_adaptive_map_occupied(CCC_Adaptive_map_entry const *const e) {
392 29 : if (!e) {
393 1 : return CCC_TRIBOOL_ERROR;
394 : }
395 28 : return (e->entry.status & CCC_ENTRY_OCCUPIED) != 0;
396 29 : }
397 :
398 : CCC_Entry_status
399 2 : CCC_adaptive_map_entry_status(CCC_Adaptive_map_entry const *const e) {
400 2 : return e ? e->entry.status : CCC_ENTRY_ARGUMENT_ERROR;
401 : }
402 :
403 : void *
404 10 : CCC_adaptive_map_begin(CCC_Adaptive_map const *const map) {
405 10 : return map ? min(map) : NULL;
406 : }
407 :
408 : void *
409 3 : CCC_adaptive_map_reverse_begin(CCC_Adaptive_map const *const map) {
410 3 : return map ? max(map) : NULL;
411 : }
412 :
413 : void *
414 268 : CCC_adaptive_map_end(CCC_Adaptive_map const *const) {
415 268 : return NULL;
416 : }
417 :
418 : void *
419 131 : CCC_adaptive_map_reverse_end(CCC_Adaptive_map const *const) {
420 131 : return NULL;
421 : }
422 :
423 : void *
424 471 : CCC_adaptive_map_next(
425 : CCC_Adaptive_map const *const map,
426 : CCC_Adaptive_map_node const *const iterator_intruder
427 : ) {
428 471 : if (!map || !iterator_intruder) {
429 2 : return NULL;
430 : }
431 938 : struct CCC_Adaptive_map_node const *n
432 469 : = next(map, iterator_intruder, INORDER);
433 469 : return n == NULL ? NULL : struct_base(map, n);
434 471 : }
435 :
436 : void *
437 153 : CCC_adaptive_map_reverse_next(
438 : CCC_Adaptive_map const *const map,
439 : CCC_Adaptive_map_node const *const iterator_intruder
440 : ) {
441 153 : if (!map || !iterator_intruder) {
442 2 : return NULL;
443 : }
444 302 : struct CCC_Adaptive_map_node const *n
445 151 : = next(map, iterator_intruder, INORDER_REVERSE);
446 151 : return n == NULL ? NULL : struct_base(map, n);
447 153 : }
448 :
449 : CCC_Range
450 8 : CCC_adaptive_map_equal_range(
451 : CCC_Adaptive_map *const map,
452 : void const *const begin_key,
453 : void const *const end_key
454 : ) {
455 8 : if (!map || !begin_key || !end_key) {
456 3 : return (CCC_Range){};
457 : }
458 5 : return equal_range(map, begin_key, end_key, INORDER);
459 8 : }
460 :
461 : CCC_Range_reverse
462 8 : CCC_adaptive_map_equal_range_reverse(
463 : CCC_Adaptive_map *const map,
464 : void const *const reverse_begin_key,
465 : void const *const reverse_end_key
466 : )
467 :
468 : {
469 8 : if (!map || !reverse_begin_key || !reverse_end_key) {
470 3 : return (CCC_Range_reverse){};
471 : }
472 5 : CCC_Range const range
473 5 : = equal_range(map, reverse_begin_key, reverse_end_key, INORDER_REVERSE);
474 15 : return (CCC_Range_reverse){
475 5 : .reverse_begin = range.begin,
476 5 : .reverse_end = range.end,
477 : };
478 8 : }
479 :
480 : /** This is a linear time constant space deletion of tree nodes via left
481 : rotations so element fields are modified during progression of deletes. */
482 : CCC_Result
483 16 : CCC_adaptive_map_clear(
484 : CCC_Adaptive_map *const map,
485 : CCC_Destructor const *const destructor,
486 : CCC_Allocator const *const allocator
487 : ) {
488 16 : if (!map || !allocator || !destructor) {
489 3 : return CCC_RESULT_ARGUMENT_ERROR;
490 : }
491 13 : struct CCC_Adaptive_map_node *node = map->root;
492 1055 : while (node != NULL) {
493 1042 : if (node->branch[L] != NULL) {
494 501 : struct CCC_Adaptive_map_node *const l = node->branch[L];
495 501 : node->branch[L] = l->branch[R];
496 501 : l->branch[R] = node;
497 501 : node = l;
498 : continue;
499 501 : }
500 541 : struct CCC_Adaptive_map_node *const next = node->branch[R];
501 541 : node->branch[L] = node->branch[R] = NULL;
502 541 : node->parent = NULL;
503 541 : void *const del = struct_base(map, node);
504 541 : if (destructor->destroy) {
505 48 : destructor->destroy((CCC_Arguments){
506 16 : .type = del,
507 16 : .context = destructor->context,
508 : });
509 16 : }
510 541 : if (allocator->allocate) {
511 2164 : (void)allocator->allocate((CCC_Allocator_arguments){
512 541 : .input = del,
513 : .bytes = 0,
514 541 : .alignment = map->alignof_type,
515 541 : .context = allocator->context,
516 : });
517 541 : }
518 541 : node = next;
519 541 : }
520 13 : map->count = 0;
521 13 : map->root = NULL;
522 13 : return CCC_RESULT_OK;
523 16 : }
524 :
525 : CCC_Tribool
526 1751 : CCC_adaptive_map_validate(CCC_Adaptive_map const *const map) {
527 1751 : if (!map) {
528 1 : return CCC_TRIBOOL_ERROR;
529 : }
530 1750 : return validate(map);
531 1751 : }
532 :
533 : /*========================== Private Interface ============================*/
534 :
535 : struct CCC_Adaptive_map_entry
536 98 : CCC_private_adaptive_map_entry(
537 : struct CCC_Adaptive_map *const t, void const *const key
538 : ) {
539 98 : return entry(t, key);
540 98 : }
541 :
542 : void *
543 196 : CCC_private_adaptive_map_insert(
544 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *n
545 : ) {
546 196 : return insert(t, n);
547 : }
548 :
549 : void *
550 87 : CCC_private_adaptive_map_key_in_slot(
551 : struct CCC_Adaptive_map const *const t, void const *const slot
552 : ) {
553 87 : return key_in_slot(t, slot);
554 : }
555 :
556 : struct CCC_Adaptive_map_node *
557 214 : CCC_private_adaptive_map_node_in_slot(
558 : struct CCC_Adaptive_map const *const t, void const *slot
559 : ) {
560 214 : return elem_in_slot(t, slot);
561 : }
562 :
563 : /*====================== Static Splay Tree Helpers ========================*/
564 :
565 : static struct CCC_Adaptive_map_entry
566 1211 : entry(struct CCC_Adaptive_map *const t, void const *const key) {
567 1211 : void *const found = find(t, key);
568 1211 : if (found) {
569 1947 : return (struct CCC_Adaptive_map_entry){
570 649 : .map = t,
571 1298 : .entry = {
572 649 : .type = found,
573 : .status = CCC_ENTRY_OCCUPIED,
574 : },
575 : };
576 : }
577 1686 : return (struct CCC_Adaptive_map_entry){
578 562 : .map = t,
579 1124 : .entry = {
580 562 : .type = found,
581 : .status = CCC_ENTRY_VACANT,
582 : },
583 : };
584 1211 : }
585 :
586 : static inline void *
587 90862 : key_from_node(
588 : struct CCC_Adaptive_map const *const t, CCC_Adaptive_map_node const *const n
589 : ) {
590 90862 : return n ? (char *)struct_base(t, n) + t->key_offset : NULL;
591 : }
592 :
593 : static inline void *
594 297 : key_in_slot(struct CCC_Adaptive_map const *const t, void const *const slot) {
595 297 : return slot ? (char *)slot + t->key_offset : NULL;
596 : }
597 :
598 : static inline struct CCC_Adaptive_map_node *
599 1876 : elem_in_slot(struct CCC_Adaptive_map const *const t, void const *const slot) {
600 :
601 1876 : return slot ? (struct CCC_Adaptive_map_node *)((char *)slot
602 1876 : + t->type_intruder_offset)
603 : : NULL;
604 : }
605 :
606 : static inline void
607 3186 : init_node(struct CCC_Adaptive_map_node *const n) {
608 3186 : n->branch[L] = NULL;
609 3186 : n->branch[R] = NULL;
610 3186 : n->parent = NULL;
611 3186 : }
612 :
613 : static inline CCC_Tribool
614 3634 : is_empty(struct CCC_Adaptive_map const *const t) {
615 3634 : return !t->count || !t->root;
616 : }
617 :
618 : static void *
619 3 : max(struct CCC_Adaptive_map const *const t) {
620 3 : if (!t->count) {
621 0 : return NULL;
622 : }
623 3 : struct CCC_Adaptive_map_node *m = t->root;
624 21 : for (; m->branch[R] != NULL; m = m->branch[R]) {}
625 3 : return struct_base(t, m);
626 3 : }
627 :
628 : static void *
629 9 : min(struct CCC_Adaptive_map const *t) {
630 9 : if (!t->count) {
631 1 : return NULL;
632 : }
633 8 : struct CCC_Adaptive_map_node *m = t->root;
634 36 : for (; m->branch[L] != NULL; m = m->branch[L]) {}
635 8 : return struct_base(t, m);
636 9 : }
637 :
638 : static struct CCC_Adaptive_map_node const *
639 627 : next(
640 : struct CCC_Adaptive_map const *const t [[maybe_unused]],
641 : struct CCC_Adaptive_map_node const *n,
642 : enum Link const traversal
643 : ) {
644 627 : if (!n) {
645 0 : return NULL;
646 : }
647 627 : assert(t->root->parent == NULL);
648 627 : if (n->branch[traversal] != NULL) {
649 603 : for (n = n->branch[traversal]; n->branch[!traversal] != NULL;
650 288 : n = n->branch[!traversal]) {}
651 315 : return n;
652 : }
653 605 : for (; n->parent && n->parent->branch[!traversal] != n; n = n->parent) {}
654 312 : return n->parent;
655 627 : }
656 :
657 : static CCC_Range
658 10 : equal_range(
659 : struct CCC_Adaptive_map *const t,
660 : void const *const begin_key,
661 : void const *const end_key,
662 : enum Link const traversal
663 : ) {
664 10 : if (!t->count) {
665 2 : return (CCC_Range){};
666 : }
667 : /* As with most BST code the cases are perfectly symmetrical. If we
668 : are seeking an increasing or decreasing range we need to make sure
669 : we follow the [inclusive, exclusive) range rule. This means double
670 : checking we don't need to progress to the next greatest or next
671 : lesser element depending on the direction we are traversing. */
672 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
673 8 : struct CCC_Adaptive_map_node const *b = splay(t, t->root, begin_key);
674 8 : if (order(t, begin_key, b) == les_or_grt[traversal]) {
675 2 : b = next(t, b, traversal);
676 2 : }
677 8 : struct CCC_Adaptive_map_node const *e = splay(t, t->root, end_key);
678 8 : if (order(t, end_key, e) != les_or_grt[!traversal]) {
679 5 : e = next(t, e, traversal);
680 5 : }
681 24 : return (CCC_Range){
682 8 : .begin = b == NULL ? NULL : struct_base(t, b),
683 8 : .end = e == NULL ? NULL : struct_base(t, e),
684 : };
685 10 : }
686 :
687 : static void *
688 2499 : find(struct CCC_Adaptive_map *const t, void const *const key) {
689 2499 : if (t->root == NULL) {
690 61 : return NULL;
691 : }
692 2438 : t->root = splay(t, t->root, key);
693 2438 : return order(t, key, t->root) == CCC_ORDER_EQUAL ? struct_base(t, t->root)
694 : : NULL;
695 2499 : }
696 :
697 : static CCC_Tribool
698 10 : contains(struct CCC_Adaptive_map *const t, void const *const key) {
699 10 : t->root = splay(t, t->root, key);
700 10 : return order(t, key, t->root) == CCC_ORDER_EQUAL;
701 : }
702 :
703 : static void *
704 1515 : allocate_insert(
705 : struct CCC_Adaptive_map *const t,
706 : struct CCC_Adaptive_map_node *out_handle,
707 : CCC_Allocator const *const allocator
708 : ) {
709 1515 : init_node(out_handle);
710 1515 : CCC_Order root_order = CCC_ORDER_ERROR;
711 1515 : if (!is_empty(t)) {
712 1481 : void const *const key = key_from_node(t, out_handle);
713 1481 : t->root = splay(t, t->root, key);
714 1481 : root_order = order(t, key, t->root);
715 1481 : if (CCC_ORDER_EQUAL == root_order) {
716 0 : return NULL;
717 : }
718 1481 : }
719 1515 : if (allocator->allocate) {
720 5920 : void *const node = allocator->allocate((CCC_Allocator_arguments){
721 : .input = NULL,
722 1480 : .bytes = t->sizeof_type,
723 1480 : .alignment = t->alignof_type,
724 1480 : .context = allocator->context,
725 : });
726 1480 : if (!node) {
727 5 : return NULL;
728 : }
729 1475 : (void)memcpy(node, struct_base(t, out_handle), t->sizeof_type);
730 1475 : out_handle = elem_in_slot(t, node);
731 1475 : init_node(out_handle);
732 1480 : }
733 1510 : if (is_empty(t)) {
734 34 : t->root = out_handle;
735 34 : t->count = 1;
736 34 : return struct_base(t, out_handle);
737 : }
738 1476 : assert(root_order != CCC_ORDER_ERROR);
739 1476 : t->count++;
740 1476 : return connect_new_root(t, out_handle, root_order);
741 1515 : }
742 :
743 : static void *
744 196 : insert(
745 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *const n
746 : ) {
747 196 : init_node(n);
748 196 : if (is_empty(t)) {
749 12 : t->root = n;
750 12 : t->count = 1;
751 12 : return struct_base(t, n);
752 : }
753 184 : void const *const key = key_from_node(t, n);
754 184 : t->root = splay(t, t->root, key);
755 184 : CCC_Order const root_order = order(t, key, t->root);
756 184 : if (CCC_ORDER_EQUAL == root_order) {
757 0 : return NULL;
758 : }
759 184 : t->count++;
760 184 : return connect_new_root(t, n, root_order);
761 196 : }
762 :
763 : static void *
764 1660 : connect_new_root(
765 : struct CCC_Adaptive_map *const t,
766 : struct CCC_Adaptive_map_node *const new_root,
767 : CCC_Order const order_result
768 : ) {
769 1660 : assert(new_root);
770 1660 : enum Link const dir = CCC_ORDER_GREATER == order_result;
771 1660 : link(new_root, dir, t->root->branch[dir]);
772 1660 : link(new_root, !dir, t->root);
773 1660 : t->root->branch[dir] = NULL;
774 1660 : t->root = new_root;
775 1660 : t->root->parent = NULL;
776 3320 : return struct_base(t, new_root);
777 1660 : }
778 :
779 : static void *
780 407 : erase(struct CCC_Adaptive_map *const t, void const *const key) {
781 407 : if (is_empty(t)) {
782 1 : return NULL;
783 : }
784 406 : struct CCC_Adaptive_map_node *ret = splay(t, t->root, key);
785 406 : CCC_Order const found = order(t, key, ret);
786 406 : if (found != CCC_ORDER_EQUAL) {
787 2 : return NULL;
788 : }
789 404 : ret = remove_from_tree(t, ret);
790 404 : ret->branch[L] = ret->branch[R] = ret->parent = NULL;
791 404 : t->count--;
792 404 : return struct_base(t, ret);
793 407 : }
794 :
795 : static struct CCC_Adaptive_map_node *
796 404 : remove_from_tree(
797 : struct CCC_Adaptive_map *const t, struct CCC_Adaptive_map_node *const ret
798 : ) {
799 404 : if (ret->branch[L] == NULL) {
800 76 : t->root = ret->branch[R];
801 76 : if (t->root) {
802 69 : t->root->parent = NULL;
803 69 : }
804 76 : } else {
805 328 : t->root = splay(t, ret->branch[L], key_from_node(t, ret));
806 328 : link(t->root, R, ret->branch[R]);
807 : }
808 404 : return ret;
809 : }
810 :
811 : /** Adopts D. Sleator technique for splaying. Notable to this method is the
812 : general improvement to the tree that occurs because we always splay the key
813 : to the root, OR the next closest value to the key to the root. This has
814 : interesting performance implications for real data sets.
815 :
816 : This implementation has been modified to unite the left and right symmetries
817 : and manage the parent pointers. Parent pointers are not usual for splay trees
818 : but are necessary for a clean iteration API. */
819 : static struct CCC_Adaptive_map_node *
820 4863 : splay(
821 : struct CCC_Adaptive_map *const t,
822 : struct CCC_Adaptive_map_node *root,
823 : void const *const key
824 : ) {
825 4863 : assert(root);
826 : /* Splaying brings the key element up to the root. The zigzag fixes of
827 : splaying repair the tree and we remember the roots of these changes in
828 : this helper tree. At the end, make the root pick up these modified left
829 : and right helpers. The nil node should NULL initialized to start. */
830 4863 : struct CCC_Adaptive_map_node nil = {};
831 4863 : struct CCC_Adaptive_map_node *left_right_subtrees[LR] = {&nil, &nil};
832 11237 : for (;;) {
833 11237 : CCC_Order const root_order = order(t, key, root);
834 11237 : enum Link const order_link = CCC_ORDER_GREATER == root_order;
835 11237 : struct CCC_Adaptive_map_node *const child = root->branch[order_link];
836 11237 : if (CCC_ORDER_EQUAL == root_order || child == NULL) {
837 4199 : break;
838 : }
839 7038 : CCC_Order const child_order = order(t, key, child);
840 7038 : enum Link const child_order_link = CCC_ORDER_GREATER == child_order;
841 : /* A straight line would form from root->child->key. An opportunity
842 : to splay and heal the tree arises. */
843 7038 : if (CCC_ORDER_EQUAL != child_order && order_link == child_order_link) {
844 4172 : root->branch[order_link] = child->branch[!order_link];
845 4172 : if (child->branch[!order_link]) {
846 2002 : child->branch[!order_link]->parent = root;
847 2002 : }
848 4172 : child->branch[!order_link] = root;
849 4172 : root->parent = child;
850 4172 : root = child;
851 4172 : if (root->branch[order_link] == NULL) {
852 664 : break;
853 : }
854 3508 : }
855 6374 : left_right_subtrees[!order_link]->branch[order_link] = root;
856 6374 : root->parent = left_right_subtrees[!order_link];
857 6374 : left_right_subtrees[!order_link] = root;
858 6374 : root = root->branch[order_link];
859 11237 : }
860 4863 : left_right_subtrees[L]->branch[R] = root->branch[L];
861 4863 : if (left_right_subtrees[L] != &nil && root->branch[L]) {
862 379 : root->branch[L]->parent = left_right_subtrees[L];
863 379 : }
864 4863 : left_right_subtrees[R]->branch[L] = root->branch[R];
865 4863 : if (left_right_subtrees[R] != &nil && root->branch[R]) {
866 358 : root->branch[R]->parent = left_right_subtrees[R];
867 358 : }
868 4863 : root->branch[L] = nil.branch[R];
869 4863 : if (nil.branch[R]) {
870 4493 : nil.branch[R]->parent = root;
871 4493 : }
872 4863 : root->branch[R] = nil.branch[L];
873 4863 : if (nil.branch[L]) {
874 2592 : nil.branch[L]->parent = root;
875 2592 : }
876 4863 : root->parent = NULL;
877 4863 : t->root = root;
878 9726 : return root;
879 4863 : }
880 :
881 : static inline void *
882 206973 : struct_base(
883 : struct CCC_Adaptive_map const *const t,
884 : struct CCC_Adaptive_map_node const *const n
885 : ) {
886 : /* Link is the first field of the struct and is an array so no need to get
887 : pointer address of [0] element of array. That's the same as just the
888 : array field. */
889 206973 : return n ? ((char *)n->branch) - t->type_intruder_offset : NULL;
890 : }
891 :
892 : static inline CCC_Order
893 110209 : order(
894 : struct CCC_Adaptive_map const *const t,
895 : void const *const key,
896 : struct CCC_Adaptive_map_node const *const node
897 : ) {
898 440836 : return t->comparator.compare((CCC_Key_comparator_arguments){
899 110209 : .key_left = key,
900 110209 : .type_right = struct_base(t, node),
901 110209 : .context = t->comparator.context,
902 : });
903 : }
904 :
905 : static inline void
906 6 : swap(void *const temp, size_t const sizeof_type, void *const a, void *const b) {
907 6 : if (a == b || !a || !b) {
908 0 : return;
909 : }
910 6 : (void)memcpy(temp, a, sizeof_type);
911 6 : (void)memcpy(a, b, sizeof_type);
912 6 : (void)memcpy(b, temp, sizeof_type);
913 12 : }
914 :
915 : static inline void
916 3648 : link(
917 : struct CCC_Adaptive_map_node *const parent,
918 : enum Link const dir,
919 : struct CCC_Adaptive_map_node *const subtree
920 : ) {
921 3648 : if (parent) {
922 3648 : parent->branch[dir] = subtree;
923 3648 : }
924 3648 : if (subtree) {
925 2690 : subtree->parent = parent;
926 2690 : }
927 3648 : }
928 :
929 : /* NOLINTBEGIN(*misc-no-recursion) */
930 :
931 : /* ====================== Debugging ====================== */
932 :
933 : /** @internal Validate binary tree invariants with ranges. Use a recursive
934 : method that does not rely upon the implementation of iterators or any other
935 : possibly buggy implementation. A pure functional range check will provide the
936 : most reliable check regardless of implementation changes throughout code base.
937 : */
938 : struct Tree_range {
939 : struct CCC_Adaptive_map_node const *low;
940 : struct CCC_Adaptive_map_node const *root;
941 : struct CCC_Adaptive_map_node const *high;
942 : };
943 :
944 : /** @internal */
945 : struct Parent_status {
946 : CCC_Tribool correct;
947 : struct CCC_Adaptive_map_node const *parent;
948 : };
949 :
950 : static size_t
951 117186 : recursive_count(
952 : struct CCC_Adaptive_map const *const t,
953 : struct CCC_Adaptive_map_node const *const r
954 : ) {
955 117186 : if (r == NULL) {
956 59468 : return 0;
957 : }
958 115436 : return 1 + recursive_count(t, r->branch[R])
959 57718 : + recursive_count(t, r->branch[L]);
960 117186 : }
961 :
962 : static CCC_Tribool
963 117186 : are_subtrees_valid(
964 : struct CCC_Adaptive_map const *const t,
965 : struct Tree_range const r,
966 : struct CCC_Adaptive_map_node const *const nil
967 : ) {
968 117186 : if (r.root == nil) {
969 59468 : return CCC_TRUE;
970 : }
971 57718 : if (r.low != nil
972 57718 : && order(t, key_from_node(t, r.low), r.root) != CCC_ORDER_LESSER) {
973 0 : return CCC_FALSE;
974 : }
975 57718 : if (r.high != nil
976 57718 : && order(t, key_from_node(t, r.high), r.root) != CCC_ORDER_GREATER) {
977 0 : return CCC_FALSE;
978 : }
979 115436 : return are_subtrees_valid(
980 57718 : t,
981 230872 : (struct Tree_range){
982 57718 : .low = r.low,
983 57718 : .root = r.root->branch[L],
984 57718 : .high = r.root,
985 : },
986 57718 : nil
987 : )
988 57718 : && are_subtrees_valid(
989 57718 : t,
990 230872 : (struct Tree_range){
991 57718 : .low = r.root,
992 57718 : .root = r.root->branch[R],
993 57718 : .high = r.high,
994 : },
995 57718 : nil
996 : );
997 117186 : }
998 :
999 : static CCC_Tribool
1000 117186 : is_parent_correct(
1001 : struct CCC_Adaptive_map const *const t,
1002 : struct CCC_Adaptive_map_node const *const parent,
1003 : struct CCC_Adaptive_map_node const *const root
1004 : ) {
1005 117186 : if (root == NULL) {
1006 59468 : return CCC_TRUE;
1007 : }
1008 57718 : if (root->parent != parent) {
1009 0 : return CCC_FALSE;
1010 : }
1011 115436 : return is_parent_correct(t, root, root->branch[L])
1012 57718 : && is_parent_correct(t, root, root->branch[R]);
1013 117186 : }
1014 :
1015 : /** Validate tree prefers to use recursion to examine the tree over the provided
1016 : iterators of any implementation so as to avoid using a flawed implementation of
1017 : such iterators. This should help be more sure that the implementation is correct
1018 : because it follows the truth of the provided pointers with its own stack as
1019 : backtracking information. */
1020 : static CCC_Tribool
1021 1750 : validate(struct CCC_Adaptive_map const *const t) {
1022 1750 : if (!are_subtrees_valid(
1023 1750 : t,
1024 3500 : (struct Tree_range){
1025 : .low = NULL,
1026 1750 : .root = t->root,
1027 : .high = NULL,
1028 : },
1029 : NULL
1030 : )) {
1031 0 : return CCC_FALSE;
1032 : }
1033 1750 : if (!is_parent_correct(t, NULL, t->root)) {
1034 0 : return CCC_FALSE;
1035 : }
1036 1750 : if (recursive_count(t, t->root) != t->count) {
1037 0 : return CCC_FALSE;
1038 : }
1039 1750 : return CCC_TRUE;
1040 1750 : }
1041 :
1042 : /* NOLINTEND(*misc-no-recursion) */
|
