5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2002 - 2008 Pekka Riikonen
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; version 2 of the License.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
20 /****h* silcutil/List Interface
24 * Generic list interface that can turn any structure with list pointers
25 * into a SilcList. The interface can provide both singly and doubly linked
26 * lists. The interface does not allocate any memory.
28 * SILC List is not thread-safe. If the same list context must be used
29 * in multithreaded environment concurrency control must be employed.
33 * struct EntryStruct {
35 * struct EntryStruct *next; // The list member pointer
41 * silc_list_init(list, struct EntryStruct, next);
48 /****s* silcutil/SilcList
52 * typedef struct { ... } SilcList;
56 * This is the SilcList context, and is initialized by calling the
57 * function silc_list_init.
60 typedef struct SilcListStruct {
61 void *head; /* Start of the list */
62 void *tail; /* End of the list */
63 void *current; /* Current pointer in list */
64 SilcUInt16 next_offset; /* Offset to 'next' pointer */
65 SilcUInt16 prev_offset; /* Offset to 'prev' pointer */
66 unsigned int prev_set : 1; /* Set if 'prev' exists */
67 unsigned int end_set : 1; /* Set if silc_list_end was called */
68 unsigned int count : 30; /* Number of entries in the list */
71 /****d* silcutil/SILC_LIST_END
75 * #define SILC_LIST_END NULL
79 * Functions return this when the list is invalid or when traversing
80 * the list there is no more entires in the list.
84 #define SILC_LIST_END NULL
87 /****f* silcutil/silc_list_init
91 * #define silc_list_init(list, type, nextfield) ...
95 * This macro initializes the SilcList list. The `list' is the defined
96 * list, second argument is the structure of the entries in the list,
97 * and last argument is the pointer in the structure that is used
98 * as next list members. When using SilcList you must not touch the
99 * structure member pointers manually. If your list has also a prev
100 * pointer should use silc_list_init_prev instead of this call if
101 * you need to be able traverse the list backwards as well.
105 * struct SilcInternalEntryStruct {
107 * struct SilcInternalEntryStruct *next; // The list member pointer
111 * silc_list_init(list, struct SilcInternalEntryStruct, next);
114 #define silc_list_init(list, type, nextfield) \
117 (list).next_offset = silc_offsetof(type, nextfield); \
118 (list).prev_set = 0; \
119 (list).prev_offset = 0; \
120 (list).end_set = 0; \
121 (list).head = (list).tail = (list).current = NULL; \
124 /****f* silcutil/silc_list_init_prev
128 * #define silc_list_init_prev(list, type, nextfield, prevfield) ...
132 * This macro initializes the SilcList list. The `list' is the defined
133 * list, second argument is the structure of the entries in the list,
134 * and last two arguments are the pointers in the structure that is used
135 * as next and prev list members. When using SilcList you must not
136 * touch the structure member pointers manually.
138 * Having both next and prev pointers makes it possible to traverse
139 * list from both ends of the list (from start to end, and from end
144 * struct SilcInternalEntryStruct {
146 * struct SilcInternalEntryStruct *next; // The list member pointer
147 * struct SilcInternalEntryStruct *prev; // The list member pointer
151 * silc_list_init_prev(list, struct SilcInternalEntryStruct, next, prev);
154 #define silc_list_init_prev(list, type, nextfield, prevfield) \
157 (list).next_offset = silc_offsetof(type, nextfield); \
158 (list).prev_offset = silc_offsetof(type, prevfield); \
159 (list).prev_set = 1; \
160 (list).end_set = 0; \
161 (list).head = (list).tail = (list).current = NULL; \
164 /****f* silcutil/silc_list_count
168 * #define silc_list_count(list) ...
172 * Returns the number of entries in the list indicated by `list'.
175 #define silc_list_count(list) (list).count
177 /****f* silcutil/silc_list_start
181 * #define silc_list_start(list) ...
185 * Sets the start of the list. This prepares the list for traversing
186 * the entries from the start of the list towards end of the list.
189 #define silc_list_start(list) \
190 ((list).current = (list).head, (list).end_set = 0)
192 /****f* silcutil/silc_list_end
196 * #define silc_list_end(list) ...
200 * Sets the end of the list. This prepares the list for traversing
201 * the entries from the end of the list towards start of the list.
205 * You can use this call only if you initialized the list with
206 * silc_list_init_prev.
209 #define silc_list_end(list) \
210 ((list).current = (list).tail, (list).end_set = 1)
212 /* Macros to get position to next and prev list pointers */
213 #define __silc_list_next(list, pos) \
214 ((void **)((unsigned char *)(pos) + (list).next_offset))
215 #define __silc_list_prev(list, pos) \
216 ((void **)((unsigned char *)(pos) + (list).prev_offset))
218 /****f* silcutil/silc_list_add
222 * #define silc_list_add(list, entry) ...
226 * Adds new entry indicated by `entry' to the end of the list indicated
230 #define silc_list_add(list, entry) \
233 (list).head = (entry); \
235 *__silc_list_next(list, (list).tail) = (entry); \
236 if ((list).prev_set) \
237 *__silc_list_prev(list, entry) = (list).tail; \
238 (list).tail = (entry); \
239 *__silc_list_next(list, entry) = NULL; \
243 /****f* silcutil/silc_list_insert
247 * #define silc_list_insert(list, current, entry) ...
251 * Insert new entry indicated by `entry' after the entry `current'
252 * to the list indicated by `list'. If `current' is NULL, then the
253 * `entry' is added at the head of the list. Use the silc_list_add
254 * to add at the end of the list.
257 #define silc_list_insert(list, current, entry) \
261 *__silc_list_next(list, entry) = (list).head; \
263 *__silc_list_next(list, entry) = NULL; \
264 if ((list).prev_set && (list).head) \
265 *__silc_list_prev(list, (list).head) = entry; \
267 (list).tail = (entry); \
268 (list).head = (entry); \
269 if ((list).prev_set) \
270 *__silc_list_prev(list, entry) = NULL; \
272 *__silc_list_next(list, entry) = *__silc_list_next(list, current); \
273 *__silc_list_next(list, current) = entry; \
274 if ((list).prev_set) { \
275 *__silc_list_prev(list, entry) = current; \
276 if (*__silc_list_next(list, entry)) \
277 *__silc_list_prev(list, *__silc_list_next(list, entry)) = entry; \
279 if ((list).tail == (current)) \
280 (list).tail = (entry); \
285 /****f* silcutil/silc_list_del
289 * #define silc_list_del(list, entry) ...
293 * Remove entry indicated by `entry' from the list indicated by `list'.
296 #define silc_list_del(list, entry) \
300 for (p = &(list).head; *p; p = __silc_list_next(list, *p)) { \
301 if (*p == (entry)) { \
302 *p = *__silc_list_next(list, entry); \
303 if (*p && (list).prev_set) \
304 *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry); \
305 if ((list).current == (entry)) \
306 (list).current = *p; \
312 if (entry == (list).tail) \
313 (list).tail = prev; \
316 /****f* silcutil/silc_list_get
320 * #define silc_list_get(list) ...
324 * Returns the current entry from the list indicated by `list' and
325 * moves the list pointer forward so that calling this next time will
326 * return the next entry from the list. This can be used to traverse
327 * the list. Returns SILC_LIST_END when the entire list has been
328 * tarversed and no additional entries exist in the list. Later,
329 * silc_list_start (or silc_list_end) must be called again when
330 * re-starting the list tarversing.
334 * // Traverse the list from the beginning to the end
335 * silc_list_start(list);
336 * while ((entry = silc_list_get(list)) != SILC_LIST_END) {
340 * // Traverse the list from the end to the beginning
341 * silc_list_end(list);
342 * while ((entry = silc_list_get(list)) != SILC_LIST_END) {
347 #define silc_list_get(x) __silc_list_get(&(x))
349 void *__silc_list_get(SilcList *list)
351 void *pos = list->current;
353 list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
354 *__silc_list_next(*list, pos));