lib/silcutil/silclist.h

   1 /*
   2
   3   silclist.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2002 - 2007 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 /****h* silcutil/SILC List Interface
  21  *
  22  * DESCRIPTION
  23  *
  24  * Generic list interface that can turn any structure with list pointers
  25  * into a SilcList.  The interface can provide both singly and doubly linked
  26  * lists.  The interface does not allocate any memory.
  27  *
  28  * SILC List is not thread-safe.  If the same list context must be used
  29  * in multithreaded environment concurrency control must be employed.
  30  *
  31  * EXAMPLE
  32  *
  33  * struct EntryStruct {
  34  *   char *dummy;
  35  *   struct EntryStruct *next;        // The list member pointer
  36  * };
  37  *
  38  * SilcList list;
  39  *
  40  * // Initialize list
  41  * silc_list_init(list, struct EntryStruct, next);
  42  *
  43  ***/
  44
  45 #ifndef SILCLIST_H
  46 #define SILCLIST_H
  47
  48 /****s* silcutil/SilcList/SilcList
  49  *
  50  * NAME
  51  *
  52  *    typedef struct { ... } SilcList;
  53  *
  54  * DESCRIPTION
  55  *
  56  *    This is the SilcList context, and is initialized by calling the
  57  *    function silc_list_init.
  58  *
  59  ***/
  60 typedef struct SilcListStruct {
  61   void *head;                        /* Start of the list */
  62   void *tail;                        /* End of the list */
  63   void *current;                     /* Current pointer in list */
  64   SilcUInt16 next_offset;            /* Offset to 'next' pointer */
  65   SilcUInt16 prev_offset;            /* Offset to 'prev' pointer */
  66   unsigned int prev_set    : 1;      /* Set if 'prev' exists */
  67   unsigned int end_set     : 1;      /* Set if silc_list_end was called */
  68   unsigned int count       : 30;     /* Number of entries in the list */
  69 } SilcList;
  70
  71 /****d* silcutil/SilcList/SILC_LIST_END
  72  *
  73  * NAME
  74  *
  75  *    #define SILC_LIST_END ...
  76  *
  77  * DESCRIPTION
  78  *
  79  *    Functions return this when the list is invalid or when traversing
  80  *    the list there is no more entires in the list.
  81  *
  82  * SOURCE
  83  */
  84 #define SILC_LIST_END NULL
  85 /***/
  86
  87 /****f* silcutil/SilcList/silc_list_init
  88  *
  89  * SYNOPSIS
  90  *
  91  *    #define silc_list_init(list, type, nextfield) ...
  92  *
  93  * DESCRIPTION
  94  *
  95  *    This macro initializes the SilcList list.  The `list' is the defined
  96  *    list, second argument is the structure of the entries in the list,
  97  *    and last argument is the pointer in the structure that is used
  98  *    as next list members.  When using SilcList you must not touch the
  99  *    structure member pointers manually.  If your list has also a prev
 100  *    pointer should use silc_list_init_prev instead of this call if
 101  *    you need to be able traverse the list backwards as well.
 102  *
 103  * EXAMPLE
 104  *
 105  *    struct SilcInternalEntryStruct {
 106  *      char *dummy;
 107  *      struct SilcInternalEntryStruct *next; // The list member pointer
 108  *    };
 109  *
 110  *    SilcList list;
 111  *    silc_list_init(list, struct SilcInternalEntryStruct, next);
 112  *
 113  ***/
 114 #define silc_list_init(list, type, nextfield)           \
 115 do {                                                    \
 116   (list).count = 0;                                     \
 117   (list).next_offset = silc_offsetof(type, nextfield);  \
 118   (list).prev_set = 0;                                  \
 119   (list).prev_offset = 0;                               \
 120   (list).end_set = 0;                                   \
 121   (list).head = (list).tail = (list).current = NULL;    \
 122 } while(0)
 123
 124 /****f* silcutil/SilcList/silc_list_init_prev
 125  *
 126  * SYNOPSIS
 127  *
 128  *    #define silc_list_init_prev(list, type, nextfield, prevfield) ...
 129  *
 130  * DESCRIPTION
 131  *
 132  *    This macro initializes the SilcList list.  The `list' is the defined
 133  *    list, second argument is the structure of the entries in the list,
 134  *    and last two arguments are the pointers in the structure that is used
 135  *    as next and prev list members.  When using SilcList you must not
 136  *    touch the structure member pointers manually.
 137  *
 138  *    Having both next and prev pointers makes it possible to traverse
 139  *    list from both ends of the list (from start to end, and from end
 140  *    to start).
 141  *
 142  * EXAMPLE
 143  *
 144  *    struct SilcInternalEntryStruct {
 145  *      char *dummy;
 146  *      struct SilcInternalEntryStruct *next; // The list member pointer
 147  *      struct SilcInternalEntryStruct *prev; // The list member pointer
 148  *    };
 149  *
 150  *    SilcList list;
 151  *    silc_list_init_prev(list, struct SilcInternalEntryStruct, next, prev);
 152  *
 153  ***/
 154 #define silc_list_init_prev(list, type, nextfield, prevfield)   \
 155 do {                                                            \
 156   (list).count = 0;                                             \
 157   (list).next_offset = silc_offsetof(type, nextfield);          \
 158   (list).prev_offset = silc_offsetof(type, prevfield);          \
 159   (list).prev_set = 1;                                          \
 160   (list).end_set = 0;                                           \
 161   (list).head = (list).tail = (list).current = NULL;            \
 162 } while(0)
 163
 164 /****f* silcutil/SilcList/silc_list_count
 165  *
 166  * SYNOPSIS
 167  *
 168  *    #define silc_list_count(list) ...
 169  *
 170  * DESCRIPTION
 171  *
 172  *    Returns the number of entries in the list indicated by `list'.
 173  *
 174  ***/
 175 #define silc_list_count(list) (list).count
 176
 177 /****f* silcutil/SilcList/silc_list_start
 178  *
 179  * SYNOPSIS
 180  *
 181  *    #define silc_list_start(list) ...
 182  *
 183  * DESCRIPTION
 184  *
 185  *    Sets the start of the list.  This prepares the list for traversing
 186  *    the entries from the start of the list towards end of the list.
 187  *
 188  ***/
 189 #define silc_list_start(list)                           \
 190   ((list).current = (list).head, (list).end_set = 0)
 191
 192 /****f* silcutil/SilcList/silc_list_end
 193  *
 194  * SYNOPSIS
 195  *
 196  *    #define silc_list_end(list) ...
 197  *
 198  * DESCRIPTION
 199  *
 200  *    Sets the end of the list.  This prepares the list for traversing
 201  *    the entries from the end of the list towards start of the list.
 202  *
 203  * NOTES
 204  *
 205  *    You can use this call only if you initialized the list with
 206  *    silc_list_init_prev.
 207  *
 208  ***/
 209 #define silc_list_end(list)                             \
 210   ((list).current = (list).tail, (list).end_set = 1)
 211
 212 /* Macros to get position to next and prev list pointers */
 213 #define __silc_list_next(list, pos)                             \
 214   ((void **)((unsigned char *)(pos) + (list).next_offset))
 215 #define __silc_list_prev(list, pos)                             \
 216   ((void **)((unsigned char *)(pos) + (list).prev_offset))
 217
 218 /****f* silcutil/SilcList/silc_list_add
 219  *
 220  * SYNOPSIS
 221  *
 222  *    #define silc_list_add(list, entry) ...
 223  *
 224  * DESCRIPTION
 225  *
 226  *    Adds new entry indicated by `entry' to the end of the list indicated
 227  *    by `list'.
 228  *
 229  ***/
 230 #define silc_list_add(list, entry)                      \
 231 do {                                                    \
 232   if (!(list).head)                                     \
 233     (list).head = (entry);                              \
 234   else                                                  \
 235     *__silc_list_next(list, (list).tail) = (entry);     \
 236   if ((list).prev_set)                                  \
 237     *__silc_list_prev(list, entry) = (list).tail;       \
 238   (list).tail = (entry);                                \
 239   *__silc_list_next(list, entry) = NULL;                \
 240   (list).count++;                                       \
 241 } while(0)
 242
 243 /****f* silcutil/SilcList/silc_list_insert
 244  *
 245  * SYNOPSIS
 246  *
 247  *    #define silc_list_insert(list, current, entry) ...
 248  *
 249  * DESCRIPTION
 250  *
 251  *    Insert new entry indicated by `entry' after the entry `current'
 252  *    to the list indicated by `list'.  If `current' is NULL, then the
 253  *    `entry' is added at the head of the list.  Use the silc_list_add
 254  *    to add at the end of the list.
 255  *
 256  ***/
 257 #define silc_list_insert(list, current, entry)                           \
 258 do {                                                                     \
 259   if (!(current)) {                                                      \
 260     if ((list).head)                                                     \
 261       *__silc_list_next(list, entry) = (list).head;                      \
 262     else                                                                 \
 263       *__silc_list_next(list, entry) = NULL;                             \
 264     if ((list).prev_set && (list).head)                                  \
 265       *__silc_list_prev(list, (list).head) = entry;                      \
 266     if (!(list).tail)                                                    \
 267       (list).tail = (entry);                                             \
 268     (list).head = (entry);                                               \
 269     if ((list).prev_set)                                                 \
 270       *__silc_list_prev(list, entry) = NULL;                             \
 271   } else {                                                               \
 272     *__silc_list_next(list, entry) = *__silc_list_next(list, current);   \
 273     *__silc_list_next(list, current) = entry;                            \
 274     if ((list).prev_set) {                                               \
 275       *__silc_list_prev(list, entry) = current;                          \
 276       if (*__silc_list_next(list, entry))                                \
 277         *__silc_list_prev(list, *__silc_list_next(list, entry)) = entry; \
 278     }                                                                    \
 279     if ((list).tail == (current))                                        \
 280       (list).tail = (entry);                                             \
 281   }                                                                      \
 282   (list).count++;                                                        \
 283 } while(0)
 284
 285 /****f* silcutil/SilcList/silc_list_del
 286  *
 287  * SYNOPSIS
 288  *
 289  *    #define silc_list_del(list, entry) ...
 290  *
 291  * DESCRIPTION
 292  *
 293  *    Remove entry indicated by `entry' from the list indicated by `list'.
 294  *
 295  ***/
 296 #define silc_list_del(list, entry)                                      \
 297 do {                                                                    \
 298   void **p, *prev;                                                      \
 299   prev = NULL;                                                          \
 300   for (p = &(list).head; *p; p = __silc_list_next(list, *p)) {          \
 301     if (*p == (entry)) {                                                \
 302       *p = *__silc_list_next(list, entry);                              \
 303       if (*p && (list).prev_set)                                        \
 304         *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry);   \
 305       if ((list).current == (entry))                                    \
 306         (list).current = *p;                                            \
 307       (list).count--;                                                   \
 308       break;                                                            \
 309     }                                                                   \
 310     prev = *p;                                                          \
 311   }                                                                     \
 312   if (entry == (list).tail)                                             \
 313     (list).tail = prev;                                                 \
 314 } while(0)
 315
 316 /****f* silcutil/SilcList/silc_list_get
 317  *
 318  * SYNOPSIS
 319  *
 320  *    #define silc_list_get(list) ...
 321  *
 322  * DESCRIPTION
 323  *
 324  *    Returns the current entry from the list indicated by `list' and
 325  *    moves the list pointer forward so that calling this next time will
 326  *    return the next entry from the list.  This can be used to traverse
 327  *    the list.  Returns SILC_LIST_END when the entire list has been
 328  *    tarversed and no additional entries exist in the list. Later,
 329  *    silc_list_start (or silc_list_end) must be called again when
 330  *    re-starting the list tarversing.
 331  *
 332  * EXAMPLE
 333  *
 334  *    // Traverse the list from the beginning to the end
 335  *    silc_list_start(list);
 336  *    while ((entry = silc_list_get(list)) != SILC_LIST_END) {
 337  *      ...
 338  *    }
 339  *
 340  *    // Traverse the list from the end to the beginning
 341  *    silc_list_end(list);
 342  *    while ((entry = silc_list_get(list)) != SILC_LIST_END) {
 343  *      ...
 344  *    }
 345  *
 346  ***/
 347 #define silc_list_get(x) __silc_list_get(&(x))
 348 static inline
 349 void *__silc_list_get(SilcList *list)
 350 {
 351   void *pos = list->current;
 352   if (pos)
 353     list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
 354                      *__silc_list_next(*list, pos));
 355   return pos;
 356 }
 357
 358 #endif