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.
34 * Return pointer to node at marker.
35 * else null if no nodes.
38 inline void *dlist_mark(Dlist *list)
40 if(list->marker!=NULL)
41 return(list->marker->data);
47 * Set marker to start.
50 inline void dlist_start(Dlist *list)
52 list->marker=list->head;
59 inline void dlist_end(Dlist *list)
61 list->marker=list->head;
64 /* internal use function
65 * quickie inline to consolidate the marker movement logic
68 * when direction true it moves marker after
69 * when direction false it moves marker before.
70 * return pointer to data at new marker
71 * if nowhere to move the marker in desired direction return null
73 inline void *_dlist_mark_move(Dlist *list,int direction)
77 if( list->marker && list->marker->next!=NULL)
78 list->marker=list->marker->next;
84 if( list->marker && list->marker->prev!=NULL)
85 list->marker=list->marker->prev;
89 if(list->marker!=list->head)
90 return(list->marker->data);
96 * Create new linked list to store nodes of datasize.
97 * return null if list cannot be created.
99 Dlist *dlist_new(size_t datasize)
102 if((list=malloc(sizeof(Dlist))))
106 list->data_size=datasize;
108 list->head=&(list->headnode);
109 list->head->prev=NULL;
110 list->head->next=NULL;
111 list->head->data=NULL;
117 * Create new linked list to store nodes of datasize set list
118 * data node delete function to the passed in del_func
119 * return null if list cannot be created.
121 Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*))
124 list=dlist_new(datasize);
126 list->del_func=del_func;
132 * remove marker node from list
133 * call data_delete function on data if registered.
134 * otherwise call free.
135 * when direction true it moves marker after
136 * when direction false it moves marker before.
140 void dlist_delete(Dlist *list,int direction)
142 if((list->marker != list->head)&&(list->marker!=NULL))
146 _dlist_mark_move(list,direction);
147 if(list->head->next==corpse)
148 list->head->next=corpse->next;
149 if(list->head->prev==corpse)
150 list->head->prev=corpse->prev;
151 if(corpse->prev!=NULL) //should be impossible
152 corpse->prev->next=corpse->next;
153 if(corpse->next!=NULL) //should be impossible
154 corpse->next->prev=corpse->prev;
155 list->del_func(corpse->data);
162 * Insert node containing data at marker.
163 * If direction true it inserts after.
164 * If direction false it inserts before.
165 * move marker to inserted node
166 * return pointer to inserted node
168 void *dlist_insert(Dlist *list,void *data,int direction)
170 DL_node *new_node=NULL;
171 if(list==NULL || data==NULL)
173 if(list->marker==NULL) //in case the marker ends up unset
174 list->marker=list->head;
175 if((new_node=malloc(sizeof(DL_node))))
181 if(list->head->next==NULL) //no l
183 list->head->next=list->head->prev=new_node;
184 new_node->prev=list->head;
185 new_node->next=list->head;
189 new_node->next=list->marker->next;
190 new_node->prev=list->marker;
191 list->marker->next->prev=new_node;
192 list->marker->next=new_node;
196 new_node->prev=list->marker->prev;
197 new_node->next=list->marker;
198 list->marker->prev->next=new_node;
199 list->marker->prev=new_node;
201 list->marker=new_node;
207 return(list->marker->data);
211 * Remove DL_node from list without deallocating data.
212 * if marker == killme .
213 * when direction true it moves marker after
214 * when direction false it moves marker before.
215 * to previous if there is no next.
217 void *_dlist_remove(Dlist *list,DL_node *killme,int direction)
221 void *killer_data=killme->data;
222 // take care of head and marker pointers.
223 if(list->marker==killme)
224 _dlist_mark_move(list,direction);
225 if(killme ==list->head->next)
226 list->head->next=killme->next;
227 if(killme==list->head->prev)
228 list->head->prev=killme->prev;
230 if(killme->prev !=NULL)
231 killme->prev->next=killme->next;
232 if(killme->next !=NULL)
233 killme->next->prev=killme->prev;
244 * Insert node containing data after end.
246 void dlist_push(Dlist *list,void *data)
248 list->marker=list->head->prev;
249 dlist_insert(list,data,1);
253 * Insert node containing data at start.
256 void dlist_unshift(Dlist *list,void *data)
259 list->marker=list->head->next;
260 dlist_insert(list,data,0);
263 void dlist_unshift_sorted(Dlist *list, void *data,
264 int (*sorter)(void *new, void *old))
266 if (list->count == 0)
267 dlist_unshift(list, data);
269 list->marker=list->head->next;
270 dlist_insert_sorted(list, data, sorter);
275 * Remove end node from list.
276 * Return pointer to data in removed node.
280 void *dlist_pop(Dlist *list)
282 return(_dlist_remove(list,list->head->prev,0));
286 * Remove start node from list.
287 * Return pointer to data in removed node.
291 void *dlist_shift(Dlist *list)
293 return(_dlist_remove(list,list->head->next,1));
298 * destroy the list freeing all memory
302 void dlist_destroy(Dlist *list)
308 while (dlist_mark(list)) {
309 dlist_delete(list,1);
316 * Return void pointer to list_data element matching comp function criteria
318 * Does not move the marker.
321 void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *))
323 /* test the comp function on each node */
324 struct dl_node *nodepointer;
325 dlist_for_each_nomark(list,nodepointer)
326 if(comp(target,nodepointer->data))
327 return(nodepointer->data);
332 * Apply the node_operation function to each data node in the list
334 void dlist_transform(struct dlist *list, void (*node_operation)(void *))
336 struct dl_node *nodepointer;
337 dlist_for_each_nomark(list,nodepointer)
338 node_operation(nodepointer->data);
342 * insert new into list in sorted order
343 * sorter function in form int sorter(new,ith)
344 * must return 1 for when new should go before ith
346 * return pointer to inserted node
347 * NOTE: assumes list is already sorted
349 void *dlist_insert_sorted(struct dlist *list, void *new, int (*sorter)(void *, void *))
351 for(dlist_start(list),dlist_next(list); \
352 list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
353 return(dlist_insert_before(list,new));