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. It is also in a Struct
29 : of Arrays layout to improve memory alignment and reduce wasted space. While
30 : it is recommended that the user reserve space for the needed nodes ahead of
31 : time, the amortized O(log(N)) run times of a Splay Tree remain the same in
32 : the dynamic resizing case. */
33 : /** C23 provided headers. */
34 : #include <stdalign.h>
35 : #include <stddef.h>
36 : #include <stdint.h>
37 :
38 : /** CCC provided headers. */
39 : #include "ccc/configuration.h" /* IWYU pragma: keep */
40 : #include "ccc/specialized/array_adaptive_map.h"
41 : #include "ccc/specialized/private/private_array_adaptive_map.h"
42 : #include "ccc/types.h"
43 : #include "source/compiler_utilities.h"
44 :
45 : /*========================== Type Declarations ===========================*/
46 :
47 : /** @internal */
48 : enum : uint8_t {
49 : LR = 2,
50 : };
51 :
52 : /** @internal */
53 : enum Branch : uint8_t {
54 : L = 0,
55 : R,
56 : };
57 :
58 : #define INORDER R
59 : #define INORDER_REVERSE L
60 :
61 : enum : uint8_t {
62 : /** 0th slot is sentinel. Count will be 2 when inserting new root. */
63 : INSERT_ROOT_NODE_COUNT = 2,
64 : };
65 :
66 : /*======================== Data Alignment Test ==========================*/
67 :
68 : enum : size_t {
69 : /** @internal Test capacity. */
70 : TCAP = 3,
71 : /** @internal Alignment of node type. */
72 : ALIGNOF_NODE = alignof(struct CCC_Array_adaptive_map_node),
73 : /** @internal Size of node type. */
74 : SIZEOF_NODE = sizeof(struct CCC_Array_adaptive_map_node),
75 : };
76 : /** @internal This is a static fixed size map exclusive to this translation unit
77 : used to ensure assumptions about data layout are correct. The following static
78 : asserts must be true in order to support the Struct of Array style layout we
79 : use for the data and nodes. It is important that in our user code when we set
80 : the positions of the node pointer relative to the data pointer the positions are
81 : correct regardless of backing storage as a fixed map or heap allocation.
82 :
83 : Use an int because that will force the nodes array to be wary of
84 : where to start. The nodes are 8 byte aligned but an int is 4. This means the
85 : nodes need to start after a 4 byte buffer of padding at end of data array. */
86 : [[maybe_unused]] static __auto_type const static_data_nodes_layout_test
87 : = CCC_array_adaptive_map_storage_for((int const[TCAP]){});
88 : /** Some assumptions in the code assume that nodes array is last so ensure that
89 : is the case here. Also good to assume user data comes first. */
90 : static_assert(
91 : offsetof(typeof(static_data_nodes_layout_test), data)
92 : < offsetof(typeof(static_data_nodes_layout_test), nodes),
93 : "The order of the arrays in a Struct of Arrays map is data, then "
94 : "nodes."
95 : );
96 : /** We don't care about the alignment or padding after the nodes array because
97 : we never need to set or move any pointers to that position. The alignment is
98 : important for the nodes pointer to be set to the correct aligned position and
99 : so that we allocate enough bytes for our single allocation if the map is dynamic
100 : and not a fixed type. */
101 : static_assert(
102 : offsetof(typeof(static_data_nodes_layout_test), nodes[TCAP])
103 : - offsetof(typeof(static_data_nodes_layout_test), data[0])
104 : == CCC_roundup(
105 : (sizeof(*static_data_nodes_layout_test.data) * TCAP),
106 : ALIGNOF_NODE
107 : ) + (SIZEOF_NODE * TCAP),
108 : "The pointer difference in bytes between end of the nodes array and start "
109 : "of user data array must be the same as the total bytes we assume to be "
110 : "stored in that range. Alignment of user data must be considered."
111 : );
112 : static_assert(
113 : offsetof(typeof(static_data_nodes_layout_test), data)
114 : + CCC_roundup(
115 : (sizeof(*static_data_nodes_layout_test.data) * TCAP),
116 : ALIGNOF_NODE
117 : )
118 : == offsetof(typeof(static_data_nodes_layout_test), nodes),
119 : "The start of the nodes array must begin at the next aligned "
120 : "byte given alignment of a node."
121 : );
122 :
123 : /*============================== Prototypes ==============================*/
124 :
125 : static size_t splay(struct CCC_Array_adaptive_map *, size_t, void const *);
126 : static struct CCC_Array_adaptive_map_node *
127 : node_at(struct CCC_Array_adaptive_map const *, size_t);
128 : static void *data_at(struct CCC_Array_adaptive_map const *, size_t);
129 : static struct CCC_Array_adaptive_map_handle
130 : handle(struct CCC_Array_adaptive_map *, void const *);
131 : static size_t erase(struct CCC_Array_adaptive_map *, void const *);
132 : static size_t maybe_allocate_insert(
133 : struct CCC_Array_adaptive_map *, void const *, CCC_Allocator const *
134 : );
135 : static CCC_Result
136 : resize(struct CCC_Array_adaptive_map *, size_t, CCC_Allocator const *);
137 : static void
138 : resize_struct_of_arrays(struct CCC_Array_adaptive_map const *, void *, size_t);
139 : static size_t data_bytes(size_t, size_t);
140 : static size_t nodes_bytes(size_t);
141 : static struct CCC_Array_adaptive_map_node *
142 : nodes_base_address(size_t, void const *, size_t);
143 : static size_t find(struct CCC_Array_adaptive_map *, void const *);
144 : static void
145 : connect_new_root(struct CCC_Array_adaptive_map *, size_t, CCC_Order);
146 : static void insert(struct CCC_Array_adaptive_map *, size_t n);
147 : static void *key_in_slot(struct CCC_Array_adaptive_map const *, void const *);
148 : static size_t
149 : allocate_slot(struct CCC_Array_adaptive_map *, CCC_Allocator const *);
150 : static CCC_Tribool checked_total_bytes(size_t *, size_t, size_t);
151 : static CCC_Handle_range equal_range(
152 : struct CCC_Array_adaptive_map *, void const *, void const *, enum Branch
153 : );
154 : static void *key_at(struct CCC_Array_adaptive_map const *, size_t);
155 : static CCC_Order
156 : order_nodes(struct CCC_Array_adaptive_map const *, void const *, size_t);
157 : static size_t remove_from_tree(struct CCC_Array_adaptive_map *, size_t);
158 : static size_t
159 : min_max_from(struct CCC_Array_adaptive_map const *, size_t, enum Branch);
160 : static size_t next(struct CCC_Array_adaptive_map const *, size_t, enum Branch);
161 : static size_t
162 : branch_index(struct CCC_Array_adaptive_map const *, size_t, enum Branch);
163 : static size_t parent_index(struct CCC_Array_adaptive_map const *, size_t);
164 : static size_t *
165 : branch_pointer(struct CCC_Array_adaptive_map const *, size_t, enum Branch);
166 : static size_t *parent_pointer(struct CCC_Array_adaptive_map const *, size_t);
167 : static CCC_Tribool validate(struct CCC_Array_adaptive_map const *);
168 : static void init_node(struct CCC_Array_adaptive_map const *, size_t);
169 : static void swap(void *, size_t, void *, void *);
170 : static void link(struct CCC_Array_adaptive_map *, size_t, enum Branch, size_t);
171 : static void
172 : delete_nodes(struct CCC_Array_adaptive_map const *, CCC_Destructor const *);
173 :
174 : /*============================== Interface ==============================*/
175 :
176 : void *
177 16735 : CCC_array_adaptive_map_at(
178 : CCC_Array_adaptive_map const *const map, CCC_Handle_index const index
179 : ) {
180 16735 : if (!map || !index) {
181 13 : return NULL;
182 : }
183 16722 : return data_at(map, index);
184 16735 : }
185 :
186 : CCC_Tribool
187 66 : CCC_array_adaptive_map_contains(
188 : CCC_Array_adaptive_map *const map, void const *const key
189 : ) {
190 66 : if (!map || !key) {
191 2 : return CCC_TRIBOOL_ERROR;
192 : }
193 64 : map->root = splay(map, map->root, key);
194 64 : return order_nodes(map, key, map->root) == CCC_ORDER_EQUAL;
195 66 : }
196 :
197 : CCC_Handle_index
198 2017 : CCC_array_adaptive_map_get_key_value(
199 : CCC_Array_adaptive_map *const map, void const *const key
200 : ) {
201 2017 : if (!map || !key) {
202 2 : return 0;
203 : }
204 2015 : return find(map, key);
205 2017 : }
206 :
207 : CCC_Array_adaptive_map_handle
208 13044 : CCC_array_adaptive_map_handle(
209 : CCC_Array_adaptive_map *const map, void const *const key
210 : ) {
211 13044 : if (!map || !key) {
212 2 : return (CCC_Array_adaptive_map_handle){
213 : .status = CCC_ENTRY_ARGUMENT_ERROR,
214 : };
215 : }
216 13042 : return handle(map, key);
217 13044 : }
218 :
219 : CCC_Handle_index
220 8381 : CCC_array_adaptive_map_insert_handle(
221 : CCC_Array_adaptive_map_handle const *const handle,
222 : void const *const key_val_type,
223 : CCC_Allocator const *const allocator
224 : ) {
225 8381 : if (!handle || !key_val_type || !allocator) {
226 3 : return 0;
227 : }
228 8378 : if (handle->status == CCC_ENTRY_OCCUPIED) {
229 3105 : void *const ret = data_at(handle->map, handle->index);
230 3105 : if (key_val_type != ret) {
231 3105 : (void)memcpy(ret, key_val_type, handle->map->sizeof_type);
232 3105 : }
233 3105 : return handle->index;
234 3105 : }
235 5273 : return maybe_allocate_insert(handle->map, key_val_type, allocator);
236 8381 : }
237 :
238 : CCC_Array_adaptive_map_handle *
239 112 : CCC_array_adaptive_map_and_modify(
240 : CCC_Array_adaptive_map_handle *const handle,
241 : CCC_Modifier const *const modifier
242 : ) {
243 112 : if (!handle || !modifier) {
244 2 : return NULL;
245 : }
246 110 : if (modifier->modify && handle->status & CCC_ENTRY_OCCUPIED) {
247 168 : modifier->modify((CCC_Arguments){
248 56 : .type = data_at(handle->map, handle->index),
249 56 : .context = modifier->context,
250 : });
251 56 : }
252 110 : return handle;
253 112 : }
254 :
255 : CCC_Handle_index
256 262 : CCC_array_adaptive_map_or_insert(
257 : CCC_Array_adaptive_map_handle const *const handle,
258 : void const *const key_val_type,
259 : CCC_Allocator const *const allocator
260 : ) {
261 262 : if (!handle || !key_val_type || !allocator) {
262 3 : return 0;
263 : }
264 259 : if (handle->status & CCC_ENTRY_OCCUPIED) {
265 153 : return handle->index;
266 : }
267 106 : return maybe_allocate_insert(handle->map, key_val_type, allocator);
268 262 : }
269 :
270 : CCC_Handle
271 1565 : CCC_array_adaptive_map_swap_handle(
272 : CCC_Array_adaptive_map *const map,
273 : void *const type_output,
274 : CCC_Allocator const *const allocator
275 : ) {
276 1565 : if (!map || !type_output || !allocator) {
277 3 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
278 : }
279 1562 : size_t const found = find(map, key_in_slot(map, type_output));
280 1562 : if (found) {
281 107 : assert(map->root);
282 107 : void *const ret = data_at(map, map->root);
283 107 : void *const temp = data_at(map, 0);
284 107 : swap(temp, map->sizeof_type, type_output, ret);
285 214 : return (CCC_Handle){
286 107 : .index = found,
287 : .status = CCC_ENTRY_OCCUPIED,
288 : };
289 107 : }
290 1455 : size_t const inserted = maybe_allocate_insert(map, type_output, allocator);
291 1455 : if (!inserted) {
292 1 : return (CCC_Handle){
293 : .index = 0,
294 : .status = CCC_ENTRY_INSERT_ERROR,
295 : };
296 : }
297 2908 : return (CCC_Handle){
298 1454 : .index = inserted,
299 : .status = CCC_ENTRY_VACANT,
300 : };
301 1565 : }
302 :
303 : CCC_Handle
304 1224 : CCC_array_adaptive_map_try_insert(
305 : CCC_Array_adaptive_map *const map,
306 : void const *const key_val_type,
307 : CCC_Allocator const *const allocator
308 : ) {
309 1224 : if (!map || !key_val_type || !allocator) {
310 3 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
311 : }
312 1221 : size_t const found = find(map, key_in_slot(map, key_val_type));
313 1221 : if (found) {
314 423 : assert(map->root);
315 846 : return (CCC_Handle){
316 423 : .index = found,
317 : .status = CCC_ENTRY_OCCUPIED,
318 : };
319 : }
320 798 : size_t const inserted = maybe_allocate_insert(map, key_val_type, allocator);
321 798 : if (!inserted) {
322 1 : return (CCC_Handle){
323 : .index = 0,
324 : .status = CCC_ENTRY_INSERT_ERROR,
325 : };
326 : }
327 1594 : return (CCC_Handle){
328 797 : .index = inserted,
329 : .status = CCC_ENTRY_VACANT,
330 : };
331 1224 : }
332 :
333 : CCC_Handle
334 3022 : CCC_array_adaptive_map_insert_or_assign(
335 : CCC_Array_adaptive_map *const map,
336 : void const *const key_val_type,
337 : CCC_Allocator const *const allocator
338 : ) {
339 3022 : if (!map || !key_val_type || !allocator) {
340 3 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
341 : }
342 3019 : size_t const found = find(map, key_in_slot(map, key_val_type));
343 3019 : if (found) {
344 383 : assert(map->root);
345 383 : void *const f_base = data_at(map, found);
346 383 : if (key_val_type != f_base) {
347 383 : memcpy(f_base, key_val_type, map->sizeof_type);
348 383 : }
349 766 : return (CCC_Handle){
350 383 : .index = found,
351 : .status = CCC_ENTRY_OCCUPIED,
352 : };
353 383 : }
354 2636 : size_t const inserted = maybe_allocate_insert(map, key_val_type, allocator);
355 2636 : if (!inserted) {
356 3 : return (CCC_Handle){
357 : .index = 0,
358 : .status = CCC_ENTRY_INSERT_ERROR,
359 : };
360 : }
361 5266 : return (CCC_Handle){
362 2633 : .index = inserted,
363 : .status = CCC_ENTRY_VACANT,
364 : };
365 3022 : }
366 :
367 : CCC_Handle
368 2280 : CCC_array_adaptive_map_remove_key_value(
369 : CCC_Array_adaptive_map *const map, void *const type_output
370 : ) {
371 2280 : if (!map || !type_output) {
372 2 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
373 : }
374 2278 : size_t const removed = erase(map, key_in_slot(map, type_output));
375 2278 : if (!removed) {
376 3 : return (CCC_Handle){
377 : .index = 0,
378 : .status = CCC_ENTRY_VACANT,
379 : };
380 : }
381 2275 : assert(removed);
382 2275 : void const *const r = data_at(map, removed);
383 2275 : if (type_output != r) {
384 2275 : (void)memcpy(type_output, r, map->sizeof_type);
385 2275 : }
386 2275 : return (CCC_Handle){
387 : .index = 0,
388 : .status = CCC_ENTRY_OCCUPIED,
389 : };
390 2280 : }
391 :
392 : CCC_Handle
393 55 : CCC_array_adaptive_map_remove_handle(
394 : CCC_Array_adaptive_map_handle *const handle
395 : ) {
396 55 : if (!handle) {
397 1 : return (CCC_Handle){.status = CCC_ENTRY_ARGUMENT_ERROR};
398 : }
399 54 : if (handle->status == CCC_ENTRY_OCCUPIED) {
400 88 : size_t const erased
401 44 : = erase(handle->map, key_at(handle->map, handle->index));
402 44 : assert(erased);
403 88 : return (CCC_Handle){
404 44 : .index = erased,
405 : .status = CCC_ENTRY_OCCUPIED,
406 : };
407 44 : }
408 10 : return (CCC_Handle){
409 : .index = 0,
410 : .status = CCC_ENTRY_VACANT,
411 : };
412 55 : }
413 :
414 : CCC_Handle_index
415 16 : CCC_array_adaptive_map_unwrap(
416 : CCC_Array_adaptive_map_handle const *const handle
417 : ) {
418 16 : if (!handle) {
419 1 : return 0;
420 : }
421 15 : return handle->status == CCC_ENTRY_OCCUPIED ? handle->index : 0;
422 16 : }
423 :
424 : CCC_Tribool
425 3 : CCC_array_adaptive_map_insert_error(
426 : CCC_Array_adaptive_map_handle const *const handle
427 : ) {
428 3 : if (!handle) {
429 2 : return CCC_TRIBOOL_ERROR;
430 : }
431 1 : return (handle->status & CCC_ENTRY_INSERT_ERROR) != 0;
432 3 : }
433 :
434 : CCC_Tribool
435 84 : CCC_array_adaptive_map_occupied(
436 : CCC_Array_adaptive_map_handle const *const handle
437 : ) {
438 84 : if (!handle) {
439 1 : return CCC_TRIBOOL_ERROR;
440 : }
441 83 : return (handle->status & CCC_ENTRY_OCCUPIED) != 0;
442 84 : }
443 :
444 : CCC_Handle_status
445 2 : CCC_array_adaptive_map_handle_status(
446 : CCC_Array_adaptive_map_handle const *const handle
447 : ) {
448 2 : return handle ? handle->status : CCC_ENTRY_ARGUMENT_ERROR;
449 : }
450 :
451 : CCC_Tribool
452 2353 : CCC_array_adaptive_map_is_empty(CCC_Array_adaptive_map const *const map) {
453 2353 : if (!map) {
454 1 : return CCC_TRIBOOL_ERROR;
455 : }
456 2352 : return !CCC_array_adaptive_map_count(map).count;
457 2353 : }
458 :
459 : CCC_Count
460 2506 : CCC_array_adaptive_map_count(CCC_Array_adaptive_map const *const map) {
461 2506 : if (!map) {
462 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
463 : }
464 5010 : return (CCC_Count){
465 2505 : .count = map->count ? map->count - 1 : 0,
466 : };
467 2506 : }
468 :
469 : CCC_Count
470 12 : CCC_array_adaptive_map_capacity(CCC_Array_adaptive_map const *const map) {
471 12 : if (!map) {
472 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
473 : }
474 11 : return (CCC_Count){.count = map->capacity};
475 12 : }
476 :
477 : CCC_Handle_index
478 16 : CCC_array_adaptive_map_begin(CCC_Array_adaptive_map const *const map) {
479 16 : if (!map || !map->capacity) {
480 3 : return 0;
481 : }
482 13 : size_t const n = min_max_from(map, map->root, L);
483 13 : return n;
484 16 : }
485 :
486 : CCC_Handle_index
487 3 : CCC_array_adaptive_map_reverse_begin(CCC_Array_adaptive_map const *const map) {
488 3 : if (!map || !map->capacity) {
489 1 : return 0;
490 : }
491 2 : size_t const n = min_max_from(map, map->root, R);
492 2 : return n;
493 3 : }
494 :
495 : CCC_Handle_index
496 2942 : CCC_array_adaptive_map_next(
497 : CCC_Array_adaptive_map const *const map, CCC_Handle_index const iterator
498 : ) {
499 2942 : if (!map || !map->capacity) {
500 1 : return 0;
501 : }
502 2941 : size_t const n = next(map, iterator, INORDER);
503 2941 : return n;
504 2942 : }
505 :
506 : CCC_Handle_index
507 1265 : CCC_array_adaptive_map_reverse_next(
508 : CCC_Array_adaptive_map const *const map, CCC_Handle_index const iterator
509 : ) {
510 1265 : if (!map || !iterator || !map->capacity) {
511 1 : return 0;
512 : }
513 1264 : size_t const n = next(map, iterator, INORDER_REVERSE);
514 1264 : return n;
515 1265 : }
516 :
517 : CCC_Handle_index
518 4184 : CCC_array_adaptive_map_end(CCC_Array_adaptive_map const *const) {
519 4184 : return 0;
520 : }
521 :
522 : CCC_Handle_index
523 4 : CCC_array_adaptive_map_reverse_end(CCC_Array_adaptive_map const *const) {
524 4 : return 0;
525 : }
526 :
527 : CCC_Handle_range
528 8 : CCC_array_adaptive_map_equal_range(
529 : CCC_Array_adaptive_map *const map,
530 : void const *const begin_key,
531 : void const *const end_key
532 : ) {
533 8 : if (!map || !begin_key || !end_key) {
534 3 : return (CCC_Handle_range){};
535 : }
536 5 : return equal_range(map, begin_key, end_key, INORDER);
537 8 : }
538 :
539 : CCC_Handle_range_reverse
540 8 : CCC_array_adaptive_map_equal_range_reverse(
541 : CCC_Array_adaptive_map *const map,
542 : void const *const reverse_begin_key,
543 : void const *const reverse_end_key
544 : )
545 :
546 : {
547 8 : if (!map || !reverse_begin_key || !reverse_end_key) {
548 3 : return (CCC_Handle_range_reverse){};
549 : }
550 5 : CCC_Handle_range const range
551 5 : = equal_range(map, reverse_begin_key, reverse_end_key, INORDER_REVERSE);
552 15 : return (CCC_Handle_range_reverse){
553 5 : .reverse_begin = range.begin,
554 5 : .reverse_end = range.end,
555 : };
556 8 : }
557 :
558 : CCC_Result
559 15 : CCC_array_adaptive_map_reserve(
560 : CCC_Array_adaptive_map *const map,
561 : size_t const to_add,
562 : CCC_Allocator const *const allocator
563 : ) {
564 15 : if (!map || !to_add || !allocator || !allocator->allocate) {
565 3 : return CCC_RESULT_ARGUMENT_ERROR;
566 : }
567 12 : size_t const needed = map->count + to_add + (map->count == 0);
568 12 : if (needed <= map->capacity) {
569 1 : return CCC_RESULT_OK;
570 : }
571 11 : size_t const old_count = map->count;
572 11 : size_t old_cap = map->capacity;
573 11 : CCC_Result const r = resize(map, needed, allocator);
574 11 : if (r != CCC_RESULT_OK) {
575 1 : return r;
576 : }
577 10 : if (!old_cap) {
578 10 : map->count = 1;
579 10 : }
580 10 : old_cap = old_count ? old_cap : 0;
581 10 : size_t const new_cap = map->capacity;
582 10 : size_t prev = 0;
583 10 : size_t i = new_cap;
584 1445 : while (i--) {
585 1445 : if (i <= old_cap) {
586 10 : break;
587 : }
588 1435 : node_at(map, i)->next_free = prev;
589 1435 : prev = i;
590 : }
591 10 : if (!map->free_list) {
592 10 : map->free_list = prev;
593 10 : }
594 10 : return CCC_RESULT_OK;
595 15 : }
596 :
597 : CCC_Result
598 7 : CCC_array_adaptive_map_copy(
599 : CCC_Array_adaptive_map *const destination,
600 : CCC_Array_adaptive_map const *const source,
601 : CCC_Allocator const *const allocator
602 : ) {
603 7 : if (!destination || !source || !allocator || source == destination
604 7 : || (destination->capacity < source->capacity && !allocator->allocate)) {
605 2 : return CCC_RESULT_ARGUMENT_ERROR;
606 : }
607 5 : if (!source->capacity) {
608 1 : return CCC_RESULT_OK;
609 : }
610 4 : if (destination->capacity < source->capacity) {
611 3 : CCC_Result const r = resize(destination, source->capacity, allocator);
612 3 : if (r != CCC_RESULT_OK) {
613 1 : return r;
614 : }
615 3 : } else {
616 : /* Might not be necessary but not worth finding out. Do every time. */
617 1 : destination->nodes = nodes_base_address(
618 1 : destination->sizeof_type, destination->data, destination->capacity
619 : );
620 : }
621 3 : if (!destination->data || !source->data) {
622 1 : return CCC_RESULT_ARGUMENT_ERROR;
623 : }
624 2 : resize_struct_of_arrays(source, destination->data, destination->capacity);
625 2 : destination->free_list = source->free_list;
626 2 : destination->root = source->root;
627 2 : destination->count = source->count;
628 2 : destination->comparator = source->comparator;
629 2 : destination->sizeof_type = source->sizeof_type;
630 2 : destination->key_offset = source->key_offset;
631 2 : return CCC_RESULT_OK;
632 7 : }
633 :
634 : CCC_Result
635 2 : CCC_array_adaptive_map_clear(
636 : CCC_Array_adaptive_map *const map, CCC_Destructor const *const destructor
637 : ) {
638 2 : if (!map || !destructor) {
639 1 : return CCC_RESULT_ARGUMENT_ERROR;
640 : }
641 1 : if (destructor->destroy) {
642 1 : delete_nodes(map, destructor);
643 1 : }
644 1 : map->count = 1;
645 1 : map->root = 0;
646 1 : return CCC_RESULT_OK;
647 2 : }
648 :
649 : CCC_Result
650 20 : CCC_array_adaptive_map_clear_and_free(
651 : CCC_Array_adaptive_map *const map,
652 : CCC_Destructor const *const destructor,
653 : CCC_Allocator const *const allocator
654 : ) {
655 20 : if (!map || !destructor || !allocator || !allocator->allocate) {
656 4 : return CCC_RESULT_ARGUMENT_ERROR;
657 : }
658 16 : if (destructor->destroy) {
659 1 : delete_nodes(map, destructor);
660 1 : }
661 16 : map->root = 0;
662 16 : map->count = 0;
663 16 : map->capacity = 0;
664 64 : (void)allocator->allocate((CCC_Allocator_arguments){
665 16 : .input = map->data,
666 : .bytes = 0,
667 16 : .alignment = CCC_max(ALIGNOF_NODE, map->alignof_type),
668 16 : .context = allocator->context,
669 : });
670 16 : map->data = NULL;
671 16 : map->nodes = NULL;
672 16 : return CCC_RESULT_OK;
673 20 : }
674 :
675 : CCC_Tribool
676 9866 : CCC_array_adaptive_map_validate(CCC_Array_adaptive_map const *const map) {
677 9866 : if (!map) {
678 1 : return CCC_TRIBOOL_ERROR;
679 : }
680 9865 : return validate(map);
681 9866 : }
682 :
683 : /*=========================== Private Interface ===========================*/
684 :
685 : void
686 144 : CCC_private_array_adaptive_map_insert(
687 : struct CCC_Array_adaptive_map *const map, size_t const elem_i
688 : ) {
689 144 : insert(map, elem_i);
690 144 : }
691 :
692 : struct CCC_Array_adaptive_map_handle
693 48 : CCC_private_array_adaptive_map_handle(
694 : struct CCC_Array_adaptive_map *const map, void const *const key
695 : ) {
696 48 : return handle(map, key);
697 48 : }
698 :
699 : void *
700 36 : CCC_private_array_adaptive_map_key_at(
701 : struct CCC_Array_adaptive_map const *const map, size_t const slot
702 : ) {
703 36 : return key_at(map, slot);
704 : }
705 :
706 : void *
707 2207 : CCC_private_array_adaptive_map_data_at(
708 : struct CCC_Array_adaptive_map const *const map, size_t const slot
709 : ) {
710 2207 : return data_at(map, slot);
711 : }
712 :
713 : size_t
714 146 : CCC_private_array_adaptive_map_allocate_slot(
715 : struct CCC_Array_adaptive_map *const map,
716 : CCC_Allocator const *const allocator
717 : ) {
718 146 : return allocate_slot(map, allocator);
719 : }
720 :
721 : /*=========================== Static Helpers ===========================*/
722 :
723 : static CCC_Handle_range
724 10 : equal_range(
725 : struct CCC_Array_adaptive_map *const t,
726 : void const *const begin_key,
727 : void const *const end_key,
728 : enum Branch const traversal
729 : ) {
730 10 : if (CCC_array_adaptive_map_is_empty(t)) {
731 2 : return (CCC_Handle_range){};
732 : }
733 : /* As with most BST code the cases are perfectly symmetrical. If we
734 : are seeking an increasing or decreasing range we need to make sure
735 : we follow the [inclusive, exclusive) range rule. This means double
736 : checking we don't need to progress to the next greatest or next
737 : lesser element depending on the direction we are traversing. */
738 8 : CCC_Order const les_or_grt[2] = {CCC_ORDER_LESSER, CCC_ORDER_GREATER};
739 8 : size_t b = splay(t, t->root, begin_key);
740 8 : if (order_nodes(t, begin_key, b) == les_or_grt[traversal]) {
741 2 : b = next(t, b, traversal);
742 2 : }
743 8 : size_t e = splay(t, t->root, end_key);
744 8 : if (order_nodes(t, end_key, e) != les_or_grt[!traversal]) {
745 5 : e = next(t, e, traversal);
746 5 : }
747 24 : return (CCC_Handle_range){
748 8 : .begin = b,
749 8 : .end = e,
750 : };
751 10 : }
752 :
753 : static struct CCC_Array_adaptive_map_handle
754 13090 : handle(struct CCC_Array_adaptive_map *const map, void const *const key) {
755 13090 : size_t const found = find(map, key);
756 13090 : if (found) {
757 22542 : return (struct CCC_Array_adaptive_map_handle){
758 7514 : .map = map,
759 7514 : .index = found,
760 : .status = CCC_ENTRY_OCCUPIED,
761 : };
762 : }
763 11152 : return (struct CCC_Array_adaptive_map_handle){
764 5576 : .map = map,
765 : .index = 0,
766 : .status = CCC_ENTRY_VACANT,
767 : };
768 13090 : }
769 :
770 : static size_t
771 10268 : maybe_allocate_insert(
772 : struct CCC_Array_adaptive_map *const map,
773 : void const *const user_type,
774 : CCC_Allocator const *const allocator
775 : ) {
776 10268 : size_t const node = allocate_slot(map, allocator);
777 10268 : if (!node) {
778 8 : return 0;
779 : }
780 10260 : (void)memcpy(data_at(map, node), user_type, map->sizeof_type);
781 10260 : insert(map, node);
782 10260 : return node;
783 10268 : }
784 :
785 : static size_t
786 10414 : allocate_slot(
787 : struct CCC_Array_adaptive_map *const map,
788 : CCC_Allocator const *const allocator
789 : ) {
790 : /* The end sentinel node will always be at 0. This also means once
791 : initialized the internal size for implementer is always at least 1. */
792 10414 : size_t const old_count = map->count;
793 10414 : size_t old_cap = map->capacity;
794 10414 : if (!old_count || old_count == old_cap) {
795 94 : assert(!map->free_list);
796 94 : if (old_count == old_cap) {
797 49 : size_t new_cap = 0;
798 49 : if (ckd_mul(&new_cap, old_cap, 2)) {
799 0 : return 0;
800 : }
801 49 : if (resize(map, CCC_max(new_cap, 8U), allocator) != CCC_RESULT_OK) {
802 10 : return 0;
803 : }
804 49 : } else {
805 45 : map->nodes = nodes_base_address(
806 45 : map->sizeof_type, map->data, map->capacity
807 : );
808 : }
809 84 : old_cap = old_count ? old_cap : 1;
810 84 : size_t const new_cap = map->capacity;
811 84 : size_t prev = 0;
812 16980 : for (size_t i = new_cap - 1; i >= old_cap; prev = i, --i) {
813 16896 : node_at(map, i)->next_free = prev;
814 16896 : }
815 84 : map->free_list = prev;
816 84 : map->count = CCC_max(old_count, 1U);
817 84 : }
818 10404 : assert(map->free_list);
819 10404 : ++map->count;
820 10404 : size_t const slot = map->free_list;
821 10404 : map->free_list = node_at(map, slot)->next_free;
822 10404 : return slot;
823 10414 : }
824 :
825 : static CCC_Result
826 63 : resize(
827 : struct CCC_Array_adaptive_map *const map,
828 : size_t const new_capacity,
829 : CCC_Allocator const *const allocator
830 : ) {
831 63 : if (!allocator->allocate) {
832 9 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
833 : }
834 54 : size_t new_bytes = 0;
835 54 : if (checked_total_bytes(&new_bytes, map->sizeof_type, new_capacity)) {
836 0 : return CCC_RESULT_ALLOCATOR_ERROR;
837 : }
838 216 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
839 : .input = NULL,
840 54 : .bytes = new_bytes,
841 54 : .alignment = CCC_max(ALIGNOF_NODE, map->alignof_type),
842 54 : .context = allocator->context,
843 : });
844 54 : if (!new_data) {
845 3 : return CCC_RESULT_ALLOCATOR_ERROR;
846 : }
847 51 : resize_struct_of_arrays(map, new_data, new_capacity);
848 51 : map->nodes = nodes_base_address(map->sizeof_type, new_data, new_capacity);
849 204 : allocator->allocate((CCC_Allocator_arguments){
850 51 : .input = map->data,
851 : .bytes = 0,
852 51 : .alignment = CCC_max(ALIGNOF_NODE, map->alignof_type),
853 51 : .context = allocator->context,
854 : });
855 51 : map->data = new_data;
856 51 : map->capacity = new_capacity;
857 51 : return CCC_RESULT_OK;
858 63 : }
859 :
860 : static void
861 10404 : insert(struct CCC_Array_adaptive_map *const map, size_t const n) {
862 10404 : init_node(map, n);
863 10404 : if (map->count == INSERT_ROOT_NODE_COUNT) {
864 60 : map->root = n;
865 60 : return;
866 : }
867 10344 : void const *const key = key_at(map, n);
868 10344 : map->root = splay(map, map->root, key);
869 10344 : CCC_Order const root_order = order_nodes(map, key, map->root);
870 10344 : if (CCC_ORDER_EQUAL == root_order) {
871 0 : return;
872 : }
873 10344 : connect_new_root(map, n, root_order);
874 20748 : }
875 :
876 : static void
877 10344 : connect_new_root(
878 : struct CCC_Array_adaptive_map *const map,
879 : size_t const new_root,
880 : CCC_Order const order_result
881 : ) {
882 10344 : enum Branch const dir = CCC_ORDER_GREATER == order_result;
883 10344 : link(map, new_root, dir, branch_index(map, map->root, dir));
884 10344 : link(map, new_root, !dir, map->root);
885 10344 : *branch_pointer(map, map->root, dir) = 0;
886 10344 : map->root = new_root;
887 10344 : *parent_pointer(map, map->root) = 0;
888 10344 : }
889 :
890 : static size_t
891 2322 : erase(struct CCC_Array_adaptive_map *const map, void const *const key) {
892 2322 : if (CCC_array_adaptive_map_is_empty(map)) {
893 1 : return 0;
894 : }
895 2321 : size_t const ret = splay(map, map->root, key);
896 2321 : CCC_Order const found = order_nodes(map, key, ret);
897 2321 : if (found != CCC_ORDER_EQUAL) {
898 2 : return 0;
899 : }
900 2319 : return remove_from_tree(map, ret);
901 2322 : }
902 :
903 : static size_t
904 2319 : remove_from_tree(struct CCC_Array_adaptive_map *const map, size_t const ret) {
905 2319 : if (!branch_index(map, ret, L)) {
906 361 : map->root = branch_index(map, ret, R);
907 361 : *parent_pointer(map, map->root) = 0;
908 361 : } else {
909 1958 : map->root = splay(map, branch_index(map, ret, L), key_at(map, ret));
910 1958 : link(map, map->root, R, branch_index(map, ret, R));
911 : }
912 2319 : node_at(map, ret)->next_free = map->free_list;
913 2319 : map->free_list = ret;
914 2319 : --map->count;
915 2319 : return ret;
916 : }
917 :
918 : static size_t
919 20907 : find(struct CCC_Array_adaptive_map *const map, void const *const key) {
920 20907 : if (!map->root) {
921 77 : return 0;
922 : }
923 20830 : map->root = splay(map, map->root, key);
924 20830 : return order_nodes(map, key, map->root) == CCC_ORDER_EQUAL ? map->root : 0;
925 20907 : }
926 :
927 : /** Adopts D. Sleator technique for splaying. Notable to this method is the
928 : general improvement to the tree that occurs because we always splay the key
929 : to the root, OR the next closest value to the key to the root. This has
930 : interesting performance implications for real data sets.
931 :
932 : This implementation has been modified to unite the left and right symmetries
933 : and manage the parent pointers. Parent pointers are not usual for splay trees
934 : but are necessary for a clean iteration API. */
935 : static size_t
936 35533 : splay(
937 : struct CCC_Array_adaptive_map *const map, size_t root, void const *const key
938 : ) {
939 35533 : assert(root);
940 : /* Splaying brings the key element up to the root. The zigzag fixes of
941 : splaying repair the tree and we remember the roots of these changes in
942 : this helper tree. At the end, make the root pick up these modified left
943 : and right helpers. The nil node should NULL initialized to start. */
944 35533 : struct CCC_Array_adaptive_map_node *const nil = node_at(map, 0);
945 35533 : nil->branch[L] = nil->branch[R] = nil->parent = 0;
946 35533 : size_t left_right_subtrees[LR] = {0, 0};
947 156439 : for (;;) {
948 156439 : CCC_Order const root_order = order_nodes(map, key, root);
949 156439 : enum Branch const order_link = CCC_ORDER_GREATER == root_order;
950 156439 : size_t const child = branch_index(map, root, order_link);
951 156439 : if (CCC_ORDER_EQUAL == root_order || !child) {
952 26872 : break;
953 : }
954 259134 : CCC_Order const child_order
955 129567 : = order_nodes(map, key, branch_index(map, root, order_link));
956 129567 : enum Branch const child_order_link = CCC_ORDER_GREATER == child_order;
957 : /* A straight line has formed from root->child->grandchild. An
958 : opportunity to splay and heal the tree arises. */
959 129567 : if (CCC_ORDER_EQUAL != child_order && order_link == child_order_link) {
960 82722 : link(map, root, order_link, branch_index(map, child, !order_link));
961 82722 : link(map, child, !order_link, root);
962 82722 : root = child;
963 82722 : if (!branch_index(map, root, order_link)) {
964 8661 : break;
965 : }
966 74061 : }
967 120906 : link(map, left_right_subtrees[!order_link], order_link, root);
968 120906 : left_right_subtrees[!order_link] = root;
969 120906 : root = branch_index(map, root, order_link);
970 156439 : }
971 35533 : link(map, left_right_subtrees[L], R, branch_index(map, root, L));
972 35533 : link(map, left_right_subtrees[R], L, branch_index(map, root, R));
973 35533 : link(map, root, L, nil->branch[R]);
974 35533 : link(map, root, R, nil->branch[L]);
975 35533 : map->root = root;
976 35533 : *parent_pointer(map, map->root) = 0;
977 71066 : return root;
978 35533 : }
979 :
980 : /** Links the parent node to node starting at subtree root via direction dir.
981 : updates the parent of the child being picked up by the new parent as well. */
982 : static inline void
983 451128 : link(
984 : struct CCC_Array_adaptive_map *const map,
985 : size_t const parent,
986 : enum Branch const dir,
987 : size_t const subtree
988 : ) {
989 451128 : *branch_pointer(map, parent, dir) = subtree;
990 451128 : *parent_pointer(map, subtree) = parent;
991 451128 : }
992 :
993 : static size_t
994 15 : min_max_from(
995 : struct CCC_Array_adaptive_map const *const map,
996 : size_t start,
997 : enum Branch const dir
998 : ) {
999 15 : if (!start) {
1000 1 : return 0;
1001 : }
1002 114 : for (; branch_index(map, start, dir);
1003 100 : start = branch_index(map, start, dir)) {}
1004 14 : return start;
1005 15 : }
1006 :
1007 : static size_t
1008 4212 : next(
1009 : struct CCC_Array_adaptive_map const *const map,
1010 : size_t n,
1011 : enum Branch const traversal
1012 : ) {
1013 4212 : if (!n) {
1014 0 : return 0;
1015 : }
1016 4212 : assert(!parent_index(map, map->root));
1017 4212 : if (branch_index(map, n, traversal)) {
1018 4441 : for (n = branch_index(map, n, traversal);
1019 4441 : branch_index(map, n, !traversal);
1020 2363 : n = branch_index(map, n, !traversal)) {}
1021 2078 : return n;
1022 : }
1023 2134 : size_t p = parent_index(map, n);
1024 3827 : for (; p && branch_index(map, p, !traversal) != n;
1025 1693 : n = p, p = parent_index(map, p)) {}
1026 2134 : return p;
1027 4212 : }
1028 :
1029 : /** Deletes all nodes in the tree by calling destructor function on them in
1030 : linear time and constant space. This function modifies nodes as it deletes the
1031 : tree elements. Assumes the destructor function is non-null.
1032 :
1033 : This function does not update any count or capacity fields of the map, it
1034 : simply calls the destructor on each node and removes the nodes references to
1035 : other tree elements. */
1036 : static void
1037 2 : delete_nodes(
1038 : struct CCC_Array_adaptive_map const *const map,
1039 : CCC_Destructor const *const destructor
1040 : ) {
1041 2 : size_t node = map->root;
1042 31 : while (node) {
1043 29 : struct CCC_Array_adaptive_map_node *const e = node_at(map, node);
1044 29 : if (e->branch[L]) {
1045 14 : size_t const left = e->branch[L];
1046 14 : e->branch[L] = node_at(map, left)->branch[R];
1047 14 : node_at(map, left)->branch[R] = node;
1048 14 : node = left;
1049 : continue;
1050 14 : }
1051 15 : size_t const next = e->branch[R];
1052 15 : e->branch[L] = e->branch[R] = 0;
1053 15 : e->parent = 0;
1054 45 : destructor->destroy((CCC_Arguments){
1055 15 : .type = data_at(map, node),
1056 15 : .context = destructor->context,
1057 : });
1058 15 : node = next;
1059 29 : }
1060 2 : }
1061 :
1062 : static inline CCC_Order
1063 6744691 : order_nodes(
1064 : struct CCC_Array_adaptive_map const *const map,
1065 : void const *const key,
1066 : size_t const node
1067 : ) {
1068 26978764 : return map->comparator.compare((CCC_Key_comparator_arguments){
1069 6744691 : .key_left = key,
1070 6744691 : .type_right = data_at(map, node),
1071 6744691 : .context = map->comparator.context,
1072 : });
1073 : }
1074 :
1075 : static inline void
1076 10404 : init_node(struct CCC_Array_adaptive_map const *const map, size_t const node) {
1077 10404 : struct CCC_Array_adaptive_map_node *const e = node_at(map, node);
1078 10404 : e->branch[L] = e->branch[R] = e->parent = 0;
1079 10404 : }
1080 :
1081 : /** Calculates the number of bytes needed for user data INCLUDING any bytes we
1082 : need to add to the end of the array such that the following nodes array starts
1083 : on an aligned byte boundary given the alignment requirements of a node. This
1084 : means the value returned from this function may or may not be slightly larger
1085 : then the raw size of just user elements if rounding up must occur. */
1086 : static inline size_t
1087 205 : data_bytes(size_t const sizeof_type, size_t const capacity) {
1088 205 : return CCC_roundup(sizeof_type * capacity, ALIGNOF_NODE);
1089 : }
1090 :
1091 : /** Calculates the number of bytes needed for the nodes array without any
1092 : consideration for end padding as no arrays follow. */
1093 : static inline size_t
1094 36 : nodes_bytes(size_t const capacity) {
1095 36 : return SIZEOF_NODE * capacity;
1096 : }
1097 :
1098 : /** Calculates the number of bytes needed for all arrays in the Struct of Arrays
1099 : map design INCLUDING any extra padding bytes that need to be added between the
1100 : data and node arrays and the node and parity arrays. Padding might be needed if
1101 : the alignment of the type in next array that follows a preceding array is
1102 : different from the preceding array. In that case it is the preceding array's
1103 : responsibility to add padding bytes to its end such that the next array begins
1104 : on an aligned byte boundary for its own type. This means that the bytes returned
1105 : by this function may be greater than summing the (sizeof(type) * capacity) for
1106 : each array in the conceptual struct.
1107 :
1108 : This functions checks for overflow at every step of calculating the size of
1109 : this contiguous allocation and returns CCC_TRUE if overflow occured, otherwise
1110 : CCC_FALSE. This function should be used when capacity is accepted from an
1111 : external source such as user input. */
1112 : static inline CCC_Tribool
1113 54 : checked_total_bytes(
1114 : size_t *const result, size_t const sizeof_type, size_t const capacity
1115 : ) {
1116 54 : size_t node_byte_count = 0;
1117 54 : if (ckd_mul(&node_byte_count, capacity, (size_t)SIZEOF_NODE)) {
1118 0 : return CCC_TRUE;
1119 : }
1120 54 : *result = 0;
1121 54 : if (ckd_mul(result, sizeof_type, capacity)) {
1122 0 : return CCC_TRUE;
1123 : }
1124 54 : if (CCC_checked_roundup(result, *result, ALIGNOF_NODE)) {
1125 0 : return CCC_TRUE;
1126 : }
1127 54 : if (ckd_add(result, *result, node_byte_count)) {
1128 0 : return CCC_TRUE;
1129 : }
1130 54 : return CCC_FALSE;
1131 54 : }
1132 :
1133 : /** Returns the base of the node array relative to the data base pointer. This
1134 : positions is guaranteed to be the first aligned byte given the alignment of the
1135 : node type after the data array. The data array has added any necessary padding
1136 : after it to ensure that the base of the node array is aligned for its type. */
1137 : static inline struct CCC_Array_adaptive_map_node *
1138 169 : nodes_base_address(
1139 : size_t const sizeof_type, void const *const data, size_t const capacity
1140 : ) {
1141 338 : return (struct CCC_Array_adaptive_map_node *)((char *)data
1142 169 : + data_bytes(
1143 169 : sizeof_type, capacity
1144 : ));
1145 : }
1146 :
1147 : /** Copies over the Struct of Arrays contained within the one contiguous
1148 : allocation of the map to the new memory provided. Assumes the new_data pointer
1149 : points to the base of an allocation that has been allocated with sufficient
1150 : bytes to support the user data, nodes, and parity arrays for the provided new
1151 : capacity. */
1152 : static inline void
1153 53 : resize_struct_of_arrays(
1154 : struct CCC_Array_adaptive_map const *const source,
1155 : void *const destination_data_base,
1156 : size_t const destination_capacity
1157 : ) {
1158 53 : if (!source->data) {
1159 17 : return;
1160 : }
1161 36 : assert(destination_capacity >= source->capacity);
1162 36 : size_t const sizeof_type = source->sizeof_type;
1163 : /* Each section of the allocation "grows" when we re-size so one copy would
1164 : not work. Instead each component is copied over allowing each to grow. */
1165 36 : (void)memcpy(
1166 36 : destination_data_base,
1167 36 : source->data,
1168 36 : data_bytes(sizeof_type, source->capacity)
1169 : );
1170 36 : (void)memcpy(
1171 36 : nodes_base_address(
1172 36 : sizeof_type, destination_data_base, destination_capacity
1173 : ),
1174 36 : nodes_base_address(sizeof_type, source->data, source->capacity),
1175 36 : nodes_bytes(source->capacity)
1176 : );
1177 89 : }
1178 :
1179 : static inline void
1180 107 : swap(void *const temp, size_t const sizeof_type, void *const a, void *const b) {
1181 107 : if (a == b) {
1182 0 : return;
1183 : }
1184 107 : (void)memcpy(temp, a, sizeof_type);
1185 107 : (void)memcpy(a, b, sizeof_type);
1186 107 : (void)memcpy(b, temp, sizeof_type);
1187 214 : }
1188 :
1189 : static inline struct CCC_Array_adaptive_map_node *
1190 30461595 : node_at(struct CCC_Array_adaptive_map const *const map, size_t const i) {
1191 30461595 : return &map->nodes[i];
1192 : }
1193 :
1194 : static inline void *
1195 13217420 : data_at(struct CCC_Array_adaptive_map const *const map, size_t const i) {
1196 13217420 : return (char *)map->data + (i * map->sizeof_type);
1197 : }
1198 :
1199 : static inline size_t
1200 21520597 : branch_index(
1201 : struct CCC_Array_adaptive_map const *const map,
1202 : size_t const parent,
1203 : enum Branch const dir
1204 : ) {
1205 21520597 : return node_at(map, parent)->branch[dir];
1206 : }
1207 :
1208 : static inline size_t
1209 3481892 : parent_index(
1210 : struct CCC_Array_adaptive_map const *const map, size_t const child
1211 : ) {
1212 3481892 : return node_at(map, child)->parent;
1213 : }
1214 :
1215 : static inline size_t *
1216 461472 : branch_pointer(
1217 : struct CCC_Array_adaptive_map const *const map,
1218 : size_t const node,
1219 : enum Branch const branch
1220 : ) {
1221 461472 : return &node_at(map, node)->branch[branch];
1222 : }
1223 :
1224 : static inline size_t *
1225 497366 : parent_pointer(
1226 : struct CCC_Array_adaptive_map const *const map, size_t const node
1227 : ) {
1228 497366 : return &node_at(map, node)->parent;
1229 : }
1230 :
1231 : static inline void *
1232 6437492 : key_at(struct CCC_Array_adaptive_map const *const map, size_t const i) {
1233 6437492 : return (char *)data_at(map, i) + map->key_offset;
1234 : }
1235 :
1236 : static void *
1237 8080 : key_in_slot(
1238 : struct CCC_Array_adaptive_map const *map, void const *const user_struct
1239 : ) {
1240 8080 : return (char *)user_struct + map->key_offset;
1241 : }
1242 :
1243 : /*=========================== Validation ===============================*/
1244 :
1245 : /* NOLINTBEGIN(*misc-no-recursion) */
1246 :
1247 : /** @internal */
1248 : struct Tree_range {
1249 : size_t low;
1250 : size_t root;
1251 : size_t high;
1252 : };
1253 :
1254 : static size_t
1255 6957561 : recursive_count(
1256 : struct CCC_Array_adaptive_map const *const map, size_t const r
1257 : ) {
1258 6957561 : if (!r) {
1259 3483708 : return 0;
1260 : }
1261 6947706 : return 1 + recursive_count(map, branch_index(map, r, R))
1262 3473853 : + recursive_count(map, branch_index(map, r, L));
1263 6957561 : }
1264 :
1265 : static CCC_Tribool
1266 6957561 : are_subtrees_valid(
1267 : struct CCC_Array_adaptive_map const *map, struct Tree_range const r
1268 : ) {
1269 6957561 : if (!r.root) {
1270 3483708 : return CCC_TRUE;
1271 : }
1272 3473853 : if (r.low
1273 3473853 : && order_nodes(map, key_at(map, r.low), r.root) != CCC_ORDER_LESSER) {
1274 0 : return CCC_FALSE;
1275 : }
1276 3473853 : if (r.high
1277 3473853 : && order_nodes(map, key_at(map, r.high), r.root) != CCC_ORDER_GREATER) {
1278 0 : return CCC_FALSE;
1279 : }
1280 6947706 : return are_subtrees_valid(
1281 3473853 : map,
1282 13895412 : (struct Tree_range){
1283 3473853 : .low = r.low,
1284 3473853 : .root = branch_index(map, r.root, L),
1285 3473853 : .high = r.root,
1286 : }
1287 : )
1288 3473853 : && are_subtrees_valid(
1289 3473853 : map,
1290 13895412 : (struct Tree_range){
1291 3473853 : .low = r.root,
1292 3473853 : .root = branch_index(map, r.root, R),
1293 3473853 : .high = r.high,
1294 : }
1295 : );
1296 6957561 : }
1297 :
1298 : static CCC_Tribool
1299 6957561 : is_storing_parent(
1300 : struct CCC_Array_adaptive_map const *const map,
1301 : size_t const p,
1302 : size_t const root
1303 : ) {
1304 6957561 : if (!root) {
1305 3483708 : return CCC_TRUE;
1306 : }
1307 3473853 : if (parent_index(map, root) != p) {
1308 0 : return CCC_FALSE;
1309 : }
1310 6947706 : return is_storing_parent(map, root, branch_index(map, root, L))
1311 3473853 : && is_storing_parent(map, root, branch_index(map, root, R));
1312 6957561 : }
1313 :
1314 : static CCC_Tribool
1315 9855 : is_free_list_valid(struct CCC_Array_adaptive_map const *const map) {
1316 9855 : if (!map->count) {
1317 0 : return CCC_TRUE;
1318 : }
1319 9855 : size_t cur_free_index = map->free_list;
1320 9855 : size_t list_count = 0;
1321 4433075 : while (cur_free_index && list_count < map->capacity) {
1322 4423220 : cur_free_index = node_at(map, cur_free_index)->next_free;
1323 4423220 : ++list_count;
1324 : }
1325 9855 : if (cur_free_index) {
1326 0 : return CCC_FALSE;
1327 : }
1328 9855 : if (list_count + map->count != map->capacity) {
1329 0 : return CCC_FALSE;
1330 : }
1331 9855 : return CCC_TRUE;
1332 9855 : }
1333 :
1334 : static CCC_Tribool
1335 9865 : validate(struct CCC_Array_adaptive_map const *const map) {
1336 9865 : if (!map->count) {
1337 10 : return CCC_TRUE;
1338 : }
1339 9855 : if (!are_subtrees_valid(map, (struct Tree_range){.root = map->root})) {
1340 0 : return CCC_FALSE;
1341 : }
1342 9855 : size_t const size = recursive_count(map, map->root);
1343 9855 : if (size && size != map->count - 1) {
1344 0 : return CCC_FALSE;
1345 : }
1346 9855 : if (!is_storing_parent(map, 0, map->root)) {
1347 0 : return CCC_FALSE;
1348 : }
1349 9855 : if (!is_free_list_valid(map)) {
1350 0 : return CCC_FALSE;
1351 : }
1352 9855 : return CCC_TRUE;
1353 9865 : }
1354 :
1355 : /* NOLINTEND(*misc-no-recursion) */
|
