diff -c -r -N src.orig/backend/access/gin/ginbulk.c src/backend/access/gin/ginbulk.c
*** src.orig/backend/access/gin/ginbulk.c	2010-02-08 15:20:50.000000000 +0300
--- src/backend/access/gin/ginbulk.c	2010-02-08 20:20:26.000000000 +0300
***************
*** 22,80 ****
  #define DEF_NENTRY	2048
  #define DEF_NPTR	4
  
! void
! ginInitBA(BuildAccumulator *accum)
  {
! 	accum->maxdepth = 1;
! 	accum->stackpos = 0;
! 	accum->entries = NULL;
! 	accum->stack = NULL;
! 	accum->allocatedMemory = 0;
! 	accum->entryallocator = NULL;
! }
! 
! static EntryAccumulator *
! EAAllocate(BuildAccumulator *accum)
! {
! 	if (accum->entryallocator == NULL || accum->length >= DEF_NENTRY)
! 	{
! 		accum->entryallocator = palloc(sizeof(EntryAccumulator) * DEF_NENTRY);
! 		accum->allocatedMemory += GetMemoryChunkSpace(accum->entryallocator);
! 		accum->length = 0;
! 	}
  
! 	accum->length++;
! 	return accum->entryallocator + accum->length - 1;
! }
  
! /*
!  * 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++;
  }
  
  /*
--- 22,81 ----
  #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->allocatedMemory = 0;
! 	accum->entryallocator = NULL;
! 	accum->tree = rb_create(cmpEntryAccumulator, ginAppendData, NULL, accum);
! 	accum->iterator = NULL;
! 	accum->tmpList = NULL;
  }
  
  /*
***************
*** 103,213 ****
  static void
  ginInsertEntry(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum, Datum entry)
  {
! 	EntryAccumulator *ea = accum->entries,
! 			   *pea = NULL;
! 	int			res = 0;
! 	uint32		depth = 1;
  
! 	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++;
  	}
  
! 	if (depth > accum->maxdepth)
! 		accum->maxdepth = depth;
  
  	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;
! 		}
  	}
  	else
! 		ginInsertData(accum, ea, heapptr);
! }
! 
! /*
!  * insert middle of left part the middle of right one,
!  * then calls itself for each parts
!  */
! static void
! ginChooseElem(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum,
! 			  Datum *entries, uint32 nentry,
! 			  uint32 low, uint32 high, uint32 offset)
! {
! 	uint32		pos;
! 	uint32		middle = (low + high) >> 1;
! 
! 	pos = (low + middle) >> 1;
! 	if (low != middle && pos >= offset && pos - offset < nentry)
! 		ginInsertEntry(accum, heapptr, attnum, entries[pos - offset]);
! 	pos = (high + middle + 1) >> 1;
! 	if (middle + 1 != high && pos >= offset && pos - offset < nentry)
! 		ginInsertEntry(accum, heapptr, attnum, entries[pos - offset]);
! 
! 	if (low != middle)
! 		ginChooseElem(accum, heapptr, attnum, entries, nentry, low, middle, offset);
! 	if (high != middle + 1)
! 		ginChooseElem(accum, heapptr, attnum, entries, nentry, middle + 1, high, offset);
  }
  
  /*
   * Insert one heap pointer. Suppose entries is sorted.
!  * Insertion order tries to get binary tree balanced: first insert middle value,
!  * next middle on left part and middle of right part.
   */
  void
  ginInsertRecordBA(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum,
  				  Datum *entries, int32 nentry)
  {
! 	uint32		i,
! 				nbit = 0,
! 				offset;
  
  	if (nentry <= 0)
  		return;
  
  	Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);
  
! 	i = nentry - 1;
! 	for (; i > 0; i >>= 1)
! 		nbit++;
  
! 	nbit = 1 << nbit;
! 	offset = (nbit - nentry) / 2;
  
! 	ginInsertEntry(accum, heapptr, attnum, entries[(nbit >> 1) - offset]);
! 	ginChooseElem(accum, heapptr, attnum, entries, nentry, 0, nbit, offset);
  }
  
  static int
--- 104,202 ----
  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--;
