include/asterisk/linkedlists.h

   1 /*
   2  * Asterisk -- An open source telephony toolkit.
   3  *
   4  * Copyright (C) 1999 - 2005, Digium, Inc.
   5  *
   6  * Mark Spencer <markster@digium.com>
   7  * Kevin P. Fleming <kpfleming@digium.com>
   8  *
   9  * See http://www.asterisk.org for more information about
  10  * the Asterisk project. Please do not directly contact
  11  * any of the maintainers of this project for assistance;
  12  * the project provides a web site, mailing lists and IRC
  13  * channels for your use.
  14  *
  15  * This program is free software, distributed under the terms of
  16  * the GNU General Public License Version 2. See the LICENSE file
  17  * at the top of the source tree.
  18  */
  19
  20 #ifndef ASTERISK_LINKEDLISTS_H
  21 #define ASTERISK_LINKEDLISTS_H
  22
  23 #include "asterisk/lock.h"
  24
  25 /*!
  26   \file linkedlists.h
  27   \brief A set of macros to manage forward-linked lists.
  28 */
  29
  30 /*!
  31   \brief Attempts to lock a list.
  32   \param head This is a pointer to the list head structure
  33
  34   This macro attempts to place an exclusive lock in the
  35   list head structure pointed to by head.
  36   Returns non-zero on success, 0 on failure
  37 */
  38 #define AST_LIST_LOCK(head)                                             \
  39         ast_mutex_lock(&(head)->lock)
  40
  41 /*!
  42   \brief Attempts to unlock a list.
  43   \param head This is a pointer to the list head structure
  44
  45   This macro attempts to remove an exclusive lock from the
  46   list head structure pointed to by head. If the list
  47   was not locked by this thread, this macro has no effect.
  48 */
  49 #define AST_LIST_UNLOCK(head)                                           \
  50         ast_mutex_unlock(&(head)->lock)
  51
  52 /*!
  53   \brief Defines a structure to be used to hold a list of specified type.
  54   \param name This will be the name of the defined structure.
  55   \param type This is the type of each list entry.
  56
  57   This macro creates a structure definition that can be used
  58   to hold a list of the entries of type \a type. It does not actually
  59   declare (allocate) a structure; to do that, either follow this
  60   macro with the desired name of the instance you wish to declare,
  61   or use the specified \a name to declare instances elsewhere.
  62
  63   Example usage:
  64   \code
  65   static AST_LIST_HEAD(entry_list, entry) entries;
  66   \endcode
  67
  68   This would define \c struct \c entry_list, and declare an instance of it named
  69   \a entries, all intended to hold a list of type \c struct \c entry.
  70 */
  71 #define AST_LIST_HEAD(name, type)                                       \
  72 struct name {                                                           \
  73         struct type *first;                                             \
  74         struct type *last;                                              \
  75         ast_mutex_t lock;                                               \
  76 }
  77
  78 /*!
  79   \brief Defines a structure to be used to hold a list of specified type (with no lock).
  80   \param name This will be the name of the defined structure.
  81   \param type This is the type of each list entry.
  82
  83   This macro creates a structure definition that can be used
  84   to hold a list of the entries of type \a type. It does not actually
  85   declare (allocate) a structure; to do that, either follow this
  86   macro with the desired name of the instance you wish to declare,
  87   or use the specified \a name to declare instances elsewhere.
  88
  89   Example usage:
  90   \code
  91   static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries;
  92   \endcode
  93
  94   This would define \c struct \c entry_list, and declare an instance of it named
  95   \a entries, all intended to hold a list of type \c struct \c entry.
  96 */
  97 #define AST_LIST_HEAD_NOLOCK(name, type)                                \
  98 struct name {                                                           \
  99         struct type *first;                                             \
 100         struct type *last;                                              \
 101 }
 102
 103 /*!
 104   \brief Defines a structure to be used to hold a list of specified type, statically initialized.
 105   \param name This will be the name of the defined structure.
 106   \param type This is the type of each list entry.
 107
 108   This macro creates a structure definition that can be used
 109   to hold a list of the entries of type \a type, and allocates an instance
 110   of it, initialized to be empty.
 111
 112   Example usage:
 113   \code
 114   static AST_LIST_HEAD_STATIC(entry_list, entry);
 115   \endcode
 116
 117   This would define \c struct \c entry_list, intended to hold a list of
 118   type \c struct \c entry.
 119 */
 120 #define AST_LIST_HEAD_STATIC(name, type)                                \
 121 struct name {                                                           \
 122         struct type *first;                                             \
 123         struct type *last;                                              \
 124         ast_mutex_t lock;                                               \
 125 } name = {                                                              \
 126         .first = NULL,                                                  \
 127         .last = NULL,                                                   \
 128         .lock = AST_MUTEX_INIT_VALUE,                                   \
 129 };
 130
 131 /*!
 132   \brief Initializes a list head structure with a specified first entry.
 133   \param head This is a pointer to the list head structure
 134   \param entry pointer to the list entry that will become the head of the list
 135
 136   This macro initializes a list head structure by setting the head
 137   entry to the supplied value and recreating the embedded lock.
 138 */
 139 #define AST_LIST_HEAD_SET(head, entry) do {                             \
 140         (head)->first = (entry);                                        \
 141         (head)->last = (entry);                                         \
 142         ast_mutex_init(&(head)->lock);                                  \
 143 } while (0)
 144
 145 /*!
 146   \brief Initializes a list head structure with a specified first entry.
 147   \param head This is a pointer to the list head structure
 148   \param entry pointer to the list entry that will become the head of the list
 149
 150   This macro initializes a list head structure by setting the head
 151   entry to the supplied value.
 152 */
 153 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
 154         (head)->first = (entry);                                        \
 155         (head)->last = (entry);                                         \
 156 } while (0)
 157
 158 /*!
 159   \brief Declare a forward link structure inside a list entry.
 160   \param type This is the type of each list entry.
 161
 162   This macro declares a structure to be used to link list entries together.
 163   It must be used inside the definition of the structure named in
 164   \a type, as follows:
 165
 166   \code
 167   struct list_entry {
 168         ...
 169         AST_LIST_ENTRY(list_entry) list;
 170   }
 171   \endcode
 172
 173   The field name \a list here is arbitrary, and can be anything you wish.
 174 */
 175 #define AST_LIST_ENTRY(type)                                            \
 176 struct {                                                                \
 177         struct type *next;                                              \
 178 }
 179
 180 /*!
 181   \brief Returns the first entry contained in a list.
 182   \param head This is a pointer to the list head structure
 183  */
 184 #define AST_LIST_FIRST(head)    ((head)->first)
 185
 186 /*!
 187   \brief Returns the next entry in the list after the given entry.
 188   \param elm This is a pointer to the current entry.
 189   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 190   used to link entries of this list together.
 191 */
 192 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
 193
 194 /*!
 195   \brief Checks whether the specified list contains any entries.
 196   \param head This is a pointer to the list head structure
 197
 198   Returns non-zero if the list has entries, zero if not.
 199  */
 200 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
 201
 202 /*!
 203   \brief Loops over (traverses) the entries in a list.
 204   \param head This is a pointer to the list head structure
 205   \param var This is the name of the variable that will hold a pointer to the
 206   current list entry on each iteration. It must be declared before calling
 207   this macro.
 208   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 209   used to link entries of this list together.
 210
 211   This macro is use to loop over (traverse) the entries in a list. It uses a
 212   \a for loop, and supplies the enclosed code with a pointer to each list
 213   entry as it loops. It is typically used as follows:
 214   \code
 215   static AST_LIST_HEAD(entry_list, list_entry) entries;
 216   ...
 217   struct list_entry {
 218         ...
 219         AST_LIST_ENTRY(list_entry) list;
 220   }
 221   ...
 222   struct list_entry *current;
 223   ...
 224   AST_LIST_TRAVERSE(&entries, current, list) {
 225      (do something with current here)
 226   }
 227   \endcode
 228   \warning If you modify the forward-link pointer contained in the \a current entry while
 229   inside the loop, the behavior will be unpredictable. At a minimum, the following
 230   macros will modify the forward-link pointer, and should not be used inside
 231   AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
 232   careful consideration of their consequences:
 233   \li AST_LIST_NEXT() (when used as an lvalue)
 234   \li AST_LIST_INSERT_AFTER()
 235   \li AST_LIST_INSERT_HEAD()
 236   \li AST_LIST_INSERT_TAIL()
 237 */
 238 #define AST_LIST_TRAVERSE(head,var,field)                               \
 239         for((var) = (head)->first; (var); (var) = (var)->field.next)
 240
 241 /*!
 242   \brief Loops safely over (traverses) the entries in a list.
 243   \param head This is a pointer to the list head structure
 244   \param var This is the name of the variable that will hold a pointer to the
 245   current list entry on each iteration. It must be declared before calling
 246   this macro.
 247   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 248   used to link entries of this list together.
 249
 250   This macro is used to safely loop over (traverse) the entries in a list. It
 251   uses a \a for loop, and supplies the enclosed code with a pointer to each list
 252   entry as it loops. It is typically used as follows:
 253
 254   \code
 255   static AST_LIST_HEAD(entry_list, list_entry) entries;
 256   ...
 257   struct list_entry {
 258         ...
 259         AST_LIST_ENTRY(list_entry) list;
 260   }
 261   ...
 262   struct list_entry *current;
 263   ...
 264   AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
 265      (do something with current here)
 266   }
 267   AST_LIST_TRAVERSE_SAFE_END;
 268   \endcode
 269
 270   It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
 271   (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
 272   the \a current pointer without affecting the loop traversal.
 273 */
 274 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
 275         typeof((head)->first) __list_next;                                              \
 276         typeof((head)->first) __list_prev = NULL;                                       \
 277         for ((var) = (head)->first,  __list_next = (var) ? (var)->field.next : NULL;    \
 278              (var);                                                                     \
 279              __list_prev = (var), (var) = __list_next,                                  \
 280              __list_next = (var) ? (var)->field.next : NULL                             \
 281             )
 282
 283 /*!
 284   \brief Removes the \a current entry from a list during a traversal.
 285   \param head This is a pointer to the list head structure
 286   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 287   used to link entries of this list together.
 288
 289   \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
 290   block; it is used to unlink the current entry from the list without affecting
 291   the list traversal (and without having to re-traverse the list to modify the
 292   previous entry, if any).
 293  */
 294 #define AST_LIST_REMOVE_CURRENT(head, field)                                            \
 295         if (__list_prev)                                                                \
 296                 __list_prev->field.next = __list_next;                                  \
 297         else                                                                            \
 298                 (head)->first = __list_next;                                            \
 299         if (!__list_next)                                                               \
 300                 (head)->last = __list_prev;
 301
 302 /*!
 303   \brief Closes a safe loop traversal block.
 304  */
 305 #define AST_LIST_TRAVERSE_SAFE_END  }
 306
 307 /*!
 308   \brief Initializes a list head structure.
 309   \param head This is a pointer to the list head structure
 310
 311   This macro initializes a list head structure by setting the head
 312   entry to \a NULL (empty list) and recreating the embedded lock.
 313 */
 314 #define AST_LIST_HEAD_INIT(head) {                                      \
 315         (head)->first = NULL;                                           \
 316         (head)->last = NULL;                                            \
 317         ast_mutex_init(&(head)->lock);                                  \
 318 }
 319
 320 /*!
 321   \brief Destroys a list head structure.
 322   \param head This is a pointer to the list head structure
 323
 324   This macro destroys a list head structure by setting the head
 325   entry to \a NULL (empty list) and destroying the embedded lock.
 326   It does not free the structure from memory.
 327 */
 328 #define AST_LIST_HEAD_DESTROY(head) {                                   \
 329         (head)->first = NULL;                                           \
 330         (head)->last = NULL;                                            \
 331         ast_mutex_destroy(&(head)->lock);                               \
 332 }
 333
 334 /*!
 335   \brief Initializes a list head structure.
 336   \param head This is a pointer to the list head structure
 337
 338   This macro initializes a list head structure by setting the head
 339   entry to \a NULL (empty list) and recreating the embedded lock.
 340 */
 341 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
 342         (head)->first = NULL;                                           \
 343         (head)->last = NULL;                                            \
 344 }
 345
 346 /*!
 347   \brief Inserts a list entry after a given entry.
 348   \param head This is a pointer to the list head structure
 349   \param listelm This is a pointer to the entry after which the new entry should
 350   be inserted.
 351   \param elm This is a pointer to the entry to be inserted.
 352   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 353   used to link entries of this list together.
 354  */
 355 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
 356         (elm)->field.next = (listelm)->field.next;                      \
 357         (listelm)->field.next = (elm);                                  \
 358         if ((head)->last == (listelm))                                  \
 359                 (head)->last = (elm);                                   \
 360 } while (0)
 361
 362 /*!
 363   \brief Inserts a list entry at the head of a list.
 364   \param head This is a pointer to the list head structure
 365   \param elm This is a pointer to the entry to be inserted.
 366   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 367   used to link entries of this list together.
 368  */
 369 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
 370                 (elm)->field.next = (head)->first;                      \
 371                 (head)->first = (elm);                                  \
 372                 if (!(head)->last)                                      \
 373                         (head)->last = (elm);                           \
 374 } while (0)
 375
 376 /*!
 377   \brief Appends a list entry to the tail of a list.
 378   \param head This is a pointer to the list head structure
 379   \param elm This is a pointer to the entry to be appended.
 380   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 381   used to link entries of this list together.
 382
 383   Note: The link field in the appended entry is \b not modified, so if it is
 384   actually the head of a list itself, the entire list will be appended.
 385  */
 386 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
 387       if (!(head)->first) {                                             \
 388                 (head)->first = (elm);                                  \
 389                 (head)->last = (elm);                                   \
 390       } else {                                                          \
 391                 (head)->last->field.next = (elm);                       \
 392                 (head)->last = (elm);                                   \
 393       }                                                                 \
 394 } while (0)
 395
 396 /*!
 397   \brief Removes and returns the head entry from a list.
 398   \param head This is a pointer to the list head structure
 399   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 400   used to link entries of this list together.
 401
 402   Removes the head entry from the list, and returns a pointer to it.
 403   This macro is safe to call on an empty list.
 404  */
 405 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
 406                 typeof((head)->first) cur = (head)->first;              \
 407                 if (cur) {                                              \
 408                         (head)->first = cur->field.next;                \
 409                         cur->field.next = NULL;                         \
 410                         if ((head)->last == cur)                        \
 411                                 (head)->last = NULL;                    \
 412                 }                                                       \
 413                 cur;                                                    \
 414         })
 415
 416 /*!
 417   \brief Removes a specific entry from a list.
 418   \param head This is a pointer to the list head structure
 419   \param elm This is a pointer to the entry to be removed.
 420   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 421   used to link entries of this list together.
 422   \warning The removed entry is \b not freed nor modified in any way.
 423  */
 424 #define AST_LIST_REMOVE(head, elm, field) do {                          \
 425         if ((head)->first == (elm)) {                                   \
 426                 (head)->first = (elm)->field.next;                      \
 427                 if ((head)->last == (elm))                      \
 428                         (head)->last = NULL;                    \
 429         } else {                                                                \
 430                 typeof(elm) curelm = (head)->first;                     \
 431                 while (curelm->field.next != (elm))                     \
 432                         curelm = curelm->field.next;                    \
 433                 curelm->field.next = (elm)->field.next;                 \
 434                 if ((head)->last == curelm->field.next)                 \
 435                         (head)->last = curelm;                          \
 436         }                                                               \
 437 } while (0)
 438
 439 #endif /* _ASTERISK_LINKEDLISTS_H */