From 777808a9f51063dc31abcef54f49e6a327efcfb8 Mon Sep 17 00:00:00 2001 From: Andres Freund Date: Wed, 19 Feb 2020 12:06:08 -0800 Subject: [PATCH v1 1/6] Add additional prev/next & detached node functions to ilist. --- src/include/lib/ilist.h | 132 +++++++++++++++++++++++++++++++++------- src/backend/lib/ilist.c | 8 +-- 2 files changed, 113 insertions(+), 27 deletions(-) diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h index 98db885f6ff..1ad9ceb033f 100644 --- a/src/include/lib/ilist.h +++ b/src/include/lib/ilist.h @@ -255,8 +255,8 @@ typedef struct slist_mutable_iter extern void slist_delete(slist_head *head, slist_node *node); #ifdef ILIST_DEBUG -extern void dlist_check(dlist_head *head); -extern void slist_check(slist_head *head); +extern void dlist_check(const dlist_head *head); +extern void slist_check(const slist_head *head); #else /* * These seemingly useless casts to void are here to keep the compiler quiet @@ -270,6 +270,11 @@ extern void slist_check(slist_head *head); /* doubly linked list implementation */ +/* prototypes dlist helpers */ +static inline void *dlist_element_off(dlist_node *node, size_t off); +static inline void *dlist_head_element_off(dlist_head *head, size_t off); +static inline void *dlist_tail_element_off(dlist_head *head, size_t off); + /* * Initialize a doubly linked list. * Previous state will be thrown away without any cleanup. @@ -280,13 +285,24 @@ dlist_init(dlist_head *head) head->head.next = head->head.prev = &head->head; } +/* + * Initialize a doubly linked element. + * + * This is only needed when dlist_node_is_detached() may be needed. + */ +static inline void +dlist_node_init(dlist_node *node) +{ + node->next = node->prev = NULL; +} + /* * Is the list empty? * * An empty list has either its first 'next' pointer set to NULL, or to itself. */ static inline bool -dlist_is_empty(dlist_head *head) +dlist_is_empty(const dlist_head *head) { dlist_check(head); @@ -361,6 +377,20 @@ dlist_delete(dlist_node *node) node->next->prev = node->prev; } + +/* + * Like dlist_delete(), but also sets next/prev to NULL to signal not being in + * list. + */ +static inline void +dlist_delete_thoroughly(dlist_node *node) +{ + node->prev->next = node->next; + node->next->prev = node->prev; + node->next = NULL; + node->prev = NULL; +} + /* * Remove and return the first node from a list (there must be one). */ @@ -399,7 +429,7 @@ dlist_move_head(dlist_head *head, dlist_node *node) * Caution: unreliable if 'node' is not in the list. */ static inline bool -dlist_has_next(dlist_head *head, dlist_node *node) +dlist_has_next(const dlist_head *head, const dlist_node *node) { return node->next != &head->head; } @@ -409,11 +439,25 @@ dlist_has_next(dlist_head *head, dlist_node *node) * Caution: unreliable if 'node' is not in the list. */ static inline bool -dlist_has_prev(dlist_head *head, dlist_node *node) +dlist_has_prev(const dlist_head *head, const dlist_node *node) { return node->prev != &head->head; } +/* + * Check if node is detached. A node is only detached if it either has been + * initialized with dlist_init_node(), or deleted with + * dlist_delete_thoroughly(). + */ +static inline bool +dlist_node_is_detached(const dlist_node *node) +{ + Assert((node->next == NULL && node->prev == NULL) || + (node->next != NULL && node->prev != NULL)); + + return node->next == NULL; +} + /* * Return the next node in the list (there must be one). */ @@ -434,14 +478,6 @@ dlist_prev_node(dlist_head *head, dlist_node *node) return node->prev; } -/* internal support function to get address of head element's struct */ -static inline void * -dlist_head_element_off(dlist_head *head, size_t off) -{ - Assert(!dlist_is_empty(head)); - return (char *) head->head.next - off; -} - /* * Return the first node in the list (there must be one). */ @@ -451,14 +487,6 @@ dlist_head_node(dlist_head *head) return (dlist_node *) dlist_head_element_off(head, 0); } -/* internal support function to get address of tail element's struct */ -static inline void * -dlist_tail_element_off(dlist_head *head, size_t off) -{ - Assert(!dlist_is_empty(head)); - return (char *) head->head.prev - off; -} - /* * Return the last node in the list (there must be one). */ @@ -497,6 +525,24 @@ dlist_tail_node(dlist_head *head) (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ ((type *) dlist_tail_element_off(lhead, offsetof(type, membername)))) +/* + * Return the address of the previous element in the list. + * + * The node must have a previous node. + */ +#define dlist_prev_element(type, membername, node) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + ((type *) dlist_prev_element_off(node, offsetof(type, membername)))) + +/* + * Return the address of the next element in the list. + * + * The node must have a next node. + */ +#define dlist_next_element(type, membername, node) \ + (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \ + ((type *) dlist_next_element_off(node, offsetof(type, membername)))) + /* * Iterate through the list pointed at by 'lhead' storing the state in 'iter'. * @@ -543,6 +589,46 @@ dlist_tail_node(dlist_head *head) (iter).cur != (iter).end; \ (iter).cur = (iter).cur->prev) +/* internal support function to get address of element's struct */ +static inline void * +dlist_element_off(dlist_node *node, size_t off) +{ + return (char *) node - off; +} + +/* internal support function to get address of head element's struct */ +static inline void * +dlist_head_element_off(dlist_head *head, size_t off) +{ + Assert(!dlist_is_empty(head)); + return dlist_element_off(head->head.next, off); +} + +/* internal support function to get address of tail element's struct */ +static inline void * +dlist_tail_element_off(dlist_head *head, size_t off) +{ + Assert(!dlist_is_empty(head)); + return dlist_element_off(head->head.next, off); +} + +/* internal support function to get address of prev element's struct */ +static inline void * +dlist_prev_element_off(dlist_node *node, size_t off) +{ + Assert(!dlist_node_is_detached(node) && + dlist_node_is_detached(node->prev)); + return dlist_element_off(node->prev, off); +} + +/* internal support function to get address of next element's struct */ +static inline void * +dlist_next_element_off(dlist_node *node, size_t off) +{ + Assert(!dlist_node_is_detached(node) && + dlist_node_is_detached(node->next)); + return dlist_element_off(node->next, off); +} /* singly linked list implementation */ @@ -560,7 +646,7 @@ slist_init(slist_head *head) * Is the list empty? */ static inline bool -slist_is_empty(slist_head *head) +slist_is_empty(const slist_head *head) { slist_check(head); @@ -608,7 +694,7 @@ slist_pop_head_node(slist_head *head) * Check whether 'node' has a following node. */ static inline bool -slist_has_next(slist_head *head, slist_node *node) +slist_has_next(const slist_head *head, const slist_node *node) { slist_check(head); diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c index 9b02d546076..82752ab1a39 100644 --- a/src/backend/lib/ilist.c +++ b/src/backend/lib/ilist.c @@ -56,9 +56,9 @@ slist_delete(slist_head *head, slist_node *node) * Verify integrity of a doubly linked list */ void -dlist_check(dlist_head *head) +dlist_check(const dlist_head *head) { - dlist_node *cur; + const dlist_node *cur; if (head == NULL) elog(ERROR, "doubly linked list head address is NULL"); @@ -93,9 +93,9 @@ dlist_check(dlist_head *head) * Verify integrity of a singly linked list */ void -slist_check(slist_head *head) +slist_check(const slist_head *head) { - slist_node *cur; + const slist_node *cur; if (head == NULL) elog(ERROR, "singly linked list head address is NULL"); -- 2.25.0.114.g5b0ca878e0