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