5 Author: Pekka Riikonen <priikone@silcnet.org>
7 Copyright (C) 2002 - 2007 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/SILC List Interface
24 * Implementation of the SilcList interface. This interface provides
25 * simple linked list. This interface does not allocate any memory.
27 * SILC List is not thread-safe. If the same list context must be used
28 * in multithreaded environment concurrency control must be employed.
35 /****s* silcutil/SilcList/SilcList
39 * typedef struct { ... } SilcList;
43 * This is the SilcList context, and is initialized by calling the
44 * function silc_list_init.
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 */
58 /****d* silcutil/SilcList/SILC_LIST_END
62 * #define SILC_LIST_END ...
66 * Functions return this when the list is invalid or when traversing
67 * the list there is no more entires in the list.
71 #define SILC_LIST_END NULL
74 /****f* silcutil/SilcList/silc_list_init
78 * #define silc_list_init(list, type, nextfield) ...
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.
92 * struct SilcInternalEntryStruct {
94 * struct SilcInternalEntryStruct *next; // The list member pointer
98 * silc_list_init(list, struct SilcInternalEntryStruct, next);
101 #define silc_list_init(list, type, nextfield) \
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; \
111 /****f* silcutil/SilcList/silc_list_init_prev
115 * #define silc_list_init_prev(list, type, nextfield, prevfield) ...
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.
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
131 * struct SilcInternalEntryStruct {
133 * struct SilcInternalEntryStruct *next; // The list member pointer
134 * struct SilcInternalEntryStruct *prev; // The list member pointer
138 * silc_list_init_prev(list, struct SilcInternalEntryStruct, next, prev);
141 #define silc_list_init_prev(list, type, nextfield, prevfield) \
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; \
151 /****f* silcutil/SilcList/silc_list_count
155 * #define silc_list_count(list) ...
159 * Returns the number of entries in the list indicated by `list'.
162 #define silc_list_count(list) (list).count
164 /****f* silcutil/SilcList/silc_list_start
168 * #define silc_list_start(list) ...
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.
176 #define silc_list_start(list) \
177 ((list).current = (list).head, (list).end_set = 0)
179 /****f* silcutil/SilcList/silc_list_end
183 * #define silc_list_end(list) ...
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.
192 * You can use this call only if you initialized the list with
193 * silc_list_init_prev.
196 #define silc_list_end(list) \
197 ((list).current = (list).tail, (list).end_set = 1)
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))
205 /****f* silcutil/SilcList/silc_list_add
209 * #define silc_list_add(list, entry) ...
213 * Adds new entry indicated by `entry' to the end of the list indicated
217 #define silc_list_add(list, entry) \
220 (list).head = (entry); \
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; \
230 /****f* silcutil/SilcList/silc_list_insert
234 * #define silc_list_insert(list, current, entry) ...
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.
244 #define silc_list_insert(list, current, entry) \
248 *__silc_list_next(list, entry) = (list).head; \
250 *__silc_list_next(list, entry) = NULL; \
251 if ((list).prev_set && (list).head) \
252 *__silc_list_prev(list, (list).head) = entry; \
254 (list).tail = (entry); \
255 (list).head = (entry); \
256 if ((list).prev_set) \
257 *__silc_list_prev(list, entry) = NULL; \
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; \
266 if ((list).tail == (current)) \
267 (list).tail = (entry); \
272 /****f* silcutil/SilcList/silc_list_del
276 * #define silc_list_del(list, entry) ...
280 * Remove entry indicated by `entry' from the list indicated by `list'.
283 #define silc_list_del(list, entry) \
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; \
299 if (entry == (list).tail) \
300 (list).tail = prev; \
303 /****f* silcutil/SilcList/silc_list_get
307 * #define silc_list_get(list) ...
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.
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) {
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) {
334 #define silc_list_get(x) __silc_list_get(&(x))
336 void *__silc_list_get(SilcList *list)
338 void *pos = list->current;
340 list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
341 *__silc_list_next(*list, pos));