From 2dd87ed9e6c71127cbd1464754095af8e3c548fd Mon Sep 17 00:00:00 2001
From: Howard Chu <hyc@openldap.org>
Date: Mon, 12 Sep 2005 03:54:52 +0000
Subject: [PATCH] Use quicksort instead of heapsort for hdb_idl_sort

---
 servers/slapd/back-bdb/idl.c | 86 ++++++++++++++++++++++++------------
 servers/slapd/back-bdb/idl.h |  5 ++-
 2 files changed, 60 insertions(+), 31 deletions(-)

diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c
index 5c5e0ef304..e8d6546ff0 100644
--- a/servers/slapd/back-bdb/idl.c
+++ b/servers/slapd/back-bdb/idl.c
@@ -1297,43 +1297,71 @@ int bdb_idl_append( ID *a, ID *b )
 	
 }
 
-/* Sort an IDL using HeapSort */
-static void
-siftDown(ID *ids, int root, int bottom)
-{
-	int child;
-	ID temp;
-
-	temp = ids[root];
-	while ((child=root*2) <= bottom) {
-		if (child < bottom && ids[child] < ids[child + 1])
-			child++;
+/* Quicksort + Insertion sort for small arrays */
 
-		if (temp >= ids[child])
-			break;
-		ids[root] = ids[child];
-		root = child;
-	}
-	ids[root] = temp;
-}
+#define SMALL	8
+#define	SWAP(a,b)	a^=b;b^=a;a^=b	/* Swap integers without temp var */
 
 void
 bdb_idl_sort( ID *ids )
 {
-	int i;
-	ID temp;
+	int istack[BDB_IDL_LOGN*4];
+	int i,j,k,l,ir,jstack;
+	ID a;
 
 	if ( BDB_IDL_IS_RANGE( ids ))
 		return;
 
-	for (i = ids[0] / 2; i >= 1; i--)
-		siftDown(ids, i, ids[0]);
-
-	for (i = ids[0]; i > 1; i--)
-	{
-		temp = ids[i];
-		ids[i] = ids[1];
-		ids[1] = temp;
-		siftDown(ids, 1, i-1);
+	ir = ids[0];
+	l = 1;
+	jstack = 0;
+	for(;;) {
+		if (ir - l < SMALL) {	/* Insertion sort */
+			for (j=l+1;j<=ir;j++) {
+				a = ids[j];
+				for (i=j-1;i>=1;i--) {
+					if (ids[i] <= a) break;
+					ids[i+1] = ids[i];
+				}
+				ids[i+1] = a;
+			}
+			if (jstack == 0) break;
+			ir = istack[jstack--];
+			l = istack[jstack--];
+		} else {
+			k = (l + ir) >> 1;	/* Choose median of left, center, right */
+			SWAP(ids[k], ids[l+1]);
+			if (ids[l] > ids[ir]) {
+				SWAP(ids[l], ids[ir]);
+			}
+			if (ids[l+1] > ids[ir]) {
+				SWAP(ids[l+1], ids[ir]);
+			}
+			if (ids[l] > ids[l+1]) {
+				SWAP(ids[l], ids[l+1]);
+			}
+			i = l+1;
+			j = ir;
+			a = ids[l+1];
+			for(;;) {
+				do i++; while(ids[i] < a);
+				do j--; while(ids[j] > a);
+				if (j < i) break;
+				SWAP(ids[i],ids[j]);
+			}
+			ids[l+1] = ids[j];
+			ids[j] = a;
+			jstack += 2;
+			assert(jstack <= BDB_IDL_LOGN*4);
+			if (ir-i+1 >= j-1) {
+				istack[jstack] = ir;
+				istack[jstack-1] = i;
+				ir = j-1;
+			} else {
+				istack[jstack] = j-1;
+				istack[jstack-1] = l;
+				l = i;
+			}
+		}
 	}
 }
diff --git a/servers/slapd/back-bdb/idl.h b/servers/slapd/back-bdb/idl.h
index 357c6539bd..29fcc83b0b 100644
--- a/servers/slapd/back-bdb/idl.h
+++ b/servers/slapd/back-bdb/idl.h
@@ -20,8 +20,9 @@
 /* IDL sizes - likely should be even bigger
  *   limiting factors: sizeof(ID), thread stack size
  */
-#define BDB_IDL_DB_SIZE		(1<<16) /* 64K IDL on disk */
-#define BDB_IDL_UM_SIZE		(1<<17) /* 128K IDL in memory */
+#define	BDB_IDL_LOGN	16	/* DB_SIZE is 2^16, UM_SIZE is 2^17 */
+#define BDB_IDL_DB_SIZE		(1<<BDB_IDL_LOGN)
+#define BDB_IDL_UM_SIZE		(1<<(BDB_IDL_LOGN+1))
 #define BDB_IDL_UM_SIZEOF	(BDB_IDL_UM_SIZE * sizeof(ID))
 
 #define BDB_IDL_DB_MAX		(BDB_IDL_DB_SIZE-1)
-- 
2.39.5