Mercurial > LinkedList

view src/LinkedList.c @ 4:c9e6f5c0a9b2

find changesets by author, revision, files, or words in the commit message
Added copyright notices, COPYING and README files.
author Eris Caffee <discordia@eldalin.com>
date Fri, 22 Jul 2011 20:45:30 -0500
parents 34f1d2f54d37
children
line source
1 /*******************************************************************************
2 * LinkedList
3 *
4 * A simple doubly linked list class in C.
5 *
6 *******************************************************************************
7 *
8 * Copyright (C) 2010 Sarah Eris Horsley Caffee
9 *
10 * This is free software: you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation, either version 3 of the License, or
13 * (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program. If not, see <http://www.gnu.org/licenses/>.
22 *
23 *******************************************************************************
24 *
25 * Not thread safe.
26 *
27 ******************************************************************************/
28
29 #include "LinkedList.h"
30
31 #include <stdlib.h>
32
33 /*******************************************************************************
34 * "Private" inner class.
35 */
36 struct ll_node
37 {
38 ll_node * next;
39 ll_node * prev;
40 void * data;
41 };
42
43
44 /*******************************************************************************
45 * Insert an element at end of list.
46 * Sets curr and tail pointers to the new node.
47 * Returns data on success, NULL on error.
48 */
49 void * ll_push(LinkedList * this, void * data)
50 {
51 ll_node * new_node;
52
53 if ((!this) || (!data))
54 return NULL;
55
56 if (!(new_node = calloc(1, sizeof(ll_node))))
57 return NULL;
58
59 new_node->data = data;
60
61 if (!(this->Tail))
62 {
63 /* empty list */
64 this->Head = this->Tail = this->Curr = new_node;
65 }
66 else
67 {
68 new_node->prev = this->Tail;
69 this->Tail->next = new_node;
70 this->Tail = this->Curr = new_node;
71 }
72
73 this->Size++;
74 return this->Curr->data;
75 }
76
77
78 /*******************************************************************************
79 * Insert an element after the one pointed to by this->curr.
80 * Sets curr pointer to the new node (and tail if curr = tail when called).
81 * Returns data on success, NULL on error.
82 */
83 void * ll_insert(LinkedList * this, void * data)
84 {
85 ll_node * new_node;
86
87 if ((!this) || (!data))
88 return NULL;
89
90 /* If at end of list or list is empty or list has only one element */
91 if (this->Curr == this->Tail)
92 {
93 return ll_push(this, data);
94 }
95
96 if (!(new_node = calloc(1, sizeof(ll_node))))
97 return NULL;
98
99 new_node->data = data;
100 new_node->prev = this->Curr;
101 new_node->next = this->Curr->next;
102 this->Curr->next = new_node;
103 new_node->next->prev = new_node;
104 this->Curr = new_node;
105
106 this->Size++;
107 return this->Curr->data;
108 }
109
110
111 /*******************************************************************************
112 * Insert an element and make it the new head.
113 * Sets head and curr pointers to the new node.
114 * Returns data on success, NULL on error.
115 */
116 void * ll_insert_at_head(LinkedList * this, void * data)
117 {
118 ll_node * new_node;
119
120 if ((!this) || (!data))
121 return NULL;
122
123 if (!(new_node = calloc(1, sizeof(ll_node))))
124 return NULL;
125
126 new_node->data = data;
127 new_node->prev = NULL;
128 new_node->next = this->Head;;
129
130 if (this->Head)
131 this->Head->prev = new_node;
132 this->Head = this->Curr = new_node;
133
134 this->Size++;
135 return this->Curr->data;
136 }
137
138
139 /*******************************************************************************
140 * Remove the tail element from the list.
141 * Sets curr to tail.
142 * Return data, or NULL if the list is empty.
143 */
144 void * ll_pop(LinkedList * this)
145 {
146 void * data;
147 ll_node * tmp;
148
149 if (!this)
150 return NULL;
151
152 if (!(this->Tail))
153 return NULL;
154
155 tmp = this->Tail;
156 data = this->Tail->data;
157
158 if (!(this->Tail->prev))
159 {
160 /* Only element in list */
161 this->Head = this->Tail = this->Curr = NULL;
162 }
163 else
164 {
165 this->Tail->prev->next = NULL;
166 this->Tail = this->Curr = this->Tail->prev;
167 }
168
169 free(tmp);
170 this->Size--;
171
172 return data;
173 }
174
175
176 /*******************************************************************************
177 * Delete the element pointed to by this->curr.
178 * A pointer to the stored data is returned, or NULL is no list or an empty list
179 * is specified. It must be freed by the caller.
180 */
181 void * ll_remove(LinkedList * this)
182 {
183 void * data;
184 ll_node * tmp;
185
186 if (!this)
187 return NULL;
188
189 if (this->Curr == this->Tail)
190 return ll_pop(this);
191
192 tmp = this->Curr;
193 data = this->Curr->data;
194
195 if (this->Curr == this->Head)
196 {
197 this->Head->next->prev = NULL;
198 this->Head = this->Curr = this->Head->next;
199 }
200 else
201 {
202 this->Curr->prev->next = this->Curr->next;
203 this->Curr->next->prev = this->Curr->prev;
204 }
205
206 free(tmp);
207 this->Size--;
208
209 return data;
210 }
211
212
213 /*******************************************************************************
214 * Return the size of the list, or -1 is list is null.
215 */
216 int ll_size(LinkedList * this)
217 {
218 if (!this) return -1;
219
220 return this->Size;
221 }
222
223
224 /*******************************************************************************
225 * Select the first element in the list if there is one.
226 * Return data pointer of new current element, or NULL is list is empty.
227 */
228 void * ll_head(LinkedList * this)
229 {
230 if (!this) return NULL;
231
232 this->Curr = this->Head;
233
234 if (this->Curr)
235 return this->Curr->data;
236 else
237 return NULL;
238 }
239
240
241 /*******************************************************************************
242 * Select the last element in the list if there is one.
243 * Return data pointer of new current element, or NULL is list is empty.
244 */
245 void * ll_tail(LinkedList * this)
246 {
247 if (!this) return NULL;
248
249 this->Curr = this->Tail;
250
251 if (this->Curr)
252 return this->Curr->data;
253 else
254 return NULL;
255 }
256
257
258 /*******************************************************************************
259 * Return NULL if the list is empty or we are already at the tail, otherwise
260 * set Curr to the next element and return its data pointer.
261 */
262 void * ll_next(LinkedList * this)
263 {
264 if (!this) return NULL;
265
266 if (this->Curr && this->Curr->next)
267 {
268 this->Curr = this->Curr->next;
269 return this->Curr->data;
270 }
271 else
272 return NULL;
273
274 }
275
276
277 /*******************************************************************************
278 * Return NULL if the list is empty or we are already at the head, otherwise
279 * set Curr to the prev element and return its data pointer.
280 */
281 void * ll_prev(LinkedList * this)
282 {
283 if (!this) return NULL;
284
285 if (this->Curr && this->Curr->prev)
286 {
287 this->Curr = this->Curr->prev;
288 return this->Curr->data;
289 }
290 else
291 return NULL;
292 }
293
294
295 /*******************************************************************************
296 * Return the data pointer of the current node, or NULL is list is empty.
297 */
298 void * ll_data(LinkedList * this)
299 {
300 if (!this) return NULL;
301
302 if (this->Curr)
303 return this->Curr->data;
304 else
305 return NULL;
306 }
307
308
309 /*******************************************************************************
310 * Constuctor. Call this when creating a new list.
311 */
312 void ll_init(LinkedList * this)
313 {
314 if (this)
315 {
316 this->push = ll_push;
317 this->pop = ll_pop;
318 this->insert = ll_insert;
319 this->remove = ll_remove;
320 this->insert_at_head = ll_insert_at_head;
321 this->size = ll_size;
322 this->head = ll_head;
323 this->tail = ll_tail;
324 this->next = ll_next;
325 this->prev = ll_prev;
326 this->data = ll_data;
327
328 this->Head = this->Tail = this->Curr = NULL;
329 this->Size = 0;
330 }
331 }
332
333