From f7e1dcc20bc873cae0ea532f094cbe417626519f Mon Sep 17 00:00:00 2001 From: Yong Bakos Date: Thu, 22 Sep 2016 21:59:37 -0500 Subject: [PATCH] util: Document wl_list methods Add doxygen comment blocks to all wl_list methods. Signed-off-by: Yong Bakos Reviewed-by: Bryce Harrington [Pekka: removed "itself" as suggested by Bryce] Reviewed-by: Pekka Paalanen --- src/wayland-util.h | 224 +++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 184 insertions(+), 40 deletions(-) diff --git a/src/wayland-util.h b/src/wayland-util.h index cacc122..a404390 100644 --- a/src/wayland-util.h +++ b/src/wayland-util.h @@ -78,73 +78,150 @@ struct wl_interface { /** \class wl_list * - * \brief doubly-linked list + * \brief Doubly-linked list * - * The list head is of "struct wl_list" type, and must be initialized - * using wl_list_init(). All entries in the list must be of the same - * type. The item type must have a "struct wl_list" member. This - * member will be initialized by wl_list_insert(). There is no need to - * call wl_list_init() on the individual item. To query if the list is - * empty in O(1), use wl_list_empty(). + * On its own, an instance of `struct wl_list` represents the sentinel head of + * a doubly-linked list, and must be initialized using wl_list_init(). + * When empty, the list head's `next` and `prev` members point to the list head + * itself, otherwise `next` references the first element in the list, and `prev` + * refers to the last element in the list. * - * Let's call the list reference "struct wl_list foo_list", the item type as - * "item_t", and the item member as "struct wl_list link". + * Use the `struct wl_list` type to represent both the list head and the links + * between elements within the list. Use wl_list_empty() to determine if the + * list is empty in O(1). + * + * All elements in the list must be of the same type. The element type must have + * a `struct wl_list` member, often named `link` by convention. Prior to + * insertion, there is no need to initialize an element's `link` - invoking + * wl_list_init() on an individual list element's `struct wl_list` member is + * unnecessary if the very next operation is wl_list_insert(). However, a + * common idiom is to initialize an element's `link` prior to removal - ensure + * safety by invoking wl_list_init() before wl_list_remove(). + * + * Consider a list reference `struct wl_list foo_list`, an element type as + * `struct element`, and an element's link member as `struct wl_list link`. + * + * The following code initializes a list and adds three elements to it. * - * The following code will initialize a list: * \code * struct wl_list foo_list; * - * struct item_t { - * int foo; - * struct wl_list link; + * struct element { + * int foo; + * struct wl_list link; * }; - * struct item_t item1, item2, item3; + * struct element e1, e2, e3; * * wl_list_init(&foo_list); - * wl_list_insert(&foo_list, &item1.link); // Pushes item1 at the head - * wl_list_insert(&foo_list, &item2.link); // Pushes item2 at the head - * wl_list_insert(&item2.link, &item3.link); // Pushes item3 after item2 + * wl_list_insert(&foo_list, &e1.link); // e1 is the first element + * wl_list_insert(&foo_list, &e2.link); // e2 is now the first element + * wl_list_insert(&e2.link, &e3.link); // insert e3 after e2 * \endcode * - * The list now looks like [item2, item3, item1] + * The list now looks like [e2, e3, e1]. + * + * The `wl_list` API provides some iterator macros. For example, to iterate + * a list in ascending order: * - * Iterate the list in ascending order: * \code - * item_t *item; - * wl_list_for_each(item, foo_list, link) { - * Do_something_with_item(item); + * struct element *e; + * wl_list_for_each(e, foo_list, link) { + * do_something_with_element(e); * } * \endcode + * + * See the documentation of each iterator for details. + * \sa http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h */ struct wl_list { struct wl_list *prev; struct wl_list *next; }; +/** + * Initializes the list. + * + * \param list List to initialize + * + * \memberof wl_list + */ void wl_list_init(struct wl_list *list); +/** + * Inserts an element into the list, after the element represented by \p list. + * When \p list is a reference to the list itself (the head), set the containing + * struct of \p elm as the first element in the list. + * + * \note If \p elm is already part of a list, inserting it again will lead to + * list corruption. + * + * \param list List element after which the new element is inserted + * \param elm Link of the containing struct to insert into the list + * + * \memberof wl_list + */ void wl_list_insert(struct wl_list *list, struct wl_list *elm); +/** + * Removes an element from the list. + * + * \note This operation leaves \p elm in an invalid state. + * + * \param elm Link of the containing struct to remove from the list + * + * \memberof wl_list + */ void wl_list_remove(struct wl_list *elm); +/** + * Determines the length of the list. + * + * \note This is an O(n) operation. + * + * \param list List whose length is to be determined + * + * \return Number of elements in the list + * + * \memberof wl_list + */ int wl_list_length(const struct wl_list *list); +/** + * Determines if the list is empty. + * + * \param list List whose emptiness is to be determined + * + * \return 1 if empty, or 0 if not empty + * + * \memberof wl_list + */ int wl_list_empty(const struct wl_list *list); +/** + * Inserts all of the elements of one list into another, after the element + * represented by \p list. + * + * \note This leaves \p other in an invalid state. + * + * \param list List element after which the other list elements will be inserted + * \param other List of elements to insert + * + * \memberof wl_list + */ void wl_list_insert_list(struct wl_list *list, struct wl_list *other); /** - * Retrieves a pointer to the containing struct of a given member item. + * Retrieves a pointer to a containing struct, given a member name. * - * This macro allows conversion from a pointer to a item to its containing + * This macro allows "conversion" from a pointer to a member to its containing * struct. This is useful if you have a contained item like a wl_list, - * wl_listener, or wl_signal, provided via a callback or other means and would + * wl_listener, or wl_signal, provided via a callback or other means, and would * like to retrieve the struct that contains it. * * To demonstrate, the following example retrieves a pointer to @@ -152,41 +229,82 @@ wl_list_insert_list(struct wl_list *list, struct wl_list *other); * * \code * struct example_container { - * struct wl_listener destroy_listener; - * // other members... + * struct wl_listener destroy_listener; + * // other members... * }; * * void example_container_destroy(struct wl_listener *listener, void *data) * { - * struct example_container *ctr; + * struct example_container *ctr; * - * ctr = wl_container_of(listener, ctr, destroy_listener); - * // destroy ctr... + * ctr = wl_container_of(listener, ctr, destroy_listener); + * // destroy ctr... * } * \endcode * - * \param ptr A valid pointer to the contained item. + * \note `sample` need not be a valid pointer. A null or uninitialised pointer + * is sufficient. * - * \param sample A pointer to the type of content that the list item - * stores. Sample does not need be a valid pointer; a null or - * an uninitialised pointer will suffice. + * \param ptr Valid pointer to the contained member + * \param sample Pointer to a struct whose type contains \p ptr + * \param member Named location of \p ptr within the \p sample type * - * \param member The named location of ptr within the sample type. - * - * \return The container for the specified pointer. + * \return The container for the specified pointer */ #define wl_container_of(ptr, sample, member) \ (__typeof__(sample))((char *)(ptr) - \ offsetof(__typeof__(*sample), member)) -/* If the above macro causes problems on your compiler you might be - * able to find an alternative name for the non-standard __typeof__ - * operator and add a special case here */ +/** + * Iterates over a list. + * + * This macro expresses a for-each iterator for wl_list. Given a list and + * wl_list link member name (often named `link` by convention), this macro + * assigns each element in the list to \p pos, which can then be referenced in + * a trailing code block. For example, given a wl_list of `struct message` + * elements: + * + * \code + * struct message { + * char *contents; + * wl_list link; + * }; + * + * struct wl_list *message_list; + * // Assume message_list now "contains" many messages + * + * struct message *m; + * wl_list_for_each(m, message_list, link) { + * do_something_with_message(m); + * } + * \endcode + * + * \param pos Cursor that each list element will be assigned to + * \param head Head of the list to iterate over + * \param member Name of the link member within the element struct + * + * \relates wl_list + */ #define wl_list_for_each(pos, head, member) \ for (pos = wl_container_of((head)->next, pos, member); \ &pos->member != (head); \ pos = wl_container_of(pos->member.next, pos, member)) +/** + * Iterates over a list, safe against removal of the list element. + * + * \note Only removal of the current element, \p pos, is safe. Removing + * any other element during traversal may lead to a loop malfunction. + * + * \sa wl_list_for_each() + * + * \param pos Cursor that each list element will be assigned to + * \param tmp Temporary pointer of the same type as \p pos + * \param head Head of the list to iterate over + * \param member Name of the link member within the element struct + * + * \relates wl_list + */ #define wl_list_for_each_safe(pos, tmp, head, member) \ for (pos = wl_container_of((head)->next, pos, member), \ tmp = wl_container_of((pos)->member.next, tmp, member); \ @@ -194,11 +312,37 @@ wl_list_insert_list(struct wl_list *list, struct wl_list *other); pos = tmp, \ tmp = wl_container_of(pos->member.next, tmp, member)) +/** + * Iterates backwards over a list. + * + * \sa wl_list_for_each() + * + * \param pos Cursor that each list element will be assigned to + * \param head Head of the list to iterate over + * \param member Name of the link member within the element struct + * + * \relates wl_list + */ #define wl_list_for_each_reverse(pos, head, member) \ for (pos = wl_container_of((head)->prev, pos, member); \ &pos->member != (head); \ pos = wl_container_of(pos->member.prev, pos, member)) +/** + * Iterates backwards over a list, safe against removal of the list element. + * + * \note Only removal of the current element, \p pos, is safe. Removing + * any other element during traversal may lead to a loop malfunction. + * + * \sa wl_list_for_each() + * + * \param pos Cursor that each list element will be assigned to + * \param tmp Temporary pointer of the same type as \p pos + * \param head Head of the list to iterate over + * \param member Name of the link member within the element struct + * + * \relates wl_list + */ #define wl_list_for_each_reverse_safe(pos, tmp, head, member) \ for (pos = wl_container_of((head)->prev, pos, member), \ tmp = wl_container_of((pos)->member.prev, tmp, member); \ -- 2.7.4