Introducing doubly linked lists to trunk from branch team/murf/bug11210.
authorSteve Murphy <murf@digium.com>
Wed, 16 Apr 2008 17:14:18 +0000 (17:14 +0000)
committerSteve Murphy <murf@digium.com>
Wed, 16 Apr 2008 17:14:18 +0000 (17:14 +0000)
git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@114172 65c4cc65-6c06-0410-ace0-fbb531ad65f3

CHANGES
include/asterisk/dlinkedlists.h [new file with mode: 0644]
tests/test_dlinklists.c [new file with mode: 0644]

diff --git a/CHANGES b/CHANGES
index 338b986..1558c5c 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -615,6 +615,9 @@ Miscellaneous
   * A new option when starting a remote asterisk (rasterisk, asterisk -r) for
      specifying which socket to use to connect to the running Asterisk daemon
      (-s)
+  * Added Doubly-linked lists after the fashion of linkedlists.h. They are in
+    dlinkedlists.h. Doubly-linked lists feature fast deletion times.
+    Added regression tests to the tests/ dir, also.
   * Added logging to 'make update' command.  See update.log
   * Added strictrtp option to rtp.conf. If enabled this will drop RTP packets that
      do not come from the remote party.
diff --git a/include/asterisk/dlinkedlists.h b/include/asterisk/dlinkedlists.h
new file mode 100644 (file)
index 0000000..2f42fdd
--- /dev/null
@@ -0,0 +1,974 @@
+/*
+ * Asterisk -- An open source telephony toolkit.
+ *
+ * Copyright (C) 2007, Digium, Inc.
+ *
+ * Steve Murphy <murf@digium.com>
+ * 
+ * Doubly-Linked List Macros--
+ * Based on linkedlists.h (to the point of plagiarism!), which is by:
+ *
+ * Mark Spencer <markster@digium.com>
+ * Kevin P. Fleming <kpfleming@digium.com>
+ *
+ * See http://www.asterisk.org for more information about
+ * the Asterisk project. Please do not directly contact
+ * any of the maintainers of this project for assistance;
+ * the project provides a web site, mailing lists and IRC
+ * channels for your use.
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU General Public License Version 2. See the LICENSE file
+ * at the top of the source tree.
+ */
+
+#ifndef ASTERISK_DLINKEDLISTS_H
+#define ASTERISK_DLINKEDLISTS_H
+
+#include "asterisk/lock.h"
+
+/*!
+  \file dlinkedlists.h
+  \brief A set of macros to manage doubly-linked lists.
+*/
+
+/*!
+  \brief Locks a list.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to place an exclusive lock in the
+  list head structure pointed to by head.
+  \retval 0 on success
+  \retval non-zero on failure
+*/
+#define AST_DLLIST_LOCK(head)                                          \
+       ast_mutex_lock(&(head)->lock) 
+
+/*!
+  \brief Write locks a list.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to place an exclusive write lock in the
+  list head structure pointed to by head.
+  \retval 0 on success
+  \retval non-zero on failure
+*/
+#define AST_RWDLLIST_WRLOCK(head)                                         \
+        ast_rwlock_wrlock(&(head)->lock)
+
+/*!
+  \brief Read locks a list.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to place a read lock in the
+  list head structure pointed to by head.
+  \retval 0 on success
+  \retval non-zero on failure
+*/
+#define AST_RWDLLIST_RDLOCK(head)                                         \
+        ast_rwlock_rdlock(&(head)->lock)
+       
+/*!
+  \brief Locks a list, without blocking if the list is locked.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to place an exclusive lock in the
+  list head structure pointed to by head.
+  \retval 0 on success
+  \retval non-zero on failure
+*/
+#define AST_DLLIST_TRYLOCK(head)                                               \
+       ast_mutex_trylock(&(head)->lock) 
+
+/*!
+  \brief Write locks a list, without blocking if the list is locked.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to place an exclusive write lock in the
+  list head structure pointed to by head.
+  \retval 0 on success
+  \retval non-zero on failure
+*/
+#define AST_RWDLLIST_TRYWRLOCK(head)                                      \
+        ast_rwlock_trywrlock(&(head)->lock)
+
+/*!
+  \brief Read locks a list, without blocking if the list is locked.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to place a read lock in the
+  list head structure pointed to by head.
+  \retval 0 on success
+  \retval non-zero on failure
+*/
+#define AST_RWDLLIST_TRYRDLOCK(head)                                      \
+        ast_rwlock_tryrdlock(&(head)->lock)
+       
+/*!
+  \brief Attempts to unlock a list.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to remove an exclusive lock from the
+  list head structure pointed to by head. If the list
+  was not locked by this thread, this macro has no effect.
+*/
+#define AST_DLLIST_UNLOCK(head)                                                \
+       ast_mutex_unlock(&(head)->lock)
+
+/*!
+  \brief Attempts to unlock a read/write based list.
+  \param head This is a pointer to the list head structure
+
+  This macro attempts to remove a read or write lock from the
+  list head structure pointed to by head. If the list
+  was not locked by this thread, this macro has no effect.
+*/
+#define AST_RWDLLIST_UNLOCK(head)                                         \
+        ast_rwlock_unlock(&(head)->lock)
+
+/*!
+  \brief Defines a structure to be used to hold a list of specified type.
+  \param name This will be the name of the defined structure.
+  \param type This is the type of each list entry.
+
+  This macro creates a structure definition that can be used
+  to hold a list of the entries of type \a type. It does not actually
+  declare (allocate) a structure; to do that, either follow this
+  macro with the desired name of the instance you wish to declare,
+  or use the specified \a name to declare instances elsewhere.
+
+  Example usage:
+  \code
+  static AST_DLLIST_HEAD(entry_list, entry) entries;
+  \endcode
+
+  This would define \c struct \c entry_list, and declare an instance of it named
+  \a entries, all intended to hold a list of type \c struct \c entry.
+*/
+#define AST_DLLIST_HEAD(name, type)                                    \
+struct name {                                                          \
+       struct type *first;                                             \
+       struct type *last;                                              \
+       ast_mutex_t lock;                                               \
+}
+
+/*!
+  \brief Defines a structure to be used to hold a read/write list of specified type.
+  \param name This will be the name of the defined structure.
+  \param type This is the type of each list entry.
+
+  This macro creates a structure definition that can be used
+  to hold a list of the entries of type \a type. It does not actually
+  declare (allocate) a structure; to do that, either follow this
+  macro with the desired name of the instance you wish to declare,
+  or use the specified \a name to declare instances elsewhere.
+
+  Example usage:
+  \code
+  static AST_RWDLLIST_HEAD(entry_list, entry) entries;
+  \endcode
+
+  This would define \c struct \c entry_list, and declare an instance of it named
+  \a entries, all intended to hold a list of type \c struct \c entry.
+*/
+#define AST_RWDLLIST_HEAD(name, type)                                     \
+struct name {                                                           \
+        struct type *first;                                             \
+        struct type *last;                                              \
+        ast_rwlock_t lock;                                              \
+}
+
+/*!
+  \brief Defines a structure to be used to hold a list of specified type (with no lock).
+  \param name This will be the name of the defined structure.
+  \param type This is the type of each list entry.
+
+  This macro creates a structure definition that can be used
+  to hold a list of the entries of type \a type. It does not actually
+  declare (allocate) a structure; to do that, either follow this
+  macro with the desired name of the instance you wish to declare,
+  or use the specified \a name to declare instances elsewhere.
+
+  Example usage:
+  \code
+  static AST_DLLIST_HEAD_NOLOCK(entry_list, entry) entries;
+  \endcode
+
+  This would define \c struct \c entry_list, and declare an instance of it named
+  \a entries, all intended to hold a list of type \c struct \c entry.
+*/
+#define AST_DLLIST_HEAD_NOLOCK(name, type)                             \
+struct name {                                                          \
+       struct type *first;                                             \
+       struct type *last;                                              \
+}
+
+/*!
+  \brief Defines initial values for a declaration of AST_DLLIST_HEAD
+*/
+#define AST_DLLIST_HEAD_INIT_VALUE     {               \
+       .first = NULL,                                  \
+       .last = NULL,                                   \
+       .lock = AST_MUTEX_INIT_VALUE,                   \
+       }
+
+/*!
+  \brief Defines initial values for a declaration of AST_RWDLLIST_HEAD
+*/
+#define AST_RWDLLIST_HEAD_INIT_VALUE      {               \
+        .first = NULL,                                  \
+        .last = NULL,                                   \
+        .lock = AST_RWLOCK_INIT_VALUE,                  \
+        }
+
+/*!
+  \brief Defines initial values for a declaration of AST_DLLIST_HEAD_NOLOCK
+*/
+#define AST_DLLIST_HEAD_NOLOCK_INIT_VALUE      {       \
+       .first = NULL,                                  \
+       .last = NULL,                                   \
+       }
+
+/*!
+  \brief Defines a structure to be used to hold a list of specified type, statically initialized.
+  \param name This will be the name of the defined structure.
+  \param type This is the type of each list entry.
+
+  This macro creates a structure definition that can be used
+  to hold a list of the entries of type \a type, and allocates an instance
+  of it, initialized to be empty.
+
+  Example usage:
+  \code
+  static AST_DLLIST_HEAD_STATIC(entry_list, entry);
+  \endcode
+
+  This would define \c struct \c entry_list, intended to hold a list of
+  type \c struct \c entry.
+*/
+#if defined(AST_MUTEX_INIT_W_CONSTRUCTORS)
+#define AST_DLLIST_HEAD_STATIC(name, type)                             \
+struct name {                                                          \
+       struct type *first;                                             \
+       struct type *last;                                              \
+       ast_mutex_t lock;                                               \
+} name;                                                                        \
+static void  __attribute__ ((constructor)) __init_##name(void)         \
+{                                                                      \
+        AST_DLLIST_HEAD_INIT(&name);                                   \
+}                                                                      \
+static void  __attribute__ ((destructor)) __fini_##name(void)          \
+{                                                                      \
+        AST_DLLIST_HEAD_DESTROY(&name);                                        \
+}                                                                      \
+struct __dummy_##name
+#else
+#define AST_DLLIST_HEAD_STATIC(name, type)                             \
+struct name {                                                          \
+       struct type *first;                                             \
+       struct type *last;                                              \
+       ast_mutex_t lock;                                               \
+} name = AST_DLLIST_HEAD_INIT_VALUE
+#endif
+
+/*!
+  \brief Defines a structure to be used to hold a read/write list of specified type, statically initialized.
+  \param name This will be the name of the defined structure.
+  \param type This is the type of each list entry.
+
+  This macro creates a structure definition that can be used
+  to hold a list of the entries of type \a type, and allocates an instance
+  of it, initialized to be empty.
+
+  Example usage:
+  \code
+  static AST_RWDLLIST_HEAD_STATIC(entry_list, entry);
+  \endcode
+
+  This would define \c struct \c entry_list, intended to hold a list of
+  type \c struct \c entry.
+*/
+#ifndef AST_RWLOCK_INIT_VALUE
+#define AST_RWDLLIST_HEAD_STATIC(name, type)                              \
+struct name {                                                           \
+        struct type *first;                                             \
+        struct type *last;                                              \
+        ast_rwlock_t lock;                                              \
+} name;                                                                 \
+static void  __attribute__ ((constructor)) __init_##name(void)          \
+{                                                                       \
+        AST_RWDLLIST_HEAD_INIT(&name);                                    \
+}                                                                       \
+static void  __attribute__ ((destructor)) __fini_##name(void)           \
+{                                                                       \
+        AST_RWDLLIST_HEAD_DESTROY(&name);                                 \
+}                                                                       \
+struct __dummy_##name
+#else
+#define AST_RWDLLIST_HEAD_STATIC(name, type)                              \
+struct name {                                                           \
+        struct type *first;                                             \
+        struct type *last;                                              \
+        ast_rwlock_t lock;                                              \
+} name = AST_RWDLLIST_HEAD_INIT_VALUE
+#endif
+
+/*!
+  \brief Defines a structure to be used to hold a list of specified type, statically initialized.
+
+  This is the same as AST_DLLIST_HEAD_STATIC, except without the lock included.
+*/
+#define AST_DLLIST_HEAD_NOLOCK_STATIC(name, type)                              \
+struct name {                                                          \
+       struct type *first;                                             \
+       struct type *last;                                              \
+} name = AST_DLLIST_HEAD_NOLOCK_INIT_VALUE
+
+/*!
+  \brief Initializes a list head structure with a specified first entry.
+  \param head This is a pointer to the list head structure
+  \param entry pointer to the list entry that will become the head of the list
+
+  This macro initializes a list head structure by setting the head
+  entry to the supplied value and recreating the embedded lock.
+*/
+#define AST_DLLIST_HEAD_SET(head, entry) do {                          \
+       (head)->first = (entry);                                        \
+       (head)->last = (entry);                                         \
+       ast_mutex_init(&(head)->lock);                                  \
+} while (0)
+
+/*!
+  \brief Initializes an rwlist head structure with a specified first entry.
+  \param head This is a pointer to the list head structure
+  \param entry pointer to the list entry that will become the head of the list
+
+  This macro initializes a list head structure by setting the head
+  entry to the supplied value and recreating the embedded lock.
+*/
+#define AST_RWDLLIST_HEAD_SET(head, entry) do {                           \
+        (head)->first = (entry);                                        \
+        (head)->last = (entry);                                         \
+        ast_rwlock_init(&(head)->lock);                                 \
+} while (0)
+
+/*!
+  \brief Initializes a list head structure with a specified first entry.
+  \param head This is a pointer to the list head structure
+  \param entry pointer to the list entry that will become the head of the list
+
+  This macro initializes a list head structure by setting the head
+  entry to the supplied value.
+*/
+#define AST_DLLIST_HEAD_SET_NOLOCK(head, entry) do {                   \
+       (head)->first = (entry);                                        \
+       (head)->last = (entry);                                         \
+} while (0)
+
+/*!
+  \brief Declare previous/forward links inside a list entry.
+  \param type This is the type of each list entry.
+
+  This macro declares a structure to be used to doubly link list entries together.
+  It must be used inside the definition of the structure named in
+  \a type, as follows:
+
+  \code
+  struct list_entry {
+       ...
+       AST_DLLIST_ENTRY(list_entry) list;
+  }
+  \endcode
+
+  The field name \a list here is arbitrary, and can be anything you wish.
+*/
+#define AST_DLLIST_ENTRY(type)                 \
+struct {                                                               \
+       struct type *prev;                                              \
+       struct type *next;                                              \
+}
+
+#define AST_RWDLLIST_ENTRY AST_DLLIST_ENTRY
+/*!
+  \brief Returns the first entry contained in a list.
+  \param head This is a pointer to the list head structure
+ */
+#define        AST_DLLIST_FIRST(head)  ((head)->first)
+
+#define AST_RWDLLIST_FIRST AST_DLLIST_FIRST
+
+/*!
+  \brief Returns the last entry contained in a list.
+  \param head This is a pointer to the list head structure
+ */
+#define        AST_DLLIST_LAST(head)   ((head)->last)
+
+#define AST_RWDLLIST_LAST AST_DLLIST_LAST
+
+/*!
+  \brief Returns the next entry in the list after the given entry.
+  \param elm This is a pointer to the current entry.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+*/
+#define AST_DLLIST_NEXT(elm, field)    ((elm)->field.next)
+
+#define AST_RWDLLIST_NEXT AST_DLLIST_NEXT
+
+/*!
+  \brief Returns the previous entry in the list before the given entry.
+  \param elm This is a pointer to the current entry.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+*/
+#define AST_DLLIST_PREV(elm, field)    ((elm)->field.prev)
+
+#define AST_RWDLLIST_PREV AST_DLLIST_PREV
+
+/*!
+  \brief Checks whether the specified list contains any entries.
+  \param head This is a pointer to the list head structure
+
+  \return non-zero if the list has entries
+  \return zero if not.
+ */
+#define        AST_DLLIST_EMPTY(head)  (AST_DLLIST_FIRST(head) == NULL)
+
+#define AST_RWDLLIST_EMPTY AST_DLLIST_EMPTY
+
+/*!
+  \brief Loops over (traverses) the entries in a list.
+  \param head This is a pointer to the list head structure
+  \param var This is the name of the variable that will hold a pointer to the
+  current list entry on each iteration. It must be declared before calling
+  this macro.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  This macro is use to loop over (traverse) the entries in a list. It uses a
+  \a for loop, and supplies the enclosed code with a pointer to each list
+  entry as it loops. It is typically used as follows:
+  \code
+  static AST_DLLIST_HEAD(entry_list, list_entry) entries;
+  ...
+  struct list_entry {
+       ...
+       AST_DLLIST_ENTRY(list_entry) list;
+  }
+  ...
+  struct list_entry *current;
+  ...
+  AST_DLLIST_TRAVERSE(&entries, current, list) {
+     (do something with current here)
+  }
+  \endcode
+  \warning If you modify the forward-link pointer contained in the \a current entry while
+  inside the loop, the behavior will be unpredictable. At a minimum, the following
+  macros will modify the forward-link pointer, and should not be used inside
+  AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
+  careful consideration of their consequences:
+  \li AST_DLLIST_NEXT() (when used as an lvalue)
+  \li AST_DLLIST_INSERT_AFTER()
+  \li AST_DLLIST_INSERT_HEAD()
+  \li AST_DLLIST_INSERT_TAIL()
+*/
+#define AST_DLLIST_TRAVERSE(head,var,field)                            \
+       for((var) = (head)->first; (var); (var) = (var)->field.next)
+
+#define AST_RWDLLIST_TRAVERSE AST_DLLIST_TRAVERSE
+
+/*!
+  \brief Loops over (traverses) the entries in a list in reverse order, starting at the end.
+  \param head This is a pointer to the list head structure
+  \param var This is the name of the variable that will hold a pointer to the
+  current list entry on each iteration. It must be declared before calling
+  this macro.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  This macro is use to loop over (traverse) the entries in a list in reverse order. It uses a
+  \a for loop, and supplies the enclosed code with a pointer to each list
+  entry as it loops. It is typically used as follows:
+  \code
+  static AST_DLLIST_HEAD(entry_list, list_entry) entries;
+  ...
+  struct list_entry {
+       ...
+       AST_DLLIST_ENTRY(list_entry) list;
+  }
+  ...
+  struct list_entry *current;
+  ...
+  AST_DLLIST_TRAVERSE_BACKWARDS(&entries, current, list) {
+     (do something with current here)
+  }
+  \endcode
+  \warning If you modify the forward-link pointer contained in the \a current entry while
+  inside the loop, the behavior will be unpredictable. At a minimum, the following
+  macros will modify the forward-link pointer, and should not be used inside
+  AST_DLLIST_TRAVERSE() against the entry pointed to by the \a current pointer without
+  careful consideration of their consequences:
+  \li AST_DLLIST_PREV() (when used as an lvalue)
+  \li AST_DLLIST_INSERT_BEFORE()
+  \li AST_DLLIST_INSERT_HEAD()
+  \li AST_DLLIST_INSERT_TAIL()
+*/
+#define AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field)                          \
+       for((var) = (head)->last; (var); (var) = (var)->field.prev)
+
+#define AST_RWDLLIST_TRAVERSE_BACKWARDS AST_DLLIST_TRAVERSE_BACKWARDS
+
+/*!
+  \brief Loops safely over (traverses) the entries in a list.
+  \param head This is a pointer to the list head structure
+  \param var This is the name of the variable that will hold a pointer to the
+  current list entry on each iteration. It must be declared before calling
+  this macro.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  This macro is used to safely loop over (traverse) the entries in a list. It
+  uses a \a for loop, and supplies the enclosed code with a pointer to each list
+  entry as it loops. It is typically used as follows:
+
+  \code
+  static AST_DLLIST_HEAD(entry_list, list_entry) entries;
+  ...
+  struct list_entry {
+       ...
+       AST_DLLIST_ENTRY(list_entry) list;
+  }
+  ...
+  struct list_entry *current;
+  ...
+  AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
+     (do something with current here)
+  }
+  AST_DLLIST_TRAVERSE_SAFE_END;
+  \endcode
+
+  It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
+  (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
+  the \a current pointer without affecting the loop traversal.
+*/
+#define AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field) {                             \
+       typeof((head)) __list_head = head;                                              \
+       typeof(__list_head->first) __list_next;                                         \
+       typeof(__list_head->first) __list_prev = NULL;                                  \
+       typeof(__list_head->first) __new_prev = NULL;                                   \
+       for ((var) = __list_head->first, __new_prev = (var),                            \
+             __list_next = (var) ? (var)->field.next : NULL;                           \
+            (var);                                                                     \
+            __list_prev = __new_prev, (var) = __list_next,                             \
+            __new_prev = (var),                                                        \
+            __list_next = (var) ? (var)->field.next : NULL                             \
+           )
+
+#define AST_RWDLLIST_TRAVERSE_SAFE_BEGIN AST_DLLIST_TRAVERSE_SAFE_BEGIN
+
+/*!
+  \brief Loops safely over (traverses) the entries in a list.
+  \param head This is a pointer to the list head structure
+  \param var This is the name of the variable that will hold a pointer to the
+  current list entry on each iteration. It must be declared before calling
+  this macro.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  This macro is used to safely loop over (traverse) the entries in a list. It
+  uses a \a for loop, and supplies the enclosed code with a pointer to each list
+  entry as it loops. It is typically used as follows:
+
+  \code
+  static AST_DLLIST_HEAD(entry_list, list_entry) entries;
+  ...
+  struct list_entry {
+       ...
+       AST_DLLIST_ENTRY(list_entry) list;
+  }
+  ...
+  struct list_entry *current;
+  ...
+  AST_DLLIST_TRAVERSE_SAFE_BEGIN(&entries, current, list) {
+     (do something with current here)
+  }
+  AST_DLLIST_TRAVERSE_SAFE_END;
+  \endcode
+
+  It differs from AST_DLLIST_TRAVERSE() in that the code inside the loop can modify
+  (or even free, after calling AST_DLLIST_REMOVE_CURRENT()) the entry pointed to by
+  the \a current pointer without affecting the loop traversal.
+*/
+#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field) {                           \
+       typeof((head)) __list_head = head;                                              \
+       typeof(__list_head->first) __list_next;                                         \
+       typeof(__list_head->first) __list_prev = NULL;                                  \
+       typeof(__list_head->first) __new_prev = NULL;                                   \
+       for ((var) = __list_head->last, __new_prev = (var),                             \
+                        __list_next = NULL, __list_prev = (var) ? (var)->field.prev : NULL;    \
+            (var);                                                                     \
+            __list_next = __new_prev, (var) = __list_prev,                             \
+            __new_prev = (var),                                                        \
+            __list_prev = (var) ? (var)->field.prev : NULL                             \
+           )
+
+#define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN
+
+/*!
+  \brief Removes the \a current entry from a list during a traversal.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_SAFE_BEGIN()
+  block; it is used to unlink the current entry from the list without affecting
+  the list traversal (and without having to re-traverse the list to modify the
+  previous entry, if any).
+ */
+#define AST_DLLIST_REMOVE_CURRENT(field) do {                  \
+       __new_prev->field.next = NULL;                                          \
+       __new_prev->field.prev = NULL;                                          \
+       if (__list_next)                                                                        \
+               __new_prev = __list_prev;                                               \
+       else                                                                                            \
+               __new_prev = NULL;                                                              \
+       if (__list_prev) {                                  \
+               if (__list_next)                                                                \
+                       __list_next->field.prev = __list_prev;          \
+               __list_prev->field.next = __list_next;                  \
+       } else {                                            \
+               __list_head->first = __list_next;                               \
+               if (__list_next)                                                                \
+                       __list_next->field.prev = NULL;                         \
+       }                                                                                                       \
+       if (!__list_next)                                                                       \
+               __list_head->last = __list_prev;                                \
+       } while (0)
+
+#define AST_RWDLLIST_REMOVE_CURRENT AST_DLLIST_REMOVE_CURRENT
+
+#define AST_DLLIST_MOVE_CURRENT(newhead, field) do { \
+       typeof ((newhead)->first) __list_cur = __new_prev;                              \
+       AST_DLLIST_REMOVE_CURRENT(field);                                                       \
+       AST_DLLIST_INSERT_TAIL((newhead), __list_cur, field);                           \
+       } while (0)
+
+#define AST_RWDLLIST_MOVE_CURRENT AST_DLLIST_MOVE_CURRENT
+
+#define AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field) do { \
+       typeof ((newhead)->first) __list_cur = __new_prev;                      \
+       if (!__list_next) {                                                                                     \
+               AST_DLLIST_REMOVE_CURRENT(field);                                               \
+               __new_prev = NULL;                                                                              \
+               AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field);   \
+       } else {                                                                                                        \
+               AST_DLLIST_REMOVE_CURRENT(field);                                               \
+               AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field);   \
+       }} while (0)
+
+#define AST_RWDLLIST_MOVE_CURRENT_BACKWARDS AST_DLLIST_MOVE_CURRENT
+
+/*!
+  \brief Inserts a list entry before the current entry during a traversal.
+  \param elm This is a pointer to the entry to be inserted.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_SAFE_BEGIN()
+  block.
+ */
+#define AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) do {      \
+       if (__list_prev) {                                                                              \
+               (elm)->field.next = __list_prev->field.next;            \
+               (elm)->field.prev = __list_prev;                                        \
+               if (__list_prev->field.next)                        \
+                       __list_prev->field.next->field.prev = (elm);    \
+               __list_prev->field.next = (elm);                                        \
+       } else {                                                                                                \
+               (elm)->field.next = __list_head->first;                 \
+               __list_head->first->field.prev = (elm);                 \
+               (elm)->field.prev = NULL;                                               \
+               __list_head->first = (elm);                                             \
+       }                                                                                                       \
+} while (0)
+
+#define AST_RWDLLIST_INSERT_BEFORE_CURRENT AST_DLLIST_INSERT_BEFORE_CURRENT
+
+/*!
+  \brief Inserts a list entry after the current entry during a backwards traversal. Since
+         this is a backwards traversal, this will insert the entry AFTER the current
+         element. Since this is a backwards traveral, though, this would be BEFORE
+         the current entry in traversal order. Confusing? 
+  \param elm This is a pointer to the entry to be inserted.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  \note This macro can \b only be used inside an AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN()
+  block. If you use this with the AST_DLLIST_TRAVERSE_SAFE_BEGIN(), be prepared for
+  strange things!
+ */
+#define AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field) do {                    \
+       if (__list_next) {                                                              \
+               (elm)->field.next = __list_next;                        \
+               (elm)->field.prev = __new_prev;                         \
+               __new_prev->field.next = (elm);                         \
+               __list_next->field.prev = (elm);                        \
+       } else {                                                                                \
+               (elm)->field.prev = __list_head->last;          \
+               (elm)->field.next = NULL;                                       \
+               __list_head->last->field.next = (elm);          \
+               __list_head->last = (elm);                                      \
+       }                                                                                               \
+} while (0)
+
+#define AST_RWDLLIST_INSERT_BEFORE_CURRENT_BACKWARDS AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS
+
+/*!
+  \brief Closes a safe loop traversal block.
+ */
+#define AST_DLLIST_TRAVERSE_SAFE_END  }
+
+#define AST_RWDLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_SAFE_END
+
+/*!
+  \brief Closes a safe loop traversal block.
+ */
+#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END  }
+
+#define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
+
+/*!
+  \brief Initializes a list head structure.
+  \param head This is a pointer to the list head structure
+
+  This macro initializes a list head structure by setting the head
+  entry to \a NULL (empty list) and recreating the embedded lock.
+*/
+#define AST_DLLIST_HEAD_INIT(head) {                                   \
+       (head)->first = NULL;                                           \
+       (head)->last = NULL;                                            \
+       ast_mutex_init(&(head)->lock);                                  \
+}
+
+/*!
+  \brief Initializes an rwlist head structure.
+  \param head This is a pointer to the list head structure
+
+  This macro initializes a list head structure by setting the head
+  entry to \a NULL (empty list) and recreating the embedded lock.
+*/
+#define AST_RWDLLIST_HEAD_INIT(head) {                                    \
+        (head)->first = NULL;                                           \
+        (head)->last = NULL;                                            \
+        ast_rwlock_init(&(head)->lock);                                 \
+}
+
+/*!
+  \brief Destroys a list head structure.
+  \param head This is a pointer to the list head structure
+
+  This macro destroys a list head structure by setting the head
+  entry to \a NULL (empty list) and destroying the embedded lock.
+  It does not free the structure from memory.
+*/
+#define AST_DLLIST_HEAD_DESTROY(head) {                                        \
+       (head)->first = NULL;                                           \
+       (head)->last = NULL;                                            \
+       ast_mutex_destroy(&(head)->lock);                               \
+}
+
+/*!
+  \brief Destroys an rwlist head structure.
+  \param head This is a pointer to the list head structure
+
+  This macro destroys a list head structure by setting the head
+  entry to \a NULL (empty list) and destroying the embedded lock.
+  It does not free the structure from memory.
+*/
+#define AST_RWDLLIST_HEAD_DESTROY(head) {                                 \
+        (head)->first = NULL;                                           \
+        (head)->last = NULL;                                            \
+        ast_rwlock_destroy(&(head)->lock);                              \
+}
+
+/*!
+  \brief Initializes a list head structure.
+  \param head This is a pointer to the list head structure
+
+  This macro initializes a list head structure by setting the head
+  entry to \a NULL (empty list). There is no embedded lock handling
+  with this macro.
+*/
+#define AST_DLLIST_HEAD_INIT_NOLOCK(head) {                            \
+       (head)->first = NULL;                                           \
+       (head)->last = NULL;                                            \
+}
+
+/*!
+  \brief Inserts a list entry after a given entry.
+  \param head This is a pointer to the list head structure
+  \param listelm This is a pointer to the entry after which the new entry should
+  be inserted.
+  \param elm This is a pointer to the entry to be inserted.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+ */
+#define AST_DLLIST_INSERT_AFTER(head, listelm, elm, field) do {                \
+       (elm)->field.next = (listelm)->field.next;                      \
+       (elm)->field.prev = (listelm);                  \
+       if ((listelm)->field.next)                              \
+               (listelm)->field.next->field.prev = (elm);      \
+       (listelm)->field.next = (elm);                                  \
+       if ((head)->last == (listelm))                                  \
+               (head)->last = (elm);                                   \
+} while (0)
+
+#define AST_RWDLLIST_INSERT_AFTER AST_DLLIST_INSERT_AFTER
+
+/*!
+  \brief Inserts a list entry before a given entry.
+  \param head This is a pointer to the list head structure
+  \param listelm This is a pointer to the entry before which the new entry should
+  be inserted.
+  \param elm This is a pointer to the entry to be inserted.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+ */
+#define AST_DLLIST_INSERT_BEFORE(head, listelm, elm, field) do {               \
+       (elm)->field.next = (listelm);                  \
+       (elm)->field.prev = (listelm)->field.prev;                      \
+       if ((listelm)->field.prev)                              \
+               (listelm)->field.prev->field.next = (elm);      \
+       (listelm)->field.prev = (elm);                                  \
+       if ((head)->first == (listelm))                                 \
+               (head)->first = (elm);                                  \
+} while (0)
+
+#define AST_RWDLLIST_INSERT_BEFORE AST_DLLIST_INSERT_BEFORE
+
+/*!
+  \brief Inserts a list entry at the head of a list.
+  \param head This is a pointer to the list head structure
+  \param elm This is a pointer to the entry to be inserted.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+ */
+#define AST_DLLIST_INSERT_HEAD(head, elm, field) do {                  \
+               (elm)->field.next = (head)->first;                      \
+               if ((head)->first)                          \
+                       (head)->first->field.prev = (elm);                      \
+               (elm)->field.prev = NULL;                       \
+               (head)->first = (elm);                                  \
+               if (!(head)->last)                                      \
+                       (head)->last = (elm);                           \
+} while (0)
+
+#define AST_RWDLLIST_INSERT_HEAD AST_DLLIST_INSERT_HEAD
+
+/*!
+  \brief Appends a list entry to the tail of a list.
+  \param head This is a pointer to the list head structure
+  \param elm This is a pointer to the entry to be appended.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  Note: The link field in the appended entry is \b not modified, so if it is
+  actually the head of a list itself, the entire list will be appended
+  temporarily (until the next AST_DLLIST_INSERT_TAIL is performed).
+ */
+#define AST_DLLIST_INSERT_TAIL(head, elm, field) do {  \
+      if (!(head)->first) {                                            \
+               (head)->first = (elm);                                  \
+               (head)->last = (elm);                   \
+               (elm)->field.next = NULL;                               \
+               (elm)->field.prev = NULL;                               \
+      } else {                                                                 \
+               (head)->last->field.next = (elm);               \
+               (elm)->field.prev = (head)->last;               \
+               (elm)->field.next = NULL;                               \
+               (head)->last = (elm);                                   \
+      }                                                                                        \
+} while (0)
+
+#define AST_RWDLLIST_INSERT_TAIL AST_DLLIST_INSERT_TAIL
+
+/*!
+  \brief Appends a whole list to the tail of a list.
+  \param head This is a pointer to the list head structure
+  \param list This is a pointer to the list to be appended.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  Note: The source list (the \a list parameter) will be empty after
+  calling this macro (the list entries are \b moved to the target list).
+ */
+#define AST_DLLIST_APPEND_DLLIST(head, list, field) do {                       \
+      if (!(head)->first) {                                            \
+               (head)->first = (list)->first;                          \
+               (head)->last = (list)->last;                            \
+      } else {                                                         \
+               (head)->last->field.next = (list)->first;               \
+               (list)->first->field.prev = (head)->last;               \
+               (head)->last = (list)->last;                            \
+      }                                                                        \
+      (list)->first = NULL;                                            \
+      (list)->last = NULL;                                             \
+} while (0)
+
+#define AST_RWDLLIST_APPEND_DLLIST AST_DLLIST_APPEND_DLLIST
+
+/*!
+  \brief Removes and returns the head entry from a list.
+  \param head This is a pointer to the list head structure
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+
+  Removes the head entry from the list, and returns a pointer to it.
+  This macro is safe to call on an empty list.
+ */
+#define AST_DLLIST_REMOVE_HEAD(head, field) ({                         \
+               typeof((head)->first) cur = (head)->first;              \
+               if (cur) {                                              \
+                       (head)->first = cur->field.next;                \
+                       if (cur->field.next)                \
+                               cur->field.next->field.prev = NULL;     \
+                       cur->field.next = NULL;                         \
+                       if ((head)->last == cur)                        \
+                               (head)->last = NULL;                    \
+               }                                                       \
+               cur;                                                    \
+       })
+
+#define AST_RWDLLIST_REMOVE_HEAD AST_DLLIST_REMOVE_HEAD
+
+/*!
+  \brief Removes a specific entry from a list.
+  \param head This is a pointer to the list head structure
+  \param elm This is a pointer to the entry to be removed.
+  \param field This is the name of the field (declared using AST_DLLIST_ENTRY())
+  used to link entries of this list together.
+  \warning The removed entry is \b not freed nor modified in any way.
+ */
+#define AST_DLLIST_REMOVE(head, elm, field) ({                         \
+       __typeof(elm) __res = (elm);                                            \
+       if ((head)->first == (elm)) {                                                           \
+               (head)->first = (elm)->field.next;                                              \
+               if ((elm)->field.next)                                                                  \
+                       (elm)->field.next->field.prev = NULL;                           \
+               if ((head)->last == (elm))                                                              \
+                       (head)->last = NULL;                                                            \
+       } else {                                                                                                                \
+               (elm)->field.prev->field.next = (elm)->field.next;                      \
+               if ((elm)->field.next)                                                                                  \
+                       (elm)->field.next->field.prev = (elm)->field.prev;                      \
+               if ((head)->last == (elm))                                                                              \
+                       (head)->last = (elm)->field.prev;                                                       \
+       }                                                                                                                                       \
+       (elm)->field.next = NULL;                                                                                       \
+       (elm)->field.prev = NULL;                                                                                       \
+       (__res);                                                                                                                        \
+})
+
+#define AST_RWDLLIST_REMOVE AST_DLLIST_REMOVE
+
+#endif /* _ASTERISK_DLINKEDLISTS_H */
diff --git a/tests/test_dlinklists.c b/tests/test_dlinklists.c
new file mode 100644 (file)
index 0000000..45a34ea
--- /dev/null
@@ -0,0 +1,363 @@
+/*
+ * Asterisk -- An open source telephony toolkit.
+ *
+ * Copyright (C) 2008, Steve Murphy
+ *
+ * Steve Murphy <murf@digium.com>
+ *
+ * See http://www.asterisk.org for more information about
+ * the Asterisk project. Please do not directly contact
+ * any of the maintainers of this project for assistance;
+ * the project provides a web site, mailing lists and IRC
+ * channels for your use.
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU General Public License Version 2. See the LICENSE file
+ * at the top of the source tree.
+ */
+
+/*! \file
+ *
+ * \brief Doubly-Linked List Tests
+ *
+ * \author\verbatim Steve Murphy <murf@digium.com> \endverbatim
+ * 
+ * This module will run some DLL tests at load time
+ * \ingroup tests
+ */
+
+/*** MODULEINFO
+       <defaultenabled>no</defaultenabled>
+ ***/
+
+#include "asterisk.h"
+
+ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
+
+#include "asterisk/file.h"
+#include "asterisk/channel.h"
+#include "asterisk/pbx.h"
+#include "asterisk/module.h"
+#include "asterisk/lock.h"
+#include "asterisk/app.h"
+
+
+#include "asterisk/dlinkedlists.h"
+
+/* Tests for DLLists! We really should, and here is a nice place to do it in asterisk */
+
+struct test1
+{
+       char name[10];
+       AST_DLLIST_ENTRY(test1) list;
+};
+
+struct test_container
+{
+       AST_DLLIST_HEAD(entries, test1) entries;
+    int count;
+};
+
+static void print_list(struct test_container *x, char *expect)
+{
+       struct test1 *t1;
+       char buff[1000];
+       buff[0] = 0;
+       AST_DLLIST_TRAVERSE(&x->entries, t1, list) {
+               strcat(buff,t1->name);
+               if (t1 != AST_DLLIST_LAST(&x->entries))
+                       strcat(buff," <=> ");
+       }
+       
+       ast_log(LOG_NOTICE,"Got: %s  [expect %s]\n", buff, expect);
+}
+
+static void print_list_backwards(struct test_container *x, char *expect)
+{
+       struct test1 *t1;
+       char buff[1000];
+       buff[0] = 0;
+       AST_DLLIST_TRAVERSE_BACKWARDS(&x->entries, t1, list) {
+               strcat(buff,t1->name);
+               if (t1 != AST_DLLIST_FIRST(&x->entries))
+                       strcat(buff," <=> ");
+       }
+       
+       ast_log(LOG_NOTICE,"Got: %s  [expect %s]\n", buff, expect);
+}
+
+static struct test_container *make_cont(void)
+{
+       struct test_container *t = ast_calloc(sizeof(struct test_container),1);
+       return t;
+}
+
+static struct test1 *make_test1(char *name)
+{
+       struct test1 *t1 = ast_calloc(sizeof(struct test1),1);
+       strcpy(t1->name, name);
+       return t1;
+}
+
+static void destroy_test_container(struct test_container *x)
+{
+       /* remove all the test1's */
+       struct test1 *t1;
+       AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&x->entries, t1, list) {
+               AST_DLLIST_REMOVE_CURRENT(list);
+               free(t1);
+       }
+       AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
+       free(x);
+}
+
+/* Macros to test:
+AST_DLLIST_LOCK(head)
+AST_RWDLLIST_WRLOCK(head)
+AST_RWDLLIST_WRLOCK(head) 
+AST_RWDLLIST_RDLOCK(head)
+AST_DLLIST_TRYLOCK(head)
+AST_RWDLLIST_TRYWRLOCK(head)
+AST_RWDLLIST_TRYRDLOCK(head)
+AST_DLLIST_UNLOCK(head)
+AST_RWDLLIST_UNLOCK(head)
+
+AST_DLLIST_HEAD(name, type)
+AST_RWDLLIST_HEAD(name, type)
+AST_DLLIST_HEAD_NOLOCK(name, type)
+AST_DLLIST_HEAD_STATIC(name, type)
+AST_RWDLLIST_HEAD_STATIC(name, type)
+AST_DLLIST_HEAD_NOLOCK_STATIC(name, type)
+AST_DLLIST_HEAD_SET(head, entry)
+AST_RWDLLIST_HEAD_SET(head, entry)
+AST_DLLIST_HEAD_SET_NOLOCK(head, entry)
+AST_DLLIST_HEAD_INIT(head)
+AST_RWDLLIST_HEAD_INIT(head)
+AST_DLLIST_HEAD_INIT_NOLOCK(head)
+
+AST_RWDLLIST_HEAD_DESTROY(head)
+
+AST_DLLIST_ENTRY(type)
+
+--- the above not going to be dealt with here ---
+
+AST_DLLIST_INSERT_HEAD(head, elm, field)
+AST_DLLIST_TRAVERSE(head,var,field)
+AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field)
+AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
+AST_DLLIST_FIRST(head)
+AST_DLLIST_LAST(head)
+AST_DLLIST_NEXT(elm, field)
+AST_DLLIST_PREV(elm, field)
+AST_DLLIST_EMPTY(head)
+AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field)
+AST_DLLIST_INSERT_AFTER(head, listelm, elm, field)
+AST_DLLIST_INSERT_TAIL(head, elm, field)
+AST_DLLIST_REMOVE_HEAD(head, field)
+AST_DLLIST_REMOVE(head, elm, field)
+AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field)
+AST_DLLIST_TRAVERSE_SAFE_END
+AST_DLLIST_REMOVE_CURRENT(field)
+AST_DLLIST_MOVE_CURRENT(newhead, field)
+AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) 
+
+
+AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field)
+AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field)
+AST_DLLIST_HEAD_DESTROY(head)
+
+AST_DLLIST_APPEND_DLLIST(head, list, field)
+
+*/
+
+static void dll_tests(void)
+{
+       struct test_container *tc;
+       struct test1 *a;
+       struct test1 *b;
+       struct test1 *c;
+       struct test1 *d;
+       struct test1 *e;
+       
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_INSERT_HEAD, AST_DLLIST_TRAVERSE, AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN, AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END\n");
+       tc = make_cont();
+       a = make_test1("A");
+       b = make_test1("B");
+       c = make_test1("C");
+       d = make_test1("D");
+       AST_DLLIST_INSERT_HEAD(&tc->entries, d, list);
+       AST_DLLIST_INSERT_HEAD(&tc->entries, c, list);
+       AST_DLLIST_INSERT_HEAD(&tc->entries, b, list);
+       AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
+       print_list(tc, "A <=> B <=> C <=> D");
+
+       destroy_test_container(tc);
+       
+       tc = make_cont();
+
+       if (AST_DLLIST_EMPTY(&tc->entries))
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_EMPTY....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_EMPTY....PROBLEM!!\n");
+
+
+       a = make_test1("A");
+       b = make_test1("B");
+       c = make_test1("C");
+       d = make_test1("D");
+       
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_INSERT_TAIL\n");
+       AST_DLLIST_INSERT_TAIL(&tc->entries, a, list);
+       AST_DLLIST_INSERT_TAIL(&tc->entries, b, list);
+       AST_DLLIST_INSERT_TAIL(&tc->entries, c, list);
+       AST_DLLIST_INSERT_TAIL(&tc->entries, d, list);
+       print_list(tc, "A <=> B <=> C <=> D");
+
+       if (AST_DLLIST_FIRST(&tc->entries) == a)
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_FIRST....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_FIRST....PROBLEM\n");
+
+       if (AST_DLLIST_LAST(&tc->entries) == d)
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_LAST....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_LAST....PROBLEM\n");
+
+       if (AST_DLLIST_NEXT(a,list) == b)
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_NEXT....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_NEXT....PROBLEM\n");
+
+       if (AST_DLLIST_PREV(d,list) == c)
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_PREV....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_PREV....PROBLEM\n");
+
+       destroy_test_container(tc);
+
+       tc = make_cont();
+
+       a = make_test1("A");
+       b = make_test1("B");
+       c = make_test1("C");
+       d = make_test1("D");
+
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_INSERT_AFTER, AST_DLLIST_TRAVERSE_BACKWARDS\n");
+       AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, c, d, list);
+       print_list_backwards(tc, "D <=> C <=> B <=> A");
+
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD\n");
+       AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
+       print_list_backwards(tc, "D <=> C <=> B");
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD\n");
+       AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
+       print_list_backwards(tc, "D <=> C");
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD\n");
+       AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
+       print_list_backwards(tc, "D");
+       AST_DLLIST_REMOVE_HEAD(&tc->entries, list);
+
+       if (AST_DLLIST_EMPTY(&tc->entries))
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_HEAD....PROBLEM!!\n");
+
+       AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, c, d, list);
+
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE\n");
+       AST_DLLIST_REMOVE(&tc->entries, c, list);
+       print_list(tc, "A <=> B <=> D");
+       AST_DLLIST_REMOVE(&tc->entries, a, list);
+       print_list(tc, "B <=> D");
+       AST_DLLIST_REMOVE(&tc->entries, d, list);
+       print_list(tc, "B");
+       AST_DLLIST_REMOVE(&tc->entries, b, list);
+       
+       if (AST_DLLIST_EMPTY(&tc->entries))
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE....OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE....PROBLEM!!\n");
+
+       AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, c, d, list);
+
+       AST_DLLIST_TRAVERSE_SAFE_BEGIN(&tc->entries, e, list) {
+               AST_DLLIST_REMOVE_CURRENT(list);
+       }
+       AST_DLLIST_TRAVERSE_SAFE_END;
+       if (AST_DLLIST_EMPTY(&tc->entries))
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_CURRENT... OK\n");
+       else
+               ast_log(LOG_NOTICE,"Test AST_DLLIST_REMOVE_CURRENT... PROBLEM\n");
+       
+       ast_log(LOG_NOTICE,"Test AST_DLLIST_MOVE_CURRENT, AST_DLLIST_INSERT_BEFORE_CURRENT\n");
+       AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
+       AST_DLLIST_TRAVERSE_SAFE_BEGIN(&tc->entries, e, list) {
+               if (e == a) {
+                       AST_DLLIST_INSERT_BEFORE_CURRENT(d, list);  /* D A B C */
+               }
+               
+               if (e == b) {
+                       AST_DLLIST_MOVE_CURRENT(&tc->entries, list); /* D A C B */
+               }
+               
+       }
+       AST_DLLIST_TRAVERSE_SAFE_END;
+       print_list(tc, "D <=> A <=> C <=> B");
+       
+       destroy_test_container(tc);
+
+       tc = make_cont();
+
+       a = make_test1("A");
+       b = make_test1("B");
+       c = make_test1("C");
+       d = make_test1("D");
+
+       ast_log(LOG_NOTICE,"Test: AST_DLLIST_MOVE_CURRENT_BACKWARDS and AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS\n");
+       AST_DLLIST_INSERT_HEAD(&tc->entries, a, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, a, b, list);
+       AST_DLLIST_INSERT_AFTER(&tc->entries, b, c, list);
+       AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&tc->entries, e, list) {
+               if (e == c && AST_DLLIST_FIRST(&tc->entries) != c) {
+                       AST_DLLIST_MOVE_CURRENT_BACKWARDS(&tc->entries, list); /* C A B */
+                       print_list(tc, "C <=> A <=> B");
+               }
+
+               if (e == b) {
+                       AST_DLLIST_REMOVE_CURRENT(list);  /* C A */
+                       print_list(tc, "C <=> A");
+               }
+               if (e == a) {
+                       AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(d, list); /* C A D */
+                       print_list(tc, "C <=> A <=> D");
+               }
+               
+       }
+       AST_DLLIST_TRAVERSE_SAFE_END;
+       print_list(tc, "C <=> A <=> D");
+
+}
+
+static int unload_module(void)
+{
+       return 0;
+}
+
+static int load_module(void)
+{
+       dll_tests();
+       return AST_MODULE_LOAD_SUCCESS;
+}
+
+AST_MODULE_INFO_STANDARD(ASTERISK_GPL_KEY, "Test Doubly-Linked Lists");