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