From c3c80925e780489351c4de210364e55d223f02a8 Mon Sep 17 00:00:00 2001 From: Andres Freund Date: Sun, 6 May 2012 00:26:35 +0200 Subject: [PATCH 1/2] Add embedded list interface Adds a single and a double linked list which can easily embedded into other datastructures and can be used without additional memory allocations. --- src/backend/lib/Makefile | 2 +- src/backend/lib/ilist.c | 123 ++++++++++++ src/include/lib/ilist.h | 468 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 592 insertions(+), 1 deletion(-) 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/ilist.c b/src/backend/lib/ilist.c new file mode 100644 index 0000000..f78ac51 --- /dev/null +++ b/src/backend/lib/ilist.c @@ -0,0 +1,123 @@ +/*------------------------------------------------------------------------- + * + * 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" + +/* + * 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 ILIST_USE_DECLARATION +#endif + +#include "lib/ilist.h" + +#ifndef USE_INLINE +#undef ILIST_USE_DECLARATION +#endif + +/* + * removes a node from a list + * + * Attention: O(n) + */ +void +ilist_s_delete(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) != NULL) + { + 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 delete nonexisting node"); +#endif +} + +#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 /* ILIST_DEBUG */ diff --git a/src/include/lib/ilist.h b/src/include/lib/ilist.h new file mode 100644 index 0000000..ef66d39 --- /dev/null +++ b/src/include/lib/ilist.h @@ -0,0 +1,468 @@ +/*------------------------------------------------------------------------- + * + * 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_head(somelist, &get_value_in_a_list()->list_node); + * ... + * ilist_d_push_head(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_delete(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 + +/* + * 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 USE_INLINE +#define INLINE_IF_POSSIBLE static inline +#define ILIST_USE_DECLARATION +#else +#define INLINE_IF_POSSIBLE +#endif + +/* Functions we want to be inlined if possible */ +#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_head(ilist_d_head *head, ilist_d_node *node); +extern void ilist_d_push_tail(ilist_d_head *head, ilist_d_node *node); +extern void ilist_d_insert_after(unused_attr ilist_d_head *head, + ilist_d_node *after, ilist_d_node *node); +extern void ilist_d_insert_before(unused_attr ilist_d_head *head, + ilist_d_node *before, ilist_d_node *node); +extern void ilist_d_delete(unused_attr ilist_d_head *head, ilist_d_node *node); +extern ilist_d_node* ilist_d_pop_head(ilist_d_head *head); +extern void ilist_d_move_head(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_head(ilist_s_head *head, ilist_s_node *node); +extern ilist_s_node* ilist_s_pop_head(ilist_s_head *head); +extern void ilist_s_insert_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 */ + +/* Functions which are too big to be inline */ + +/* + * deletes a node from a list + * + * Attention: O(n) + */ +extern void ilist_s_delete(ilist_s_head *head, ilist_s_node *node); + +#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*/ + + +/* + * The following function declarations are only used if inlining is supported + * or when included from a file that explicitly declares USE_DECLARATION + */ +#ifdef ILIST_USE_DECLARATION + +/* + * Initialize the head of a list. Previous state will be thrown away without + * any cleanup. + */ +INLINE_IF_POSSIBLE void +ilist_d_init(ilist_d_head *head) +{ + head->head.next = head->head.prev = &head->head; + ilist_d_check(head); +} + +/* + * inserts a node at the beginning of the list + */ +INLINE_IF_POSSIBLE void +ilist_d_push_head(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); +} + + +/* + * inserts a node at the end of the list + */ +INLINE_IF_POSSIBLE void +ilist_d_push_tail(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); +} + + +/* + * insert a node after another *in the same list* + */ +INLINE_IF_POSSIBLE void +ilist_d_insert_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); +} + +/* + * insert a node after another *in the same list* + */ +INLINE_IF_POSSIBLE void +ilist_d_insert_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); +} + + +/* + * deletes a node from a list + */ +INLINE_IF_POSSIBLE void +ilist_d_delete(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); +} + +/* + * deletes the first node from a list or returns NULL + */ +INLINE_IF_POSSIBLE ilist_d_node* +ilist_d_pop_head(ilist_d_head *head) +{ + ilist_d_node* ret; + + if (&head->head == head->head.next) + return NULL; + + ret = head->head.next; + ilist_d_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 +ilist_d_move_head(ilist_d_head *head, ilist_d_node *node) +{ + /* fast path if its already at the head */ + if(&head->head == node) + return; + ilist_d_delete(head, node); + ilist_d_push_head(head, node); + ilist_d_check(head); +} + +/* + * Check whether the passed node is the last element in the list + */ +INLINE_IF_POSSIBLE 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 + */ +INLINE_IF_POSSIBLE bool +ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node) +{ + return node->prev != &head->head; +} + +/* + * Check whether the list is empty. + */ +INLINE_IF_POSSIBLE bool +ilist_d_is_empty(ilist_d_head *head) +{ + return head->head.next == head->head.prev; +} + +#endif /* ILIST_USE_DECLARATION */ + +/* + * 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_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 corrupt data if there is no + * element in the list. + */ +#define ilist_d_head_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_tail(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 delete 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) + + +#ifdef ILIST_USE_DECLARATION + +/* + * Initialize a single linked list element. + */ +INLINE_IF_POSSIBLE void +ilist_s_init(ilist_s_head *head) +{ + head->head.next = NULL; + ilist_s_check(head); +} + +INLINE_IF_POSSIBLE void +ilist_s_push_head(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 + */ +INLINE_IF_POSSIBLE ilist_s_node* +ilist_s_pop_head(ilist_s_head *head) +{ + ilist_s_node* node = head->head.next; + head->head.next = head->head.next->next; + ilist_s_check(head); + return node; +} + +INLINE_IF_POSSIBLE void +ilist_s_insert_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); +} + + +INLINE_IF_POSSIBLE +bool ilist_s_is_empty(ilist_s_head *head) +{ + return head->head.next == NULL; +} + +INLINE_IF_POSSIBLE bool +ilist_s_has_next(unused_attr ilist_s_head* head, + ilist_s_node *node) +{ + return node->next != NULL; +} + +#endif /* ILIST_USE_DECLARATION */ + +#define ilist_s_head(type, membername, ptr) \ +( \ + ilist_s_is_empty(ptr) ? \ + ilist_container(type, membername, (ptr).next) \ + : NULL \ +) + +#define ilist_s_head_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) + +/* + * if we defined ILIST_USE_DECLARATION undef it again, its not interesting + * outside this file + */ +#ifdef USE_INLINE +#undef ILIST_USE_DECLARATION +#endif + +#endif /* ILIST_H */ -- 1.7.10.rc3.3.g19a6c.dirty