From 5f72be6b33b43f9615700305e469e3e3698417dd Mon Sep 17 00:00:00 2001 From: Alvaro Herrera Date: Tue, 4 Sep 2012 19:07:38 -0300 Subject: [PATCH 1/3] initial ilist stuff from Andres --- src/backend/lib/Makefile | 2 +- src/backend/lib/README.ilist | 43 ++++ src/backend/lib/ilist.c | 115 +++++++++++ src/include/lib/ilist.h | 454 ++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 613 insertions(+), 1 deletions(-) create mode 100644 src/backend/lib/README.ilist create mode 100644 src/backend/lib/ilist.c create mode 100644 src/include/lib/ilist.h 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/README.ilist b/src/backend/lib/README.ilist new file mode 100644 index 0000000..3a3d8a8 --- /dev/null +++ b/src/backend/lib/README.ilist @@ -0,0 +1,43 @@ +his is intended to be used in the following manner: + +#include "lib/ilist.h" + +typedef struct something_in_a_list +{ + int value; + int somethingelse; + Dlist_head values; +} something_in_a_list; + +typedef struct value_in_a_list +{ + int data; + int somethingelse; + Dlist_node list_node; +} value_in_a_list; + +something_in_a_list *somelist = get_blarg(); + +Dlist_push_head(somelist, &get_value_in_a_list()->list_node); +... +Dlist_push_head(somelist, &get_value_in_a_list()->list_node); +... +... +Dlist_node *node, + *next; + +Dlist_foreach(node, somelist) +{ + value_in_a_list *val = ilist_container(value_in_a_list, list_node, node); + do_something_with_val(val); +} + +Dlist_foreach_modify(node, next, somelist) +{ + /* + * here we can inspect the node and maybe delete it. Any other + * manipulation is forbidden. + */ + if (node is to be deleted) + Dlist_delete(node); +} diff --git a/src/backend/lib/ilist.c b/src/backend/lib/ilist.c new file mode 100644 index 0000000..d8bd4f3 --- /dev/null +++ b/src/backend/lib/ilist.c @@ -0,0 +1,115 @@ +/*------------------------------------------------------------------------- + * + * ilist.c + * support for integrated/inline doubly- and singly- 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 file only contains functions that are too big to be considered + * for inlining. See ilist.h for most of the goodies. + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +/* + * If inlines are in use, include the header normally which will get us only + * the function definitions as inlines. But if inlines aren't available, + * include the header with ILIST_USE_DEFINITION defined; this makes it pour in + * regular (not inline) function declarations and the corresponding (non + * inline) definitions. + */ +#ifndef USE_INLINE +#define ILIST_USE_DEFINITION +#endif +#include "lib/ilist.h" + +/* + * removes a node from a list + * + * Attention: O(n) + */ +void +slist_delete(slist_head *head, slist_node *node) +{ + slist_node *last = &head->head; + slist_node *cur; + bool found PG_USED_FOR_ASSERTS_ONLY = false; + + while ((cur = last->next) != NULL) + { + if (cur == node) + { + last->next = cur->next; +#ifdef USE_ASSERT_CHECKING + found = true; +#endif + break; + } + last = cur; + } + + slist_check(head); + Assert(found); +} + +#ifdef ILIST_DEBUG +/* + * Verify integrity of a doubly linked list + */ +void +dlist_check(dlist_head *head) +{ + dlist_node *cur; + + if (!head || !(&head->head)) + elog(ERROR, "doubly 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, "doubly 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, "doubly linked list is corrupted"); + } +} + +/* + * Verify integrity of a singly linked list + */ +void +slist_check(slist_head *head) +{ + slist_node *cur; + + if (!head || !(&head->head)) + elog(ERROR, "singly linked list head is not properly initialized"); + + /* + * there isn't much we can test in a singly linked list except that its + * really circular + */ + for (cur = head->head.next; cur != &head->head; cur = cur->next) + if (!cur) + elog(ERROR, "singly linked list is corrupted"); +} + +#endif /* ILIST_DEBUG */ diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h new file mode 100644 index 0000000..2c29902 --- /dev/null +++ b/src/include/lib/ilist.h @@ -0,0 +1,454 @@ +/*------------------------------------------------------------------------- + * + * ilist.h + * integrated/inline doubly- and singly-linked lists + * + * This implementation is as efficient as possible: the lists don't have + * any memory management overhead, because the list pointers are embedded + * within some larger structure. Also, they are always circularly linked, even + * when empty; this enables many manipulations to be done without branches, + * which is beneficial performance-wise. + * + * See src/backend/lib/README.ilist for intended usage. + * + * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/include/lib/ilist.h + *------------------------------------------------------------------------- + */ +#ifndef ILIST_H +#define ILIST_H + +/* + * enable for extra debugging. This is rather expensive, so it's not enabled by + * default even with --enable-cassert. +*/ +#undef ILIST_DEBUG + +/* + * struct to embed in other structs that need to be part of a doubly linked + * list. + */ +typedef struct dlist_node dlist_node; +struct dlist_node +{ + dlist_node *prev; + dlist_node *next; +}; + +/* + * Head of a doubly linked list. + * + * Lists are internally *always* circularly linked, even when empty. + */ +typedef struct dlist_head +{ + dlist_node head; +} dlist_head; + +/* + * struct to embed in other structs that need to be part of a singly linked + * list. + */ +typedef struct slist_node slist_node; +struct slist_node +{ + slist_node *next; +}; + +/* + * Head of a singly linked list. + * + * Lists are internally *always* circularly linked, even when empty. + */ +typedef struct slist_head +{ + slist_node head; +} slist_head; + +#ifdef USE_INLINE +#define INLINE_IF_POSSIBLE static inline +#define ILIST_USE_DEFINITION +#else +#define INLINE_IF_POSSIBLE + +/* Prototypes for functions we want to be inlined if possible */ +extern void dlist_init(dlist_head *head); +extern void dlist_push_head(dlist_head *head, dlist_node *node); +extern void dlist_push_tail(dlist_head *head, dlist_node *node); +extern void dlist_insert_after(dlist_head *head, + dlist_node *after, dlist_node *node); +extern void dlist_insert_before(dlist_head *head, + dlist_node *before, dlist_node *node); +extern void dlist_delete(dlist_head *head, dlist_node *node); +extern dlist_node *dlist_pop_head(dlist_head *head); +extern void dlist_move_head(dlist_head *head, dlist_node *node); +extern bool dlist_has_next(dlist_head *head, dlist_node *node); +extern bool dlist_has_prev(dlist_head *head, dlist_node *node); +extern bool dlist_is_empty(dlist_head *head); +extern void dlist_check(dlist_head *head); + +extern void slist_init(slist_head *head); +extern void slist_push_head(slist_head *head, slist_node *node); +extern slist_node *slist_pop_head(slist_head *head); +extern void slist_insert_after(slist_head *head, + slist_node *after, slist_node *node); +extern bool slist_is_empty(slist_head *head); +extern bool slist_has_next(slist_head *head, + slist_node *node); +#endif /* USE_INLINE */ + +/* These functions are too big to be inline, so they are in the C file always */ +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); +#else +/* + * These seemingly useless casts to void are here to keep the compiler quiet + * about the argument being unused in many functions in a non-debug compile, + * in which functions the only point of passing the list head pointer is to be + * able to run these checks. + */ +#define dlist_check(head) (void) (head) +#define slist_check(head) (void) (head) +#endif /* ILIST_DEBUG */ + +/* + * 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))) + +/* + * The following function definitions are only used if inlining is supported by + * the compiler, or when included from a file that explicitly declares + * ILIST_USE_DEFINITION. + */ +#ifdef ILIST_USE_DEFINITION + +/* + * Initialize the head of a list. Previous state will be thrown away without + * any cleanup. + */ +INLINE_IF_POSSIBLE void +dlist_init(dlist_head *head) +{ + head->head.next = head->head.prev = &head->head; + + dlist_check(head); +} + +/* + * inserts a node at the beginning of the list + */ +INLINE_IF_POSSIBLE void +dlist_push_head(dlist_head *head, dlist_node *node) +{ + node->next = head->head.next; + node->prev = &head->head; + node->next->prev = node; + head->head.next = node; + + dlist_check(head); +} + +/* + * inserts a node at the end of the list + */ +INLINE_IF_POSSIBLE void +dlist_push_tail(dlist_head *head, dlist_node *node) +{ + node->next = &head->head; + node->prev = head->head.prev; + node->prev->next = node; + head->head.prev = node; + + dlist_check(head); +} + +/* + * insert a node after another *in the same list* + */ +INLINE_IF_POSSIBLE void +dlist_insert_after(dlist_head *head, dlist_node *after, + dlist_node *node) +{ + dlist_check(head); + + node->prev = after; + node->next = after->next; + after->next = node; + node->next->prev = node; + + dlist_check(head); +} + +/* + * insert a node after another *in the same list* + */ +INLINE_IF_POSSIBLE void +dlist_insert_before(dlist_head *head, dlist_node *before, + dlist_node *node) +{ + dlist_check(head); + + node->prev = before->prev; + node->next = before; + before->prev = node; + node->prev->next = node; + + dlist_check(head); +} + +/* + * deletes a node from a list + */ +INLINE_IF_POSSIBLE void +dlist_delete(dlist_head *head, dlist_node *node) +{ + dlist_check(head); + + node->prev->next = node->next; + node->next->prev = node->prev; + + dlist_check(head); +} + +/* + * deletes the first node from a list or returns NULL + */ +INLINE_IF_POSSIBLE dlist_node * +dlist_pop_head(dlist_head *head) +{ + dlist_node *ret; + + if (&head->head == head->head.next) + return NULL; + + ret = head->head.next; + dlist_delete(head, head->head.next); + return ret; +} + +/* + * moves an element (that has to be in the list) to the head of the list + */ +INLINE_IF_POSSIBLE void +dlist_move_head(dlist_head *head, dlist_node *node) +{ + /* fast path if it's already at the head */ + if (&head->head == node) + return; + + dlist_delete(head, node); + dlist_push_head(head, node); + + dlist_check(head); +} + +/* + * Check whether the passed node is the last element in the list + */ +INLINE_IF_POSSIBLE bool +dlist_has_next(dlist_head *head, dlist_node *node) +{ + return node->next != &head->head; +} + +/* + * Check whether the passed node is the first element in the list + */ +INLINE_IF_POSSIBLE bool +dlist_has_prev(dlist_head *head, dlist_node *node) +{ + return node->prev != &head->head; +} + +/* + * Check whether the list is empty. + */ +INLINE_IF_POSSIBLE bool +dlist_is_empty(dlist_head *head) +{ + return head->head.next == &head->head; +} +#endif /* ILIST_USE_DEFINITION */ + +/* + * Return the value of first element in the list if there is one, return NULL + * otherwise. + * + * ptr *will* be evaluated multiple times. + */ +#define dlist_get_head(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 return corrupt data if + * there is no element in the list. + */ +#define dlist_get_head_unchecked(type, membername, ptr) \ + ilist_container(type, membername, (ptr)->head.next) + +/* + * Return the value of the last element in the list if there is one, return + * NULL otherwise. + * + * ptr *will* be evaluated multiple times. + */ +#define dlist_get_tail(type, membername, ptr) \ +( \ + (&((ptr)->head) == (ptr)->head.prev) ? \ + NULL : ilist_container(type, membername, (ptr)->head.prev) \ +) + +/* + * 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 dlist_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 delete the current element from the list. Every other + * manipulation can lead to corruption. + */ +#define dlist_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 dlist_reverse_foreach(name, ptr) \ + for (name = (ptr)->head.prev; name != &(ptr)->head; name = name->prev) + + +#ifdef ILIST_USE_DEFINITION + +/* + * Initialize a singly linked list. + */ +INLINE_IF_POSSIBLE void +slist_init(slist_head *head) +{ + head->head.next = NULL; + + slist_check(head); +} + +/* + * Install a new element as head of the list, pushing the original head to the + * second position. + */ +INLINE_IF_POSSIBLE void +slist_push_head(slist_head *head, slist_node *node) +{ + node->next = head->head.next; + head->head.next = node; + + slist_check(head); +} + +/* + * Returns the first element of the list, removing it. + * Fails if the list is empty + */ +INLINE_IF_POSSIBLE slist_node * +slist_pop_head(slist_head *head) +{ + slist_node *node; + + node = head->head.next; + head->head.next = head->head.next->next; + + slist_check(head); + + return node; +} + +/* + * Insert a new element after the listed one. + */ +INLINE_IF_POSSIBLE void +slist_insert_after(slist_head *head, slist_node *after, + slist_node *node) +{ + node->next = after->next; + after->next = node; + + slist_check(head); +} + +/* + * Is the list empty? + */ +INLINE_IF_POSSIBLE bool +slist_is_empty(slist_head *head) +{ + slist_check(head); + + return head->head.next == NULL; +} + +/* + * Is there at least one more element in the list? + */ +INLINE_IF_POSSIBLE bool +slist_has_next(slist_head *head, + slist_node *node) +{ + slist_check(head); + + return node->next != NULL; +} +#endif /* ILIST_USE_DEFINITION */ + +#define slist_get_head(type, membername, ptr) \ +( \ + slist_is_empty(ptr) ? NULL : \ + ilist_container(type, membername, (ptr).next) \ +) + +#define slist_get_head_unchecked(type, membername, ptr) \ + ilist_container(type, membername, (ptr)->head.next) + +/* + * 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 slist_foreach(name, ptr) \ + for (name = (ptr)->head.next; name != NULL; 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 delete the current element from the list. Every other + * manipulation can lead to corruption. + */ +#define slist_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.2.5