1 |
/* |
2 |
* ircd-hybrid: an advanced Internet Relay Chat Daemon(ircd). |
3 |
* tools.h: Header for the various tool functions. |
4 |
* |
5 |
* Copyright (C) 2002 by the past and present ircd coders, and others. |
6 |
* |
7 |
* This program is free software; you can redistribute it and/or modify |
8 |
* it under the terms of the GNU General Public License as published by |
9 |
* the Free Software Foundation; either version 2 of the License, or |
10 |
* (at your option) any later version. |
11 |
* |
12 |
* This program is distributed in the hope that it will be useful, |
13 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
15 |
* GNU General Public License for more details. |
16 |
* |
17 |
* You should have received a copy of the GNU General Public License |
18 |
* along with this program; if not, write to the Free Software |
19 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 |
20 |
* USA |
21 |
* |
22 |
* $Id$ |
23 |
*/ |
24 |
|
25 |
#ifndef __TOOLS_H__ |
26 |
#define __TOOLS_H__ |
27 |
#include "stdinc.h" |
28 |
|
29 |
/* |
30 |
* double-linked-list and single-linked-list stuff |
31 |
*/ |
32 |
typedef struct _dlink_node dlink_node; |
33 |
typedef struct _dlink_list dlink_list; |
34 |
|
35 |
struct _dlink_node |
36 |
{ |
37 |
void *data; |
38 |
dlink_node *prev; |
39 |
dlink_node *next; |
40 |
}; |
41 |
|
42 |
struct _dlink_list |
43 |
{ |
44 |
dlink_node *head; |
45 |
dlink_node *tail; |
46 |
unsigned long length; |
47 |
}; |
48 |
|
49 |
extern void dlinkAdd(void *data, dlink_node * m, dlink_list * list); |
50 |
extern void dlinkAddBefore(dlink_node *b, void *data, dlink_node *m, dlink_list *list); |
51 |
extern void dlinkAddTail(void *data, dlink_node *m, dlink_list *list); |
52 |
extern void dlinkDelete(dlink_node *m, dlink_list *list); |
53 |
extern void dlinkMoveList(dlink_list *from, dlink_list *to); |
54 |
extern dlink_node *dlinkFind(dlink_list *m, void *data); |
55 |
extern dlink_node *dlinkFindDelete(dlink_list *m, void *data); |
56 |
|
57 |
#ifndef NDEBUG |
58 |
void mem_frob(void *data, int len); |
59 |
#else |
60 |
#define mem_frob(x, y) |
61 |
#endif |
62 |
|
63 |
/* These macros are basically swiped from the linux kernel |
64 |
* they are simple yet effective |
65 |
*/ |
66 |
|
67 |
/* |
68 |
* Walks forward of a list. |
69 |
* pos is your node |
70 |
* head is your list head |
71 |
*/ |
72 |
#define DLINK_FOREACH(pos, head) for (pos = (head); pos != NULL; pos = pos->next) |
73 |
|
74 |
/* |
75 |
* Walks forward of a list safely while removing nodes |
76 |
* pos is your node |
77 |
* n is another list head for temporary storage |
78 |
* head is your list head |
79 |
*/ |
80 |
#define DLINK_FOREACH_SAFE(pos, n, head) for (pos = (head), n = pos ? pos->next : NULL; pos != NULL; pos = n, n = pos ? pos->next : NULL) |
81 |
#define DLINK_FOREACH_PREV(pos, head) for (pos = (head); pos != NULL; pos = pos->prev) |
82 |
|
83 |
/* Returns the list length */ |
84 |
#define dlink_list_length(list) (list)->length |
85 |
|
86 |
/* |
87 |
* The functions below are included for the sake of inlining |
88 |
* hopefully this will speed up things just a bit |
89 |
* |
90 |
*/ |
91 |
/* forte (and maybe others) dont like these being declared twice, |
92 |
* so we dont declare the inlines unless GNUC. |
93 |
*/ |
94 |
#ifdef __GNUC__ |
95 |
|
96 |
/* |
97 |
* dlink_ routines are stolen from squid, except for dlinkAddBefore, |
98 |
* which is mine. |
99 |
* -- adrian |
100 |
*/ |
101 |
extern inline void |
102 |
dlinkAdd(void *data, dlink_node * m, dlink_list * list) |
103 |
{ |
104 |
m->data = data; |
105 |
m->prev = NULL; |
106 |
m->next = list->head; |
107 |
/* Assumption: If list->tail != NULL, list->head != NULL */ |
108 |
if (list->head != NULL) |
109 |
list->head->prev = m; |
110 |
else if (list->tail == NULL) |
111 |
list->tail = m; |
112 |
list->head = m; |
113 |
list->length++; |
114 |
} |
115 |
|
116 |
extern inline void |
117 |
dlinkAddBefore(dlink_node *b, void *data, dlink_node *m, dlink_list *list) |
118 |
{ |
119 |
/* Shortcut - if its the first one, call dlinkAdd only */ |
120 |
if (b == list->head) |
121 |
dlinkAdd(data, m, list); |
122 |
else { |
123 |
m->data = data; |
124 |
b->prev->next = m; |
125 |
m->prev = b->prev; |
126 |
b->prev = m; |
127 |
m->next = b; |
128 |
list->length++; |
129 |
} |
130 |
} |
131 |
|
132 |
extern inline void |
133 |
dlinkAddTail(void *data, dlink_node *m, dlink_list *list) |
134 |
{ |
135 |
m->data = data; |
136 |
m->next = NULL; |
137 |
m->prev = list->tail; |
138 |
/* Assumption: If list->tail != NULL, list->head != NULL */ |
139 |
if (list->tail != NULL) |
140 |
list->tail->next = m; |
141 |
else if (list->head == NULL) |
142 |
list->head = m; |
143 |
list->tail = m; |
144 |
list->length++; |
145 |
} |
146 |
|
147 |
/* Execution profiles show that this function is called the most |
148 |
* often of all non-spontaneous functions. So it had better be |
149 |
* efficient. */ |
150 |
extern inline void |
151 |
dlinkDelete(dlink_node *m, dlink_list *list) |
152 |
{ |
153 |
/* Assumption: If m->next == NULL, then list->tail == m |
154 |
* and: If m->prev == NULL, then list->head == m |
155 |
*/ |
156 |
if (m->next) |
157 |
m->next->prev = m->prev; |
158 |
else { |
159 |
assert(list->tail == m); |
160 |
list->tail = m->prev; |
161 |
} |
162 |
if (m->prev) |
163 |
m->prev->next = m->next; |
164 |
else { |
165 |
assert(list->head == m); |
166 |
list->head = m->next; |
167 |
} |
168 |
/* Set this to NULL does matter */ |
169 |
m->next = m->prev = NULL; |
170 |
list->length--; |
171 |
} |
172 |
|
173 |
/* |
174 |
* dlinkFind |
175 |
* inputs - list to search |
176 |
* - data |
177 |
* output - pointer to link or NULL if not found |
178 |
* side effects - Look for ptr in the linked listed pointed to by link. |
179 |
*/ |
180 |
extern inline dlink_node * |
181 |
dlinkFind(dlink_list *list, void *data) |
182 |
{ |
183 |
dlink_node *ptr; |
184 |
|
185 |
DLINK_FOREACH(ptr, list->head) |
186 |
{ |
187 |
if (ptr->data == data) |
188 |
return(ptr); |
189 |
} |
190 |
|
191 |
return(NULL); |
192 |
} |
193 |
|
194 |
extern inline void |
195 |
dlinkMoveList(dlink_list *from, dlink_list *to) |
196 |
{ |
197 |
/* There are three cases */ |
198 |
/* case one, nothing in from list */ |
199 |
|
200 |
if (from->head == NULL) |
201 |
return; |
202 |
|
203 |
/* case two, nothing in to list */ |
204 |
/* actually if to->head is NULL and to->tail isn't, thats a bug */ |
205 |
|
206 |
if (to->head == NULL) |
207 |
{ |
208 |
to->head = from->head; |
209 |
to->tail = from->tail; |
210 |
from->head = from->tail = NULL; |
211 |
to->length = from->length; |
212 |
from->length = 0; |
213 |
return; |
214 |
} |
215 |
|
216 |
/* third case play with the links */ |
217 |
|
218 |
from->tail->next = to->head; |
219 |
from->head->prev = to->head->prev; |
220 |
to->head->prev = from->tail; |
221 |
to->head = from->head; |
222 |
from->head = from->tail = NULL; |
223 |
to->length += from->length; |
224 |
from->length = 0; |
225 |
|
226 |
/* I think I got that right */ |
227 |
} |
228 |
|
229 |
extern inline dlink_node * |
230 |
dlinkFindDelete(dlink_list *list, void *data) |
231 |
{ |
232 |
dlink_node *m; |
233 |
|
234 |
DLINK_FOREACH(m, list->head) |
235 |
{ |
236 |
if (m->data == data) |
237 |
{ |
238 |
if (m->next) |
239 |
m->next->prev = m->prev; |
240 |
else |
241 |
{ |
242 |
assert(list->tail == m); |
243 |
list->tail = m->prev; |
244 |
} |
245 |
if (m->prev) |
246 |
m->prev->next = m->next; |
247 |
else |
248 |
{ |
249 |
assert(list->head == m); |
250 |
list->head = m->next; |
251 |
} |
252 |
/* Set this to NULL does matter */ |
253 |
m->next = m->prev = NULL; |
254 |
list->length--; |
255 |
|
256 |
return(m); |
257 |
} |
258 |
} |
259 |
|
260 |
return(NULL); |
261 |
} |
262 |
|
263 |
#endif /* __GNUC__ */ |
264 |
|
265 |
#endif /* __TOOLS_H__ */ |