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