From 4a7f5e33bd0e1a6750229b84850da0f5881baba4 Mon Sep 17 00:00:00 2001
From: Howard Chu <hyc@openldap.org>
Date: Thu, 15 Sep 2005 08:29:58 +0000
Subject: [PATCH] More optimizing - try harder to avoid sorting

---
 servers/slapd/back-bdb/dn2id.c     | 14 +++++---
 servers/slapd/back-bdb/idl.c       | 54 ++++++++++++++----------------
 servers/slapd/back-bdb/proto-bdb.h |  4 +--
 3 files changed, 37 insertions(+), 35 deletions(-)

diff --git a/servers/slapd/back-bdb/dn2id.c b/servers/slapd/back-bdb/dn2id.c
index 4d548b4fb6..e7b90ee0df 100644
--- a/servers/slapd/back-bdb/dn2id.c
+++ b/servers/slapd/back-bdb/dn2id.c
@@ -818,12 +818,13 @@ struct dn2id_cookie {
 	ID dbuf;
 	ID *ids;
 	void *ptr;
-	ID tmp[BDB_IDL_UM_SIZE];
+	ID *tmp;
 	ID *buf;
 	DBT key;
 	DBT data;
 	DBC *dbc;
 	Operation *op;
+	int need_sort;
 };
 
 static int
@@ -952,7 +953,7 @@ hdb_dn2idl_internal(
 
 saveit:
 	if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 1 )
-		bdb_idl_sort( cx->tmp );
+		bdb_idl_sort( cx->tmp, cx->buf );
 	if ( cx->bdb->bi_idl_cache_max_size ) {
 		cx->key.data = &cx->id;
 		bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc );
