mirror of
https://github.com/berkeleydb/je.git
synced 2024-11-15 01:46:24 +00:00
427 lines
13 KiB
Java
427 lines
13 KiB
Java
|
/*-
|
|||
|
|
* Copyright (C) 2002, 2017, Oracle and/or its affiliates. All rights reserved.
|
|||
|
|
*
|
|||
|
|
* This file was distributed by Oracle as part of a version of Oracle Berkeley
|
|||
|
|
* DB Java Edition made available at:
|
|||
|
|
*
|
|||
|
|
* http://www.oracle.com/technetwork/database/database-technologies/berkeleydb/downloads/index.html
|
|||
|
|
*
|
|||
|
|
* Please see the LICENSE file included in the top-level directory of the
|
|||
|
|
* appropriate version of Oracle Berkeley DB Java Edition for a copy of the
|
|||
|
|
* license and additional information.
|
|||
|
|
*/
|
|||
|
|
|
|||
|
|
package com.sleepycat.collections;
|
|||
|
|
|
|||
|
|
import static org.junit.Assert.assertEquals;
|
|||
|
|
import static org.junit.Assert.assertNotNull;
|
|||
|
|
import static org.junit.Assert.fail;
|
|||
|
|
|
|||
|
|
import java.io.File;
|
|||
|
|
import java.io.Serializable;
|
|||
|
|
import java.util.Arrays;
|
|||
|
|
import java.util.Comparator;
|
|||
|
|
|
|||
|
|
import org.junit.After;
|
|||
|
|
import org.junit.Test;
|
|||
|
|
|
|||
|
|
import com.sleepycat.bind.ByteArrayBinding;
|
|||
|
|
import com.sleepycat.compat.DbCompat;
|
|||
|
|
import com.sleepycat.je.Database;
|
|||
|
|
import com.sleepycat.je.DatabaseConfig;
|
|||
|
|
import com.sleepycat.je.DatabaseEntry;
|
|||
|
|
import com.sleepycat.je.DatabaseException;
|
|||
|
|
import com.sleepycat.je.Environment;
|
|||
|
|
import com.sleepycat.je.EnvironmentConfig;
|
|||
|
|
import com.sleepycat.je.OperationStatus;
|
|||
|
|
import com.sleepycat.util.keyrange.KeyRange;
|
|||
|
|
import com.sleepycat.util.keyrange.KeyRangeException;
|
|||
|
|
import com.sleepycat.util.test.SharedTestUtils;
|
|||
|
|
import com.sleepycat.util.test.TestBase;
|
|||
|
|
|
|||
|
|
/**
|
|||
|
|
* @author Mark Hayes
|
|||
|
|
*/
|
|||
|
|
public class KeyRangeTest extends TestBase {
|
|||
|
|
|
|||
|
|
private static boolean VERBOSE = false;
|
|||
|
|
|
|||
|
|
private static final byte FF = (byte) 0xFF;
|
|||
|
|
|
|||
|
|
private static final byte[][] KEYS = {
|
|||
|
|
/* 0 */ {1},
|
|||
|
|
/* 1 */ {FF},
|
|||
|
|
/* 2 */ {FF, 0},
|
|||
|
|
/* 3 */ {FF, 0x7F},
|
|||
|
|
/* 4 */ {FF, FF},
|
|||
|
|
/* 5 */ {FF, FF, 0},
|
|||
|
|
/* 6 */ {FF, FF, 0x7F},
|
|||
|
|
/* 7 */ {FF, FF, FF},
|
|||
|
|
};
|
|||
|
|
private static byte[][] EXTREME_KEY_BYTES = {
|
|||
|
|
/* 0 */ {0},
|
|||
|
|
/* 1 */ {FF, FF, FF, FF},
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
private Environment env;
|
|||
|
|
private Database store;
|
|||
|
|
private DataView view;
|
|||
|
|
private DataCursor cursor;
|
|||
|
|
|
|||
|
|
private void openDb(Comparator<byte []> comparator)
|
|||
|
|
throws Exception {
|
|||
|
|
|
|||
|
|
File dir = SharedTestUtils.getNewDir();
|
|||
|
|
ByteArrayBinding dataBinding = new ByteArrayBinding();
|
|||
|
|
EnvironmentConfig envConfig = new EnvironmentConfig();
|
|||
|
|
envConfig.setAllowCreate(true);
|
|||
|
|
DbCompat.setInitializeCache(envConfig, true);
|
|||
|
|
env = new Environment(dir, envConfig);
|
|||
|
|
DatabaseConfig dbConfig = new DatabaseConfig();
|
|||
|
|
DbCompat.setTypeBtree(dbConfig);
|
|||
|
|
dbConfig.setAllowCreate(true);
|
|||
|
|
if (comparator != null) {
|
|||
|
|
DbCompat.setBtreeComparator(dbConfig, comparator);
|
|||
|
|
}
|
|||
|
|
store = DbCompat.testOpenDatabase
|
|||
|
|
(env, null, "test.db", null, dbConfig);
|
|||
|
|
view = new DataView(store, dataBinding, dataBinding, null, true, null);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void closeDb()
|
|||
|
|
throws Exception {
|
|||
|
|
|
|||
|
|
store.close();
|
|||
|
|
store = null;
|
|||
|
|
env.close();
|
|||
|
|
env = null;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
@After
|
|||
|
|
public void tearDown() {
|
|||
|
|
try {
|
|||
|
|
if (store != null) {
|
|||
|
|
store.close();
|
|||
|
|
}
|
|||
|
|
} catch (Exception e) {
|
|||
|
|
System.out.println("Exception ignored during close: " + e);
|
|||
|
|
}
|
|||
|
|
try {
|
|||
|
|
if (env != null) {
|
|||
|
|
env.close();
|
|||
|
|
}
|
|||
|
|
} catch (Exception e) {
|
|||
|
|
System.out.println("Exception ignored during close: " + e);
|
|||
|
|
}
|
|||
|
|
/* Ensure that GC can cleanup. */
|
|||
|
|
env = null;
|
|||
|
|
store = null;
|
|||
|
|
view = null;
|
|||
|
|
cursor = null;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
@Test
|
|||
|
|
public void testScan() throws Exception {
|
|||
|
|
openDb(null);
|
|||
|
|
doScan(false);
|
|||
|
|
closeDb();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
@Test
|
|||
|
|
public void testScanComparator() throws Exception {
|
|||
|
|
openDb(new ReverseComparator());
|
|||
|
|
doScan(true);
|
|||
|
|
closeDb();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void doScan(boolean reversed) throws Exception {
|
|||
|
|
|
|||
|
|
byte[][] keys = new byte[KEYS.length][];
|
|||
|
|
final int end = KEYS.length - 1;
|
|||
|
|
cursor = new DataCursor(view, true);
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
keys[i] = KEYS[i];
|
|||
|
|
cursor.put(keys[i], KEYS[i], null, false);
|
|||
|
|
}
|
|||
|
|
cursor.close();
|
|||
|
|
byte[][] extremeKeys = new byte[EXTREME_KEY_BYTES.length][];
|
|||
|
|
for (int i = 0; i < extremeKeys.length; i++) {
|
|||
|
|
extremeKeys[i] = EXTREME_KEY_BYTES[i];
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// with empty range
|
|||
|
|
|
|||
|
|
cursor = new DataCursor(view, false);
|
|||
|
|
expectRange(KEYS, 0, end, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
|
|||
|
|
// begin key only, inclusive
|
|||
|
|
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
cursor = newCursor(view, keys[i], true, null, false, reversed);
|
|||
|
|
expectRange(KEYS, i, end, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// begin key only, exclusive
|
|||
|
|
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
cursor = newCursor(view, keys[i], false, null, false, reversed);
|
|||
|
|
expectRange(KEYS, i + 1, end, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// end key only, inclusive
|
|||
|
|
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
cursor = newCursor(view, null, false, keys[i], true, reversed);
|
|||
|
|
expectRange(KEYS, 0, i, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// end key only, exclusive
|
|||
|
|
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
cursor = newCursor(view, null, false, keys[i], false, reversed);
|
|||
|
|
expectRange(KEYS, 0, i - 1, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// begin and end keys, inclusive and exclusive
|
|||
|
|
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
for (int j = i; j <= end; j++) {
|
|||
|
|
// begin inclusive, end inclusive
|
|||
|
|
|
|||
|
|
cursor = newCursor(view, keys[i], true, keys[j],
|
|||
|
|
true, reversed);
|
|||
|
|
expectRange(KEYS, i, j, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
|
|||
|
|
// begin inclusive, end exclusive
|
|||
|
|
|
|||
|
|
cursor = newCursor(view, keys[i], true, keys[j],
|
|||
|
|
false, reversed);
|
|||
|
|
expectRange(KEYS, i, j - 1, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
|
|||
|
|
// begin exclusive, end inclusive
|
|||
|
|
|
|||
|
|
cursor = newCursor(view, keys[i], false, keys[j],
|
|||
|
|
true, reversed);
|
|||
|
|
expectRange(KEYS, i + 1, j, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
|
|||
|
|
// begin exclusive, end exclusive
|
|||
|
|
|
|||
|
|
cursor = newCursor(view, keys[i], false, keys[j],
|
|||
|
|
false, reversed);
|
|||
|
|
expectRange(KEYS, i + 1, j - 1, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// single key range
|
|||
|
|
|
|||
|
|
for (int i = 0; i <= end; i++) {
|
|||
|
|
cursor = new DataCursor(view, false, keys[i]);
|
|||
|
|
expectRange(KEYS, i, i, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// start with lower extreme (before any existing key)
|
|||
|
|
|
|||
|
|
cursor = newCursor(view, extremeKeys[0], true, null, false, reversed);
|
|||
|
|
expectRange(KEYS, 0, end, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
|
|||
|
|
// start with higher extreme (after any existing key)
|
|||
|
|
|
|||
|
|
cursor = newCursor(view, null, false, extremeKeys[1], true, reversed);
|
|||
|
|
expectRange(KEYS, 0, end, reversed);
|
|||
|
|
cursor.close();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private DataCursor newCursor(DataView view,
|
|||
|
|
Object beginKey, boolean beginInclusive,
|
|||
|
|
Object endKey, boolean endInclusive,
|
|||
|
|
boolean reversed)
|
|||
|
|
throws Exception {
|
|||
|
|
|
|||
|
|
if (reversed) {
|
|||
|
|
return new DataCursor(view, false,
|
|||
|
|
endKey, endInclusive,
|
|||
|
|
beginKey, beginInclusive);
|
|||
|
|
} else {
|
|||
|
|
return new DataCursor(view, false,
|
|||
|
|
beginKey, beginInclusive,
|
|||
|
|
endKey, endInclusive);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void expectRange(byte[][] bytes, int first, int last,
|
|||
|
|
boolean reversed)
|
|||
|
|
throws DatabaseException {
|
|||
|
|
|
|||
|
|
int i;
|
|||
|
|
boolean init;
|
|||
|
|
for (init = true, i = first;; i++, init = false) {
|
|||
|
|
if (checkRange(bytes, first, last, i <= last,
|
|||
|
|
reversed, !reversed, init, i)) {
|
|||
|
|
break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
for (init = true, i = last;; i--, init = false) {
|
|||
|
|
if (checkRange(bytes, first, last, i >= first,
|
|||
|
|
reversed, reversed, init, i)) {
|
|||
|
|
break;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private boolean checkRange(byte[][] bytes, int first, int last,
|
|||
|
|
boolean inRange, boolean reversed,
|
|||
|
|
boolean forward, boolean init,
|
|||
|
|
int i)
|
|||
|
|
throws DatabaseException {
|
|||
|
|
|
|||
|
|
OperationStatus s;
|
|||
|
|
if (forward) {
|
|||
|
|
if (init) {
|
|||
|
|
s = cursor.getFirst(false);
|
|||
|
|
} else {
|
|||
|
|
s = cursor.getNext(false);
|
|||
|
|
}
|
|||
|
|
} else {
|
|||
|
|
if (init) {
|
|||
|
|
s = cursor.getLast(false);
|
|||
|
|
} else {
|
|||
|
|
s = cursor.getPrev(false);
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
String msg = " " + (forward ? "next" : "prev") + " i=" + i +
|
|||
|
|
" first=" + first + " last=" + last +
|
|||
|
|
(reversed ? " reversed" : " not reversed");
|
|||
|
|
|
|||
|
|
// check that moving past ends doesn't move the cursor
|
|||
|
|
if (s == OperationStatus.SUCCESS && i == first) {
|
|||
|
|
OperationStatus s2 = reversed ? cursor.getNext(false)
|
|||
|
|
: cursor.getPrev(false);
|
|||
|
|
assertEquals(msg, OperationStatus.NOTFOUND, s2);
|
|||
|
|
}
|
|||
|
|
if (s == OperationStatus.SUCCESS && i == last) {
|
|||
|
|
OperationStatus s2 = reversed ? cursor.getPrev(false)
|
|||
|
|
: cursor.getNext(false);
|
|||
|
|
assertEquals(msg, OperationStatus.NOTFOUND, s2);
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
byte[] val = (s == OperationStatus.SUCCESS)
|
|||
|
|
? ((byte[]) cursor.getCurrentValue())
|
|||
|
|
: null;
|
|||
|
|
|
|||
|
|
if (inRange) {
|
|||
|
|
assertNotNull("RangeNotFound" + msg, val);
|
|||
|
|
|
|||
|
|
if (!Arrays.equals(val, bytes[i])){
|
|||
|
|
printBytes(val);
|
|||
|
|
printBytes(bytes[i]);
|
|||
|
|
fail("RangeKeyNotEqual" + msg);
|
|||
|
|
}
|
|||
|
|
if (VERBOSE) {
|
|||
|
|
System.out.println("GotRange" + msg);
|
|||
|
|
}
|
|||
|
|
return false;
|
|||
|
|
} else {
|
|||
|
|
assertEquals("RangeExceeded" + msg, OperationStatus.NOTFOUND, s);
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
private void printBytes(byte[] bytes) {
|
|||
|
|
|
|||
|
|
for (int i = 0; i < bytes.length; i += 1) {
|
|||
|
|
System.out.print(Integer.toHexString(bytes[i] & 0xFF));
|
|||
|
|
System.out.print(' ');
|
|||
|
|
}
|
|||
|
|
System.out.println();
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
@Test
|
|||
|
|
public void testSubRanges() {
|
|||
|
|
|
|||
|
|
DatabaseEntry begin = new DatabaseEntry();
|
|||
|
|
DatabaseEntry begin2 = new DatabaseEntry();
|
|||
|
|
DatabaseEntry end = new DatabaseEntry();
|
|||
|
|
DatabaseEntry end2 = new DatabaseEntry();
|
|||
|
|
KeyRange range = new KeyRange(null);
|
|||
|
|
KeyRange range2 = null;
|
|||
|
|
|
|||
|
|
/* Base range [1, 2] */
|
|||
|
|
begin.setData(new byte[] { 1 });
|
|||
|
|
end.setData(new byte[] { 2 });
|
|||
|
|
range = range.subRange(begin, true, end, true);
|
|||
|
|
|
|||
|
|
/* Subrange (0, 1] is invalid **. */
|
|||
|
|
begin2.setData(new byte[] { 0 });
|
|||
|
|
end2.setData(new byte[] { 1 });
|
|||
|
|
try {
|
|||
|
|
range2 = range.subRange(begin2, false, end2, true);
|
|||
|
|
fail();
|
|||
|
|
} catch (KeyRangeException expected) {}
|
|||
|
|
|
|||
|
|
/* Subrange [1, 3) is invalid. */
|
|||
|
|
begin2.setData(new byte[] { 1 });
|
|||
|
|
end2.setData(new byte[] { 3 });
|
|||
|
|
try {
|
|||
|
|
range2 = range.subRange(begin2, true, end2, false);
|
|||
|
|
fail();
|
|||
|
|
} catch (KeyRangeException expected) {}
|
|||
|
|
|
|||
|
|
/* Subrange [2, 2] is valid. */
|
|||
|
|
begin2.setData(new byte[] { 2 });
|
|||
|
|
end2.setData(new byte[] { 2 });
|
|||
|
|
range2 = range.subRange(begin2, true, end2, true);
|
|||
|
|
|
|||
|
|
/* Subrange [0, 1] is invalid. */
|
|||
|
|
begin2.setData(new byte[] { 0 });
|
|||
|
|
end2.setData(new byte[] { 1 });
|
|||
|
|
try {
|
|||
|
|
range2 = range.subRange(begin2, true, end2, true);
|
|||
|
|
fail();
|
|||
|
|
} catch (KeyRangeException expected) {}
|
|||
|
|
|
|||
|
|
/* Subrange (0, 3] is invalid. */
|
|||
|
|
begin2.setData(new byte[] { 0 });
|
|||
|
|
end2.setData(new byte[] { 3 });
|
|||
|
|
try {
|
|||
|
|
range2 = range.subRange(begin2, false, end2, true);
|
|||
|
|
fail();
|
|||
|
|
} catch (KeyRangeException expected) {}
|
|||
|
|
|
|||
|
|
/* Subrange [3, 3) is invalid. */
|
|||
|
|
begin2.setData(new byte[] { 3 });
|
|||
|
|
end2.setData(new byte[] { 3 });
|
|||
|
|
try {
|
|||
|
|
range2 = range.subRange(begin2, true, end2, false);
|
|||
|
|
fail();
|
|||
|
|
} catch (KeyRangeException expected) {}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
@SuppressWarnings("serial")
|
|||
|
|
public static class ReverseComparator implements Comparator<byte[]>,
|
|||
|
|
Serializable {
|
|||
|
|
public int compare(byte[] d1, byte[] d2) {
|
|||
|
|
int cmp = KeyRange.compareBytes(d1, 0, d1.length,
|
|||
|
|
d2, 0, d2.length);
|
|||
|
|
if (cmp < 0) {
|
|||
|
|
return 1;
|
|||
|
|
} else if (cmp > 0) {
|
|||
|
|
return -1;
|
|||
|
|
} else {
|
|||
|
|
return 0;
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
}
|