1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.hadoop.hbase;
20
21 import java.io.Serializable;
22 import java.util.Comparator;
23
24 import org.apache.hadoop.hbase.KeyValue.Type;
25 import org.apache.hadoop.hbase.classification.InterfaceAudience;
26 import org.apache.hadoop.hbase.classification.InterfaceStability;
27 import org.apache.hadoop.hbase.util.Bytes;
28
29 import com.google.common.primitives.Longs;
30
31
32
33
34
35
36
37
38 @edu.umd.cs.findbugs.annotations.SuppressWarnings(
39 value="UNKNOWN",
40 justification="Findbugs doesn't like the way we are negating the result of a compare in below")
41 @InterfaceAudience.Private
42 @InterfaceStability.Evolving
43 public class CellComparator implements Comparator<Cell>, Serializable {
44 private static final long serialVersionUID = -8760041766259623329L;
45
46 @Override
47 public int compare(Cell a, Cell b) {
48 return compare(a, b, false);
49 }
50
51
52
53
54
55
56
57
58
59
60
61 public static int compare(final Cell a, final Cell b, boolean ignoreSequenceid) {
62
63 int c = compareRows(a, b);
64 if (c != 0) return c;
65
66 c = compareWithoutRow(a, b);
67 if(c != 0) return c;
68
69 if (!ignoreSequenceid) {
70
71
72 return Longs.compare(b.getMvccVersion(), a.getMvccVersion());
73 } else {
74 return c;
75 }
76 }
77
78 public static int findCommonPrefixInRowPart(Cell left, Cell right, int rowCommonPrefix) {
79 return findCommonPrefix(left.getRowArray(), right.getRowArray(), left.getRowLength()
80 - rowCommonPrefix, right.getRowLength() - rowCommonPrefix, left.getRowOffset()
81 + rowCommonPrefix, right.getRowOffset() + rowCommonPrefix);
82 }
83
84 private static int findCommonPrefix(byte[] left, byte[] right, int leftLength, int rightLength,
85 int leftOffset, int rightOffset) {
86 int length = Math.min(leftLength, rightLength);
87 int result = 0;
88
89 while (result < length && left[leftOffset + result] == right[rightOffset + result]) {
90 result++;
91 }
92 return result;
93 }
94
95 public static int findCommonPrefixInFamilyPart(Cell left, Cell right, int familyCommonPrefix) {
96 return findCommonPrefix(left.getFamilyArray(), right.getFamilyArray(), left.getFamilyLength()
97 - familyCommonPrefix, right.getFamilyLength() - familyCommonPrefix, left.getFamilyOffset()
98 + familyCommonPrefix, right.getFamilyOffset() + familyCommonPrefix);
99 }
100
101 public static int findCommonPrefixInQualifierPart(Cell left, Cell right,
102 int qualifierCommonPrefix) {
103 return findCommonPrefix(left.getQualifierArray(), right.getQualifierArray(),
104 left.getQualifierLength() - qualifierCommonPrefix, right.getQualifierLength()
105 - qualifierCommonPrefix, left.getQualifierOffset() + qualifierCommonPrefix,
106 right.getQualifierOffset() + qualifierCommonPrefix);
107 }
108
109
110
111 public static boolean equals(Cell a, Cell b){
112 return equalsRow(a, b)
113 && equalsFamily(a, b)
114 && equalsQualifier(a, b)
115 && equalsTimestamp(a, b)
116 && equalsType(a, b);
117 }
118
119 public static boolean equalsRow(Cell a, Cell b){
120 return Bytes.equals(
121 a.getRowArray(), a.getRowOffset(), a.getRowLength(),
122 b.getRowArray(), b.getRowOffset(), b.getRowLength());
123 }
124
125 public static boolean equalsFamily(Cell a, Cell b){
126 return Bytes.equals(
127 a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(),
128 b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength());
129 }
130
131 public static boolean equalsQualifier(Cell a, Cell b){
132 return Bytes.equals(
133 a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(),
134 b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength());
135 }
136
137 public static boolean equalsTimestamp(Cell a, Cell b){
138 return a.getTimestamp() == b.getTimestamp();
139 }
140
141 public static boolean equalsType(Cell a, Cell b){
142 return a.getTypeByte() == b.getTypeByte();
143 }
144
145 public static int compareColumns(final Cell left, final Cell right) {
146 int lfoffset = left.getFamilyOffset();
147 int rfoffset = right.getFamilyOffset();
148 int lclength = left.getQualifierLength();
149 int rclength = right.getQualifierLength();
150 int lfamilylength = left.getFamilyLength();
151 int rfamilylength = right.getFamilyLength();
152 int diff = compare(left.getFamilyArray(), lfoffset, lfamilylength, right.getFamilyArray(),
153 rfoffset, rfamilylength);
154 if (diff != 0) {
155 return diff;
156 } else {
157 return compare(left.getQualifierArray(), left.getQualifierOffset(), lclength,
158 right.getQualifierArray(), right.getQualifierOffset(), rclength);
159 }
160 }
161
162 public static int compareFamilies(Cell left, Cell right) {
163 return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(),
164 right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
165 }
166
167 public static int compareQualifiers(Cell left, Cell right) {
168 return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
169 left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
170 right.getQualifierLength());
171 }
172
173 public final static int compareQualifiers(Cell left, byte[] right, int rOffset, int rLength) {
174 return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(),
175 left.getQualifierLength(), right, rOffset, rLength);
176 }
177
178 public int compareFlatKey(Cell left, Cell right) {
179 int compare = compareRows(left, right);
180 if (compare != 0) {
181 return compare;
182 }
183 return compareWithoutRow(left, right);
184 }
185
186
187
188
189
190 public static int compareRows(final Cell left, final Cell right) {
191 return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
192 right.getRowArray(), right.getRowOffset(), right.getRowLength());
193 }
194
195
196
197
198
199 public static int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset,
200 int rlength) {
201 return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
202 }
203
204 public static int compareWithoutRow(final Cell leftCell, final Cell rightCell) {
205
206
207
208
209
210
211
212 if (leftCell.getFamilyLength() + leftCell.getQualifierLength() == 0
213 && leftCell.getTypeByte() == Type.Minimum.getCode()) {
214
215 return 1;
216 }
217 if (rightCell.getFamilyLength() + rightCell.getQualifierLength() == 0
218 && rightCell.getTypeByte() == Type.Minimum.getCode()) {
219 return -1;
220 }
221 boolean sameFamilySize = (leftCell.getFamilyLength() == rightCell.getFamilyLength());
222 if (!sameFamilySize) {
223
224
225 return Bytes.compareTo(leftCell.getFamilyArray(), leftCell.getFamilyOffset(),
226 leftCell.getFamilyLength(), rightCell.getFamilyArray(), rightCell.getFamilyOffset(),
227 rightCell.getFamilyLength());
228 }
229 int diff = compareColumns(leftCell, rightCell);
230 if (diff != 0) return diff;
231
232 diff = compareTimestamps(leftCell, rightCell);
233 if (diff != 0) return diff;
234
235
236
237
238
239 return (0xff & rightCell.getTypeByte()) - (0xff & leftCell.getTypeByte());
240 }
241
242 public static int compareTimestamps(final Cell left, final Cell right) {
243 return compareTimestamps(left.getTimestamp(), right.getTimestamp());
244 }
245
246
247
248
249
250
251 public static int hashCode(Cell cell){
252 if (cell == null) {
253 return 0;
254 }
255
256 int hash = calculateHashForKeyValue(cell);
257 hash = 31 * hash + (int)cell.getMvccVersion();
258 return hash;
259 }
260
261
262
263
264
265
266
267
268 public static int hashCodeIgnoreMvcc(Cell cell) {
269 if (cell == null) {
270 return 0;
271 }
272
273 int hash = calculateHashForKeyValue(cell);
274 return hash;
275 }
276
277 private static int calculateHashForKeyValue(Cell cell) {
278
279 int rowHash = Bytes.hashCode(cell.getRowArray(), cell.getRowOffset(), cell.getRowLength());
280 int familyHash =
281 Bytes.hashCode(cell.getFamilyArray(), cell.getFamilyOffset(), cell.getFamilyLength());
282 int qualifierHash = Bytes.hashCode(cell.getQualifierArray(), cell.getQualifierOffset(),
283 cell.getQualifierLength());
284
285
286 int hash = 31 * rowHash + familyHash;
287 hash = 31 * hash + qualifierHash;
288 hash = 31 * hash + (int)cell.getTimestamp();
289 hash = 31 * hash + cell.getTypeByte();
290 return hash;
291 }
292
293
294
295
296 public static boolean areKeyLengthsEqual(Cell a, Cell b) {
297 return a.getRowLength() == b.getRowLength()
298 && a.getFamilyLength() == b.getFamilyLength()
299 && a.getQualifierLength() == b.getQualifierLength();
300 }
301
302 public static boolean areRowLengthsEqual(Cell a, Cell b) {
303 return a.getRowLength() == b.getRowLength();
304 }
305
306
307
308
309 private static int compare(byte[] left, int leftOffset, int leftLength, byte[] right,
310 int rightOffset, int rightLength) {
311 return Bytes.compareTo(left, leftOffset, leftLength, right, rightOffset, rightLength);
312 }
313
314 public static int compareCommonRowPrefix(Cell left, Cell right, int rowCommonPrefix) {
315 return compare(left.getRowArray(), left.getRowOffset() + rowCommonPrefix, left.getRowLength()
316 - rowCommonPrefix, right.getRowArray(), right.getRowOffset() + rowCommonPrefix,
317 right.getRowLength() - rowCommonPrefix);
318 }
319
320 public static int compareCommonFamilyPrefix(Cell left, Cell right,
321 int familyCommonPrefix) {
322 return compare(left.getFamilyArray(), left.getFamilyOffset() + familyCommonPrefix,
323 left.getFamilyLength() - familyCommonPrefix, right.getFamilyArray(),
324 right.getFamilyOffset() + familyCommonPrefix,
325 right.getFamilyLength() - familyCommonPrefix);
326 }
327
328 public static int compareCommonQualifierPrefix(Cell left, Cell right,
329 int qualCommonPrefix) {
330 return compare(left.getQualifierArray(), left.getQualifierOffset() + qualCommonPrefix,
331 left.getQualifierLength() - qualCommonPrefix, right.getQualifierArray(),
332 right.getQualifierOffset() + qualCommonPrefix, right.getQualifierLength()
333 - qualCommonPrefix);
334 }
335
336
337
338
339
340 public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){
341 return 0 == compareStaticIgnoreMvccVersion(a, b);
342 }
343
344 private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) {
345
346 int c = compareRows(a, b);
347 if (c != 0) return c;
348
349
350 c = compareColumns(a, b);
351 if (c != 0) return c;
352
353
354 c = compareTimestamps(a, b);
355 if (c != 0) return c;
356
357
358 c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte());
359 return c;
360 }
361
362 public static int compareTimestamps(final long ltimestamp, final long rtimestamp) {
363
364
365
366
367 if (ltimestamp < rtimestamp) {
368 return 1;
369 } else if (ltimestamp > rtimestamp) {
370 return -1;
371 }
372 return 0;
373 }
374
375
376
377
378 public static class RowComparator extends CellComparator {
379 @Override
380 public int compare(Cell a, Cell b) {
381 return compareRows(a, b);
382 }
383 }
384
385
386
387
388
389
390
391
392
393
394
395 public static Cell getMidpoint(final KeyValue.KVComparator comparator, final Cell left,
396 final Cell right) {
397
398
399 if (right == null) {
400 throw new IllegalArgumentException("right cell can not be null");
401 }
402 if (left == null) {
403 return right;
404 }
405
406
407
408 if (comparator != null && comparator instanceof KeyValue.MetaComparator) {
409 return right;
410 }
411 int diff = compareRows(left, right);
412 if (diff > 0) {
413 throw new IllegalArgumentException("Left row sorts after right row; left=" +
414 CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
415 }
416 if (diff < 0) {
417
418 byte [] midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
419 left.getRowLength(),
420 right.getRowArray(), right.getRowOffset(), right.getRowLength());
421
422 if (midRow == null) return right;
423 return CellUtil.createCell(midRow);
424 }
425
426 diff = compareFamilies(left, right);
427 if (diff > 0) {
428 throw new IllegalArgumentException("Left family sorts after right family; left=" +
429 CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
430 }
431 if (diff < 0) {
432 byte [] midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
433 left.getFamilyLength(),
434 right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength());
435
436 if (midRow == null) return right;
437
438 return CellUtil.createCell(right.getRowArray(), right.getRowOffset(), right.getRowLength(),
439 midRow, 0, midRow.length, HConstants.EMPTY_BYTE_ARRAY, 0,
440 HConstants.EMPTY_BYTE_ARRAY.length);
441 }
442
443 diff = compareQualifiers(left, right);
444 if (diff > 0) {
445 throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left=" +
446 CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
447 }
448 if (diff < 0) {
449 byte [] midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
450 left.getQualifierLength(),
451 right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength());
452
453 if (midRow == null) return right;
454
455 return CellUtil.createCell(right.getRowArray(), right.getRowOffset(), right.getRowLength(),
456 right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength(),
457 midRow, 0, midRow.length);
458 }
459
460 return right;
461 }
462
463
464
465
466
467
468
469
470
471
472
473 private static byte [] getMinimumMidpointArray(final byte [] leftArray, final int leftOffset,
474 final int leftLength,
475 final byte [] rightArray, final int rightOffset, final int rightLength) {
476
477 int minLength = leftLength < rightLength ? leftLength : rightLength;
478 int diffIdx = 0;
479 while (diffIdx < minLength &&
480 leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
481 diffIdx++;
482 }
483 byte [] minimumMidpointArray = null;
484 if (diffIdx >= minLength) {
485
486 minimumMidpointArray = new byte[diffIdx + 1];
487 System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
488 } else {
489 int diffByte = leftArray[leftOffset + diffIdx];
490 if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
491 minimumMidpointArray = new byte[diffIdx + 1];
492 System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
493 minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
494 } else {
495 minimumMidpointArray = new byte[diffIdx + 1];
496 System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
497 }
498 }
499 return minimumMidpointArray;
500 }
501 }