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 `source/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/doubly_linked_list.h"
25 : #include "ccc/private/private_doubly_linked_list.h"
26 : #include "ccc/sort.h"
27 : #include "ccc/types.h"
28 :
29 : /*=========================== Prototypes ===============================*/
30 :
31 : static void push_back(
32 : struct CCC_Doubly_linked_list *, struct CCC_Doubly_linked_list_node *
33 : );
34 : static void push_front(
35 : struct CCC_Doubly_linked_list *, struct CCC_Doubly_linked_list_node *
36 : );
37 : static void remove_node(
38 : struct CCC_Doubly_linked_list *, struct CCC_Doubly_linked_list_node *
39 : );
40 : static void insert_node(
41 : struct CCC_Doubly_linked_list *,
42 : struct CCC_Doubly_linked_list_node *,
43 : struct CCC_Doubly_linked_list_node *
44 : );
45 : static void *struct_base(
46 : struct CCC_Doubly_linked_list const *,
47 : struct CCC_Doubly_linked_list_node const *
48 : );
49 : static void erase_inclusive_range(
50 : struct CCC_Doubly_linked_list const *,
51 : struct CCC_Doubly_linked_list_node *,
52 : struct CCC_Doubly_linked_list_node *,
53 : CCC_Allocator const *
54 : );
55 : static size_t
56 : len(struct CCC_Doubly_linked_list_node const *,
57 : struct CCC_Doubly_linked_list_node const *);
58 : static struct CCC_Doubly_linked_list_node *
59 : type_intruder_in(CCC_Doubly_linked_list const *, void const *);
60 : static struct CCC_Doubly_linked_list_node *first_out_of_order(
61 : struct CCC_Doubly_linked_list const *,
62 : struct CCC_Doubly_linked_list_node *,
63 : CCC_Order,
64 : CCC_Comparator const *
65 : );
66 : static struct CCC_Doubly_linked_list_node *merge(
67 : struct CCC_Doubly_linked_list *,
68 : struct CCC_Doubly_linked_list_node *,
69 : struct CCC_Doubly_linked_list_node *,
70 : struct CCC_Doubly_linked_list_node *,
71 : CCC_Order,
72 : CCC_Comparator const *
73 : );
74 : static CCC_Order get_order(
75 : struct CCC_Doubly_linked_list const *,
76 : struct CCC_Doubly_linked_list_node const *,
77 : struct CCC_Doubly_linked_list_node const *,
78 : CCC_Comparator const *
79 : );
80 :
81 : /*=========================== Interface ===============================*/
82 :
83 : void *
84 26 : CCC_doubly_linked_list_push_front(
85 : CCC_Doubly_linked_list *const list,
86 : CCC_Doubly_linked_list_node *type_intruder,
87 : CCC_Allocator const *const allocator
88 : ) {
89 26 : if (!list || !type_intruder || !allocator) {
90 3 : return NULL;
91 : }
92 23 : if (allocator->allocate) {
93 20 : void *const copy = allocator->allocate((CCC_Allocator_arguments){
94 : .input = NULL,
95 5 : .bytes = list->sizeof_type,
96 5 : .alignment = list->alignof_type,
97 5 : .context = allocator->context,
98 : });
99 5 : if (!copy) {
100 1 : return NULL;
101 : }
102 4 : memcpy(copy, struct_base(list, type_intruder), list->sizeof_type);
103 4 : type_intruder = type_intruder_in(list, copy);
104 5 : }
105 :
106 22 : push_front(list, type_intruder);
107 22 : return struct_base(list, type_intruder);
108 26 : }
109 :
110 : void *
111 49 : CCC_doubly_linked_list_push_back(
112 : CCC_Doubly_linked_list *const list,
113 : CCC_Doubly_linked_list_node *type_intruder,
114 : CCC_Allocator const *const allocator
115 : ) {
116 49 : if (!list || !type_intruder || !allocator) {
117 3 : return NULL;
118 : }
119 46 : if (allocator->allocate) {
120 32 : void *const node = allocator->allocate((CCC_Allocator_arguments){
121 : .input = NULL,
122 8 : .bytes = list->sizeof_type,
123 8 : .alignment = list->alignof_type,
124 8 : .context = allocator->context,
125 : });
126 8 : if (!node) {
127 1 : return NULL;
128 : }
129 7 : (void)memcpy(node, struct_base(list, type_intruder), list->sizeof_type);
130 7 : type_intruder = type_intruder_in(list, node);
131 8 : }
132 45 : push_back(list, type_intruder);
133 45 : return struct_base(list, type_intruder);
134 49 : }
135 :
136 : void *
137 18 : CCC_doubly_linked_list_front(CCC_Doubly_linked_list const *list) {
138 18 : if (!list) {
139 1 : return NULL;
140 : }
141 17 : return struct_base(list, list->head);
142 18 : }
143 :
144 : void *
145 12 : CCC_doubly_linked_list_back(CCC_Doubly_linked_list const *list) {
146 12 : if (!list) {
147 1 : return NULL;
148 : }
149 11 : return struct_base(list, list->tail);
150 12 : }
151 :
152 : CCC_Result
153 4 : CCC_doubly_linked_list_pop_front(
154 : CCC_Doubly_linked_list *const list, CCC_Allocator const *const allocator
155 : ) {
156 4 : if (!list || !list->head || !allocator) {
157 1 : return CCC_RESULT_ARGUMENT_ERROR;
158 : }
159 3 : struct CCC_Doubly_linked_list_node *const r = list->head;
160 3 : remove_node(list, r);
161 3 : if (allocator->allocate) {
162 3 : assert(r);
163 12 : (void)allocator->allocate((CCC_Allocator_arguments){
164 3 : .input = struct_base(list, r),
165 : .bytes = 0,
166 3 : .alignment = list->alignof_type,
167 3 : .context = allocator->context,
168 : });
169 3 : }
170 3 : return CCC_RESULT_OK;
171 4 : }
172 :
173 : CCC_Result
174 9 : CCC_doubly_linked_list_pop_back(
175 : CCC_Doubly_linked_list *const list, CCC_Allocator const *const allocator
176 : ) {
177 9 : if (!list || !list->head || !allocator) {
178 1 : return CCC_RESULT_ARGUMENT_ERROR;
179 : }
180 8 : struct CCC_Doubly_linked_list_node *const r = list->tail;
181 8 : remove_node(list, r);
182 8 : if (allocator->allocate) {
183 16 : (void)allocator->allocate((CCC_Allocator_arguments){
184 4 : .input = struct_base(list, r),
185 : .bytes = 0,
186 4 : .alignment = list->alignof_type,
187 4 : .context = allocator->context,
188 : });
189 4 : }
190 8 : return CCC_RESULT_OK;
191 9 : }
192 :
193 : void *
194 6 : CCC_doubly_linked_list_insert(
195 : CCC_Doubly_linked_list *const list,
196 : CCC_Doubly_linked_list_node *const position,
197 : CCC_Doubly_linked_list_node *type_intruder,
198 : CCC_Allocator const *const allocator
199 : ) {
200 6 : if (!list || !type_intruder || !allocator) {
201 3 : return NULL;
202 : }
203 3 : if (allocator->allocate) {
204 12 : void *const node = allocator->allocate((CCC_Allocator_arguments){
205 : .input = NULL,
206 3 : .bytes = list->sizeof_type,
207 3 : .alignment = list->alignof_type,
208 3 : .context = allocator->context,
209 : });
210 3 : if (!node) {
211 1 : return NULL;
212 : }
213 2 : (void)memcpy(node, struct_base(list, type_intruder), list->sizeof_type);
214 2 : type_intruder = type_intruder_in(list, node);
215 3 : }
216 2 : insert_node(list, position, type_intruder);
217 2 : return struct_base(list, type_intruder);
218 6 : }
219 :
220 : void *
221 5 : CCC_doubly_linked_list_erase(
222 : CCC_Doubly_linked_list *const list,
223 : CCC_Doubly_linked_list_node *type_intruder,
224 : CCC_Allocator const *const allocator
225 : ) {
226 5 : if (!list || !type_intruder || !allocator || !list->head) {
227 3 : return NULL;
228 : }
229 2 : void *const ret = struct_base(list, type_intruder->next);
230 2 : remove_node(list, type_intruder);
231 2 : if (allocator->allocate) {
232 8 : (void)allocator->allocate((CCC_Allocator_arguments){
233 2 : .input = struct_base(list, type_intruder),
234 : .bytes = 0,
235 2 : .alignment = list->alignof_type,
236 2 : .context = allocator->context,
237 : });
238 2 : }
239 2 : return ret;
240 5 : }
241 :
242 : void *
243 7 : CCC_doubly_linked_list_erase_range(
244 : CCC_Doubly_linked_list *const list,
245 : CCC_Doubly_linked_list_node *const type_intruder_begin,
246 : CCC_Doubly_linked_list_node *type_intruder_end,
247 : CCC_Allocator const *const allocator
248 : ) {
249 7 : if (!list || !allocator || !list->head || !type_intruder_begin
250 5 : || type_intruder_begin == type_intruder_end) {
251 3 : return NULL;
252 : }
253 4 : if (type_intruder_end) {
254 3 : type_intruder_end = type_intruder_end->previous;
255 3 : }
256 4 : if (type_intruder_begin == type_intruder_end) {
257 1 : return CCC_doubly_linked_list_erase(
258 1 : list, type_intruder_begin, allocator
259 : );
260 : }
261 3 : CCC_Doubly_linked_list_node *const previous = type_intruder_begin->previous;
262 6 : CCC_Doubly_linked_list_node *const next
263 3 : = type_intruder_end ? type_intruder_end->next : NULL;
264 :
265 3 : if (previous) {
266 1 : previous->next = next;
267 1 : } else {
268 2 : list->head = next;
269 : }
270 :
271 3 : if (next) {
272 2 : next->previous = previous;
273 2 : } else {
274 1 : list->tail = previous;
275 : }
276 :
277 3 : type_intruder_begin->previous = NULL;
278 3 : if (type_intruder_end) {
279 2 : type_intruder_end->next = NULL;
280 2 : }
281 3 : erase_inclusive_range(
282 3 : list, type_intruder_begin, type_intruder_end, allocator
283 : );
284 :
285 3 : return struct_base(list, next);
286 7 : }
287 :
288 : CCC_Doubly_linked_list_node *
289 25 : CCC_doubly_linked_list_node_begin(CCC_Doubly_linked_list const *const list) {
290 25 : return list ? list->head : NULL;
291 : }
292 :
293 : void *
294 6 : CCC_doubly_linked_list_extract(
295 : CCC_Doubly_linked_list *const list,
296 : CCC_Doubly_linked_list_node *type_intruder
297 : ) {
298 6 : if (!list || !type_intruder) {
299 2 : return NULL;
300 : }
301 4 : remove_node(list, type_intruder);
302 4 : return struct_base(list, type_intruder);
303 6 : }
304 :
305 : void *
306 5 : CCC_doubly_linked_list_extract_range(
307 : CCC_Doubly_linked_list *const list,
308 : CCC_Doubly_linked_list_node *type_intruder_begin,
309 : CCC_Doubly_linked_list_node *type_intruder_end
310 : ) {
311 5 : if (!list || !list->head || !type_intruder_begin
312 4 : || type_intruder_begin == type_intruder_end) {
313 2 : return NULL;
314 : }
315 3 : if (type_intruder_end) {
316 2 : type_intruder_end = type_intruder_end->previous;
317 2 : }
318 3 : if (type_intruder_begin == type_intruder_end) {
319 1 : remove_node(list, type_intruder_begin);
320 1 : return struct_base(list, type_intruder_begin);
321 : }
322 :
323 2 : CCC_Doubly_linked_list_node *const previous = type_intruder_begin->previous;
324 4 : CCC_Doubly_linked_list_node *const next
325 2 : = type_intruder_end ? type_intruder_end->next : NULL;
326 :
327 2 : if (previous) {
328 1 : previous->next = next;
329 1 : } else {
330 1 : list->head = next;
331 : }
332 :
333 2 : if (next) {
334 1 : next->previous = previous;
335 1 : } else {
336 1 : list->tail = previous;
337 : }
338 :
339 2 : type_intruder_begin->previous = NULL;
340 2 : if (type_intruder_end) {
341 1 : type_intruder_end->next = NULL;
342 1 : }
343 2 : return struct_base(list, next);
344 5 : }
345 :
346 : CCC_Result
347 23 : CCC_doubly_linked_list_splice(
348 : CCC_Doubly_linked_list *const position_doubly_linked_list,
349 : CCC_Doubly_linked_list_node *position,
350 : CCC_Doubly_linked_list *const to_cut_doubly_linked_list,
351 : CCC_Doubly_linked_list_node *to_cut
352 : ) {
353 23 : if (!position_doubly_linked_list || !to_cut_doubly_linked_list || !to_cut) {
354 3 : return CCC_RESULT_ARGUMENT_ERROR;
355 : }
356 20 : if ((to_cut_doubly_linked_list == position_doubly_linked_list)
357 20 : && (to_cut == position || (to_cut && to_cut->next == position))) {
358 1 : return CCC_RESULT_OK;
359 : }
360 19 : remove_node(to_cut_doubly_linked_list, to_cut);
361 19 : insert_node(position_doubly_linked_list, position, to_cut);
362 19 : return CCC_RESULT_OK;
363 23 : }
364 :
365 : CCC_Result
366 10 : CCC_doubly_linked_list_splice_range(
367 : CCC_Doubly_linked_list *const position_doubly_linked_list,
368 : CCC_Doubly_linked_list_node *const type_intruder_position,
369 : CCC_Doubly_linked_list *const to_cut_doubly_linked_list,
370 : CCC_Doubly_linked_list_node *const type_intruder_to_cut_begin,
371 : CCC_Doubly_linked_list_node *const type_intruder_to_cut_exclusive_end
372 : ) {
373 10 : if (!position_doubly_linked_list || !to_cut_doubly_linked_list
374 9 : || !type_intruder_to_cut_begin
375 8 : || type_intruder_to_cut_begin == type_intruder_to_cut_exclusive_end) {
376 3 : return CCC_RESULT_ARGUMENT_ERROR;
377 : }
378 14 : CCC_Doubly_linked_list_node *const to_cut_inclusive_end
379 7 : = type_intruder_to_cut_exclusive_end
380 3 : ? type_intruder_to_cut_exclusive_end->previous
381 4 : : to_cut_doubly_linked_list->tail;
382 7 : if (type_intruder_to_cut_begin == to_cut_inclusive_end) {
383 1 : return CCC_doubly_linked_list_splice(
384 1 : position_doubly_linked_list,
385 1 : type_intruder_position,
386 1 : to_cut_doubly_linked_list,
387 1 : type_intruder_to_cut_begin
388 : );
389 : }
390 :
391 12 : CCC_Doubly_linked_list_node *const to_cut_previous
392 6 : = type_intruder_to_cut_begin->previous;
393 :
394 6 : if (to_cut_previous) {
395 4 : to_cut_previous->next = type_intruder_to_cut_exclusive_end;
396 4 : } else {
397 2 : to_cut_doubly_linked_list->head = type_intruder_to_cut_exclusive_end;
398 : }
399 :
400 6 : if (type_intruder_to_cut_exclusive_end) {
401 2 : type_intruder_to_cut_exclusive_end->previous = to_cut_previous;
402 2 : } else {
403 4 : to_cut_doubly_linked_list->tail = to_cut_previous;
404 : }
405 12 : CCC_Doubly_linked_list_node *const position_previous
406 6 : = type_intruder_position ? type_intruder_position->previous
407 1 : : position_doubly_linked_list->tail;
408 :
409 6 : if (position_previous == position_doubly_linked_list->tail) {
410 2 : position_doubly_linked_list->tail = to_cut_inclusive_end;
411 2 : }
412 6 : if (position_previous) {
413 2 : position_previous->next = type_intruder_to_cut_begin;
414 2 : } else {
415 4 : position_doubly_linked_list->head = type_intruder_to_cut_begin;
416 : }
417 :
418 6 : type_intruder_to_cut_begin->previous = position_previous;
419 :
420 6 : if (to_cut_inclusive_end) {
421 6 : to_cut_inclusive_end->next = type_intruder_position;
422 6 : }
423 :
424 6 : if (type_intruder_position) {
425 5 : type_intruder_position->previous = to_cut_inclusive_end;
426 5 : }
427 :
428 6 : return CCC_RESULT_OK;
429 10 : }
430 :
431 : void *
432 41 : CCC_doubly_linked_list_begin(CCC_Doubly_linked_list const *const list) {
433 41 : if (!list || list->head == NULL) {
434 1 : return NULL;
435 : }
436 40 : return struct_base(list, list->head);
437 41 : }
438 :
439 : void *
440 37 : CCC_doubly_linked_list_reverse_begin(CCC_Doubly_linked_list const *const list) {
441 37 : if (!list || list->tail == NULL) {
442 1 : return NULL;
443 : }
444 36 : return struct_base(list, list->tail);
445 37 : }
446 :
447 : void *
448 286 : CCC_doubly_linked_list_end(CCC_Doubly_linked_list const *const) {
449 286 : return NULL;
450 : }
451 :
452 : void *
453 260 : CCC_doubly_linked_list_reverse_end(CCC_Doubly_linked_list const *const) {
454 260 : return NULL;
455 : }
456 :
457 : void *
458 243 : CCC_doubly_linked_list_next(
459 : CCC_Doubly_linked_list const *const list,
460 : CCC_Doubly_linked_list_node const *type_intruder
461 : ) {
462 243 : if (!list || !type_intruder || type_intruder->next == NULL) {
463 35 : return NULL;
464 : }
465 208 : return struct_base(list, type_intruder->next);
466 243 : }
467 :
468 : void *
469 231 : CCC_doubly_linked_list_reverse_next(
470 : CCC_Doubly_linked_list const *const list,
471 : CCC_Doubly_linked_list_node const *type_intruder
472 : ) {
473 231 : if (!list || !type_intruder || type_intruder->previous == NULL) {
474 34 : return NULL;
475 : }
476 197 : return struct_base(list, type_intruder->previous);
477 231 : }
478 :
479 : CCC_Count
480 38 : CCC_doubly_linked_list_count(CCC_Doubly_linked_list const *const list) {
481 38 : if (!list) {
482 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
483 : }
484 37 : return (CCC_Count){.count = len(list->head, NULL)};
485 38 : }
486 :
487 : CCC_Tribool
488 12 : CCC_doubly_linked_list_is_empty(CCC_Doubly_linked_list const *const list) {
489 12 : if (!list) {
490 1 : return CCC_TRIBOOL_ERROR;
491 : }
492 11 : return !list->head;
493 12 : }
494 :
495 : CCC_Result
496 7 : CCC_doubly_linked_list_clear(
497 : CCC_Doubly_linked_list *const list,
498 : CCC_Destructor const *const destructor,
499 : CCC_Allocator const *const allocator
500 : ) {
501 7 : if (!list || !destructor || !allocator) {
502 3 : return CCC_RESULT_ARGUMENT_ERROR;
503 : }
504 4 : if (!destructor->destroy && !allocator->allocate) {
505 1 : list->head = list->tail = NULL;
506 1 : return CCC_RESULT_OK;
507 : }
508 17 : while (list->head) {
509 14 : struct CCC_Doubly_linked_list_node *const removed = list->head;
510 14 : remove_node(list, removed);
511 14 : void *const node = struct_base(list, removed);
512 14 : if (destructor->destroy) {
513 24 : destructor->destroy((CCC_Arguments){
514 8 : .type = node,
515 8 : .context = destructor->context,
516 : });
517 8 : }
518 14 : if (allocator->allocate) {
519 56 : (void)allocator->allocate((CCC_Allocator_arguments){
520 14 : .input = node,
521 : .bytes = 0,
522 14 : .alignment = list->alignof_type,
523 14 : .context = allocator->context,
524 : });
525 14 : }
526 14 : }
527 3 : list->tail = NULL;
528 3 : return CCC_RESULT_OK;
529 7 : }
530 :
531 : CCC_Tribool
532 118 : CCC_doubly_linked_list_validate(CCC_Doubly_linked_list const *const list) {
533 118 : if (!list) {
534 0 : return CCC_TRIBOOL_ERROR;
535 : }
536 118 : if (!list->head && !list->tail) {
537 7 : return CCC_TRUE;
538 : }
539 111 : if (!list->head || !list->tail) {
540 0 : return CCC_FALSE;
541 : }
542 111 : struct CCC_Doubly_linked_list_node const *forward = list->head;
543 111 : struct CCC_Doubly_linked_list_node const *reverse = list->tail;
544 789 : while (forward && reverse && forward != list->tail
545 450 : && reverse != list->head) {
546 339 : if (!forward || forward->next == forward
547 339 : || forward->previous == forward) {
548 0 : return CCC_FALSE;
549 : }
550 339 : if (!reverse || reverse->next == reverse
551 339 : || reverse->previous == reverse) {
552 0 : return CCC_FALSE;
553 : }
554 339 : forward = forward->next;
555 339 : reverse = reverse->previous;
556 : }
557 111 : return CCC_TRUE;
558 118 : }
559 :
560 : /*========================== Sorting ================================*/
561 :
562 : /** Returns true if the list is sorted in non-decreasing order. The user should
563 : flip the return values of their comparison function if they want a different
564 : order for elements.*/
565 : CCC_Tribool
566 20 : CCC_doubly_linked_list_is_sorted(
567 : CCC_Doubly_linked_list const *const list,
568 : CCC_Order const order,
569 : CCC_Comparator const *const comparator
570 : ) {
571 20 : if (!list || !comparator || !comparator->compare
572 18 : || (order != CCC_ORDER_LESSER && order != CCC_ORDER_GREATER)) {
573 3 : return CCC_TRIBOOL_ERROR;
574 : }
575 17 : if (list->head == list->tail) {
576 1 : return CCC_TRUE;
577 : }
578 32 : CCC_Order const wrong_order
579 16 : = order == CCC_ORDER_LESSER ? CCC_ORDER_GREATER : CCC_ORDER_LESSER;
580 88 : for (struct CCC_Doubly_linked_list_node const *cur = list->head->next;
581 79 : cur != NULL;
582 63 : cur = cur->next) {
583 72 : if (get_order(list, cur->previous, cur, comparator) == wrong_order) {
584 9 : return CCC_FALSE;
585 : }
586 63 : }
587 7 : return CCC_TRUE;
588 20 : }
589 :
590 : /** Inserts an element in the provided order. This means an element will go to
591 : the end of a section of duplicate values which is good for round-robin style
592 : list use. */
593 : void *
594 12 : CCC_doubly_linked_list_insert_sorted(
595 : CCC_Doubly_linked_list *const list,
596 : CCC_Doubly_linked_list_node *type_intruder,
597 : CCC_Order const order,
598 : CCC_Comparator const *const comparator,
599 : CCC_Allocator const *const allocator
600 : ) {
601 12 : if (!list || !allocator || !comparator || !comparator->compare
602 9 : || !type_intruder) {
603 4 : return NULL;
604 : }
605 8 : if (allocator->allocate) {
606 12 : void *const node = allocator->allocate((CCC_Allocator_arguments){
607 : .input = NULL,
608 3 : .bytes = list->sizeof_type,
609 3 : .alignment = list->alignof_type,
610 3 : .context = allocator->context,
611 : });
612 3 : if (!node) {
613 2 : return NULL;
614 : }
615 1 : (void)memcpy(node, struct_base(list, type_intruder), list->sizeof_type);
616 1 : type_intruder = type_intruder_in(list, node);
617 3 : }
618 6 : struct CCC_Doubly_linked_list_node *pos = list->head;
619 87 : for (; pos != NULL
620 44 : && get_order(list, type_intruder, pos, comparator) != order;
621 38 : pos = pos->next) {}
622 6 : insert_node(list, pos, type_intruder);
623 6 : return struct_base(list, type_intruder);
624 12 : }
625 :
626 : /** Sorts the list in the provided order according to the user comparison
627 : callback function in `O(N * log(N))` time and `O(1)` space. This sort is stable.
628 :
629 : The following merging algorithm and associated helper functions are based on
630 : the iterative natural merge sort used in the list module of the pintOS project
631 : for learning operating systems. Currently the original is located at the
632 : following path in the pintOS source code:
633 :
634 : `src/lib/kernel/list.c`
635 :
636 : However, if refactors change this location, seek the list intrusive container
637 : module for original implementations. The code has been changed for the C
638 : Container Collection as follows:
639 :
640 : - there is no sentinel node, only NULL pointer.
641 : - splicing in the merge operation has been simplified along with other tweaks.
642 : - comparison callbacks are handled with three way comparison.
643 :
644 : If the runtime is not obvious from the code, consider that this algorithm runs
645 : bottom up on sorted sub-ranges. It roughly "halves" the remaining sub-ranges
646 : that need to be sorted by roughly "doubling" the length of a sorted range on
647 : each merge step. Therefore the number of times we must perform the merge step is
648 : `O(log(N))`. The most elements we would have to merge in the merge step is all
649 : `N` elements so together that gives us the runtime of `O(N * log(N))`. */
650 : CCC_Result
651 10 : CCC_sort_doubly_linked_list_mergesort(
652 : CCC_Doubly_linked_list *const list,
653 : CCC_Order const order,
654 : CCC_Comparator const *const comparator
655 : ) {
656 10 : if (!list || !comparator || !comparator->compare
657 8 : || (order != CCC_ORDER_LESSER && order != CCC_ORDER_GREATER)) {
658 3 : return CCC_RESULT_ARGUMENT_ERROR;
659 : }
660 : /* Algorithm is one pass if list is sorted. Merging is never true. */
661 7 : CCC_Tribool merging = CCC_FALSE;
662 7 : do {
663 28 : merging = CCC_FALSE;
664 : /* 0th index of the A list. The start of one list to merge. */
665 28 : struct CCC_Doubly_linked_list_node *left_start = list->head;
666 66 : while (left_start != NULL) {
667 : /* The Nth index of list A (its size) aka 0th index of B list. */
668 106 : struct CCC_Doubly_linked_list_node *const left_end_right_start
669 53 : = first_out_of_order(list, left_start, order, comparator);
670 53 : if (left_end_right_start == NULL) {
671 15 : break;
672 : }
673 : /* Left picks up the exclusive end of this merge, the start of
674 : right, in order to progress the sorting algorithm with the next
675 : run that needs fixing. Merge returns the end of right to indicate
676 : it is the final sentinel node yet to be examined. */
677 38 : left_start = merge(
678 38 : list,
679 38 : left_start,
680 38 : left_end_right_start,
681 38 : first_out_of_order(
682 38 : list, left_end_right_start, order, comparator
683 : ),
684 38 : order,
685 38 : comparator
686 : );
687 38 : merging = CCC_TRUE;
688 53 : }
689 28 : } while (merging);
690 7 : return CCC_RESULT_OK;
691 10 : }
692 :
693 : /** Merges lists `[left, right)` with `[right, right_end)`
694 : to form `[left, right_end)`. Returns the exclusive end of the range,
695 : `right_end`, once the merge sort is complete.
696 :
697 : Notice that all ranges treat the end of their range as an exclusive sentinel for
698 : consistency. This function assumes the provided lists are already sorted
699 : separately. */
700 : static inline struct CCC_Doubly_linked_list_node *
701 38 : merge(
702 : struct CCC_Doubly_linked_list *const list,
703 : struct CCC_Doubly_linked_list_node *left,
704 : struct CCC_Doubly_linked_list_node *right,
705 : struct CCC_Doubly_linked_list_node *const right_end,
706 : CCC_Order const order,
707 : CCC_Comparator const *const comparator
708 : ) {
709 154 : while (left && left != right && right && right != right_end) {
710 116 : if (get_order(list, right, left, comparator) == order) {
711 77 : struct CCC_Doubly_linked_list_node *const to_merge = right;
712 77 : right = to_merge->next;
713 77 : if (to_merge->next) {
714 64 : to_merge->next->previous = to_merge->previous;
715 64 : } else {
716 13 : list->tail = to_merge->previous;
717 : }
718 0 : assert(
719 77 : to_merge->previous
720 77 : && "merged element must always have a previous pointer because "
721 : "lists of size 1 or less are not merged and merging "
722 : "iterates forward"
723 : );
724 77 : to_merge->previous->next = to_merge->next;
725 77 : to_merge->previous = left->previous;
726 77 : to_merge->next = left;
727 77 : if (left->previous) {
728 57 : left->previous->next = to_merge;
729 57 : } else {
730 20 : list->head = to_merge;
731 : }
732 77 : left->previous = to_merge;
733 77 : } else {
734 39 : left = left->next;
735 : }
736 : }
737 38 : return right_end;
738 : }
739 :
740 : /** Finds the first element lesser than it's previous element as defined by
741 : the user comparison callback function. If no out of order element can be
742 : found the list sentinel is returned. */
743 : static inline struct CCC_Doubly_linked_list_node *
744 91 : first_out_of_order(
745 : struct CCC_Doubly_linked_list const *const list,
746 : struct CCC_Doubly_linked_list_node *start,
747 : CCC_Order const order,
748 : CCC_Comparator const *const comparator
749 : ) {
750 91 : assert(list && start);
751 91 : do {
752 268 : start = start->next;
753 359 : } while (start != NULL
754 268 : && get_order(list, start, start->previous, comparator) != order);
755 91 : return start;
756 : }
757 :
758 : /*======================= Private Interface ===========================*/
759 :
760 : void
761 101 : CCC_private_doubly_linked_list_push_back(
762 : struct CCC_Doubly_linked_list *const list,
763 : struct CCC_Doubly_linked_list_node *type_intruder
764 : ) {
765 101 : push_back(list, type_intruder);
766 101 : }
767 :
768 : void
769 4 : CCC_private_doubly_linked_list_push_front(
770 : struct CCC_Doubly_linked_list *const list,
771 : struct CCC_Doubly_linked_list_node *const type_intruder
772 : ) {
773 4 : push_front(list, type_intruder);
774 4 : }
775 :
776 : struct CCC_Doubly_linked_list_node *
777 105 : CCC_private_doubly_linked_list_node_in(
778 : struct CCC_Doubly_linked_list const *const list,
779 : void const *const any_struct
780 : ) {
781 105 : return type_intruder_in(list, any_struct);
782 : }
783 :
784 : /*======================= Static Helpers ===========================*/
785 :
786 : static inline void
787 26 : push_front(
788 : struct CCC_Doubly_linked_list *const list,
789 : struct CCC_Doubly_linked_list_node *const node
790 : ) {
791 26 : node->previous = NULL;
792 26 : node->next = list->head;
793 26 : if (list->head) {
794 17 : list->head->previous = node;
795 17 : } else {
796 9 : list->tail = node;
797 : }
798 26 : list->head = node;
799 26 : }
800 :
801 : static inline void
802 149 : push_back(
803 : struct CCC_Doubly_linked_list *const list,
804 : struct CCC_Doubly_linked_list_node *const node
805 : ) {
806 149 : node->next = NULL;
807 149 : node->previous = list->tail;
808 149 : if (list->tail) {
809 124 : list->tail->next = node;
810 124 : } else {
811 25 : list->head = node;
812 : }
813 149 : list->tail = node;
814 149 : }
815 :
816 : static inline void
817 27 : insert_node(
818 : struct CCC_Doubly_linked_list *const list,
819 : struct CCC_Doubly_linked_list_node *const position,
820 : struct CCC_Doubly_linked_list_node *const node
821 : ) {
822 27 : if (!position) {
823 3 : return push_back(list, node);
824 : }
825 24 : node->next = position;
826 24 : node->previous = position->previous;
827 :
828 24 : if (position->previous) {
829 7 : position->previous->next = node;
830 7 : } else {
831 17 : list->head = node;
832 : }
833 24 : position->previous = node;
834 51 : }
835 :
836 : static inline void
837 51 : remove_node(
838 : struct CCC_Doubly_linked_list *const list,
839 : struct CCC_Doubly_linked_list_node *const node
840 : ) {
841 51 : if (node->previous) {
842 27 : node->previous->next = node->next;
843 27 : } else {
844 24 : list->head = node->next;
845 : }
846 51 : if (node->next) {
847 31 : node->next->previous = node->previous;
848 31 : } else {
849 20 : list->tail = node->previous;
850 : }
851 51 : node->next = node->previous = NULL;
852 51 : }
853 :
854 : /** Operates on each element in the specified range calling the allocation
855 : function to free the nodes, if provided. In either case, the number of nodes
856 : in the inclusive range is returned. */
857 : static void
858 3 : erase_inclusive_range(
859 : struct CCC_Doubly_linked_list const *const list,
860 : struct CCC_Doubly_linked_list_node *begin,
861 : struct CCC_Doubly_linked_list_node *const inclusive_end,
862 : CCC_Allocator const *const allocator
863 : ) {
864 3 : if (!allocator->allocate) {
865 1 : return;
866 : }
867 7 : while (begin) {
868 6 : CCC_Doubly_linked_list_node *const next = begin->next;
869 24 : allocator->allocate((CCC_Allocator_arguments){
870 6 : .input = struct_base(list, begin),
871 : .bytes = 0,
872 6 : .alignment = list->alignof_type,
873 6 : .context = allocator->context,
874 : });
875 6 : if (begin == inclusive_end) {
876 1 : break;
877 : }
878 5 : begin = next;
879 6 : }
880 5 : }
881 :
882 : /** Finds the length from [begin, end). */
883 : static size_t
884 37 : len(struct CCC_Doubly_linked_list_node const *begin,
885 : struct CCC_Doubly_linked_list_node const *const end) {
886 37 : size_t s = 0;
887 137 : while (begin != end) {
888 100 : begin = begin->next;
889 100 : ++s;
890 : }
891 74 : return s;
892 37 : }
893 :
894 : static inline void *
895 1581 : struct_base(
896 : struct CCC_Doubly_linked_list const *const list,
897 : struct CCC_Doubly_linked_list_node const *const node
898 : ) {
899 1581 : return node ? ((char *)&node->next) - list->type_intruder_offset : NULL;
900 : }
901 :
902 : static inline struct CCC_Doubly_linked_list_node *
903 119 : type_intruder_in(
904 : struct CCC_Doubly_linked_list const *const list,
905 : void const *const struct_base
906 : ) {
907 119 : return struct_base
908 : ? (struct CCC_Doubly_linked_list_node
909 119 : *)((char *)struct_base + list->type_intruder_offset)
910 : : NULL;
911 : }
912 :
913 : static inline CCC_Order
914 471 : get_order(
915 : struct CCC_Doubly_linked_list const *const list,
916 : struct CCC_Doubly_linked_list_node const *const left,
917 : struct CCC_Doubly_linked_list_node const *const right,
918 : CCC_Comparator const *const comparator
919 : ) {
920 1884 : return comparator->compare((CCC_Comparator_arguments){
921 471 : .type_left = struct_base(list, left),
922 471 : .type_right = struct_base(list, right),
923 471 : .context = comparator->context,
924 : });
925 : }
|
