Mercurial > data_structures

view src/list.c @ 5:e117c4d93602

find changesets by author, revision, files, or words in the commit message
Added list - a doubly linked list. Fixed memory leaks in some of the test drivers.
author Eris Caffee <discordia@eldalin.com>
date Fri, 21 Sep 2012 18:42:49 -0500
parents
children abdba37f67a2
line source
1 #include <stdlib.h>
2
3 #include "list.h"
4
5
6 ////////////////////////////////////////////////////////////////////////////////
7 // Allocates new list and returns poitner to it.
8 struct list *
9 list_new(void)
10 {
11 struct list * l = malloc(sizeof(struct list));
12 if (NULL == l)
13 return NULL;
14
15 l->size = 0;
16 l->head = l->tail = NULL;
17
18 return l;
19 }
20
21 ////////////////////////////////////////////////////////////////////////////////
22 // Deletes list. Does not delete data elements. To avoid memory leaks,
23 // Only call this on an empty list.
24 void
25 list_delete(struct list * l)
26 {
27 if (NULL != l)
28 {
29 // This will cause memory leaks, but we don't have destructors.
30 // Hopefuly the caller has already emptied the list.
31 struct list_node * prev;
32 struct list_node * curr = l->tail;
33 while (curr)
34 {
35 prev = curr->prev;
36 free(curr);
37 curr = prev;
38 }
39 free(l);
40 }
41 }
42
43 ////////////////////////////////////////////////////////////////////////////////
44 // Returns the numb er of elements in the list.
45 size_t
46 list_size(struct list * l)
47 {
48 if (NULL == l)
49 return 0;
50 return l->size;
51 }
52
53 ////////////////////////////////////////////////////////////////////////////////
54 // Add an element to the end of the list.
55 void *
56 list_push_back(struct list * l, void * elem)
57 {
58 if ( (NULL == l) || (NULL == elem) )
59 return NULL;
60
61 struct list_node * new = malloc(sizeof(struct list_node));
62 if (NULL == new)
63 return NULL;
64
65 new->data = elem;
66 new->prev = new->next = NULL;
67
68 if (NULL == l->tail)
69 {
70 l->head = l->tail = new;
71 }
72 else
73 {
74 new->prev = l->tail;
75 l->tail->next = new;
76 l->tail = new;
77 }
78
79 l->size++;
80
81 return elem;
82 }
83
84 ////////////////////////////////////////////////////////////////////////////////
85 // Remove an element from the back of the list.
86 void *
87 list_pop_back(struct list * l)
88 {
89 if ( (NULL == l) || (NULL == l->tail) )
90 return NULL;
91
92 void * t = l->tail->data;
93
94 struct list_node * prev = l->tail->prev;
95 if (prev)
96 prev->next = NULL;
97 free(l->tail);
98 l->tail = prev;
99 l->size--;
100 if (0 == l->size)
101 l->head = NULL;
102
103 return t;
104 }
105
106 ////////////////////////////////////////////////////////////////////////////////
107 // Add an element to the front of the list.
108 void *
109 list_push_front(struct list * l, void * elem)
110 {
111 if ( (NULL == l) || (NULL == elem) )
112 return NULL;
113
114 struct list_node * new = malloc(sizeof(struct list_node));
115 if (NULL == new)
116 return NULL;
117
118 new->data = elem;
119 new->prev = new->next = NULL;
120
121 if (NULL == l->head)
122 {
123 l->head = l->tail = new;
124 }
125 else
126 {
127 new->next = l->head;
128 l->head->prev = new;
129 l->head = new;
130 }
131
132 l->size++;
133
134 return elem;
135 }
136
137 ////////////////////////////////////////////////////////////////////////////////
138 // Remove and element from the front of the list.
139 void *
140 list_pop_front(struct list * l)
141 {
142 if ( (NULL == l) || (NULL == l->head) )
143 return NULL;
144
145 void * t = l->head->data;
146
147 struct list_node * next = l->head->next;
148 if (next)
149 next->prev = NULL;
150 free(l->head);
151 l->head = next;
152 l->size--;
153
154 if (0 == l->size)
155 l->tail = NULL;
156
157 return t;
158 }
159
160 ////////////////////////////////////////////////////////////////////////////////
161 // Intialize an iterator to point to the first element of the list
162 // Returns the elements value.
163 void *
164 list_begin(struct list * l, struct list_iterator * lit)
165 {
166 if ( (NULL == l) || (NULL == lit) )
167 return NULL;
168
169 lit->l = l;
170 lit->curr = l->head;
171
172 if (lit->curr)
173 return lit->curr->data;
174
175 return NULL;
176 }
177
178 ////////////////////////////////////////////////////////////////////////////////
179 // Intialize an iterator to point to the last element of the list
180 // Returns the elements value.
181 void *
182 list_end(struct list * l, struct list_iterator * lit)
183 {
184 if ( (NULL == l) || (NULL == lit) )
185 return NULL;
186
187 lit->l = l;
188 lit->curr = l->tail;
189
190 if (lit->curr)
191 return lit->curr->data;
192
193 return NULL;
194 }
195
196 ////////////////////////////////////////////////////////////////////////////////
197 // Move the iterator to the next element in the list, returning its value.
198 void *
199 list_next(struct list_iterator * lit)
200 {
201 if (NULL == lit)
202 return NULL;
203
204 lit->curr = lit->curr->next;
205
206 if (lit->curr)
207 return lit->curr->data;
208
209 return NULL;
210 }
211
212 ////////////////////////////////////////////////////////////////////////////////
213 // Move the iterator to the previous element in the list, returning its value.
214 void *
215 list_prev(struct list_iterator * lit)
216 {
217 if (NULL == lit)
218 return NULL;
219
220 lit->curr = lit->curr->prev;
221
222 if (lit->curr)
223 return lit->curr->data;
224
225 return NULL;
226 }
227
228 ////////////////////////////////////////////////////////////////////////////////
229 // Remove the current element pointed to by the iterator, returning that elements value.
230 void *
231 list_erase(struct list_iterator * lit)
232 {
233 if ( (NULL == lit) || (NULL == lit->curr) )
234 return NULL;
235
236 if (lit->curr->prev)
237 lit->curr->prev->next = lit->curr->next;
238
239 if (lit->curr->next)
240 lit->curr->next->prev = lit->curr->prev;
241
242 struct list_node * temp = lit->curr;
243 void * elem = lit->curr->data;
244
245 lit->curr = lit->curr->next;
246 free(temp);
247
248 lit->l->size--;
249 if (0 == lit->l->size)
250 lit->l->tail = lit->l->head = NULL;
251
252 return elem;
253 }
254
255 ////////////////////////////////////////////////////////////////////////////////
256 // Insert a new element after the one pointed to by the iterator.
257 // The iterator is then set to point to this new element.
258 // Return the new elements value.
259 void *
260 list_insert_after(struct list_iterator * lit, void * elem)
261 {
262 if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
263 return NULL;
264
265 struct list_node * new = malloc(sizeof(struct list_node));
266 if (NULL == new)
267 return NULL;
268
269 new->data = elem;
270 new->prev = lit->curr;
271 if (lit->curr->next)
272 lit->curr->next->prev = new;
273 new->next = lit->curr->next;
274 lit->curr->next = new;
275
276 lit->curr = new;
277
278 lit->l->size++;
279 if (NULL == lit->curr->next)
280 lit->l->tail = lit->curr;
281
282 return elem;
283 }
284
285 ////////////////////////////////////////////////////////////////////////////////
286 // Insert a new element before the one pointed to by the iterator.
287 // The iterator is then set to point to this new element.
288 // Return the new elements value.
289 void *
290 list_insert_before(struct list_iterator * lit, void * elem)
291 {
292 if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
293 return NULL;
294
295 struct list_node * new = malloc(sizeof(struct list_node));
296 if (NULL == new)
297 return NULL;
298
299 new->data = elem;
300 new->next = lit->curr;
301 if (lit->curr->prev)
302 lit->curr->prev->next = new;
303 new->prev = lit->curr->prev;
304 lit->curr->prev = new;
305
306 lit->curr = new;
307
308 lit->l->size++;
309 if (NULL == lit->curr->prev)
310 lit->l->head = lit->curr;
311
312 return elem;
313 }
314
315 ////////////////////////////////////////////////////////////////////////////////
316 // Return the value of the element pointed to by the iterator.
317 void *
318 list_value(struct list_iterator * lit)
319 {
320 if ( (NULL == lit) || (NULL == lit->curr) )
321 return NULL;
322 return lit->curr->data;
323 }
324