X-Git-Url: http://git.silcnet.org/gitweb/?a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilcdlist.h;h=a27aaad41ca86fd5f9139a986e53fe3bf10e8322;hb=e7b6c157b80152bf9fb9266e6bdd93f9fb0db776;hp=d9f6d55267bfd19cbe45526237c4d5381b28a1c6;hpb=303401f3d85675fbe2afcc27cdfe89ef2f0ca5c1;p=silc.git diff --git a/lib/silcutil/silcdlist.h b/lib/silcutil/silcdlist.h index d9f6d552..a27aaad4 100644 --- a/lib/silcutil/silcdlist.h +++ b/lib/silcutil/silcdlist.h @@ -2,15 +2,14 @@ silcdlist.h - Author: Pekka Riikonen + Author: Pekka Riikonen - Copyright (C) 2000 Pekka Riikonen + Copyright (C) 2000 - 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 @@ -22,22 +21,35 @@ #define SILDCLIST_H #include "silclist.h" - + /****h* silcutil/SILC Dynamic List Interface * * DESCRIPTION * - * SILC Dynamic List API can be used to add opaque contexts to list that - * will automatically allocate list entries. Normal SILC List API cannot - * be used for this purpose because in that case the context passed to the - * list must be defined as list structure already. This is not the case in - * SilcDList. + * SILC Dynamic List API can be used to add opaque contexts to list that + * will automatically allocate list entries. The simpler SilcList cannot + * be used for this purpose because in that case the context passed to the + * list must be defined as list structure already. This is not the case in + * SilcDList. But SilcDList is a bit slower than SilcList because it + * requires memory allocation when adding new entries to the list. + * + * SILC Dynamic List is not thread-safe. If the same list context must be + * used in multithreaded environment concurrency control must be employed. + * + * EXAMPLE + * + * SilcDList list = silc_dlist_init(); * - * This is slower than SilcList because this requires one extra memory - * allocation when adding new entries to the list. The context is probably - * allocated already and the new list entry requires one additional memory - * allocation. The memory allocation and freeing is done automatically in - * the API and does not show to the caller. + * silc_dlist_add(list, entry1); + * silc_dlist_add(list, entry2); + * + * // Traverse the list from the beginning to the end + * silc_dlist_start(list) + * while ((entry = silc_dlist_get(list)) != SILC_LIST_END) { + * ... + * } + * + * silc_dlist_uninit(list); * ***/ @@ -53,40 +65,80 @@ * Application defines this object and adds contexts to this list with * Dynamic List Interface functions. * - * SOURCE - */ -typedef struct { + ***/ +typedef struct SilcDListStruct { + SilcStack stack; SilcList list; + void *current; + void *prev; } *SilcDList; -/***/ /* SilcDListEntry structure, one entry in the list. This MUST NOT be used directly by the application. */ typedef struct SilcDListEntryStruct { void *context; struct SilcDListEntryStruct *next; + struct SilcDListEntryStruct *prev; } *SilcDListEntry; /****f* silcutil/SilcDListAPI/silc_dlist_init * * SYNOPSIS - * + * + * static inline + * SilcDList silc_dlist_init(void); + * + * DESCRIPTION + * + * Initializes SilcDList. Returns the SilcDList context or NULL if system + * is out of memory. + * + ***/ + +static inline +SilcDList silc_dlist_init(void) +{ + SilcDList list; + + list = (SilcDList)silc_malloc(sizeof(*list)); + if (!list) + return NULL; + list->stack = list->current = list->prev = NULL; + silc_list_init_prev(list->list, struct SilcDListEntryStruct, next, prev); + + return list; +} + +/****f* silcutil/SilcDListAPI/silc_dlist_sinit + * + * SYNOPSIS + * * static inline - * SilcDList silc_dlist_init(); + * SilcDList silc_dlist_sinit(SilcStack stack); * * DESCRIPTION * - * Initializes SilcDList. + * Initializes SilcDList. Returns the SilcDList context or NULL on error. + * This is same as silc_dlist_init but allocates the memory from `stack' + * if `stack' is non-NULL. * ***/ static inline -SilcDList silc_dlist_init() +SilcDList silc_dlist_sinit(SilcStack stack) { SilcDList list; - list = (SilcDList)silc_calloc(1, sizeof(*list)); - silc_list_init(list->list, struct SilcDListEntryStruct, next); + if (stack) + stack = silc_stack_alloc(0, stack); + list = (SilcDList)silc_smalloc(stack, sizeof(*list)); + if (!list) { + silc_stack_free(stack); + return NULL; + } + list->stack = stack; + list->current = list->prev = NULL; + silc_list_init_prev(list->list, struct SilcDListEntryStruct, next, prev); return list; } @@ -101,7 +153,9 @@ SilcDList silc_dlist_init() * DESCRIPTION * * Uninits and frees all memory. Must be called to free memory. Does NOT - * free the contexts saved by caller. + * free the contexts saved by caller. If the silc_dlist_sinit was used + * with SilcStack this will release all memory allocated by the SilcDList + * back to the SilcStack. * ***/ @@ -110,12 +164,14 @@ void silc_dlist_uninit(SilcDList list) { if (list) { SilcDListEntry e; + SilcStack stack = list->stack; silc_list_start(list->list); while ((e = (SilcDListEntry)silc_list_get(list->list)) != SILC_LIST_END) { silc_list_del(list->list, e); - silc_free(e); + silc_sfree(stack, e); } - silc_free(list); + silc_sfree(stack, list); + silc_stack_free(stack); } } @@ -148,7 +204,7 @@ int silc_dlist_count(SilcDList list) * DESCRIPTION * * Set the start of the list. This prepares the list for traversing entries - * from the start of the list. + * from the start of the list towards end of the list. * ***/ @@ -156,6 +212,28 @@ static inline void silc_dlist_start(SilcDList list) { silc_list_start(list->list); + list->current = list->prev = NULL; +} + +/****f* silcutil/SilcDListAPI/silc_dlist_end + * + * SYNOPSIS + * + * static inline + * void silc_dlist_end(SilcDList list); + * + * DESCRIPTION + * + * Set the end of the list. This prepares the list for traversing entries + * from the end of the list towards start of the list. + * + ***/ + +static inline +void silc_dlist_end(SilcDList list) +{ + silc_list_end(list->list); + list->current = list->prev = NULL; } /****f* silcutil/SilcDListAPI/silc_dlist_add @@ -163,7 +241,7 @@ void silc_dlist_start(SilcDList list) * SYNOPSIS * * static inline - * void silc_dlist_add(SilcDList list, void *context); + * SilcBool silc_dlist_add(SilcDList list, void *context); * * DESCRIPTION * @@ -173,11 +251,40 @@ void silc_dlist_start(SilcDList list) ***/ static inline -void silc_dlist_add(SilcDList list, void *context) +SilcBool silc_dlist_add(SilcDList list, void *context) { - SilcDListEntry e = (SilcDListEntry)silc_calloc(1, sizeof(*e)); + SilcDListEntry e = (SilcDListEntry)silc_smalloc(list->stack, sizeof(*e)); + if (silc_unlikely(!e)) + return FALSE; e->context = context; silc_list_add(list->list, e); + return TRUE; +} + +/****f* silcutil/SilcDList/silc_dlist_insert + * + * SYNOPSIS + * + * static inline + * SilcBool silc_dlist_insert(SilcDList list, void *context); + * + * DESCRIPTION + * + * Insert new entry to the list between current and previous entry. + * If list is at the start this adds the entry at head of the list. + * Use silc_dlist_add to add at the end of the list. + * + ***/ + +static inline +SilcBool silc_dlist_insert(SilcDList list, void *context) +{ + SilcDListEntry e = (SilcDListEntry)silc_smalloc(list->stack, sizeof(*e)); + if (silc_unlikely(!e)) + return FALSE; + e->context = context; + silc_list_insert(list->list, list->prev, e); + return TRUE; } /****f* silcutil/SilcDListAPI/silc_dlist_del @@ -185,27 +292,31 @@ void silc_dlist_add(SilcDList list, void *context) * SYNOPSIS * * static inline - * void silc_dlist_del(SilcDList list, void *context); + * void silc_dlist_del(SilcDList list, void *entry); * * DESCRIPTION * - * Remove entry from the list. Returns < 0 on error, 0 otherwise. + * Remove entry from the list. * ***/ static inline -void silc_dlist_del(SilcDList list, void *context) +void silc_dlist_del(SilcDList list, void *entry) { SilcDListEntry e; silc_list_start(list->list); while ((e = (SilcDListEntry)silc_list_get(list->list)) != SILC_LIST_END) { - if (e->context == context) { + if (e->context == entry) { silc_list_del(list->list, e); #if defined(SILC_DEBUG) memset(e, 'F', sizeof(*e)); #endif - silc_free(e); + if (list->current == e) + list->current = NULL; + if (list->prev == e) + list->prev = NULL; + silc_sfree(list->stack, e); break; } } @@ -223,12 +334,12 @@ void silc_dlist_del(SilcDList list, void *context) * Returns current entry from the list and moves the list pointer forward * so that calling this next time returns the next entry from the list. * This can be used to traverse the list. Return SILC_LIST_END when the - * entire list has been traversed. Later, silc_list_start must be called - * again when re-starting list traversing. + * entire list has been traversed. Later, silc_list_start (or + * silc_dlist_end) must be called again when re-starting list traversing. * * EXAMPLE * - * // Traverse the list from the beginning to the end + * // Traverse the list from the beginning to the end * silc_dlist_start(list) * while ((entry = silc_dlist_get(list)) != SILC_LIST_END) { * ... @@ -239,7 +350,9 @@ void silc_dlist_del(SilcDList list, void *context) static inline void *silc_dlist_get(SilcDList list) { - SilcDListEntry e = (SilcDListEntry)silc_list_get(list->list); + SilcDListEntry e; + list->prev = list->current; + list->current = e = (SilcDListEntry)silc_list_get(list->list); if (e != SILC_LIST_END) return e->context; return SILC_LIST_END;