rbtree-rewrite.patch
text/x-patch
Filename: rbtree-rewrite.patch
Type: text/x-patch
Part: 0
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: context
| File | + | − |
|---|---|---|
| src/backend/access/gin/ginbtree.c | 8 | 6 |
| src/backend/access/gin/ginbulk.c | 77 | 55 |
| src/backend/access/gin/ginentrypage.c | 3 | 1 |
| src/backend/access/gin/ginfast.c | 2 | 0 |
| src/backend/access/gin/gininsert.c | 3 | 0 |
| src/backend/utils/misc/rbtree.c | 263 | 197 |
| src/include/access/gin.h | 2 | 2 |
| src/include/utils/rbtree.h | 43 | 23 |
Index: src/backend/access/gin/ginbtree.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/access/gin/ginbtree.c,v
retrieving revision 1.15
diff -c -r1.15 ginbtree.c
*** src/backend/access/gin/ginbtree.c 2 Jan 2010 16:57:33 -0000 1.15
--- src/backend/access/gin/ginbtree.c 1 Aug 2010 01:44:08 -0000
***************
*** 267,272 ****
--- 267,274 ----
/*
* Insert value (stored in GinBtree) to tree described by stack
+ *
+ * NB: the passed-in stack is freed, as though by freeGinBtreeStack.
*/
void
ginInsertValue(GinBtree btree, GinBtreeStack *stack)
***************
*** 308,317 ****
PageSetTLI(page, ThisTimeLineID);
}
! UnlockReleaseBuffer(stack->buffer);
END_CRIT_SECTION();
! freeGinBtreeStack(stack->parent);
return;
}
else
--- 310,320 ----
PageSetTLI(page, ThisTimeLineID);
}
! LockBuffer(stack->buffer, GIN_UNLOCK);
END_CRIT_SECTION();
! freeGinBtreeStack(stack);
!
return;
}
else
***************
*** 325,331 ****
*/
newlpage = btree->splitPage(btree, stack->buffer, rbuffer, stack->off, &rdata);
-
((ginxlogSplit *) (rdata->data))->rootBlkno = rootBlkno;
parent = stack->parent;
--- 328,333 ----
***************
*** 341,347 ****
((ginxlogSplit *) (rdata->data))->isRootSplit = TRUE;
((ginxlogSplit *) (rdata->data))->rrlink = InvalidBlockNumber;
-
page = BufferGetPage(stack->buffer);
lpage = BufferGetPage(lbuffer);
rpage = BufferGetPage(rbuffer);
--- 343,348 ----
***************
*** 375,384 ****
UnlockReleaseBuffer(rbuffer);
UnlockReleaseBuffer(lbuffer);
! UnlockReleaseBuffer(stack->buffer);
!
END_CRIT_SECTION();
return;
}
else
--- 376,386 ----
UnlockReleaseBuffer(rbuffer);
UnlockReleaseBuffer(lbuffer);
! LockBuffer(stack->buffer, GIN_UNLOCK);
END_CRIT_SECTION();
+ freeGinBtreeStack(stack);
+
return;
}
else
Index: src/backend/access/gin/ginbulk.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/access/gin/ginbulk.c,v
retrieving revision 1.19
diff -c -r1.19 ginbulk.c
*** src/backend/access/gin/ginbulk.c 26 Feb 2010 02:00:33 -0000 1.19
--- src/backend/access/gin/ginbulk.c 1 Aug 2010 01:44:08 -0000
***************
*** 19,35 ****
#include "utils/memutils.h"
! #define DEF_NENTRY 2048
! #define DEF_NPTR 4
- static void *
- ginAppendData(void *old, void *new, void *arg)
- {
- EntryAccumulator *eo = (EntryAccumulator *) old,
- *en = (EntryAccumulator *) new;
BuildAccumulator *accum = (BuildAccumulator *) arg;
if (eo->number >= eo->length)
{
accum->allocatedMemory -= GetMemoryChunkSpace(eo->list);
--- 19,39 ----
#include "utils/memutils.h"
! #define DEF_NENTRY 2048 /* EntryAccumulator allocation quantum */
! #define DEF_NPTR 5 /* ItemPointer initial allocation quantum */
+ /* Combiner function for rbtree.c */
+ static void
+ ginCombineData(RBNode *existing, const RBNode *newdata, void *arg)
+ {
+ EntryAccumulator *eo = (EntryAccumulator *) existing;
+ const EntryAccumulator *en = (const EntryAccumulator *) newdata;
BuildAccumulator *accum = (BuildAccumulator *) arg;
+ /*
+ * Note this code assumes that newdata contains only one itempointer.
+ */
if (eo->number >= eo->length)
{
accum->allocatedMemory -= GetMemoryChunkSpace(eo->list);
***************
*** 53,81 ****
eo->list[eo->number] = en->list[0];
eo->number++;
-
- return old;
}
static int
! cmpEntryAccumulator(const void *a, const void *b, void *arg)
{
! EntryAccumulator *ea = (EntryAccumulator *) a;
! EntryAccumulator *eb = (EntryAccumulator *) b;
BuildAccumulator *accum = (BuildAccumulator *) arg;
return compareAttEntries(accum->ginstate, ea->attnum, ea->value,
eb->attnum, eb->value);
}
void
ginInitBA(BuildAccumulator *accum)
{
accum->allocatedMemory = 0;
accum->entryallocator = NULL;
! accum->tree = rb_create(cmpEntryAccumulator, ginAppendData, NULL, accum);
! accum->iterator = NULL;
! accum->tmpList = NULL;
}
/*
--- 57,113 ----
eo->list[eo->number] = en->list[0];
eo->number++;
}
+ /* Comparator function for rbtree.c */
static int
! cmpEntryAccumulator(const RBNode *a, const RBNode *b, void *arg)
{
! const EntryAccumulator *ea = (const EntryAccumulator *) a;
! const EntryAccumulator *eb = (const EntryAccumulator *) b;
BuildAccumulator *accum = (BuildAccumulator *) arg;
return compareAttEntries(accum->ginstate, ea->attnum, ea->value,
eb->attnum, eb->value);
}
+ /* Allocator function for rbtree.c */
+ static RBNode *
+ ginAllocEntryAccumulator(void *arg)
+ {
+ BuildAccumulator *accum = (BuildAccumulator *) arg;
+ EntryAccumulator *ea;
+
+ /*
+ * Allocate memory by rather big chunks to decrease overhead. We have
+ * no need to reclaim RBNodes individually, so this costs nothing.
+ */
+ if (accum->entryallocator == NULL || accum->length >= DEF_NENTRY)
+ {
+ accum->entryallocator = palloc(sizeof(EntryAccumulator) * DEF_NENTRY);
+ accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
+ accum->length = 0;
+ }
+
+ /* Allocate new RBNode from current chunk */
+ ea = accum->entryallocator + accum->length;
+ accum->length++;
+
+ return (RBNode *) ea;
+ }
+
void
ginInitBA(BuildAccumulator *accum)
{
accum->allocatedMemory = 0;
+ accum->length = 0;
accum->entryallocator = NULL;
! accum->tree = rb_create(sizeof(EntryAccumulator),
! cmpEntryAccumulator,
! ginCombineData,
! ginAllocEntryAccumulator,
! NULL, /* no freefunc needed */
! (void *) accum);
}
/*
***************
*** 104,158 ****
static void
ginInsertEntry(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum entry)
{
! EntryAccumulator *key,
! *ea;
/*
! * Allocate memory by rather big chunk to decrease overhead, we don't keep
! * pointer to previously allocated chunks because they will free by
! * MemoryContextReset() call.
*/
! if (accum->entryallocator == NULL || accum->length >= DEF_NENTRY)
! {
! accum->entryallocator = palloc(sizeof(EntryAccumulator) * DEF_NENTRY);
! accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
! accum->length = 0;
! }
! /* "Allocate" new key in chunk */
! key = accum->entryallocator + accum->length;
! accum->length++;
! key->attnum = attnum;
! key->value = entry;
! /* To prevent multiple palloc/pfree cycles, we reuse array */
! if (accum->tmpList == NULL)
! accum->tmpList =
! (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
! key->list = accum->tmpList;
! key->list[0] = *heapptr;
!
! ea = rb_insert(accum->tree, key);
!
! if (ea == NULL)
{
/*
! * The key has been inserted, so continue initialization.
*/
! key->value = getDatumCopy(accum, attnum, entry);
! key->length = DEF_NPTR;
! key->number = 1;
! key->shouldSort = FALSE;
! accum->allocatedMemory += GetMemoryChunkSpace(key->list);
! accum->tmpList = NULL;
}
else
{
/*
! * The key has been appended, so "free" allocated key by decrementing
! * chunk's counter.
*/
- accum->length--;
}
}
--- 136,176 ----
static void
ginInsertEntry(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum entry)
{
! EntryAccumulator key;
! EntryAccumulator *ea;
! bool isNew;
/*
! * For the moment, fill only the fields of key that will be looked at
! * by cmpEntryAccumulator or ginCombineData.
*/
! key.attnum = attnum;
! key.value = entry;
! /* temporarily set up single-entry itempointer list */
! key.list = heapptr;
! ea = (EntryAccumulator *) rb_insert(accum->tree, (RBNode *) &key, &isNew);
! if (isNew)
{
/*
! * Finish initializing new tree entry, including making permanent
! * copies of the datum and itempointer.
*/
! ea->value = getDatumCopy(accum, attnum, entry);
! ea->length = DEF_NPTR;
! ea->number = 1;
! ea->shouldSort = FALSE;
! ea->list =
! (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR);
! ea->list[0] = *heapptr;
! accum->allocatedMemory += GetMemoryChunkSpace(ea->list);
}
else
{
/*
! * ginCombineData did everything needed.
*/
}
}
***************
*** 214,229 ****
return res;
}
ItemPointerData *
ginGetEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *value, uint32 *n)
{
EntryAccumulator *entry;
ItemPointerData *list;
! if (accum->iterator == NULL)
! accum->iterator = rb_begin_iterate(accum->tree, LeftRightWalk);
!
! entry = rb_iterate(accum->iterator);
if (entry == NULL)
return NULL;
--- 232,251 ----
return res;
}
+ /* Prepare to read out the rbtree contents using ginGetEntry */
+ void
+ ginBeginBAScan(BuildAccumulator *accum)
+ {
+ rb_begin_iterate(accum->tree, LeftRightWalk);
+ }
+
ItemPointerData *
ginGetEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *value, uint32 *n)
{
EntryAccumulator *entry;
ItemPointerData *list;
! entry = (EntryAccumulator *) rb_iterate(accum->tree);
if (entry == NULL)
return NULL;
Index: src/backend/access/gin/ginentrypage.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/access/gin/ginentrypage.c,v
retrieving revision 1.24
diff -c -r1.24 ginentrypage.c
*** src/backend/access/gin/ginentrypage.c 26 Feb 2010 02:00:33 -0000 1.24
--- src/backend/access/gin/ginentrypage.c 1 Aug 2010 01:44:08 -0000
***************
*** 615,621 ****
}
/*
! * return newly allocate rightmost tuple
*/
IndexTuple
ginPageGetLinkItup(Buffer buf)
--- 615,621 ----
}
/*
! * return newly allocated rightmost tuple
*/
IndexTuple
ginPageGetLinkItup(Buffer buf)
***************
*** 646,655 ****
--- 646,657 ----
itup = ginPageGetLinkItup(lbuf);
if (PageAddItem(page, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
elog(ERROR, "failed to add item to index root page");
+ pfree(itup);
itup = ginPageGetLinkItup(rbuf);
if (PageAddItem(page, (Item) itup, IndexTupleSize(itup), InvalidOffsetNumber, false, false) == InvalidOffsetNumber)
elog(ERROR, "failed to add item to index root page");
+ pfree(itup);
}
void
Index: src/backend/access/gin/ginfast.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/access/gin/ginfast.c,v
retrieving revision 1.7
diff -c -r1.7 ginfast.c
*** src/backend/access/gin/ginfast.c 11 Feb 2010 14:29:50 -0000 1.7
--- src/backend/access/gin/ginfast.c 1 Aug 2010 01:44:08 -0000
***************
*** 786,791 ****
--- 786,792 ----
* significant amount of time - so, run it without locking pending
* list.
*/
+ ginBeginBAScan(&accum);
while ((list = ginGetEntry(&accum, &attnum, &entry, &nlist)) != NULL)
{
ginEntryInsert(index, ginstate, attnum, entry, list, nlist, FALSE);
***************
*** 820,825 ****
--- 821,827 ----
ginInitBA(&accum);
processPendingPage(&accum, &datums, page, maxoff + 1);
+ ginBeginBAScan(&accum);
while ((list = ginGetEntry(&accum, &attnum, &entry, &nlist)) != NULL)
ginEntryInsert(index, ginstate, attnum, entry, list, nlist, FALSE);
}
Index: src/backend/access/gin/gininsert.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/access/gin/gininsert.c,v
retrieving revision 1.26
diff -c -r1.26 gininsert.c
*** src/backend/access/gin/gininsert.c 11 Feb 2010 14:29:50 -0000 1.26
--- src/backend/access/gin/gininsert.c 1 Aug 2010 01:44:08 -0000
***************
*** 176,181 ****
--- 176,182 ----
gdi = prepareScanPostingTree(index, rootPostingTree, FALSE);
gdi->btree.isBuild = isBuild;
insertItemPointer(gdi, items, nitem);
+ pfree(gdi);
return;
}
***************
*** 254,259 ****
--- 255,261 ----
uint32 nlist;
OffsetNumber attnum;
+ ginBeginBAScan(&buildstate->accum);
while ((list = ginGetEntry(&buildstate->accum, &attnum, &entry, &nlist)) != NULL)
{
/* there could be many entries, so be willing to abort here */
***************
*** 360,365 ****
--- 362,368 ----
/* dump remaining entries to the index */
oldCtx = MemoryContextSwitchTo(buildstate.tmpCtx);
+ ginBeginBAScan(&buildstate.accum);
while ((list = ginGetEntry(&buildstate.accum, &attnum, &entry, &nlist)) != NULL)
{
/* there could be many entries, so be willing to abort here */
Index: src/backend/utils/misc/rbtree.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/utils/misc/rbtree.c,v
retrieving revision 1.3
diff -c -r1.3 rbtree.c
*** src/backend/utils/misc/rbtree.c 26 Feb 2010 02:01:14 -0000 1.3
--- src/backend/utils/misc/rbtree.c 1 Aug 2010 01:44:08 -0000
***************
*** 17,23 ****
* longest path from root to leaf is only about twice as long as the shortest,
* so lookups are guaranteed to run in O(lg n) time.
*
! * Copyright (c) 1996-2009, PostgreSQL Global Development Group
*
* IDENTIFICATION
* $PostgreSQL: pgsql/src/backend/utils/misc/rbtree.c,v 1.3 2010/02/26 02:01:14 momjian Exp $
--- 17,23 ----
* longest path from root to leaf is only about twice as long as the shortest,
* so lookups are guaranteed to run in O(lg n) time.
*
! * Copyright (c) 2009-2010, PostgreSQL Global Development Group
*
* IDENTIFICATION
* $PostgreSQL: pgsql/src/backend/utils/misc/rbtree.c,v 1.3 2010/02/26 02:01:14 momjian Exp $
***************
*** 28,39 ****
#include "utils/rbtree.h"
- /**********************************************************************
- * Declarations *
- **********************************************************************/
/*
! * Values for RBNode->iteratorState
*/
#define InitialState (0)
#define FirstStepDone (1)
--- 28,39 ----
#include "utils/rbtree.h"
/*
! * Values of RBNode.iteratorState
! *
! * Note that iteratorState has an undefined value except in nodes that are
! * currently being visited by an active iteration.
*/
#define InitialState (0)
#define FirstStepDone (1)
***************
*** 41,121 ****
#define ThirdStepDone (3)
/*
! * Colors of node
*/
#define RBBLACK (0)
#define RBRED (1)
! typedef struct RBNode
! {
! uint32 iteratorState:2,
! color: 1,
! unused:29;
! struct RBNode *left;
! struct RBNode *right;
! struct RBNode *parent;
! void *data;
! } RBNode;
!
struct RBTree
{
! RBNode *root;
rb_comparator comparator;
! rb_appendator appendator;
rb_freefunc freefunc;
void *arg;
};
- struct RBTreeIterator
- {
- RBNode *node;
- void *(*iterate) (RBTreeIterator *iterator);
- };
-
/*
* all leafs are sentinels, use customized NIL name to prevent
! * collision with sytem-wide NIL which is actually NULL
*/
! #define RBNIL &sentinel
! RBNode sentinel = {InitialState, RBBLACK, 0, RBNIL, RBNIL, NULL, NULL};
- /**********************************************************************
- * Create *
- **********************************************************************/
RBTree *
! rb_create(rb_comparator comparator, rb_appendator appendator,
! rb_freefunc freefunc, void *arg)
{
! RBTree *tree = palloc(sizeof(RBTree));
tree->root = RBNIL;
tree->comparator = comparator;
! tree->appendator = appendator;
tree->freefunc = freefunc;
-
tree->arg = arg;
return tree;
}
/**********************************************************************
* Search *
**********************************************************************/
! void *
! rb_find(RBTree *rb, void *data)
{
RBNode *node = rb->root;
- int cmp;
while (node != RBNIL)
{
! cmp = rb->comparator(data, node->data, rb->arg);
if (cmp == 0)
! return node->data;
else if (cmp < 0)
node = node->left;
else
--- 41,170 ----
#define ThirdStepDone (3)
/*
! * Colors of nodes (values of RBNode.color)
*/
#define RBBLACK (0)
#define RBRED (1)
! /*
! * RBTree control structure
! */
struct RBTree
{
! RBNode *root; /* root node, or RBNIL if tree is empty */
!
! /* Iteration state */
! RBNode *cur; /* current iteration node */
! RBNode *(*iterate) (RBTree *rb);
!
! /* Remaining fields are constant after rb_create */
!
! Size node_size; /* actual size of tree nodes */
! /* The caller-supplied manipulation functions */
rb_comparator comparator;
! rb_combiner combiner;
! rb_allocfunc allocfunc;
rb_freefunc freefunc;
+ /* Passthrough arg passed to all manipulation functions */
void *arg;
};
/*
* all leafs are sentinels, use customized NIL name to prevent
! * collision with system-wide constant NIL which is actually NULL
*/
! #define RBNIL (&sentinel)
! static RBNode sentinel = {InitialState, RBBLACK, RBNIL, RBNIL, NULL};
+ /*
+ * rb_create: create an empty RBTree
+ *
+ * Arguments are:
+ * node_size: actual size of tree nodes (> sizeof(RBNode))
+ * The manipulation functions:
+ * comparator: compare two RBNodes for less/equal/greater
+ * combiner: merge an existing tree entry with a new one
+ * allocfunc: allocate a new RBNode
+ * freefunc: free an old RBNode
+ * arg: passthrough pointer that will be passed to the manipulation functions
+ *
+ * Note that the combiner's righthand argument will be a "proposed" tree node,
+ * ie the input to rb_insert, in which the RBNode fields themselves aren't
+ * valid. Similarly, either input to the comparator may be a "proposed" node.
+ * This shouldn't matter since the functions aren't supposed to look at the
+ * RBNode fields, only the extra fields of the struct the RBNode is embedded
+ * in.
+ *
+ * The freefunc should just be pfree or equivalent; it should NOT attempt
+ * to free any subsidiary data, because the node passed to it may not contain
+ * valid data! freefunc can be NULL if caller doesn't require retail
+ * space reclamation.
+ *
+ * The RBTree node is palloc'd in the caller's memory context. Note that
+ * all contents of the tree are actually allocated by the caller, not here.
+ *
+ * Since tree contents are managed by the caller, there is currently not
+ * an explicit "destroy" operation; typically a tree would be freed by
+ * resetting or deleting the memory context it's stored in. You can pfree
+ * the RBTree node if you feel the urge.
+ */
RBTree *
! rb_create(Size node_size,
! rb_comparator comparator,
! rb_combiner combiner,
! rb_allocfunc allocfunc,
! rb_freefunc freefunc,
! void *arg)
{
! RBTree *tree = (RBTree *) palloc(sizeof(RBTree));
!
! Assert(node_size > sizeof(RBNode));
tree->root = RBNIL;
+ tree->cur = RBNIL;
+ tree->iterate = NULL;
+ tree->node_size = node_size;
tree->comparator = comparator;
! tree->combiner = combiner;
! tree->allocfunc = allocfunc;
tree->freefunc = freefunc;
tree->arg = arg;
return tree;
}
+ /* Copy the additional data fields from one RBNode to another */
+ static inline void
+ rb_copy_data(RBTree *rb, RBNode *dest, const RBNode *src)
+ {
+ memcpy(dest + 1, src + 1, rb->node_size - sizeof(RBNode));
+ }
+
/**********************************************************************
* Search *
**********************************************************************/
! /*
! * rb_find: search for a value in an RBTree
! *
! * data represents the value to try to find. Its RBNode fields need not
! * be valid, it's the extra data in the larger struct that is of interest.
! *
! * Returns the matching tree entry, or NULL if no match is found.
! */
! RBNode *
! rb_find(RBTree *rb, const RBNode *data)
{
RBNode *node = rb->root;
while (node != RBNIL)
{
! int cmp = rb->comparator(data, node, rb->arg);
if (cmp == 0)
! return node;
else if (cmp < 0)
node = node->left;
else
***************
*** 125,130 ****
--- 174,205 ----
return NULL;
}
+ /*
+ * rb_leftmost: fetch the leftmost (smallest-valued) tree node.
+ * Returns NULL if tree is empty.
+ *
+ * Note: in the original implementation this included an unlink step, but
+ * that's a bit awkward. Just call rb_delete on the result if that's what
+ * you want.
+ */
+ RBNode *
+ rb_leftmost(RBTree *rb)
+ {
+ RBNode *node = rb->root;
+ RBNode *leftmost = rb->root;
+
+ while (node != RBNIL)
+ {
+ leftmost = node;
+ node = node->left;
+ }
+
+ if (leftmost != RBNIL)
+ return leftmost;
+
+ return NULL;
+ }
+
/**********************************************************************
* Insertion *
**********************************************************************/
***************
*** 309,321 ****
}
/*
! * Allocate node for data and insert in tree.
*
! * Return old data (or result of appendator method) if it exists and NULL
! * otherwise.
*/
! void *
! rb_insert(RBTree *rb, void *data)
{
RBNode *current,
*parent,
--- 384,407 ----
}
/*
! * rb_insert: insert a new value into the tree.
*
! * data represents the value to insert. Its RBNode fields need not
! * be valid, it's the extra data in the larger struct that is of interest.
! *
! * If the value represented by "data" is not present in the tree, then
! * we copy "data" into a new tree entry and return that node, setting *isNew
! * to true.
! *
! * If the value represented by "data" is already present, then we call the
! * combiner function to merge data into the existing node, and return the
! * existing node, setting *isNew to false.
! *
! * "data" is unmodified in either case; it's typically just a local
! * variable in the caller.
*/
! RBNode *
! rb_insert(RBTree *rb, const RBNode *data, bool *isNew)
{
RBNode *current,
*parent,
***************
*** 325,367 ****
/* find where node belongs */
current = rb->root;
parent = NULL;
! cmp = 0;
while (current != RBNIL)
{
! cmp = rb->comparator(data, current->data, rb->arg);
if (cmp == 0)
{
/*
! * Found node with given key. If appendator method is provided,
! * call it to join old and new data; else, new data replaces old
! * data.
*/
! if (rb->appendator)
! {
! current->data = rb->appendator(current->data, data, rb->arg);
! return current->data;
! }
! else
! {
! void *old = current->data;
!
! current->data = data;
! return old;
! }
}
parent = current;
current = (cmp < 0) ? current->left : current->right;
}
! /* setup new node in tree */
! x = palloc(sizeof(RBNode));
! x->data = data;
! x->parent = parent;
! x->left = RBNIL;
! x->right = RBNIL;
! x->color = RBRED;
x->iteratorState = InitialState;
/* insert node in tree */
if (parent)
--- 411,447 ----
/* find where node belongs */
current = rb->root;
parent = NULL;
! cmp = 0; /* just to prevent compiler warning */
!
while (current != RBNIL)
{
! cmp = rb->comparator(data, current, rb->arg);
if (cmp == 0)
{
/*
! * Found node with given key. Apply combiner.
*/
! rb->combiner(current, data, rb->arg);
! *isNew = false;
! return current;
}
parent = current;
current = (cmp < 0) ? current->left : current->right;
}
! /*
! * Value is not present, so create a new node containing data.
! */
! *isNew = true;
!
! x = rb->allocfunc(rb->arg);
x->iteratorState = InitialState;
+ x->color = RBRED;
+ x->left = RBNIL;
+ x->right = RBNIL;
+ x->parent = parent;
+ rb_copy_data(rb, x, data);
/* insert node in tree */
if (parent)
***************
*** 377,383 ****
}
rb_insert_fixup(rb, x);
! return NULL;
}
/**********************************************************************
--- 457,464 ----
}
rb_insert_fixup(rb, x);
!
! return x;
}
/**********************************************************************
***************
*** 533,543 ****
}
/*
! * If we removed the tree successor of z rather than z itself, then attach
* the data for the removed node to the one we were supposed to remove.
*/
if (y != z)
! z->data = y->data;
/*
* Removing a black node might make some paths from root to leaf contain
--- 614,624 ----
}
/*
! * If we removed the tree successor of z rather than z itself, then move
* the data for the removed node to the one we were supposed to remove.
*/
if (y != z)
! rb_copy_data(rb, z, y);
/*
* Removing a black node might make some paths from root to leaf contain
***************
*** 546,805 ****
if (y->color == RBBLACK)
rb_delete_fixup(rb, x);
! pfree(y);
! }
!
! extern void
! rb_delete(RBTree *rb, void *data)
! {
! RBNode *node = rb->root;
! int cmp;
!
! while (node != RBNIL)
! {
! cmp = rb->comparator(data, node->data, rb->arg);
!
! if (cmp == 0)
! {
! /* found node to delete */
! if (rb->freefunc)
! rb->freefunc (node->data);
!
! node->data = NULL;
! rb_delete_node(rb, node);
! return;
! }
! else if (cmp < 0)
! node = node->left;
! else
! node = node->right;
! }
}
/*
! * Return data on left most node and delete
! * that node
*/
! extern void *
! rb_leftmost(RBTree *rb)
{
! RBNode *node = rb->root;
! RBNode *leftmost = rb->root;
! void *res = NULL;
!
! while (node != RBNIL)
! {
! leftmost = node;
! node = node->left;
! }
!
! if (leftmost != RBNIL)
! {
! res = leftmost->data;
! leftmost->data = NULL;
! rb_delete_node(rb, leftmost);
! }
!
! return res;
}
/**********************************************************************
* Traverse *
**********************************************************************/
! static void *
! rb_next_node(RBTreeIterator *iterator, RBNode *node)
! {
! node->iteratorState = InitialState;
! iterator->node = node;
! return iterator->iterate(iterator);
! }
! static void *
! rb_left_right_iterator(RBTreeIterator *iterator)
{
! RBNode *node = iterator->node;
switch (node->iteratorState)
{
case InitialState:
if (node->left != RBNIL)
{
node->iteratorState = FirstStepDone;
! return rb_next_node(iterator, node->left);
}
case FirstStepDone:
node->iteratorState = SecondStepDone;
! return node->data;
case SecondStepDone:
if (node->right != RBNIL)
{
node->iteratorState = ThirdStepDone;
! return rb_next_node(iterator, node->right);
}
case ThirdStepDone:
if (node->parent)
! {
! iterator->node = node->parent;
! return iterator->iterate(iterator);
! }
break;
default:
! elog(ERROR, "Unknow node state: %d", node->iteratorState);
}
return NULL;
}
! static void *
! rb_right_left_iterator(RBTreeIterator *iterator)
{
! RBNode *node = iterator->node;
switch (node->iteratorState)
{
case InitialState:
if (node->right != RBNIL)
{
node->iteratorState = FirstStepDone;
! return rb_next_node(iterator, node->right);
}
case FirstStepDone:
node->iteratorState = SecondStepDone;
! return node->data;
case SecondStepDone:
if (node->left != RBNIL)
{
node->iteratorState = ThirdStepDone;
! return rb_next_node(iterator, node->left);
}
case ThirdStepDone:
if (node->parent)
! {
! iterator->node = node->parent;
! return iterator->iterate(iterator);
! }
break;
default:
! elog(ERROR, "Unknow node state: %d", node->iteratorState);
}
return NULL;
}
! static void *
! rb_direct_iterator(RBTreeIterator *iterator)
{
! RBNode *node = iterator->node;
switch (node->iteratorState)
{
case InitialState:
node->iteratorState = FirstStepDone;
! return node->data;
case FirstStepDone:
if (node->left != RBNIL)
{
node->iteratorState = SecondStepDone;
! return rb_next_node(iterator, node->left);
}
case SecondStepDone:
if (node->right != RBNIL)
{
node->iteratorState = ThirdStepDone;
! return rb_next_node(iterator, node->right);
}
case ThirdStepDone:
if (node->parent)
! {
! iterator->node = node->parent;
! return iterator->iterate(iterator);
! }
break;
default:
! elog(ERROR, "Unknow node state: %d", node->iteratorState);
}
return NULL;
}
! static void *
! rb_inverted_iterator(RBTreeIterator *iterator)
{
! RBNode *node = iterator->node;
switch (node->iteratorState)
{
case InitialState:
if (node->left != RBNIL)
{
node->iteratorState = FirstStepDone;
! return rb_next_node(iterator, node->left);
}
case FirstStepDone:
if (node->right != RBNIL)
{
node->iteratorState = SecondStepDone;
! return rb_next_node(iterator, node->right);
}
case SecondStepDone:
node->iteratorState = ThirdStepDone;
! return node->data;
case ThirdStepDone:
if (node->parent)
! {
! iterator->node = node->parent;
! return iterator->iterate(iterator);
! }
break;
default:
! elog(ERROR, "Unknow node state: %d", node->iteratorState);
}
return NULL;
}
! RBTreeIterator *
rb_begin_iterate(RBTree *rb, RBOrderControl ctrl)
{
! RBTreeIterator *iterator = palloc(sizeof(RBTreeIterator));
!
! iterator->node = rb->root;
! if (iterator->node != RBNIL)
! iterator->node->iteratorState = InitialState;
switch (ctrl)
{
case LeftRightWalk: /* visit left, then self, then right */
! iterator->iterate = rb_left_right_iterator;
break;
case RightLeftWalk: /* visit right, then self, then left */
! iterator->iterate = rb_right_left_iterator;
break;
case DirectWalk: /* visit self, then left, then right */
! iterator->iterate = rb_direct_iterator;
break;
case InvertedWalk: /* visit left, then right, then self */
! iterator->iterate = rb_inverted_iterator;
break;
default:
! elog(ERROR, "Unknown iterator order: %d", ctrl);
}
-
- return iterator;
}
! void *
! rb_iterate(RBTreeIterator *iterator)
{
! if (iterator->node == RBNIL)
return NULL;
! return iterator->iterate(iterator);
! }
!
! void
! rb_free_iterator(RBTreeIterator *iterator)
! {
! pfree(iterator);
}
--- 627,871 ----
if (y->color == RBBLACK)
rb_delete_fixup(rb, x);
! /* Now we can recycle the y node */
! if (rb->freefunc)
! rb->freefunc(y, rb->arg);
}
/*
! * rb_delete: remove the given tree entry
! *
! * "node" must have previously been found via rb_find or rb_leftmost.
! * It is caller's responsibility to free any subsidiary data attached
! * to the node before calling rb_delete. (Do *not* try to push that
! * responsibility off to the freefunc, as some other physical node
! * may be the one actually freed!)
*/
! void
! rb_delete(RBTree *rb, RBNode *node)
{
! rb_delete_node(rb, node);
}
/**********************************************************************
* Traverse *
**********************************************************************/
! /*
! * The iterator routines were originally coded in tail-recursion style,
! * which is nice to look at, but is trouble if your compiler isn't smart
! * enough to optimize it. Now we just use looping.
! */
! #define descend(next_node) \
! do { \
! (next_node)->iteratorState = InitialState; \
! node = rb->cur = (next_node); \
! goto restart; \
! } while (0)
!
! #define ascend(next_node) \
! do { \
! node = rb->cur = (next_node); \
! goto restart; \
! } while (0)
!
! static RBNode *
! rb_left_right_iterator(RBTree *rb)
{
! RBNode *node = rb->cur;
+ restart:
switch (node->iteratorState)
{
case InitialState:
if (node->left != RBNIL)
{
node->iteratorState = FirstStepDone;
! descend(node->left);
}
+ /* FALL THROUGH */
case FirstStepDone:
node->iteratorState = SecondStepDone;
! return node;
case SecondStepDone:
if (node->right != RBNIL)
{
node->iteratorState = ThirdStepDone;
! descend(node->right);
}
+ /* FALL THROUGH */
case ThirdStepDone:
if (node->parent)
! ascend(node->parent);
break;
default:
! elog(ERROR, "unrecognized rbtree node state: %d",
! node->iteratorState);
}
return NULL;
}
! static RBNode *
! rb_right_left_iterator(RBTree *rb)
{
! RBNode *node = rb->cur;
+ restart:
switch (node->iteratorState)
{
case InitialState:
if (node->right != RBNIL)
{
node->iteratorState = FirstStepDone;
! descend(node->right);
}
+ /* FALL THROUGH */
case FirstStepDone:
node->iteratorState = SecondStepDone;
! return node;
case SecondStepDone:
if (node->left != RBNIL)
{
node->iteratorState = ThirdStepDone;
! descend(node->left);
}
+ /* FALL THROUGH */
case ThirdStepDone:
if (node->parent)
! ascend(node->parent);
break;
default:
! elog(ERROR, "unrecognized rbtree node state: %d",
! node->iteratorState);
}
return NULL;
}
! static RBNode *
! rb_direct_iterator(RBTree *rb)
{
! RBNode *node = rb->cur;
+ restart:
switch (node->iteratorState)
{
case InitialState:
node->iteratorState = FirstStepDone;
! return node;
case FirstStepDone:
if (node->left != RBNIL)
{
node->iteratorState = SecondStepDone;
! descend(node->left);
}
+ /* FALL THROUGH */
case SecondStepDone:
if (node->right != RBNIL)
{
node->iteratorState = ThirdStepDone;
! descend(node->right);
}
+ /* FALL THROUGH */
case ThirdStepDone:
if (node->parent)
! ascend(node->parent);
break;
default:
! elog(ERROR, "unrecognized rbtree node state: %d",
! node->iteratorState);
}
return NULL;
}
! static RBNode *
! rb_inverted_iterator(RBTree *rb)
{
! RBNode *node = rb->cur;
+ restart:
switch (node->iteratorState)
{
case InitialState:
if (node->left != RBNIL)
{
node->iteratorState = FirstStepDone;
! descend(node->left);
}
+ /* FALL THROUGH */
case FirstStepDone:
if (node->right != RBNIL)
{
node->iteratorState = SecondStepDone;
! descend(node->right);
}
+ /* FALL THROUGH */
case SecondStepDone:
node->iteratorState = ThirdStepDone;
! return node;
case ThirdStepDone:
if (node->parent)
! ascend(node->parent);
break;
default:
! elog(ERROR, "unrecognized rbtree node state: %d",
! node->iteratorState);
}
return NULL;
}
! /*
! * rb_begin_iterate: prepare to traverse the tree in any of several orders
! *
! * After calling rb_begin_iterate, call rb_iterate repeatedly until it
! * returns NULL or the traversal stops being of interest.
! *
! * If the tree is changed during traversal, results of further calls to
! * rb_iterate are unspecified.
! *
! * Note: this used to return a separately palloc'd iterator control struct,
! * but that's a bit pointless since the data structure is incapable of
! * supporting multiple concurrent traversals. Now we just keep the state
! * in RBTree.
! */
! void
rb_begin_iterate(RBTree *rb, RBOrderControl ctrl)
{
! rb->cur = rb->root;
! if (rb->cur != RBNIL)
! rb->cur->iteratorState = InitialState;
switch (ctrl)
{
case LeftRightWalk: /* visit left, then self, then right */
! rb->iterate = rb_left_right_iterator;
break;
case RightLeftWalk: /* visit right, then self, then left */
! rb->iterate = rb_right_left_iterator;
break;
case DirectWalk: /* visit self, then left, then right */
! rb->iterate = rb_direct_iterator;
break;
case InvertedWalk: /* visit left, then right, then self */
! rb->iterate = rb_inverted_iterator;
break;
default:
! elog(ERROR, "unrecognized rbtree iteration order: %d", ctrl);
}
}
! /*
! * rb_iterate: return the next node in traversal order, or NULL if no more
! */
! RBNode *
! rb_iterate(RBTree *rb)
{
! if (rb->cur == RBNIL)
return NULL;
! return rb->iterate(rb);
}
Index: src/include/access/gin.h
===================================================================
RCS file: /cvsroot/pgsql/src/include/access/gin.h,v
retrieving revision 1.39
diff -c -r1.39 gin.h
*** src/include/access/gin.h 31 Jul 2010 00:30:54 -0000 1.39
--- src/include/access/gin.h 1 Aug 2010 01:44:08 -0000
***************
*** 565,570 ****
--- 565,571 ----
/* ginbulk.c */
typedef struct EntryAccumulator
{
+ RBNode rbnode;
Datum value;
uint32 length;
uint32 number;
***************
*** 579,593 ****
long allocatedMemory;
uint32 length;
EntryAccumulator *entryallocator;
- ItemPointerData *tmpList;
RBTree *tree;
- RBTreeIterator *iterator;
} BuildAccumulator;
extern void ginInitBA(BuildAccumulator *accum);
extern void ginInsertRecordBA(BuildAccumulator *accum,
ItemPointer heapptr,
OffsetNumber attnum, Datum *entries, int32 nentry);
extern ItemPointerData *ginGetEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *entry, uint32 *n);
/* ginfast.c */
--- 580,593 ----
long allocatedMemory;
uint32 length;
EntryAccumulator *entryallocator;
RBTree *tree;
} BuildAccumulator;
extern void ginInitBA(BuildAccumulator *accum);
extern void ginInsertRecordBA(BuildAccumulator *accum,
ItemPointer heapptr,
OffsetNumber attnum, Datum *entries, int32 nentry);
+ extern void ginBeginBAScan(BuildAccumulator *accum);
extern ItemPointerData *ginGetEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *entry, uint32 *n);
/* ginfast.c */
Index: src/include/utils/rbtree.h
===================================================================
RCS file: /cvsroot/pgsql/src/include/utils/rbtree.h,v
retrieving revision 1.3
diff -c -r1.3 rbtree.h
*** src/include/utils/rbtree.h 11 May 2010 18:14:01 -0000 1.3
--- src/include/utils/rbtree.h 1 Aug 2010 01:44:08 -0000
***************
*** 3,46 ****
* rbtree.h
* interface for PostgreSQL generic Red-Black binary tree package
*
! * Copyright (c) 1996-2009, PostgreSQL Global Development Group
*
* IDENTIFICATION
* $PostgreSQL: pgsql/src/include/utils/rbtree.h,v 1.3 2010/05/11 18:14:01 rhaas Exp $
*
*-------------------------------------------------------------------------
*/
-
#ifndef RBTREE_H
#define RBTREE_H
typedef struct RBTree RBTree;
- typedef struct RBTreeIterator RBTreeIterator;
! typedef int (*rb_comparator) (const void *a, const void *b, void *arg);
! typedef void *(*rb_appendator) (void *currentdata, void *newval, void *arg);
! typedef void (*rb_freefunc) (void *a);
! extern RBTree *rb_create(rb_comparator comparator,
! rb_appendator appendator,
rb_freefunc freefunc,
void *arg);
! extern void *rb_find(RBTree *rb, void *data);
! extern void *rb_insert(RBTree *rb, void *data);
! extern void rb_delete(RBTree *rb, void *data);
! extern void *rb_leftmost(RBTree *rb);
! typedef enum RBOrderControl
! {
! LeftRightWalk,
! RightLeftWalk,
! DirectWalk,
! InvertedWalk
! } RBOrderControl;
! extern RBTreeIterator *rb_begin_iterate(RBTree *rb, RBOrderControl ctrl);
! extern void *rb_iterate(RBTreeIterator *iterator);
! extern void rb_free_iterator(RBTreeIterator *iterator);
! #endif
--- 3,66 ----
* rbtree.h
* interface for PostgreSQL generic Red-Black binary tree package
*
! * Copyright (c) 2009-2010, PostgreSQL Global Development Group
*
* IDENTIFICATION
* $PostgreSQL: pgsql/src/include/utils/rbtree.h,v 1.3 2010/05/11 18:14:01 rhaas Exp $
*
*-------------------------------------------------------------------------
*/
#ifndef RBTREE_H
#define RBTREE_H
+ /*
+ * RBNode is intended to be used as the first field of a larger struct,
+ * whose additional fields carry whatever payload data the caller needs
+ * for a tree entry. (The total size of that larger struct is passed to
+ * rb_create.) RBNode is declared here to support this usage, but
+ * callers must treat it as an opaque struct.
+ */
+ typedef struct RBNode
+ {
+ char iteratorState; /* workspace for iterating through tree */
+ char color; /* node's current color, red or black */
+ struct RBNode *left; /* left child, or RBNIL if none */
+ struct RBNode *right; /* right child, or RBNIL if none */
+ struct RBNode *parent; /* parent, or NULL (not RBNIL!) if none */
+ } RBNode;
+
+ /* Opaque struct representing a whole tree */
typedef struct RBTree RBTree;
! /* Available tree iteration orderings */
! typedef enum RBOrderControl
! {
! LeftRightWalk, /* inorder: left child, node, right child */
! RightLeftWalk, /* reverse inorder: right, node, left */
! DirectWalk, /* preorder: node, left child, right child */
! InvertedWalk /* postorder: left child, right child, node */
! } RBOrderControl;
! /* Support functions to be provided by caller */
! typedef int (*rb_comparator) (const RBNode *a, const RBNode *b, void *arg);
! typedef void (*rb_combiner) (RBNode *existing, const RBNode *newdata, void *arg);
! typedef RBNode *(*rb_allocfunc) (void *arg);
! typedef void (*rb_freefunc) (RBNode *x, void *arg);
!
! extern RBTree *rb_create(Size node_size,
! rb_comparator comparator,
! rb_combiner combiner,
! rb_allocfunc allocfunc,
rb_freefunc freefunc,
void *arg);
! extern RBNode *rb_find(RBTree *rb, const RBNode *data);
! extern RBNode *rb_leftmost(RBTree *rb);
! extern RBNode *rb_insert(RBTree *rb, const RBNode *data, bool *isNew);
! extern void rb_delete(RBTree *rb, RBNode *node);
! extern void rb_begin_iterate(RBTree *rb, RBOrderControl ctrl);
! extern RBNode *rb_iterate(RBTree *rb);
! #endif /* RBTREE_H */