lib/silcutil/silclist.h

   1 /*
   2
   3   silclist.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2002 - 2005 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.
  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 {
  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).head = (list).tail = (list).current = NULL;    \
 108 } while(0)
 109
 110 /****f* silcutil/SilcList/silc_list_init_prev
 111  *
 112  * SYNOPSIS
 113  *
 114  *    #define silc_list_init_prev(list, type, nextfield, prevfield) ...
 115  *
 116  * DESCRIPTION
 117  *
 118  *    This macro initializes the SilcList list.  The `list' is the defined
 119  *    list, second argument is the structure of the entries in the list,
 120  *    and last two arguments are the pointers in the structure that is used
 121  *    as next and prev list members.  When using SilcList you must not
 122  *    touch the structure member pointers manually.
 123  *
 124  *    Having both next and prev pointers makes it possible to traverse
 125  *    list from both ends of the list (from start to end, and from end
 126  *    to start).
 127  *
 128  * EXAMPLE
 129  *
 130  *    struct SilcInternalEntryStruct {
 131  *      char *dummy;
 132  *      struct SilcInternalEntryStruct *next; // The list member pointer
 133  *      struct SilcInternalEntryStruct *prev; // The list member pointer
 134  *    };
 135  *
 136  *    SilcList list;
 137  *    silc_list_init_prev(list, struct SilcInternalEntryStruct, next, prev);
 138  *
 139  ***/
 140 #define silc_list_init_prev(list, type, nextfield, prevfield)   \
 141 do {                                                            \
 142   (list).count = 0;                                             \
 143   (list).next_offset = silc_offsetof(type, nextfield);          \
 144   (list).prev_offset = silc_offsetof(type, prevfield);          \
 145   (list).prev_set = 1;                                          \
 146   (list).head = (list).tail = (list).current = NULL;            \
 147 } while(0)
 148
 149 /****f* silcutil/SilcList/silc_list_count
 150  *
 151  * SYNOPSIS
 152  *
 153  *    #define silc_list_count(list) ...
 154  *
 155  * DESCRIPTION
 156  *
 157  *    Returns the number of entries in the list indicated by `list'.
 158  *
 159  ***/
 160 #define silc_list_count(list) (list).count
 161
 162 /****f* silcutil/SilcList/silc_list_start
 163  *
 164  * SYNOPSIS
 165  *
 166  *    #define silc_list_start(list) ...
 167  *
 168  * DESCRIPTION
 169  *
 170  *    Sets the start of the list.  This prepares the list for traversing
 171  *    the entries from the start of the list towards end of the list.
 172  *
 173  ***/
 174 #define silc_list_start(list)                           \
 175   ((list).current = (list).head, (list).end_set = 0)
 176
 177 /****f* silcutil/SilcList/silc_list_end
 178  *
 179  * SYNOPSIS
 180  *
 181  *    #define silc_list_end(list) ...
 182  *
 183  * DESCRIPTION
 184  *
 185  *    Sets the end of the list.  This prepares the list for traversing
 186  *    the entries from the end of the list towards start of the list.
 187  *
 188  * NOTES
 189  *
 190  *    You can use this call only if you initialized the list with
 191  *    silc_list_init_prev.
 192  *
 193  ***/
 194 #define silc_list_end(list)                             \
 195   ((list).current = (list).tail, (list).end_set = 1)
 196
 197 /* Macros to get position to next and prev list pointers */
 198 #define __silc_list_next(list, pos)                             \
 199   ((void **)((unsigned char *)(pos) + (list).next_offset))
 200 #define __silc_list_prev(list, pos)                             \
 201   ((void **)((unsigned char *)(pos) + (list).prev_offset))
 202
 203 /****f* silcutil/SilcList/silc_list_add
 204  *
 205  * SYNOPSIS
 206  *
 207  *    #define silc_list_add(list, entry) ...
 208  *
 209  * DESCRIPTION
 210  *
 211  *    Adds new entry indicated by `entry' to the end of the list indicated
 212  *    by `list'.
 213  *
 214  ***/
 215 #define silc_list_add(list, entry)                      \
 216 do {                                                    \
 217   if (!(list).head)                                     \
 218     (list).head = (entry);                              \
 219   else                                                  \
 220     *__silc_list_next(list, (list).tail) = (entry);     \
 221   if ((list).prev_set)                                  \
 222     *__silc_list_prev(list, entry) = (list).tail;       \
 223   (list).tail = (entry);                                \
 224   *__silc_list_next(list, entry) = NULL;                \
 225   (list).count++;                                       \
 226 } while(0)
 227
 228 /****f* silcutil/SilcList/silc_list_insert
 229  *
 230  * SYNOPSIS
 231  *
 232  *    #define silc_list_insert(list, current, entry) ...
 233  *
 234  * DESCRIPTION
 235  *
 236  *    Insert new entry indicated by `entry' after the entry `current'
 237  *    to the list indicated by `list'.  If `current' is NULL, then the
 238  *    `entry' is added at the head of the list.  Use the silc_list_add
 239  *    to add at the end of the list.
 240  *
 241  ***/
 242 #define silc_list_insert(list, current, entry)                           \
 243 do {                                                                     \
 244   if (!(current)) {                                                      \
 245     if ((list).head)                                                     \
 246       *__silc_list_next(list, entry) = (list).head;                      \
 247     else                                                                 \
 248       *__silc_list_next(list, entry) = NULL;                             \
 249     if ((list).prev_set && (list).head)                                  \
 250       *__silc_list_prev(list, (list).head) = entry;                      \
 251     if (!(list).tail)                                                    \
 252       (list).tail = (entry);                                             \
 253     (list).head = (entry);                                               \
 254     if ((list).prev_set)                                                 \
 255       *__silc_list_prev(list, entry) = NULL;                             \
 256   } else {                                                               \
 257     *__silc_list_next(list, entry) = *__silc_list_next(list, current);   \
 258     *__silc_list_next(list, current) = entry;                            \
 259     if ((list).prev_set) {                                               \
 260       *__silc_list_prev(list, entry) = current;                          \
 261       if (*__silc_list_next(list, entry))                                \
 262         *__silc_list_prev(list, *__silc_list_next(list, entry)) = entry; \
 263     }                                                                    \
 264     if ((list).tail == (current))                                        \
 265       (list).tail = (entry);                                             \
 266   }                                                                      \
 267   (list).count++;                                                        \
 268 } while(0)
 269
 270 /****f* silcutil/SilcList/silc_list_del
 271  *
 272  * SYNOPSIS
 273  *
 274  *    #define silc_list_del(list, entry) ...
 275  *
 276  * DESCRIPTION
 277  *
 278  *    Remove entry indicated by `entry' from the list indicated by `list'.
 279  *
 280  ***/
 281 #define silc_list_del(list, entry)                                      \
 282 do {                                                                    \
 283   void **p, *prev;                                                      \
 284   prev = NULL;                                                          \
 285   for (p = &(list).head; *p; p = __silc_list_next(list, *p)) {          \
 286     if (*p == (entry)) {                                                \
 287       *p = *__silc_list_next(list, entry);                              \
 288       if (*p && (list).prev_set)                                        \
 289         *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry);   \
 290       if ((list).current == (entry))                                    \
 291         (list).current = *p;                                            \
 292       (list).count--;                                                   \
 293       break;                                                            \
 294     }                                                                   \
 295     prev = *p;                                                          \
 296   }                                                                     \
 297   if (entry == (list).tail)                                             \
 298     (list).tail = prev;                                                 \
 299 } while(0)
 300
 301 /****f* silcutil/SilcList/silc_list_get
 302  *
 303  * SYNOPSIS
 304  *
 305  *    #define silc_list_get(list) ...
 306  *
 307  * DESCRIPTION
 308  *
 309  *    Returns the current entry from the list indicated by `list' and
 310  *    moves the list pointer forward so that calling this next time will
 311  *    return the next entry from the list.  This can be used to traverse
 312  *    the list.  Returns SILC_LIST_END when the entire list has been
 313  *    tarversed and no additional entries exist in the list. Later,
 314  *    silc_list_start (or silc_list_end) must be called again when
 315  *    re-starting the list tarversing.
 316  *
 317  * EXAMPLE
 318  *
 319  *    // Traverse the list from the beginning to the end
 320  *    silc_list_start(list);
 321  *    while ((entry = silc_list_get(list)) != SILC_LIST_END) {
 322  *      ...
 323  *    }
 324  *
 325  *    // Traverse the list from the end to the beginning
 326  *    silc_list_end(list);
 327  *    while ((entry = silc_list_get(list)) != SILC_LIST_END) {
 328  *      ...
 329  *    }
 330  *
 331  ***/
 332 #define silc_list_get(x) __silc_list_get(&(x))
 333 static inline
 334 void *__silc_list_get(SilcList *list)
 335 {
 336   void *pos = list->current;
 337   if (pos)
 338     list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
 339                      *__silc_list_next(*list, pos));
 340   return pos;
 341 }
 342
 343 #endif