4 * Copyright (C) 2003 Eric J Bohm
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021110307 USA
23 /* Double linked list implementation.
25 * You allocate the data and give dlist the pointer.
26 * If your data is complex set the dlist->del_func to a an appropriate
27 * delete function. Otherwise dlist will just use free.
33 * Return pointer to node at marker.
34 * else null if no nodes.
37 inline void *dlist_mark(Dlist *list)
39 if(list->marker!=NULL)
40 return(list->marker->data);
46 * Set marker to start.
49 inline void dlist_start(Dlist *list)
51 list->marker=list->head;
58 inline void dlist_end(Dlist *list)
60 list->marker=list->head;
63 /* internal use function
64 * quickie inline to consolidate the marker movement logic
67 * when direction true it moves marker after
68 * when direction false it moves marker before.
69 * return pointer to data at new marker
70 * if nowhere to move the marker in desired direction return null
72 inline void *_dlist_mark_move(Dlist *list,int direction)
76 if( list->marker && list->marker->next!=NULL)
77 list->marker=list->marker->next;
83 if( list->marker && list->marker->prev!=NULL)
84 list->marker=list->marker->prev;
88 if(list->marker!=list->head)
89 return(list->marker->data);
95 * Create new linked list to store nodes of datasize.
96 * return null if list cannot be created.
98 Dlist *dlist_new(size_t datasize)
101 if((list=malloc(sizeof(Dlist))))
105 list->data_size=datasize;
107 list->head=&(list->headnode);
108 list->head->prev=NULL;
109 list->head->next=NULL;
110 list->head->data=NULL;
116 * Create new linked list to store nodes of datasize set list
117 * data node delete function to the passed in del_func
118 * return null if list cannot be created.
120 Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*))
123 list=dlist_new(datasize);
125 list->del_func=del_func;
131 * remove marker node from list
132 * call data_delete function on data if registered.
133 * otherwise call free.
134 * when direction true it moves marker after
135 * when direction false it moves marker before.
139 void dlist_delete(Dlist *list,int direction)
141 if((list->marker != list->head)&&(list->marker!=NULL))
145 _dlist_mark_move(list,direction);
146 if(list->head->next==corpse)
147 list->head->next=corpse->next;
148 if(list->head->prev==corpse)
149 list->head->prev=corpse->prev;
150 if(corpse->prev!=NULL) //should be impossible
151 corpse->prev->next=corpse->next;
152 if(corpse->next!=NULL) //should be impossible
153 corpse->next->prev=corpse->prev;
154 list->del_func(corpse->data);
161 * Insert node containing data at marker.
162 * If direction true it inserts after.
163 * If direction false it inserts before.
164 * move marker to inserted node
165 * return pointer to inserted node
167 void *dlist_insert(Dlist *list,void *data,int direction)
169 DL_node *new_node=NULL;
170 if(list==NULL || data==NULL)
172 if(list->marker==NULL) //in case the marker ends up unset
173 list->marker=list->head;
174 if((new_node=malloc(sizeof(DL_node))))
180 if(list->head->next==NULL) //no l
182 list->head->next=list->head->prev=new_node;
183 new_node->prev=list->head;
184 new_node->next=list->head;
188 new_node->next=list->marker->next;
189 new_node->prev=list->marker;
190 list->marker->next->prev=new_node;
191 list->marker->next=new_node;
195 new_node->prev=list->marker->prev;
196 new_node->next=list->marker;
197 list->marker->prev->next=new_node;
198 list->marker->prev=new_node;
200 list->marker=new_node;
206 return(list->marker->data);
210 * Insert dl_node at marker.
211 * If direction true it inserts after.
212 * If direction false it inserts before.
213 * move marker to inserted node
214 * return pointer to inserted node
216 void *_dlist_insert_dlnode(struct dlist *list,struct dl_node *new_node,int direction)
218 if(list==NULL || new_node==NULL)
220 if(list->marker==NULL) //in case the marker ends up unset
221 list->marker=list->head;
223 if(list->head->next==NULL)
225 list->head->next=list->head->prev=new_node;
226 new_node->prev=list->head;
227 new_node->next=list->head;
231 new_node->next=list->marker->next;
232 new_node->prev=list->marker;
233 list->marker->next->prev=new_node;
234 list->marker->next=new_node;
238 new_node->prev=list->marker->prev;
239 new_node->next=list->marker;
240 list->marker->prev->next=new_node;
241 list->marker->prev=new_node;
243 list->marker=new_node;
244 return(list->marker);
250 * Remove DL_node from list without deallocating data.
251 * if marker == killme .
252 * when direction true it moves marker after
253 * when direction false it moves marker before.
254 * to previous if there is no next.
256 void *_dlist_remove(Dlist *list,DL_node *killme,int direction)
260 void *killer_data=killme->data;
261 // take care of head and marker pointers.
262 if(list->marker==killme)
263 _dlist_mark_move(list,direction);
264 if(killme ==list->head->next)
265 list->head->next=killme->next;
266 if(killme==list->head->prev)
267 list->head->prev=killme->prev;
269 if(killme->prev !=NULL)
270 killme->prev->next=killme->next;
271 if(killme->next !=NULL)
272 killme->next->prev=killme->prev;
282 * move dl_node from source to dest
283 * if marker == target .
284 * when direction true it moves marker after
285 * when direction false it moves marker before.
286 * to previous if there is no next.
288 void dlist_move(struct dlist *source, struct dlist *dest, struct dl_node *target,int direction)
293 if(target==source->head)
295 //not even going to try
299 // take care of head and marker pointers.
300 if(source->marker==target)
301 _dlist_mark_move(source,direction);
302 if(target ==source->head->next)
303 source->head->next=target->next;
304 if(target==source->head->prev)
305 source->head->prev=target->prev;
311 source->head->next=NULL;
312 source->head->prev=NULL;
316 if(target->prev !=NULL)
317 target->prev->next=target->next;
318 if(target->next !=NULL)
319 target->next->prev=target->prev;
324 _dlist_insert_dlnode(dest,target,direction);
331 * Insert node containing data after end.
333 void dlist_push(Dlist *list,void *data)
335 list->marker=list->head->prev;
336 dlist_insert(list,data,1);
340 * Insert node containing data at start.
343 void dlist_unshift(Dlist *list,void *data)
346 list->marker=list->head->next;
347 dlist_insert(list,data,0);
350 void dlist_unshift_sorted(Dlist *list, void *data,
351 int (*sorter)(void *new_elem, void *old_elem))
353 if (list->count == 0)
354 dlist_unshift(list, data);
356 list->marker=list->head->next;
357 dlist_insert_sorted(list, data, sorter);
362 * Remove end node from list.
363 * Return pointer to data in removed node.
367 void *dlist_pop(Dlist *list)
369 return(_dlist_remove(list,list->head->prev,0));
373 * Remove start node from list.
374 * Return pointer to data in removed node.
378 void *dlist_shift(Dlist *list)
380 return(_dlist_remove(list,list->head->next,1));
385 * destroy the list freeing all memory
389 void dlist_destroy(Dlist *list)
395 while (dlist_mark(list)) {
396 dlist_delete(list,1);
403 * Return void pointer to list_data element matching comp function criteria
405 * Does not move the marker.
408 void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *))
410 /* test the comp function on each node */
411 struct dl_node *nodepointer;
412 dlist_for_each_nomark(list,nodepointer)
413 if(comp(target,nodepointer->data))
414 return(nodepointer->data);
419 * Apply the node_operation function to each data node in the list
421 void dlist_transform(struct dlist *list, void (*node_operation)(void *))
423 struct dl_node *nodepointer;
424 dlist_for_each_nomark(list,nodepointer)
425 node_operation(nodepointer->data);
429 * insert new into list in sorted order
430 * sorter function in form int sorter(new,ith)
431 * must return 1 for when new should go before ith
433 * return pointer to inserted node
434 * NOTE: assumes list is already sorted
436 void *dlist_insert_sorted(struct dlist *list, void *new, int (*sorter)(void *, void *))
438 for(dlist_start(list),dlist_next(list); \
439 list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
440 return(dlist_insert_before(list,new));
444 * NOTE: internal use only
446 int _dlist_merge(struct dlist *listsource, struct dlist *listdest, unsigned int passcount, int (*compare)(void *, void *))
449 struct dl_node *l1head;
450 struct dl_node *l2head;
451 struct dl_node *target;
452 unsigned int l1count=0;
453 unsigned int l2count=0;
454 unsigned int mergecount=0;
455 while(listsource->count>0)
457 l1head=listsource->head->next;
459 while((l1count<passcount)&&(l2head!=listsource->head))
464 // so now we have two lists to merge
466 if(l2head==listsource->head)
474 while(l1count>0 || l2count>0)
477 if((l2count>0)&&(l1count>0))
479 // we have things to merge
480 int result=compare(l1head->data,l2head->data);
486 dlist_move(listsource,listdest,target,1);
488 if(l2head==listsource->head)
496 dlist_move(listsource,listdest,target,1);
502 // only have l1 to work with
507 dlist_move(listsource,listdest,target,1);
513 // only have l2 to work with
516 if(l2head==listsource->head)
524 dlist_move(listsource,listdest,target,1);
530 { //nothing left and this should be unreachable
538 * mergesort the list based on compare
539 * compare function in form int sorter(void * a,void * b)
540 * must return >0 for a after b
541 * must return <0 for a before b
544 * NOTE: mergesort changes the mark pointer
546 void dlist_sort_custom(struct dlist *list, int (*compare)(void *, void *))
549 struct dlist *listsource, *listdest, *swap;
550 struct dlist *templist;
551 unsigned int passcount = 1;
552 unsigned int mergecount = 1;
555 templist = dlist_new(list->data_size);
557 // do nothing if there isn't anything to sort
560 if(listsource->count<2)
568 mergecount=_dlist_merge(listsource, listdest, passcount, compare);
571 passcount=passcount*2;
579 // now put the input list pointers right
580 // list pointers = newlist pointers
581 // including the forward and next nodes prev and back pointers
584 list->marker = listdest->marker;
585 list->count = listdest->count;
586 list->data_size = listdest->data_size;
587 list->del_func = listdest->del_func;
588 list->head->prev = listdest->head->prev;
589 list->head->next = listdest->head->next;
590 list->head->data = listdest->head->data;
591 list->head->next->prev=list->head;
592 list->head->prev->next=list->head;
593 templist->head->next=NULL;
594 templist->head->prev=NULL;
602 dlist_destroy(templist);
607 /* internal use function
608 swaps elements a and b
609 No sense in juggling node pointers when we can just swap the data pointers
612 void _dlist_swap(struct dlist *list, struct dl_node *a, struct dl_node *b)