From 2e9d955fbb625004061509a62ecca83fde68d027 Mon Sep 17 00:00:00 2001 From: Andres Freund 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 + +/* + * 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