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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap in places. Update documentation with new coding style.
Rob Landley <rob@landley.net>
parents:
624
diff
changeset

46 // would then scream about typepunned 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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. Rewordwrap 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 } 