include/asterisk/linkedlists.h

   1 /*
   2  * Asterisk -- An open source telephony toolkit.
   3  *
   4  * Copyright (C) 1999 - 2006, 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 Locks 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  * \retval 0 on success
  37  * \retval non-zero on failure
  38  */
  39 #define AST_LIST_LOCK(head)                                             \
  40         ast_mutex_lock(&(head)->lock)
  41
  42 /*!
  43  * \brief Write locks a list.
  44  * \param head This is a pointer to the list head structure
  45  *
  46  * This macro attempts to place an exclusive write lock in the
  47  * list head structure pointed to by head.
  48  * \retval 0 on success
  49  * \retval non-zero on failure
  50  */
  51 #define AST_RWLIST_WRLOCK(head)                                         \
  52         ast_rwlock_wrlock(&(head)->lock)
  53
  54 /*!
  55  * \brief Write locks a list, with timeout.
  56  * \param head This is a pointer to the list head structure
  57  * \param ts Pointer to a timespec structure
  58  *
  59  * This macro attempts to place an exclusive write lock in the
  60  * list head structure pointed to by head.
  61  * \retval 0 on success
  62  * \retval non-zero on failure
  63  *
  64  * \since 1.6.1
  65  */
  66 #define AST_RWLIST_TIMEDWRLOCK(head, ts)        ast_rwlock_timedwrlock(&(head)->lock, ts)
  67
  68 /*!
  69  * \brief Read locks a list.
  70  * \param head This is a pointer to the list head structure
  71  *
  72  * This macro attempts to place a read lock in the
  73  * list head structure pointed to by head.
  74  * \retval 0 on success
  75  * \retval non-zero on failure
  76  */
  77 #define AST_RWLIST_RDLOCK(head)                                         \
  78         ast_rwlock_rdlock(&(head)->lock)
  79
  80 /*!
  81  * \brief Read locks a list, with timeout.
  82  * \param head This is a pointer to the list head structure
  83  * \param ts Pointer to a timespec structure
  84  *
  85  * This macro attempts to place a read lock in the
  86  * list head structure pointed to by head.
  87  * \retval 0 on success
  88  * \retval non-zero on failure
  89  *
  90  * \since 1.6.1
  91  */
  92 #define AST_RWLIST_TIMEDRDLOCK(head, ts)                                 \
  93         ast_rwlock_timedrdlock(&(head)->lock, ts)
  94
  95 /*!
  96  * \brief Locks a list, without blocking if the list is locked.
  97  * \param head This is a pointer to the list head structure
  98  *
  99  * This macro attempts to place an exclusive lock in the
 100  * list head structure pointed to by head.
 101  * \retval 0 on success
 102  * \retval non-zero on failure
 103  */
 104 #define AST_LIST_TRYLOCK(head)                                          \
 105         ast_mutex_trylock(&(head)->lock)
 106
 107 /*!
 108  * \brief Write locks a list, without blocking if the list is locked.
 109  * \param head This is a pointer to the list head structure
 110  *
 111  * This macro attempts to place an exclusive write lock in the
 112  * list head structure pointed to by head.
 113  * \retval 0 on success
 114  * \retval non-zero on failure
 115  */
 116 #define AST_RWLIST_TRYWRLOCK(head)                                      \
 117         ast_rwlock_trywrlock(&(head)->lock)
 118
 119 /*!
 120  * \brief Read locks a list, without blocking if the list is locked.
 121  * \param head This is a pointer to the list head structure
 122  *
 123  * This macro attempts to place a read lock in the
 124  * list head structure pointed to by head.
 125  * \retval 0 on success
 126  * \retval non-zero on failure
 127  */
 128 #define AST_RWLIST_TRYRDLOCK(head)                                      \
 129         ast_rwlock_tryrdlock(&(head)->lock)
 130
 131 /*!
 132  * \brief Attempts to unlock a list.
 133  * \param head This is a pointer to the list head structure
 134  *
 135  * This macro attempts to remove an exclusive lock from the
 136  * list head structure pointed to by head. If the list
 137  * was not locked by this thread, this macro has no effect.
 138  */
 139 #define AST_LIST_UNLOCK(head)                                           \
 140         ast_mutex_unlock(&(head)->lock)
 141
 142 /*!
 143  * \brief Attempts to unlock a read/write based list.
 144  * \param head This is a pointer to the list head structure
 145  *
 146  * This macro attempts to remove a read or write lock from the
 147  * list head structure pointed to by head. If the list
 148  * was not locked by this thread, this macro has no effect.
 149  */
 150 #define AST_RWLIST_UNLOCK(head)                                         \
 151         ast_rwlock_unlock(&(head)->lock)
 152
 153 /*!
 154  * \brief Defines a structure to be used to hold a list of specified type.
 155  * \param name This will be the name of the defined structure.
 156  * \param type This is the type of each list entry.
 157  *
 158  * This macro creates a structure definition that can be used
 159  * to hold a list of the entries of type \a type. It does not actually
 160  * declare (allocate) a structure; to do that, either follow this
 161  * macro with the desired name of the instance you wish to declare,
 162  * or use the specified \a name to declare instances elsewhere.
 163  *
 164  * Example usage:
 165  * \code
 166  * static AST_LIST_HEAD(entry_list, entry) entries;
 167  * \endcode
 168  *
 169  * This would define \c struct \c entry_list, and declare an instance of it named
 170  * \a entries, all intended to hold a list of type \c struct \c entry.
 171  */
 172 #define AST_LIST_HEAD(name, type)                                       \
 173 struct name {                                                           \
 174         struct type *first;                                             \
 175         struct type *last;                                              \
 176         ast_mutex_t lock;                                               \
 177 }
 178
 179 /*!
 180  * \brief Defines a structure to be used to hold a read/write list of specified type.
 181  * \param name This will be the name of the defined structure.
 182  * \param type This is the type of each list entry.
 183  *
 184  * This macro creates a structure definition that can be used
 185  * to hold a list of the entries of type \a type. It does not actually
 186  * declare (allocate) a structure; to do that, either follow this
 187  * macro with the desired name of the instance you wish to declare,
 188  * or use the specified \a name to declare instances elsewhere.
 189  *
 190  * Example usage:
 191  * \code
 192  * static AST_RWLIST_HEAD(entry_list, entry) entries;
 193  * \endcode
 194  *
 195  * This would define \c struct \c entry_list, and declare an instance of it named
 196  * \a entries, all intended to hold a list of type \c struct \c entry.
 197  */
 198 #define AST_RWLIST_HEAD(name, type)                                     \
 199 struct name {                                                           \
 200         struct type *first;                                             \
 201         struct type *last;                                              \
 202         ast_rwlock_t lock;                                              \
 203 }
 204
 205 /*!
 206  * \brief Defines a structure to be used to hold a list of specified type (with no lock).
 207  * \param name This will be the name of the defined structure.
 208  * \param type This is the type of each list entry.
 209  *
 210  * This macro creates a structure definition that can be used
 211  * to hold a list of the entries of type \a type. It does not actually
 212  * declare (allocate) a structure; to do that, either follow this
 213  * macro with the desired name of the instance you wish to declare,
 214  * or use the specified \a name to declare instances elsewhere.
 215  *
 216  * Example usage:
 217  * \code
 218  * static AST_LIST_HEAD_NOLOCK(entry_list, entry) entries;
 219  * \endcode
 220  *
 221  * This would define \c struct \c entry_list, and declare an instance of it named
 222  * \a entries, all intended to hold a list of type \c struct \c entry.
 223  */
 224 #define AST_LIST_HEAD_NOLOCK(name, type)                                \
 225 struct name {                                                           \
 226         struct type *first;                                             \
 227         struct type *last;                                              \
 228 }
 229
 230 /*!
 231  * \brief Defines initial values for a declaration of AST_LIST_HEAD
 232  */
 233 #define AST_LIST_HEAD_INIT_VALUE        {               \
 234         .first = NULL,                                  \
 235         .last = NULL,                                   \
 236         .lock = AST_MUTEX_INIT_VALUE,                   \
 237         }
 238
 239 /*!
 240  * \brief Defines initial values for a declaration of AST_RWLIST_HEAD
 241  */
 242 #define AST_RWLIST_HEAD_INIT_VALUE      {               \
 243         .first = NULL,                                  \
 244         .last = NULL,                                   \
 245         .lock = AST_RWLOCK_INIT_VALUE,                  \
 246         }
 247
 248 /*!
 249  * \brief Defines initial values for a declaration of AST_LIST_HEAD_NOLOCK
 250  */
 251 #define AST_LIST_HEAD_NOLOCK_INIT_VALUE {       \
 252         .first = NULL,                                  \
 253         .last = NULL,                                   \
 254         }
 255
 256 /*!
 257  * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
 258  * \param name This will be the name of the defined structure.
 259  * \param type This is the type of each list entry.
 260  *
 261  * This macro creates a structure definition that can be used
 262  * to hold a list of the entries of type \a type, and allocates an instance
 263  * of it, initialized to be empty.
 264  *
 265  * Example usage:
 266  * \code
 267  * static AST_LIST_HEAD_STATIC(entry_list, entry);
 268  * \endcode
 269  *
 270  * This would define \c struct \c entry_list, intended to hold a list of
 271  * type \c struct \c entry.
 272  */
 273 #if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
 274 #define AST_LIST_HEAD_STATIC(name, type)                                \
 275 struct name {                                                           \
 276         struct type *first;                                             \
 277         struct type *last;                                              \
 278         ast_mutex_t lock;                                               \
 279 } name;                                                                 \
 280 static void  __attribute__((constructor)) __init_##name(void)           \
 281 {                                                                       \
 282         AST_LIST_HEAD_INIT(&name);                                      \
 283 }                                                                       \
 284 static void  __attribute__((destructor)) __fini_##name(void)            \
 285 {                                                                       \
 286         AST_LIST_HEAD_DESTROY(&name);                                   \
 287 }                                                                       \
 288 struct __dummy_##name
 289 #else
 290 #define AST_LIST_HEAD_STATIC(name, type)                                \
 291 struct name {                                                           \
 292         struct type *first;                                             \
 293         struct type *last;                                              \
 294         ast_mutex_t lock;                                               \
 295 } name = AST_LIST_HEAD_INIT_VALUE
 296 #endif
 297
 298 /*!
 299  * \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
 300  * \param name This will be the name of the defined structure.
 301  * \param type This is the type of each list entry.
 302  *
 303  * This macro creates a structure definition that can be used
 304  * to hold a list of the entries of type \a type, and allocates an instance
 305  * of it, initialized to be empty.
 306  *
 307  * Example usage:
 308  * \code
 309  * static AST_RWLIST_HEAD_STATIC(entry_list, entry);
 310  * \endcode
 311  *
 312  * This would define \c struct \c entry_list, intended to hold a list of
 313  * type \c struct \c entry.
 314  */
 315 #ifndef HAVE_PTHREAD_RWLOCK_INITIALIZER
 316 #define AST_RWLIST_HEAD_STATIC(name, type)                              \
 317 struct name {                                                           \
 318         struct type *first;                                             \
 319         struct type *last;                                              \
 320         ast_rwlock_t lock;                                              \
 321 } name;                                                                 \
 322 static void  __attribute__((constructor)) __init_##name(void)          \
 323 {                                                                       \
 324         AST_RWLIST_HEAD_INIT(&name);                                    \
 325 }                                                                       \
 326 static void  __attribute__((destructor)) __fini_##name(void)           \
 327 {                                                                       \
 328         AST_RWLIST_HEAD_DESTROY(&name);                                 \
 329 }                                                                       \
 330 struct __dummy_##name
 331 #else
 332 #define AST_RWLIST_HEAD_STATIC(name, type)                              \
 333 struct name {                                                           \
 334         struct type *first;                                             \
 335         struct type *last;                                              \
 336         ast_rwlock_t lock;                                              \
 337 } name = AST_RWLIST_HEAD_INIT_VALUE
 338 #endif
 339
 340 /*!
 341  * \brief Defines a structure to be used to hold a list of specified type, statically initialized.
 342  *
 343  * This is the same as AST_LIST_HEAD_STATIC, except without the lock included.
 344  */
 345 #define AST_LIST_HEAD_NOLOCK_STATIC(name, type)                         \
 346 struct name {                                                           \
 347         struct type *first;                                             \
 348         struct type *last;                                              \
 349 } name = AST_LIST_HEAD_NOLOCK_INIT_VALUE
 350
 351 /*!
 352  * \brief Initializes a list head structure with a specified first entry.
 353  * \param head This is a pointer to the list head structure
 354  * \param entry pointer to the list entry that will become the head of the list
 355  *
 356  * This macro initializes a list head structure by setting the head
 357  * entry to the supplied value and recreating the embedded lock.
 358  */
 359 #define AST_LIST_HEAD_SET(head, entry) do {                             \
 360         (head)->first = (entry);                                        \
 361         (head)->last = (entry);                                         \
 362         ast_mutex_init(&(head)->lock);                                  \
 363 } while (0)
 364
 365 /*!
 366  * \brief Initializes an rwlist head structure with a specified first entry.
 367  * \param head This is a pointer to the list head structure
 368  * \param entry pointer to the list entry that will become the head of the list
 369  *
 370  * This macro initializes a list head structure by setting the head
 371  * entry to the supplied value and recreating the embedded lock.
 372  */
 373 #define AST_RWLIST_HEAD_SET(head, entry) do {                           \
 374         (head)->first = (entry);                                        \
 375         (head)->last = (entry);                                         \
 376         ast_rwlock_init(&(head)->lock);                                 \
 377 } while (0)
 378
 379 /*!
 380  * \brief Initializes a list head structure with a specified first entry.
 381  * \param head This is a pointer to the list head structure
 382  * \param entry pointer to the list entry that will become the head of the list
 383  *
 384  * This macro initializes a list head structure by setting the head
 385  * entry to the supplied value.
 386  */
 387 #define AST_LIST_HEAD_SET_NOLOCK(head, entry) do {                      \
 388         (head)->first = (entry);                                        \
 389         (head)->last = (entry);                                         \
 390 } while (0)
 391
 392 /*!
 393  * \brief Declare a forward link structure inside a list entry.
 394  * \param type This is the type of each list entry.
 395  *
 396  * This macro declares a structure to be used to link list entries together.
 397  * It must be used inside the definition of the structure named in
 398  * \a type, as follows:
 399  *
 400  * \code
 401  * struct list_entry {
 402       ...
 403       AST_LIST_ENTRY(list_entry) list;
 404  * }
 405  * \endcode
 406  *
 407  * The field name \a list here is arbitrary, and can be anything you wish.
 408  */
 409 #define AST_LIST_ENTRY(type)                                            \
 410 struct {                                                                \
 411         struct type *next;                                              \
 412 }
 413
 414 #define AST_RWLIST_ENTRY AST_LIST_ENTRY
 415
 416 /*!
 417  * \brief Returns the first entry contained in a list.
 418  * \param head This is a pointer to the list head structure
 419  */
 420 #define AST_LIST_FIRST(head)    ((head)->first)
 421
 422 #define AST_RWLIST_FIRST AST_LIST_FIRST
 423
 424 /*!
 425  * \brief Returns the last entry contained in a list.
 426  * \param head This is a pointer to the list head structure
 427  */
 428 #define AST_LIST_LAST(head)     ((head)->last)
 429
 430 #define AST_RWLIST_LAST AST_LIST_LAST
 431
 432 /*!
 433  * \brief Returns the next entry in the list after the given entry.
 434  * \param elm This is a pointer to the current entry.
 435  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 436  * used to link entries of this list together.
 437  */
 438 #define AST_LIST_NEXT(elm, field)       ((elm)->field.next)
 439
 440 #define AST_RWLIST_NEXT AST_LIST_NEXT
 441
 442 /*!
 443  * \brief Checks whether the specified list contains any entries.
 444  * \param head This is a pointer to the list head structure
 445  *
 446  * \return non-zero if the list has entries
 447  * \return zero if not.
 448  */
 449 #define AST_LIST_EMPTY(head)    (AST_LIST_FIRST(head) == NULL)
 450
 451 #define AST_RWLIST_EMPTY AST_LIST_EMPTY
 452
 453 /*!
 454  * \brief Loops over (traverses) the entries in a list.
 455  * \param head This is a pointer to the list head structure
 456  * \param var This is the name of the variable that will hold a pointer to the
 457  * current list entry on each iteration. It must be declared before calling
 458  * this macro.
 459  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 460  * used to link entries of this list together.
 461  *
 462  * This macro is use to loop over (traverse) the entries in a list. It uses a
 463  * \a for loop, and supplies the enclosed code with a pointer to each list
 464  * entry as it loops. It is typically used as follows:
 465  * \code
 466  * static AST_LIST_HEAD(entry_list, list_entry) entries;
 467  * ...
 468  * struct list_entry {
 469       ...
 470       AST_LIST_ENTRY(list_entry) list;
 471  * }
 472  * ...
 473  * struct list_entry *current;
 474  * ...
 475  * AST_LIST_TRAVERSE(&entries, current, list) {
 476      (do something with current here)
 477  * }
 478  * \endcode
 479  * \warning If you modify the forward-link pointer contained in the \a current entry while
 480  * inside the loop, the behavior will be unpredictable. At a minimum, the following
 481  * macros will modify the forward-link pointer, and should not be used inside
 482  * AST_LIST_TRAVERSE() against the entry pointed to by the \a current pointer without
 483  * careful consideration of their consequences:
 484  * \li AST_LIST_NEXT() (when used as an lvalue)
 485  * \li AST_LIST_INSERT_AFTER()
 486  * \li AST_LIST_INSERT_HEAD()
 487  * \li AST_LIST_INSERT_TAIL()
 488  * \li AST_LIST_INSERT_SORTALPHA()
 489  */
 490 #define AST_LIST_TRAVERSE(head,var,field)                               \
 491         for((var) = (head)->first; (var); (var) = (var)->field.next)
 492
 493 #define AST_RWLIST_TRAVERSE AST_LIST_TRAVERSE
 494
 495 /*!
 496  * \brief Loops safely over (traverses) the entries in a list.
 497  * \param head This is a pointer to the list head structure
 498  * \param var This is the name of the variable that will hold a pointer to the
 499  * current list entry on each iteration. It must be declared before calling
 500  * this macro.
 501  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 502  * used to link entries of this list together.
 503  *
 504  * This macro is used to safely loop over (traverse) the entries in a list. It
 505  * uses a \a for loop, and supplies the enclosed code with a pointer to each list
 506  * entry as it loops. It is typically used as follows:
 507  *
 508  * \code
 509  * static AST_LIST_HEAD(entry_list, list_entry) entries;
 510  * ...
 511  * struct list_entry {
 512       ...
 513       AST_LIST_ENTRY(list_entry) list;
 514  * }
 515  * ...
 516  * struct list_entry *current;
 517  * ...
 518  * AST_LIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
 519      (do something with current here)
 520  * }
 521  * AST_LIST_TRAVERSE_SAFE_END;
 522  * \endcode
 523  *
 524  * It differs from AST_LIST_TRAVERSE() in that the code inside the loop can modify
 525  * (or even free, after calling AST_LIST_REMOVE_CURRENT()) the entry pointed to by
 526  * the \a current pointer without affecting the loop traversal.
 527  */
 528 #define AST_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                                \
 529         typeof((head)) __list_head = head;                                              \
 530         typeof(__list_head->first) __list_next;                                         \
 531         typeof(__list_head->first) __list_prev = NULL;                                  \
 532         typeof(__list_head->first) __new_prev = NULL;                                   \
 533         for ((var) = __list_head->first, __new_prev = (var),                            \
 534               __list_next = (var) ? (var)->field.next : NULL;                           \
 535              (var);                                                                     \
 536              __list_prev = __new_prev, (var) = __list_next,                             \
 537              __new_prev = (var),                                                        \
 538              __list_next = (var) ? (var)->field.next : NULL                             \
 539             )
 540
 541 #define AST_RWLIST_TRAVERSE_SAFE_BEGIN AST_LIST_TRAVERSE_SAFE_BEGIN
 542
 543 /*!
 544  * \brief Removes the \a current entry from a list during a traversal.
 545  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 546  * used to link entries of this list together.
 547  *
 548  * \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
 549  * block; it is used to unlink the current entry from the list without affecting
 550  * the list traversal (and without having to re-traverse the list to modify the
 551  * previous entry, if any).
 552  */
 553 #define AST_LIST_REMOVE_CURRENT(field) do { \
 554         __new_prev->field.next = NULL;                                                  \
 555         __new_prev = __list_prev;                                                       \
 556         if (__list_prev)                                                                \
 557                 __list_prev->field.next = __list_next;                                  \
 558         else                                                                            \
 559                 __list_head->first = __list_next;                                       \
 560         if (!__list_next)                                                               \
 561                 __list_head->last = __list_prev;                                        \
 562         } while (0)
 563
 564 #define AST_RWLIST_REMOVE_CURRENT AST_LIST_REMOVE_CURRENT
 565
 566 #define AST_LIST_MOVE_CURRENT(newhead, field) do { \
 567         typeof ((newhead)->first) __list_cur = __new_prev;                              \
 568         AST_LIST_REMOVE_CURRENT(field);                                                 \
 569         AST_LIST_INSERT_TAIL((newhead), __list_cur, field);                             \
 570         } while (0)
 571
 572 #define AST_RWLIST_MOVE_CURRENT AST_LIST_MOVE_CURRENT
 573
 574 /*!
 575  * \brief Inserts a list entry before the current entry during a traversal.
 576  * \param elm This is a pointer to the entry to be inserted.
 577  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 578  * used to link entries of this list together.
 579  *
 580  * \note This macro can \b only be used inside an AST_LIST_TRAVERSE_SAFE_BEGIN()
 581  * block.
 582  */
 583 #define AST_LIST_INSERT_BEFORE_CURRENT(elm, field) do {                 \
 584         if (__list_prev) {                                              \
 585                 (elm)->field.next = __list_prev->field.next;            \
 586                 __list_prev->field.next = elm;                          \
 587         } else {                                                        \
 588                 (elm)->field.next = __list_head->first;                 \
 589                 __list_head->first = (elm);                             \
 590         }                                                               \
 591         __new_prev = (elm);                                             \
 592 } while (0)
 593
 594 #define AST_RWLIST_INSERT_BEFORE_CURRENT AST_LIST_INSERT_BEFORE_CURRENT
 595
 596 /*!
 597  * \brief Closes a safe loop traversal block.
 598  */
 599 #define AST_LIST_TRAVERSE_SAFE_END  }
 600
 601 #define AST_RWLIST_TRAVERSE_SAFE_END AST_LIST_TRAVERSE_SAFE_END
 602
 603 /*!
 604  * \brief Initializes a list head structure.
 605  * \param head This is a pointer to the list head structure
 606  *
 607  * This macro initializes a list head structure by setting the head
 608  * entry to \a NULL (empty list) and recreating the embedded lock.
 609  */
 610 #define AST_LIST_HEAD_INIT(head) {                                      \
 611         (head)->first = NULL;                                           \
 612         (head)->last = NULL;                                            \
 613         ast_mutex_init(&(head)->lock);                                  \
 614 }
 615
 616 /*!
 617  * \brief Initializes an rwlist head structure.
 618  * \param head This is a pointer to the list head structure
 619  *
 620  * This macro initializes a list head structure by setting the head
 621  * entry to \a NULL (empty list) and recreating the embedded lock.
 622  */
 623 #define AST_RWLIST_HEAD_INIT(head) {                                    \
 624         (head)->first = NULL;                                           \
 625         (head)->last = NULL;                                            \
 626         ast_rwlock_init(&(head)->lock);                                 \
 627 }
 628
 629 /*!
 630  * \brief Destroys a list head structure.
 631  * \param head This is a pointer to the list head structure
 632  *
 633  * This macro destroys a list head structure by setting the head
 634  * entry to \a NULL (empty list) and destroying the embedded lock.
 635  * It does not free the structure from memory.
 636  */
 637 #define AST_LIST_HEAD_DESTROY(head) {                                   \
 638         (head)->first = NULL;                                           \
 639         (head)->last = NULL;                                            \
 640         ast_mutex_destroy(&(head)->lock);                               \
 641 }
 642
 643 /*!
 644  * \brief Destroys an rwlist head structure.
 645  * \param head This is a pointer to the list head structure
 646  *
 647  * This macro destroys a list head structure by setting the head
 648  * entry to \a NULL (empty list) and destroying the embedded lock.
 649  * It does not free the structure from memory.
 650  */
 651 #define AST_RWLIST_HEAD_DESTROY(head) {                                 \
 652         (head)->first = NULL;                                           \
 653         (head)->last = NULL;                                            \
 654         ast_rwlock_destroy(&(head)->lock);                              \
 655 }
 656
 657 /*!
 658  * \brief Initializes a list head structure.
 659  * \param head This is a pointer to the list head structure
 660  *
 661  * This macro initializes a list head structure by setting the head
 662  * entry to \a NULL (empty list). There is no embedded lock handling
 663  * with this macro.
 664  */
 665 #define AST_LIST_HEAD_INIT_NOLOCK(head) {                               \
 666         (head)->first = NULL;                                           \
 667         (head)->last = NULL;                                            \
 668 }
 669
 670 /*!
 671  * \brief Inserts a list entry after a given entry.
 672  * \param head This is a pointer to the list head structure
 673  * \param listelm This is a pointer to the entry after which the new entry should
 674  * be inserted.
 675  * \param elm This is a pointer to the entry to be inserted.
 676  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 677  * used to link entries of this list together.
 678  */
 679 #define AST_LIST_INSERT_AFTER(head, listelm, elm, field) do {           \
 680         (elm)->field.next = (listelm)->field.next;                      \
 681         (listelm)->field.next = (elm);                                  \
 682         if ((head)->last == (listelm))                                  \
 683                 (head)->last = (elm);                                   \
 684 } while (0)
 685
 686 #define AST_RWLIST_INSERT_AFTER AST_LIST_INSERT_AFTER
 687
 688 /*!
 689  * \brief Inserts a list entry at the head of a list.
 690  * \param head This is a pointer to the list head structure
 691  * \param elm This is a pointer to the entry to be inserted.
 692  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 693  * used to link entries of this list together.
 694  */
 695 #define AST_LIST_INSERT_HEAD(head, elm, field) do {                     \
 696                 (elm)->field.next = (head)->first;                      \
 697                 (head)->first = (elm);                                  \
 698                 if (!(head)->last)                                      \
 699                         (head)->last = (elm);                           \
 700 } while (0)
 701
 702 #define AST_RWLIST_INSERT_HEAD AST_LIST_INSERT_HEAD
 703
 704 /*!
 705  * \brief Appends a list entry to the tail of a list.
 706  * \param head This is a pointer to the list head structure
 707  * \param elm This is a pointer to the entry to be appended.
 708  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 709  * used to link entries of this list together.
 710  *
 711  * Note: The link field in the appended entry is \b not modified, so if it is
 712  * actually the head of a list itself, the entire list will be appended
 713  * temporarily (until the next AST_LIST_INSERT_TAIL is performed).
 714  */
 715 #define AST_LIST_INSERT_TAIL(head, elm, field) do {                     \
 716       if (!(head)->first) {                                             \
 717                 (head)->first = (elm);                                  \
 718                 (head)->last = (elm);                                   \
 719       } else {                                                          \
 720                 (head)->last->field.next = (elm);                       \
 721                 (head)->last = (elm);                                   \
 722       }                                                                 \
 723 } while (0)
 724
 725 #define AST_RWLIST_INSERT_TAIL AST_LIST_INSERT_TAIL
 726
 727 /*!
 728  * \brief Inserts a list entry into a alphabetically sorted list
 729  * \param head Pointer to the list head structure
 730  * \param elm Pointer to the entry to be inserted
 731  * \param field Name of the list entry field (declared using AST_LIST_ENTRY())
 732  * \param sortfield Name of the field on which the list is sorted
 733  * \since 1.6.1
 734  */
 735 #define AST_LIST_INSERT_SORTALPHA(head, elm, field, sortfield) do { \
 736         if (!(head)->first) {                                           \
 737                 (head)->first = (elm);                                      \
 738                 (head)->last = (elm);                                       \
 739         } else {                                                        \
 740                 typeof((head)->first) cur = (head)->first, prev = NULL;     \
 741                 while (cur && strcmp(cur->sortfield, elm->sortfield) < 0) { \
 742                         prev = cur;                                             \
 743                         cur = cur->field.next;                                  \
 744                 }                                                           \
 745                 if (!prev) {                                                \
 746                         AST_LIST_INSERT_HEAD(head, elm, field);                 \
 747                 } else if (!cur) {                                          \
 748                         AST_LIST_INSERT_TAIL(head, elm, field);                 \
 749                 } else {                                                    \
 750                         AST_LIST_INSERT_AFTER(head, prev, elm, field);          \
 751                 }                                                           \
 752         }                                                               \
 753 } while (0)
 754
 755 #define AST_RWLIST_INSERT_SORTALPHA     AST_LIST_INSERT_SORTALPHA
 756
 757 /*!
 758  * \brief Appends a whole list to the tail of a list.
 759  * \param head This is a pointer to the list head structure
 760  * \param list This is a pointer to the list to be appended.
 761  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 762  * used to link entries of this list together.
 763  *
 764  * Note: The source list (the \a list parameter) will be empty after
 765  * calling this macro (the list entries are \b moved to the target list).
 766  */
 767 #define AST_LIST_APPEND_LIST(head, list, field) do {                    \
 768         if (!(list)->first) {                                           \
 769                 break;                                                  \
 770         }                                                               \
 771         if (!(head)->first) {                                           \
 772                 (head)->first = (list)->first;                          \
 773                 (head)->last = (list)->last;                            \
 774         } else {                                                        \
 775                 (head)->last->field.next = (list)->first;               \
 776                 (head)->last = (list)->last;                            \
 777         }                                                               \
 778         (list)->first = NULL;                                           \
 779         (list)->last = NULL;                                            \
 780 } while (0)
 781
 782 #define AST_RWLIST_APPEND_LIST AST_LIST_APPEND_LIST
 783
 784 /*!
 785   \brief Inserts a whole list after a specific entry in a list
 786   \param head This is a pointer to the list head structure
 787   \param list This is a pointer to the list to be inserted.
 788   \param elm This is a pointer to the entry after which the new list should
 789   be inserted.
 790   \param field This is the name of the field (declared using AST_LIST_ENTRY())
 791   used to link entries of the lists together.
 792
 793   Note: The source list (the \a list parameter) will be empty after
 794   calling this macro (the list entries are \b moved to the target list).
 795  */
 796 #define AST_LIST_INSERT_LIST_AFTER(head, list, elm, field) do {         \
 797         (list)->last->field.next = (elm)->field.next;                   \
 798         (elm)->field.next = (list)->first;                              \
 799         if ((head)->last == elm) {                                      \
 800                 (head)->last = (list)->last;                            \
 801         }                                                               \
 802         (list)->first = NULL;                                           \
 803         (list)->last = NULL;                                            \
 804 } while(0)
 805
 806 #define AST_RWLIST_INSERT_LIST_AFTER AST_LIST_INSERT_LIST_AFTER
 807
 808 /*!
 809  * \brief Removes and returns the head entry from a list.
 810  * \param head This is a pointer to the list head structure
 811  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 812  * used to link entries of this list together.
 813  *
 814  * Removes the head entry from the list, and returns a pointer to it.
 815  * This macro is safe to call on an empty list.
 816  */
 817 #define AST_LIST_REMOVE_HEAD(head, field) ({                            \
 818                 typeof((head)->first) cur = (head)->first;              \
 819                 if (cur) {                                              \
 820                         (head)->first = cur->field.next;                \
 821                         cur->field.next = NULL;                         \
 822                         if ((head)->last == cur)                        \
 823                                 (head)->last = NULL;                    \
 824                 }                                                       \
 825                 cur;                                                    \
 826         })
 827
 828 #define AST_RWLIST_REMOVE_HEAD AST_LIST_REMOVE_HEAD
 829
 830 /*!
 831  * \brief Removes a specific entry from a list.
 832  * \param head This is a pointer to the list head structure
 833  * \param elm This is a pointer to the entry to be removed.
 834  * \param field This is the name of the field (declared using AST_LIST_ENTRY())
 835  * used to link entries of this list together.
 836  * \warning The removed entry is \b not freed nor modified in any way.
 837  */
 838 #define AST_LIST_REMOVE(head, elm, field) ({                            \
 839         __typeof(elm) __res = NULL; \
 840         if ((head)->first == (elm)) {                                   \
 841                 __res = (head)->first;                      \
 842                 (head)->first = (elm)->field.next;                      \
 843                 if ((head)->last == (elm))                      \
 844                         (head)->last = NULL;                    \
 845         } else {                                                                \
 846                 typeof(elm) curelm = (head)->first;                     \
 847                 while (curelm && (curelm->field.next != (elm)))                 \
 848                         curelm = curelm->field.next;                    \
 849                 if (curelm) { \
 850                         __res = (elm); \
 851                         curelm->field.next = (elm)->field.next;                 \
 852                         if ((head)->last == (elm))                              \
 853                                 (head)->last = curelm;                          \
 854                 } \
 855         }                                                               \
 856         (elm)->field.next = NULL;                                       \
 857         (__res); \
 858 })
 859
 860 #define AST_RWLIST_REMOVE AST_LIST_REMOVE
 861
 862 #endif /* _ASTERISK_LINKEDLISTS_H */