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 : /* Citation:
15 : [1] See the sort methods for citations and change lists regarding the pintOS
16 : educational operating system natural merge sort algorithm used for linked lists.
17 : Code in the pintOS source is at `src/lib/kernel.list.c`, but this may change
18 : if they refactor. */
19 : /** C23 provided headers. */
20 : #include <stddef.h>
21 :
22 : /** CCC provided headers. */
23 : #include "ccc/configuration.h" /* IWYU pragma: keep */
24 : #include "ccc/private/private_singly_linked_list.h"
25 : #include "ccc/singly_linked_list.h"
26 : #include "ccc/sort.h"
27 : #include "ccc/types.h"
28 :
29 : /** @brief When sorting, a singly linked list is at a disadvantage for iterative
30 : O(1) space merge sort: it doesn't have a prev pointer. This will help list
31 : elements remember their previous element for splicing and merging. */
32 : struct Link {
33 : /** The previous element of cur. Must manually update and manage. */
34 : struct CCC_Singly_linked_list_node *previous;
35 : /** The current element. Must manually manage and update. */
36 : struct CCC_Singly_linked_list_node *current;
37 : };
38 :
39 : /*=========================== Prototypes =============================*/
40 :
41 : static void *struct_base(
42 : struct CCC_Singly_linked_list const *,
43 : struct CCC_Singly_linked_list_node const *
44 : );
45 : static void remove_node(
46 : struct CCC_Singly_linked_list *,
47 : struct CCC_Singly_linked_list_node *,
48 : struct CCC_Singly_linked_list_node *
49 : );
50 : static void insert_node(
51 : struct CCC_Singly_linked_list *,
52 : struct CCC_Singly_linked_list_node *,
53 : struct CCC_Singly_linked_list_node *
54 : );
55 : static struct CCC_Singly_linked_list_node *before(
56 : struct CCC_Singly_linked_list const *,
57 : struct CCC_Singly_linked_list_node const *
58 : );
59 : static size_t
60 : len(struct CCC_Singly_linked_list_node const *,
61 : struct CCC_Singly_linked_list_node const *);
62 : static void erase_range(
63 : struct CCC_Singly_linked_list const *,
64 : struct CCC_Singly_linked_list_node const *,
65 : struct CCC_Singly_linked_list_node *,
66 : CCC_Allocator const *
67 : );
68 : static struct CCC_Singly_linked_list_node *
69 : elem_in(struct CCC_Singly_linked_list const *, void const *);
70 : static struct Link merge(
71 : CCC_Singly_linked_list *,
72 : struct Link,
73 : struct Link,
74 : struct Link,
75 : CCC_Order,
76 : CCC_Comparator const *
77 : );
78 : static struct Link first_out_of_order(
79 : CCC_Singly_linked_list const *,
80 : struct Link,
81 : CCC_Order,
82 : CCC_Comparator const *
83 : );
84 : static CCC_Order get_order(
85 : struct CCC_Singly_linked_list const *,
86 : struct CCC_Singly_linked_list_node const *,
87 : struct CCC_Singly_linked_list_node const *,
88 : CCC_Comparator const *
89 : );
90 :
91 : /*=========================== Interface =============================*/
92 :
93 : void *
94 54 : CCC_singly_linked_list_push_front(
95 : CCC_Singly_linked_list *const list,
96 : CCC_Singly_linked_list_node *type_intruder,
97 : CCC_Allocator const *const allocator
98 : ) {
99 54 : if (!list || !type_intruder || !allocator) {
100 3 : return NULL;
101 : }
102 51 : if (allocator->allocate) {
103 28 : void *const node = allocator->allocate((CCC_Allocator_arguments){
104 : .input = NULL,
105 7 : .bytes = list->sizeof_type,
106 7 : .alignment = list->alignof_type,
107 7 : .context = allocator->context,
108 : });
109 7 : if (!node) {
110 1 : return NULL;
111 : }
112 6 : (void)memcpy(node, struct_base(list, type_intruder), list->sizeof_type);
113 6 : type_intruder = elem_in(list, node);
114 7 : }
115 50 : insert_node(list, NULL, type_intruder);
116 50 : return struct_base(list, list->head);
117 54 : }
118 :
119 : void *
120 5 : CCC_singly_linked_list_front(CCC_Singly_linked_list const *const list) {
121 5 : if (!list || list->head == NULL) {
122 1 : return NULL;
123 : }
124 4 : return struct_base(list, list->head);
125 5 : }
126 :
127 : CCC_Result
128 4 : CCC_singly_linked_list_pop_front(
129 : CCC_Singly_linked_list *const list, CCC_Allocator const *const allocator
130 : ) {
131 4 : if (!list || !list->head || !allocator) {
132 1 : return CCC_RESULT_ARGUMENT_ERROR;
133 : }
134 3 : struct CCC_Singly_linked_list_node *const remove = list->head;
135 3 : remove_node(list, NULL, list->head);
136 3 : if (allocator->allocate) {
137 12 : (void)allocator->allocate((CCC_Allocator_arguments){
138 3 : .input = struct_base(list, remove),
139 : .bytes = 0,
140 3 : .alignment = list->alignof_type,
141 3 : .context = allocator->context,
142 : });
143 3 : }
144 3 : return CCC_RESULT_OK;
145 4 : }
146 :
147 : CCC_Result
148 11 : CCC_singly_linked_list_splice(
149 : CCC_Singly_linked_list *const position_list,
150 : CCC_Singly_linked_list_node *const type_intruder_position,
151 : CCC_Singly_linked_list *const splice_list,
152 : CCC_Singly_linked_list_node *const type_intruder_splice
153 : ) {
154 11 : if (!position_list || !type_intruder_splice || !splice_list) {
155 3 : return CCC_RESULT_ARGUMENT_ERROR;
156 : }
157 8 : if ((position_list == splice_list)
158 13 : && (type_intruder_splice == type_intruder_position
159 7 : || (type_intruder_position
160 6 : && type_intruder_position->next == type_intruder_splice))) {
161 2 : return CCC_RESULT_OK;
162 : }
163 6 : remove_node(
164 6 : splice_list,
165 6 : before(splice_list, type_intruder_splice),
166 6 : type_intruder_splice
167 : );
168 6 : insert_node(position_list, type_intruder_position, type_intruder_splice);
169 6 : return CCC_RESULT_OK;
170 11 : }
171 :
172 : CCC_Result
173 12 : CCC_singly_linked_list_splice_range(
174 : CCC_Singly_linked_list *const position_list,
175 : CCC_Singly_linked_list_node *const type_intruder_position,
176 : CCC_Singly_linked_list *const to_cut_list,
177 : CCC_Singly_linked_list_node *const type_intruder_to_cut_begin,
178 : CCC_Singly_linked_list_node *const type_intruder_to_cut_exclusive_end
179 : ) {
180 12 : if (!position_list || !type_intruder_to_cut_begin || !to_cut_list) {
181 3 : return CCC_RESULT_ARGUMENT_ERROR;
182 : }
183 9 : if (type_intruder_position == type_intruder_to_cut_begin) {
184 1 : return CCC_RESULT_OK;
185 : }
186 16 : CCC_Singly_linked_list_node *const to_cut_inclusive_end
187 8 : = before(to_cut_list, type_intruder_to_cut_exclusive_end);
188 8 : if (type_intruder_to_cut_begin == to_cut_inclusive_end) {
189 1 : return CCC_singly_linked_list_splice(
190 1 : position_list,
191 1 : type_intruder_position,
192 1 : to_cut_list,
193 1 : type_intruder_to_cut_begin
194 : );
195 : }
196 7 : remove_node(
197 7 : to_cut_list,
198 7 : before(to_cut_list, type_intruder_to_cut_begin),
199 7 : to_cut_inclusive_end
200 : );
201 7 : if (type_intruder_position) {
202 5 : if (to_cut_inclusive_end) {
203 5 : to_cut_inclusive_end->next = type_intruder_position->next;
204 5 : }
205 5 : type_intruder_position->next = type_intruder_to_cut_begin;
206 5 : } else {
207 2 : if (to_cut_inclusive_end) {
208 2 : to_cut_inclusive_end->next = position_list->head;
209 2 : }
210 2 : position_list->head = type_intruder_to_cut_begin;
211 : }
212 7 : return CCC_RESULT_OK;
213 12 : }
214 :
215 : void *
216 4 : CCC_singly_linked_list_erase(
217 : CCC_Singly_linked_list *const list,
218 : CCC_Singly_linked_list_node *const type_intruder,
219 : CCC_Allocator const *const allocator
220 : ) {
221 4 : if (!list || !type_intruder || !allocator || !list->head
222 1 : || type_intruder == NULL) {
223 3 : return NULL;
224 : }
225 2 : struct CCC_Singly_linked_list_node const *const return_this
226 1 : = type_intruder->next;
227 1 : remove_node(list, before(list, type_intruder), type_intruder);
228 1 : type_intruder->next = NULL;
229 1 : if (allocator->allocate) {
230 4 : (void)allocator->allocate((CCC_Allocator_arguments){
231 1 : .input = struct_base(list, type_intruder),
232 : .bytes = 0,
233 1 : .alignment = list->alignof_type,
234 1 : .context = allocator->context,
235 : });
236 1 : }
237 1 : return struct_base(list, return_this);
238 4 : }
239 :
240 : void *
241 7 : CCC_singly_linked_list_erase_range(
242 : CCC_Singly_linked_list *const list,
243 : CCC_Singly_linked_list_node *const type_intruder_begin,
244 : CCC_Singly_linked_list_node *const type_intruder_end,
245 : CCC_Allocator const *const allocator
246 : ) {
247 7 : if (!list || !type_intruder_begin || !allocator || !list->head) {
248 3 : return NULL;
249 : }
250 8 : struct CCC_Singly_linked_list_node *const inclusive_end
251 4 : = before(list, type_intruder_end);
252 8 : struct CCC_Singly_linked_list_node *const before_begin
253 4 : = before(list, type_intruder_begin);
254 4 : remove_node(list, before_begin, inclusive_end);
255 4 : erase_range(list, type_intruder_begin, inclusive_end, allocator);
256 4 : return struct_base(list, type_intruder_end);
257 7 : }
258 :
259 : void *
260 4 : CCC_singly_linked_list_extract(
261 : CCC_Singly_linked_list *const list,
262 : CCC_Singly_linked_list_node *const type_intruder
263 : ) {
264 4 : if (!list || !type_intruder || !list->head) {
265 2 : return NULL;
266 : }
267 4 : struct CCC_Singly_linked_list_node const *const return_this
268 2 : = type_intruder->next;
269 2 : remove_node(list, before(list, type_intruder), type_intruder);
270 2 : type_intruder->next = NULL;
271 2 : return struct_base(list, return_this);
272 4 : }
273 :
274 : void *
275 7 : CCC_singly_linked_list_extract_range(
276 : CCC_Singly_linked_list *const list,
277 : CCC_Singly_linked_list_node *const type_intruder_begin,
278 : CCC_Singly_linked_list_node *const type_intruder_end
279 : ) {
280 7 : if (!list || !type_intruder_begin || !list->head) {
281 2 : return NULL;
282 : }
283 10 : struct CCC_Singly_linked_list_node *const inclusive_end
284 5 : = before(list, type_intruder_end);
285 10 : struct CCC_Singly_linked_list_node *const before_begin
286 5 : = before(list, type_intruder_begin);
287 5 : remove_node(list, before_begin, inclusive_end);
288 5 : if (inclusive_end) {
289 5 : inclusive_end->next = NULL;
290 5 : }
291 5 : return struct_base(list, type_intruder_end);
292 7 : }
293 :
294 : void *
295 52 : CCC_singly_linked_list_begin(CCC_Singly_linked_list const *const list) {
296 52 : if (!list) {
297 1 : return NULL;
298 : }
299 51 : return struct_base(list, list->head);
300 52 : }
301 :
302 : CCC_Singly_linked_list_node *
303 11 : CCC_singly_linked_list_node_begin(CCC_Singly_linked_list const *const list) {
304 11 : if (!list) {
305 1 : return NULL;
306 : }
307 10 : return list->head;
308 11 : }
309 :
310 : CCC_Singly_linked_list_node *
311 2 : CCC_singly_linked_list_node_before_begin(CCC_Singly_linked_list const *const) {
312 2 : return NULL;
313 : }
314 :
315 : void *
316 343 : CCC_singly_linked_list_end(CCC_Singly_linked_list const *const) {
317 343 : return NULL;
318 : }
319 :
320 : void *
321 299 : CCC_singly_linked_list_next(
322 : CCC_Singly_linked_list const *const list,
323 : CCC_Singly_linked_list_node const *const type_intruder
324 : ) {
325 299 : if (!list || !type_intruder) {
326 2 : return NULL;
327 : }
328 297 : return struct_base(list, type_intruder->next);
329 299 : }
330 :
331 : CCC_Result
332 6 : CCC_singly_linked_list_clear(
333 : CCC_Singly_linked_list *const list,
334 : CCC_Destructor const *const destructor,
335 : CCC_Allocator const *const allocator
336 : ) {
337 6 : if (!list || !destructor || !allocator) {
338 3 : return CCC_RESULT_ARGUMENT_ERROR;
339 : }
340 3 : if (!destructor->destroy && !allocator->allocate) {
341 1 : list->head = NULL;
342 1 : return CCC_RESULT_OK;
343 : }
344 13 : while (list->head) {
345 11 : struct CCC_Singly_linked_list_node *const remove = list->head;
346 11 : remove_node(list, NULL, remove);
347 11 : void *const data = struct_base(list, remove);
348 11 : if (destructor->destroy) {
349 24 : destructor->destroy((CCC_Arguments){
350 8 : .type = data,
351 8 : .context = destructor->context,
352 : });
353 8 : }
354 11 : if (allocator->allocate) {
355 44 : (void)allocator->allocate((CCC_Allocator_arguments){
356 11 : .input = data,
357 : .bytes = 0,
358 11 : .alignment = list->alignof_type,
359 11 : .context = allocator->context,
360 : });
361 11 : }
362 11 : }
363 2 : list->head = NULL;
364 2 : return CCC_RESULT_OK;
365 6 : }
366 :
367 : CCC_Tribool
368 53 : CCC_singly_linked_list_validate(CCC_Singly_linked_list const *const list) {
369 53 : if (!list) {
370 0 : return CCC_TRIBOOL_ERROR;
371 : }
372 334 : for (struct CCC_Singly_linked_list_node *e = list->head; e != NULL;
373 281 : e = e->next) {
374 281 : if (!e || e->next == e) {
375 0 : return CCC_FALSE;
376 : }
377 281 : }
378 53 : return CCC_TRUE;
379 53 : }
380 :
381 : CCC_Count
382 17 : CCC_singly_linked_list_count(CCC_Singly_linked_list const *const list) {
383 :
384 17 : if (!list) {
385 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
386 : }
387 32 : return (CCC_Count){
388 16 : .count = len(list->head, NULL),
389 : };
390 17 : }
391 :
392 : CCC_Tribool
393 10 : CCC_singly_linked_list_is_empty(CCC_Singly_linked_list const *const list) {
394 10 : if (!list) {
395 1 : return CCC_TRIBOOL_ERROR;
396 : }
397 9 : return !list->head;
398 10 : }
399 :
400 : /*========================== Sorting ================================*/
401 :
402 : CCC_Tribool
403 20 : CCC_singly_linked_list_is_sorted(
404 : CCC_Singly_linked_list const *const list,
405 : CCC_Order const order,
406 : CCC_Comparator const *const comparator
407 : ) {
408 20 : if (!list || !comparator || !comparator->compare
409 18 : || (order != CCC_ORDER_GREATER && order != CCC_ORDER_LESSER)) {
410 3 : return CCC_TRIBOOL_ERROR;
411 : }
412 17 : if (!list->head) {
413 1 : return CCC_TRUE;
414 : }
415 32 : CCC_Order const wrong_order
416 16 : = order == CCC_ORDER_LESSER ? CCC_ORDER_GREATER : CCC_ORDER_LESSER;
417 100 : for (struct CCC_Singly_linked_list_node const *previous = list->head,
418 16 : *current = list->head->next;
419 75 : current != NULL;
420 59 : previous = current, current = current->next) {
421 68 : if (get_order(list, previous, current, comparator) == wrong_order) {
422 9 : return CCC_FALSE;
423 : }
424 59 : }
425 7 : return CCC_TRUE;
426 20 : }
427 :
428 : /** Inserts an element in sorted order. The element will go to the end of a
429 : section of duplicate values which is good for round-robin style list use. */
430 : void *
431 12 : CCC_singly_linked_list_insert_sorted(
432 : CCC_Singly_linked_list *list,
433 : CCC_Singly_linked_list_node *type_intruder,
434 : CCC_Order const order,
435 : CCC_Comparator const *const comparator,
436 : CCC_Allocator const *const allocator
437 : ) {
438 12 : if (!list || !type_intruder || !allocator || !comparator
439 9 : || !comparator->compare) {
440 4 : return NULL;
441 : }
442 8 : if (allocator->allocate) {
443 12 : void *const node = allocator->allocate((CCC_Allocator_arguments){
444 : .input = NULL,
445 3 : .bytes = list->sizeof_type,
446 3 : .alignment = list->alignof_type,
447 3 : .context = allocator->context,
448 : });
449 3 : if (!node) {
450 2 : return NULL;
451 : }
452 1 : (void)memcpy(node, struct_base(list, type_intruder), list->sizeof_type);
453 1 : type_intruder = elem_in(list, node);
454 3 : }
455 6 : struct CCC_Singly_linked_list_node *prev = NULL;
456 88 : for (struct CCC_Singly_linked_list_node *i = list->head;
457 44 : i != NULL && get_order(list, type_intruder, i, comparator) != order;
458 38 : prev = i, i = i->next) {}
459 6 : insert_node(list, prev, type_intruder);
460 6 : return struct_base(list, type_intruder);
461 12 : }
462 :
463 : /** Sorts the list in `O(N * log(N))` time with `O(1)` space (no recursion). If
464 : the list is already sorted this algorithm only needs one pass. This sort is
465 : stable.
466 :
467 : The following merging algorithm and associated helper functions are based on
468 : the iterative natural merge sort used in the list module of the pintOS project
469 : for learning operating systems. Currently the original is located at the
470 : following path in the pintOS source code:
471 :
472 : `src/lib/kernel/list.c`
473 :
474 : However, if refactors change this location, seek the list intrusive container
475 : module for original implementations. The code has been changed for the C
476 : Container Collection as follows:
477 :
478 : - the algorithm is adapted to work with a singly linked list rather than doubly
479 : - there is no sentinel, only NULL pointer.
480 : - splicing in the merge operation has been simplified along with other tweaks.
481 : - comparison callbacks are handled with three way comparison.
482 :
483 : If the runtime is not obvious from the code, consider that this algorithm runs
484 : bottom up on sorted sub-ranges. It roughly "halves" the remaining sub-ranges
485 : that need to be sorted by roughly "doubling" the length of a sorted range on
486 : each merge step. Therefore the number of times we must perform the merge step is
487 : `O(log(N))`. The most elements we would have to merge in the merge step is all
488 : `N` elements so together that gives us the runtime of `O(N * log(N))`. */
489 : CCC_Result
490 10 : CCC_sort_singly_linked_list_mergesort(
491 : CCC_Singly_linked_list *const list,
492 : CCC_Order const order,
493 : CCC_Comparator const *const comparator
494 : ) {
495 10 : if (!list || !comparator || !comparator->compare
496 8 : || (order != CCC_ORDER_LESSER && order != CCC_ORDER_GREATER)) {
497 3 : return CCC_RESULT_ARGUMENT_ERROR;
498 : }
499 : /* Algorithm is one pass if list is sorted. Merging is never true. */
500 7 : CCC_Tribool merging = CCC_FALSE;
501 7 : do {
502 30 : merging = CCC_FALSE;
503 : /* 0th index of the A list. The start of one list to merge. */
504 30 : struct Link left_start = {.previous = NULL, .current = list->head};
505 72 : while (left_start.current != NULL) {
506 : /* The Nth index of list A (its size) aka 0th index of B list. */
507 60 : struct Link left_end_right_start
508 60 : = first_out_of_order(list, left_start, order, comparator);
509 60 : if (left_end_right_start.current == NULL) {
510 18 : break;
511 : }
512 : /* A picks up the exclusive end of this merge, B, in order
513 : to progress the sorting algorithm with the next run that needs
514 : fixing. Merge returns the final B element to indicate it is the
515 : final sentinel that has not yet been examined. */
516 84 : left_start = merge(
517 42 : list,
518 : left_start,
519 : left_end_right_start,
520 42 : first_out_of_order(
521 42 : list, left_end_right_start, order, comparator
522 : ),
523 42 : order,
524 42 : comparator
525 : );
526 42 : merging = CCC_TRUE;
527 60 : }
528 30 : } while (merging);
529 7 : return CCC_RESULT_OK;
530 10 : }
531 :
532 : /** Merges lists `[left, right)` with `[right, right_end)`
533 : to form `[left, right_end)`. Returns the exclusive end of the range,
534 : `right_end`, once the merge sort is complete.
535 :
536 : Notice that all ranges treat the end of their range as an exclusive sentinel for
537 : consistency. This function assumes the provided lists are already sorted
538 : separately. A list link must be returned because the `right_end` previous field
539 : may be updated due to arbitrary splices during comparison sorting. */
540 : static inline struct Link
541 42 : merge(
542 : CCC_Singly_linked_list *const list,
543 : struct Link left,
544 : struct Link right,
545 : struct Link right_end,
546 : CCC_Order const order,
547 : CCC_Comparator const *const comparator
548 : ) {
549 326 : while (left.current && left.current != right.current && right.current
550 165 : && right.current != right_end.current) {
551 131 : if (get_order(list, right.current, left.current, comparator) == order) {
552 : /* The current element is the lesser element that must be spliced
553 : out. However, right.previous is not updated because only current
554 : is spliced out. Algorithm will continue with new current, but
555 : same previous. */
556 77 : struct CCC_Singly_linked_list_node *const to_merge = right.current;
557 77 : right.current = to_merge->next;
558 0 : assert(
559 77 : right.previous
560 77 : && "merged element must always have a previous pointer because "
561 : "lists of size 1 or less are not merged and merging "
562 : "iterates forward"
563 : );
564 77 : right.previous->next = to_merge->next;
565 : /* This is so we return an accurate right_end link at the end. */
566 77 : if (to_merge == right_end.previous) {
567 34 : right_end.previous = right.previous;
568 34 : }
569 77 : if (left.previous) {
570 56 : left.previous->next = to_merge;
571 56 : } else {
572 21 : list->head = to_merge;
573 : }
574 77 : to_merge->next = left.current;
575 : /* Another critical update reflected in our links, not the list. */
576 77 : left.previous = to_merge;
577 77 : } else {
578 54 : left.previous = left.current;
579 54 : left.current = left.current->next;
580 : }
581 : }
582 42 : return right_end;
583 42 : }
584 :
585 : /** Returns a pair of elements marking the first list elem that is smaller than
586 : its previous `CCC_ORDER_LESSER` according to the user comparison callback. The
587 : list_link returned will have the out of order element as cur and the last
588 : remaining in order element as prev. The cur element may be the sentinel if the
589 : run is sorted. */
590 : static inline struct Link
591 102 : first_out_of_order(
592 : CCC_Singly_linked_list const *const list,
593 : struct Link link,
594 : CCC_Order const order,
595 : CCC_Comparator const *const comparator
596 : ) {
597 102 : do {
598 284 : link.previous = link.current;
599 284 : link.current = link.current->next;
600 386 : } while (link.current != NULL
601 284 : && get_order(list, link.current, link.previous, comparator)
602 254 : != order);
603 102 : return link;
604 102 : }
605 :
606 : /*========================= Private Interface ==========================*/
607 :
608 : void
609 96 : CCC_private_singly_linked_list_push_front(
610 : struct CCC_Singly_linked_list *const list,
611 : struct CCC_Singly_linked_list_node *const type_intruder
612 : ) {
613 96 : insert_node(list, NULL, type_intruder);
614 96 : }
615 :
616 : struct CCC_Singly_linked_list_node *
617 96 : CCC_private_singly_linked_list_node_in(
618 : struct CCC_Singly_linked_list const *const list,
619 : void const *const user_struct
620 : ) {
621 96 : return elem_in(list, user_struct);
622 : }
623 :
624 : /*=========================== Static Helpers =============================*/
625 :
626 : static inline void
627 158 : insert_node(
628 : struct CCC_Singly_linked_list *const list,
629 : struct CCC_Singly_linked_list_node *const before,
630 : struct CCC_Singly_linked_list_node *const node
631 : ) {
632 158 : if (before) {
633 10 : if (node) {
634 10 : node->next = before->next;
635 10 : }
636 10 : before->next = node;
637 10 : } else {
638 148 : if (node) {
639 148 : node->next = list->head;
640 148 : }
641 148 : list->head = node;
642 : }
643 158 : }
644 :
645 : static inline void
646 39 : remove_node(
647 : struct CCC_Singly_linked_list *const list,
648 : struct CCC_Singly_linked_list_node *const before,
649 : struct CCC_Singly_linked_list_node *const node
650 : ) {
651 39 : if (before) {
652 12 : if (node) {
653 12 : before->next = node->next;
654 12 : node->next = NULL;
655 12 : } else {
656 0 : before->next = NULL;
657 : }
658 12 : } else {
659 27 : if (node) {
660 27 : list->head = node->next;
661 27 : node->next = NULL;
662 27 : } else {
663 0 : list->head = NULL;
664 : }
665 : }
666 39 : }
667 :
668 : static inline struct CCC_Singly_linked_list_node *
669 42 : before(
670 : struct CCC_Singly_linked_list const *const list,
671 : struct CCC_Singly_linked_list_node const *const to_find
672 : ) {
673 42 : struct CCC_Singly_linked_list_node *i = list->head;
674 129 : for (; i && i->next != to_find; i = i->next) {}
675 84 : return i;
676 42 : }
677 :
678 : static void
679 4 : erase_range(
680 : struct CCC_Singly_linked_list const *const list,
681 : struct CCC_Singly_linked_list_node const *begin,
682 : struct CCC_Singly_linked_list_node *const end,
683 : CCC_Allocator const *const allocator
684 : ) {
685 4 : if (!allocator->allocate) {
686 1 : return;
687 : }
688 7 : for (;;) {
689 7 : CCC_Singly_linked_list_node *const next = begin->next;
690 28 : (void)allocator->allocate((CCC_Allocator_arguments){
691 7 : .input = struct_base(list, begin),
692 : .bytes = 0,
693 7 : .alignment = list->alignof_type,
694 7 : .context = allocator->context,
695 : });
696 7 : if (begin == end) {
697 3 : break;
698 : }
699 4 : begin = next;
700 7 : }
701 7 : }
702 :
703 : /** Returns the length [begin, end). Assumes end follows begin. */
704 : static size_t
705 16 : len(struct CCC_Singly_linked_list_node const *begin,
706 : struct CCC_Singly_linked_list_node const *const end) {
707 16 : size_t s = 0;
708 61 : for (; begin != end; begin = begin->next, ++s) {}
709 32 : return s;
710 16 : }
711 :
712 : /** Provides the base address of the user struct holding e. */
713 : static inline void *
714 1441 : struct_base(
715 : struct CCC_Singly_linked_list const *const list,
716 : struct CCC_Singly_linked_list_node const *const node
717 : ) {
718 1441 : return node ? ((char *)&node->next) - list->type_intruder_offset : NULL;
719 : }
720 :
721 : /** Given the user struct provides the address of intrusive elem. */
722 : static inline struct CCC_Singly_linked_list_node *
723 103 : elem_in(
724 : struct CCC_Singly_linked_list const *const list,
725 : void const *const any_struct
726 : ) {
727 103 : return any_struct ? (struct CCC_Singly_linked_list_node
728 103 : *)((char *)any_struct + list->type_intruder_offset)
729 : : NULL;
730 : }
731 :
732 : /** Calls the user provided three way comparison callback function on the user
733 : type wrapping the provided intrusive handles. Returns the three way comparison
734 : result value. */
735 : static inline CCC_Order
736 496 : get_order(
737 : struct CCC_Singly_linked_list const *const list,
738 : struct CCC_Singly_linked_list_node const *const left,
739 : struct CCC_Singly_linked_list_node const *const right,
740 : CCC_Comparator const *const comparator
741 : ) {
742 1984 : return comparator->compare((CCC_Comparator_arguments){
743 496 : .type_left = struct_base(list, left),
744 496 : .type_right = struct_base(list, right),
745 496 : .context = comparator->context,
746 : });
747 : }
|
