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