Mercurial > data_structures

view src/list.c @ 11:8b09943f1a70

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