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