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