From bd13347df5b07c4a8e6477febea8e692a84f9118 Mon Sep 17 00:00:00 2001
From: Olly Betts <olly@survex.com>
Date: Wed, 28 Mar 2018 17:52:08 +1300
Subject: [PATCH] [honey] For bchop index store upper bound key

Add a key which is an upper bound on all keys in the table, pointing
to the root (start of the index) so that searching for a key larger
than any in the table quickly fails.

If the largest key in the table has 0xff for all its first four bytes
then we don't add this new entry (because there's no 4 byte entry
which gives an upper bound).  It's probably less likely that keys
beyond the end of the table will be searched for in this case anyway.
---
 xapian-core/backends/honey/honey_table.h | 33 +++++++++++++++++++++++++++++++-
 1 file changed, 32 insertions(+), 1 deletion(-)

diff --git a/xapian-core/backends/honey/honey_table.h b/xapian-core/backends/honey/honey_table.h
index 9dbb7f3f2..f03398ef8 100644
--- a/xapian-core/backends/honey/honey_table.h
+++ b/xapian-core/backends/honey/honey_table.h
@@ -419,6 +419,8 @@ class SSIndex {
     }
 
     off_t write(BufferedFile& fh) {
+	off_t root = fh.get_pos();
+
 #ifdef SSINDEX_ARRAY
 	if (!pointers) {
 	    first = last = 0;
@@ -441,6 +443,36 @@ class SSIndex {
 	delete [] pointers;
 	pointers = NULL;
 #elif defined SSINDEX_BINARY_CHOP
+	if (last_index_key.size() == SSINDEX_BINARY_CHOP_KEY_SIZE) {
+	    // Increment final byte(s) to give a key which is definitely
+	    // at or above any key which this could be truncated from.
+	    size_t i = last_index_key.size();
+	    unsigned char ch;
+	    do {
+		if (i == 0) {
+		    // We can't increment "\xff\xff\xff\xff" to give an upper
+		    // bound - just skip adding one in this case as the table
+		    // will handle it OK and there's not much to be gained by
+		    // adding one as few keys are larger.
+		    goto skip_adding_upper_bound;
+		}
+		--i;
+		ch = static_cast<unsigned char>(last_index_key[i]) + 1;
+		last_index_key[i] = ch;
+	    } while (ch == 0);
+	} else {
+	    // Pad with zeros, which gives an upper bound.
+	    last_index_key.resize(SSINDEX_BINARY_CHOP_KEY_SIZE);
+	}
+
+	{
+	    data += last_index_key;
+	    size_t c = data.size();
+	    data.resize(c + 4);
+	    unaligned_write4(reinterpret_cast<unsigned char*>(&data[c]), root);
+	}
+
+skip_adding_upper_bound:
 	// Fill in bytes 1 to 4 with the number of entries.
 	size_t n_index = (data.size() - 5) / (SSINDEX_BINARY_CHOP_KEY_SIZE + 4);
 	data[1] = n_index >> 24;
@@ -453,7 +485,6 @@ class SSIndex {
 # error "SSINDEX type not specified"
 #endif
 
-	off_t root = fh.get_pos();
 	fh.write(data.data(), data.size());
 	// FIXME: parent stuff...
 	return root;
-- 
2.11.4.GIT