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