! 	}
  }
  
  /*
   * Insert one heap pointer. Suppose entries is sorted.
!  * Insertion order tries to keep binary tree balanced to prevent
!  * repeated rebalalacing: we will insert elements in order close 
!  * to balanced tree. First, we virtually enlarge our array to
!  * the closest 2**n-1 number (ideally balanced binary tree contains
!  * that number of nodes). Second, we insert middle of out virtual 
!  * array into tree (it will be a root), then we insert middles of
!  * each half of out virtual array, then middles of quarters etc.
!  * This insertion order decreases number of rebalancings of tree.
   */
  void
  ginInsertRecordBA(BuildAccumulator *accum, ItemPointer heapptr, OffsetNumber attnum,
  				  Datum *entries, int32 nentry)
  {
! 	uint32	step = nentry;
  
  	if (nentry <= 0)
  		return;
  
  	Assert(ItemPointerIsValid(heapptr) && attnum >= FirstOffsetNumber);
  
! 	/*
! 	 * step will contain largest power of 2 and <= nentry
! 	 */
! 	step |= (step >>  1);
! 	step |= (step >>  2);
! 	step |= (step >>  4);
! 	step |= (step >>  8);
! 	step |= (step >> 16);
! 	step ++;
! 	step >>= 1;
! 
! 	while(step > 0) {
! 		int i;
  
! 		for (i = step-1; i < nentry; i += 2 * step)
! 			ginInsertEntry(accum, heapptr, attnum, entries[i]);
  
! 		step >>= 1; /* /2 */
! 	}
  }
  
  static int
***************
*** 219,304 ****
  	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 (entry == NULL)
  		return NULL;
--- 208,223 ----
  	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;
