1 Purpose: Create a generic linked list in C for fun. This list
2 is circular (for easy front/back access) and doubly linked.
3 Try to make C "object oriented".
4
5 Conventions:
6 * All identifiers generated by linked list begin with "List".
7 * The List "object" is actually an underlying pointer, this
8 means it needs initialization with a call to List_new(),
9 and destruction with a call to List_destroy().
10 * The iterator is NOT an underlying ptr, so it doesn't need
11 to be initialized or destroyed. However, it does need to
12 be set to the front or back of a list to do any good.
13 * By default, ListItem is a void* pointer.
14
15 Overview of Publicly Available Functions:
16 void List_new(List*);
17 void List_destroy(List,ListFreeFunc*);
18
19 List List_splice(List this, int offset, int length,
20 List other_list, ListCopyFunc* myCopy);
21
22 NOTE: this is a macro.
23 int List_length(List);
24
25 int List_push(List,ListItem);
26 int List_unshift(List,ListItem);
27
28 ListItem List_at(List, int);
29 ListItem List_pop(List);
30 ListItem List_shift(List);
31
32 ListIterator List_front(List);
33 ListIterator List_back(List);
34 ListItem ListIterator_item(ListIterator);
35 int ListIterator_next(ListIterator*);
36 int ListIterator_prev(ListIterator*);
37
38 NOTE: This is a macro.
39 int ListIterator_valid(ListIterator it);
40
41
42
43 Usage:
44 #include "List.h"
45
46 List list;
47 List_new(list);
48
49 // Add an element to the linked list to either the front (unshift)
50 // or the back of the list(push). Returns the number of elements
51 // in the list after the operation is performed.
52 length = List_push(list, (void*)data);
53 length = List_unshift(list, (void*)data);
54
55 // Remove an element from the linked list from either the front
56 // (shift) or the back of the list (pop). Returns the item
57 // removed from the list. If you simply don't want the item, be
58 // sure to free it (assuming you defined it on the heap).
59 data = List_pop(list);
60 data = List_shift(list);
61
62 // Access the n'th element of a list, if you want to iterate over
63 // a list, this is a poor way of doing that. This is 0 based.
64 data = List_at(list, n);
65
66 // Returns the number of items in a list.
67 length = List_length(list);
68
69 ////////////// Iteratoring over lists \\\\\\\\\\\\\\\
70 // NOTE: ListIterators do not need to be free'd.
71 // Create an iterator pointing at the front/back of a list:
72 ListIterator it = List_front(list);
73 ListIterator it = List_back(list);
74
75 // Access the current element, returns NULL if not currently pointing
76 // at an item (like if the list was empty).
77 data = ListIterator_item(it);
78
79 // Iterate forward (next), or backwards (prev), returns true if
80 // pointing at a valid item (like if the list is not empty).
81 isValid = ListIterator_next(it);
82 isValid = ListIterator_prev(it);
83
84 // This function removes the elements designated by offset and
85 // length from a list and replaces them with the elements of the
86 // other_list, if not NULL. This function returns the elements
87 // removed from the list. The list will grow or shrink as necessary.
88 // if length == -1, then everything from offset onward is removed.
89 //
90 // In order to make a copy of each element from other_list into list,
91 // there is an optional "copy constructor" which can be passed in.
92 // If this argument is NULL, only a bitwise copy of the item in the list
93 // is performed (so if ListItem is some sort of pointer, the items are
94 // not copied).
95 // SEE EXAMPLES BELOW!
96 spliced_out_list =
97 List_splice(list, offset, length,
98 other_list, (ListCopyFunc*)myCopy);
99
100 // If all your elements in the list have been created with "malloc",
101 // you will need to pass this function "free". If NULL is second parameter,
102 // no memory deallocation on the items being pointed at will be done.
103 // (all this assuming that ListItem is a void*, which is the default).
104 List_destroy(ll,(ListFreeFunc*)myItemFree);
105
106 EXAMPLES:
107 // Remove all elements from "index" 3 to the end (note that you need
108 // to destroy the returned list).
109 List_destroy( List_splice(list, 3, -1, NULL, NULL) );
110
111 // Grab and remove elements from "index" 1 to 4 (note that these are 0
112 // indexed numbers).
113 List one2four = List_splice(list, 1, 3, NULL, NULL);
114
115 // Remove last element from the list and copy all items from other_list
116 // into the end of list using the myCopy function to copy the items.
117 List_destroy( List_splice(list, -1, -1, other_list, myCopy) );
118
119 // Same thing:
120 List_destroy( List_splice(list, -1, 1, other_list, myCopy) );
121
122
123
124 --------------------------------------------------------------- List.h
125 /* Author: Brian Maher <maherb@cc.wwu.edu>
126 *
127 * License: LGPL - Lesser General Public License
128 * See: http://www.gnu.org/copyleft/lesser.html
129 * Quick License:
130 * -Don't claim that you created this code, please give me credit.
131 * -Any good ideas for improvement/fixes/etc, send to the above
132 * author with modifications to source code.
133 *
134 * $Revision$
135 * $Source$
136 */
137
138 #ifndef LIST_H_
139 #define LIST_H_
140
141 /* NOTE: change this if you are not going to use a void* type. (not tested)*/
142 #ifndef ListItem
143 #define ListItem void*
144 #endif /* ListItem */
145 #ifndef ListItemInvalid
146 #define ListItemInvalid NULL
147 #endif /* ListItemInvalid */
148
149 /* PRIVATE!! data structures: */
150 typedef struct ListNode_t {
151 ListItem data;
152 struct ListNode_t* next, * prev;
153 } ListNode_t;
154
155 typedef struct List_t {
156 ListNode_t* first;
157 int length;
158 } List_t;
159
160 typedef struct ListIterator_t {
161 ListNode_t* cur;
162 List_t* list;
163 } ListIterator_t;
164 /* /PRIVATE */
165
166 /* Typedefs: */
167 typedef void* ListCopyFunc(void*);
168 typedef void ListFreeFunc(ListItem);
169
170 /* Translate privately defined data structures into public data
171 structures. */
172 #define List List_t*
173 #define ListIterator ListIterator_t
174
175
176
177
178 /* THE LIST INTERFACE
179 *
180 * - Destruction/creation: new,destroy
181 * - Mutators: splice,push,unshift,shift,pop
182 * - Accessors: length, at
183 * - Iterators: back, front, next, prev.
184 * - Iterator access: item, valid
185 */
186
187 void List_new(List*);
188 void List_destroy(List,ListFreeFunc*);
189
190
191 List List_splice(List this, int offset, int length,
192 List other_list, ListCopyFunc* myCopy);
193 int List_push(List,ListItem);
194 int List_unshift(List,ListItem);
195 ListItem List_pop(List);
196 ListItem List_shift(List);
197
198
199 ListItem List_at(List, int);
200 /* NOTE that this is a macro */
201 #define List_length(ls) (ls->length)
202
203
204 ListIterator List_front(List);
205 ListIterator List_back(List);
206 ListItem ListIterator_item(ListIterator);
207 int ListIterator_next(ListIterator*);
208 int ListIterator_prev(ListIterator*);
209 /* NOTE: this is a macro */
210 #define ListIterator_valid(iter) ((iter).cur != NULL)
211
212
213
214
215 #ifdef _DEBUG
216 #include <stdio.h>
217 void List_print(List this, FILE* fd);
218 #endif /* _DEBUG */
219
220 #endif /* LIST_H_ */
221