Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 1 | /* llist.c - Linked list functions |
Rob Landley | 15bdc11 | 2006-11-01 22:28:46 -0500 | [diff] [blame] | 2 | * |
| 3 | * Linked list structures have a next pointer as their first element. |
| 4 | */ |
| 5 | |
| 6 | #include "toys.h" |
| 7 | |
Rob Landley | e604d53 | 2014-05-21 06:57:43 -0500 | [diff] [blame] | 8 | // Callback function to free data pointer of double_list or arg_list |
| 9 | |
| 10 | void llist_free_arg(void *node) |
| 11 | { |
| 12 | struct arg_list *d = node; |
| 13 | |
| 14 | free(d->arg); |
| 15 | free(d); |
| 16 | } |
| 17 | |
| 18 | void llist_free_double(void *node) |
| 19 | { |
| 20 | struct double_list *d = node; |
| 21 | |
| 22 | free(d->data); |
| 23 | free(d); |
| 24 | } |
| 25 | |
Rob Landley | 9e2b6db | 2012-07-15 17:22:04 -0500 | [diff] [blame] | 26 | // Call a function (such as free()) on each element of a linked list. |
Rob Landley | e604d53 | 2014-05-21 06:57:43 -0500 | [diff] [blame] | 27 | void llist_traverse(void *list, void (*using)(void *node)) |
Rob Landley | 15bdc11 | 2006-11-01 22:28:46 -0500 | [diff] [blame] | 28 | { |
Rob Landley | fe91e68 | 2012-11-22 21:18:09 -0600 | [diff] [blame] | 29 | void *old = list; |
| 30 | |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 31 | while (list) { |
| 32 | void *pop = llist_pop(&list); |
| 33 | using(pop); |
Rob Landley | bdf037f | 2008-10-23 16:44:30 -0500 | [diff] [blame] | 34 | |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 35 | // End doubly linked list too. |
Rob Landley | fe91e68 | 2012-11-22 21:18:09 -0600 | [diff] [blame] | 36 | if (old == list) break; |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 37 | } |
Rob Landley | 15bdc11 | 2006-11-01 22:28:46 -0500 | [diff] [blame] | 38 | } |
Rob Landley | 0a04b3e | 2006-11-03 00:05:52 -0500 | [diff] [blame] | 39 | |
| 40 | // Return the first item from the list, advancing the list (which must be called |
| 41 | // as &list) |
| 42 | void *llist_pop(void *list) |
| 43 | { |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 44 | // I'd use a void ** for the argument, and even accept the typecast in all |
| 45 | // callers as documentation you need the &, except the stupid compiler |
| 46 | // would then scream about type-punned pointers. Screw it. |
| 47 | void **llist = (void **)list; |
| 48 | void **next = (void **)*llist; |
| 49 | *llist = *next; |
Rob Landley | 0a04b3e | 2006-11-03 00:05:52 -0500 | [diff] [blame] | 50 | |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 51 | return (void *)next; |
Rob Landley | 0a04b3e | 2006-11-03 00:05:52 -0500 | [diff] [blame] | 52 | } |
Rob Landley | 6ef04ef | 2008-01-20 17:34:53 -0600 | [diff] [blame] | 53 | |
Rob Landley | 5f57bcc | 2013-09-09 04:26:03 -0500 | [diff] [blame] | 54 | void *dlist_pop(void *list) |
| 55 | { |
| 56 | struct double_list **pdlist = (struct double_list **)list, *dlist = *pdlist; |
| 57 | |
Rob Landley | bb215e4 | 2013-09-09 05:26:52 -0500 | [diff] [blame] | 58 | if (dlist->next == dlist) *pdlist = 0; |
| 59 | else { |
| 60 | dlist->next->prev = dlist->prev; |
| 61 | dlist->prev->next = *pdlist = dlist->next; |
| 62 | } |
Rob Landley | 5f57bcc | 2013-09-09 04:26:03 -0500 | [diff] [blame] | 63 | |
| 64 | return dlist; |
| 65 | } |
| 66 | |
Rob Landley | 2c48247 | 2012-03-12 00:25:40 -0500 | [diff] [blame] | 67 | void dlist_add_nomalloc(struct double_list **list, struct double_list *new) |
| 68 | { |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 69 | if (*list) { |
| 70 | new->next = *list; |
| 71 | new->prev = (*list)->prev; |
| 72 | (*list)->prev->next = new; |
| 73 | (*list)->prev = new; |
| 74 | } else *list = new->next = new->prev = new; |
Rob Landley | 2c48247 | 2012-03-12 00:25:40 -0500 | [diff] [blame] | 75 | } |
| 76 | |
| 77 | |
Rob Landley | 53c7504 | 2010-01-05 10:43:36 -0600 | [diff] [blame] | 78 | // Add an entry to the end of a doubly linked list |
Rob Landley | bdf037f | 2008-10-23 16:44:30 -0500 | [diff] [blame] | 79 | struct double_list *dlist_add(struct double_list **list, char *data) |
Rob Landley | 6ef04ef | 2008-01-20 17:34:53 -0600 | [diff] [blame] | 80 | { |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 81 | struct double_list *new = xmalloc(sizeof(struct double_list)); |
Rob Landley | 6ef04ef | 2008-01-20 17:34:53 -0600 | [diff] [blame] | 82 | |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 83 | new->data = data; |
| 84 | dlist_add_nomalloc(list, new); |
Rob Landley | bdf037f | 2008-10-23 16:44:30 -0500 | [diff] [blame] | 85 | |
Rob Landley | 7aa651a | 2012-11-13 17:14:08 -0600 | [diff] [blame] | 86 | return new; |
Rob Landley | 6ef04ef | 2008-01-20 17:34:53 -0600 | [diff] [blame] | 87 | } |
Rob Landley | dc64025 | 2014-05-29 05:22:02 -0500 | [diff] [blame] | 88 | |
| 89 | // Terminate circular list for traversal in either direction. Returns end *. |
| 90 | void *dlist_terminate(void *list) |
| 91 | { |
| 92 | struct double_list *end = list; |
| 93 | |
| 94 | if (!list) return 0; |
| 95 | |
| 96 | end = end->prev; |
| 97 | end->next->prev = 0; |
| 98 | end->next = 0; |
| 99 | |
| 100 | return end; |
| 101 | } |