diff --git a/src/backend/access/gin/ginbulk.c b/src/backend/access/gin/ginbulk.c index 954884d..e043713 100644 --- a/src/backend/access/gin/ginbulk.c +++ b/src/backend/access/gin/ginbulk.c @@ -22,15 +22,60 @@ #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); + eo->length *= 2; + eo->list = (ItemPointerData *) repalloc(eo->list, + sizeof(ItemPointerData) * eo->length); + accum->allocatedMemory += GetMemoryChunkSpace(eo->list); + } + + /* If item pointers are not ordered, they will need to be sorted. */ + if (eo->shouldSort == FALSE) + { + int res; + + res = compareItemPointers(eo->list + eo->number - 1, en->list); + Assert(res != 0); + + if (res > 0) + eo->shouldSort = TRUE; + } + + 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->maxdepth = 1; - accum->stackpos = 0; - accum->entries = NULL; - accum->stack = NULL; accum->allocatedMemory = 0; accum->entryallocator = NULL; + accum->tree = rb_create(cmpEntryAccumulator, ginAppendData, NULL, accum); + accum->iterator = NULL; + accum->tmpList = NULL; } static EntryAccumulator * @@ -48,36 +93,6 @@ EAAllocate(BuildAccumulator *accum) } /* - * Stores heap item pointer. For robust, it checks that - * item pointer are ordered - */ -static void -ginInsertData(BuildAccumulator *accum, EntryAccumulator *entry, ItemPointer heapptr) -{ - if (entry->number >= entry->length) - { - accum->allocatedMemory -= GetMemoryChunkSpace(entry->list); - entry->length *= 2; - entry->list = (ItemPointerData *) repalloc(entry->list, - sizeof(ItemPointerData) * entry->length); - accum->allocatedMemory += GetMemoryChunkSpace(entry->list); - } - - if (entry->shouldSort == FALSE) - { - int res = compareItemPointers(entry->list + entry->number - 1, heapptr); - - Assert(res != 0); - - if (res > 0) - entry->shouldSort = TRUE; - } - - entry->list[entry->number] = *heapptr; - entry->number++; -} - -/* * This is basically the same as datumCopy(), but modified to count * palloc'd space in accum. */ @@ -103,57 +118,38 @@ getDatumCopy(BuildAccumulator *accum, OffsetNumber attnum, Datum value) static void ginInsertEntry(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum entry) { - EntryAccumulator *ea = accum->entries, - *pea = NULL; - int res = 0; - uint32 depth = 1; + EntryAccumulator *key = EAAllocate(accum), + *ea; - while (ea) - { - res = compareAttEntries(accum->ginstate, attnum, entry, ea->attnum, ea->value); - if (res == 0) - break; /* found */ - else - { - pea = ea; - if (res < 0) - ea = ea->left; - else - ea = ea->right; - } - depth++; - } + key->attnum = attnum; + key->value = entry; + if (accum->tmpList == NULL) + accum->tmpList = + (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR); + key->list = accum->tmpList; + key->list[0] = *heapptr; - if (depth > accum->maxdepth) - accum->maxdepth = depth; + ea = rb_insert(accum->tree, key); if (ea == NULL) { - ea = EAAllocate(accum); - - ea->left = ea->right = NULL; - ea->attnum = attnum; - ea->value = getDatumCopy(accum, attnum, entry); - ea->length = DEF_NPTR; - ea->number = 1; - ea->shouldSort = FALSE; - ea->list = (ItemPointerData *) palloc(sizeof(ItemPointerData) * DEF_NPTR); - accum->allocatedMemory += GetMemoryChunkSpace(ea->list); - ea->list[0] = *heapptr; - - if (pea == NULL) - accum->entries = ea; - else - { - Assert(res != 0); - if (res < 0) - pea->left = ea; - else - pea->right = ea; - } + /* + * 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 - ginInsertData(accum, ea, heapptr); + { + /* + * The key has been appended, so reset + */ + accum->length--; + } } /* @@ -219,86 +215,16 @@ qsortCompareItemPointers(const void *a, const void *b) return res; } -/* - * walk on binary tree and returns ordered nodes - */ -static EntryAccumulator * -walkTree(BuildAccumulator *accum) -{ - EntryAccumulator *entry = accum->stack[accum->stackpos]; - - if (entry->list != NULL) - { - /* return entry itself: we already was at left sublink */ - return entry; - } - else if (entry->right && entry->right != accum->stack[accum->stackpos + 1]) - { - /* go on right sublink */ - accum->stackpos++; - entry = entry->right; - - /* find most-left value */ - for (;;) - { - accum->stack[accum->stackpos] = entry; - if (entry->left) - { - accum->stackpos++; - entry = entry->left; - } - else - break; - } - } - else - { - /* we already return all left subtree, itself and right subtree */ - if (accum->stackpos == 0) - return 0; - accum->stackpos--; - return walkTree(accum); - } - - return entry; -} - ItemPointerData * ginGetEntry(BuildAccumulator *accum, OffsetNumber *attnum, Datum *value, uint32 *n) { EntryAccumulator *entry; ItemPointerData *list; - if (accum->stack == NULL) - { - /* first call */ - accum->stack = palloc0(sizeof(EntryAccumulator *) * (accum->maxdepth + 1)); - accum->allocatedMemory += GetMemoryChunkSpace(accum->stack); - entry = accum->entries; - - if (entry == NULL) - return NULL; - - /* find most-left value */ - for (;;) - { - accum->stack[accum->stackpos] = entry; - if (entry->left) - { - accum->stackpos++; - entry = entry->left; - } - else - break; - } - } - else - { - accum->allocatedMemory -= GetMemoryChunkSpace(accum->stack[accum->stackpos]->list); - pfree(accum->stack[accum->stackpos]->list); - accum->stack[accum->stackpos]->list = NULL; - entry = walkTree(accum); - } + if (accum->iterator == NULL) + accum->iterator = rb_begin_iterate(accum->tree, LeftRightWalk); + + entry = rb_iterate(accum->iterator); if (entry == NULL) return NULL; diff --git a/src/backend/access/gin/ginfast.c b/src/backend/access/gin/ginfast.c index 8d48cdf..3fb4441 100644 --- a/src/backend/access/gin/ginfast.c +++ b/src/backend/access/gin/ginfast.c @@ -765,8 +765,7 @@ ginInsertCleanup(Relation index, GinState *ginstate, */ if (GinPageGetOpaque(page)->rightlink == InvalidBlockNumber || (GinPageHasFullRow(page) && - (accum.allocatedMemory >= maintenance_work_mem * 1024L || - accum.maxdepth > GIN_MAX_TREE_DEPTH))) + (accum.allocatedMemory >= maintenance_work_mem * 1024L))) { ItemPointerData *list; uint32 nlist; diff --git a/src/backend/access/gin/gininsert.c b/src/backend/access/gin/gininsert.c index 902e361..97fc417 100644 --- a/src/backend/access/gin/gininsert.c +++ b/src/backend/access/gin/gininsert.c @@ -247,9 +247,7 @@ ginBuildCallback(Relation index, HeapTuple htup, Datum *values, &htup->t_self); /* If we've maxed out our available memory, dump everything to the index */ - /* Also dump if the tree seems to be getting too unbalanced */ - if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L || - buildstate->accum.maxdepth > GIN_MAX_TREE_DEPTH) + if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L) { ItemPointerData *list; Datum entry; diff --git a/src/backend/utils/misc/Makefile b/src/backend/utils/misc/Makefile index 03a155c..e8866df 100644 --- a/src/backend/utils/misc/Makefile +++ b/src/backend/utils/misc/Makefile @@ -14,7 +14,8 @@ include $(top_builddir)/src/Makefile.global override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS) -OBJS = guc.o help_config.o pg_rusage.o ps_status.o superuser.o tzparser.o +OBJS = guc.o help_config.o pg_rusage.o ps_status.o superuser.o tzparser.o \ + rbtree.o # This location might depend on the installation directories. Therefore # we can't subsitute it into pg_config.h. diff --git a/src/backend/utils/misc/rbtree.c b/src/backend/utils/misc/rbtree.c new file mode 100644 index 0000000..b10c669 --- /dev/null +++ b/src/backend/utils/misc/rbtree.c @@ -0,0 +1,814 @@ +/*------------------------------------------------------------------------- + * + * rbtree.c + * implementation for PostgreSQL generic Red-Black binary tree package + * Adopted from http://algolist.manual.ru/ds/rbtree.php + * + * This code comes from Thomas Niemann's "Sorting and Searching Algorithms: + * a Cookbook". + * + * See http://www.cs.auckland.ac.nz/software/AlgAnim/niemann/s_man.htm for + * license terms: "Source code, when part of a software project, may be used + * freely without reference to the author." + * + * Red-black trees are a type of balanced binary tree wherein (1) any child of + * a red node is always black, and (2) every path from root to leaf traverses + * an equal number of black nodes. From these properties, it follows that the + * 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/nodes/rbtree.c,v 1.69 2008/01/01 19:45:50 momjian Exp $ + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "utils/rbtree.h" + +/********************************************************************** + * Declarations * + **********************************************************************/ + +/* + * Values for RBNode->iteratorState + */ +#define InitialState (0) +#define FirstStepDone (1) +#define SecondStepDone (2) +#define ThirdStepDone (3) + +/* + * Colors of node + */ +#define BLACK (0) +#define RED (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 castimized NIL name to prevent + * collision with sytem-wide NIL which is actually NULL + */ +#define RBNIL &sentinel + +RBNode sentinel = {InitialState, BLACK, 0, RBNIL, RBNIL, NULL, NULL}; + +/********************************************************************** + * Create/free * + **********************************************************************/ + +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; +} + +static void +rb_free_recursive(RBNode *node, rb_freefunc freefunc) +{ + if (node->left != RBNIL) + rb_free_recursive(node->left, freefunc); + if (node->right != RBNIL) + rb_free_recursive(node->right, freefunc); + if (freefunc && node->data) + freefunc(node->data); + pfree(node); +} + +void +rb_free(RBTree *rb) +{ + if (!rb) + return; + + if (rb->root != RBNIL) + rb_free_recursive(rb->root, rb->freefunc); + + pfree(rb); +} + +/********************************************************************** + * 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 + node = node->right; + } + + return NULL; +} + +/********************************************************************** + * Insertion * + **********************************************************************/ + +/* + * Rotate node x to left. + * + * x's right child takes its place in the tree, and x becomes the left + * child of that node. + */ +static void +rb_rotate_left(RBTree *rb, RBNode *x) +{ + RBNode *y = x->right; + + /* establish x->right link */ + x->right = y->left; + if (y->left != RBNIL) + y->left->parent = x; + + /* establish y->parent link */ + if (y != RBNIL) + y->parent = x->parent; + if (x->parent) + { + if (x == x->parent->left) + x->parent->left = y; + else + x->parent->right = y; + } + else + { + rb->root = y; + } + + /* link x and y */ + y->left = x; + if (x != RBNIL) + x->parent = y; +} + +/* + * Rotate node x to right. + * + * x's left right child takes its place in the tree, and x becomes the right + * child of that node. + */ +static void +rb_rotate_right(RBTree *rb, RBNode *x) +{ + RBNode *y = x->left; + + /* establish x->left link */ + x->left = y->right; + if (y->right != RBNIL) + y->right->parent = x; + + /* establish y->parent link */ + if (y != RBNIL) + y->parent = x->parent; + if (x->parent) + { + if (x == x->parent->right) + x->parent->right = y; + else + x->parent->left = y; + } + else + { + rb->root = y; + } + + /* link x and y */ + y->right = x; + if (x != RBNIL) + x->parent = y; +} + +/* + * Maintain Red-Black tree balance after inserting node x. + * + * The newly inserted node is always initially marked red. That may lead to + * a situation where a red node has a red child, which is prohibited. We can + * always fix the problem by a series of color changes and/or "rotations", + * which move the problem progressively higher up in the tree. If one of the + * two red nodes is the root, we can always fix the problem by changing the + * root from red to black. + * + * (This does not work lower down in the tree because we must also maintain + * the invariant that every leaf has equal black-height.) + */ +static void +rb_insert_fixup(RBTree *rb, RBNode *x) +{ + /* + * x is always a red node. Initially, it is the newly inserted node. + * Each iteration of this loop moves it higher up in the tree. + */ + while (x != rb->root && x->parent->color == RED) + { + /* + * x and x->parent are both red. Fix depends on whether x->parent is + * a left or right child. In either case, we define y to be the + * "uncle" of x, that is, the other child of x's grandparent. + * + * If the uncle is red, we flip the grandparent to red and its two + * children to black. Then we loop around again to check whether the + * grandparent still has a problem. + * + * If the uncle is black, we will perform one or two "rotations" to + * balance the tree. Either x or x->parent will take the grandparent's + * position in the tree and recolored black, and the original + * grandparent will be recolored red and become a child of that node. + * This always leaves us with a valid red-black tree, so the loop + * will terminate. + */ + if (x->parent == x->parent->parent->left) + { + RBNode *y = x->parent->parent->right; + + if (y->color == RED) + { + /* uncle is RED */ + x->parent->color = BLACK; + y->color = BLACK; + x->parent->parent->color = RED; + x = x->parent->parent; + } + else + { + /* uncle is BLACK */ + if (x == x->parent->right) + { + /* make x a left child */ + x = x->parent; + rb_rotate_left(rb, x); + } + + /* recolor and rotate */ + x->parent->color = BLACK; + x->parent->parent->color = RED; + rb_rotate_right(rb, x->parent->parent); + } + } + else + { + /* mirror image of above code */ + RBNode *y = x->parent->parent->left; + + if (y->color == RED) + { + /* uncle is RED */ + x->parent->color = BLACK; + y->color = BLACK; + x->parent->parent->color = RED; + x = x->parent->parent; + } + else + { + /* uncle is BLACK */ + if (x == x->parent->left) + { + x = x->parent; + rb_rotate_right(rb, x); + } + x->parent->color = BLACK; + x->parent->parent->color = RED; + rb_rotate_left(rb, x->parent->parent); + } + } + } + + /* + * The root may already have been black; if not, the black-height of every + * node in the tree increases by one. + */ + rb->root->color = BLACK; +} + +/* + * 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, + *x; + int cmp; + + /* find where node belongs */ + current = rb->root; + parent = NULL; + 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 = RED; + x->iteratorState = InitialState; + + /* insert node in tree */ + if (parent) + { + if (cmp < 0) + parent->left = x; + else + parent->right = x; + } + else + { + rb->root = x; + } + + rb_insert_fixup(rb, x); + return NULL; +} + +/********************************************************************** + * Deletion * + **********************************************************************/ + +/* + * Maintain Red-Black tree balance after deleting a black node. + */ +static void +rb_delete_fixup(RBTree *rb, RBNode *x) +{ + /* + * x is always a black node. Initially, it is the former child of the + * deleted node. Each iteration of this loop moves it higher up in the + * tree. + */ + while (x != rb->root && x->color == BLACK) + { + /* + * Left and right cases are symmetric. Any nodes that are children + * of x have a black-height one less than the remainder of the nodes + * in the tree. We rotate and recolor nodes to move the problem up + * the tree: at some stage we'll either fix the problem, or reach the + * root (where the black-height is allowed to decrease). + */ + if (x == x->parent->left) + { + RBNode *w = x->parent->right; + + if (w->color == RED) + { + w->color = BLACK; + x->parent->color = RED; + rb_rotate_left(rb, x->parent); + w = x->parent->right; + } + + if (w->left->color == BLACK && w->right->color == BLACK) + { + w->color = RED; + x = x->parent; + } + else + { + if (w->right->color == BLACK) + { + w->left->color = BLACK; + w->color = RED; + rb_rotate_right(rb, w); + w = x->parent->right; + } + w->color = x->parent->color; + x->parent->color = BLACK; + w->right->color = BLACK; + rb_rotate_left(rb, x->parent); + x = rb->root; /* Arrange for loop to terminate. */ + } + } + else + { + RBNode *w = x->parent->left; + + if (w->color == RED) + { + w->color = BLACK; + x->parent->color = RED; + rb_rotate_right(rb, x->parent); + w = x->parent->left; + } + + if (w->right->color == BLACK && w->left->color == BLACK) + { + w->color = RED; + x = x->parent; + } + else + { + if (w->left->color == BLACK) + { + w->right->color = BLACK; + w->color = RED; + rb_rotate_left(rb, w); + w = x->parent->left; + } + w->color = x->parent->color; + x->parent->color = BLACK; + w->left->color = BLACK; + rb_rotate_right(rb, x->parent); + x = rb->root; /* Arrange for loop to terminate. */ + } + } + } + x->color = BLACK; +} + +/* + * Delete node z from tree. + */ +static void +rb_delete_node(RBTree *rb, RBNode *z) +{ + RBNode *x, + *y; + + if (!z || z == RBNIL) + return; + + /* + * y is the node that will actually be removed from the tree. This will + * be z if z has fewer than two children, or the tree successor of z + * otherwise. + */ + if (z->left == RBNIL || z->right == RBNIL) + { + /* y has a RBNIL node as a child */ + y = z; + } + else + { + /* find tree successor */ + y = z->right; + while (y->left != RBNIL) + y = y->left; + } + + /* x is y's only child */ + if (y->left != RBNIL) + x = y->left; + else + x = y->right; + + /* Remove y from the tree. */ + x->parent = y->parent; + if (y->parent) + { + if (y == y->parent->left) + y->parent->left = x; + else + y->parent->right = x; + } + else + { + rb->root = x; + } + + /* + * 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 + * fewer black nodes than others, or it might make two red nodes adjacent. + */ + if (y->color == BLACK) + 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); +} diff --git a/src/include/access/gin.h b/src/include/access/gin.h index b96ff95..fcc5371 100644 --- a/src/include/access/gin.h +++ b/src/include/access/gin.h @@ -13,6 +13,7 @@ #include "access/genam.h" #include "access/itup.h" #include "access/xlog.h" +#include "utils/rbtree.h" #include "fmgr.h" @@ -27,14 +28,6 @@ #define GINNProcs 5 /* - * Max depth allowed in search tree during bulk inserts. This is to keep from - * degenerating to O(N^2) behavior when the tree is unbalanced due to sorted - * or nearly-sorted input. (Perhaps it would be better to use a balanced-tree - * algorithm, but in common cases that would only add useless overhead.) - */ -#define GIN_MAX_TREE_DEPTH 100 - -/* * Page opaque data in a inverted index page. * * Note: GIN does not include a page ID word as do the other index types. @@ -571,26 +564,22 @@ extern Datum ginarrayconsistent(PG_FUNCTION_ARGS); typedef struct EntryAccumulator { OffsetNumber attnum; + bool shouldSort; Datum value; uint32 length; uint32 number; ItemPointerData *list; - bool shouldSort; - struct EntryAccumulator *left; - struct EntryAccumulator *right; } EntryAccumulator; typedef struct { GinState *ginstate; - EntryAccumulator *entries; - uint32 maxdepth; - EntryAccumulator **stack; - uint32 stackpos; long allocatedMemory; - uint32 length; - EntryAccumulator *entryallocator; + EntryAccumulator *entryallocator; + ItemPointerData *tmpList; + RBTree *tree; + RBTreeIterator *iterator; } BuildAccumulator; extern void ginInitBA(BuildAccumulator *accum); diff --git a/src/include/utils/rbtree.h b/src/include/utils/rbtree.h new file mode 100644 index 0000000..6ce74b0 --- /dev/null +++ b/src/include/utils/rbtree.h @@ -0,0 +1,47 @@ +/*------------------------------------------------------------------------- + * + * rbtree.h + * interface for PostgreSQL generic Red-Black binary tree package + * + * Copyright (c) 1996-2009, PostgreSQL Global Development Group + * + * IDENTIFICATION + * $PostgreSQL: pgsql/src/backend/nodes/list.c,v 1.69 2008/01/01 19:45:50 momjian 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 *current, void *new, 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_free(RBTree *rb); + +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