From c3777b877b2ed46e3e29a000b14fa1b5d7e97af9 Mon Sep 17 00:00:00 2001 From: Richard Qin Date: Mon, 28 Sep 2026 01:03:56 +0800 Subject: Standardized list.h comments --- lab02/list.h | 234 +++++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 196 insertions(+), 38 deletions(-) diff --git a/lab02/list.h b/lab02/list.h index f04df43..7d4ca23 100644 --- a/lab02/list.h +++ b/lab02/list.h @@ -1,4 +1,13 @@ /* SPDX-License-Identifier: GPL-2.0 */ + +/** + * @file list.h + * @brief Intrusive circular doubly linked list primitives. + * + * A list node is embedded in the structure that owns it. The list head is + * represented by a sentinel `struct list_head` whose links point to itself + * when the list is empty. + */ #ifndef LIST_H #define LIST_H @@ -8,25 +17,57 @@ #include "container_of.h" +/** + * @brief A node in an intrusive circular doubly linked list. + */ struct list_head { struct list_head *next; struct list_head *prev; }; +/** @brief Poison value written to a deleted node's `next` link. */ #define LIST_POISON1 ((void *) 0x100) + +/** @brief Poison value written to a deleted node's `prev` link. */ #define LIST_POISON2 ((void *) 0x122) +/** + * @brief Circular doubly linked list implementation. + * + * Some internal functions are useful when manipulating whole lists because + * the neighboring nodes are already known. + */ + +/** @brief Initializes a list head initializer. */ #define LIST_HEAD_INIT(name) { &(name), &(name) } +/** + * @brief Declares and initializes an empty list head. + * @param name The list head variable name. + */ #define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name) +/** + * @brief Initializes a list node or list head. + * + * The node is made self-linked. When used as a list head, this represents + * an empty list. + * + * @param list The node or list head to initialize. + * @post `list->next == list`. + * @post `list->prev == list`. + */ static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; } +/** + * @internal + * @brief Links a node between two known adjacent nodes. + */ static inline void __list_add(struct list_head *node, struct list_head *prev, struct list_head *next) @@ -37,18 +78,41 @@ static inline void __list_add(struct list_head *node, prev->next = node; } +/** + * @brief Inserts a node immediately after a list node. + * + * This operation is suitable for stack-like insertion. + * + * @param node The node to insert. + * @param head The node after which `node` is inserted. + * @pre `node` is not currently linked into a list. + */ static inline void list_add(struct list_head *node, struct list_head *head) { __list_add(node, head, head->next); } +/** + * @brief Inserts a node immediately before a list node. + * + * This operation is suitable for queue-like insertion when `head` is the + * list sentinel. + * + * @param node The node to insert. + * @param head The node before which `node` is inserted. + * @pre `node` is not currently linked into a list. + */ static inline void list_add_tail(struct list_head *node, struct list_head *head) { __list_add(node, head->prev, head); } +/** + * @internal + * @brief Unlinks the range between two known adjacent nodes. + */ static inline void __list_del(struct list_head *prev, struct list_head *next) { @@ -56,11 +120,24 @@ static inline void __list_del(struct list_head *prev, prev->next = next; } +/** + * @internal + * @brief Unlinks a node using its stored neighboring links. + */ static inline void __list_del_entry(struct list_head *entry) { __list_del(entry->prev, entry->next); } +/** + * @brief Removes a node from its list. + * + * After this operation, the node's links contain poison values and must not + * be used for list traversal. + * + * @param entry The node to remove. + * @pre `entry` belongs to a valid list. + */ static inline void list_del(struct list_head *entry) { __list_del_entry(entry); @@ -68,7 +145,16 @@ static inline void list_del(struct list_head *entry) entry->prev = LIST_POISON2; } - +/** + * @brief Replaces one list node with another. + * + * The replacement node takes the position of the old node. + * + * @param old The node to replace. + * @param new The replacement node. + * @pre `old` belongs to a valid list. + * @pre `new` is not currently linked into a list. + */ static inline void list_replace(struct list_head *old, struct list_head *new) { @@ -78,6 +164,15 @@ static inline void list_replace(struct list_head *old, new->prev->next = new; } +/** + * @brief Replaces one node and reinitializes the old node. + * + * @param old The node to replace. + * @param new The replacement node. + * @pre `old` belongs to a valid list. + * @pre `new` is not currently linked into a list. + * @post `old` is a self-linked standalone node. + */ static inline void list_replace_init(struct list_head *old, struct list_head *new) { @@ -85,12 +180,26 @@ static inline void list_replace_init(struct list_head *old, INIT_LIST_HEAD(old); } +/** + * @brief Removes a node from its list and inserts it after `head`. + * + * @param list The node to move. + * @param head The node that precedes the moved node. + * @pre `list` belongs to a valid list. + */ static inline void list_move(struct list_head *list, struct list_head *head) { __list_del_entry(list); list_add(list, head); } +/** + * @brief Removes a node from its list and inserts it before `head`. + * + * @param list The node to move. + * @param head The node that follows the moved node. + * @pre `list` belongs to a valid list. + */ static inline void list_move_tail(struct list_head *list, struct list_head *head) { @@ -98,87 +207,131 @@ static inline void list_move_tail(struct list_head *list, list_add_tail(list, head); } +/** + * @brief Tests whether a node is the first entry in a list. + * + * @param list The node to test. + * @param head The list head. + * @return Nonzero if `list` is the first entry; zero otherwise. + */ static inline int list_is_first(const struct list_head *list, const struct list_head *head) { return list->prev == head; } +/** + * @brief Tests whether a node is the last entry in a list. + * + * @param list The node to test. + * @param head The list head. + * @return Nonzero if `list` is the last entry; zero otherwise. + */ static inline int list_is_last(const struct list_head *list, const struct list_head *head) { return list->next == head; } +/** + * @brief Tests whether a node is the list head. + * + * @param list The node to test. + * @param head The list head. + * @return Nonzero if `list == head`; zero otherwise. + */ static inline int list_is_head(const struct list_head *list, const struct list_head *head) { return list == head; } +/** + * @brief Tests whether a list is empty. + * + * @param head The list head. + * @return Nonzero if the list contains no entries; zero otherwise. + */ static inline int list_empty(const struct list_head *head) { return head->next == head; } /** - * list_entry - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. + * @brief Returns the containing structure for a list node. + * + * @param ptr A pointer to the embedded `struct list_head`. + * @param type The containing structure type. + * @param member The embedded list member. + * @return A pointer to the containing structure. */ #define list_entry(ptr, type, member) \ container_of(ptr, type, member) /** - * list_first_entry - get the first element from a list - * @ptr: the list head to take the element from. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. + * @brief Returns the first containing structure in a list. * - * Note, that list is expected to be not empty. + * @param ptr The list head. + * @param type The containing structure type. + * @param member The embedded list member. + * @pre The list is not empty. */ #define list_first_entry(ptr, type, member) \ list_entry((ptr)->next, type, member) /** - * list_last_entry - get the last element from a list - * @ptr: the list head to take the element from. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_head within the struct. + * @brief Returns the last containing structure in a list. * - * Note, that list is expected to be not empty. + * @param ptr The list head. + * @param type The containing structure type. + * @param member The embedded list member. + * @pre The list is not empty. */ #define list_last_entry(ptr, type, member) \ list_entry((ptr)->prev, type, member) /** - * list_next_entry - get the next element in list - * @pos: the type * to cursor - * @member: the name of the list_head within the struct. + * @brief Returns the containing structure following the current node. + * + * @param pos The typed cursor. + * @param member The embedded list member. + * @return The next containing structure. */ #define list_next_entry(pos, member) \ list_entry((pos)->member.next, typeof(*(pos)), member) /** - * list_prev_entry - get the prev element in list - * @pos: the type * to cursor - * @member: the name of the list_head within the struct. + * @brief Returns the containing structure preceding the current node. + * + * @param pos The typed cursor. + * @param member The embedded list member. + * @return The previous containing structure. */ #define list_prev_entry(pos, member) \ list_entry((pos)->member.prev, typeof(*(pos)), member) /** - * list_entry_is_head - test if the entry points to the head of the list - * @pos: the type * to cursor - * @head: the head for your list. - * @member: the name of the list_head within the struct. + * @brief Tests whether a typed cursor refers to the list head. + * + * @param pos The typed cursor. + * @param head The list head. + * @param member The embedded list member. + * @return Nonzero if `pos` refers to `head`; zero otherwise. */ #define list_entry_is_head(pos, head, member) \ (&pos->member == (head)) /** - * list_for_each_entry - iterate over list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_head within the struct. + * @brief Iterates over containing structures in forward order. + * + * Example: + * @code + * struct item *pos; + * list_for_each_entry(pos, &head, link) { + * use_item(pos); + * } + * @endcode + * + * @param pos The typed loop cursor. + * @param head The list head. + * @param member The embedded list member. */ #define list_for_each_entry(pos, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member); \ @@ -186,10 +339,11 @@ static inline int list_empty(const struct list_head *head) pos = list_next_entry(pos, member)) /** - * list_for_each_entry_reverse - iterate backwards over list of given type. - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_head within the struct. + * @brief Iterates over containing structures in reverse order. + * + * @param pos The typed loop cursor. + * @param head The list head. + * @param member The embedded list member. */ #define list_for_each_entry_reverse(pos, head, member) \ for (pos = list_last_entry(head, typeof(*pos), member); \ @@ -197,11 +351,15 @@ static inline int list_empty(const struct list_head *head) pos = list_prev_entry(pos, member)) /** - * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_head within the struct. + * @brief Iterates over containing structures while allowing removal. + * + * The additional cursor stores the next entry before the loop body runs, so + * the current entry may be removed safely from the list. + * + * @param pos The typed loop cursor. + * @param n The temporary typed cursor. + * @param head The list head. + * @param member The embedded list member. */ #define list_for_each_entry_safe(pos, n, head, member) \ for (pos = list_first_entry(head, typeof(*pos), member), \ -- cgit v1.2.3