diff options
| -rw-r--r-- | include/asterisk/dlinkedlists.h | 1918 | ||||
| -rw-r--r-- | tests/test_linkedlists.c | 381 |
2 files changed, 1442 insertions, 857 deletions
diff --git a/include/asterisk/dlinkedlists.h b/include/asterisk/dlinkedlists.h index fba69ecdf..31e4d8ddb 100644 --- a/include/asterisk/dlinkedlists.h +++ b/include/asterisk/dlinkedlists.h @@ -28,994 +28,1212 @@ #include "asterisk/lock.h" /*! - \file dlinkedlists.h - \brief A set of macros to manage doubly-linked lists. -*/ + * \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 - \since 1.6.1 -*/ + * \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 + * \since 1.6.1 + */ #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 - \since 1.6.1 -*/ -#define AST_RWDLLIST_WRLOCK(head) \ - ast_rwlock_wrlock(&(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 + * \since 1.6.1 + */ +#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 - \since 1.6.1 -*/ -#define AST_RWDLLIST_RDLOCK(head) \ - ast_rwlock_rdlock(&(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 + * \since 1.6.1 + */ +#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 - \since 1.6.1 -*/ -#define AST_DLLIST_TRYLOCK(head) \ + * \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 + * \since 1.6.1 + */ +#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 - \since 1.6.1 -*/ -#define AST_RWDLLIST_TRYWRLOCK(head) \ - ast_rwlock_trywrlock(&(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 + * \since 1.6.1 + */ +#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 - \since 1.6.1 -*/ -#define AST_RWDLLIST_TRYRDLOCK(head) \ - ast_rwlock_tryrdlock(&(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 + * \since 1.6.1 + */ +#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. - \since 1.6.1 -*/ -#define AST_DLLIST_UNLOCK(head) \ + * \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. + * \since 1.6.1 + */ +#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. - \since 1.6.1 -*/ -#define AST_RWDLLIST_UNLOCK(head) \ - ast_rwlock_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. + * \since 1.6.1 + */ +#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. - \since 1.6.1 -*/ + * \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. + * \since 1.6.1 + */ #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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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 - \since 1.6.1 -*/ -#define AST_DLLIST_HEAD_INIT_VALUE { \ - .first = NULL, \ - .last = NULL, \ - .lock = AST_MUTEX_INIT_VALUE, \ + struct name { \ + struct type *first; \ + struct type *last; \ + ast_mutex_t lock; \ } /*! - \brief Defines initial values for a declaration of AST_RWDLLIST_HEAD - \since 1.6.1 -*/ -#define AST_RWDLLIST_HEAD_INIT_VALUE { \ - .first = NULL, \ - .last = NULL, \ - .lock = AST_RWLOCK_INIT_VALUE, \ - } + * \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. + * \since 1.6.1 + */ +#define AST_RWDLLIST_HEAD(name, type) \ + struct name { \ + struct type *first; \ + struct type *last; \ + ast_rwlock_t lock; \ + } /*! - \brief Defines initial values for a declaration of AST_DLLIST_HEAD_NOLOCK - \since 1.6.1 -*/ -#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 (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. + * \since 1.6.1 + */ +#define AST_DLLIST_HEAD_NOLOCK(name, type) \ + struct name { \ + struct type *first; \ + struct type *last; \ } /*! - \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. + * \brief Defines initial values for a declaration of AST_DLLIST_HEAD + * \since 1.6.1 + */ +#define AST_DLLIST_HEAD_INIT_VALUE \ + { \ + .first = NULL, \ + .last = NULL, \ + .lock = AST_MUTEX_INIT_VALUE, \ + } - 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. +/*! + * \brief Defines initial values for a declaration of AST_RWDLLIST_HEAD + * \since 1.6.1 + */ +#define AST_RWDLLIST_HEAD_INIT_VALUE \ + { \ + .first = NULL, \ + .last = NULL, \ + .lock = AST_RWLOCK_INIT_VALUE, \ + } - Example usage: - \code - static AST_DLLIST_HEAD_STATIC(entry_list, entry); - \endcode +/*! + * \brief Defines initial values for a declaration of AST_DLLIST_HEAD_NOLOCK + * \since 1.6.1 + */ +#define AST_DLLIST_HEAD_NOLOCK_INIT_VALUE \ + { \ + .first = NULL, \ + .last = NULL, \ + } - This would define \c struct \c entry_list, intended to hold a list of - type \c struct \c entry. - \since 1.6.1 -*/ +/*! + * \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. + * \since 1.6.1 + */ #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 +#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 +#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. - \since 1.6.1 -*/ -#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 + * \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. + * \since 1.6.1 + */ +#ifndef HAVE_PTHREAD_RWLOCK_INITIALIZER +#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 +#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#define AST_DLLIST_ENTRY(type) \ -struct { \ - struct type *prev; \ - struct type *next; \ -} + * \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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#define AST_DLLIST_ENTRY(type) AST_DLLIST_HEAD_NOLOCK(, type) #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 - \since 1.6.1 + * \brief Returns the first entry contained in a list. + * \param head This is a pointer to the list head structure + * \since 1.6.1 */ #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 - \since 1.6.1 + * \brief Returns the last entry contained in a list. + * \param head This is a pointer to the list head structure + * \since 1.6.1 */ #define AST_DLLIST_LAST(head) ((head)->last) #define AST_RWDLLIST_LAST AST_DLLIST_LAST +#define AST_DLLIST_NEXT_DIRECTION(elm, field, direction) ((elm)->field.direction) + +#define AST_RWDLLIST_NEXT_DIRECTION AST_DLLIST_NEXT_DIRECTION + /*! - \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. - \since 1.6.1 -*/ -#define AST_DLLIST_NEXT(elm, field) ((elm)->field.next) + * \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. + * \since 1.6.1 + */ +#define AST_DLLIST_NEXT(elm, field) AST_DLLIST_NEXT_DIRECTION(elm, field, first) #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. - \since 1.6.1 -*/ -#define AST_DLLIST_PREV(elm, field) ((elm)->field.prev) + * \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. + * \since 1.6.1 + */ +#define AST_DLLIST_PREV(elm, field) AST_DLLIST_NEXT_DIRECTION(elm, field, last) #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. - \since 1.6.1 + * \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. + * \since 1.6.1 */ #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() - \since 1.6.1 -*/ + * \brief Checks whether the specified list contains the element. + * \param head This is a pointer to the list head structure + * \param elm This is a pointer to the list element to see if in list. + * \param field List node field for the next node information. + * + * \return elm if the list has elm in it. + * \return NULL if not. + * \since 11 + */ +#define AST_DLLIST_IS_MEMBER(head, elm, field) \ + ({ \ + typeof((head)->first) __cur; \ + typeof((elm)) __elm = (elm); \ + if (!__elm) { \ + __cur = NULL; \ + } else { \ + __cur = (head)->first; \ + while (__cur && __cur != __elm) { \ + __cur = __cur->field.first; \ + } \ + } \ + __cur; \ + }) + +#define AST_RWDLLIST_IS_MEMBER AST_DLLIST_IS_MEMBER + +/*! + * \brief Traverse a doublly linked list using the specified direction list. + * + * \param head List head structure pointer. + * \param var This is the name of the variable that will hold a pointer to the + * current list node on each iteration. It must be declared before calling + * this macro. + * \param field List node field for the next node information. (declared using AST_DLLIST_ENTRY()) + * \param start Specified list node to start traversal: first or last + * + * This macro is use to loop over (traverse) the nodes in a list. It uses a + * \a for loop, and supplies the enclosed code with a pointer to each list + * node 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_DIRECTION(&entries, current, list, first) { + * (do something with current here (travers list in forward direction)) + * } + * ... + * AST_DLLIST_TRAVERSE_DIRECTION(&entries, current, list, last) { + * (do something with current here (travers list in reverse direction)) + * } + * \endcode + * + * \since 11 + */ +#define AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, start) \ + for ((var) = (head)->start; (var); (var) = AST_DLLIST_NEXT_DIRECTION(var, field, start)) + +#define AST_RWDLLIST_TRAVERSE_DIRECTION AST_DLLIST_TRAVERSE_DIRECTION + +/*! + * \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() + * \since 1.6.1 + */ #define AST_DLLIST_TRAVERSE(head,var,field) \ - for((var) = (head)->first; (var); (var) = (var)->field.next) + AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, first) #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() - \since 1.6.1 -*/ + * \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() + * \since 1.6.1 + */ #define AST_DLLIST_TRAVERSE_BACKWARDS(head,var,field) \ - for((var) = (head)->last; (var); (var) = (var)->field.prev) + AST_DLLIST_TRAVERSE_DIRECTION(head, var, field, last) #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. - \since 1.6.1 -*/ -#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 Safe traversal of a doublly linked list using the specified direction list. + * + * \param head List head structure pointer. + * \param var This is the name of the variable that will hold a pointer to the + * current list node on each iteration. It must be declared before calling + * this macro. + * \param field List node field for the next node information. (declared using AST_DLLIST_ENTRY()) + * \param start Specified list node to start traversal: first or last + * + * This macro is used to safely loop over (traverse) the nodes in a list. It + * uses a \a for loop, and supplies the enclosed code with a pointer to each list + * node 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_DIRECTION_SAFE_BEGIN(&entries, current, list, first) { + * (do something with current here (travers list in forward direction)) + * } + * ... + * AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(&entries, current, list, last) { + * (do something with current here (travers list in reverse direction)) + * } + * AST_DLLIST_TRAVERSE_DIRECTION_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. + * + * \since 11 + */ +#define AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, start) \ + do { \ + typeof((head)) __list_head = (head); \ + typeof(__list_head->first) __list_current; \ + typeof(__list_head->first) __list_first; \ + typeof(__list_head->first) __list_last; \ + typeof(__list_head->first) __list_next; \ + for ((var) = __list_head->start, \ + __list_current = (var), \ + __list_first = (var) ? (var)->field.first : NULL, \ + __list_last = (var) ? (var)->field.last : NULL, \ + __list_next = (var) ? AST_DLLIST_NEXT_DIRECTION(var, field, start) : NULL; \ + (var); \ + (void) __list_current,/* To quiet compiler? */ \ + (void) __list_first,/* To quiet compiler? */ \ + (void) __list_last,/* To quiet compiler? */ \ + (var) = __list_next, \ + __list_current = (var), \ + __list_first = (var) ? (var)->field.first : NULL, \ + __list_last = (var) ? (var)->field.last : NULL, \ + __list_next = (var) ? AST_DLLIST_NEXT_DIRECTION(var, field, start) : NULL \ + ) + +#define AST_RWDLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN AST_DLLIST_TRAVERSE_DIRECTION_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. - \since 1.6.1 -*/ -#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 \ - ) + * \brief Inserts a list node before the current node 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 nodes of this list together. + * + * \since 1.6.1 + */ +#define AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field) \ + do { \ + typeof((elm)) __elm = (elm); \ + __elm->field.last = __list_last; \ + __elm->field.first = __list_current; \ + if (__list_head->first == __list_current) { \ + __list_head->first = __elm; \ + } else { \ + __list_last->field.first = __elm; \ + } \ + __list_current->field.last = __elm; \ + if (__list_next == __list_last) { \ + __list_next = __elm; \ + } \ + __list_last = __elm; \ + } while (0) -#define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN +#define AST_RWDLLIST_INSERT_BEFORE_CURRENT AST_DLLIST_INSERT_BEFORE_CURRENT /*! - \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). - \since 1.6.1 - */ -#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) + * \brief Inserts a list node after the current node during a traversal. + * \param elm This is a pointer to the node to be inserted. + * \param field This is the name of the field (declared using AST_DLLIST_ENTRY()) + * used to link nodes of this list together. + * + * \since 11 + */ +#define AST_DLLIST_INSERT_AFTER_CURRENT(elm, field) \ + do { \ + typeof((elm)) __elm = (elm); \ + __elm->field.first = __list_first; \ + __elm->field.last = __list_current; \ + if (__list_head->last == __list_current) { \ + __list_head->last = __elm; \ + } else { \ + __list_first->field.last = __elm; \ + } \ + __list_current->field.first = __elm; \ + if (__list_next == __list_first) { \ + __list_next = __elm; \ + } \ + __list_first = __elm; \ + } while (0) + +#define AST_RWDLLIST_INSERT_AFTER_CURRENT AST_DLLIST_INSERT_AFTER_CURRENT + +/*! + * \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). + * \since 1.6.1 + */ +#define AST_DLLIST_REMOVE_CURRENT(field) \ + do { \ + if (__list_first) { \ + __list_first->field.last = __list_last; \ + } else { \ + __list_head->last = __list_last; \ + } \ + if (__list_last) { \ + __list_last->field.first = __list_first; \ + } else { \ + __list_head->first = __list_first; \ + } \ + __list_current->field.first = NULL; \ + __list_current->field.last = NULL; \ + __list_current = NULL; \ + } 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) +/*! + * \brief Move the current list entry to another list at the tail. + * + * \note This is a silly macro. It should be done explicitly + * otherwise the field parameter must be the same for the two + * lists. + * + * AST_DLLIST_REMOVE_CURRENT(field); + * AST_DLLIST_INSERT_TAIL(newhead, var, other_field); + */ +#define AST_DLLIST_MOVE_CURRENT(newhead, field) \ + do { \ + typeof ((newhead)->first) __list_cur = __list_current; \ + 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. - \since 1.6.1 - */ -#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) +/*! + * \brief Move the current list entry to another list at the head. + * + * \note This is a silly macro. It should be done explicitly + * otherwise the field parameter must be the same for the two + * lists. + * + * AST_DLLIST_REMOVE_CURRENT(field); + * AST_DLLIST_INSERT_HEAD(newhead, var, other_field); + */ +#define AST_DLLIST_MOVE_CURRENT_BACKWARDS(newhead, field) \ + do { \ + typeof ((newhead)->first) __list_cur = __list_current; \ + AST_DLLIST_REMOVE_CURRENT(field); \ + AST_DLLIST_INSERT_HEAD((newhead), __list_cur, field); \ + } while (0) -#define AST_RWDLLIST_INSERT_BEFORE_CURRENT AST_DLLIST_INSERT_BEFORE_CURRENT +#define AST_RWDLLIST_MOVE_CURRENT_BACKWARDS AST_DLLIST_MOVE_CURRENT_BACKWARDS + +#define AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END \ + } while (0) + +#define AST_RWDLLIST_TRAVERSE_DIRECTION_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END /*! - \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! - \since 1.6.1 - */ -#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) + * \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. + * \since 1.6.1 + */ +#define AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field) \ + AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, first) + +#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. + * \since 1.6.1 + */ +#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field) \ + AST_DLLIST_TRAVERSE_DIRECTION_SAFE_BEGIN(head, var, field, last) + +#define AST_RWDLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN + +/*! + * \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. + * + * \since 1.6.1 + */ +#define AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field) \ + AST_DLLIST_INSERT_AFTER_CURRENT(elm, field) #define AST_RWDLLIST_INSERT_BEFORE_CURRENT_BACKWARDS AST_DLLIST_INSERT_BEFORE_CURRENT_BACKWARDS /*! - \brief Closes a safe loop traversal block. - \since 1.6.1 + * \brief Closes a safe loop traversal block. + * \since 1.6.1 */ -#define AST_DLLIST_TRAVERSE_SAFE_END } +#define AST_DLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_SAFE_END #define AST_RWDLLIST_TRAVERSE_SAFE_END AST_DLLIST_TRAVERSE_SAFE_END /*! - \brief Closes a safe loop traversal block. - \since 1.6.1 + * \brief Closes a safe loop traversal block. + * \since 1.6.1 */ -#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END } +#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END AST_DLLIST_TRAVERSE_DIRECTION_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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 -*/ -#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. - \since 1.6.1 - */ -#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) + * \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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#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. + * \since 1.6.1 + */ +#define AST_DLLIST_INSERT_AFTER(head, listelm, elm, field) \ + do { \ + typeof((listelm)) __listelm = (listelm); \ + typeof((elm)) __elm = (elm); \ + __elm->field.first = __listelm->field.first; \ + __elm->field.last = __listelm; \ + if ((head)->last == __listelm) { \ + (head)->last = __elm; \ + } else { \ + __listelm->field.first->field.last = __elm; \ + } \ + __listelm->field.first = __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. - \since 1.6.1 - */ -#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) + * \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. + * \since 1.6.1 + */ +#define AST_DLLIST_INSERT_BEFORE(head, listelm, elm, field) \ + do { \ + typeof((listelm)) __listelm = (listelm); \ + typeof((elm)) __elm = (elm); \ + __elm->field.last = __listelm->field.last; \ + __elm->field.first = __listelm; \ + if ((head)->first == __listelm) { \ + (head)->first = __elm; \ + } else { \ + __listelm->field.last->field.first = __elm; \ + } \ + __listelm->field.last = __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. - \since 1.6.1 + * \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. + * \since 1.6.1 */ -#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_DLLIST_INSERT_HEAD(head, elm, field) \ + do { \ + typeof((elm)) __elm = (elm); \ + __elm->field.last = NULL; \ + __elm->field.first = (head)->first; \ + if (!(head)->first) { \ + (head)->last = __elm; \ + } else { \ + (head)->first->field.last = __elm; \ + } \ + (head)->first = __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). - \since 1.6.1 - */ -#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) + * \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). + * \since 1.6.1 + */ +#define AST_DLLIST_INSERT_TAIL(head, elm, field) \ + do { \ + typeof((elm)) __elm = (elm); \ + __elm->field.first = NULL; \ + if (!(head)->first) { \ + __elm->field.last = NULL; \ + (head)->first = __elm; \ + } else { \ + __elm->field.last = (head)->last; \ + (head)->last->field.first = __elm; \ + } \ + (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). - \since 1.6.1 - */ -#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) + * \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). + * \since 1.6.1 + */ +#define AST_DLLIST_APPEND_DLLIST(head, list, field) \ + do { \ + if (!(head)->first) { \ + (head)->first = (list)->first; \ + (head)->last = (list)->last; \ + } else { \ + (head)->last->field.first = (list)->first; \ + (list)->first->field.last = (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. - \since 1.6.1 - */ -#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; \ + * \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. + * \since 1.6.1 + */ +#define AST_DLLIST_REMOVE_HEAD(head, field) \ + ({ \ + typeof((head)->first) cur = (head)->first; \ + if (cur) { \ + (head)->first = cur->field.first; \ + if ((head)->first) { \ + (head)->first->field.last = NULL; \ + } \ + cur->field.first = NULL; \ + cur->field.last = 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. - \since 1.6.1 - */ -#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); \ -}) + * \brief Removes and returns the tail node 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 nodes of this list together. + * + * Removes the tail entry from the list, and returns a pointer to it. + * This macro is safe to call on an empty list. + * \since 11 + */ +#define AST_DLLIST_REMOVE_TAIL(head, field) \ + ({ \ + typeof((head)->last) cur = (head)->last; \ + if (cur) { \ + (head)->last = cur->field.last; \ + if ((head)->last) { \ + (head)->last->field.first = NULL; \ + } \ + cur->field.first = NULL; \ + cur->field.last = NULL; \ + if ((head)->first == cur) { \ + (head)->first = NULL; \ + } \ + } \ + cur; \ + }) + +#define AST_RWDLLIST_REMOVE_TAIL AST_DLLIST_REMOVE_TAIL + +/*! + * \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. + * \since 1.6.1 + */ +#define AST_DLLIST_REMOVE(head, elm, field) \ + do { \ + typeof((elm)) __elm = (elm); \ + if (__elm) { \ + if (__elm->field.first) { \ + __elm->field.first->field.last = __elm->field.last; \ + } else { \ + (head)->last = __elm->field.last; \ + } \ + if (__elm->field.last) { \ + __elm->field.last->field.first = __elm->field.first; \ + } else { \ + (head)->first = __elm->field.first; \ + } \ + __elm->field.first = NULL; \ + __elm->field.last = NULL; \ + } \ + } while (0) #define AST_RWDLLIST_REMOVE AST_DLLIST_REMOVE +/*! + * \brief Removes a specific node from a list if it is in the list. + * \param head This is a pointer to the list head structure + * \param elm This is a pointer to the node to be removed. + * \param field This is the name of the field (declared using AST_DLLIST_ENTRY()) + * used to link nodes of this list together. + * \warning The removed node is \b not freed. + * \return elm if the list had elm in it. + * \return NULL if not. + * \since 11 + */ +#define AST_DLLIST_REMOVE_VERIFY(head, elm, field) \ + ({ \ + typeof((elm)) __res = AST_DLLIST_IS_MEMBER(head, elm, field); \ + AST_DLLIST_REMOVE(head, __res, field); \ + __res; \ + }) + +#define AST_RWDLLIST_REMOVE_VERIFY AST_DLLIST_REMOVE_VERIFY + #endif /* _ASTERISK_DLINKEDLISTS_H */ diff --git a/tests/test_linkedlists.c b/tests/test_linkedlists.c index 2d816945c..6a3b9b2b0 100644 --- a/tests/test_linkedlists.c +++ b/tests/test_linkedlists.c @@ -37,10 +37,12 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$") #include "asterisk/strings.h" #include "asterisk/logger.h" #include "asterisk/linkedlists.h" +#include "asterisk/dlinkedlists.h" struct test_val { const char *name; AST_LIST_ENTRY(test_val) list; + AST_DLLIST_ENTRY(test_val) dbl_list; }; static struct test_val a = { "A" }; @@ -49,6 +51,7 @@ static struct test_val c = { "C" }; static struct test_val d = { "D" }; AST_LIST_HEAD_NOLOCK(test_llist, test_val); +AST_DLLIST_HEAD_NOLOCK(test_dbl_llist, test_val); static int list_expect(struct test_llist *test_list, const char *expect, struct ast_str **buf) { @@ -62,6 +65,43 @@ static int list_expect(struct test_llist *test_list, const char *expect, struct return strcmp(expect, ast_str_buffer(*buf)); } +static int dbl_list_expect_forward(struct test_dbl_llist *test_list, const char *expect, struct ast_str **buf) +{ + struct test_val *i; + + ast_str_reset(*buf); + AST_DLLIST_TRAVERSE(test_list, i, dbl_list) { + ast_str_append(buf, 0, "%s", i->name); + } + + return strcmp(expect, ast_str_buffer(*buf)); +} + +static int dbl_list_expect_reverse(struct test_dbl_llist *test_list, const char *expect, struct ast_str **buf) +{ + struct test_val *i; + char *str; + int len = strlen(expect); + int idx; + + ast_str_reset(*buf); + AST_DLLIST_TRAVERSE_BACKWARDS(test_list, i, dbl_list) { + ast_str_append(buf, 0, "%s", i->name); + } + + /* Check reverse string. */ + str = ast_str_buffer(*buf); + if (len != strlen(str)) { + return 1; + } + for (idx = 0; idx < len; ++idx) { + if (expect[idx] != str[len - idx - 1]) { + return 1; + } + } + return 0; +} + #define MATCH_OR_FAIL(list, val, retbuf) \ if (list_expect(list, val, &retbuf)) { \ ast_test_status_update(test, "Expected: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \ @@ -69,6 +109,18 @@ static int list_expect(struct test_llist *test_list, const char *expect, struct return AST_TEST_FAIL; \ } +#define MATCH_OR_FAIL_DBL(list, val, retbuf) \ + if (dbl_list_expect_forward(list, val, &retbuf)) { \ + ast_test_status_update(test, "Expected: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \ + ast_free(retbuf); \ + return AST_TEST_FAIL; \ + } \ + if (dbl_list_expect_reverse(list, val, &retbuf)) { \ + ast_test_status_update(test, "Expected reverse of: %s, Got: %s\n", val, ast_str_buffer(retbuf)); \ + ast_free(retbuf); \ + return AST_TEST_FAIL; \ + } + #define ELEM_OR_FAIL(x,y) \ if ((x) != (y)) { \ ast_test_status_update(test, "Expected: %s, Got: %s\n", (x)->name, (y)->name); \ @@ -122,14 +174,14 @@ AST_TEST_DEFINE(single_ll_tests) } MATCH_OR_FAIL(&test_list, "", buf); - /* ** */ + /* Check empty list test */ if (!AST_LIST_EMPTY(&test_list)) { ast_test_status_update(test, "List should be empty\n"); return AST_TEST_FAIL; } - /* ** */ + /* Insert tail and remove specific item tests. */ AST_LIST_INSERT_TAIL(&test_list, &a, list); MATCH_OR_FAIL(&test_list, "A", buf); @@ -165,7 +217,7 @@ AST_TEST_DEFINE(single_ll_tests) return AST_TEST_FAIL; } - /* ** */ + /* Insert item after specific item tests */ AST_LIST_INSERT_HEAD(&test_list, &a, list); MATCH_OR_FAIL(&test_list, "A", buf); @@ -190,7 +242,7 @@ AST_TEST_DEFINE(single_ll_tests) return AST_TEST_FAIL; } - /* ** */ + /* Append list test */ AST_LIST_INSERT_HEAD(&test_list, &a, list); MATCH_OR_FAIL(&test_list, "A", buf); @@ -212,7 +264,7 @@ AST_TEST_DEFINE(single_ll_tests) return AST_TEST_FAIL; } - /* ** */ + /* Insert list after specific item in middle test */ AST_LIST_INSERT_HEAD(&test_list, &a, list); MATCH_OR_FAIL(&test_list, "A", buf); @@ -234,7 +286,7 @@ AST_TEST_DEFINE(single_ll_tests) return AST_TEST_FAIL; } - /* ** */ + /* Insert list after specific item on end test */ AST_LIST_INSERT_HEAD(&test_list, &a, list); MATCH_OR_FAIL(&test_list, "A", buf); @@ -256,7 +308,7 @@ AST_TEST_DEFINE(single_ll_tests) return AST_TEST_FAIL; } - /* ** */ + /* Safe traversal list modification tests */ AST_LIST_INSERT_HEAD(&test_list, &a, list); MATCH_OR_FAIL(&test_list, "A", buf); @@ -286,15 +338,330 @@ AST_TEST_DEFINE(single_ll_tests) return AST_TEST_PASS; } +AST_TEST_DEFINE(double_ll_tests) +{ + struct ast_str *buf; + struct test_dbl_llist test_list = { 0, }; + struct test_dbl_llist other_list = { 0, }; + struct test_val *bogus; + + switch (cmd) { + case TEST_INIT: + info->name = "double_ll_tests"; + info->category = "/main/linkedlists"; + info->summary = "double linked list unit test"; + info->description = + "Test the double linked list API"; + return AST_TEST_NOT_RUN; + case TEST_EXECUTE: + break; + } + + if (!(buf = ast_str_create(16))) { + return AST_TEST_FAIL; + } + + if (!(bogus = alloca(sizeof(*bogus)))) { + return AST_TEST_FAIL; + } + + if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) { + ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for missing element from empty list\n"); + return AST_TEST_FAIL; + } + + /* INSERT_HEAD and REMOVE_HEAD tests */ + AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "BA", buf); + AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "", buf); + if (AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list)) { + ast_test_status_update(test, "Somehow removed an item from the head of a list that didn't exist\n"); + return AST_TEST_FAIL; + } + MATCH_OR_FAIL_DBL(&test_list, "", buf); + + /* Check empty list test */ + + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty\n"); + return AST_TEST_FAIL; + } + + /* Insert tail and remove specific item tests. */ + + AST_DLLIST_INSERT_TAIL(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AB", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) { + ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for missing element\n"); + return AST_TEST_FAIL; + } + bogus = NULL; + if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) { + ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL for element set to NULL\n"); + return AST_TEST_FAIL; + } + AST_DLLIST_REMOVE(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + AST_DLLIST_REMOVE(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AC", buf); + AST_DLLIST_REMOVE(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "C", buf); + AST_DLLIST_REMOVE(&test_list, &c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "", buf); + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty\n"); + return AST_TEST_FAIL; + } + if (AST_DLLIST_REMOVE_VERIFY(&test_list, bogus, dbl_list)) { + ast_test_status_update(test, "AST_DLLIST_REMOVE_VERIFY should safely return NULL asked to remove a NULL pointer from an empty list\n"); + return AST_TEST_FAIL; + } + + /* Insert item after and before specific item tests */ + + AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AC", buf); + AST_DLLIST_INSERT_AFTER(&test_list, &a, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + AST_DLLIST_INSERT_AFTER(&test_list, &c, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_TAIL(&test_list, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + AST_DLLIST_REMOVE_TAIL(&test_list, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AB", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_BEFORE(&test_list, &d, &c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_HEAD(&test_list, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "BCD", buf); + AST_DLLIST_INSERT_BEFORE(&test_list, &b, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + + ELEM_OR_FAIL(AST_DLLIST_FIRST(&test_list), &a); + ELEM_OR_FAIL(AST_DLLIST_LAST(&test_list), &d); + ELEM_OR_FAIL(AST_DLLIST_NEXT(&a, dbl_list), &b); + ELEM_OR_FAIL(AST_DLLIST_PREV(&b, dbl_list), &a); + + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + /* Append list test */ + + AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AB", buf); + AST_DLLIST_INSERT_HEAD(&other_list, &c, dbl_list); + MATCH_OR_FAIL_DBL(&other_list, "C", buf); + AST_DLLIST_INSERT_TAIL(&other_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&other_list, "CD", buf); + AST_DLLIST_APPEND_DLLIST(&test_list, &other_list, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + MATCH_OR_FAIL_DBL(&other_list, "", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + /* + * Safe traversal list modification tests + * Traverse starting from first element + */ + + AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AD", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + if (bogus == &d) { + AST_DLLIST_INSERT_BEFORE_CURRENT(&b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_BEFORE_CURRENT(&c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_CURRENT(dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + } + } + AST_DLLIST_TRAVERSE_SAFE_END; + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "B", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "BD", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + if (bogus == &b) { + AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_CURRENT(dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + } + } + AST_DLLIST_TRAVERSE_SAFE_END; + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "B", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + if (bogus == &b) { + AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AB", buf); + AST_DLLIST_INSERT_AFTER_CURRENT(&d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_CURRENT(dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + } + } + AST_DLLIST_TRAVERSE_SAFE_END; + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + /* + * Safe traversal list modification tests + * Traverse starting from last element + */ + + AST_DLLIST_INSERT_HEAD(&test_list, &a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "A", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AD", buf); + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) { + if (bogus == &d) { + AST_DLLIST_INSERT_BEFORE_CURRENT(&b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_BEFORE_CURRENT(&c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_CURRENT(dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + } + } + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END; + MATCH_OR_FAIL_DBL(&test_list, "ABC", buf); + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "B", buf); + AST_DLLIST_INSERT_TAIL(&test_list, &d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "BD", buf); + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) { + if (bogus == &b) { + AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_CURRENT(dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + } + } + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END; + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + AST_DLLIST_INSERT_HEAD(&test_list, &b, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "B", buf); + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&test_list, bogus, dbl_list) { + if (bogus == &b) { + AST_DLLIST_INSERT_BEFORE_CURRENT(&a, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "AB", buf); + AST_DLLIST_INSERT_AFTER_CURRENT(&d, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABD", buf); + AST_DLLIST_INSERT_AFTER_CURRENT(&c, dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ABCD", buf); + AST_DLLIST_REMOVE_CURRENT(dbl_list); + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + } + } + AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END; + MATCH_OR_FAIL_DBL(&test_list, "ACD", buf); + AST_DLLIST_TRAVERSE_SAFE_BEGIN(&test_list, bogus, dbl_list) { + AST_DLLIST_REMOVE_CURRENT(dbl_list); + } + AST_DLLIST_TRAVERSE_SAFE_END; + if (!AST_DLLIST_EMPTY(&test_list)) { + ast_test_status_update(test, "List should be empty after traversing and removal. It wasn't.\n"); + return AST_TEST_FAIL; + } + + return AST_TEST_PASS; +} + static int unload_module(void) { AST_TEST_UNREGISTER(single_ll_tests); + AST_TEST_UNREGISTER(double_ll_tests); return 0; } static int load_module(void) { AST_TEST_REGISTER(single_ll_tests); + AST_TEST_REGISTER(double_ll_tests); return AST_MODULE_LOAD_SUCCESS; } |