Mercurial > data_structures

view src/list.c @ 10:68f85ffc6029

find changesets by author, revision, files, or words in the commit message
Finished rbtree. Reworked the iterators in list. Minor tweaks to others.
author Eris Caffee <discordia@eldalin.com>
date Fri, 28 Sep 2012 18:24:53 -0500
parents abdba37f67a2
children 8b09943f1a70
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 return it->curr;
229 }
230
231 ////////////////////////////////////////////////////////////////////////////////
232 // Move the iterator to the previous element in the list.
233 struct list_iterator *
234 list_prev(struct list_iterator * it)
235 {
236 if (NULL == it)
237 return NULL;
238
239 it->curr = it->curr->prev;
240 return it->curr;
241 }
242
243 ////////////////////////////////////////////////////////////////////////////////
244 // Remove the current element pointed to by the iterator.
245 // Returns the data element that was removed so the caller can free it.
246 void *
247 list_remove(struct list_iterator * it)
248 {
249 if ( (NULL == it) || (NULL == it->curr) )
250 return NULL;
251
252 if (it->curr->prev)
253 it->curr->prev->next = it->curr->next;
254
255 if (it->curr->next)
256 it->curr->next->prev = it->curr->prev;
257
258 struct list_node * temp = it->curr;
259 void * elem = it->curr->data;
260
261 it->curr = it->curr->next;
262 free(temp);
263
264 it->l->size--;
265 if (0 == it->l->size)
266 it->l->tail = it->l->head = NULL;
267
268 return elem;
269 }
270
271 ////////////////////////////////////////////////////////////////////////////////
272 // Return the value of the element pointed to by the iterator.
273 void *
274 list_value(struct list_iterator * it)
275 {
276 if ( (NULL == it) || (NULL == it->curr) )
277 return NULL;
278 return it->curr->data;
279 }
280
281 ////////////////////////////////////////////////////////////////////////////////
282 // Insert a new element after the one pointed to by the iterator.
283 // The iterator is then set to point to this new element.
284 struct list_iterator *
285 list_insert_after(struct list_iterator * it, void * elem)
286 {
287 if ( (NULL == it) || (NULL == elem) || (NULL == it->curr) )
288 return NULL;
289
290 struct list_node * new = malloc(sizeof(struct list_node));
291 if (NULL == new)
292 return NULL;
293
294 new->data = elem;
295 new->prev = it->curr;
296 if (it->curr->next)
297 it->curr->next->prev = new;
298 new->next = it->curr->next;
299 it->curr->next = new;
300
301 it->curr = new;
302
303 it->l->size++;
304 if (NULL == it->curr->next)
305 it->l->tail = it->curr;
306
307 return it;
308 }
309
310 ////////////////////////////////////////////////////////////////////////////////
311 // Insert a new element before the one pointed to by the iterator.
312 // The iterator is then set to point to this new element.
313 struct list_iterator *
314 list_insert_before(struct list_iterator * it, void * elem)
315 {
316 if ( (NULL == it) || (NULL == elem) || (NULL == it->curr) )
317 return NULL;
318
319 struct list_node * new = malloc(sizeof(struct list_node));
320 if (NULL == new)
321 return NULL;
322
323 new->data = elem;
324 new->next = it->curr;
325 if (it->curr->prev)
326 it->curr->prev->next = new;
327 new->prev = it->curr->prev;
328 it->curr->prev = new;
329
330 it->curr = new;
331
332 it->l->size++;
333 if (NULL == it->curr->prev)
334 it->l->head = it->curr;
335
336 return it;
337 }
338