X-Git-Url: http://git.silcnet.org/gitweb/?a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilclist.h;h=bfe78be3b7352e2acd8bdd06f47bf034d0aeadea;hb=9df31f979d5ebd26edd45dceed544c4eb166ccd4;hp=e7d9c53bf1d1f0da084f2adee395b6aebb51bc3a;hpb=8fd8212bcd16f2b53fbedff2a9b9a4e8c15b9695;p=runtime.git diff --git a/lib/silcutil/silclist.h b/lib/silcutil/silclist.h index e7d9c53b..bfe78be3 100644 --- a/lib/silcutil/silclist.h +++ b/lib/silcutil/silclist.h @@ -4,7 +4,7 @@ Author: Pekka Riikonen - Copyright (C) 2002 - 2005 Pekka Riikonen + Copyright (C) 2002 - 2008 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 @@ -17,22 +17,35 @@ */ -/****h* silcutil/SILC List Interface +/****h* silcutil/List Interface * * DESCRIPTION * - * Implementation of the SilcList interface. This interface provides - * simple linked list. + * Generic list interface that can turn any structure with list pointers + * into a SilcList. The interface can provide both singly and doubly linked + * lists. The 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. * + * EXAMPLE + * + * struct EntryStruct { + * char *dummy; + * struct EntryStruct *next; // The list member pointer + * }; + * + * SilcList list; + * + * // Initialize list + * silc_list_init(list, struct EntryStruct, next); + * ***/ #ifndef SILCLIST_H #define SILCLIST_H -/****s* silcutil/SilcList/SilcList +/****s* silcutil/SilcList * * NAME * @@ -44,7 +57,7 @@ * function silc_list_init. * ***/ -typedef struct { +typedef struct SilcListStruct { void *head; /* Start of the list */ void *tail; /* End of the list */ void *current; /* Current pointer in list */ @@ -55,11 +68,11 @@ typedef struct { unsigned int count : 30; /* Number of entries in the list */ } SilcList; -/****d* silcutil/SilcList/SILC_LIST_END +/****d* silcutil/SILC_LIST_END * * NAME * - * #define SILC_LIST_END ... + * #define SILC_LIST_END NULL * * DESCRIPTION * @@ -71,7 +84,7 @@ typedef struct { #define SILC_LIST_END NULL /***/ -/****f* silcutil/SilcList/silc_list_init +/****f* silcutil/silc_list_init * * SYNOPSIS * @@ -104,10 +117,11 @@ do { \ (list).next_offset = silc_offsetof(type, nextfield); \ (list).prev_set = 0; \ (list).prev_offset = 0; \ + (list).end_set = 0; \ (list).head = (list).tail = (list).current = NULL; \ } while(0) -/****f* silcutil/SilcList/silc_list_init_prev +/****f* silcutil/silc_list_init_prev * * SYNOPSIS * @@ -143,14 +157,15 @@ do { \ (list).next_offset = silc_offsetof(type, nextfield); \ (list).prev_offset = silc_offsetof(type, prevfield); \ (list).prev_set = 1; \ + (list).end_set = 0; \ (list).head = (list).tail = (list).current = NULL; \ } while(0) -/****f* silcutil/SilcList/silc_list_count +/****f* silcutil/silc_list_count * * SYNOPSIS * - * #define silc_list_count(list) ... + * SilcUInt32 silc_list_count(SilcList list); * * DESCRIPTION * @@ -159,11 +174,11 @@ do { \ ***/ #define silc_list_count(list) (list).count -/****f* silcutil/SilcList/silc_list_start +/****f* silcutil/silc_list_start * * SYNOPSIS * - * #define silc_list_start(list) ... + * void silc_list_start(SilcList list); * * DESCRIPTION * @@ -174,11 +189,11 @@ do { \ #define silc_list_start(list) \ ((list).current = (list).head, (list).end_set = 0) -/****f* silcutil/SilcList/silc_list_end +/****f* silcutil/silc_list_end * * SYNOPSIS * - * #define silc_list_end(list) ... + * void silc_list_end(SilcList list); * * DESCRIPTION * @@ -200,11 +215,11 @@ do { \ #define __silc_list_prev(list, pos) \ ((void **)((unsigned char *)(pos) + (list).prev_offset)) -/****f* silcutil/SilcList/silc_list_add +/****f* silcutil/silc_list_add * * SYNOPSIS * - * #define silc_list_add(list, entry) ... + * void silc_list_add(SilcList list, void *entry); * * DESCRIPTION * @@ -225,11 +240,11 @@ do { \ (list).count++; \ } while(0) -/****f* silcutil/SilcList/silc_list_insert +/****f* silcutil/silc_list_insert * * SYNOPSIS * - * #define silc_list_insert(list, current, entry) ... + * void silc_list_insert(SilcList list, void *current, void *entry); * * DESCRIPTION * @@ -267,11 +282,11 @@ do { \ (list).count++; \ } while(0) -/****f* silcutil/SilcList/silc_list_del +/****f* silcutil/silc_list_del * * SYNOPSIS * - * #define silc_list_del(list, entry) ... + * void silc_list_del(SilcListlist, void *entry); * * DESCRIPTION * @@ -285,7 +300,7 @@ do { \ 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) \ + if ((list).prev_set && *p) \ *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry); \ if ((list).current == (entry)) \ (list).current = *p; \ @@ -298,11 +313,11 @@ do { \ (list).tail = prev; \ } while(0) -/****f* silcutil/SilcList/silc_list_get +/****f* silcutil/silc_list_get * * SYNOPSIS * - * #define silc_list_get(list) ... + * void *silc_list_get(SilcList list); * * DESCRIPTION * @@ -340,4 +355,143 @@ void *__silc_list_get(SilcList *list) return pos; } -#endif +/****f* silcutil/silc_list_pop + * + * SYNOPSIS + * + * void *silc_list_pop(SilcList list); + * + * DESCRIPTION + * + * Pops the head of the list. Removes the head of the list and returns + * the removed head. This will always remove the head of the list even + * if silc_list_end was called. Calling silc_list_start is not necessary. + * Returns SILC_LIST_END if the list is empty. + * + ***/ +#define silc_list_pop(x) __silc_list_pop(&(x)) +static inline +void *__silc_list_pop(SilcList *list) +{ + void *head, **p; + + if (!list->head) + return NULL; + + head = list->head; + p = &list->head; + *p = *__silc_list_next(*list, head); + if (list->prev_set && *p) + *__silc_list_prev(*list, *p) = *__silc_list_prev(*list, head); + + if (list->current == head) + list->current = *p; + if (head == list->tail) + list->tail = NULL; + + list->count--; + + return head; +} + +/****f* silcutil/silc_list_sort + * + * SYNOPSIS + * + * void silc_list_sort(SilcList list, SilcCompare compare, context); + * + * DESCRIPTION + * + * Sort the list. The `compare' function will be called with `context' + * to do comparison between the entries. The `compare' must return + * SILC_COMPARE_LESS_THAN, SILC_COMPARE_EQUAL_TO, or + * SILC_COMPARE_GREATER_THAN zero if the first argument is considered to + * be respectively less than, equal to, or greater than the second. + * The entries are then sorted in ascending order. The function must not + * return SILC_COMPARE_STOP. + * + * NOTES + * + * The list must be initialized with silc_list_init_prev for sorting + * to work. + * + ***/ +#define silc_list_sort(x, comp, ctx) __silc_list_sort(&(x), comp, ctx) +static inline +void __silc_list_sort(SilcList *list, SilcCompare compare, void *context) +{ + void *c_cur, *c_prev; + + SILC_ASSERT(list->prev_set); + if (!list->prev_set) + return; + + if (silc_list_count(*list) < 2) + return; + + /* Gnome sort */ + silc_list_start(*list); + c_prev = silc_list_get(*list); + while ((c_cur = silc_list_get(*list))) { + if (compare(c_prev, c_cur, context) == SILC_COMPARE_GREATER_THAN) { + list->current = *__silc_list_prev(*list, c_prev); + silc_list_del(*list, c_prev); + silc_list_insert(*list, c_cur, c_prev); + + if (list->current) { + c_prev = list->current; + list->current = c_cur; + continue; + } + list->current = c_cur; + __silc_list_get(list); + } + c_prev = c_cur; + } + + list->current = NULL; +} + +/****f* silcutil/silc_list_find + * + * SYNOPSIS + * + * void *silc_list_find(SilcList list, void *entry1, SilcCompare compare, + * void *context); + * + * DESCRIPTION + * + * Find an entry from the `list'. The `compare' function will be called + * with `context' to do comparison between the entries. If `compare' + * returns 0 the `entry1' is considered to be equal to `entry2' and the + * found entry is returned. Returns NULL if the entry could not be found. + * + * The silc_list_start or silc_list_end must be called before calling this + * if the finding should be started from the beginning or from the end. + * Calling it however is not required. The founding can be started at + * any point of the list. The silc_list_find can be called many times + * to find more entries following the previously found entries. + * + * The list can be enumerated by calling silc_list_get after the found + * entry. The silc_list_get will return the next entry after the found + * entry. + * + ***/ +#define silc_list_find(x, e, comp, ctx) __silc_list_find(&(x), (e), comp, ctx) +static inline +void *__silc_list_find(SilcList *list, void *entry1, SilcCompare compare, + void *context) +{ + void *entry2; + int ret; + while ((entry2 = __silc_list_get(list))) { + ret = compare(entry1, entry2, context); + if (ret == SILC_COMPARE_EQUAL_TO) + return entry2; + if (ret == SILC_COMPARE_STOP) + break; + } + return NULL; +} + +#endif /* SILCLIST_H */