lib/silcutil/silclist.h

   1 /*
   2
   3   silclist.h
   4
   5   Author: Pekka Riikonen <priikone@silcnet.org>
   6
   7   Copyright (C) 2002 - 2003 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   unsigned int next_offset : 16;     /* Offset to 'next' pointer */
  49   unsigned int prev_offset : 16;     /* 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(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_del
 226  *
 227  * SYNOPSIS
 228  *
 229  *    #define silc_list_del(list, entry) ...
 230  *
 231  * DESCRIPTION
 232  *
 233  *    Remove entry indicated by `entry' from the list indicated by `list'.
 234  *
 235  ***/
 236 #define silc_list_del(list, entry)                                      \
 237 do {                                                                    \
 238   void **p, *prev;                                                      \
 239   prev = NULL;                                                          \
 240   for (p = &(list).head; *p; p = __silc_list_next(list, *p)) {          \
 241     if (*p == (entry)) {                                                \
 242       *p = *__silc_list_next(list, entry);                              \
 243       if (*p && (list).prev_set)                                        \
 244         *__silc_list_prev(list, *p) = *__silc_list_prev(list, entry);   \
 245       if ((list).current == (entry))                                    \
 246         (list).current = *p;                                            \
 247       (list).count--;                                                   \
 248       break;                                                            \
 249     }                                                                   \
 250     prev = *p;                                                          \
 251   }                                                                     \
 252   if (entry == (list).tail)                                             \
 253     (list).tail = prev;                                                 \
 254 } while(0)
 255
 256 /****f* silcutil/SilcList/silc_list_get
 257  *
 258  * SYNOPSIS
 259  *
 260  *    #define silc_list_get(list) ...
 261  *
 262  * DESCRIPTION
 263  *
 264  *    Returns the current entry from the list indicated by `list' and
 265  *    moves the list pointer forward so that calling this next time will
 266  *    return the next entry from the list.  This can be used to traverse
 267  *    the list.  Returns SILC_LIST_END when the entire list has been
 268  *    tarversed and no additional entries exist in the list. Later,
 269  *    silc_list_start (or silc_list_end) must be called again when
 270  *    re-starting the list tarversing.
 271  *
 272  * EXAMPLE
 273  *
 274  *    // Traverse the list from the beginning to the end
 275  *    silc_list_start(list);
 276  *    while ((entry = silc_list_get(list)) != SILC_LIST_END) {
 277  *      ...
 278  *    }
 279  *
 280  *    // Traverse the list from the end to the beginning
 281  *    silc_list_end(list);
 282  *    while ((entry = silc_list_get(list)) != SILC_LIST_END) {
 283  *      ...
 284  *    }
 285  *
 286  ***/
 287 #define silc_list_get(x) __silc_list_get(&(x))
 288 static inline
 289 void *__silc_list_get(SilcList *list)
 290 {
 291   void *pos = list->current;
 292   if (pos)
 293     list->current = (list->end_set ? *__silc_list_prev(*list, pos) :
 294                      *__silc_list_next(*list, pos));
 295   return pos;
 296 }
 297
 298 #endif