Mercurial > almixer_isolated

comparison LinkedList.h @ 17:d58eb38c771b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Needed new Front and Back (non-popping) functions for LinkedList.
author Eric Wing <ewing . public |-at-| gmail . com>
date Sat, 06 Nov 2010 04:00:44 -0700
parents 1c27a52c5b15
children 7877c2e18768
comparison
equal deleted inserted replaced
16:038baa026db3 17:d58eb38c771b
1 /* 1 #include "LinkedList.h"
2 LinkedList 2 #include <stddef.h> /* for NULL */
3 Copyright (C) 2010 Eric Wing <ewing . public @ playcontrol.net> 3 #include <stdlib.h> /* for malloc/free */
4 4 #include <stdio.h> /* for debugging */
5 This library is free software; you can redistribute it and/or 5
6 modify it under the terms of the GNU Library General Public 6 struct LinkedListNode
7 License as published by the Free Software Foundation; either 7 {
8 version 2 of the License, or (at your option) any later version. 8 LinkedListNode* nextNode;
9 9 LinkedListNode* previousNode;
10 This library is distributed in the hope that it will be useful, 10 void* dataPtr;
11 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 };
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12
13 Library General Public License for more details. 13 struct LinkedList
14 14 {
15 You should have received a copy of the GNU Library General Public 15 size_t currentSize;
16 License along with this library; if not, write to the Free 16 LinkedListNode* headPtr;
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17 LinkedListNode* tailPtr;
18 */ 18 };
19 19
20 /* I'm so sick of constantly rewriting linked lists in C. 20
21 So here's some initial work to write a very simple reusable implementation. 21 LinkedListNode* LinkedListNode_Create()
22 The API could use a lot more functions, but I'll add them as I need them. 22 {
23 */ 23 LinkedListNode* list_node;
24 24 list_node = (LinkedListNode*)calloc(1, sizeof(LinkedListNode));
25 #ifndef C_LINKED_LIST_H 25 if(NULL == list_node)
26 #define C_LINKED_LIST_H 26 {
27 27 /* Very bad, but not sure what to do here. */
28 /* Set up for C function definitions, even when using C++ */ 28 return NULL;
29 #ifdef __cplusplus 29 }
30 extern "C" { 30
31 #endif 31 return list_node;
32 32 }
33 #include <stddef.h> 33
34 34
35 typedef struct LinkedListNode LinkedListNode; 35 void LinkedListNode_Free(LinkedListNode* list_node)
36 typedef struct LinkedList LinkedList; 36 {
37 37 if(NULL == list_node)
38 LinkedList* LinkedList_Create(); 38 {
39 39 return;
40 void LinkedList_Free(LinkedList* linked_list); 40 }
41 41 free(list_node);
42 void* LinkedList_Front(LinkedList* linked_list); 42 }
43 void* LinkedList_Back(LinkedList* linked_list); 43
44 44
45 unsigned int LinkedList_PushFront(LinkedList* linked_list, void* new_item); 45 LinkedList* LinkedList_Create()
46 46 {
47 unsigned int LinkedList_PushBack(LinkedList* linked_list, void* new_item); 47 LinkedList* linked_list;
48 48 linked_list = (LinkedList*)calloc(1, sizeof(LinkedList));
49 void* LinkedList_PopFront(LinkedList* linked_list); 49 if(NULL == linked_list)
50 50 {
51 void* LinkedList_PopBack(LinkedList* linked_list); 51 /* Very bad, but not sure what to do here. */
52 52 return NULL;
53 size_t LinkedList_Size(LinkedList* linked_list); 53 }
54 54
55 void LinkedList_Clear(LinkedList* linked_list); 55 return linked_list;
56 56 }
57 void* LinkedListNode_GetData(LinkedListNode* list_node); 57
58 58 void LinkedList_Free(LinkedList* linked_list)
59 LinkedListNode* LinkedList_Find(LinkedList* linked_list, void* the_data, LinkedListNode* start_node); 59 {
60 60 /* Both functions check for NULL */
61 unsigned int LinkedList_Remove(LinkedList* linked_list, LinkedListNode* list_node); 61 LinkedList_Clear(linked_list);
62 62 free(linked_list);
63 /* Ends C function definitions when using C++ */ 63 }
64 #ifdef __cplusplus 64
65 } 65
66 #endif 66 /**
67 67 * Returns 1 if successful, 0 if failure.
68 #endif /* C_LINKED_LIST_H */ 68 */
69 69 unsigned int LinkedList_PushFront(LinkedList* linked_list, void* new_item)
70 {
71 LinkedListNode* new_node;
72
73 if(NULL == linked_list)
74 {
75 return 0;
76 }
77
78 new_node = LinkedListNode_Create();
79 if(NULL == new_node)
80 {
81 return 0;
82 }
83
84 new_node->dataPtr = new_item;
85
86 if(0 == linked_list->currentSize)
87 {
88 linked_list->tailPtr = new_node;
89 }
90 else
91 {
92 LinkedListNode* head_node = linked_list->headPtr;
93 new_node->nextNode = head_node;
94 head_node->previousNode = new_node;
95 }
96
97 linked_list->headPtr = new_node;
98 linked_list->currentSize++;
99 return 1;
100 }
101
102 unsigned int LinkedList_PushBack(LinkedList* linked_list, void* new_item)
103 {
104 LinkedListNode* new_node;
105
106 if(NULL == linked_list)
107 {
108 return 0;
109 }
110
111 new_node = LinkedListNode_Create();
112 if(NULL == new_node)
113 {
114 return 0;
115 }
116
117 new_node->dataPtr = new_item;
118
119 if(0 == linked_list->currentSize)
120 {
121 linked_list->headPtr = new_node;
122 }
123 else
124 {
125 LinkedListNode* tail_node = linked_list->tailPtr;
126 new_node->previousNode = tail_node;
127 tail_node->nextNode = new_node;
128 }
129
130 linked_list->tailPtr = new_node;
131 linked_list->currentSize++;
132 return 1;
133
134 }
135
136 void* LinkedList_PopFront(LinkedList* linked_list)
137 {
138 LinkedListNode* head_node;
139 void* return_data;
140
141 if(NULL == linked_list)
142 {
143 return 0;
144 }
145 if(0 == linked_list->currentSize)
146 {
147 return NULL;
148 }
149
150 head_node = linked_list->headPtr;
151 return_data = head_node->dataPtr;
152
153 if(1 == linked_list->currentSize)
154 {
155 LinkedList_Clear(linked_list);
156 }
157 else
158 {
159 LinkedListNode* next_node = head_node->nextNode;
160 next_node->previousNode = NULL;
161 LinkedListNode_Free(head_node);
162 linked_list->headPtr = next_node;
163 linked_list->currentSize = linked_list->currentSize - 1;
164
165 }
166 return return_data;
167 }
168
169 void* LinkedList_PopBack(LinkedList* linked_list)
170 {
171 LinkedListNode* tail_node;
172 void* return_data;
173
174 if(NULL == linked_list)
175 {
176 return NULL;
177 }
178 if(0 == linked_list->currentSize)
179 {
180 return NULL;
181 }
182
183 tail_node = linked_list->tailPtr;
184 return_data = tail_node->dataPtr;
185
186 if(1 == linked_list->currentSize)
187 {
188 LinkedList_Clear(linked_list);
189 }
190 else
191 {
192 LinkedListNode* previous_node = tail_node->previousNode;
193 previous_node->nextNode = NULL;
194 LinkedListNode_Free(tail_node);
195 linked_list->tailPtr = previous_node;
196 linked_list->currentSize = linked_list->currentSize - 1;
197 }
198 return return_data;
199 }
200
201
202 void* LinkedList_Front(LinkedList* linked_list)
203 {
204 LinkedListNode* head_node;
205 void* return_data;
206
207 if(NULL == linked_list)
208 {
209 return 0;
210 }
211 if(0 == linked_list->currentSize)
212 {
213 return NULL;
214 }
215
216 head_node = linked_list->headPtr;
217 return_data = head_node->dataPtr;
218
219 return return_data;
220 }
221
222 void* LinkedList_Back(LinkedList* linked_list)
223 {
224 LinkedListNode* tail_node;
225 void* return_data;
226
227 if(NULL == linked_list)
228 {
229 return NULL;
230 }
231 if(0 == linked_list->currentSize)
232 {
233 return NULL;
234 }
235
236 tail_node = linked_list->tailPtr;
237 return_data = tail_node->dataPtr;
238
239 return return_data;
240 }
241
242
243 size_t LinkedList_Size(LinkedList* linked_list)
244 {
245 if(NULL == linked_list)
246 {
247 return 0;
248 }
249 return linked_list->currentSize;
250 }
251
252 void LinkedList_Clear(LinkedList* linked_list)
253 {
254 if(NULL == linked_list)
255 {
256 return;
257 }
258
259 LinkedListNode* current_node = linked_list->headPtr;
260 LinkedListNode* next_node;
261 while(NULL != current_node)
262 {
263 next_node = current_node->nextNode;
264 LinkedListNode_Free(current_node);
265 current_node = next_node;
266 }
267 linked_list->headPtr = NULL;
268 linked_list->tailPtr = NULL;
269 linked_list->currentSize = 0;
270 }
271
272 void* LinkedListNode_GetData(LinkedListNode* list_node)
273 {
274 if(NULL == list_node)
275 {
276 return NULL;
277 }
278 return list_node->dataPtr;
279 }
280
281 LinkedListNode* LinkedList_Find(LinkedList* linked_list, void* the_data, LinkedListNode* start_node)
282 {
283 LinkedListNode* current_node;
284 if(NULL == linked_list)
285 {
286 return NULL;
287 }
288 if(NULL == start_node)
289 {
290 start_node = linked_list->headPtr;
291 }
292
293 for(current_node = start_node; NULL != current_node; current_node = current_node->nextNode)
294 {
295 if(current_node->dataPtr == the_data)
296 {
297 return current_node;
298 }
299 }
300 return current_node;
301 }
302
303 /* Make sure your LinkedListNode is actually connected to the
304 * LinkedList instance you pass.
305 */
306 unsigned int LinkedList_Remove(LinkedList* linked_list, LinkedListNode* list_node)
307 {
308 LinkedListNode* previous_node;
309 LinkedListNode* next_node;
310 if(NULL == linked_list)
311 {
312 return 0;
313 }
314 if(NULL == list_node)
315 {
316 return 0;
317 }
318
319 if(1 == linked_list->currentSize)
320 {
321 LinkedList_Clear(linked_list);
322 }
323 else if(list_node == linked_list->headPtr)
324 {
325 LinkedList_PopFront(linked_list);
326 }
327 else if(list_node == linked_list->tailPtr)
328 {
329 LinkedList_PopBack(linked_list);
330 }
331 else
332 {
333 previous_node = list_node->previousNode;
334 next_node = list_node->nextNode;
335
336 previous_node->nextNode = next_node;
337 next_node->previousNode = previous_node;
338 LinkedListNode_Free(list_node);
339
340 linked_list->currentSize = linked_list->currentSize - 1;
341 }
342
343 return 1;
344
345 }
346
347
348