silclist.h
- Author: Timo Sirainen <tss@iki.fi>
+ Author: Pekka Riikonen <priikone@silcnet.org>
- Copyright (C) 2002 Timo Sirainen
+ Copyright (C) 2002 - 2007 Pekka Riikonen
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
+ the Free Software Foundation; version 2 of the License.
+
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* DESCRIPTION
*
* Implementation of the SilcList interface. This interface provides
- * simple linked list.
+ * simple linked list. This interface does not allocate any memory.
+ *
+ * SILC List is not thread-safe. If the same list context must be used
+ * in multithreaded environment concurrency control must be employed.
*
***/
/****s* silcutil/SilcList/SilcList
*
* NAME
- *
+ *
* typedef struct { ... } SilcList;
*
* DESCRIPTION
* This is the SilcList context, and is initialized by calling the
* function silc_list_init.
*
- * EXAMPLE
- *
- * SilcList list;
- * silc_list_init(list, struct SilcInternalEntryStruct, next);
- *
***/
-typedef struct {
- void *head, *tail;
- void *current;
- int offset;
+typedef struct SilcListStruct {
+ void *head; /* Start of the list */
+ void *tail; /* End of the list */
+ void *current; /* Current pointer in list */
+ SilcUInt16 next_offset; /* Offset to 'next' pointer */
+ SilcUInt16 prev_offset; /* Offset to 'prev' pointer */
+ unsigned int prev_set : 1; /* Set if 'prev' exists */
+ unsigned int end_set : 1; /* Set if silc_list_end was called */
+ unsigned int count : 30; /* Number of entries in the list */
} SilcList;
/****d* silcutil/SilcList/SILC_LIST_END
*
* NAME
- *
+ *
* #define SILC_LIST_END ...
*
* DESCRIPTION
#define SILC_LIST_END NULL
/***/
-/* Initializes SilcList object. Example:
-
- SilcList list;
-
- silc_list_init(list, struct SilcInternalEntryStruct, next);
-
- Where `list' is the defined list, and second argument is the structure
- of the entries in the list and last argument is the pointer in the entry
- structure that is used as list member. SilcInternalEntry might be as
- follows:
-
- struct SilcInternalEntryStruct {
- char *dummy;
- struct SilcInternalEntryStruct *next; // The list member pointer
- };
-
- The `next' pointer in the structure (or some other pointer for that matter)
- is given for the silc_list_init as the last argument. This pointer is used
- by the list routines to link the entries together in the list. Your code
- should not touch the member pointer manually.
-*/
-
/****f* silcutil/SilcList/silc_list_init
*
* SYNOPSIS
*
- * #define silc_list_init(list, type, field) ...
+ * #define silc_list_init(list, type, nextfield) ...
*
* DESCRIPTION
*
* This macro initializes the SilcList list. The `list' is the defined
* list, second argument is the structure of the entries in the list,
- * and last argument is the pointer in the entry structure that is used
- * as list member. When using SilcList, you should not touch the
- * structure member pointer (the `next' for example) manually.
+ * and last argument is the pointer in the structure that is used
+ * as next list members. When using SilcList you must not touch the
+ * structure member pointers manually. If your list has also a prev
+ * pointer should use silc_list_init_prev instead of this call if
+ * you need to be able traverse the list backwards as well.
*
* EXAMPLE
*
* silc_list_init(list, struct SilcInternalEntryStruct, next);
*
***/
-#define silc_list_init(list, type, field) \
- __silc_list_init(&(list), offsetof(type, field))
+#define silc_list_init(list, type, nextfield) \
+do { \
+ (list).count = 0; \
+ (list).next_offset = silc_offsetof(type, nextfield); \
+ (list).prev_set = 0; \
+ (list).prev_offset = 0; \
+ (list).head = (list).tail = (list).current = NULL; \
+} while(0)
-static inline void __silc_list_init(SilcList *list, int offset)
-{
- list->head = list->tail = list->current = SILC_LIST_END;
- list->offset = offset;
-}
-
-#define list_next(list, pos) ((void **) ((char *) (pos) + (list)->offset))
+/****f* silcutil/SilcList/silc_list_init_prev
+ *
+ * SYNOPSIS
+ *
+ * #define silc_list_init_prev(list, type, nextfield, prevfield) ...
+ *
+ * DESCRIPTION
+ *
+ * This macro initializes the SilcList list. The `list' is the defined
+ * list, second argument is the structure of the entries in the list,
+ * and last two arguments are the pointers in the structure that is used
+ * as next and prev list members. When using SilcList you must not
+ * touch the structure member pointers manually.
+ *
+ * Having both next and prev pointers makes it possible to traverse
+ * list from both ends of the list (from start to end, and from end
+ * to start).
+ *
+ * EXAMPLE
+ *
+ * struct SilcInternalEntryStruct {
+ * char *dummy;
+ * struct SilcInternalEntryStruct *next; // The list member pointer
+ * struct SilcInternalEntryStruct *prev; // The list member pointer
+ * };
+ *
+ * SilcList list;
+ * silc_list_init_prev(list, struct SilcInternalEntryStruct, next, prev);
+ *
+ ***/
+#define silc_list_init_prev(list, type, nextfield, prevfield) \
+do { \
+ (list).count = 0; \
+ (list).next_offset = silc_offsetof(type, nextfield); \
+ (list).prev_offset = silc_offsetof(type, prevfield); \
+ (list).prev_set = 1; \
+ (list).head = (list).tail = (list).current = NULL; \
+} while(0)
/****f* silcutil/SilcList/silc_list_count
*
* Returns the number of entries in the list indicated by `list'.
*
***/
-#define silc_list_count(list) __silc_list_count(&(list))
-static inline int __silc_list_count(SilcList *list)
-{
- int count = 0;
- void *pos;
-
- for (pos = list->head; pos != NULL; pos = *list_next(list, pos))
- count++;
-
- return count;
-}
+#define silc_list_count(list) (list).count
/****f* silcutil/SilcList/silc_list_start
*
* DESCRIPTION
*
* Sets the start of the list. This prepares the list for traversing
- * the entries from the start of the list.
+ * the entries from the start of the list towards end of the list.
*
***/
-#define silc_list_start(list) (list).current = (list).head;
+#define silc_list_start(list) \
+ ((list).current = (list).head, (list).end_set = 0)
+
+/****f* silcutil/SilcList/silc_list_end
+ *
+ * SYNOPSIS
+ *
+ * #define silc_list_end(list) ...
+ *
+ * DESCRIPTION
+ *
+ * Sets the end of the list. This prepares the list for traversing
+ * the entries from the end of the list towards start of the list.
+ *
+ * NOTES
+ *
+ * You can use this call only if you initialized the list with
+ * silc_list_init_prev.
+ *
+ ***/
+#define silc_list_end(list) \
+ ((list).current = (list).tail, (list).end_set = 1)
+
+/* Macros to get position to next and prev list pointers */
+#define __silc_list_next(list, pos) \
+ ((void **)((unsigned char *)(pos) + (list).next_offset))
+#define __silc_list_prev(list, pos) \
+ ((void **)((unsigned char *)(pos) + (list).prev_offset))
/****f* silcutil/SilcList/silc_list_add
*
*
* DESCRIPTION
*
- * Adds new entry indicated by `entry' to the end of the list indicated
+ * Adds new entry indicated by `entry' to the end of the list indicated
* by `list'.
*
***/
-#define silc_list_add(list, entry) __silc_list_add(&(list), entry)
-static inline void __silc_list_add(SilcList *list, void *data)
-{
- if (list->head == NULL)
- list->head = data;
- else
- *list_next(list, list->tail) = data;
-
- list->tail = data;
- *list_next(list, data) = NULL;
-}
+#define silc_list_add(list, entry) \
+do { \
+ if (!(list).head) \
+ (list).head = (entry); \
+ else \
+ *__silc_list_next(list, (list).tail) = (entry); \
+ if ((list).prev_set) \
+ *__silc_list_prev(list, entry) = (list).tail; \
+ (list).tail = (entry); \
+ *__silc_list_next(list, entry) = NULL; \
+ (list).count++; \
+} while(0)
+
+/****f* silcutil/SilcList/silc_list_insert
+ *
+ * SYNOPSIS
+ *
+ * #define silc_list_insert(list, current, entry) ...
+ *
+ * DESCRIPTION
+ *
+ * Insert new entry indicated by `entry' after the entry `current'
+ * to the list indicated by `list'. If `current' is NULL, then the
+ * `entry' is added at the head of the list. Use the silc_list_add
+ * to add at the end of the list.
+ *
+ ***/
+#define silc_list_insert(list, current, entry) \
+do { \
+ if (!(current)) { \
+ if ((list).head) \
+ *__silc_list_next(list, entry) = (list).head; \
+ else \
+ *__silc_list_next(list, entry) = NULL; \
+ if ((list).prev_set && (list).head) \
+ *__silc_list_prev(list, (list).head) = entry; \
+ if (!(list).tail) \
+ (list).tail = (entry); \
+ (list).head = (entry); \
+ if ((list).prev_set) \
+ *__silc_list_prev(list, entry) = NULL; \
+ } else { \
+ *__silc_list_next(list, entry) = *__silc_list_next(list, current); \
+ *__silc_list_next(list, current) = entry; \
+ if ((list).prev_set) { \
+ *__silc_list_prev(list, entry) = current; \
+ if (*__silc_list_next(list, entry)) \
+ *__silc_list_prev(list, *__silc_list_next(list, entry)) = entry; \
+ } \
+ if ((list).tail == (current)) \
+ (list).tail = (entry); \
+ } \
+ (list).count++; \
+} while(0)
/****f* silcutil/SilcList/silc_list_del
*
* Remove entry indicated by `entry' from the list indicated by `list'.
*
***/
-#define silc_list_del(list, data) __silc_list_del(&(list), data)
-static inline void __silc_list_del(SilcList *list, void *data)
-{
- void **pos, *prev;
-
- prev = NULL;
- for (pos = &list->head; *pos != NULL; pos = list_next(list, *pos)) {
- if (*pos == data) {
- *pos = *list_next(list, data);
- if (list->current == data)
- list->current = *pos;
- break;
- }
-
- prev = *pos;
- }
-
- if (data == list->tail)
- list->tail = prev;
-}
+#define silc_list_del(list, entry) \
+do { \
+ void **p, *prev; \
+ prev = NULL; \
+ for (p = &(list).head; *p; p = __silc_list_next(list, *p)) { \
+ if (*p == (entry)) { \
+ *p = *__silc_list_next(list, entry); \
+ if (*p && (list).prev_set) \
+ *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry); \
+ if ((list).current == (entry)) \
+ (list).current = *p; \
+ (list).count--; \
+ break; \
+ } \
+ prev = *p; \
+ } \
+ if (entry == (list).tail) \
+ (list).tail = prev; \
+} while(0)
/****f* silcutil/SilcList/silc_list_get
*
* SYNOPSIS
*
- * #define silc_list_get(list, entry) ...
+ * #define silc_list_get(list) ...
*
* DESCRIPTION
*
* return the next entry from the list. This can be used to traverse
* the list. Returns SILC_LIST_END when the entire list has been
* tarversed and no additional entries exist in the list. Later,
- * silc_list_start must be called again when re-starting the list
- * tarversing.
+ * silc_list_start (or silc_list_end) must be called again when
+ * re-starting the list tarversing.
*
* EXAMPLE
*
- * // Traverse the list from the beginning to the end
- * silc_list_start(list)
+ * // Traverse the list from the beginning to the end
+ * silc_list_start(list);
+ * while ((entry = silc_list_get(list)) != SILC_LIST_END) {
+ * ...
+ * }
+ *
+ * // Traverse the list from the end to the beginning
+ * silc_list_end(list);
* while ((entry = silc_list_get(list)) != SILC_LIST_END) {
* ...
* }
*
***/
#define silc_list_get(x) __silc_list_get(&(x))
-
static inline
void *__silc_list_get(SilcList *list)
{
- void *pos;
-
- pos = list->current;
- if (pos != NULL)
- list->current = *list_next(list, pos);
+ void *pos = list->current;
+ if (pos)
+ list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
+ *__silc_list_next(*list, pos));
return pos;
}