@@ -961,7 +962,8 @@ saveit:
 gotit:
 	if ( !BDB_IDL_IS_ZERO( cx->tmp )) {
 		if ( cx->prefix == DN_SUBTREE_PREFIX ) {
-			bdb_idl_merge( cx->ids, cx->tmp );
+			bdb_idl_append( cx->ids, cx->tmp );
+			cx->need_sort = 1;
 			if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
 				ID *save, idcurs;
 				EntryInfo *ei = cx->ei;
@@ -1024,8 +1026,10 @@ hdb_dn2idl(
 	cx.prefix = (op->ors_scope == LDAP_SCOPE_ONELEVEL) ?
 		DN_ONE_PREFIX : DN_SUBTREE_PREFIX;
 	cx.ids = ids;
-	cx.buf = stack;
+	cx.tmp = stack;
+	cx.buf = stack + BDB_IDL_UM_SIZE;
 	cx.op = op;
+	cx.need_sort = 0;
 
 	BDB_IDL_ZERO( ids );
 	if ( cx.prefix == DN_SUBTREE_PREFIX ) {
@@ -1040,6 +1044,8 @@ hdb_dn2idl(
 	DBTzero(&cx.data);
 
 	hdb_dn2idl_internal(&cx);
+	if ( cx.need_sort && !BDB_IDL_IS_RANGE( cx.ids ) && cx.ids[0] > 1 )
+		bdb_idl_sort( cx.ids, cx.tmp );
 
 	return cx.rc;
 }
diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c
index a7594b6a04..237df18fea 100644
--- a/servers/slapd/back-bdb/idl.c
+++ b/servers/slapd/back-bdb/idl.c
@@ -1244,13 +1244,12 @@ int bdb_idl_append_one( ID *ids, ID id )
 	return 0;
 }
 
-/* Merge sorted list b to sorted list a. There are no common values
- * in list a and b.
+/* Append sorted list b to sorted list a. The result is unsorted but
+ * a[1] is the min of the result and a[a[0]] is the max.
  */
-int bdb_idl_merge( ID *a, ID *b )
+int bdb_idl_append( ID *a, ID *b )
 {
-	ID ida, idb;
-	ID cursora, cursorb, cursorc;
+	ID ida, idb, tmp;
 
 	if ( BDB_IDL_IS_ZERO( b ) ) {
 		return 0;
@@ -1261,34 +1260,34 @@ int bdb_idl_merge( ID *a, ID *b )
 		return 0;
 	}
 
+	ida = BDB_IDL_LAST( a );
+	idb = BDB_IDL_LAST( b );
 	if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
 		a[0] + b[0] >= BDB_IDL_UM_MAX ) {
-		ida = BDB_IDL_LAST( a );
-		idb = BDB_IDL_LAST( b );
 		a[2] = IDL_MAX( ida, idb );
 		a[1] = IDL_MIN( a[1], b[1] );
 		a[0] = NOID;
 		return 0;
 	}
 
-	cursora = a[0];
-	cursorb = b[0];
-	cursorc = cursora + cursorb;
-	a[0] = cursorc;
+	if ( b[0] > 1 && ida > idb ) {
+		a[a[0]] = idb;
+		b[b[0]] = ida;
+	}
 
-	while ( cursorc > 0 ) {
-		if ( b[cursorb] > a[cursora] ) {
-			a[cursorc] = b[cursorb];
-			cursorb--;
-			if ( !cursorb )
-				break;
-		} else {
-			if ( cursora == cursorc )
-				break;
-			a[cursorc] = a[cursora];
-			cursora --;
-		}
-		cursorc--;
+	if ( b[1] < a[1] ) {
+		tmp = a[1];
+		a[1] = b[1];
+	} else {
+		tmp = b[1];
+	}
+	a[0]++;
+	a[a[0]] = tmp;
+
+	if ( b[0] > 1 ) {
+		int i = b[0] - 1;
+		AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
+		a[0] += i;
 	}
 	return 0;
 }
@@ -1298,12 +1297,10 @@ int bdb_idl_merge( ID *a, ID *b )
 #define SMALL	8
 #define	SWAP(a,b)	a^=b;b^=a;a^=b	/* Swap integers without temp var */
 
-#define ISTACK	((BDB_IDL_LOGN+1)*4)
-
 void
-bdb_idl_sort( ID *ids )
+bdb_idl_sort( ID *ids, ID *tmp )
 {
-	int istack[ISTACK];
+	int *istack = (int *)tmp;
 	int i,j,k,l,ir,jstack;
 	ID a;
 
@@ -1350,7 +1347,6 @@ bdb_idl_sort( ID *ids )
 			ids[l+1] = ids[j];
 			ids[j] = a;
 			jstack += 2;
-			assert(jstack <= ISTACK);
 			if (ir-i+1 >= j-1) {
 				istack[jstack] = ir;
 				istack[jstack-1] = i;
diff --git a/servers/slapd/back-bdb/proto-bdb.h b/servers/slapd/back-bdb/proto-bdb.h
index 75f2f991bb..860e877433 100644
--- a/servers/slapd/back-bdb/proto-bdb.h
+++ b/servers/slapd/back-bdb/proto-bdb.h
@@ -245,7 +245,7 @@ bdb_idl_cache_del(
 #define bdb_idl_intersection		BDB_SYMBOL(idl_intersection)
 #define bdb_idl_union				BDB_SYMBOL(idl_union)
 #define bdb_idl_sort				BDB_SYMBOL(idl_sort)
-#define bdb_idl_merge				BDB_SYMBOL(idl_merge)
+#define bdb_idl_append				BDB_SYMBOL(idl_append)
 #define bdb_idl_append_one			BDB_SYMBOL(idl_append_one)
 
 #define bdb_idl_fetch_key			BDB_SYMBOL(idl_fetch_key)
@@ -292,7 +292,7 @@ bdb_idl_union(
 ID bdb_idl_first( ID *ids, ID *cursor );
 ID bdb_idl_next( ID *ids, ID *cursor );
 
-void bdb_idl_sort( ID *ids );
+void bdb_idl_sort( ID *ids, ID *tmp );
 int bdb_idl_append( ID *a, ID *b );
 int bdb_idl_append_one( ID *ids, ID id );
 
-- 
2.39.5