]>
Commit | Line | Data |
---|---|---|
fe3fe3b2 DS |
1 | /* |
2 | * dlist.h | |
3 | * | |
4 | * Copyright (C) 2003 Eric J Bohm | |
5 | * | |
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. | |
10 | * | |
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. | |
15 | * | |
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 | |
19 | * | |
20 | */ | |
21 | #ifndef _DLIST_H_ | |
22 | #define _DLIST_H_ | |
23 | ||
24 | /* Double linked list header. | |
25 | ||
26 | * navigate your list with DLIST_PREV and DLIST_NEXT. These are macros | |
27 | * so function call overhead is minimized. | |
28 | ||
29 | * Supports perl style push, pop, shift, unshift list semantics. | |
30 | ||
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 | |
34 | (void * )(del(void *) | |
35 | *Otherwise dlist will just use free. | |
36 | ||
37 | * NOTE: The small amount of pain involved in doing that allows us to | |
38 | * avoid copy in copy out semantics. | |
39 | ||
40 | * Dlist uses an internal mark pointer to keep track of where you are | |
41 | * in the list. | |
42 | ||
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. | |
50 | ||
51 | * Just use the dlist_(insert|delete)_(before|after) macros if you do not want | |
52 | * to think about it. | |
53 | ||
54 | */ | |
fe3fe3b2 DS |
55 | typedef struct dl_node { |
56 | struct dl_node *prev; | |
57 | struct dl_node *next; | |
58 | void *data; | |
59 | } DL_node; | |
60 | ||
61 | typedef struct dlist { | |
62 | DL_node *marker; | |
63 | unsigned long count; | |
64 | size_t data_size; | |
65 | void (*del_func)(void *); | |
66 | DL_node headnode; | |
67 | DL_node *head; | |
68 | } Dlist; | |
69 | ||
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 *); | |
76 | ||
77 | void *dlist_insert(Dlist *,void *,int) ; | |
78 | ||
d1fb871d | 79 | void *dlist_insert_sorted(struct dlist *list, void *new_elem, int (*sorter)(void *, void *)); |
fe3fe3b2 DS |
80 | |
81 | void dlist_delete(Dlist *,int); | |
82 | ||
83 | void dlist_push(Dlist *,void *); | |
84 | ||
85 | void dlist_unshift(Dlist *,void *); | |
d1fb871d | 86 | void dlist_unshift_sorted(Dlist *,void *,int (*sorter)(void *, void *)); |
fe3fe3b2 DS |
87 | |
88 | void *dlist_pop(Dlist *); | |
89 | ||
90 | void *dlist_shift(Dlist *); | |
91 | ||
92 | void dlist_destroy(Dlist *); | |
93 | ||
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 *)); | |
96 | ||
97 | ||
98 | /* | |
99 | * _dlist_remove is for internal use only | |
100 | * _dlist_mark_move is for internal use only | |
101 | */ | |
102 | void *_dlist_remove(struct dlist *,struct dl_node *,int ); | |
103 | ||
104 | #define dlist_prev(A) _dlist_mark_move((A),0) | |
105 | #define dlist_next(A) _dlist_mark_move((A),1) | |
106 | ||
107 | #define dlist_insert_before(A,B) dlist_insert((A),(B),0) | |
108 | #define dlist_insert_after(A,B) dlist_insert((A),(B),1) | |
109 | ||
110 | #define dlist_delete_before(A) dlist_delete((A),0) | |
111 | #define dlist_delete_after(A) dlist_delete((A),1) | |
112 | ||
113 | /** | |
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 | |
116 | */ | |
117 | #define dlist_for_each(list) \ | |
118 | for(dlist_start(list),dlist_next(list); \ | |
119 | (list)->marker!=(list)->head;dlist_next(list)) | |
120 | ||
121 | /** | |
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 | |
124 | */ | |
125 | #define dlist_for_each_rev(list) \ | |
126 | for(dlist_end(list),dlist_prev(list); \ | |
127 | (list)->marker!=(list)->head;dlist_prev(list)) | |
128 | ||
129 | /** | |
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 | |
133 | */ | |
134 | #define dlist_for_each_nomark(list,iterator) \ | |
135 | for((iterator)=(list)->head->next; (iterator)!=(list)->head; \ | |
136 | (iterator)=(iterator)->next) | |
137 | ||
138 | /** | |
139 | * provide for loop header which iterates through the list without moving mark | |
140 | * in reverse | |
141 | * list: the dlist_pointer | |
142 | * iterator: dl_node pointer to iterate | |
143 | */ | |
144 | #define dlist_for_each_nomark_rev(list,iterator) \ | |
145 | for((iterator)=(list)->head->prev; (iterator)!=(list)->head; \ | |
146 | (iterator)=(iterator)->prev) | |
147 | /** | |
148 | * provide for loop header which iterates through the list providing a | |
149 | * data iterator | |
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 | |
153 | */ | |
154 | ||
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)) | |
158 | ||
159 | /** | |
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 | |
165 | */ | |
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)) | |
169 | ||
170 | /** | |
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 | |
177 | */ | |
178 | ||
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)) | |
182 | ||
183 | /** | |
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 | |
190 | */ | |
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)) | |
194 | ||
195 | #endif /* _DLIST_H_ */ |