diff -c -r -N src.orig/backend/access/gin/ginfast.c src/backend/access/gin/ginfast.c
*** src.orig/backend/access/gin/ginfast.c	2010-02-08 15:20:50.000000000 +0300
--- src/backend/access/gin/ginfast.c	2010-02-08 19:46:17.000000000 +0300
***************
*** 765,772 ****
  		 */
  		if (GinPageGetOpaque(page)->rightlink == InvalidBlockNumber ||
  			(GinPageHasFullRow(page) &&
! 			 (accum.allocatedMemory >= maintenance_work_mem * 1024L ||
! 			  accum.maxdepth > GIN_MAX_TREE_DEPTH)))
  		{
  			ItemPointerData *list;
  			uint32		nlist;
--- 765,771 ----
  		 */
  		if (GinPageGetOpaque(page)->rightlink == InvalidBlockNumber ||
  			(GinPageHasFullRow(page) &&
! 			 (accum.allocatedMemory >= maintenance_work_mem * 1024L)))
  		{
  			ItemPointerData *list;
  			uint32		nlist;
diff -c -r -N src.orig/backend/access/gin/gininsert.c src/backend/access/gin/gininsert.c
*** src.orig/backend/access/gin/gininsert.c	2010-02-08 15:20:50.000000000 +0300
--- src/backend/access/gin/gininsert.c	2010-02-08 19:46:17.000000000 +0300
***************
*** 247,255 ****
  															&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)
  	{
  		ItemPointerData *list;
  		Datum		entry;
--- 247,253 ----
  															&htup->t_self);
  
  	/* If we've maxed out our available memory, dump everything to the index */
! 	if (buildstate->accum.allocatedMemory >= maintenance_work_mem * 1024L)
  	{
  		ItemPointerData *list;
  		Datum		entry;
diff -c -r -N src.orig/backend/utils/misc/Makefile src/backend/utils/misc/Makefile
*** src.orig/backend/utils/misc/Makefile	2010-02-08 15:20:55.000000000 +0300
--- src/backend/utils/misc/Makefile	2010-02-08 19:46:17.000000000 +0300
***************
*** 14,20 ****
  
  override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
  
! OBJS = guc.o help_config.o pg_rusage.o ps_status.o superuser.o tzparser.o
  
  # This location might depend on the installation directories. Therefore
  # we can't subsitute it into pg_config.h.
--- 14,21 ----
  
  override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
  
! 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 -c -r -N src.orig/backend/utils/misc/rbtree.c src/backend/utils/misc/rbtree.c
*** src.orig/backend/utils/misc/rbtree.c	1970-01-01 03:00:00.000000000 +0300
--- src/backend/utils/misc/rbtree.c	2010-02-08 19:54:41.000000000 +0300
***************
*** 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 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/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 == RBRED)
+ 	{
+ 		/*
+ 		 * 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 == RBRED)
+ 			{
+ 				/* uncle is RBRED */
+ 				x->parent->color = RBBLACK;
+ 				y->color = RBBLACK;
+ 				x->parent->parent->color = RBRED;
+ 				x = x->parent->parent;
+ 			}
+ 			else
+ 			{
+ 				/* uncle is RBBLACK */
+ 				if (x == x->parent->right)
+ 				{
+ 					/* make x a left child */
+ 					x = x->parent;
+ 					rb_rotate_left(rb, x);
+ 				}
+ 
+ 				/* recolor and rotate */
+ 				x->parent->color = RBBLACK;
+ 				x->parent->parent->color = RBRED;
+ 				rb_rotate_right(rb, x->parent->parent);
+ 			}
+ 		}
+ 		else
+ 		{
+ 			/* mirror image of above code */
+ 			RBNode	   *y = x->parent->parent->left;
+ 
+ 			if (y->color == RBRED)
+ 			{
+ 				/* uncle is RBRED */
+ 				x->parent->color = RBBLACK;
+ 				y->color = RBBLACK;
+ 				x->parent->parent->color = RBRED;
+ 				x = x->parent->parent;
+ 			}
+ 			else
+ 			{
+ 				/* uncle is RBBLACK */
+ 				if (x == x->parent->left)
+ 				{
+ 					x = x->parent;
+ 					rb_rotate_right(rb, x);
+ 				}
+ 				x->parent->color = RBBLACK;
+ 				x->parent->parent->color = RBRED;
+ 				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 = RBBLACK;
+ }
+ 
+ /*
+  * 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 = RBRED;
+ 	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 == RBBLACK)
+ 	{
+ 		/*
+ 		 * 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 == RBRED)
+ 			{
+ 				w->color = RBBLACK;
+ 				x->parent->color = RBRED;
+ 				rb_rotate_left(rb, x->parent);
+ 				w = x->parent->right;
+ 			}
+ 
+ 			if (w->left->color == RBBLACK && w->right->color == RBBLACK)
+ 			{
+ 				w->color = RBRED;
+ 				x = x->parent;
+ 			}
+ 			else
+ 			{
+ 				if (w->right->color == RBBLACK)
+ 				{
+ 					w->left->color = RBBLACK;
+ 					w->color = RBRED;
+ 					rb_rotate_right(rb, w);
+ 					w = x->parent->right;
+ 				}
+ 				w->color = x->parent->color;
+ 				x->parent->color = RBBLACK;
+ 				w->right->color = RBBLACK;
+ 				rb_rotate_left(rb, x->parent);
+ 				x = rb->root;		/* Arrange for loop to terminate. */
+ 			}
+ 		}
+ 		else
+ 		{
+ 			RBNode	   *w = x->parent->left;
+ 
+ 			if (w->color == RBRED)
+ 			{
+ 				w->color = RBBLACK;
+ 				x->parent->color = RBRED;
+ 				rb_rotate_right(rb, x->parent);
+ 				w = x->parent->left;
+ 			}
+ 
+ 			if (w->right->color == RBBLACK && w->left->color == RBBLACK)
+ 			{
+ 				w->color = RBRED;
+ 				x = x->parent;
+ 			}
+ 			else
+ 			{
+ 				if (w->left->color == RBBLACK)
+ 				{
+ 					w->right->color = RBBLACK;
+ 					w->color = RBRED;
+ 					rb_rotate_left(rb, w);
+ 					w = x->parent->left;
+ 				}
+ 				w->color = x->parent->color;
+ 				x->parent->color = RBBLACK;
+ 				w->left->color = RBBLACK;
+ 				rb_rotate_right(rb, x->parent);
+ 				x = rb->root;		/* Arrange for loop to terminate. */
+ 			}
+ 		}
+ 	}
+ 	x->color = RBBLACK;
+ }
+ 
+ /*
+  * 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 == 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);
+ }
diff -c -r -N src.orig/include/access/gin.h src/include/access/gin.h
*** src.orig/include/access/gin.h	2010-02-08 15:20:57.000000000 +0300
--- src/include/access/gin.h	2010-02-08 19:46:17.000000000 +0300
***************
*** 13,18 ****
--- 13,19 ----
  #include "access/genam.h"
  #include "access/itup.h"
  #include "access/xlog.h"
+ #include "utils/rbtree.h"
  #include "fmgr.h"
  
  
***************
*** 27,40 ****
  #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.
--- 28,33 ----
***************
*** 570,596 ****
  /* ginbulk.c */
  typedef struct EntryAccumulator
  {
- 	OffsetNumber attnum;
  	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;
  } BuildAccumulator;
  
  extern void ginInitBA(BuildAccumulator *accum);
--- 563,585 ----
  /* ginbulk.c */
  typedef struct EntryAccumulator
  {
  	Datum		value;
  	uint32		length;
  	uint32		number;
! 	OffsetNumber attnum;
  	bool		shouldSort;
! 	ItemPointerData *list;
  } EntryAccumulator;
  
  typedef struct
  {
  	GinState   *ginstate;
  	long		allocatedMemory;
  	uint32		length;
! 	EntryAccumulator   *entryallocator;
! 	ItemPointerData	   *tmpList;
! 	RBTree	   *tree;
! 	RBTreeIterator *iterator;
  } BuildAccumulator;
  
  extern void ginInitBA(BuildAccumulator *accum);
diff -c -r -N src.orig/include/utils/rbtree.h src/include/utils/rbtree.h
*** src.orig/include/utils/rbtree.h	1970-01-01 03:00:00.000000000 +0300
--- src/include/utils/rbtree.h	2010-02-08 19:46:17.000000000 +0300
***************
*** 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
