X-Git-Url: http://git.silcnet.org/gitweb/?p=silc.git;a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilclist.h;h=60e1bcc4f31e3ef32b44564ad5ebca45a77a62b8;hp=76dcf69239ed1f92e490336ab2a05225671a2be6;hb=413da0f8686910f5e627393157566ae729ca99c4;hpb=050bd9d9e5d843220f3f393a18ab5011622237b9 diff --git a/lib/silcutil/silclist.h b/lib/silcutil/silclist.h index 76dcf692..60e1bcc4 100644 --- a/lib/silcutil/silclist.h +++ b/lib/silcutil/silclist.h @@ -1,16 +1,15 @@ /* - silclist.h + silclist.h - Author: Timo Sirainen + Author: Pekka Riikonen - Copyright (C) 2002 Timo Sirainen + Copyright (C) 2002 - 2003 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 @@ -41,16 +40,16 @@ * 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; + void *head; /* Start of the list */ + void *tail; /* End of the list */ + void *current; /* Current pointer in list */ + unsigned int next_offset : 16; /* Offset to 'next' pointer */ + unsigned int prev_offset : 16; /* 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 @@ -69,41 +68,21 @@ typedef struct { #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 * @@ -116,16 +95,53 @@ typedef struct { * silc_list_init(list, struct SilcInternalEntryStruct, next); * ***/ -#define silc_list_init(list, type, field) \ - __silc_list_init(&(list), silc_offsetof(type, field)) - -static inline void __silc_list_init(SilcList *list, int offset) -{ - list->head = list->tail = list->current = SILC_LIST_END; - list->offset = offset; -} +#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) -#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(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 * @@ -138,17 +154,7 @@ static inline void __silc_list_init(SilcList *list, int offset) * 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 * @@ -159,10 +165,37 @@ static inline int __silc_list_count(SilcList *list) * 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, (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_start(list) (list).current = (list).head; +#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 * @@ -176,17 +209,18 @@ static inline int __silc_list_count(SilcList *list) * 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_del * @@ -199,32 +233,31 @@ static inline void __silc_list_add(SilcList *list, void *data) * 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 * @@ -233,28 +266,32 @@ static inline void __silc_list_del(SilcList *list, void *data) * 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) + * 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; }