[PATCH wayland v3 1/2] util: Document wl_list methods
Pekka Paalanen
ppaalanen at gmail.com
Mon Sep 5 12:09:38 UTC 2016
On Sun, 4 Sep 2016 13:23:04 -0700
Yong Bakos <junk at humanoriented.com> wrote:
> From: Yong Bakos <ybakos at humanoriented.com>
>
> Add doxygen comment blocks to all wl_list methods.
>
> Signed-off-by: Yong Bakos <ybakos at humanoriented.com>
> ---
> v3: Standardize on term 'element', to match param names, tests, and other text.
> Use 'relates' for macros (instead of 'memberof').
> v2: Refine the writing for clarity.
> Add dox for wl_list macros, omitted in v1.
> Add notices for unsafe operations and invalid states (giucam, pq)
>
>
> src/wayland-util.h | 220 +++++++++++++++++++++++++++++++++++++++++++----------
> 1 file changed, 180 insertions(+), 40 deletions(-)
>
> diff --git a/src/wayland-util.h b/src/wayland-util.h
> index cacc122..7705c66 100644
> --- a/src/wayland-util.h
> +++ b/src/wayland-util.h
> @@ -78,115 +78,232 @@ struct wl_interface {
>
> /** \class wl_list
> *
> - * \brief doubly-linked list
> + * \brief Circular 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 circular, 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. 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.
> + *
> + * 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 <em>[e2, e3, e1]</em>.
> + *
> + * 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 *element;
This should be 'e', not 'element'.
> + * 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 where its `prev` and
> + * `next` point to `NULL`.
No, do not say NULL. We do not guarantee that even if the code does it.
It's just that leaving the pointers dangling as we originally did made
bugs ever harder to catch.
If we actually document it to be NULL, then someone might have the
funny idea to start comparing prev/next to NULL and we don't want that.
Should perhaps use some non-zero poison value, maybe. Anyway, just say
they are invalid or undefined.
> + *
> + * \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 itself 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.
> *
> + * \note If this 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 of your own.
> + *
Huh?
Does that differ from "Found a bug? Report it or send a patch."?
Hm, I see you lifted it from a regular code comment. Maybe it should
stay there.
> * To demonstrate, the following example retrieves a pointer to
> * `example_container` given only its `destroy_listener` member:
> *
> * \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...
These are strange cases of mixing up tabs and spaces. Are you sure
you intended this?
> * }
> * \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 *messages;
By convention, call it message_list.
We should have the convention to name every list head as
"something_list", likewise members are "link" or "something_link".
> + * // Assume messages now "contains" many messages
> + *
> + * struct message *m;
> + * wl_list_for_each(m, messages, link) {
> + * do_something_with_message(m);
Again a mixup of tabs and spaces.
> + * }
> + * \endcode
> + *
> + * \param pos Cursor that each list element will be assigned to
> + * \param head Head of the list to enumerate
s/enumerate/iterate/
> + * \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.
> + *
Might want to emphasize that only removal of the current element is
allowed. Removing any other element may cause the loop to malfunction.
It's actually a pretty annoying trap that iterating over a list,
removing something and updating some related state elsewhere might
cause another item to be removed from the same list. This is always a
bug. The chances of actually triggering the bug are not high because
you'd have to remove exactly the element next to current one to cause
problems. Then, the problem is not guaranteed crash or even a hang
either.
> + * \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 enumerate
> + * \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 +311,34 @@ 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 enumerate
> + * \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.
> + *
> + * \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 enumerate
> + * \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); \
> --
Very good, just those minor details to fix and I'd be happy to land it
with my R-b.
Btw. once upon a time, I wrote the attached patch. I never bothered to
polish it for upstream. I'm not even sure how to expose it. Having to
rebuild libwayland is awkward, but we also do not want to enable it
always. I wonder what others would think of it. Maybe you'd like to
find out? Maybe the max plausible list length should be configurable?
Env var?
Thanks,
pq
-------------- next part --------------
A non-text attachment was scrubbed...
Name: commit-1fbfff0
Type: application/octet-stream
Size: 2366 bytes
Desc: not available
URL: <https://lists.freedesktop.org/archives/wayland-devel/attachments/20160905/a561ed5c/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 811 bytes
Desc: OpenPGP digital signature
URL: <https://lists.freedesktop.org/archives/wayland-devel/attachments/20160905/a561ed5c/attachment.sig>
More information about the wayland-devel
mailing list