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 02111-1307 USA
24 /* Double linked list header.
26 * navigate your list with DLIST_PREV and DLIST_NEXT. These are macros
27 * so function call overhead is minimized.
29 * Supports perl style push, pop, shift, unshift list semantics.
31 * You allocate the data and give dlist the pointer. If your data is
32 * complex set the dlist->del_func to a an appropriate delete using
33 * dlist_new_with_delete. Your delete function must match
35 *Otherwise dlist will just use free.
37 * NOTE: The small amount of pain involved in doing that allows us to
38 * avoid copy in copy out semantics.
40 * Dlist uses an internal mark pointer to keep track of where you are
43 * insert and delete take a directional parameter. Where direction
44 * corresponds to the direction in which you want the list to go.
45 * true direction corresponded to progressing forward in the last
46 * false to regressing in the list.
47 * so a dlist_insert(yourlist,item,1) will insert it after the mark
48 * so a dlist_insert(yourlist,item,0) will insert it before the mark
49 * any insert will move the mark to the new node regardless of the direction.
51 * Just use the dlist_(insert|delete)_(before|after) macros if you do not want
55 typedef struct dl_node {
61 typedef struct dlist {
65 void (*del_func)(void *);
70 Dlist *dlist_new(size_t datasize);
71 Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*));
72 void *_dlist_mark_move(Dlist *list,int direction);
73 void *dlist_mark(Dlist *);
74 void dlist_start(Dlist *);
75 void dlist_end(Dlist *);
77 void *dlist_insert(Dlist *,void *,int) ;
79 void *dlist_insert_sorted(struct dlist *list, void *new_elem, int (*sorter)(void *, void *));
81 void dlist_delete(Dlist *,int);
83 void dlist_push(Dlist *,void *);
85 void dlist_unshift(Dlist *,void *);
86 void dlist_unshift_sorted(Dlist *,void *,int (*sorter)(void *, void *));
88 void *dlist_pop(Dlist *);
90 void *dlist_shift(Dlist *);
92 void dlist_destroy(Dlist *);
94 void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *));
95 void dlist_transform(struct dlist *list, void (*node_operation)(void *));
99 * _dlist_remove is for internal use only
100 * _dlist_mark_move is for internal use only
102 void *_dlist_remove(struct dlist *,struct dl_node *,int );
104 #define dlist_prev(A) _dlist_mark_move((A),0)
105 #define dlist_next(A) _dlist_mark_move((A),1)
107 #define dlist_insert_before(A,B) dlist_insert((A),(B),0)
108 #define dlist_insert_after(A,B) dlist_insert((A),(B),1)
110 #define dlist_delete_before(A) dlist_delete((A),0)
111 #define dlist_delete_after(A) dlist_delete((A),1)
114 * provide for loop header which iterates the mark from start to end
115 * list: the dlist pointer, use dlist_mark(list) to get iterator
117 #define dlist_for_each(list) \
118 for(dlist_start(list),dlist_next(list); \
119 (list)->marker!=(list)->head;dlist_next(list))
122 * provide for loop header which iterates the mark from end to start
123 * list: the dlist pointer, use dlist_mark(list) to get iterator
125 #define dlist_for_each_rev(list) \
126 for(dlist_end(list),dlist_prev(list); \
127 (list)->marker!=(list)->head;dlist_prev(list))
130 * provide for loop header which iterates through the list without moving mark
131 * list: the dlist_pointer
132 * iterator: dl_node pointer to iterate
134 #define dlist_for_each_nomark(list,iterator) \
135 for((iterator)=(list)->head->next; (iterator)!=(list)->head; \
136 (iterator)=(iterator)->next)
139 * provide for loop header which iterates through the list without moving mark
141 * list: the dlist_pointer
142 * iterator: dl_node pointer to iterate
144 #define dlist_for_each_nomark_rev(list,iterator) \
145 for((iterator)=(list)->head->prev; (iterator)!=(list)->head; \
146 (iterator)=(iterator)->prev)
148 * provide for loop header which iterates through the list providing a
150 * list: the dlist pointer
151 * data_iterator: the pointer of type datatype to iterate
152 * datatype: actual type of the contents in the dl_node->data
155 #define dlist_for_each_data(list,data_iterator,datatype) \
156 for(dlist_start(list), (data_iterator)=(datatype *) dlist_next(list); \
157 (list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_next(list))
160 * provide for loop header which iterates through the list providing a
161 * data iterator in reverse
162 * list: the dlist pointer
163 * data_iterator: the pointer of type datatype to iterate
164 * datatype: actual type of the contents in the dl_node->data
166 #define dlist_for_each_data_rev(list,data_iterator,datatype) \
167 for(dlist_end(list), (data_iterator)=(datatype *) dlist_prev(list); \
168 (list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_prev(list))
171 * provide for loop header which iterates through the list providing a
172 * data iterator without moving the mark
173 * list: the dlist pointer
174 * iterator: the dl_node pointer to iterate
175 * data_iterator: the pointer of type datatype to iterate
176 * datatype: actual type of the contents in the dl_node->data
179 #define dlist_for_each_data_nomark(list,iterator,data_iterator,datatype) \
180 for((iterator)=(list)->head->next, (data_iterator)=(datatype *) (iterator)->data; \
181 (iterator)!=(list)->head;(iterator)=(iterator)->next,(data_iterator)=(datatype *) (iterator))
184 * provide for loop header which iterates through the list providing a
185 * data iterator in reverse without moving the mark
186 * list: the dlist pointer
187 * iterator: the dl_node pointer to iterate
188 * data_iterator: the pointer of type datatype to iterate
189 * datatype: actual type of the contents in the dl_node->data
191 #define dlist_for_each_data_nomark_rev(list,iterator, data_iterator,datatype) \
192 for((iterator)=(list)->head->prev, (data_iterator)=(datatype *) (iterator)->data; \
193 (iterator)!=(list)->head;(iterator)=(iterator)->prev,(data_iterator)=(datatype *) (iterator))
195 #endif /* _DLIST_H_ */