1 /*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2002, 2014 Oracle and/or its affiliates. All rights reserved. 5 * 6 */ 7 8 package com.sleepycat.je.dbi; 9 10 import java.util.Comparator; 11 12 import com.sleepycat.je.DatabaseEntry; 13 import com.sleepycat.je.tree.Key; 14 import com.sleepycat.je.tree.LN; 15 import com.sleepycat.util.PackedInteger; 16 17 /** 18 * Utility methods for combining, splitting and comparing two-part key values 19 * for duplicates databases. 20 * 21 * At the Btree storage level, for the key/data pairs in a duplicates database, 22 * the data is always zero length and the key is a two-part key. The 'key' 23 * parameter in the API is the first part of the key. The the 'data' parameter 24 * in the API is the second part of the key. 25 * 26 * The length of the first part is stored at the end of the combined key as a 27 * packed integer, so that the two parts can be split, combined, and compared 28 * separately. The length is stored at the end, rather than the start, to 29 * enable key prefixing for the first part, e.g., for Strings with different 30 * lengths but common prefixes. 31 */ 32 public class DupKeyData { 33 34 private static final int PREFIX_ONLY = -1; 35 36 /** 37 * Returns twoPartKey as: 38 * paramKey bytes, 39 * paramData bytes, 40 * reverse-packed len of paramKey bytes. 41 * 42 * The byte array in the resulting twoPartKey will be copied again by JE at 43 * a lower level. It would be nice if there were a way to give ownership 44 * of the array to JE, to avoid the extra copy. 45 */ combine(final DatabaseEntry paramKey, final DatabaseEntry paramData)46 public static DatabaseEntry combine(final DatabaseEntry paramKey, 47 final DatabaseEntry paramData) { 48 final byte[] buf = combine 49 (paramKey.getData(), paramKey.getOffset(), paramKey.getSize(), 50 paramData.getData(), paramData.getOffset(), paramData.getSize()); 51 return new DatabaseEntry(buf); 52 } 53 combine(final byte[] key, final byte[] data)54 public static byte[] combine(final byte[] key, final byte[] data) { 55 return combine(key, 0, key.length, data, 0, data.length); 56 } 57 combine(final byte[] key, final int keyOff, final int keySize, final byte[] data, final int dataOff, final int dataSize)58 public static byte[] combine(final byte[] key, 59 final int keyOff, 60 final int keySize, 61 final byte[] data, 62 final int dataOff, 63 final int dataSize) { 64 final int keySizeLen = PackedInteger.getWriteIntLength(keySize); 65 final byte[] buf = new byte[keySizeLen + keySize + dataSize]; 66 System.arraycopy(key, keyOff, buf, 0, keySize); 67 System.arraycopy(data, dataOff, buf, keySize, dataSize); 68 final int nextOff = 69 PackedInteger.writeReverseInt(buf, keySize + dataSize, keySize); 70 assert nextOff == buf.length; 71 return buf; 72 } 73 74 /** 75 * Splits twoPartKey, previously set by combine, into original paramKey and 76 * paramData if they are non-null. 77 * 78 * The offset of the twoPartKey must be zero. This can be assumed because 79 * the entry is read from the database and JE always returns entries with a 80 * zero offset. 81 * 82 * This method copies the bytes into to new arrays rather than using the 83 * DatabaseEntry offset and size to shared the array, to keep with the 84 * convention that JE always returns whole arrays. It would be nice to 85 * avoid the copy, but that might break user apps. 86 */ split(final DatabaseEntry twoPartKey, final DatabaseEntry paramKey, final DatabaseEntry paramData)87 public static void split(final DatabaseEntry twoPartKey, 88 final DatabaseEntry paramKey, 89 final DatabaseEntry paramData) { 90 assert twoPartKey.getOffset() == 0; 91 split(twoPartKey.getData(), twoPartKey.getSize(), paramKey, paramData); 92 } 93 94 /** 95 * Same as split method above, but with twoPartKey/twoPartKeySize byte 96 * array and array size params. 97 */ split(final byte[] twoPartKey, final int twoPartKeySize, final DatabaseEntry paramKey, final DatabaseEntry paramData)98 public static void split(final byte[] twoPartKey, 99 final int twoPartKeySize, 100 final DatabaseEntry paramKey, 101 final DatabaseEntry paramData) { 102 final int keySize = 103 PackedInteger.readReverseInt(twoPartKey, twoPartKeySize - 1); 104 assert keySize != PREFIX_ONLY; 105 106 if (paramKey != null) { 107 final byte[] keyBuf = new byte[keySize]; 108 System.arraycopy(twoPartKey, 0, keyBuf, 0, keySize); 109 110 if (keySize == 0 || paramKey.getPartial()) { 111 LN.setEntry(paramKey, keyBuf); 112 } else { 113 paramKey.setData(keyBuf, 0, keySize); 114 } 115 } 116 117 if (paramData != null) { 118 final int keySizeLen = 119 PackedInteger.getReadIntLength(twoPartKey, twoPartKeySize - 1); 120 121 final int dataSize = twoPartKeySize - keySize - keySizeLen; 122 final byte[] dataBuf = new byte[dataSize]; 123 System.arraycopy(twoPartKey, keySize, dataBuf, 0, dataSize); 124 125 if (dataSize == 0 || paramData.getPartial()) { 126 LN.setEntry(paramData, dataBuf); 127 } else { 128 paramData.setData(dataBuf, 0, dataSize); 129 } 130 } 131 } 132 133 /** 134 * Splits twoPartKey and returns a two-part key entry containing the key 135 * portion of twoPartKey combined with newData. 136 */ replaceData(final byte[] twoPartKey, final byte[] newData)137 public static byte[] replaceData(final byte[] twoPartKey, 138 final byte[] newData) { 139 final int origKeySize = 140 PackedInteger.readReverseInt(twoPartKey, twoPartKey.length - 1); 141 final int keySize = (origKeySize == PREFIX_ONLY) ? 142 (twoPartKey.length - 1) : 143 origKeySize; 144 return combine(twoPartKey, 0, keySize, newData, 0, newData.length); 145 } 146 147 /** 148 * Splits twoPartKey and returns a two-part key entry containing the key 149 * portion from twoPartKey, no data, and the special PREFIX_ONLY value for 150 * the key length. When used for a search, this will compare as less than 151 * any other entry having the same first part, i.e., in the same duplicate 152 * set. 153 */ removeData(final byte[] twoPartKey)154 public static DatabaseEntry removeData(final byte[] twoPartKey) { 155 final int keySize = 156 PackedInteger.readReverseInt(twoPartKey, twoPartKey.length - 1); 157 assert keySize != PREFIX_ONLY; 158 return new DatabaseEntry(makePrefixKey(twoPartKey, 0, keySize)); 159 } 160 161 /** 162 * Returns a two-part key entry with the given key portion, no data, and 163 * the special PREFIX_ONLY value for the key length. When used for a 164 * search, this will compare as less than any other entry having the same 165 * first part, i.e., in the same duplicate set. 166 */ makePrefixKey(final byte[] key, final int keyOff, final int keySize)167 public static byte[] makePrefixKey(final byte[] key, 168 final int keyOff, 169 final int keySize) { 170 final byte[] buf = new byte[keySize + 1]; 171 System.arraycopy(key, 0, buf, 0, keySize); 172 buf[keySize] = (byte) PREFIX_ONLY; 173 return buf; 174 } 175 176 /** 177 * Comparator that compares the combined key/data two-part key, calling the 178 * user-defined btree and duplicate comparator as needed. 179 */ 180 public static class TwoPartKeyComparator implements Comparator<byte[]> { 181 182 private final Comparator<byte[]> btreeComparator; 183 private final Comparator<byte[]> duplicateComparator; 184 TwoPartKeyComparator(final Comparator<byte[]> btreeComparator, final Comparator<byte[]> dupComparator)185 public TwoPartKeyComparator(final Comparator<byte[]> btreeComparator, 186 final Comparator<byte[]> dupComparator) { 187 this.btreeComparator = btreeComparator; 188 this.duplicateComparator = dupComparator; 189 } 190 compare(final byte[] twoPartKey1, final byte[] twoPartKey2)191 public int compare(final byte[] twoPartKey1, 192 final byte[] twoPartKey2) { 193 194 /* Compare key portion. */ 195 final int origKeySize1 = PackedInteger.readReverseInt 196 (twoPartKey1, twoPartKey1.length - 1); 197 198 final int keySize1 = (origKeySize1 == PREFIX_ONLY) ? 199 (twoPartKey1.length - 1) : 200 origKeySize1; 201 202 final int origKeySize2 = PackedInteger.readReverseInt 203 (twoPartKey2, twoPartKey2.length - 1); 204 205 final int keySize2 = (origKeySize2 == PREFIX_ONLY) ? 206 (twoPartKey2.length - 1) : 207 origKeySize2; 208 209 final int keyCmp; 210 211 if (btreeComparator == null) { 212 keyCmp = Key.compareUnsignedBytes( 213 twoPartKey1, 0, keySize1, twoPartKey2, 0, keySize2); 214 } else { 215 final byte[] key1 = new byte[keySize1]; 216 final byte[] key2 = new byte[keySize2]; 217 System.arraycopy(twoPartKey1, 0, key1, 0, keySize1); 218 System.arraycopy(twoPartKey2, 0, key2, 0, keySize2); 219 keyCmp = btreeComparator.compare(key1, key2); 220 } 221 222 if (keyCmp != 0) { 223 return keyCmp; 224 } 225 226 if (origKeySize1 == PREFIX_ONLY || origKeySize2 == PREFIX_ONLY) { 227 if (origKeySize1 == origKeySize2) { 228 return 0; 229 } 230 return (origKeySize1 == PREFIX_ONLY) ? -1 : 1; 231 } 232 233 /* Compare data portion. */ 234 final int keySizeLen1 = PackedInteger.getReadIntLength 235 (twoPartKey1, twoPartKey1.length - 1); 236 final int keySizeLen2 = PackedInteger.getReadIntLength 237 (twoPartKey2, twoPartKey2.length - 1); 238 239 final int dataSize1 = twoPartKey1.length - keySize1 - keySizeLen1; 240 final int dataSize2 = twoPartKey2.length - keySize2 - keySizeLen2; 241 242 final int dataCmp; 243 if (duplicateComparator == null) { 244 dataCmp = Key.compareUnsignedBytes 245 (twoPartKey1, keySize1, dataSize1, 246 twoPartKey2, keySize2, dataSize2); 247 } else { 248 final byte[] data1 = new byte[dataSize1]; 249 final byte[] data2 = new byte[dataSize2]; 250 System.arraycopy(twoPartKey1, keySize1, data1, 0, dataSize1); 251 System.arraycopy(twoPartKey2, keySize2, data2, 0, dataSize2); 252 dataCmp = duplicateComparator.compare(data1, data2); 253 } 254 return dataCmp; 255 } 256 } 257 258 /** 259 * Used to perform the getNextNoDup operation. 260 * 261 * Compares the left parameter (the key parameter in a user-initiated 262 * search operation) as: 263 * - less than a right operand with a prefix with is less than the 264 * prefix of the left operand. This is standard. 265 * - greater than a right operand with a prefix with is greater than the 266 * prefix of the left operand. This is standard. 267 * - greater than a right operand with a prefix equal to the prefix of 268 * the left operation. This is non-standard. 269 * 270 * The last property causes the range search to find the first duplicate in 271 * the duplicate set following the duplicate set of the left operand. 272 */ 273 public static class NextNoDupComparator implements Comparator<byte[]> { 274 275 private final Comparator<byte[]> btreeComparator; 276 NextNoDupComparator(final Comparator<byte[]> btreeComparator)277 public NextNoDupComparator(final Comparator<byte[]> btreeComparator) { 278 this.btreeComparator = btreeComparator; 279 } 280 compare(final byte[] twoPartKey1, final byte[] twoPartKey2)281 public int compare(final byte[] twoPartKey1, 282 final byte[] twoPartKey2) { 283 final int cmp = compareMainKey(twoPartKey1, twoPartKey2, 284 btreeComparator); 285 return (cmp != 0) ? cmp : 1; 286 } 287 } 288 289 /** 290 * Used to perform the putNoOverwrite operation. Only used to find the 291 * insertion position in the BIN, after the standard comparator is used to 292 * find the correct BIN for insertion. Because it compares part-one only, 293 * it prevents insertion of a duplicate for the main key given. 294 */ 295 public static class PutNoOverwriteComparator 296 implements Comparator<byte[]> { 297 298 private final Comparator<byte[]> btreeComparator; 299 PutNoOverwriteComparator(final Comparator<byte[]> cmp)300 public PutNoOverwriteComparator(final Comparator<byte[]> cmp) { 301 this.btreeComparator = cmp; 302 } 303 compare(final byte[] twoPartKey1, final byte[] twoPartKey2)304 public int compare(final byte[] twoPartKey1, 305 final byte[] twoPartKey2) { 306 return compareMainKey(twoPartKey1, twoPartKey2, btreeComparator); 307 } 308 } 309 310 /** 311 * Compares the first part of the two keys. 312 */ 313 public static int compareMainKey(final byte[] keyBytes1, final byte[] keyBytes2, final Comparator<byte[]> btreeComparator)314 compareMainKey(final byte[] keyBytes1, 315 final byte[] keyBytes2, 316 final Comparator<byte[]> btreeComparator) { 317 final int origKeySize2 = 318 PackedInteger.readReverseInt(keyBytes2, keyBytes2.length - 1); 319 final int keySize2 = (origKeySize2 == PREFIX_ONLY) ? 320 (keyBytes2.length - 1) : 321 origKeySize2; 322 return compareMainKey(keyBytes1, keyBytes2, 0, keySize2, 323 btreeComparator); 324 } 325 326 /** 327 * Compares the first part of the two keys. 328 */ 329 public static int compareMainKey(final byte[] keyBytes1, final byte[] keyBytes2, final int keyOff2, final int keySize2, final Comparator<byte[]> btreeComparator)330 compareMainKey(final byte[] keyBytes1, 331 final byte[] keyBytes2, 332 final int keyOff2, 333 final int keySize2, 334 final Comparator<byte[]> btreeComparator) { 335 final int origKeySize1 = 336 PackedInteger.readReverseInt(keyBytes1, keyBytes1.length - 1); 337 final int keySize1 = (origKeySize1 == PREFIX_ONLY) ? 338 (keyBytes1.length - 1) : 339 origKeySize1; 340 final int keyCmp; 341 if (btreeComparator == null) { 342 keyCmp = Key.compareUnsignedBytes 343 (keyBytes1, 0, keySize1, 344 keyBytes2, keyOff2, keySize2); 345 } else { 346 final byte[] key1 = new byte[keySize1]; 347 final byte[] key2 = new byte[keySize2]; 348 System.arraycopy(keyBytes1, 0, key1, 0, keySize1); 349 System.arraycopy(keyBytes2, keyOff2, key2, 0, keySize2); 350 keyCmp = btreeComparator.compare(key1, key2); 351 } 352 return keyCmp; 353 } 354 } 355