Mercurial > data_structures

view src/list.c @ 9:abdba37f67a2

find changesets by author, revision, files, or words in the commit message
Red-black tree in progress. Linked list needs iterators redone, also in progress. Sleepy.
author Eris Caffee <discordia@eldalin.com>
date Fri, 28 Sep 2012 03:08:25 -0500
parents e117c4d93602
children 68f85ffc6029
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 // Intialize an iterator to point to the first element of the list
181 struct list_iterator *
182 list_begin(struct list * l)
183 {
184 if ( (NULL == l) || (NULL == l->head) )
185 return NULL;
186
187 struct list_iterator * it = malloc(sizeof(struct list_iterator));
188 if (NULL == it)
189 return NULL;
190
191 it->l = l;
192 it->curr = l->head;
193
194 return it;
195 }
196
197 ////////////////////////////////////////////////////////////////////////////////
198 // Intialize an iterator to point to the last element of the list
199 struct list_iterator *
200 list_end(struct list * l)
201 {
202 if ( (NULL == l) || (NULL == l->head) )
203 return NULL;
204
205 struct list_iterator * it = malloc(sizeof(struct list_iterator));
206 if (NULL == it)
207 return NULL;
208
209 it->l = l;
210 it->curr = l->tail;
211
212 return it;
213 }
214
215 ////////////////////////////////////////////////////////////////////////////////
216 // Move the iterator to the next element in the list, returning its value.
217 void *
218 list_next(struct list_iterator * lit)
219 {
220 if (NULL == lit)
221 return NULL;
222
223 lit->curr = lit->curr->next;
224
225 if (lit->curr)
226 return lit->curr->data;
227
228 return NULL;
229 }
230
231 ////////////////////////////////////////////////////////////////////////////////
232 // Move the iterator to the previous element in the list, returning its value.
233 void *
234 list_prev(struct list_iterator * lit)
235 {
236 if (NULL == lit)
237 return NULL;
238
239 lit->curr = lit->curr->prev;
240
241 if (lit->curr)
242 return lit->curr->data;
243
244 return NULL;
245 }
246
247 ////////////////////////////////////////////////////////////////////////////////
248 // Remove the current element pointed to by the iterator, returning that elements value.
249 void *
250 list_erase(struct list_iterator * lit)
251 {
252 if ( (NULL == lit) || (NULL == lit->curr) )
253 return NULL;
254
255 if (lit->curr->prev)
256 lit->curr->prev->next = lit->curr->next;
257
258 if (lit->curr->next)
259 lit->curr->next->prev = lit->curr->prev;
260
261 struct list_node * temp = lit->curr;
262 void * elem = lit->curr->data;
263
264 lit->curr = lit->curr->next;
265 free(temp);
266
267 lit->l->size--;
268 if (0 == lit->l->size)
269 lit->l->tail = lit->l->head = NULL;
270
271 return elem;
272 }
273
274 ////////////////////////////////////////////////////////////////////////////////
275 // Insert a new element after the one pointed to by the iterator.
276 // The iterator is then set to point to this new element.
277 // Return the new elements value.
278 void *
279 list_insert_after(struct list_iterator * lit, void * elem)
280 {
281 if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
282 return NULL;
283
284 struct list_node * new = malloc(sizeof(struct list_node));
285 if (NULL == new)
286 return NULL;
287
288 new->data = elem;
289 new->prev = lit->curr;
290 if (lit->curr->next)
291 lit->curr->next->prev = new;
292 new->next = lit->curr->next;
293 lit->curr->next = new;
294
295 lit->curr = new;
296
297 lit->l->size++;
298 if (NULL == lit->curr->next)
299 lit->l->tail = lit->curr;
300
301 return elem;
302 }
303
304 ////////////////////////////////////////////////////////////////////////////////
305 // Insert a new element before the one pointed to by the iterator.
306 // The iterator is then set to point to this new element.
307 // Return the new elements value.
308 void *
309 list_insert_before(struct list_iterator * lit, void * elem)
310 {
311 if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
312 return NULL;
313
314 struct list_node * new = malloc(sizeof(struct list_node));
315 if (NULL == new)
316 return NULL;
317
318 new->data = elem;
319 new->next = lit->curr;
320 if (lit->curr->prev)
321 lit->curr->prev->next = new;
322 new->prev = lit->curr->prev;
323 lit->curr->prev = new;
324
325 lit->curr = new;
326
327 lit->l->size++;
328 if (NULL == lit->curr->prev)
329 lit->l->head = lit->curr;
330
331 return elem;
332 }
333
334 ////////////////////////////////////////////////////////////////////////////////
335 // Return the value of the element pointed to by the iterator.
336 void *
337 list_value(struct list_iterator * lit)
338 {
339 if ( (NULL == lit) || (NULL == lit->curr) )
340 return NULL;
341 return lit->curr->data;
342 }
343