From aa3297aa36e62278508c315ddfd5594c98e08a05 Mon Sep 17 00:00:00 2001
From: Howard Chu <hyc@openldap.org>
Date: Tue, 13 Sep 2005 07:55:01 +0000
Subject: [PATCH] More back-hdb search optimization

---
 servers/slapd/back-bdb/dn2id.c     |  6 ++--
 servers/slapd/back-bdb/idl.c       | 46 +++++++++++++-----------------
 servers/slapd/back-bdb/proto-bdb.h |  2 +-
 3 files changed, 24 insertions(+), 30 deletions(-)

diff --git a/servers/slapd/back-bdb/dn2id.c b/servers/slapd/back-bdb/dn2id.c
index 89d5704c64..c9f93fe0a6 100644
--- a/servers/slapd/back-bdb/dn2id.c
+++ b/servers/slapd/back-bdb/dn2id.c
@@ -953,13 +953,15 @@ hdb_dn2idl_internal(
 saveit:
 	if ( cx->bdb->bi_idl_cache_max_size ) {
 		cx->key.data = &cx->id;
+		if ( !BDB_IDL_IS_RANGE( cx->tmp ) && cx->tmp[0] > 1 )
+			bdb_idl_sort( cx->tmp );
 		bdb_idl_cache_put( cx->bdb, cx->db, &cx->key, cx->tmp, cx->rc );
 	}
 	;
 gotit:
 	if ( !BDB_IDL_IS_ZERO( cx->tmp )) {
 		if ( cx->prefix == DN_SUBTREE_PREFIX ) {
-			bdb_idl_append( cx->ids, cx->tmp );
+			bdb_idl_merge( cx->ids, cx->tmp );
 			if ( !(cx->ei->bei_state & CACHE_ENTRY_NO_GRANDKIDS)) {
 				ID *save, idcurs;
 				EntryInfo *ei = cx->ei;
@@ -1038,8 +1040,6 @@ hdb_dn2idl(
 	DBTzero(&cx.data);
 
 	hdb_dn2idl_internal(&cx);
-	if ( !BDB_IDL_IS_ZERO( ids ) && !BDB_IDL_IS_RANGE( ids ))
-		bdb_idl_sort( ids );
 
 	return cx.rc;
 }
diff --git a/servers/slapd/back-bdb/idl.c b/servers/slapd/back-bdb/idl.c
index b29860f820..a826d401e4 100644
--- a/servers/slapd/back-bdb/idl.c
+++ b/servers/slapd/back-bdb/idl.c
@@ -1244,12 +1244,13 @@ int bdb_idl_append_one( ID *ids, ID id )
 	return 0;
 }
 
-/* Append unsorted list b to unsorted list a. Both lists must have their
- * lowest value in slot 1 and highest value in slot 2.
+/* Merge sorted list b to sorted list a. There are no common values
+ * in list a and b.
  */
-int bdb_idl_append( ID *a, ID *b )
+int bdb_idl_merge( ID *a, ID *b )
 {
 	ID ida, idb;
+	ID cursora, cursorb, cursorc;
 
 	if ( BDB_IDL_IS_ZERO( b ) ) {
 		return 0;
@@ -1263,38 +1264,31 @@ int bdb_idl_append( ID *a, ID *b )
 	if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
 		a[0] + b[0] >= BDB_IDL_UM_MAX ) {
 		ida = IDL_MIN( a[1], b[1] );
-		idb = IDL_MAX( a[2], b[2] );
+		idb = IDL_MAX( a[a[0]], b[b[0]] );
 		a[0] = NOID;
 		a[1] = ida;
 		a[2] = idb;
 		return 0;
 	}
 
-	if ( b[1] < a[1] ) {
-		ida = a[1];
-		a[1] = b[1];
-	} else {
-		ida = b[1];
-	}
-	a[0]++;
-	a[a[0]] = ida;
-
-	if ( b[0] > 1 && b[2] > a[2] ) {
-		ida = a[2];
-		a[2] = b[2];
-	} else {
-		ida = b[2];
-	}
-	a[0]++;
-	a[a[0]] = ida;
+	cursora = a[0];
+	cursorb = b[0];
+	cursorc = cursora + cursorb;
+	a[0] = cursorc;
 
-	if ( b[0] > 2 ) {
-		int i = b[0] - 2;
-		AC_MEMCPY(a+a[0]+1, b+3, i * sizeof(ID));
-		a[0] += i;
+	while ( cursorc > 0 ) {
+		if ( b[cursorb] > a[cursora] ) {
+			a[cursorc] = b[cursorb];
+			cursorb--;
+		} else {
+			if ( cursora == cursorc )
+				break;
+			a[cursorc] = a[cursora];
+			cursora --;
+		}
+		cursorc--;
 	}
 	return 0;
-	
 }
 
 /* Quicksort + Insertion sort for small arrays */
diff --git a/servers/slapd/back-bdb/proto-bdb.h b/servers/slapd/back-bdb/proto-bdb.h
index 5955721f4e..75f2f991bb 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_append				BDB_SYMBOL(idl_append)
+#define bdb_idl_merge				BDB_SYMBOL(idl_merge)
 #define bdb_idl_append_one			BDB_SYMBOL(idl_append_one)
 
 #define bdb_idl_fetch_key			BDB_SYMBOL(idl_fetch_key)
-- 
2.39.5