1 /*
2
3 silclist.h
4
5 Author: Pekka Riikonen <priikone@silcnet.org>
6
7 Copyright (C) 2002 - 2007 Pekka Riikonen
8
9 The contents of this file are subject to one of the Licenses specified
10 in the COPYING file; You may not use this file except in compliance
11 with the License.
12
13 The software distributed under the License is distributed on an "AS IS"
14 basis, in the hope that it will be useful, but WITHOUT WARRANTY OF ANY
15 KIND, either expressed or implied. See the COPYING file for more
16 information.
17
18 */
19
20 /****h* silcutil/SILC List Interface
21 *
22 * DESCRIPTION
23 *
24 * Implementation of the SilcList interface. This interface provides
25 * simple linked list. This interface does not allocate any memory.
26 *
27 * SILC List is not thread-safe. If the same list context must be used
28 * in multithreaded environment concurrency control must be employed.
29 *
30 ***/
31
32 #ifndef SILCLIST_H
33 #define SILCLIST_H
34
35 /****s* silcutil/SilcList/SilcList
36 *
37 * NAME
38 *
39 * typedef struct { ... } SilcList;
40 *
41 * DESCRIPTION
42 *
43 * This is the SilcList context, and is initialized by calling the
44 * function silc_list_init.
45 *
46 ***/
47 typedef struct SilcListStruct {
48 void *head; /* Start of the list */
49 void *tail; /* End of the list */
50 void *current; /* Current pointer in list */
51 SilcUInt16 next_offset; /* Offset to 'next' pointer */
52 SilcUInt16 prev_offset; /* Offset to 'prev' pointer */
53 unsigned int prev_set : 1; /* Set if 'prev' exists */
54 unsigned int end_set : 1; /* Set if silc_list_end was called */
55 unsigned int count : 30; /* Number of entries in the list */
56 } SilcList;
57
58 /****d* silcutil/SilcList/SILC_LIST_END
59 *
60 * NAME
61 *
62 * #define SILC_LIST_END ...
63 *
64 * DESCRIPTION
65 *
66 * Functions return this when the list is invalid or when traversing
67 * the list there is no more entires in the list.
68 *
69 * SOURCE
70 */
71 #define SILC_LIST_END NULL
72 /***/
73
74 /****f* silcutil/SilcList/silc_list_init
75 *
76 * SYNOPSIS
77 *
78 * #define silc_list_init(list, type, nextfield) ...
79 *
80 * DESCRIPTION
81 *
82 * This macro initializes the SilcList list. The `list' is the defined
83 * list, second argument is the structure of the entries in the list,
84 * and last argument is the pointer in the structure that is used
85 * as next list members. When using SilcList you must not touch the
86 * structure member pointers manually. If your list has also a prev
87 * pointer should use silc_list_init_prev instead of this call if
88 * you need to be able traverse the list backwards as well.
89 *
90 * EXAMPLE
91 *
92 * struct SilcInternalEntryStruct {
93 * char *dummy;
94 * struct SilcInternalEntryStruct *next; // The list member pointer
95 * };
96 *
97 * SilcList list;
98 * silc_list_init(list, struct SilcInternalEntryStruct, next);
99 *
100 ***/
101 #define silc_list_init(list, type, nextfield) \
102 do { \
103 (list).count = 0; \
104 (list).next_offset = silc_offsetof(type, nextfield); \
105 (list).prev_set = 0; \
106 (list).prev_offset = 0; \
107 (list).end_set = 0; \
108 (list).head = (list).tail = (list).current = NULL; \
109 } while(0)
110
111 /****f* silcutil/SilcList/silc_list_init_prev
112 *
113 * SYNOPSIS
114 *
115 * #define silc_list_init_prev(list, type, nextfield, prevfield) ...
116 *
117 * DESCRIPTION
118 *
119 * This macro initializes the SilcList list. The `list' is the defined
120 * list, second argument is the structure of the entries in the list,
121 * and last two arguments are the pointers in the structure that is used
122 * as next and prev list members. When using SilcList you must not
123 * touch the structure member pointers manually.
124 *
125 * Having both next and prev pointers makes it possible to traverse
126 * list from both ends of the list (from start to end, and from end
127 * to start).
128 *
129 * EXAMPLE
130 *
131 * struct SilcInternalEntryStruct {
132 * char *dummy;
133 * struct SilcInternalEntryStruct *next; // The list member pointer
134 * struct SilcInternalEntryStruct *prev; // The list member pointer
135 * };
136 *
137 * SilcList list;
138 * silc_list_init_prev(list, struct SilcInternalEntryStruct, next, prev);
139 *
140 ***/
141 #define silc_list_init_prev(list, type, nextfield, prevfield) \
142 do { \
143 (list).count = 0; \
144 (list).next_offset = silc_offsetof(type, nextfield); \
145 (list).prev_offset = silc_offsetof(type, prevfield); \
146 (list).prev_set = 1; \
147 (list).end_set = 0; \
148 (list).head = (list).tail = (list).current = NULL; \
149 } while(0)
150
151 /****f* silcutil/SilcList/silc_list_count
152 *
153 * SYNOPSIS
154 *
155 * #define silc_list_count(list) ...
156 *
157 * DESCRIPTION
158 *
159 * Returns the number of entries in the list indicated by `list'.
160 *
161 ***/
162 #define silc_list_count(list) (list).count
163
164 /****f* silcutil/SilcList/silc_list_start
165 *
166 * SYNOPSIS
167 *
168 * #define silc_list_start(list) ...
169 *
170 * DESCRIPTION
171 *
172 * Sets the start of the list. This prepares the list for traversing
173 * the entries from the start of the list towards end of the list.
174 *
175 ***/
176 #define silc_list_start(list) \
177 ((list).current = (list).head, (list).end_set = 0)
178
179 /****f* silcutil/SilcList/silc_list_end
180 *
181 * SYNOPSIS
182 *
183 * #define silc_list_end(list) ...
184 *
185 * DESCRIPTION
186 *
187 * Sets the end of the list. This prepares the list for traversing
188 * the entries from the end of the list towards start of the list.
189 *
190 * NOTES
191 *
192 * You can use this call only if you initialized the list with
193 * silc_list_init_prev.
194 *
195 ***/
196 #define silc_list_end(list) \
197 ((list).current = (list).tail, (list).end_set = 1)
198
199 /* Macros to get position to next and prev list pointers */
200 #define __silc_list_next(list, pos) \
201 ((void **)((unsigned char *)(pos) + (list).next_offset))
202 #define __silc_list_prev(list, pos) \
203 ((void **)((unsigned char *)(pos) + (list).prev_offset))
204
205 /****f* silcutil/SilcList/silc_list_add
206 *
207 * SYNOPSIS
208 *
209 * #define silc_list_add(list, entry) ...
210 *
211 * DESCRIPTION
212 *
213 * Adds new entry indicated by `entry' to the end of the list indicated
214 * by `list'.
215 *
216 ***/
217 #define silc_list_add(list, entry) \
218 do { \
219 if (!(list).head) \
220 (list).head = (entry); \
221 else \
222 *__silc_list_next(list, (list).tail) = (entry); \
223 if ((list).prev_set) \
224 *__silc_list_prev(list, entry) = (list).tail; \
225 (list).tail = (entry); \
226 *__silc_list_next(list, entry) = NULL; \
227 (list).count++; \
228 } while(0)
229
230 /****f* silcutil/SilcList/silc_list_insert
231 *
232 * SYNOPSIS
233 *
234 * #define silc_list_insert(list, current, entry) ...
235 *
236 * DESCRIPTION
237 *
238 * Insert new entry indicated by `entry' after the entry `current'
239 * to the list indicated by `list'. If `current' is NULL, then the
240 * `entry' is added at the head of the list. Use the silc_list_add
241 * to add at the end of the list.
242 *
243 ***/
244 #define silc_list_insert(list, current, entry) \
245 do { \
246 if (!(current)) { \
247 if ((list).head) \
248 *__silc_list_next(list, entry) = (list).head; \
249 else \
250 *__silc_list_next(list, entry) = NULL; \
251 if ((list).prev_set && (list).head) \
252 *__silc_list_prev(list, (list).head) = entry; \
253 if (!(list).tail) \
254 (list).tail = (entry); \
255 (list).head = (entry); \
256 if ((list).prev_set) \
257 *__silc_list_prev(list, entry) = NULL; \
258 } else { \
259 *__silc_list_next(list, entry) = *__silc_list_next(list, current); \
260 *__silc_list_next(list, current) = entry; \
261 if ((list).prev_set) { \
262 *__silc_list_prev(list, entry) = current; \
263 if (*__silc_list_next(list, entry)) \
264 *__silc_list_prev(list, *__silc_list_next(list, entry)) = entry; \
265 } \
266 if ((list).tail == (current)) \
267 (list).tail = (entry); \
268 } \
269 (list).count++; \
270 } while(0)
271
272 /****f* silcutil/SilcList/silc_list_del
273 *
274 * SYNOPSIS
275 *
276 * #define silc_list_del(list, entry) ...
277 *
278 * DESCRIPTION
279 *
280 * Remove entry indicated by `entry' from the list indicated by `list'.
281 *
282 ***/
283 #define silc_list_del(list, entry) \
284 do { \
285 void **p, *prev; \
286 prev = NULL; \
287 for (p = &(list).head; *p; p = __silc_list_next(list, *p)) { \
288 if (*p == (entry)) { \
289 *p = *__silc_list_next(list, entry); \
290 if (*p && (list).prev_set) \
291 *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry); \
292 if ((list).current == (entry)) \
293 (list).current = *p; \
294 (list).count--; \
295 break; \
296 } \
297 prev = *p; \
298 } \
299 if (entry == (list).tail) \
300 (list).tail = prev; \
301 } while(0)
302
303 /****f* silcutil/SilcList/silc_list_get
304 *
305 * SYNOPSIS
306 *
307 * #define silc_list_get(list) ...
308 *
309 * DESCRIPTION
310 *
311 * Returns the current entry from the list indicated by `list' and
312 * moves the list pointer forward so that calling this next time will
313 * return the next entry from the list. This can be used to traverse
314 * the list. Returns SILC_LIST_END when the entire list has been
315 * tarversed and no additional entries exist in the list. Later,
316 * silc_list_start (or silc_list_end) must be called again when
317 * re-starting the list tarversing.
318 *
319 * EXAMPLE
320 *
321 * // Traverse the list from the beginning to the end
322 * silc_list_start(list);
323 * while ((entry = silc_list_get(list)) != SILC_LIST_END) {
324 * ...
325 * }
326 *
327 * // Traverse the list from the end to the beginning
328 * silc_list_end(list);
329 * while ((entry = silc_list_get(list)) != SILC_LIST_END) {
330 * ...
331 * }
332 *
333 ***/
334 #define silc_list_get(x) __silc_list_get(&(x))
335 static inline
__silc_list_get(SilcList * list)336 void *__silc_list_get(SilcList *list)
337 {
338 void *pos = list->current;
339 if (pos)
340 list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
341 *__silc_list_next(*list, pos));
342 return pos;
343 }
344
345 #endif
346