Generic implementation of red-black binary tree. It's planned to use in

several places, but for now only GIN uses it during index creation.
Using self-balanced tree greatly speeds up index creation in corner cases
with preordered data.

2 files changed, 54 insertions, 19 deletions

diff --git a/src/include/access/gin.h b/src/include/access/gin.h
index 0ea25dc4039..48965613608 100644
--- a/src/include/access/gin.h
+++ b/src/include/access/gin.h
@@ -4,7 +4,7 @@
  *
  *	Copyright (c) 2006-2010, PostgreSQL Global Development Group
  *
- *	$PostgreSQL: pgsql/src/include/access/gin.h,v 1.36 2010/01/02 16:58:00 momjian Exp $
+ *	$PostgreSQL: pgsql/src/include/access/gin.h,v 1.37 2010/02/11 14:29:50 teodor Exp $
  *--------------------------------------------------------------------------
  */
 #ifndef 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.
@@ -570,27 +563,23 @@ extern Datum ginarrayconsistent(PG_FUNCTION_ARGS);
 /* ginbulk.c */
 typedef struct EntryAccumulator
 {
-	OffsetNumber attnum;
 	Datum		value;
 	uint32		length;
 	uint32		number;
-	ItemPointerData *list;
+	OffsetNumber attnum;
 	bool		shouldSort;
-	struct EntryAccumulator *left;
-	struct EntryAccumulator *right;
+	ItemPointerData *list;
 } 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 00000000000..535a23780b3
--- /dev/null
+++ b/src/include/utils/rbtree.h
@@ -0,0 +1,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.1 2010/02/11 14:29:50 teodor 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_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