1 SEE Linked List for the header file and a description of how
2 to use this library.
3
4 ---------------------------------------------------- List.c
5 /* Author: Brian Maher <maherb@cc.wwu.edu>
6 *
7 * License: LGPL - Lesser General Public License
8 * See: http://www.gnu.org/copyleft/lesser.html
9 * Quick License:
10 * -Don't claim that you created this code, please give me credit.
11 * -Any good ideas for improvement/fixes/etc, send to the above
12 * author with modifications to source code.
13 *
14 * $Revision$
15 * $Source$
16 *
17 */
18
19 #include "List.h"
20 #include <stdlib.h>
21 #include <assert.h>
22 #ifdef _DEBUG
23 #include <stdio.h>
24 #endif
25
26 /* Emulate bool type. */
27 #define bool int
28 #define true 1
29 #define false 0
30
31 /* Declare some helper functions */
32 static ListNode_t* List__at(List this, int index);
33
34 /* List creation/destruction: */
35 void List_new(List* this) {
36 *this = (List)malloc(sizeof(List_t));
37 (*this)->first = NULL;
38 (*this)->length = 0;
39 }
40
41 void List_destroy(List this, ListFreeFunc* itemFree) {
42 ListNode_t *prev, *cur;
43
44 assert(this != NULL);
45 cur = this->first;
46 if(cur != NULL) {
47 do {
48
49 /* Iterate our linked list pointer: */
50 prev = cur;
51 cur = cur->next;
52
53 /* Free the current item: */
54 if(itemFree != NULL) itemFree( prev->data );
55 memset(prev,sizeof(ListNode_t),0);
56 free(prev);
57
58 } while( cur != this->first );
59 }
60
61 /* Free the actual linked list: */
62 free(this);
63 }
64
65 /* List adding: */
66 int List_push(List this, ListItem item) {
67 ListNode_t* node;
68
69 assert(this != NULL);
70 node = (ListNode_t*)malloc(sizeof(ListNode_t));
71 node->data = item;
72
73 if(this->first == NULL) {
74 /* Inserting the first item: */
75 this->first = node;
76 node->next = node->prev = node;
77 } else {
78 node->next = this->first;
79 node->prev = this->first->prev;
80 node->prev->next = node;
81 this->first->prev = node;
82 }
83 return ++(this->length);
84 }
85
86 int List_unshift(List this, ListItem item) {
87 List_push(this, item);
88 /* Rotate the list: */
89 this->first = this->first->prev;
90 return this->length;
91 }
92
93 /* debugging */
94 #ifdef _DEBUG
95 void List_print(List this, FILE* fd) {
96 ListIterator it;
97 int i;
98
99 if(this == NULL) {
100 fprintf(fd,"NULL");
101 return;
102 }
103 it = List_front(this);
104 fprintf(fd,"(");
105 for(i=0;ListIterator_valid(it);ListIterator_next(&it),i++) {
106 fprintf(stderr,"%c ",*((char*)ListIterator_item(it)));
107 /* check the backward pointers */
108 assert(it.cur->next->prev == it.cur);
109 }
110 /* Do some asserts to make sure this is a valid list */
111 assert( i == it.list->length );
112 /* NOTE: one pointer can not be checked the ptr: list->first->prev */
113 if( i > 0 ) {
114 fprintf(fd,"\b)");
115 } else {
116 fprintf(fd,")");
117 }
118 }
119 #endif /* _DEBUG */
120
121 /* RETURN: NULL on error, otherwise a new List object which was extracted.
122 */
123 List List_splice(List this, int offset, int length,
124 List other_list, ListCopyFunc* copy_fn) {
125 ListNode_t *cur;
126 List ret;
127 bool prepend=false;
128
129 assert(this != NULL);
130 assert(length >= -1);
131 assert(other_list == NULL || other_list->length >= 0);
132
133 #ifdef _DEBUG
134 fprintf(stderr,"List_splice( this: ");
135 List_print(this, stderr);
136 fprintf(stderr," offset: %d length: %d other_list: ", offset, length);
137 List_print(other_list, stderr);
138 fprintf(stderr," )\n");
139 #endif /* _DEBUG */
140
141 List_new(&ret);
142 /* FIRST: iterate to the correct offset. */
143 if(offset == this->length) {
144 assert( length == 0 || length == -1 );
145 /* set cur to the end of the list */
146 if(this->first == NULL) {
147 assert(this->length == 0);
148 cur = NULL;
149 } else {
150 cur = this->first->prev;
151 }
152 } else {
153 cur = List__at(this, offset);
154 /* passed a bad offset */
155 assert( cur != NULL );
156 if( cur == this->first ) {
157 prepend = true;
158 }
159
160 /* SECOND: Create returned list, and splice out this list */
161 List_new(&ret);
162 if( length > 0 ||
163 (length == -1 && this->length > 0) ) {
164
165 ListNode_t *first, *prev;
166
167 /* if this happened, length was to long */
168 assert( cur != NULL );
169
170 prev = cur->prev;
171 ret->first = first = cur;
172
173 /* Loop for the length of the list. */
174 assert( length == -1 || length > 0 );
175 assert( ret->length == 0 );
176 ret->length++;
177 for(length--;
178 length != 0 && this->first != cur->next;
179 length--, cur=cur->next, ret->length++);
180
181 /* splice this list out: */
182 this->length -= ret->length;
183
184 /* change this->first if necessary */
185 if(first == this->first) this->first = cur->next;
186
187 if(this->length == 0) {
188 this->first = NULL;
189 } else {
190 prev->next = cur->next;
191 cur->next->prev = prev;
192 }
193
194 /* connect up the return list: */
195 first->prev = cur;
196 cur->next = first;
197
198 cur = prev;
199 } else {
200 cur = cur->prev;
201 }/* end of [if] we need to extract anything from the list */
202 }/* cur is just before insertion point */
203
204 #ifdef _DEBUG
205 fprintf(stderr,"MID( this: ");
206 List_print(this, stderr);
207 fprintf(stderr," ret: ");
208 List_print(ret, stderr);
209 fprintf(stderr,")\n");
210 #endif /* _DEBUG */
211
212 /* THIRD: Copy all items in other list */
213 if(other_list != NULL && other_list->first != NULL) {
214 ListNode_t *first, *last; /* pts at first and last node created */
215 ListNode_t *o_cur; /* pts to current location in other_list */
216 int i;
217
218 assert( other_list->length > 0 );
219
220 /* First we will copy all items in other_list */
221 o_cur = other_list->first;
222 last = first = malloc(sizeof(ListNode_t));
223 last->data = (copy_fn == NULL)? o_cur->data : copy_fn( o_cur->data );
224 o_cur = o_cur->next;
225 for(i=1; o_cur != other_list->first; o_cur = o_cur->next,i++ ) {
226 ListNode_t* node = malloc(sizeof(ListNode_t));
227 node->prev = last;
228 last->next = node;
229 last = node;
230 node->data = (copy_fn == NULL)? o_cur->data : copy_fn( o_cur->data );
231 }
232 assert(i == other_list->length);
233 /* at this point:
234 first -> pts to first node in newly created list.
235 last -> pts to last node in newly created list.
236 cur -> pts right before insertion pt */
237
238 /* Now link this newly created list into the existing list */
239 if( this->first == NULL ) {
240 assert( this->length == 0 );
241 /* In case we started with an empty list */
242 first->prev = last;
243 this->first = last->next = first;
244 } else {
245 ListNode_t* end;
246
247 if(prepend) {
248 assert(cur == this->first->prev);
249 /* prepend was signalled:
250 exceptional because we need to alter this->first */
251 this->first = cur;
252 }
253
254 end = cur->next;
255 cur->next = first;
256 first->prev = cur;
257
258 end->prev = last;
259 last->next = end;
260 if(prepend) {
261 /* correct back the this->first */
262 this->first = first;
263 }
264 }
265 this->length += other_list->length;
266 }
267
268 #ifdef _DEBUG
269 fprintf(stderr,"RET( this: ");
270 List_print(this, stderr);
271 fprintf(stderr," ret: ");
272 List_print(ret, stderr);
273 fprintf(stderr,")\n");
274 #endif /* _DEBUG */
275
276 return ret;
277 }
278
279 /* helper functions */
280 static ListNode_t* List__at(List this, int index) {
281 ListNode_t* cur;
282
283 assert(this != NULL);
284 /* overstep list! */
285 if(index >= this->length || index < -(this->length)) return NULL;
286
287 #ifdef _DEBUG
288 fprintf(stderr,"List__at( this: ");
289 List_print(this, stderr);
290 fprintf(stderr,", %d )",index);
291 #endif /* _DEBUG */
292
293 cur = this->first;
294 if(index < 0) {
295 /* TRICKY! if we have one element in the list, and we are passed -1,
296 this should be just like if we where passed 0 */
297 cur = this->first->prev; index++;
298 for(;index != 0;index++) {
299 cur = cur->prev;
300
301 /* Check if they are trying to overstep their list, should have
302 been handled above. */
303 assert( cur != this->first->prev );
304 }
305 } else if(index > 0) {
306 for(;index != 0;index--) {
307 cur = cur->next;
308 /* Check if they are trying to overstep their list: */
309 assert( cur != this->first );
310 }
311 }
312 #ifdef _DEBUG
313 fprintf(stderr," -> (%c)\n", *((char*)cur->data));
314 #endif _DEBUG
315 return cur;
316 }
317
318 /* List access/removal: */
319 ListItem List_at(List this, int index) {
320 ListNode_t* cur = List__at(this, index);
321 return (cur == NULL)? ListItemInvalid : cur->data;
322 }
323
324 ListItem List_pop(List this) {
325 ListNode_t* rem;
326 ListItem ret;
327 assert(this != NULL);
328 if(this->first == NULL) return ListItemInvalid;
329
330 rem = this->first->prev;
331 ret = rem->data;
332 if(rem == this->first) {
333 this->first = NULL;
334 } else {
335 this->first->prev = rem->prev;
336 rem->prev->next = this->first;
337 }
338
339 #ifndef NDEBUG
340 memset(rem,sizeof(ListNode_t),0);
341 #endif
342 free(rem);
343 this->length--;
344 return ret;
345 }
346
347 ListItem List_shift(List this) {
348 assert(this != NULL);
349 if(this->first == NULL) return ListItemInvalid;
350 this->first = this->first->next;
351 return List_pop(this);
352 }
353
354
355 /* Iterator stuff: */
356 ListIterator List_front(List this) {
357 ListIterator it;
358
359 assert(this != NULL);
360 it.cur = this->first;
361 it.list = this;
362 return it;
363 }
364 ListIterator List_back(List this) {
365 ListIterator it;
366
367 assert(this != NULL);
368 it.cur = this->first->prev;
369 it.list = this;
370 return it;
371 }
372
373 ListItem ListIterator_item(ListIterator it) {
374 if(it.cur == NULL) return ListItemInvalid;
375 return it.cur->data;
376 }
377 bool ListIterator_next(ListIterator* it) {
378 if(it->cur == NULL) return false;
379 it->cur = it->cur->next;
380 if(it->cur == it->list->first) {
381 it->cur = NULL;
382 return false;
383 }
384 return true;
385 }
386 bool ListIterator_prev(ListIterator* it) {
387 if(it->cur == NULL) return false;
388 it->cur = it->cur->prev;
389 if(it->cur == it->list->first) {
390 it->cur = NULL;
391 return false;
392 }
393 return true;
394 }
395
396 /* Changed to impliment this as a macro.
397 bool ListIterator_valid(ListIterator it) {
398 return (bool)(it.cur != NULL);
399 }
400 */
401