]>
Commit | Line | Data |
---|---|---|
212380e3 AC |
1 | /* |
2 | * ircd-ratbox: A slightly useful ircd. | |
3 | * tools.h: Header for the various tool functions. | |
4 | * | |
5 | * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center | |
6 | * Copyright (C) 1996-2002 Hybrid Development Team | |
7 | * Copyright (C) 2002-2004 ircd-ratbox development team | |
8 | * | |
9 | * This program is free software; you can redistribute it and/or modify | |
10 | * it under the terms of the GNU General Public License as published by | |
11 | * the Free Software Foundation; either version 2 of the License, or | |
12 | * (at your option) any later version. | |
13 | * | |
14 | * This program is distributed in the hope that it will be useful, | |
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
17 | * GNU General Public License for more details. | |
18 | * | |
19 | * You should have received a copy of the GNU General Public License | |
20 | * along with this program; if not, write to the Free Software | |
21 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 | |
22 | * USA | |
23 | * | |
01cebbd8 | 24 | * $Id: tools.h 3201 2007-02-04 01:59:38Z jilles $ |
212380e3 AC |
25 | */ |
26 | ||
27 | #ifndef __TOOLS_H__ | |
28 | #define __TOOLS_H__ | |
29 | ||
30 | ||
31 | /* | |
32 | * double-linked-list stuff | |
33 | */ | |
34 | typedef struct _dlink_node dlink_node; | |
35 | typedef struct _dlink_list dlink_list; | |
36 | ||
37 | struct _dlink_node | |
38 | { | |
39 | void *data; | |
40 | dlink_node *prev; | |
41 | dlink_node *next; | |
42 | ||
43 | }; | |
44 | ||
45 | struct _dlink_list | |
46 | { | |
47 | dlink_node *head; | |
48 | dlink_node *tail; | |
49 | unsigned long length; | |
50 | }; | |
51 | ||
52 | dlink_node *make_dlink_node(void); | |
53 | void free_dlink_node(dlink_node * lp); | |
54 | void init_dlink_nodes(void); | |
55 | ||
56 | #ifndef NDEBUG | |
57 | void mem_frob(void *data, int len); | |
58 | #else | |
59 | #define mem_frob(x, y) | |
60 | #endif | |
61 | ||
62 | /* This macros are basically swiped from the linux kernel | |
63 | * they are simple yet effective | |
64 | */ | |
65 | ||
66 | /* | |
67 | * Walks forward of a list. | |
68 | * pos is your node | |
69 | * head is your list head | |
70 | */ | |
71 | #define DLINK_FOREACH(pos, head) for (pos = (head); pos != NULL; pos = pos->next) | |
72 | ||
73 | /* | |
74 | * Walks forward of a list safely while removing nodes | |
75 | * pos is your node | |
76 | * n is another list head for temporary storage | |
77 | * head is your list head | |
78 | */ | |
79 | #define DLINK_FOREACH_SAFE(pos, n, head) for (pos = (head), n = pos ? pos->next : NULL; pos != NULL; pos = n, n = pos ? pos->next : NULL) | |
80 | ||
81 | #define DLINK_FOREACH_PREV(pos, head) for (pos = (head); pos != NULL; pos = pos->prev) | |
82 | ||
83 | ||
84 | /* Returns the list length */ | |
85 | #define dlink_list_length(list) (list)->length | |
86 | #define dlink_move_list(oldlist, newlist, node) | |
87 | ||
88 | #define dlinkAddAlloc(data, list) dlinkAdd(data, make_dlink_node(), list) | |
89 | #define dlinkAddTailAlloc(data, list) dlinkAddTail(data, make_dlink_node(), list) | |
90 | #define dlinkDestroy(node, list) do { dlinkDelete(node, list); free_dlink_node(node); } while(0) | |
91 | ||
92 | ||
93 | /* | |
94 | * The functions below are included for the sake of inlining | |
95 | * hopefully this will speed up things just a bit | |
96 | * | |
97 | */ | |
98 | ||
99 | /* | |
100 | * dlink_ routines are stolen from squid, except for dlinkAddBefore, | |
101 | * which is mine. | |
102 | * -- adrian | |
103 | */ | |
104 | ||
105 | /* I hate C sometimes */ | |
106 | #if defined __OPTIMIZE__ && !defined __OPTIMIZE_SIZE__ && !defined __NO_INLINE__ | |
107 | #define INLINE_FUNC extern inline | |
108 | #define NEED_INLINES | |
109 | #else | |
110 | #undef INLINE_FUNC | |
111 | #define INLINE_FUNC | |
112 | #endif | |
113 | ||
114 | #ifdef TOOLS_C | |
115 | #undef INLINE_FUNC | |
116 | #define INLINE_FUNC | |
117 | #endif | |
118 | ||
119 | void dlinkMoveNode(dlink_node * m, dlink_list * oldlist, dlink_list * newlist); | |
120 | void dlinkAdd(void *data, dlink_node * m, dlink_list * list); | |
121 | void dlinkAddBefore(dlink_node * b, void *data, dlink_node * m, dlink_list * list); | |
122 | void dlinkMoveTail(dlink_node *m, dlink_list *list); | |
123 | void dlinkAddTail(void *data, dlink_node * m, dlink_list * list); | |
124 | void dlinkDelete(dlink_node * m, dlink_list * list); | |
125 | dlink_node *dlinkFindDelete(void *data, dlink_list *list); | |
126 | int dlinkFindDestroy(void *data, dlink_list *list); | |
127 | dlink_node *dlinkFind(void *data, dlink_list *list); | |
128 | void dlinkMoveList(dlink_list * from, dlink_list * to); | |
212380e3 AC |
129 | |
130 | #if defined(NEED_INLINES) || defined(TOOLS_C) | |
131 | INLINE_FUNC void | |
132 | dlinkMoveNode(dlink_node * m, dlink_list * oldlist, dlink_list * newlist) | |
133 | { | |
134 | /* Assumption: If m->next == NULL, then list->tail == m | |
135 | * and: If m->prev == NULL, then list->head == m | |
136 | */ | |
137 | assert(m != NULL); | |
138 | assert(oldlist != NULL); | |
139 | assert(newlist != NULL); | |
140 | ||
141 | if(m->next) | |
142 | m->next->prev = m->prev; | |
143 | else | |
144 | oldlist->tail = m->prev; | |
145 | ||
146 | if(m->prev) | |
147 | m->prev->next = m->next; | |
148 | else | |
149 | oldlist->head = m->next; | |
150 | ||
151 | m->prev = NULL; | |
152 | m->next = newlist->head; | |
153 | if(newlist->head != NULL) | |
154 | newlist->head->prev = m; | |
155 | else if(newlist->tail == NULL) | |
156 | newlist->tail = m; | |
157 | newlist->head = m; | |
158 | ||
159 | oldlist->length--; | |
160 | newlist->length++; | |
161 | } | |
162 | ||
163 | INLINE_FUNC void | |
164 | dlinkAdd(void *data, dlink_node * m, dlink_list * list) | |
165 | { | |
166 | assert(data != NULL); | |
167 | assert(m != NULL); | |
168 | assert(list != NULL); | |
169 | m->data = data; | |
170 | m->prev = NULL; | |
171 | m->next = list->head; | |
172 | ||
173 | /* Assumption: If list->tail != NULL, list->head != NULL */ | |
174 | if(list->head != NULL) | |
175 | list->head->prev = m; | |
176 | else if(list->tail == NULL) | |
177 | list->tail = m; | |
178 | ||
179 | list->head = m; | |
180 | list->length++; | |
181 | } | |
182 | ||
183 | INLINE_FUNC void | |
184 | dlinkAddBefore(dlink_node * b, void *data, dlink_node * m, dlink_list * list) | |
185 | { | |
186 | assert(b != NULL); | |
187 | assert(data != NULL); | |
188 | assert(m != NULL); | |
189 | assert(list != NULL); | |
190 | ||
191 | /* Shortcut - if its the first one, call dlinkAdd only */ | |
192 | if(b == list->head) | |
193 | { | |
194 | dlinkAdd(data, m, list); | |
195 | } | |
196 | else | |
197 | { | |
198 | m->data = data; | |
199 | b->prev->next = m; | |
200 | m->prev = b->prev; | |
201 | b->prev = m; | |
202 | m->next = b; | |
203 | list->length++; | |
204 | } | |
205 | } | |
206 | ||
207 | INLINE_FUNC void | |
208 | dlinkMoveTail(dlink_node *m, dlink_list *list) | |
209 | { | |
210 | if(list->tail == m) | |
211 | return; | |
212 | ||
213 | /* From here assume that m->next != NULL as that can only | |
214 | * be at the tail and assume that the node is on the list | |
215 | */ | |
216 | ||
217 | m->next->prev = m->prev; | |
218 | ||
219 | if(m->prev != NULL) | |
220 | m->prev->next = m->next; | |
221 | else | |
222 | list->head = m->next; | |
223 | ||
224 | list->tail->next = m; | |
225 | m->prev = list->tail; | |
226 | m->next = NULL; | |
227 | list->tail = m; | |
228 | } | |
229 | ||
230 | INLINE_FUNC void | |
231 | dlinkAddTail(void *data, dlink_node * m, dlink_list * list) | |
232 | { | |
233 | assert(m != NULL); | |
234 | assert(list != NULL); | |
235 | assert(data != NULL); | |
236 | m->data = data; | |
237 | m->next = NULL; | |
238 | m->prev = list->tail; | |
239 | ||
240 | /* Assumption: If list->tail != NULL, list->head != NULL */ | |
241 | if(list->tail != NULL) | |
242 | list->tail->next = m; | |
243 | else if(list->head == NULL) | |
244 | list->head = m; | |
245 | ||
246 | list->tail = m; | |
247 | list->length++; | |
248 | } | |
249 | ||
250 | /* Execution profiles show that this function is called the most | |
251 | * often of all non-spontaneous functions. So it had better be | |
252 | * efficient. */ | |
253 | INLINE_FUNC void | |
254 | dlinkDelete(dlink_node * m, dlink_list * list) | |
255 | { | |
256 | assert(m != NULL); | |
257 | assert(list != NULL); | |
258 | ||
259 | /* Assumption: If m->next == NULL, then list->tail == m | |
260 | * and: If m->prev == NULL, then list->head == m | |
261 | */ | |
262 | if(m->next) | |
263 | m->next->prev = m->prev; | |
264 | else | |
265 | list->tail = m->prev; | |
266 | ||
267 | if(m->prev) | |
268 | m->prev->next = m->next; | |
269 | else | |
270 | list->head = m->next; | |
271 | ||
272 | m->next = m->prev = NULL; | |
273 | list->length--; | |
274 | } | |
275 | ||
276 | INLINE_FUNC dlink_node * | |
277 | dlinkFindDelete(void *data, dlink_list *list) | |
278 | { | |
279 | dlink_node *m; | |
280 | assert(list != NULL); | |
281 | assert(data != NULL); | |
282 | ||
283 | DLINK_FOREACH(m, list->head) | |
284 | { | |
285 | if(m->data != data) | |
286 | continue; | |
287 | ||
288 | if(m->next) | |
289 | m->next->prev = m->prev; | |
290 | else | |
291 | list->tail = m->prev; | |
292 | ||
293 | if(m->prev) | |
294 | m->prev->next = m->next; | |
295 | else | |
296 | list->head = m->next; | |
297 | ||
298 | m->next = m->prev = NULL; | |
299 | list->length--; | |
300 | return m; | |
301 | } | |
302 | ||
303 | return NULL; | |
304 | } | |
305 | ||
306 | INLINE_FUNC int | |
307 | dlinkFindDestroy(void *data, dlink_list *list) | |
308 | { | |
309 | void *ptr; | |
310 | ||
311 | assert(list != NULL); | |
312 | assert(data != NULL); | |
313 | ||
314 | ptr = dlinkFindDelete(data, list); | |
315 | ||
316 | if(ptr != NULL) | |
317 | { | |
318 | free_dlink_node(ptr); | |
319 | return 1; | |
320 | } | |
321 | return 0; | |
322 | } | |
323 | ||
324 | /* | |
325 | * dlinkFind | |
326 | * inputs - list to search | |
327 | * - data | |
328 | * output - pointer to link or NULL if not found | |
329 | * side effects - Look for ptr in the linked listed pointed to by link. | |
330 | */ | |
331 | INLINE_FUNC dlink_node * | |
332 | dlinkFind(void *data, dlink_list *list) | |
333 | { | |
334 | dlink_node *ptr; | |
335 | assert(list != NULL); | |
336 | assert(data != NULL); | |
337 | ||
338 | DLINK_FOREACH(ptr, list->head) | |
339 | { | |
340 | if(ptr->data == data) | |
341 | return (ptr); | |
342 | } | |
343 | return (NULL); | |
344 | } | |
345 | ||
346 | INLINE_FUNC void | |
347 | dlinkMoveList(dlink_list * from, dlink_list * to) | |
348 | { | |
349 | assert(from != NULL); | |
350 | assert(to != NULL); | |
351 | ||
352 | /* There are three cases */ | |
353 | /* case one, nothing in from list */ | |
354 | if(from->head == NULL) | |
355 | return; | |
356 | ||
357 | /* case two, nothing in to list */ | |
358 | if(to->head == NULL) | |
359 | { | |
360 | to->head = from->head; | |
361 | to->tail = from->tail; | |
362 | from->head = from->tail = NULL; | |
363 | to->length = from->length; | |
364 | from->length = 0; | |
365 | return; | |
366 | } | |
367 | ||
368 | /* third case play with the links */ | |
369 | from->tail->next = to->head; | |
370 | to->head->prev = from->tail; | |
371 | to->head = from->head; | |
372 | from->head = from->tail = NULL; | |
373 | to->length += from->length; | |
374 | from->length = 0; | |
375 | } | |
376 | #endif | |
377 | ||
378 | #endif /* __TOOLS_H__ */ |