lib/silcutil/silcdlist.h

   1 /*
   2
   3   silcdlist.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2000 - 2008 Pekka Riikonen
   8
   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.
  12
  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.
  17
  18 */
  19
  20 #ifndef SILDCLIST_H
  21 #define SILDCLIST_H
  22
  23 #include "silclist.h"
  24
  25 /****h* silcutil/Dynamic List Interface
  26  *
  27  * DESCRIPTION
  28  *
  29  * SILC Dynamic List API can be used to add opaque contexts to list that
  30  * will automatically allocate list entries.  The simpler SilcList cannot
  31  * be used for this purpose because in that case the context passed to the
  32  * list must be defined as list structure already.  This is not the case in
  33  * SilcDList.  But SilcDList is a bit slower than SilcList because it
  34  * requires memory allocation when adding new entries to the list.
  35  *
  36  * SILC Dynamic List is not thread-safe.  If the same list context must be
  37  * used in multithreaded environment concurrency control must be employed.
  38  *
  39  * EXAMPLE
  40  *
  41  * SilcDList list = silc_dlist_init();
  42  *
  43  * silc_dlist_add(list, entry1);
  44  * silc_dlist_add(list, entry2);
  45  *
  46  * // Traverse the list from the beginning to the end
  47  * silc_dlist_start(list)
  48  * while ((entry = silc_dlist_get(list)) != SILC_LIST_END) {
  49  *      ...
  50  * }
  51  *
  52  * silc_dlist_uninit(list);
  53  *
  54  ***/
  55
  56 /****s* silcutil/SilcDList
  57  *
  58  * NAME
  59  *
  60  *    typedef struct { ... } *SilcDList, SilcDListStruct;
  61  *
  62  * DESCRIPTION
  63  *
  64  *    This is the actual SilcDList object that is used by application.
  65  *    Application defines this object and adds contexts to this list with
  66  *    Dynamic List Interface functions.
  67  *
  68  ***/
  69 typedef struct SilcDListObject {
  70   SilcStack stack;
  71   SilcList list;
  72   void *current;
  73   void *prev;
  74 } *SilcDList, SilcDListStruct;
  75
  76 /* SilcDListEntry structure, one entry in the list. This MUST NOT be used
  77    directly by the application. */
  78 typedef struct SilcDListEntryStruct {
  79   void *context;
  80   struct SilcDListEntryStruct *next;
  81   struct SilcDListEntryStruct *prev;
  82 } *SilcDListEntry;
  83
  84 /****f* silcutil/silc_dlist_init
  85  *
  86  * SYNOPSIS
  87  *
  88  *    static inline
  89  *    SilcDList silc_dlist_init(void);
  90  *
  91  * DESCRIPTION
  92  *
  93  *    Initializes SilcDList.  Returns the SilcDList context or NULL if system
  94  *    is out of memory.
  95  *
  96  ***/
  97
  98 static inline
  99 SilcDList silc_dlist_init(void)
 100 {
 101   SilcDList list;
 102
 103   list = (SilcDList)silc_malloc(sizeof(*list));
 104   if (!list)
 105     return NULL;
 106   list->stack = list->current = list->prev = NULL;
 107   silc_list_init_prev(list->list, struct SilcDListEntryStruct, next, prev);
 108
 109   return list;
 110 }
 111
 112 /****f* silcutil/silc_dlist_sinit
 113  *
 114  * SYNOPSIS
 115  *
 116  *    static inline
 117  *    SilcDList silc_dlist_sinit(SilcStack stack);
 118  *
 119  * DESCRIPTION
 120  *
 121  *    Initializes SilcDList.  Returns the SilcDList context or NULL on error.
 122  *    This is same as silc_dlist_init but allocates the memory from `stack'
 123  *    if `stack' is non-NULL.
 124  *
 125  ***/
 126
 127 static inline
 128 SilcDList silc_dlist_sinit(SilcStack stack)
 129 {
 130   SilcDList list;
 131
 132   if (stack)
 133     stack = silc_stack_alloc(0, stack);
 134   list = (SilcDList)silc_smalloc(stack, sizeof(*list));
 135   if (!list) {
 136     silc_stack_free(stack);
 137     return NULL;
 138   }
 139   list->stack = stack;
 140   list->current = list->prev = NULL;
 141   silc_list_init_prev(list->list, struct SilcDListEntryStruct, next, prev);
 142
 143   return list;
 144 }
 145
 146 /****f* silcutil/silc_dlist_init_static
 147  *
 148  * SYNOPSIS
 149  *
 150  *    static inline
 151  *    void silc_dlist_init_static(SilcDlist list);
 152  *
 153  * DESCRIPTION
 154  *
 155  *    Initialize a pre-allocated allocated SilcDList.
 156  *
 157  ***/
 158
 159 static inline
 160 void silc_dlist_init_static(SilcDList list)
 161 {
 162   list->stack = list->current = list->prev = NULL;
 163   silc_list_init_prev(list->list, struct SilcDListEntryStruct, next, prev);
 164 }
 165
 166 /****f* silcutil/silc_dlist_uninit
 167  *
 168  * SYNOPSIS
 169  *
 170  *    static inline
 171  *    void silc_dlist_uninit(SilcDList list);
 172  *
 173  * DESCRIPTION
 174  *
 175  *    Uninits and frees all memory. Must be called to free memory. Does NOT
 176  *    free the contexts saved by caller.  If the silc_dlist_sinit was used
 177  *    with SilcStack this will release all memory allocated by the SilcDList
 178  *    back to the SilcStack.
 179  *
 180  ***/
 181
 182 static inline
 183 void silc_dlist_uninit(SilcDList list)
 184 {
 185   if (list) {
 186     SilcDListEntry e;
 187     SilcStack stack = list->stack;
 188     silc_list_start(list->list);
 189     while ((e = (SilcDListEntry)silc_list_get(list->list)) != SILC_LIST_END) {
 190       silc_list_del(list->list, e);
 191       silc_sfree(stack, e);
 192     }
 193     silc_sfree(stack, list);
 194     silc_stack_free(stack);
 195   }
 196 }
 197
 198 /****f* silcutil/silc_dlist_uninit_static
 199  *
 200  * SYNOPSIS
 201  *
 202  *    static inline
 203  *    void silc_dlist_uninit_static(SilcDList list);
 204  *
 205  * DESCRIPTION
 206  *
 207  *    Uninits and frees all memory. Must be called to free memory. Does NOT
 208  *    free the contexts saved by caller.  Used to uninit a list initialized
 209  *    with silc_dlist_init_static.
 210  *
 211  ***/
 212
 213 static inline
 214 void silc_dlist_uninit_static(SilcDList list)
 215 {
 216   if (list) {
 217     SilcDListEntry e;
 218     silc_list_start(list->list);
 219     while ((e = (SilcDListEntry)silc_list_get(list->list)) != SILC_LIST_END) {
 220       silc_list_del(list->list, e);
 221       silc_free(e);
 222     }
 223   }
 224 }
 225
 226 /****f* silcutil/silc_dlist_count
 227  *
 228  * SYNOPSIS
 229  *
 230  *    static inline
 231  *    int silc_dlist_count(SilcDList list);
 232  *
 233  * DESCRIPTION
 234  *
 235  * Return the number of entries in the list.
 236  *
 237  ***/
 238
 239 static inline
 240 int silc_dlist_count(SilcDList list)
 241 {
 242   return silc_list_count(list->list);
 243 }
 244
 245 /****f* silcutil/silc_dlist_start
 246  *
 247  * SYNOPSIS
 248  *
 249  *    static inline
 250  *    void silc_dlist_start(SilcDList list);
 251  *
 252  * DESCRIPTION
 253  *
 254  *    Set the start of the list. This prepares the list for traversing entries
 255  *    from the start of the list towards end of the list.
 256  *
 257  ***/
 258
 259 static inline
 260 void silc_dlist_start(SilcDList list)
 261 {
 262   silc_list_start(list->list);
 263   list->current = list->prev = NULL;
 264 }
 265
 266 /****f* silcutil/silc_dlist_end
 267  *
 268  * SYNOPSIS
 269  *
 270  *    static inline
 271  *    void silc_dlist_end(SilcDList list);
 272  *
 273  * DESCRIPTION
 274  *
 275  *    Set the end of the list. This prepares the list for traversing entries
 276  *    from the end of the list towards start of the list.
 277  *
 278  ***/
 279
 280 static inline
 281 void silc_dlist_end(SilcDList list)
 282 {
 283   silc_list_end(list->list);
 284   list->current = list->prev = NULL;
 285 }
 286
 287 /****f* silcutil/silc_dlist_add
 288  *
 289  * SYNOPSIS
 290  *
 291  *    static inline
 292  *    SilcBool silc_dlist_add(SilcDList list, void *context);
 293  *
 294  * DESCRIPTION
 295  *
 296  *    Adds new entry to the list. This is the default function to add new
 297  *    entries to the list.
 298  *
 299  ***/
 300
 301 static inline
 302 SilcBool silc_dlist_add(SilcDList list, void *context)
 303 {
 304   SilcDListEntry e = (SilcDListEntry)silc_smalloc(list->stack, sizeof(*e));
 305   if (silc_unlikely(!e))
 306     return FALSE;
 307   e->context = context;
 308   silc_list_add(list->list, e);
 309   return TRUE;
 310 }
 311
 312 /****f* silcutil/silc_dlist_insert
 313  *
 314  * SYNOPSIS
 315  *
 316  *    static inline
 317  *    SilcBool silc_dlist_insert(SilcDList list, void *context);
 318  *
 319  * DESCRIPTION
 320  *
 321  *    Insert new entry to the list between current and previous entry.
 322  *    If list is at the start this adds the entry at head of the list.
 323  *    Use silc_dlist_add to add at the end of the list.
 324  *
 325  ***/
 326
 327 static inline
 328 SilcBool silc_dlist_insert(SilcDList list, void *context)
 329 {
 330   SilcDListEntry e = (SilcDListEntry)silc_smalloc(list->stack, sizeof(*e));
 331   if (silc_unlikely(!e))
 332     return FALSE;
 333   e->context = context;
 334   silc_list_insert(list->list, list->prev, e);
 335   return TRUE;
 336 }
 337
 338 /****f* silcutil/silc_dlist_del
 339  *
 340  * SYNOPSIS
 341  *
 342  *    static inline
 343  *    void silc_dlist_del(SilcDList list, void *entry);
 344  *
 345  * DESCRIPTION
 346  *
 347  *    Remove entry from the list.
 348  *
 349  ***/
 350
 351 static inline
 352 void silc_dlist_del(SilcDList list, void *entry)
 353 {
 354   SilcDListEntry e;
 355
 356   silc_list_start(list->list);
 357   while ((e = (SilcDListEntry)silc_list_get(list->list)) != SILC_LIST_END) {
 358     if (e->context == entry) {
 359       silc_list_del(list->list, e);
 360 #if defined(SILC_DEBUG)
 361       memset(e, 'F', sizeof(*e));
 362 #endif
 363       if (list->current == e)
 364         list->current = NULL;
 365       if (list->prev == e)
 366         list->prev = NULL;
 367       silc_sfree(list->stack, e);
 368       break;
 369     }
 370   }
 371 }
 372
 373 /****f* silcutil/silc_dlist_get
 374  *
 375  * SYNOPSIS
 376  *
 377  *    static inline
 378  *    void *silc_dlist_get(SilcDList list);
 379  *
 380  * DESCRIPTION
 381  *
 382  *    Returns current entry from the list and moves the list pointer forward
 383  *    so that calling this next time returns the next entry from the list.
 384  *    This can be used to traverse the list. Return SILC_LIST_END when the
 385  *    entire list has been traversed. Later, silc_list_start (or
 386  *    silc_dlist_end) must be called again when re-starting list traversing.
 387  *
 388  * EXAMPLE
 389  *
 390  *    // Traverse the list from the beginning to the end
 391  *    silc_dlist_start(list)
 392  *    while ((entry = silc_dlist_get(list)) != SILC_LIST_END) {
 393  *      ...
 394  *    }
 395  *
 396  ***/
 397
 398 static inline
 399 void *silc_dlist_get(SilcDList list)
 400 {
 401   SilcDListEntry e;
 402   list->prev = list->current;
 403   list->current = e = (SilcDListEntry)silc_list_get(list->list);
 404   if (e != SILC_LIST_END)
 405     return e->context;
 406   return SILC_LIST_END;
 407 }
 408
 409 #endif