agora inbox for [email protected]
help / color / mirror / Atom feedFrom: Andres Freund <[email protected]>
Subject: [PATCH v1 1/6] Add additional prev/next & detached node functions to ilist.
Date: Wed, 19 Feb 2020 12:06:08 -0800
---
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
--jukqbc7dv5ymsafw
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
filename="v1-0002-Use-dlists-instead-of-SHM_QUEUE-for-heavyweight-l.patch"
view thread (2+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH v1 1/6] Add additional prev/next & detached node functions to ilist.
In-Reply-To: <no-message-id-188845@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox