Hi,
To recapitulate why I think this sort of embedded list is worthwile:
* minimal memory overhead (16 bytes for double linked list heads/nodes on
64bit systems)
* no additional memory allocation overhead
* no additional dereference to access the contents of a list element
* most modifications are completely branchless
* the current dllist.h interface has double the memory overhead and much more
complex manipulation operators
* Multiple places in postgres have grown local single or double linked list
implementations
* I need it ;)
Attached are three patches:
1. embedded list implementation
2. make the list implementation usable without USE_INLINE
3. convert all callers to ilist.h away from dllist.h
For 1 I:
a. added more comments and some introduction, some more functions
b. moved the file from utils/ilist.h to lib/ilist.h
c. actually included the c file with the check functions
d. did *not* split it up into single/double linked list files, doesn't seem to
be worth the trouble given how small ilist.(c|h) are
e. did *not* try to get an interface similar to dllist.h. I don't think the
old one is better and it makes the breakage more obvious should somebody else
use the old implementation although I doubt it.
I can be convinced to do d. and e. but I don't think they are an improvement.
For 2 I used ugly macro hackery to avoid declaring every function twice, in a
c file and in a header.
Opinions on the state of the above patches?
I did not expect any performance difference in the current usage, but just to
be sure I ran the following tests:
connection heavy:
pgbench -n -S -p 5501 -h /tmp -U andres postgres -c 16 -j 16 -T 10 -C
master: 3109 3024 3012
ilist: 3097 3033 3024
somewhat SearchCatCache heavy:
pgbench -n -S -p 5501 -h /tmp -U andres postgres -T 100 -c 16 -j 1
master: 98979.453879 99554.485631 99393.587880
ilist: 98960.545559 99583.319870 99498.923273
As expected the differences are on the level of noise...
Greetings,
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
From 2e9d955fbb625004061509a62ecca83fde68d027 Mon Sep 17 00:00:00 2001
From: Andres Freund <and...@anarazel.de>
Date: Sun, 6 May 2012 00:26:35 +0200
Subject: [PATCH 1/3] Add embedded list interface (header only)
Adds a single and a double linked list which can easily embedded into other
datastructures and can be used without any additional allocations.
Problematic: It requires USE_INLINE to be used. It could be remade to fallback
to to externally defined functions if that is not available but that hardly
seems sensibly at this day and age. Besides, the speed hit would be noticeable
and its only used in new code which could be disabled on machines - given they
still exists - without proper support for inline functions
3 files changed, 509 insertions(+), 1 deletion(-)
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 2e1061e..c94297a 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
-OBJS = dllist.o stringinfo.o
+OBJS = dllist.o stringinfo.o ilist.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
new file mode 100644
index 0000000..72de7a3
--- /dev/null
+++ b/src/backend/lib/ilist.c
@@ -0,0 +1,79 @@
+/*-------------------------------------------------------------------------
+ *
+ * ilist.c
+ * support for integrated/inline double and single linked lists
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/lib/ilist.c
+ *
+ * NOTES
+ *
+ * This function only contains testing code for inline single/double linked
+ * lists.
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "lib/ilist.h"
+
+#ifdef ILIST_DEBUG
+void ilist_d_check(ilist_d_head* head)
+{
+ ilist_d_node *cur;
+
+ if(!head ||
+ !(&head->head))
+ elog(ERROR, "double linked list head is not properly initialized");
+
+ for(cur = head->head.next;
+ cur != &head->head;
+ cur = cur->next){
+ if(!(cur) ||
+ !(cur->next) ||
+ !(cur->prev) ||
+ !(cur->prev->next == cur) ||
+ !(cur->next->prev == cur))
+ {
+ elog(ERROR, "double linked list is corrupted");
+ }
+ }
+
+ for(cur = head->head.prev;
+ cur != &head->head;
+ cur = cur->prev){
+ if(!(cur) ||
+ !(cur->next) ||
+ !(cur->prev) ||
+ !(cur->prev->next == cur) ||
+ !(cur->next->prev == cur))
+ {
+ elog(ERROR, "double linked list is corrupted");
+ }
+ }
+}
+
+void ilist_s_check(ilist_s_head* head)
+{
+ ilist_s_node *cur;
+
+ if(!head ||
+ !(&head->head))
+ elog(ERROR, "single linked list head is not properly initialized");
+
+ /* there isn't much we can test in a single linked list except that its really circular */
+ for(cur = head->head.next;
+ cur != &head->head;
+ cur = cur->next){
+
+ if(!cur){
+ elog(ERROR, "single linked list is corrupted");
+ }
+ }
+}
+#endif
diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h
new file mode 100644
index 0000000..cb1de99
--- /dev/null
+++ b/src/include/lib/ilist.h
@@ -0,0 +1,429 @@
+/*-------------------------------------------------------------------------
+ *
+ * ilist.h
+ * integrated/inline double and single linked lists without memory
+ * managment overhead
+ *
+ * This is intended to be used in the following manner:
+ *
+ * #include "lib/ilist.h"
+ *
+ * typedef struct something_in_a_list {
+ * int value;
+ * int somethingelse;
+ * ilist_d_head values;
+ * } something_in_a_list;
+ *
+ * typedef struct value_in_a_list {
+ * int data;
+ * int somethingelse;
+ * ilist_d_node list_node;
+ * } value_in_a_list;
+ *
+ * something_in_a_list *somelist = get_blarg();
+ *
+ * ilist_d_push_front(somelist, &get_value_in_a_list()->list_node);
+ * ...
+ * ilist_d_push_front(somelist, &get_value_in_a_list()->list_node);
+ * ...
+ * ...
+ * ilist_d_node *node, *next;
+ *
+ * ilist_d_foreach(node, somelist)
+ * {
+ * value_in_a_list *val = ilist_container(value_in_a_list, list_node, node);
+ * do_something_with_val(val);
+ * }
+ *
+ * ilist_d_foreach_modify(node, next, somelist)
+ * {
+ * ilist_d_remove(node);
+ * }
+ *
+ * This allows somewhat convenient list manipulation with low overhead.
+ *
+ * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/lib/ilist.h
+ *-------------------------------------------------------------------------
+ */
+#ifndef ILIST_H
+#define ILIST_H
+
+/*
+ * enable for extra debugging. This is rather expensive so its not enabled by
+ * default even with --enable-cassert
+*/
+/* #define ILIST_DEBUG */
+
+/*
+ * gcc warns about unused parameters if -Wunused-parameter is specified (part
+ * of -Wextra ). In the cases below its perfectly fine not to use those
+ * parameters because they are just passed to make the interface consistent and
+ * to allow debugging in case of ILIST_DEBUG.
+ *
+ */
+#ifdef __GNUC__
+#define unused_attr __attribute__((unused))
+#else
+#define unused_attr
+#endif
+
+#ifndef USE_INLINE
+#error "a compiler supporting static inlines is required"
+#endif
+
+#include <assert.h>
+
+/*
+ * struct to embed in other structs that need to be part of a double linked
+ * list.
+ */
+typedef struct ilist_d_node ilist_d_node;
+struct ilist_d_node
+{
+ ilist_d_node* prev;
+ ilist_d_node* next;
+};
+
+/*
+ * Head of a double linked list. Lists are internally *always* circularly
+ * linked, even when empty. This allows to do many many manipulations without
+ * branches which is beneficial performancewise.
+ */
+typedef struct
+{
+ ilist_d_node head;
+} ilist_d_head;
+
+/*
+ * struct to embed in other structs that need to be part of a single linked
+ * list.
+ */
+typedef struct ilist_s_node ilist_s_node;
+struct ilist_s_node
+{
+ ilist_s_node* next;
+};
+
+/*
+ * Head of a single linked list.
+ */
+typedef struct
+{
+ ilist_s_node head;
+} ilist_s_head;
+
+
+
+#ifdef ILIST_DEBUG
+
+void ilist_d_check(ilist_d_head* head);
+void ilist_s_check(ilist_s_head* head);
+
+#else
+
+static inline void ilist_d_check(unused_attr ilist_d_head* head)
+{
+}
+
+static inline void ilist_s_check(unused_attr ilist_s_head* head)
+{
+}
+
+#endif /* ILIST_DEBUG */
+
+/*
+ * Initialize the head of a list. Previous state will be thrown away without
+ * any cleanup.
+ */
+static inline void ilist_d_init(ilist_d_head *head)
+{
+ head->head.next = head->head.prev = &head->head;
+ ilist_d_check(head);
+}
+
+/*
+ * adds a node at the beginning of the list
+ */
+static inline void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node)
+{
+ node->next = head->head.next;
+ node->prev = &head->head;
+ node->next->prev = node;
+ head->head.next = node;
+ ilist_d_check(head);
+}
+
+
+/*
+ * adds a node at the end of the list
+ */
+static inline void ilist_d_push_back(ilist_d_head *head, ilist_d_node *node)
+{
+ node->next = &head->head;
+ node->prev = head->head.prev;
+ node->prev->next = node;
+ head->head.prev = node;
+ ilist_d_check(head);
+}
+
+
+/*
+ * adds a node after another *in the same list*
+ */
+static inline void ilist_d_add_after(unused_attr ilist_d_head *head, ilist_d_node *after, ilist_d_node *node)
+{
+ ilist_d_check(head);
+ node->prev = after;
+ node->next = after->next;
+ after->next = node;
+ node->next->prev = node;
+ ilist_d_check(head);
+}
+
+/*
+ * adds a node after another *in the same list*
+ */
+static inline void ilist_d_add_before(unused_attr ilist_d_head *head, ilist_d_node *before, ilist_d_node *node)
+{
+ ilist_d_check(head);
+ node->prev = before->prev;
+ node->next = before;
+ before->prev = node;
+ node->prev->next = node;
+ ilist_d_check(head);
+}
+
+
+/*
+ * removes a node from a list
+ */
+static inline void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *node)
+{
+ ilist_d_check(head);
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+ ilist_d_check(head);
+}
+
+/*
+ * removes the first node from a list or returns NULL
+ */
+static inline ilist_d_node* ilist_d_pop_front(ilist_d_head *head)
+{
+ ilist_d_node* ret;
+
+ if (&head->head == head->head.next)
+ return NULL;
+
+ ret = head->head.next;
+ ilist_d_remove(head, head->head.next);
+ return ret;
+}
+
+/*
+ * moves an element that has to be in the list to the front of the list
+ */
+static inline void ilist_d_move_front(ilist_d_head *head, ilist_d_node *node)
+{
+ /* fast path if its already at the front */
+ if(&head->head == node)
+ return;
+ ilist_d_remove(head, node);
+ ilist_d_push_front(head, node);
+ ilist_d_check(head);
+}
+
+/*
+ * Check whether the passed node is the last element in the list
+ */
+static inline bool ilist_d_has_next(ilist_d_head *head, ilist_d_node *node)
+{
+ return node->next != &head->head;
+}
+
+/*
+ * Check whether the passed node is the first element in the list
+ */
+static inline bool ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node)
+{
+ return node->prev != &head->head;
+}
+
+/*
+ * Check whether the list is empty.
+ */
+static inline bool ilist_d_is_empty(ilist_d_head *head)
+{
+ return head->head.next == head->head.prev;
+}
+
+/*
+ * Return the value of first element in the list if there is one, return NULL
+ * otherwise.
+ *
+ * ptr *will* be evaluated multiple times.
+ */
+#define ilist_d_front(type, membername, ptr) (&((ptr)->head) == (ptr)->head.next) ? \
+ NULL : ilist_container(type, membername, (ptr)->head.next)
+
+/*
+ * Return the value of the first element. This will corrupt data if there is no
+ * element in the list.
+ */
+#define ilist_d_front_unchecked(type, membername, ptr) ilist_container(type, membername, (ptr)->head.next)
+
+/*
+ * Return the value of the last element in the list if ther eis one, return
+ * NULL otherwise.
+ *
+ * ptr *will* be evaluated multiple times.
+ */
+#define ilist_d_back(type, membername, ptr) (&((ptr)->head) == (ptr)->head.prev) ? \
+ NULL : ilist_container(type, membername, (ptr)->head.prev)
+
+/*
+ * Return a pointer to the struct `type` when the passed `ptr` points to the
+ * element `membername`.
+ */
+#define ilist_container(type, membername, ptr) ((type*)((char*)(ptr) - offsetof(type, membername)))
+
+/*
+ * Iterate through the list storing the current element in the variable
+ * `name`. `ptr` will be evaluated repeatedly.
+ *
+ * It is *not* allowed to manipulate the list during iteration.
+ */
+#define ilist_d_foreach(name, ptr) for(name = (ptr)->head.next; \
+ name != &(ptr)->head; \
+ name = name->next)
+
+
+/*
+ * Iterate through the list storing the current element in the variable `name`
+ * and also storing the next list element in the variable `nxt`.
+ *
+ * It is allowed to remove the current element from the list. Every other
+ * manipulation can lead to curruption.
+ */
+#define ilist_d_foreach_modify(name, nxt, ptr) for(name = (ptr)->head.next, \
+ nxt = name->next; \
+ name != &(ptr)->head \
+ ; \
+ name = nxt, nxt = name->next)
+
+/*
+ * Iterate through the list in reverse order storing the current element in the
+ * variable `name`. `ptr` will be evaluated repeatedly.
+ *
+ * It is *not* allowed to manipulate the list during iteration.
+ */
+#define ilist_d_reverse_foreach(name, ptr) for(name = (ptr)->head.prev; \
+ name != &(ptr)->head; \
+ name = name->prev)
+
+
+/*
+ * Initialize a single linked list element.
+ */
+static inline void ilist_s_init(ilist_s_head *head)
+{
+ head->head.next = NULL;
+ ilist_s_check(head);
+}
+
+static inline void ilist_s_push_front(ilist_s_head *head, ilist_s_node *node)
+{
+ node->next = head->head.next;
+ head->head.next = node;
+ ilist_s_check(head);
+}
+
+/*
+ * fails if the list is empty
+ */
+static inline ilist_s_node* ilist_s_pop_front(ilist_s_head *head)
+{
+ ilist_s_node* front = head->head.next;
+ head->head.next = head->head.next->next;
+ ilist_s_check(head);
+ return front;
+}
+
+/*
+ * removes a node from a list
+ *
+ * Attention: O(n)
+ *
+ * XXX: This function possibly should be out-of-line?
+ */
+static inline void ilist_s_remove(ilist_s_head *head,
+ ilist_s_node *node)
+{
+ ilist_s_node *last = &head->head;
+ ilist_s_node *cur;
+#ifdef ILIST_DEBUG
+ bool found = false;
+#endif
+ while ((cur = last->next))
+ {
+ if (cur == node)
+ {
+ last->next = cur->next;
+#ifdef ILIST_DEBUG
+ found = true;
+#endif
+ break;
+ }
+ last = cur;
+ }
+ ilist_s_check(head);
+
+#ifdef ILIST_DEBUG
+ if(!found)
+ elog(ERROR, "tried to remove nonexisting node");
+ assert(found);
+#endif
+}
+
+
+static inline void ilist_s_add_after(unused_attr ilist_s_head *head,
+ ilist_s_node *after, ilist_s_node *node)
+{
+ node->next = after->next;
+ after->next = node;
+ ilist_s_check(head);
+}
+
+
+static inline bool ilist_s_is_empty(ilist_s_head *head)
+{
+ return head->head.next == NULL;
+}
+
+static inline bool ilist_s_has_next(unused_attr ilist_s_head* head,
+ ilist_s_node *node)
+{
+ return node->next != NULL;
+}
+
+
+#define ilist_s_front(type, membername, ptr) (ilist_s_is_empty(ptr) ? \
+ ilist_container(type, membername, (ptr).next) : NULL
+
+#define ilist_s_front_unchecked(type, membername, ptr) \
+ ilist_container(type, membername, (ptr)->head.next)
+
+#define ilist_s_foreach(name, ptr) for(name = (ptr)->head.next; \
+ name != NULL; \
+ name = name->next)
+
+#define ilist_s_foreach_modify(name, nxt, ptr) for(name = (ptr)->head.next, \
+ nxt = name ? name->next : NULL; \
+ name != NULL; \
+ name = nxt, nxt = name ? name->next : NULL)
+
+
+#endif /* ILIST_H */
--
1.7.10.rc3.3.g19a6c.dirty
From 0c387b8ee04811f10eb638a40c0ca5befd3059ef Mon Sep 17 00:00:00 2001
From: Andres Freund <and...@anarazel.de>
Date: Tue, 26 Jun 2012 20:34:02 +0200
Subject: [PATCH 2/3] Rework the newly added ilist interface to be usable on
systems without USE_INLINE
I find doing such magick is ugly but...
2 files changed, 72 insertions(+), 39 deletions(-)
diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c
index 72de7a3..d1dccdb 100644
--- a/src/backend/lib/ilist.c
+++ b/src/backend/lib/ilist.c
@@ -20,7 +20,15 @@
#include "postgres.h"
+/*
+ * If inlines aren't available include the function as defined in the header,
+ * but without 'static inline' defined. That way we do not have to duplicate
+ * their functionality.
+ */
+#ifndef USE_INLINE
+#define USE_DECLARATION
#include "lib/ilist.h"
+#endif
#ifdef ILIST_DEBUG
void ilist_d_check(ilist_d_head* head)
@@ -76,4 +84,5 @@ void ilist_s_check(ilist_s_head* head)
}
}
}
-#endif
+
+#endif /* ILIST_DEBUG */
diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h
index cb1de99..91419a4 100644
--- a/src/include/lib/ilist.h
+++ b/src/include/lib/ilist.h
@@ -56,7 +56,6 @@
* default even with --enable-cassert
*/
/* #define ILIST_DEBUG */
-
/*
* gcc warns about unused parameters if -Wunused-parameter is specified (part
* of -Wextra ). In the cases below its perfectly fine not to use those
@@ -70,12 +69,6 @@
#define unused_attr
#endif
-#ifndef USE_INLINE
-#error "a compiler supporting static inlines is required"
-#endif
-
-#include <assert.h>
-
/*
* struct to embed in other structs that need to be part of a double linked
* list.
@@ -116,29 +109,56 @@ typedef struct
} ilist_s_head;
+#ifdef USE_INLINE
+#define INLINE_IF_POSSIBLE static inline
+#define USE_DECLARATION
+#else
+#define INLINE_IF_POSSIBLE
+#endif
-#ifdef ILIST_DEBUG
+#ifndef USE_INLINE
+extern void ilist_d_check(unused_attr ilist_d_head* head);
+extern void ilist_d_init(ilist_d_head *head);
+extern void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node);
+extern void ilist_d_push_back(ilist_d_head *head, ilist_d_node *node);
+extern void ilist_d_add_after(unused_attr ilist_d_head *head, ilist_d_node *after, ilist_d_node *node);
+extern void ilist_d_add_before(unused_attr ilist_d_head *head, ilist_d_node *before, ilist_d_node *node);
+extern void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *node);
+extern ilist_d_node* ilist_d_pop_front(ilist_d_head *head);
+extern void ilist_d_move_front(ilist_d_head *head, ilist_d_node *node);
+extern bool ilist_d_has_next(ilist_d_head *head, ilist_d_node *node);
+extern bool ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node);
+extern bool ilist_d_is_empty(ilist_d_head *head);
+extern void ilist_d_check(ilist_d_head* head);
+
+extern void ilist_s_init(ilist_s_head *head);
+extern void ilist_s_push_front(ilist_s_head *head, ilist_s_node *node);
+extern ilist_s_node* ilist_s_pop_front(ilist_s_head *head);
+extern void ilist_s_remove(ilist_s_head *head, ilist_s_node *node);
+extern void ilist_s_add_after(unused_attr ilist_s_head *head,
+ ilist_s_node *after, ilist_s_node *node);
+extern bool ilist_s_is_empty(ilist_s_head *head);
+extern bool ilist_s_has_next(unused_attr ilist_s_head* head,
+ ilist_s_node *node);
+
+#endif /* USE_INLINE */
-void ilist_d_check(ilist_d_head* head);
-void ilist_s_check(ilist_s_head* head);
+#ifdef ILIST_DEBUG
+extern void ilist_d_check(ilist_d_head* head);
+extern void ilist_s_check(ilist_s_head* head);
#else
+#define ilist_d_check(head)
+#define ilist_s_check(head)
+#endif /*ILIST_DEBUG*/
-static inline void ilist_d_check(unused_attr ilist_d_head* head)
-{
-}
-
-static inline void ilist_s_check(unused_attr ilist_s_head* head)
-{
-}
-
-#endif /* ILIST_DEBUG */
+#ifdef USE_DECLARATION
/*
* Initialize the head of a list. Previous state will be thrown away without
* any cleanup.
*/
-static inline void ilist_d_init(ilist_d_head *head)
+INLINE_IF_POSSIBLE void ilist_d_init(ilist_d_head *head)
{
head->head.next = head->head.prev = &head->head;
ilist_d_check(head);
@@ -147,7 +167,7 @@ static inline void ilist_d_init(ilist_d_head *head)
/*
* adds a node at the beginning of the list
*/
-static inline void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node)
+INLINE_IF_POSSIBLE void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node)
{
node->next = head->head.next;
node->prev = &head->head;
@@ -160,7 +180,7 @@ static inline void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node)
/*
* adds a node at the end of the list
*/
-static inline void ilist_d_push_back(ilist_d_head *head, ilist_d_node *node)
+INLINE_IF_POSSIBLE void ilist_d_push_back(ilist_d_head *head, ilist_d_node *node)
{
node->next = &head->head;
node->prev = head->head.prev;
@@ -173,7 +193,7 @@ static inline void ilist_d_push_back(ilist_d_head *head, ilist_d_node *node)
/*
* adds a node after another *in the same list*
*/
-static inline void ilist_d_add_after(unused_attr ilist_d_head *head, ilist_d_node *after, ilist_d_node *node)
+INLINE_IF_POSSIBLE void ilist_d_add_after(unused_attr ilist_d_head *head, ilist_d_node *after, ilist_d_node *node)
{
ilist_d_check(head);
node->prev = after;
@@ -186,7 +206,7 @@ static inline void ilist_d_add_after(unused_attr ilist_d_head *head, ilist_d_nod
/*
* adds a node after another *in the same list*
*/
-static inline void ilist_d_add_before(unused_attr ilist_d_head *head, ilist_d_node *before, ilist_d_node *node)
+INLINE_IF_POSSIBLE void ilist_d_add_before(unused_attr ilist_d_head *head, ilist_d_node *before, ilist_d_node *node)
{
ilist_d_check(head);
node->prev = before->prev;
@@ -200,7 +220,7 @@ static inline void ilist_d_add_before(unused_attr ilist_d_head *head, ilist_d_no
/*
* removes a node from a list
*/
-static inline void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *node)
+INLINE_IF_POSSIBLE void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *node)
{
ilist_d_check(head);
node->prev->next = node->next;
@@ -211,7 +231,7 @@ static inline void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *
/*
* removes the first node from a list or returns NULL
*/
-static inline ilist_d_node* ilist_d_pop_front(ilist_d_head *head)
+INLINE_IF_POSSIBLE ilist_d_node* ilist_d_pop_front(ilist_d_head *head)
{
ilist_d_node* ret;
@@ -226,7 +246,7 @@ static inline ilist_d_node* ilist_d_pop_front(ilist_d_head *head)
/*
* moves an element that has to be in the list to the front of the list
*/
-static inline void ilist_d_move_front(ilist_d_head *head, ilist_d_node *node)
+INLINE_IF_POSSIBLE void ilist_d_move_front(ilist_d_head *head, ilist_d_node *node)
{
/* fast path if its already at the front */
if(&head->head == node)
@@ -239,7 +259,7 @@ static inline void ilist_d_move_front(ilist_d_head *head, ilist_d_node *node)
/*
* Check whether the passed node is the last element in the list
*/
-static inline bool ilist_d_has_next(ilist_d_head *head, ilist_d_node *node)
+INLINE_IF_POSSIBLE bool ilist_d_has_next(ilist_d_head *head, ilist_d_node *node)
{
return node->next != &head->head;
}
@@ -247,7 +267,7 @@ static inline bool ilist_d_has_next(ilist_d_head *head, ilist_d_node *node)
/*
* Check whether the passed node is the first element in the list
*/
-static inline bool ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node)
+INLINE_IF_POSSIBLE bool ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node)
{
return node->prev != &head->head;
}
@@ -255,11 +275,13 @@ static inline bool ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node)
/*
* Check whether the list is empty.
*/
-static inline bool ilist_d_is_empty(ilist_d_head *head)
+INLINE_IF_POSSIBLE bool ilist_d_is_empty(ilist_d_head *head)
{
return head->head.next == head->head.prev;
}
+#endif /*USE_DECLARATION*/
+
/*
* Return the value of first element in the list if there is one, return NULL
* otherwise.
@@ -325,16 +347,18 @@ static inline bool ilist_d_is_empty(ilist_d_head *head)
name = name->prev)
+#ifdef USE_DECLARATION
+
/*
* Initialize a single linked list element.
*/
-static inline void ilist_s_init(ilist_s_head *head)
+INLINE_IF_POSSIBLE void ilist_s_init(ilist_s_head *head)
{
head->head.next = NULL;
ilist_s_check(head);
}
-static inline void ilist_s_push_front(ilist_s_head *head, ilist_s_node *node)
+INLINE_IF_POSSIBLE void ilist_s_push_front(ilist_s_head *head, ilist_s_node *node)
{
node->next = head->head.next;
head->head.next = node;
@@ -344,7 +368,7 @@ static inline void ilist_s_push_front(ilist_s_head *head, ilist_s_node *node)
/*
* fails if the list is empty
*/
-static inline ilist_s_node* ilist_s_pop_front(ilist_s_head *head)
+INLINE_IF_POSSIBLE ilist_s_node* ilist_s_pop_front(ilist_s_head *head)
{
ilist_s_node* front = head->head.next;
head->head.next = head->head.next->next;
@@ -359,7 +383,7 @@ static inline ilist_s_node* ilist_s_pop_front(ilist_s_head *head)
*
* XXX: This function possibly should be out-of-line?
*/
-static inline void ilist_s_remove(ilist_s_head *head,
+INLINE_IF_POSSIBLE void ilist_s_remove(ilist_s_head *head,
ilist_s_node *node)
{
ilist_s_node *last = &head->head;
@@ -384,12 +408,11 @@ static inline void ilist_s_remove(ilist_s_head *head,
#ifdef ILIST_DEBUG
if(!found)
elog(ERROR, "tried to remove nonexisting node");
- assert(found);
#endif
}
-static inline void ilist_s_add_after(unused_attr ilist_s_head *head,
+INLINE_IF_POSSIBLE void ilist_s_add_after(unused_attr ilist_s_head *head,
ilist_s_node *after, ilist_s_node *node)
{
node->next = after->next;
@@ -398,17 +421,18 @@ static inline void ilist_s_add_after(unused_attr ilist_s_head *head,
}
-static inline bool ilist_s_is_empty(ilist_s_head *head)
+INLINE_IF_POSSIBLE bool ilist_s_is_empty(ilist_s_head *head)
{
return head->head.next == NULL;
}
-static inline bool ilist_s_has_next(unused_attr ilist_s_head* head,
+INLINE_IF_POSSIBLE bool ilist_s_has_next(unused_attr ilist_s_head* head,
ilist_s_node *node)
{
return node->next != NULL;
}
+#endif /* USE_DECLARATION */
#define ilist_s_front(type, membername, ptr) (ilist_s_is_empty(ptr) ? \
ilist_container(type, membername, (ptr).next) : NULL
--
1.7.10.rc3.3.g19a6c.dirty
From 6123767950ea72ac11bcfd8736b4518fbe0c983b Mon Sep 17 00:00:00 2001
From: Andres Freund <and...@anarazel.de>
Date: Tue, 26 Jun 2012 19:53:24 +0200
Subject: [PATCH 3/3] Remove usage of lib/dllist.h and replace it by the new
lib/ilist.h interface
4 files changed, 125 insertions(+), 140 deletions(-)
diff --git a/src/backend/postmaster/autovacuum.c b/src/backend/postmaster/autovacuum.c
index dade5cc..ace27b3 100644
--- a/src/backend/postmaster/autovacuum.c
+++ b/src/backend/postmaster/autovacuum.c
@@ -76,6 +76,7 @@
#include "catalog/pg_database.h"
#include "commands/dbcommands.h"
#include "commands/vacuum.h"
+#include "lib/ilist.h"
#include "libpq/pqsignal.h"
#include "miscadmin.h"
#include "pgstat.h"
@@ -149,6 +150,7 @@ typedef struct avl_dbase
Oid adl_datid; /* hash key -- must be first */
TimestampTz adl_next_worker;
int adl_score;
+ ilist_d_node adl_node;
} avl_dbase;
/* struct to keep track of databases in worker */
@@ -256,7 +258,7 @@ typedef struct
static AutoVacuumShmemStruct *AutoVacuumShmem;
/* the database list in the launcher, and the context that contains it */
-static Dllist *DatabaseList = NULL;
+static ilist_d_head DatabaseList;
static MemoryContext DatabaseListCxt = NULL;
/* Pointer to my own WorkerInfo, valid on each worker */
@@ -403,6 +405,9 @@ AutoVacLauncherMain(int argc, char *argv[])
/* Identify myself via ps */
init_ps_display("autovacuum launcher process", "", "", "");
+ /* initialize to be empty */
+ ilist_d_init(&DatabaseList);
+
ereport(LOG,
(errmsg("autovacuum launcher started")));
@@ -505,7 +510,7 @@ AutoVacLauncherMain(int argc, char *argv[])
/* don't leave dangling pointers to freed memory */
DatabaseListCxt = NULL;
- DatabaseList = NULL;
+ ilist_d_init(&DatabaseList);
/*
* Make sure pgstat also considers our stat data as gone. Note: we
@@ -573,7 +578,7 @@ AutoVacLauncherMain(int argc, char *argv[])
struct timeval nap;
TimestampTz current_time = 0;
bool can_launch;
- Dlelem *elem;
+ avl_dbase *avdb;
int rc;
/*
@@ -735,11 +740,9 @@ AutoVacLauncherMain(int argc, char *argv[])
/* We're OK to start a new worker */
- elem = DLGetTail(DatabaseList);
- if (elem != NULL)
+ avdb = ilist_d_front(avl_dbase, adl_node, &DatabaseList);
+ if (avdb != NULL)
{
- avl_dbase *avdb = DLE_VAL(elem);
-
/*
* launch a worker if next_worker is right now or it is in the
* past
@@ -780,7 +783,7 @@ AutoVacLauncherMain(int argc, char *argv[])
static void
launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap)
{
- Dlelem *elem;
+ avl_dbase *avdb;
/*
* We sleep until the next scheduled vacuum. We trust that when the
@@ -793,9 +796,8 @@ launcher_determine_sleep(bool canlaunch, bool recursing, struct timeval * nap)
nap->tv_sec = autovacuum_naptime;
nap->tv_usec = 0;
}
- else if ((elem = DLGetTail(DatabaseList)) != NULL)
+ else if ((avdb = ilist_d_back(avl_dbase, adl_node, &DatabaseList)) != NULL)
{
- avl_dbase *avdb = DLE_VAL(elem);
TimestampTz current_time = GetCurrentTimestamp();
TimestampTz next_wakeup;
long secs;
@@ -864,6 +866,7 @@ rebuild_database_list(Oid newdb)
int score;
int nelems;
HTAB *dbhash;
+ ilist_d_node *elem;
/* use fresh stats */
autovac_refresh_stats();
@@ -924,36 +927,28 @@ rebuild_database_list(Oid newdb)
}
/* Now insert the databases from the existing list */
- if (DatabaseList != NULL)
+ ilist_d_foreach(elem, &DatabaseList)
{
- Dlelem *elem;
-
- elem = DLGetHead(DatabaseList);
- while (elem != NULL)
- {
- avl_dbase *avdb = DLE_VAL(elem);
- avl_dbase *db;
- bool found;
- PgStat_StatDBEntry *entry;
-
- elem = DLGetSucc(elem);
+ avl_dbase *avdb = ilist_container(avl_dbase, adl_node, elem);
+ avl_dbase *db;
+ bool found;
+ PgStat_StatDBEntry *entry;
- /*
- * skip databases with no stat entries -- in particular, this gets
- * rid of dropped databases
- */
- entry = pgstat_fetch_stat_dbentry(avdb->adl_datid);
- if (entry == NULL)
- continue;
+ /*
+ * skip databases with no stat entries -- in particular, this gets
+ * rid of dropped databases
+ */
+ entry = pgstat_fetch_stat_dbentry(avdb->adl_datid);
+ if (entry == NULL)
+ continue;
- db = hash_search(dbhash, &(avdb->adl_datid), HASH_ENTER, &found);
+ db = hash_search(dbhash, &(avdb->adl_datid), HASH_ENTER, &found);
- if (!found)
- {
- /* hash_search already filled in the key */
- db->adl_score = score++;
- /* next_worker is filled in later */
- }
+ if (!found)
+ {
+ /* hash_search already filled in the key */
+ db->adl_score = score++;
+ /* next_worker is filled in later */
}
}
@@ -984,7 +979,7 @@ rebuild_database_list(Oid newdb)
/* from here on, the allocated memory belongs to the new list */
MemoryContextSwitchTo(newcxt);
- DatabaseList = DLNewList();
+ ilist_d_init(&DatabaseList);
if (nelems > 0)
{
@@ -1026,15 +1021,13 @@ rebuild_database_list(Oid newdb)
for (i = 0; i < nelems; i++)
{
avl_dbase *db = &(dbary[i]);
- Dlelem *elem;
current_time = TimestampTzPlusMilliseconds(current_time,
millis_increment);
db->adl_next_worker = current_time;
- elem = DLNewElem(db);
/* later elements should go closer to the head of the list */
- DLAddHead(DatabaseList, elem);
+ ilist_d_push_front(&DatabaseList, &db->adl_node);
}
}
@@ -1144,7 +1137,7 @@ do_start_worker(void)
foreach(cell, dblist)
{
avw_dbase *tmp = lfirst(cell);
- Dlelem *elem;
+ ilist_d_node *elem;
/* Check to see if this one is at risk of wraparound */
if (TransactionIdPrecedes(tmp->adw_frozenxid, xidForceLimit))
@@ -1176,11 +1169,10 @@ do_start_worker(void)
* autovacuum time yet.
*/
skipit = false;
- elem = DatabaseList ? DLGetTail(DatabaseList) : NULL;
- while (elem != NULL)
+ ilist_d_reverse_foreach(elem, &DatabaseList)
{
- avl_dbase *dbp = DLE_VAL(elem);
+ avl_dbase *dbp = ilist_container(avl_dbase, adl_node, elem);
if (dbp->adl_datid == tmp->adw_datid)
{
@@ -1197,7 +1189,6 @@ do_start_worker(void)
break;
}
- elem = DLGetPred(elem);
}
if (skipit)
continue;
@@ -1271,7 +1262,7 @@ static void
launch_worker(TimestampTz now)
{
Oid dbid;
- Dlelem *elem;
+ ilist_d_node *elem;
dbid = do_start_worker();
if (OidIsValid(dbid))
@@ -1280,10 +1271,9 @@ launch_worker(TimestampTz now)
* Walk the database list and update the corresponding entry. If the
* database is not on the list, we'll recreate the list.
*/
- elem = (DatabaseList == NULL) ? NULL : DLGetHead(DatabaseList);
- while (elem != NULL)
+ ilist_d_foreach(elem, &DatabaseList)
{
- avl_dbase *avdb = DLE_VAL(elem);
+ avl_dbase *avdb = ilist_container(avl_dbase, adl_node, elem);
if (avdb->adl_datid == dbid)
{
@@ -1294,10 +1284,9 @@ launch_worker(TimestampTz now)
avdb->adl_next_worker =
TimestampTzPlusMilliseconds(now, autovacuum_naptime * 1000);
- DLMoveToFront(elem);
+ ilist_d_move_front(&DatabaseList, elem);
break;
}
- elem = DLGetSucc(elem);
}
/*
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index 913734f..f64e341 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -95,7 +95,7 @@
#include "access/xlog.h"
#include "bootstrap/bootstrap.h"
#include "catalog/pg_control.h"
-#include "lib/dllist.h"
+#include "lib/ilist.h"
#include "libpq/auth.h"
#include "libpq/ip.h"
#include "libpq/libpq.h"
@@ -145,10 +145,10 @@ typedef struct bkend
int child_slot; /* PMChildSlot for this backend, if any */
bool is_autovacuum; /* is it an autovacuum process? */
bool dead_end; /* is it going to send an error and quit? */
- Dlelem elem; /* list link in BackendList */
+ ilist_d_node elem; /* list link in BackendList */
} Backend;
-static Dllist *BackendList;
+static ilist_d_head BackendList;
#ifdef EXEC_BACKEND
static Backend *ShmemBackendArray;
@@ -976,7 +976,7 @@ PostmasterMain(int argc, char *argv[])
/*
* Initialize the list of active backends.
*/
- BackendList = DLNewList();
+ ilist_d_init(&BackendList);
/*
* Initialize pipe (or process handle on Windows) that allows children to
@@ -1797,7 +1797,7 @@ processCancelRequest(Port *port, void *pkt)
Backend *bp;
#ifndef EXEC_BACKEND
- Dlelem *curr;
+ ilist_d_node *curr;
#else
int i;
#endif
@@ -1811,9 +1811,9 @@ processCancelRequest(Port *port, void *pkt)
* duplicate array in shared memory.
*/
#ifndef EXEC_BACKEND
- for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
+ ilist_d_foreach(curr, &BackendList)
{
- bp = (Backend *) DLE_VAL(curr);
+ bp = ilist_container(Backend, elem, curr);
#else
for (i = MaxLivePostmasterChildren() - 1; i >= 0; i--)
{
@@ -2591,8 +2591,7 @@ static void
CleanupBackend(int pid,
int exitstatus) /* child's exit status. */
{
- Dlelem *curr;
-
+ ilist_d_node *curr, *next;
LogChildExit(DEBUG2, _("server process"), pid, exitstatus);
/*
@@ -2623,9 +2622,9 @@ CleanupBackend(int pid,
return;
}
- for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
+ ilist_d_foreach_modify(curr, next, &BackendList)
{
- Backend *bp = (Backend *) DLE_VAL(curr);
+ Backend *bp = ilist_container(Backend, elem, curr);
if (bp->pid == pid)
{
@@ -2644,7 +2643,7 @@ CleanupBackend(int pid,
ShmemBackendArrayRemove(bp);
#endif
}
- DLRemove(curr);
+ ilist_d_remove(&BackendList, curr);
free(bp);
break;
}
@@ -2661,7 +2660,7 @@ CleanupBackend(int pid,
static void
HandleChildCrash(int pid, int exitstatus, const char *procname)
{
- Dlelem *curr,
+ ilist_d_node *curr,
*next;
Backend *bp;
@@ -2677,10 +2676,10 @@ HandleChildCrash(int pid, int exitstatus, const char *procname)
}
/* Process regular backends */
- for (curr = DLGetHead(BackendList); curr; curr = next)
+ ilist_d_foreach_modify(curr, next, &BackendList)
{
- next = DLGetSucc(curr);
- bp = (Backend *) DLE_VAL(curr);
+ bp = ilist_container(Backend, elem, curr);
+
if (bp->pid == pid)
{
/*
@@ -2693,7 +2692,7 @@ HandleChildCrash(int pid, int exitstatus, const char *procname)
ShmemBackendArrayRemove(bp);
#endif
}
- DLRemove(curr);
+ ilist_d_remove(&BackendList, curr);
free(bp);
/* Keep looping so we can signal remaining backends */
}
@@ -3056,7 +3055,7 @@ PostmasterStateMachine(void)
* normal state transition leading up to PM_WAIT_DEAD_END, or during
* FatalError processing.
*/
- if (DLGetHead(BackendList) == NULL &&
+ if (ilist_d_is_empty(&BackendList) &&
PgArchPID == 0 && PgStatPID == 0)
{
/* These other guys should be dead already */
@@ -3182,12 +3181,12 @@ signal_child(pid_t pid, int signal)
static bool
SignalSomeChildren(int signal, int target)
{
- Dlelem *curr;
+ ilist_d_node *curr;
bool signaled = false;
- for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
+ ilist_d_foreach(curr, &BackendList)
{
- Backend *bp = (Backend *) DLE_VAL(curr);
+ Backend *bp = ilist_container(Backend, elem, curr);
if (bp->dead_end)
continue;
@@ -3325,8 +3324,8 @@ BackendStartup(Port *port)
*/
bn->pid = pid;
bn->is_autovacuum = false;
- DLInitElem(&bn->elem, bn);
- DLAddHead(BackendList, &bn->elem);
+ ilist_d_push_front(&BackendList, &bn->elem);
+
#ifdef EXEC_BACKEND
if (!bn->dead_end)
ShmemBackendArrayAdd(bn);
@@ -4422,12 +4421,12 @@ PostmasterRandom(void)
static int
CountChildren(int target)
{
- Dlelem *curr;
+ ilist_d_node *curr;
int cnt = 0;
- for (curr = DLGetHead(BackendList); curr; curr = DLGetSucc(curr))
+ ilist_d_foreach(curr, &BackendList)
{
- Backend *bp = (Backend *) DLE_VAL(curr);
+ Backend *bp = ilist_container(Backend, elem, curr);
if (bp->dead_end)
continue;
@@ -4606,8 +4605,7 @@ StartAutovacuumWorker(void)
if (bn->pid > 0)
{
bn->is_autovacuum = true;
- DLInitElem(&bn->elem, bn);
- DLAddHead(BackendList, &bn->elem);
+ ilist_d_push_front(&BackendList, &bn->elem);
#ifdef EXEC_BACKEND
ShmemBackendArrayAdd(bn);
#endif
diff --git a/src/backend/utils/cache/catcache.c b/src/backend/utils/cache/catcache.c
index 0307b96..3b4e87a 100644
--- a/src/backend/utils/cache/catcache.c
+++ b/src/backend/utils/cache/catcache.c
@@ -353,6 +353,8 @@ CatCachePrintStats(int code, Datum arg)
static void
CatCacheRemoveCTup(CatCache *cache, CatCTup *ct)
{
+ Index hashIndex;
+
Assert(ct->refcount == 0);
Assert(ct->my_cache == cache);
@@ -369,7 +371,9 @@ CatCacheRemoveCTup(CatCache *cache, CatCTup *ct)
}
/* delink from linked list */
- DLRemove(&ct->cache_elem);
+ hashIndex = HASH_INDEX(ct->hash_value, cache->cc_nbuckets);
+
+ ilist_d_remove(&cache->cc_bucket[hashIndex], &ct->cache_elem);
/* free associated tuple data */
if (ct->tuple.t_data != NULL)
@@ -412,7 +416,7 @@ CatCacheRemoveCList(CatCache *cache, CatCList *cl)
}
/* delink from linked list */
- DLRemove(&cl->cache_elem);
+ ilist_d_remove(&cache->cc_lists, &cl->cache_elem);
/* free associated tuple data */
if (cl->tuple.t_data != NULL)
@@ -452,8 +456,9 @@ CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next)
{
Index hashIndex;
- Dlelem *elt,
+ ilist_d_node *elt,
*nextelt;
+ ilist_d_head *bucket;
if (cacheId != ccp->id)
continue;
@@ -468,11 +473,9 @@ CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
* Invalidate *all* CatCLists in this cache; it's too hard to tell
* which searches might still be correct, so just zap 'em all.
*/
- for (elt = DLGetHead(&ccp->cc_lists); elt; elt = nextelt)
+ ilist_d_foreach_modify(elt, nextelt, &ccp->cc_lists)
{
- CatCList *cl = (CatCList *) DLE_VAL(elt);
-
- nextelt = DLGetSucc(elt);
+ CatCList *cl = ilist_container(CatCList, cache_elem, elt);
if (cl->refcount > 0)
cl->dead = true;
@@ -484,12 +487,10 @@ CatalogCacheIdInvalidate(int cacheId, uint32 hashValue)
* inspect the proper hash bucket for tuple matches
*/
hashIndex = HASH_INDEX(hashValue, ccp->cc_nbuckets);
-
- for (elt = DLGetHead(&ccp->cc_bucket[hashIndex]); elt; elt = nextelt)
+ bucket = &ccp->cc_bucket[hashIndex];
+ ilist_d_foreach_modify(elt, nextelt, bucket)
{
- CatCTup *ct = (CatCTup *) DLE_VAL(elt);
-
- nextelt = DLGetSucc(elt);
+ CatCTup *ct = ilist_container(CatCTup, cache_elem, elt);
if (hashValue == ct->hash_value)
{
@@ -561,13 +562,13 @@ AtEOXact_CatCache(bool isCommit)
for (ccp = CacheHdr->ch_caches; ccp; ccp = ccp->cc_next)
{
- Dlelem *elt;
+ ilist_d_node *elt;
int i;
/* Check CatCLists */
- for (elt = DLGetHead(&ccp->cc_lists); elt; elt = DLGetSucc(elt))
+ ilist_d_foreach(elt, &ccp->cc_lists)
{
- CatCList *cl = (CatCList *) DLE_VAL(elt);
+ CatCList *cl = ilist_container(CatCList, cache_elem, elt);
Assert(cl->cl_magic == CL_MAGIC);
Assert(cl->refcount == 0);
@@ -577,11 +578,10 @@ AtEOXact_CatCache(bool isCommit)
/* Check individual tuples */
for (i = 0; i < ccp->cc_nbuckets; i++)
{
- for (elt = DLGetHead(&ccp->cc_bucket[i]);
- elt;
- elt = DLGetSucc(elt))
+ ilist_d_head *bucket = &ccp->cc_bucket[i];
+ ilist_d_foreach(elt, bucket)
{
- CatCTup *ct = (CatCTup *) DLE_VAL(elt);
+ CatCTup *ct = ilist_container(CatCTup, cache_elem, elt);
Assert(ct->ct_magic == CT_MAGIC);
Assert(ct->refcount == 0);
@@ -604,16 +604,14 @@ AtEOXact_CatCache(bool isCommit)
static void
ResetCatalogCache(CatCache *cache)
{
- Dlelem *elt,
+ ilist_d_node *elt,
*nextelt;
int i;
/* Remove each list in this cache, or at least mark it dead */
- for (elt = DLGetHead(&cache->cc_lists); elt; elt = nextelt)
+ ilist_d_foreach_modify(elt, nextelt, &cache->cc_lists)
{
- CatCList *cl = (CatCList *) DLE_VAL(elt);
-
- nextelt = DLGetSucc(elt);
+ CatCList *cl = ilist_container(CatCList, cache_elem, elt);
if (cl->refcount > 0)
cl->dead = true;
@@ -624,11 +622,10 @@ ResetCatalogCache(CatCache *cache)
/* Remove each tuple in this cache, or at least mark it dead */
for (i = 0; i < cache->cc_nbuckets; i++)
{
- for (elt = DLGetHead(&cache->cc_bucket[i]); elt; elt = nextelt)
+ ilist_d_head *bucket = &cache->cc_bucket[i];
+ ilist_d_foreach_modify(elt, nextelt, bucket)
{
- CatCTup *ct = (CatCTup *) DLE_VAL(elt);
-
- nextelt = DLGetSucc(elt);
+ CatCTup *ct = ilist_container(CatCTup, cache_elem, elt);
if (ct->refcount > 0 ||
(ct->c_list && ct->c_list->refcount > 0))
@@ -770,10 +767,8 @@ InitCatCache(int id,
/*
* allocate a new cache structure
- *
- * Note: we assume zeroing initializes the Dllist headers correctly
*/
- cp = (CatCache *) palloc0(sizeof(CatCache) + nbuckets * sizeof(Dllist));
+ cp = (CatCache *) palloc0(sizeof(CatCache) + nbuckets * sizeof(ilist_d_node));
/*
* initialize the cache's relation information for the relation
@@ -792,6 +787,12 @@ InitCatCache(int id,
for (i = 0; i < nkeys; ++i)
cp->cc_key[i] = key[i];
+ ilist_d_init(&cp->cc_lists);
+
+ for (i = 0; i < nbuckets; i++){
+ ilist_d_init(&cp->cc_bucket[i]);
+ }
+
/*
* new cache is initialized as far as we can go for now. print some
* debugging information, if appropriate.
@@ -1060,7 +1061,8 @@ SearchCatCache(CatCache *cache,
ScanKeyData cur_skey[CATCACHE_MAXKEYS];
uint32 hashValue;
Index hashIndex;
- Dlelem *elt;
+ ilist_d_node *elt;
+ ilist_d_head *bucket;
CatCTup *ct;
Relation relation;
SysScanDesc scandesc;
@@ -1094,13 +1096,11 @@ SearchCatCache(CatCache *cache,
/*
* scan the hash bucket until we find a match or exhaust our tuples
*/
- for (elt = DLGetHead(&cache->cc_bucket[hashIndex]);
- elt;
- elt = DLGetSucc(elt))
- {
+ bucket = &cache->cc_bucket[hashIndex];
+ ilist_d_foreach(elt, bucket){
bool res;
- ct = (CatCTup *) DLE_VAL(elt);
+ ct = ilist_container(CatCTup, cache_elem, elt);
if (ct->dead)
continue; /* ignore dead entries */
@@ -1125,7 +1125,7 @@ SearchCatCache(CatCache *cache,
* most frequently accessed elements in any hashbucket will tend to be
* near the front of the hashbucket's list.)
*/
- DLMoveToFront(&ct->cache_elem);
+ ilist_d_move_front(bucket, &ct->cache_elem);
/*
* If it's a positive entry, bump its refcount and return it. If it's
@@ -1340,7 +1340,7 @@ SearchCatCacheList(CatCache *cache,
{
ScanKeyData cur_skey[CATCACHE_MAXKEYS];
uint32 lHashValue;
- Dlelem *elt;
+ ilist_d_node *elt;
CatCList *cl;
CatCTup *ct;
List *volatile ctlist;
@@ -1382,13 +1382,11 @@ SearchCatCacheList(CatCache *cache,
/*
* scan the items until we find a match or exhaust our list
*/
- for (elt = DLGetHead(&cache->cc_lists);
- elt;
- elt = DLGetSucc(elt))
+ ilist_d_foreach(elt, &cache->cc_lists)
{
bool res;
- cl = (CatCList *) DLE_VAL(elt);
+ cl = ilist_container(CatCList, cache_elem, elt);
if (cl->dead)
continue; /* ignore dead entries */
@@ -1416,7 +1414,7 @@ SearchCatCacheList(CatCache *cache,
* since there's no point in that unless they are searched for
* individually.)
*/
- DLMoveToFront(&cl->cache_elem);
+ ilist_d_move_front(&cache->cc_lists, &cl->cache_elem);
/* Bump the list's refcount and return it */
ResourceOwnerEnlargeCatCacheListRefs(CurrentResourceOwner);
@@ -1468,7 +1466,8 @@ SearchCatCacheList(CatCache *cache,
{
uint32 hashValue;
Index hashIndex;
-
+ bool found = false;
+ ilist_d_head *bucket;
/*
* See if there's an entry for this tuple already.
*/
@@ -1476,11 +1475,10 @@ SearchCatCacheList(CatCache *cache,
hashValue = CatalogCacheComputeTupleHashValue(cache, ntp);
hashIndex = HASH_INDEX(hashValue, cache->cc_nbuckets);
- for (elt = DLGetHead(&cache->cc_bucket[hashIndex]);
- elt;
- elt = DLGetSucc(elt))
+ bucket = &cache->cc_bucket[hashIndex];
+ ilist_d_foreach(elt, bucket)
{
- ct = (CatCTup *) DLE_VAL(elt);
+ ct = ilist_container(CatCTup, cache_elem, elt);
if (ct->dead || ct->negative)
continue; /* ignore dead and negative entries */
@@ -1498,10 +1496,11 @@ SearchCatCacheList(CatCache *cache,
if (ct->c_list)
continue;
+ found = true;
break; /* A-OK */
}
- if (elt == NULL)
+ if (!found)
{
/* We didn't find a usable entry, so make a new one */
ct = CatalogCacheCreateEntry(cache, ntp,
@@ -1564,7 +1563,6 @@ SearchCatCacheList(CatCache *cache,
cl->cl_magic = CL_MAGIC;
cl->my_cache = cache;
- DLInitElem(&cl->cache_elem, cl);
cl->refcount = 0; /* for the moment */
cl->dead = false;
cl->ordered = ordered;
@@ -1587,7 +1585,7 @@ SearchCatCacheList(CatCache *cache,
}
Assert(i == nmembers);
- DLAddHead(&cache->cc_lists, &cl->cache_elem);
+ ilist_d_push_front(&cache->cc_lists, &cl->cache_elem);
/* Finally, bump the list's refcount and return it */
cl->refcount++;
@@ -1664,14 +1662,14 @@ CatalogCacheCreateEntry(CatCache *cache, HeapTuple ntp,
*/
ct->ct_magic = CT_MAGIC;
ct->my_cache = cache;
- DLInitElem(&ct->cache_elem, (void *) ct);
+
ct->c_list = NULL;
ct->refcount = 0; /* for the moment */
ct->dead = false;
ct->negative = negative;
ct->hash_value = hashValue;
- DLAddHead(&cache->cc_bucket[hashIndex], &ct->cache_elem);
+ ilist_d_push_front(&cache->cc_bucket[hashIndex], &ct->cache_elem);
cache->cc_ntup++;
CacheHdr->ch_ntup++;
diff --git a/src/include/utils/catcache.h b/src/include/utils/catcache.h
index d91700a..20f2fa8 100644
--- a/src/include/utils/catcache.h
+++ b/src/include/utils/catcache.h
@@ -22,7 +22,7 @@
#include "access/htup.h"
#include "access/skey.h"
-#include "lib/dllist.h"
+#include "lib/ilist.h"
#include "utils/relcache.h"
/*
@@ -51,7 +51,7 @@ typedef struct catcache
ScanKeyData cc_skey[CATCACHE_MAXKEYS]; /* precomputed key info for
* heap scans */
bool cc_isname[CATCACHE_MAXKEYS]; /* flag "name" key columns */
- Dllist cc_lists; /* list of CatCList structs */
+ ilist_d_head cc_lists; /* list of CatCList structs */
#ifdef CATCACHE_STATS
long cc_searches; /* total # searches against this cache */
long cc_hits; /* # of matches against existing entry */
@@ -66,7 +66,7 @@ typedef struct catcache
long cc_lsearches; /* total # list-searches */
long cc_lhits; /* # of matches against existing lists */
#endif
- Dllist cc_bucket[1]; /* hash buckets --- VARIABLE LENGTH ARRAY */
+ ilist_d_head cc_bucket[1]; /* hash buckets --- VARIABLE LENGTH ARRAY */
} CatCache; /* VARIABLE LENGTH STRUCT */
@@ -77,11 +77,11 @@ typedef struct catctup
CatCache *my_cache; /* link to owning catcache */
/*
- * Each tuple in a cache is a member of a Dllist that stores the elements
- * of its hash bucket. We keep each Dllist in LRU order to speed repeated
+ * Each tuple in a cache is a member of a ilist_d that stores the elements
+ * of its hash bucket. We keep each ilist_d in LRU order to speed repeated
* lookups.
*/
- Dlelem cache_elem; /* list member of per-bucket list */
+ ilist_d_node cache_elem; /* list member of per-bucket list */
/*
* The tuple may also be a member of at most one CatCList. (If a single
@@ -139,7 +139,7 @@ typedef struct catclist
* might not be true during bootstrap or recovery operations. (namespace.c
* is able to save some cycles when it is true.)
*/
- Dlelem cache_elem; /* list member of per-catcache list */
+ ilist_d_node cache_elem; /* list member of per-catcache list */
int refcount; /* number of active references */
bool dead; /* dead but not yet removed? */
bool ordered; /* members listed in index order? */
--
1.7.10.rc3.3.g19a6c.dirty
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
