Mercurial > hg > toybox
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 |
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 | 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 } |