Line data Source code
1 : /***************************************************************************//**
2 :
3 : @file linkedlist.c
4 :
5 : @author Stephen Brennan
6 :
7 : @date Created Thursday, 12 September 2013
8 :
9 : @brief Implementation of "libstephen/ll.h".
10 :
11 : @copyright Copyright (c) 2013-2016, Stephen Brennan. Released under the
12 : Revised BSD License. See the LICENSE.txt file for details.
13 :
14 : *******************************************************************************/
15 :
16 : #include <stdlib.h>
17 : #include <stdio.h>
18 : #include <stdbool.h>
19 : #include <assert.h>
20 :
21 : #include "libstephen/ll.h"
22 :
23 : /*******************************************************************************
24 :
25 : Private Functions
26 :
27 : *******************************************************************************/
28 :
29 : /**
30 : @brief Removes the given node, reassigning the links to and from it.
31 :
32 : Frees the node, in addition no reassigning links. Once this function is
33 : called, the_node is invlidated. Please note that this function *does not*
34 : decrement the list's length!
35 :
36 : This function is a *private* function, not declared in libstephen.h for a
37 : reason. It is only necessary for the implementation functions within this
38 : file.
39 :
40 : @param list The list that contains this node.
41 : @param the_node The node to delete.
42 : */
43 501082 : void ll_remove_node(smb_ll *list, smb_ll_node *the_node)
44 : {
45 501082 : smb_ll_node *previous = the_node->prev;
46 501082 : smb_ll_node *next = the_node->next;
47 501082 : if (previous) {
48 8 : previous->next = next;
49 : } else {
50 501074 : list->head = next;
51 : }
52 501082 : if (next) {
53 500047 : next->prev = previous;
54 : } else {
55 1035 : list->tail = previous;
56 : }
57 501082 : smb_free(the_node);
58 501082 : }
59 :
60 40418 : smb_ll_node *ll_node_navigate(smb_ll_node *node, int index)
61 : {
62 40418 : int i = 0;
63 2749671 : while (i < index) {
64 2668835 : node = node->next;
65 2668835 : i++;
66 : }
67 40418 : return node;
68 : }
69 :
70 : /**
71 : @brief Navigates to the given index in the list, returning the correct node,
72 : or NULL.
73 :
74 : This function is a *private* function, not declared in libstephen.h for a
75 : reason.
76 :
77 : @param list The list to navigate within.
78 : @param index The index to find in the list.
79 : @param[out] status Status variable.
80 : @returns A pointer to the node navigated to.
81 : @retval NULL if the index was out of range.
82 : @exception SMB_INDEX_ERROR if the given index was out of range.
83 : */
84 40415 : smb_ll_node * ll_navigate(const smb_ll *list, int index, smb_status *status)
85 : {
86 40415 : smb_ll_node *node = list->head;
87 40415 : if (index < 0 || index >= list->length) {
88 4 : *status = SMB_INDEX_ERROR;
89 4 : return NULL;
90 : }
91 40411 : return ll_node_navigate(node, index);
92 : }
93 :
94 : /**
95 : @brief Allocates and initializes a node with the given data.
96 :
97 : @param data The data to insert into the new node.
98 : @param[out] status Status variable.
99 : @return A pointer to the node created.
100 : */
101 501082 : smb_ll_node *ll_create_node(DATA data)
102 : {
103 501082 : smb_ll_node *new_node = smb_new(smb_ll_node, 1);
104 501082 : new_node->data = data;
105 501082 : new_node->next = NULL;
106 501082 : new_node->prev = NULL;
107 501082 : return new_node;
108 : }
109 :
110 : /*******************************************************************************
111 :
112 : Public Functions
113 :
114 : *******************************************************************************/
115 :
116 1053 : void ll_init(smb_ll *new_list)
117 : {
118 1053 : new_list->length = 0;
119 1053 : new_list->head = NULL;
120 1053 : new_list->tail = NULL;
121 1053 : }
122 :
123 1053 : smb_ll *ll_create()
124 : {
125 1053 : smb_ll *new_list = smb_new(smb_ll, 1);
126 1053 : ll_init(new_list);
127 1053 : return new_list;
128 : }
129 :
130 1053 : void ll_destroy(smb_ll *list)
131 : {
132 : // Iterate through each node, deleting them as we go
133 1053 : smb_ll_node *iter = list->head;
134 : smb_ll_node *temp;
135 503172 : while (iter) {
136 501066 : temp = iter->next;
137 501066 : ll_remove_node(list, iter);
138 501066 : iter = temp;
139 : }
140 1053 : }
141 :
142 1053 : void ll_delete(smb_ll *list)
143 : {
144 1053 : ll_destroy(list);
145 1053 : smb_free(list);
146 1053 : }
147 :
148 500874 : void ll_append(smb_ll *list, DATA new_data)
149 : {
150 : // Create the new node
151 500874 : smb_ll_node *new_node = ll_create_node(new_data);
152 :
153 : // Get the last node in the list
154 500874 : smb_ll_node *last_node = list->tail;
155 :
156 : // Link them together
157 500874 : if (last_node)
158 499847 : last_node->next = new_node;
159 : else
160 1027 : list->head = new_node;
161 500874 : new_node->prev = last_node;
162 500874 : list->tail = new_node;
163 500874 : list->length++;
164 500874 : }
165 :
166 207 : void ll_prepend(smb_ll *list, DATA new_data)
167 : {
168 : // Create the new smb_ll_node
169 207 : smb_ll_node *new_node = ll_create_node(new_data);
170 207 : smb_ll_node *first_node = list->head;
171 207 : new_node->next = first_node;
172 207 : if (first_node)
173 205 : first_node->prev = new_node;
174 : else
175 2 : list->tail = new_node;
176 207 : list->head = new_node;
177 207 : list->length++;
178 207 : }
179 :
180 25 : void ll_push_back(smb_ll *list, DATA new_data)
181 : {
182 25 : ll_append(list, new_data);
183 25 : }
184 :
185 7 : DATA ll_pop_back(smb_ll *list, smb_status *status)
186 : {
187 7 : *status = SMB_SUCCESS;
188 7 : smb_ll_node *last_node = list->tail;
189 7 : if (last_node) {
190 6 : DATA to_return = last_node->data;
191 6 : ll_remove_node(list, last_node);
192 6 : list->length--;
193 6 : return to_return;
194 : } else {
195 1 : *status = SMB_INDEX_ERROR;
196 1 : return PTR(NULL);
197 : }
198 : }
199 :
200 2 : DATA ll_peek_back(smb_ll *list, smb_status *status)
201 : {
202 2 : *status = SMB_SUCCESS;
203 2 : smb_ll_node *last_node = list->tail;
204 2 : if (last_node) {
205 1 : return last_node->data;
206 : } else {
207 1 : *status = SMB_INDEX_ERROR;
208 1 : return PTR(NULL);
209 : }
210 : }
211 :
212 5 : void ll_push_front(smb_ll *list, DATA new_data)
213 : {
214 5 : ll_prepend(list, new_data);
215 5 : }
216 :
217 6 : DATA ll_pop_front(smb_ll *list, smb_status *status)
218 : {
219 6 : *status = SMB_SUCCESS;
220 6 : smb_ll_node *first_node = list->head;
221 6 : if (first_node) {
222 5 : DATA to_return = first_node->data;
223 5 : ll_remove_node(list, first_node);
224 5 : list->length--;
225 5 : return to_return;
226 : } else {
227 1 : *status = SMB_INDEX_ERROR; // The list is empty
228 1 : return PTR(NULL);
229 : }
230 : }
231 :
232 2 : DATA ll_peek_front(smb_ll *list, smb_status *status)
233 : {
234 2 : *status = SMB_SUCCESS;
235 2 : smb_ll_node *first_node = list->head;
236 2 : if (first_node) {
237 1 : return first_node->data;
238 : } else {
239 1 : *status = SMB_INDEX_ERROR; // The list is empty
240 1 : return PTR(NULL);
241 : }
242 : }
243 :
244 40375 : DATA ll_get(const smb_ll *list, int index, smb_status *status)
245 : {
246 40375 : *status = SMB_SUCCESS;
247 : // Navigate to that position in the node.
248 40375 : smb_ll_node * the_node = ll_navigate(list, index, status);
249 40375 : if (*status == SMB_INDEX_ERROR) {
250 : // Return a dummy value.
251 1 : return PTR(NULL);
252 : } else {
253 40374 : return the_node->data;
254 : }
255 : }
256 :
257 5 : void ll_remove(smb_ll *list, int index, smb_status *status)
258 : {
259 : // Fond the node
260 5 : smb_ll_node *the_node = ll_navigate(list, index, status);
261 5 : if (*status == SMB_INDEX_ERROR) {
262 7 : return; // Return the INDEX_ERROR
263 : }
264 : // Remove it (managing the links and the list header)
265 3 : ll_remove_node(list, the_node);
266 3 : list->length--;
267 : }
268 :
269 5 : void ll_insert(smb_ll *list, int index, DATA new_data)
270 : {
271 5 : if (index <= 0) {
272 2 : ll_prepend(list, new_data);
273 3 : } else if (index >= list->length) {
274 2 : ll_append(list, new_data);
275 : } else {
276 1 : smb_ll_node *new_node = ll_create_node(new_data);
277 :
278 1 : smb_status status = SMB_SUCCESS;
279 1 : smb_ll_node *current = ll_navigate(list, index, &status);
280 :
281 : // Since we already checked indices, there can be no errors.
282 1 : assert(status == SMB_SUCCESS);
283 :
284 1 : current->prev->next = new_node;
285 1 : new_node->prev = current->prev;
286 1 : new_node->next = current;
287 1 : current->prev = new_node;
288 1 : list->length++;
289 : }
290 5 : }
291 :
292 34 : void ll_set(smb_ll *list, int index, DATA new_data, smb_status *status)
293 : {
294 34 : *status = SMB_SUCCESS;
295 34 : smb_ll_node *current = ll_navigate(list, index, status);
296 34 : if (current) {
297 33 : current->data = new_data;
298 : } else {
299 1 : *status = SMB_INDEX_ERROR;
300 : }
301 34 : }
302 :
303 542679 : int ll_length(const smb_ll *list)
304 : {
305 542679 : return list->length;
306 : }
307 :
308 : /**
309 : @brief Recursive mergesort helper function.
310 : @param head Pointer to the head pointer (will be updated to reflect new list
311 : after sorting).
312 : @param length Length of sublist. Expects the trailing node will not point to
313 : the next sublist.
314 : @param cmp Comparator.
315 : @returns The tail of the sorted list!
316 : */
317 16 : static smb_ll_node *ll_sort_rec(smb_ll_node **head, int length, DATA_COMPARE cmp)
318 : {
319 16 : smb_ll_node *left = *head;
320 : smb_ll_node *right, *tail, *next;
321 :
322 : // BASE CASE!
323 16 : if (length <= 1) {
324 9 : return *head;
325 : }
326 :
327 : // Find midpoint and bisect list.
328 7 : right = ll_node_navigate(*head, length/2);
329 7 : right->prev->next = NULL;
330 7 : right->prev = NULL;
331 :
332 : // Sort each sublist.
333 7 : ll_sort_rec(&left, length/2, cmp);
334 7 : ll_sort_rec(&right, length-length/2, cmp);
335 :
336 : // Pick the first element.
337 7 : if (cmp(left->data, right->data) <= 0) {
338 5 : *head = left;
339 5 : tail = left;
340 5 : left = left->next;
341 : } else {
342 2 : *head = right;
343 2 : tail = right;
344 2 : right = right->next;
345 : }
346 :
347 : // Merge the remaining elements.
348 31 : while (--length) {
349 17 : if (left == NULL) {
350 4 : next = right;
351 4 : right = right->next;
352 13 : } else if (right == NULL) {
353 4 : next = left;
354 4 : left = left->next;
355 9 : } else if (cmp(left->data, right->data) <= 0) {
356 3 : next = left;
357 3 : left = left->next;
358 : } else {
359 6 : next = right;
360 6 : right = right->next;
361 : }
362 17 : tail->next = next;
363 17 : next->prev = tail;
364 17 : next->next = NULL;
365 17 : tail = next;
366 : }
367 7 : tail->next = NULL;
368 7 : return tail;
369 : }
370 :
371 2 : void ll_sort(smb_ll *list, DATA_COMPARE comp)
372 : {
373 2 : list->tail = ll_sort_rec(&list->head, list->length, comp);
374 2 : }
375 :
376 22 : int ll_index_of(const smb_ll *list, DATA d, DATA_COMPARE comp)
377 : {
378 22 : int idx = 0;
379 22 : smb_ll_node *curr = list->head;
380 :
381 234 : while (curr) {
382 211 : if (comp != NULL) {
383 1 : if (comp(curr->data, d) == 0) {
384 1 : return idx;
385 : }
386 : } else {
387 210 : if (curr->data.data_llint == d.data_llint) {
388 20 : return idx;
389 : }
390 : }
391 190 : idx++;
392 190 : curr = curr->next;
393 : }
394 1 : return -1;
395 : }
396 :
397 : /**
398 : @brief Get the next item in the linked list.
399 :
400 : @param iterator A pointer to the iterator.
401 : @param[out] status Status variable.
402 : @returns The data at the new location of the iterator.
403 : @exception SMB_STOP_ITERATION If the list does not have another item.
404 : */
405 501541 : DATA ll_iter_next(smb_iter *iter, smb_status *status)
406 : {
407 501541 : *status = SMB_SUCCESS;
408 501541 : smb_ll_node *node = iter->state.data_ptr;
409 501541 : if (node == NULL) {
410 1000 : *status = SMB_STOP_ITERATION;
411 1000 : return iter->state; // a DATA containing NULL
412 : }
413 500541 : iter->state.data_ptr = node->next;
414 500541 : iter->index++;
415 500541 : return node->data;
416 : }
417 :
418 : /**
419 : @brief Check if the iterator can be advanced.
420 :
421 : @param iter A pointer to the iterator.
422 : @returns Whether the iterator can be advanced.
423 : */
424 501548 : bool ll_iter_has_next(smb_iter *iter)
425 : {
426 : bool node_clean, index_clean;
427 501548 : smb_ll_node *node = iter->state.data_ptr;
428 501548 : const smb_ll *ds = iter->ds;
429 :
430 : // Is there a node to return?
431 501548 : node_clean = node != NULL;
432 : // Is the index valid?
433 501548 : index_clean = iter->index < ll_length(ds);
434 :
435 : // Both should have the same value. It is impossible for the node to be null
436 : // when the index is in bounds. So, assert it.
437 501548 : assert(node_clean == index_clean);
438 :
439 501548 : return node_clean;
440 : }
441 :
442 : /**
443 : @brief Free the resources held by the iterator.
444 : @param iter A pointer to the iterator.
445 : @param free_src Whether to free the source list.
446 : */
447 1019 : void ll_iter_destroy(smb_iter *iter)
448 : {
449 : (void)iter; // unused
450 : // Nothing to destroy
451 1019 : }
452 :
453 : /**
454 : @brief Free the iterator and its resources.
455 : @param iter A pointer to the iterator
456 : @param free_src Whether to free the source list.
457 : */
458 1 : void ll_iter_delete(smb_iter *iter)
459 : {
460 1 : iter->destroy(iter);
461 1 : smb_free(iter);
462 1 : }
463 :
464 1023 : smb_iter ll_get_iter(const smb_ll *list)
465 : {
466 2046 : smb_iter iter = {
467 : // Data in the iterator
468 : .ds = list,
469 1023 : .state = (DATA) { .data_ptr = list->head },
470 : .index = 0,
471 :
472 : // Functions
473 : .next = &ll_iter_next,
474 : .has_next = &ll_iter_has_next,
475 : .destroy = &ll_iter_destroy,
476 : .delete = &ll_iter_delete
477 : };
478 :
479 1023 : return iter;
480 : }
481 :
482 3 : void ll_filter(smb_ll *list, bool (*test_function)(DATA))
483 : {
484 3 : smb_ll_node *curr = list->head, *next;
485 13 : while (curr) {
486 7 : next = curr->next;
487 7 : if (test_function(curr->data)) {
488 2 : ll_remove_node(list, curr);
489 2 : list->length--;
490 : }
491 7 : curr = next;
492 : }
493 3 : }
494 :
495 2 : void ll_map(smb_ll *list, DATA (*map_function)(DATA))
496 : {
497 2 : smb_ll_node *curr = list->head;
498 8 : while (curr) {
499 4 : curr->data = map_function(curr->data);
500 4 : curr = curr->next;
501 : }
502 2 : }
503 :
504 2 : DATA ll_foldl(smb_ll *list, DATA start_value, DATA (*reduction)(DATA,DATA))
505 : {
506 2 : smb_ll_node *curr = list->head;
507 8 : while (curr) {
508 4 : start_value = reduction(start_value, curr->data);
509 4 : curr = curr->next;
510 : }
511 2 : return start_value;
512 : }
513 :
514 2 : DATA ll_foldr(smb_ll *list, DATA start_value, DATA (*reduction)(DATA,DATA))
515 : {
516 2 : smb_ll_node *curr = list->tail;
517 8 : while (curr) {
518 4 : start_value = reduction(curr->data, start_value);
519 4 : curr = curr->prev;
520 : }
521 2 : return start_value;
522 : }
523 :
524 : /*******************************************************************************
525 :
526 : Linked List Adapter Functions
527 :
528 : These guys are used as the function pointers for the smb_list. They really
529 : don't need any documentation.
530 :
531 : *******************************************************************************/
532 :
533 271 : void ll_append_adapter(smb_list *l, DATA new_data)
534 : {
535 271 : smb_ll *list = (smb_ll*) (l->data);
536 271 : ll_append(list, new_data);
537 271 : }
538 :
539 200 : void ll_prepend_adapter(smb_list *l, DATA new_data)
540 : {
541 200 : smb_ll *list = (smb_ll*) (l->data);
542 200 : ll_prepend(list, new_data);
543 200 : }
544 :
545 40345 : DATA ll_get_adapter(const smb_list *l, int index, smb_status *status)
546 : {
547 40345 : const smb_ll *list = (const smb_ll*) (l->data);
548 40345 : return ll_get(list, index, status);
549 : }
550 :
551 5 : void ll_remove_adapter(smb_list *l, int index, smb_status *status)
552 : {
553 5 : smb_ll *list = (smb_ll*) (l->data);
554 5 : ll_remove(list, index, status);
555 5 : }
556 :
557 5 : void ll_insert_adapter(smb_list *l, int index, DATA new_data)
558 : {
559 5 : smb_ll *list = (smb_ll*) (l->data);
560 5 : ll_insert(list, index, new_data);
561 5 : }
562 :
563 8 : void ll_delete_adapter(smb_list *l)
564 : {
565 8 : smb_ll *list = (smb_ll*) (l->data);
566 8 : ll_delete(list);
567 8 : l->data = NULL;
568 8 : }
569 :
570 31 : void ll_set_adapter(smb_list *l, int index, DATA new_data, smb_status *status)
571 : {
572 31 : smb_ll *list = (smb_ll*) (l->data);
573 31 : ll_set(list, index, new_data, status);
574 31 : }
575 :
576 25 : void ll_push_back_adapter(smb_list *l, DATA new_data)
577 : {
578 25 : smb_ll *list = (smb_ll*) (l->data);
579 25 : ll_push_back(list, new_data);
580 25 : }
581 :
582 7 : DATA ll_pop_back_adapter(smb_list *l, smb_status *status)
583 : {
584 7 : smb_ll *list = (smb_ll*) (l->data);
585 7 : return ll_pop_back(list, status);
586 : }
587 :
588 2 : DATA ll_peek_back_adapter(smb_list *l, smb_status *status)
589 : {
590 2 : smb_ll *list = (smb_ll*) (l->data);
591 2 : return ll_peek_back(list, status);
592 : }
593 :
594 5 : void ll_push_front_adapter(smb_list *l, DATA new_data)
595 : {
596 5 : smb_ll *list = (smb_ll*) (l->data);
597 5 : ll_push_front(list, new_data);
598 5 : }
599 :
600 6 : DATA ll_pop_front_adapter(smb_list *l, smb_status *status)
601 : {
602 6 : smb_ll *list = (smb_ll*) (l->data);
603 6 : return ll_pop_front(list, status);
604 : }
605 :
606 2 : DATA ll_peek_front_adapter(smb_list *l, smb_status *status)
607 : {
608 2 : smb_ll *list = (smb_ll*) (l->data);
609 2 : return ll_peek_front(list, status);
610 : }
611 :
612 41116 : int ll_length_adapter(const smb_list *l)
613 : {
614 41116 : const smb_ll *list = (const smb_ll*) (l->data);
615 41116 : return ll_length(list);
616 : }
617 :
618 22 : int ll_index_of_adapter(const smb_list *l, DATA d, DATA_COMPARE comp)
619 : {
620 22 : const smb_ll *list = (const smb_ll*) (l->data);
621 22 : return ll_index_of(list, d, comp);
622 : }
623 :
624 : /**
625 : @brief Populate a generic smb_list with function pointers necessary to use
626 : smb_ll with it.
627 :
628 : Note that this is a *private* function, not defined in libstephen.h for a
629 : reason. You shouldn't need the function, as there is library functionality
630 : that provides it for you.
631 :
632 : @param generic_list The smb_list to populate with function pointers.
633 : */
634 8 : void ll_fill_functions(smb_list *generic_list)
635 : {
636 8 : generic_list->append = ll_append_adapter;
637 8 : generic_list->prepend = ll_prepend_adapter;
638 8 : generic_list->get = ll_get_adapter;
639 8 : generic_list->remove = ll_remove_adapter;
640 8 : generic_list->insert = ll_insert_adapter;
641 8 : generic_list->delete = ll_delete_adapter;
642 8 : generic_list->push_back = ll_push_back_adapter;
643 8 : generic_list->pop_back = ll_pop_back_adapter;
644 8 : generic_list->peek_back = ll_peek_back_adapter;
645 8 : generic_list->push_front = ll_push_front_adapter;
646 8 : generic_list->pop_front = ll_pop_front_adapter;
647 8 : generic_list->peek_front = ll_peek_front_adapter;
648 8 : generic_list->length = ll_length_adapter;
649 8 : generic_list->set = ll_set_adapter;
650 8 : generic_list->index_of = ll_index_of_adapter;
651 8 : }
652 :
653 8 : smb_list ll_create_list()
654 : {
655 8 : smb_ll *list = ll_create();
656 8 : return ll_cast_to_list(list);
657 : }
658 :
659 8 : smb_list ll_cast_to_list(smb_ll *list)
660 : {
661 : smb_list generic_list;
662 8 : generic_list.data = list;
663 :
664 8 : ll_fill_functions(&generic_list);
665 :
666 8 : return generic_list;
667 : }
|
