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