From 7ae77904b349729d469a529b15b892157dd2ce29 Mon Sep 17 00:00:00 2001
From: Matthew Swift <matthew.swift@forgerock.com>
Date: Thu, 02 Apr 2015 10:16:45 +0000
Subject: [PATCH] OPENDJ-1711 - re-implement VLV support for pluggable backends
---
opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/ControlsTestCase.java | 71 +++++++++++++++++++++++
opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java | 50 ++++++++++++----
2 files changed, 108 insertions(+), 13 deletions(-)
diff --git a/opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java b/opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java
index 0c865cc..b8f037c 100644
--- a/opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java
+++ b/opendj-sdk/opendj-server-legacy/src/main/java/org/opends/server/backends/pluggable/VLVIndex.java
@@ -607,7 +607,7 @@
final ByteStringBuilder encodedPrimaryKey = new ByteStringBuilder(assertion.length() + 10);
final MatchingRule matchingRule = primarySortKey.getAttributeType().getOrderingMatchingRule();
final ByteString normalizedAttributeValue = matchingRule.normalizeAttributeValue(assertion);
- encodeVLVKeyValue(primarySortKey, normalizedAttributeValue, encodedPrimaryKey);
+ encodeVLVKeyValue(normalizedAttributeValue, encodedPrimaryKey, primarySortKey.ascending());
return encodedPrimaryKey;
}
catch (final DecodeException e)
@@ -803,37 +803,61 @@
}
}
}
- encodeVLVKeyValue(sortKey, sortValue, builder);
+ encodeVLVKeyValue(sortValue, builder, sortKey.ascending());
}
}
- private static void encodeVLVKeyValue(final SortKey sortKey, final ByteString normalizedAttributeValue,
- final ByteStringBuilder builder)
+ /**
+ * Package private for testing.
+ * <p>
+ * Keys are logically encoded as follows:
+ * <ul>
+ * <li>if the key is {@code null} then append {@code 0xff} in order to ensure that all
+ * {@code null} keys sort after non-{@code null} keys in ascending order
+ * <li>else
+ * <ul>
+ * <li>escape any bytes that look like a separator byte ({@code 0x00}) or a separator escape byte
+ * ({@code 0x01}) by prefixing the byte with a separator escape byte ({@code 0x01})
+ * <li>escape the first byte if it looks like a null key byte ({@code 0xff}) or a null key escape
+ * byte ({@code 0xfe}) by prefixing the byte with a null key escape byte ({@code 0xfe})
+ * </ul>
+ * <li>append a separator byte ({@code 0x00}) which will be used for distinguishing between the
+ * end of the key and the start of the next key
+ * <li>invert all the bytes if the sort order is descending.
+ * </ul>
+ */
+ static void encodeVLVKeyValue(final ByteString keyBytes, final ByteStringBuilder builder,
+ final boolean ascending)
{
- final boolean ascending = sortKey.ascending();
final byte separator = ascending ? (byte) 0x00 : (byte) 0xff;
- if (normalizedAttributeValue != null)
+ if (keyBytes != null)
{
- // Ensure that all keys sort before (ascending) or after (descending) missing keys.
- builder.append(separator);
-
final byte escape = ascending ? (byte) 0x01 : (byte) 0xfe;
final byte sortOrderMask = separator;
- final int length = normalizedAttributeValue.length();
+ final int length = keyBytes.length();
for (int i = 0; i < length; i++)
{
- final byte b = normalizedAttributeValue.byteAt(i);
- if (b == separator || b == escape)
+ final byte b = keyBytes.byteAt(i);
+ if ((b & (byte) 0x01) == b)
{
+ // Escape bytes that look like a separator.
builder.append(escape);
}
+ else if (i == 0 && (b & (byte) 0xfe) == (byte) 0xfe)
+ {
+ /*
+ * Ensure that all keys sort before (ascending) or after (descending) null keys, by
+ * escaping the first byte if it looks like a null key.
+ */
+ builder.append((byte) ~escape);
+ }
// Invert the bits if this key is in descending order.
builder.append((byte) (b ^ sortOrderMask));
}
}
else
{
- // Ensure that missing keys sort after (ascending) or before (descending) all other keys.
+ // Ensure that null keys sort after (ascending) or before (descending) all other keys.
builder.append(ascending ? (byte) 0xff : (byte) 0x00);
}
builder.append(separator);
diff --git a/opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/ControlsTestCase.java b/opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/ControlsTestCase.java
index 85060d2..061a550 100644
--- a/opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/ControlsTestCase.java
+++ b/opendj-sdk/opendj-server-legacy/src/test/java/org/opends/server/backends/pluggable/ControlsTestCase.java
@@ -43,6 +43,7 @@
import org.forgerock.opendj.config.server.ConfigException;
import org.forgerock.opendj.ldap.ByteString;
+import org.forgerock.opendj.ldap.ByteStringBuilder;
import org.forgerock.opendj.ldap.ResultCode;
import org.forgerock.opendj.ldap.SearchScope;
import org.opends.server.DirectoryServerTestCase;
@@ -169,6 +170,76 @@
}
@DataProvider
+ private Object[][] encodedKeyDataProvider()
+ {
+ // @formatter:off
+ return new Object[][] {
+ // Null keys sort after everything else.
+ { null, null, 0 },
+ { "", null, -1 },
+ { null, "", 1 },
+ { "00", null, -1 },
+ { null, "00", 1 },
+ { "ff", null, -1 },
+ { null, "ff", 1 },
+
+ // Empty keys sort before everything else.
+ { "", "", 0 },
+ { "00", "", 1 },
+ { "", "00", -1 },
+ { "ff", "", 1 },
+ { "", "ff", -1 },
+
+ // Bytes comparisons are unsigned.
+ { "00", "00", 0 },
+ { "00", "ff", -1 },
+ { "ff", "00", 1 },
+ { "ff", "ff", 0 },
+
+ // Short keys sort before long keys.
+ { "0000", "00", 1 },
+ { "00", "0000", -1 },
+ { "ffff", "ff", 1 },
+ { "ff", "ffff", -1 },
+ { "0000", "0000", 0 },
+ { "ffff", "ffff", 0 },
+ { "0000", "ffff", -1 },
+ { "ffff", "0000", 1 },
+ };
+ // @formatter:on
+ }
+
+ @Test(dataProvider = "encodedKeyDataProvider")
+ public void vlvKeyEncodingGenerateCorrectAscendingSortOrder(String key1, String key2, int expectedCompareResult)
+ {
+ ByteString bytes1 = key1 != null ? ByteString.valueOfHex(key1) : null;
+ ByteStringBuilder encodedBytes1 = new ByteStringBuilder();
+ VLVIndex.encodeVLVKeyValue(bytes1, encodedBytes1, true);
+
+ ByteString bytes2 = key2 != null ? ByteString.valueOfHex(key2) : null;
+ ByteStringBuilder encodedBytes2 = new ByteStringBuilder();
+ VLVIndex.encodeVLVKeyValue(bytes2, encodedBytes2, true);
+
+ int actualResult = Math.min(Math.max(encodedBytes1.compareTo(encodedBytes2), -1), 1);
+ assertThat(actualResult).isEqualTo(expectedCompareResult);
+ }
+
+ @Test(dataProvider = "encodedKeyDataProvider")
+ public void vlvKeyEncodingGenerateCorrectDescendingSortOrder(String key1, String key2, int expectedCompareResult)
+ {
+ ByteString bytes1 = key1 != null ? ByteString.valueOfHex(key1) : null;
+ ByteStringBuilder encodedBytes1 = new ByteStringBuilder();
+ VLVIndex.encodeVLVKeyValue(bytes1, encodedBytes1, false);
+
+ ByteString bytes2 = key2 != null ? ByteString.valueOfHex(key2) : null;
+ ByteStringBuilder encodedBytes2 = new ByteStringBuilder();
+ VLVIndex.encodeVLVKeyValue(bytes2, encodedBytes2, false);
+
+ int actualResult = Math.min(Math.max(encodedBytes1.compareTo(encodedBytes2), -1), 1);
+ assertThat(actualResult).isEqualTo(-expectedCompareResult);
+ }
+
+ @DataProvider
private Object[][] indexedVlvByAssertionDataProvider()
{
// @formatter:off
--
Gitblit v1.10.0