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