annotate lib/llist.c @ 1776:7bf68329eb3b draft default tip

Repository switched to git at https://github.com/landley/toybox
author Rob Landley <rob@landley.net>
date Thu, 09 Apr 2015 02:28:32 -0500
parents 4d898affda0c
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
1 /* llist.c - Linked list functions
15
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
2 *
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
3 * Linked list structures have a next pointer as their first element.
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
4 */
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
5
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
6 #include "toys.h"
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
7
1295
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
8 // Callback function to free data pointer of double_list or arg_list
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
9
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
10 void llist_free_arg(void *node)
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
11 {
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
12 struct arg_list *d = node;
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
13
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
14 free(d->arg);
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
15 free(d);
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
16 }
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
17
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
18 void llist_free_double(void *node)
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
19 {
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
20 struct double_list *d = node;
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
21
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
22 free(d->data);
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
23 free(d);
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
24 }
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
25
624
1e8b9acdafeb Genericize llist code a bit: rename llist_free() to llist_traverse(), and no longer accept NULL as a synonym for free.
Rob Landley <rob@landley.net>
parents: 540
diff changeset
26 // Call a function (such as free()) on each element of a linked list.
1295
114ec0ab161c Add free functions for predefined llist types.
Rob Landley <rob@landley.net>
parents: 1060
diff changeset
27 void llist_traverse(void *list, void (*using)(void *node))
15
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
28 {
708
50d759f8b371 Remove readlink -m for being poorly defined ("readlink -m /dev/null/and/more" answers what question, exactly?), rewrite xabspath() to work right and not depend on realpath, fix subtle longstanding bug in llist_traverse().
Rob Landley <rob@landley.net>
parents: 694
diff changeset
29 void *old = list;
50d759f8b371 Remove readlink -m for being poorly defined ("readlink -m /dev/null/and/more" answers what question, exactly?), rewrite xabspath() to work right and not depend on realpath, fix subtle longstanding bug in llist_traverse().
Rob Landley <rob@landley.net>
parents: 694
diff changeset
30
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
31 while (list) {
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
32 void *pop = llist_pop(&list);
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
33 using(pop);
315
aaac01796688 Upgrade patch to detect hunks that start after a false start.
Rob Landley <rob@landley.net>
parents: 238
diff changeset
34
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
35 // End doubly linked list too.
708
50d759f8b371 Remove readlink -m for being poorly defined ("readlink -m /dev/null/and/more" answers what question, exactly?), rewrite xabspath() to work right and not depend on realpath, fix subtle longstanding bug in llist_traverse().
Rob Landley <rob@landley.net>
parents: 694
diff changeset
36 if (old == list) break;
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
37 }
15
2a56fdc40035 Linked list functions, forgot to add this to the repository.
Rob Landley <rob@landley.net>
parents:
diff changeset
38 }
20
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
39
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
40 // Return the first item from the list, advancing the list (which must be called
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
41 // as &list)
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
42 void *llist_pop(void *list)
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
43 {
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
44 // I'd use a void ** for the argument, and even accept the typecast in all
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
45 // callers as documentation you need the &, except the stupid compiler
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
46 // would then scream about type-punned pointers. Screw it.
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
47 void **llist = (void **)list;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
48 void **next = (void **)*llist;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
49 *llist = *next;
20
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
50
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
51 return (void *)next;
20
3981c96f9285 Implement which. Add hello world to menuconfig. Wrap the various applet main
Rob Landley <rob@landley.net>
parents: 15
diff changeset
52 }
238
630b2e12db16 Move dlist_add() to lib/llist.c
Rob Landley <rob@landley.net>
parents: 20
diff changeset
53
1059
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
54 void *dlist_pop(void *list)
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
55 {
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
56 struct double_list **pdlist = (struct double_list **)list, *dlist = *pdlist;
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
57
1060
c2663b7eca78 Adjust patch to use dlist_pop()
Rob Landley <rob@landley.net>
parents: 1059
diff changeset
58 if (dlist->next == dlist) *pdlist = 0;
c2663b7eca78 Adjust patch to use dlist_pop()
Rob Landley <rob@landley.net>
parents: 1059
diff changeset
59 else {
c2663b7eca78 Adjust patch to use dlist_pop()
Rob Landley <rob@landley.net>
parents: 1059
diff changeset
60 dlist->next->prev = dlist->prev;
c2663b7eca78 Adjust patch to use dlist_pop()
Rob Landley <rob@landley.net>
parents: 1059
diff changeset
61 dlist->prev->next = *pdlist = dlist->next;
c2663b7eca78 Adjust patch to use dlist_pop()
Rob Landley <rob@landley.net>
parents: 1059
diff changeset
62 }
1059
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
63
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
64 return dlist;
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
65 }
ef72a16f4b3a Redo tail closer to the original design. Add more tests for large data sets. (Still no -f support yet.)
Rob Landley <rob@landley.net>
parents: 708
diff changeset
66
540
c2f39708a4c4 Redo tail to use optargs and optionally support lseek. Add support to optargs and llist.c, plus add a test suite entry. Still no -f support though.
Rob Landley <rob@landley.net>
parents: 366
diff changeset
67 void dlist_add_nomalloc(struct double_list **list, struct double_list *new)
c2f39708a4c4 Redo tail to use optargs and optionally support lseek. Add support to optargs and llist.c, plus add a test suite entry. Still no -f support though.
Rob Landley <rob@landley.net>
parents: 366
diff changeset
68 {
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
69 if (*list) {
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
70 new->next = *list;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
71 new->prev = (*list)->prev;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
72 (*list)->prev->next = new;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
73 (*list)->prev = new;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
74 } else *list = new->next = new->prev = new;
540
c2f39708a4c4 Redo tail to use optargs and optionally support lseek. Add support to optargs and llist.c, plus add a test suite entry. Still no -f support though.
Rob Landley <rob@landley.net>
parents: 366
diff changeset
75 }
c2f39708a4c4 Redo tail to use optargs and optionally support lseek. Add support to optargs and llist.c, plus add a test suite entry. Still no -f support though.
Rob Landley <rob@landley.net>
parents: 366
diff changeset
76
c2f39708a4c4 Redo tail to use optargs and optionally support lseek. Add support to optargs and llist.c, plus add a test suite entry. Still no -f support though.
Rob Landley <rob@landley.net>
parents: 366
diff changeset
77
366
f1e9da78c5dd Typo fix in comment.
Rob Landley <rob@landley.net>
parents: 315
diff changeset
78 // Add an entry to the end of a doubly linked list
315
aaac01796688 Upgrade patch to detect hunks that start after a false start.
Rob Landley <rob@landley.net>
parents: 238
diff changeset
79 struct double_list *dlist_add(struct double_list **list, char *data)
238
630b2e12db16 Move dlist_add() to lib/llist.c
Rob Landley <rob@landley.net>
parents: 20
diff changeset
80 {
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
81 struct double_list *new = xmalloc(sizeof(struct double_list));
238
630b2e12db16 Move dlist_add() to lib/llist.c
Rob Landley <rob@landley.net>
parents: 20
diff changeset
82
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
83 new->data = data;
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
84 dlist_add_nomalloc(list, new);
315
aaac01796688 Upgrade patch to detect hunks that start after a false start.
Rob Landley <rob@landley.net>
parents: 238
diff changeset
85
694
786841fdb1e0 Reindent to two spaces per level. Remove vi: directives that haven't worked right in years (ubuntu broke its' vim implementation). Remove trailing spaces. Add/remove blank lines. Re-wordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents: 624
diff changeset
86 return new;
238
630b2e12db16 Move dlist_add() to lib/llist.c
Rob Landley <rob@landley.net>
parents: 20
diff changeset
87 }
1321
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
88
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
89 // Terminate circular list for traversal in either direction. Returns end *.
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
90 void *dlist_terminate(void *list)
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
91 {
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
92 struct double_list *end = list;
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
93
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
94 if (!list) return 0;
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
95
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
96 end = end->prev;
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
97 end->next->prev = 0;
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
98 end->next = 0;
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
99
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
100 return end;
4d898affda0c Switch mtab_list to doubly linked so we can traverse in either order. Convert umount and df. Add dlist_terminate() to break lists for traversal in either direction.
Rob Landley <rob@landley.net>
parents: 1295
diff changeset
101 }