1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2002,2008 Oracle. All rights reserved. 5 * 6 * $Id: KeyRangeTest.java,v 12.9 2008/02/07 17:12:31 mark Exp $ 7 */ 8 9package com.sleepycat.collections; 10 11import java.io.File; 12import java.util.Arrays; 13import java.util.Comparator; 14 15import junit.framework.Test; 16import junit.framework.TestCase; 17import junit.framework.TestSuite; 18 19import com.sleepycat.bind.ByteArrayBinding; 20import com.sleepycat.compat.DbCompat; 21import com.sleepycat.db.Database; 22import com.sleepycat.db.DatabaseConfig; 23import com.sleepycat.db.DatabaseEntry; 24import com.sleepycat.db.DatabaseException; 25import com.sleepycat.db.Environment; 26import com.sleepycat.db.EnvironmentConfig; 27import com.sleepycat.db.OperationStatus; 28import com.sleepycat.util.keyrange.KeyRange; 29import com.sleepycat.util.keyrange.KeyRangeException; 30import com.sleepycat.util.test.SharedTestUtils; 31 32/** 33 * @author Mark Hayes 34 */ 35public class KeyRangeTest extends TestCase { 36 37 private static boolean VERBOSE = false; 38 39 private static final byte FF = (byte) 0xFF; 40 41 private static final byte[][] KEYS = { 42 /* 0 */ {1}, 43 /* 1 */ {FF}, 44 /* 2 */ {FF, 0}, 45 /* 3 */ {FF, 0x7F}, 46 /* 4 */ {FF, FF}, 47 /* 5 */ {FF, FF, 0}, 48 /* 6 */ {FF, FF, 0x7F}, 49 /* 7 */ {FF, FF, FF}, 50 }; 51 private static byte[][] EXTREME_KEY_BYTES = { 52 /* 0 */ {0}, 53 /* 1 */ {FF, FF, FF, FF}, 54 }; 55 56 private Environment env; 57 private Database store; 58 private DataView view; 59 private DataCursor cursor; 60 61 public static void main(String[] args) 62 throws Exception { 63 64 junit.framework.TestResult tr = 65 junit.textui.TestRunner.run(suite()); 66 if (tr.errorCount() > 0 || 67 tr.failureCount() > 0) { 68 System.exit(1); 69 } else { 70 System.exit(0); 71 } 72 } 73 74 public static Test suite() { 75 76 return new TestSuite(KeyRangeTest.class); 77 } 78 79 public KeyRangeTest(String name) { 80 81 super(name); 82 } 83 84 public void setUp() 85 throws Exception { 86 87 SharedTestUtils.printTestName(SharedTestUtils.qualifiedTestName(this)); 88 } 89 90 private void openDb(Comparator comparator) 91 throws Exception { 92 93 File dir = SharedTestUtils.getNewDir(); 94 ByteArrayBinding dataBinding = new ByteArrayBinding(); 95 EnvironmentConfig envConfig = new EnvironmentConfig(); 96 envConfig.setAllowCreate(true); 97 DbCompat.setInitializeCache(envConfig, true); 98 env = new Environment(dir, envConfig); 99 DatabaseConfig dbConfig = new DatabaseConfig(); 100 DbCompat.setTypeBtree(dbConfig); 101 dbConfig.setAllowCreate(true); 102 if (comparator != null) { 103 DbCompat.setBtreeComparator(dbConfig, comparator); 104 } 105 store = DbCompat.testOpenDatabase 106 (env, null, "test.db", null, dbConfig); 107 view = new DataView(store, dataBinding, dataBinding, null, true, null); 108 } 109 110 private void closeDb() 111 throws Exception { 112 113 store.close(); 114 store = null; 115 env.close(); 116 env = null; 117 } 118 119 public void tearDown() 120 throws Exception { 121 122 try { 123 if (store != null) { 124 store.close(); 125 } 126 } catch (Exception e) { 127 System.out.println("Exception ignored during close: " + e); 128 } 129 try { 130 if (env != null) { 131 env.close(); 132 } 133 } catch (Exception e) { 134 System.out.println("Exception ignored during close: " + e); 135 } 136 /* Ensure that GC can cleanup. */ 137 env = null; 138 store = null; 139 view = null; 140 cursor = null; 141 } 142 143 public void testScan() throws Exception { 144 openDb(null); 145 doScan(false); 146 closeDb(); 147 } 148 149 public void testScanComparator() throws Exception { 150 openDb(new ReverseComparator()); 151 doScan(true); 152 closeDb(); 153 } 154 155 private void doScan(boolean reversed) throws Exception { 156 157 byte[][] keys = new byte[KEYS.length][]; 158 final int end = KEYS.length - 1; 159 cursor = new DataCursor(view, true); 160 for (int i = 0; i <= end; i++) { 161 keys[i] = KEYS[i]; 162 cursor.put(keys[i], KEYS[i], null, false); 163 } 164 cursor.close(); 165 byte[][] extremeKeys = new byte[EXTREME_KEY_BYTES.length][]; 166 for (int i = 0; i < extremeKeys.length; i++) { 167 extremeKeys[i] = EXTREME_KEY_BYTES[i]; 168 } 169 170 // with empty range 171 172 cursor = new DataCursor(view, false); 173 expectRange(KEYS, 0, end, reversed); 174 cursor.close(); 175 176 // begin key only, inclusive 177 178 for (int i = 0; i <= end; i++) { 179 cursor = newCursor(view, keys[i], true, null, false, reversed); 180 expectRange(KEYS, i, end, reversed); 181 cursor.close(); 182 } 183 184 // begin key only, exclusive 185 186 for (int i = 0; i <= end; i++) { 187 cursor = newCursor(view, keys[i], false, null, false, reversed); 188 expectRange(KEYS, i + 1, end, reversed); 189 cursor.close(); 190 } 191 192 // end key only, inclusive 193 194 for (int i = 0; i <= end; i++) { 195 cursor = newCursor(view, null, false, keys[i], true, reversed); 196 expectRange(KEYS, 0, i, reversed); 197 cursor.close(); 198 } 199 200 // end key only, exclusive 201 202 for (int i = 0; i <= end; i++) { 203 cursor = newCursor(view, null, false, keys[i], false, reversed); 204 expectRange(KEYS, 0, i - 1, reversed); 205 cursor.close(); 206 } 207 208 // begin and end keys, inclusive and exclusive 209 210 for (int i = 0; i <= end; i++) { 211 for (int j = i; j <= end; j++) { 212 // begin inclusive, end inclusive 213 214 cursor = newCursor(view, keys[i], true, keys[j], 215 true, reversed); 216 expectRange(KEYS, i, j, reversed); 217 cursor.close(); 218 219 // begin inclusive, end exclusive 220 221 cursor = newCursor(view, keys[i], true, keys[j], 222 false, reversed); 223 expectRange(KEYS, i, j - 1, reversed); 224 cursor.close(); 225 226 // begin exclusive, end inclusive 227 228 cursor = newCursor(view, keys[i], false, keys[j], 229 true, reversed); 230 expectRange(KEYS, i + 1, j, reversed); 231 cursor.close(); 232 233 // begin exclusive, end exclusive 234 235 cursor = newCursor(view, keys[i], false, keys[j], 236 false, reversed); 237 expectRange(KEYS, i + 1, j - 1, reversed); 238 cursor.close(); 239 } 240 } 241 242 // single key range 243 244 for (int i = 0; i <= end; i++) { 245 cursor = new DataCursor(view, false, keys[i]); 246 expectRange(KEYS, i, i, reversed); 247 cursor.close(); 248 } 249 250 // start with lower extreme (before any existing key) 251 252 cursor = newCursor(view, extremeKeys[0], true, null, false, reversed); 253 expectRange(KEYS, 0, end, reversed); 254 cursor.close(); 255 256 // start with higher extreme (after any existing key) 257 258 cursor = newCursor(view, null, false, extremeKeys[1], true, reversed); 259 expectRange(KEYS, 0, end, reversed); 260 cursor.close(); 261 } 262 263 private DataCursor newCursor(DataView view, 264 Object beginKey, boolean beginInclusive, 265 Object endKey, boolean endInclusive, 266 boolean reversed) 267 throws Exception { 268 269 if (reversed) { 270 return new DataCursor(view, false, 271 endKey, endInclusive, 272 beginKey, beginInclusive); 273 } else { 274 return new DataCursor(view, false, 275 beginKey, beginInclusive, 276 endKey, endInclusive); 277 } 278 } 279 280 private void expectRange(byte[][] bytes, int first, int last, 281 boolean reversed) 282 throws DatabaseException { 283 284 int i; 285 boolean init; 286 for (init = true, i = first;; i++, init = false) { 287 if (checkRange(bytes, first, last, i <= last, 288 reversed, !reversed, init, i)) { 289 break; 290 } 291 } 292 for (init = true, i = last;; i--, init = false) { 293 if (checkRange(bytes, first, last, i >= first, 294 reversed, reversed, init, i)) { 295 break; 296 } 297 } 298 } 299 300 private boolean checkRange(byte[][] bytes, int first, int last, 301 boolean inRange, boolean reversed, 302 boolean forward, boolean init, 303 int i) 304 throws DatabaseException { 305 306 OperationStatus s; 307 if (forward) { 308 if (init) { 309 s = cursor.getFirst(false); 310 } else { 311 s = cursor.getNext(false); 312 } 313 } else { 314 if (init) { 315 s = cursor.getLast(false); 316 } else { 317 s = cursor.getPrev(false); 318 } 319 } 320 321 String msg = " " + (forward ? "next" : "prev") + " i=" + i + 322 " first=" + first + " last=" + last + 323 (reversed ? " reversed" : " not reversed"); 324 325 // check that moving past ends doesn't move the cursor 326 if (s == OperationStatus.SUCCESS && i == first) { 327 OperationStatus s2 = reversed ? cursor.getNext(false) 328 : cursor.getPrev(false); 329 assertEquals(msg, OperationStatus.NOTFOUND, s2); 330 } 331 if (s == OperationStatus.SUCCESS && i == last) { 332 OperationStatus s2 = reversed ? cursor.getPrev(false) 333 : cursor.getNext(false); 334 assertEquals(msg, OperationStatus.NOTFOUND, s2); 335 } 336 337 byte[] val = (s == OperationStatus.SUCCESS) 338 ? ((byte[]) cursor.getCurrentValue()) 339 : null; 340 341 if (inRange) { 342 assertNotNull("RangeNotFound" + msg, val); 343 344 if (!Arrays.equals(val, bytes[i])){ 345 printBytes(val); 346 printBytes(bytes[i]); 347 fail("RangeKeyNotEqual" + msg); 348 } 349 if (VERBOSE) { 350 System.out.println("GotRange" + msg); 351 } 352 return false; 353 } else { 354 assertEquals("RangeExceeded" + msg, OperationStatus.NOTFOUND, s); 355 return true; 356 } 357 } 358 359 private void printBytes(byte[] bytes) { 360 361 for (int i = 0; i < bytes.length; i += 1) { 362 System.out.print(Integer.toHexString(bytes[i] & 0xFF)); 363 System.out.print(' '); 364 } 365 System.out.println(); 366 } 367 368 public void testSubRanges() { 369 370 DatabaseEntry begin = new DatabaseEntry(); 371 DatabaseEntry begin2 = new DatabaseEntry(); 372 DatabaseEntry end = new DatabaseEntry(); 373 DatabaseEntry end2 = new DatabaseEntry(); 374 KeyRange range = new KeyRange(null); 375 KeyRange range2; 376 377 /* Base range [1, 2] */ 378 begin.setData(new byte[] { 1 }); 379 end.setData(new byte[] { 2 }); 380 range = range.subRange(begin, true, end, true); 381 382 /* Subrange (0, 1] is invalid **. */ 383 begin2.setData(new byte[] { 0 }); 384 end2.setData(new byte[] { 1 }); 385 try { 386 range2 = range.subRange(begin2, false, end2, true); 387 fail(); 388 } catch (KeyRangeException expected) {} 389 390 /* Subrange [1, 3) is invalid. */ 391 begin2.setData(new byte[] { 1 }); 392 end2.setData(new byte[] { 3 }); 393 try { 394 range2 = range.subRange(begin2, true, end2, false); 395 fail(); 396 } catch (KeyRangeException expected) {} 397 398 /* Subrange [2, 2] is valid. */ 399 begin2.setData(new byte[] { 2 }); 400 end2.setData(new byte[] { 2 }); 401 range2 = range.subRange(begin2, true, end2, true); 402 403 /* Subrange [0, 1] is invalid. */ 404 begin2.setData(new byte[] { 0 }); 405 end2.setData(new byte[] { 1 }); 406 try { 407 range2 = range.subRange(begin2, true, end2, true); 408 fail(); 409 } catch (KeyRangeException expected) {} 410 411 /* Subrange (0, 3] is invalid. */ 412 begin2.setData(new byte[] { 0 }); 413 end2.setData(new byte[] { 3 }); 414 try { 415 range2 = range.subRange(begin2, false, end2, true); 416 fail(); 417 } catch (KeyRangeException expected) {} 418 419 /* Subrange [3, 3) is invalid. */ 420 begin2.setData(new byte[] { 3 }); 421 end2.setData(new byte[] { 3 }); 422 try { 423 range2 = range.subRange(begin2, true, end2, false); 424 fail(); 425 } catch (KeyRangeException expected) {} 426 } 427 428 public static class ReverseComparator implements Comparator { 429 public int compare(Object o1, Object o2) { 430 byte[] d1 = (byte[]) o1; 431 byte[] d2 = (byte[]) o2; 432 int cmp = KeyRange.compareBytes(d1, 0, d1.length, 433 d2, 0, d2.length); 434 if (cmp < 0) { 435 return 1; 436 } else if (cmp > 0) { 437 return -1; 438 } else { 439 return 0; 440 } 441 } 442 } 443} 444