ilist.patch
application/octet-stream
Patch
Same data as JSON:
GET /api/v1/attachments/:id/patch
the parsed metadata as JSON — format, series position, per-file stats; never the diff bytes.
API reference →
Format: unified
| File | + | − |
|---|---|---|
| src/backend/lib/Makefile | 0 | 0 |
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,17 **** subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
! OBJS = dllist.o stringinfo.o
include $(top_srcdir)/src/backend/common.mk
--- 12,17 ----
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
! OBJS = dllist.o stringinfo.o ilist.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/REnew file mode 100644
index 0000000..3a3d8a8
*** /dev/null
--- b/src/backend/lib/README.ilist
***************
*** 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.new file mode 100644
index 0000000..239c538
*** /dev/null
--- b/src/backend/lib/ilist.c
***************
*** 0 ****
--- 1,117 ----
+ /*-------------------------------------------------------------------------
+ *
+ * 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 their definitions.
+ */
+ #ifdef USE_INLINE
+ #include "lib/ilist.h"
+ #else /* USE_INLINE */
+ #define ILIST_USE_DEFINITION
+ #include "lib/ilist.h"
+ #undef ILIST_USE_DEFINITION
+ #endif
+
+ /*
+ * 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/inew file mode 100644
index 0000000..27c5dba
*** /dev/null
--- b/src/include/lib/ilist.h
***************
*** 0 ****
--- 1,453 ----
+ /*-------------------------------------------------------------------------
+ *
+ * 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
+
+ /*
+ * 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.
+ *
+ * FIXME -- this should be part of c.h.
+ */
+ #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 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_check(unused_attr Dlist_head *head);
+ 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(unused_attr Dlist_head *head,
+ Dlist_node *after, Dlist_node *node);
+ extern void Dlist_insert_before(unused_attr Dlist_head *head,
+ Dlist_node *before, Dlist_node *node);
+ extern void Dlist_delete(unused_attr 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(unused_attr Slist_head *head,
+ Slist_node *after, Slist_node *node);
+ extern bool Slist_is_empty(Slist_head *head);
+ extern bool Slist_has_next(unused_attr 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
+ #define Dlist_check(head)
+ #define Slist_check(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(unused_attr 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(unused_attr 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(unused_attr 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.prev;
+ }
+ #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_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_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_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(unused_attr 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)
+ {
+ return head->head.next == NULL;
+ }
+
+ /*
+ * Is there at least one more element in the list?
+ */
+ INLINE_IF_POSSIBLE bool
+ Slist_has_next(unused_attr Slist_head *head,
+ Slist_node *node)
+ {
+ 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)
+
+ #define Slist_foreach(name, ptr) \
+ for (name = (ptr)->head.next; name != NULL; name = name->next)
+
+ #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)
+
+ /*
+ * Get rid of ILIST_USE_DEFINITION; it's not interesting outside this file.
+ */
+ #ifdef USE_INLINE
+ #undef ILIST_USE_DEFINITION
+ #endif
+
+ #endif /* ILIST_H */
diff --git a/src/tools/pgindenindex a831a1e..0aa3e3c 100644