1 // Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
2 //  This source code is licensed under both the GPLv2 (found in the
3 //  COPYING file in the root directory) and Apache 2.0 License
4 //  (found in the LICENSE.Apache file in the root directory).
5 
6 package org.rocksdb.util;
7 
8 import org.rocksdb.*;
9 
10 import java.nio.ByteBuffer;
11 
12 import static org.rocksdb.util.ByteUtil.memcmp;
13 
14 /**
15  * This is a Java Native implementation of the C++
16  * equivalent BytewiseComparatorImpl using {@link Slice}
17  *
18  * The performance of Comparators implemented in Java is always
19  * less than their C++ counterparts due to the bridging overhead,
20  * as such you likely don't want to use this apart from benchmarking
21  * and you most likely instead wanted
22  * {@link org.rocksdb.BuiltinComparator#BYTEWISE_COMPARATOR}
23  */
24 public final class BytewiseComparator extends AbstractComparator {
25 
BytewiseComparator(final ComparatorOptions copt)26   public BytewiseComparator(final ComparatorOptions copt) {
27     super(copt);
28   }
29 
30   @Override
name()31   public String name() {
32     return "rocksdb.java.BytewiseComparator";
33   }
34 
35   @Override
compare(final ByteBuffer a, final ByteBuffer b)36   public int compare(final ByteBuffer a, final ByteBuffer b) {
37     return _compare(a, b);
38   }
39 
_compare(final ByteBuffer a, final ByteBuffer b)40   static int _compare(final ByteBuffer a, final ByteBuffer b) {
41     assert(a != null && b != null);
42     final int minLen = a.remaining() < b.remaining() ?
43         a.remaining() : b.remaining();
44     int r = memcmp(a, b, minLen);
45     if (r == 0) {
46       if (a.remaining() < b.remaining()) {
47         r = -1;
48       } else if (a.remaining() > b.remaining()) {
49         r = +1;
50       }
51     }
52     return r;
53   }
54 
55   @Override
56   public void findShortestSeparator(final ByteBuffer start,
57       final ByteBuffer limit) {
58     // Find length of common prefix
59     final int minLength = Math.min(start.remaining(), limit.remaining());
60     int diffIndex = 0;
61     while (diffIndex < minLength &&
62         start.get(diffIndex) == limit.get(diffIndex)) {
63       diffIndex++;
64     }
65 
66     if (diffIndex >= minLength) {
67       // Do not shorten if one string is a prefix of the other
68     } else {
69       final int startByte = start.get(diffIndex) & 0xff;
70       final int limitByte = limit.get(diffIndex) & 0xff;
71       if (startByte >= limitByte) {
72         // Cannot shorten since limit is smaller than start or start is
73         // already the shortest possible.
74         return;
75       }
76       assert(startByte < limitByte);
77 
78       if (diffIndex < limit.remaining() - 1 || startByte + 1 < limitByte) {
79         start.put(diffIndex, (byte)((start.get(diffIndex) & 0xff) + 1));
80         start.limit(diffIndex + 1);
81       } else {
82         //     v
83         // A A 1 A A A
84         // A A 2
85         //
86         // Incrementing the current byte will make start bigger than limit, we
87         // will skip this byte, and find the first non 0xFF byte in start and
88         // increment it.
89         diffIndex++;
90 
91         while (diffIndex < start.remaining()) {
92           // Keep moving until we find the first non 0xFF byte to
93           // increment it
94           if ((start.get(diffIndex) & 0xff) <
95               0xff) {
96             start.put(diffIndex, (byte)((start.get(diffIndex) & 0xff) + 1));
97             start.limit(diffIndex + 1);
98             break;
99           }
100           diffIndex++;
101         }
102       }
103       assert(compare(start.duplicate(), limit.duplicate()) < 0);
104     }
105   }
106 
107   @Override
108   public void findShortSuccessor(final ByteBuffer key) {
109     // Find first character that can be incremented
110     final int n = key.remaining();
111     for (int i = 0; i < n; i++) {
112       final int byt = key.get(i) & 0xff;
113       if (byt != 0xff) {
114         key.put(i, (byte)(byt + 1));
115         key.limit(i+1);
116         return;
117       }
118     }
119     // *key is a run of 0xffs.  Leave it alone.
120   }
121 }
122