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.tree;
9 
10 import java.util.Comparator;
11 
12 import com.sleepycat.je.DatabaseEntry;
13 import com.sleepycat.utilint.StringUtils;
14 
15 /**
16  * Key represents a JE B-Tree Key.  Keys are immutable.  Within JE, keys are
17  * usually represented as byte arrays rather than as Key instances in order to
18  * reduce the in-memory footprint. The static methods of this class are used to
19  * operate on the byte arrays.
20  *
21  * One exception is when keys are held within a collection. In that case, Key
22  * objects are instantiated so that keys are hashed and compared by value.
23  */
24 public final class Key implements Comparable<Key> {
25 
26     public abstract static class DumpType {
27 
28         private String name;
29 
DumpType(String name)30         private DumpType(String name) {
31             this.name = name;
32         }
33 
34         public static final DumpType BINARY = new DumpType("BINARY") {
35                 @Override
36                 void dumpByteArrayInternal(StringBuilder sb, byte[] b) {
37                     for (int i = 0; i < b.length; i++) {
38                         sb.append(b[i] & 0xFF).append(" ");
39                     }
40                 }
41             };
42 
43         public static final DumpType HEX = new DumpType("HEX") {
44                 @Override
45                 void dumpByteArrayInternal(StringBuilder sb, byte[] b) {
46                     for (int i = 0; i < b.length; i++) {
47                         sb.append(Integer.toHexString(b[i] & 0xFF)).
48                             append(" ");
49                     }
50                 }
51             };
52 
53         public static final DumpType TEXT = new DumpType("TEXT") {
54                 @Override
55                 void dumpByteArrayInternal(StringBuilder sb, byte[] b) {
56                     sb.append(StringUtils.fromUTF8(b));
57                 }
58             };
59 
60         public static final DumpType OBFUSCATE = new DumpType("OBFUSCATE") {
61                 @Override
62                 void dumpByteArrayInternal(StringBuilder sb, byte[] b) {
63                     int len = b.length;
64                     sb.append("[").append(len).
65                         append(len == 1 ? " byte]" : " bytes]");
66                 }
67             };
68 
dumpByteArray(byte[] b)69         public String dumpByteArray(byte[] b) {
70             StringBuilder sb = new StringBuilder();
71             if (b != null) {
72                 dumpByteArrayInternal(sb, b);
73             } else {
74                 sb.append("null");
75             }
76             return sb.toString();
77         }
78 
79         @Override
toString()80         public String toString() {
81             return name;
82         }
83 
dumpByteArrayInternal(StringBuilder sb, byte[] b)84         abstract void dumpByteArrayInternal(StringBuilder sb, byte[] b);
85     }
86 
87     public static DumpType DUMP_TYPE = DumpType.BINARY;
88 
89     public static final byte[] EMPTY_KEY = new byte[0];
90 
91     private byte[] key;
92 
93     /**
94      * Construct a new key from a byte array.
95      */
Key(byte[] key)96     public Key(byte[] key) {
97         if (key == null) {
98             this.key = null;
99         } else {
100             this.key = new byte[key.length];
101             System.arraycopy(key, 0, this.key, 0, key.length);
102         }
103     }
104 
makeKey(DatabaseEntry dbt)105     public static byte[] makeKey(DatabaseEntry dbt) {
106         byte[] entryKey = dbt.getData();
107         if (entryKey == null) {
108             return EMPTY_KEY;
109         } else {
110             byte[] newKey = new byte[dbt.getSize()];
111             System.arraycopy(entryKey, dbt.getOffset(), newKey,
112                              0, dbt.getSize());
113             return newKey;
114         }
115     }
116 
117     /**
118      * Get the byte array for the key.
119      */
getKey()120     public byte[] getKey() {
121         return key;
122     }
123 
124     /**
125      * Compare two keys.  Standard compareTo function and returns.
126      *
127      * Note that any configured user comparison function is not used, and
128      * therefore this method should not be used for comparison of keys during
129      * Btree operations.
130      */
compareTo(Key argKey)131     public int compareTo(Key argKey) {
132         return compareUnsignedBytes(this.key, argKey.key);
133     }
134 
135     /**
136      * Support Set of Key in BINReference.
137      */
138     @Override
equals(Object o)139     public boolean equals(Object o) {
140         return (o instanceof Key) && (compareTo((Key)o) == 0);
141     }
142 
143     /**
144      * Support HashSet of Key in BINReference.
145      */
146     @Override
hashCode()147     public int hashCode() {
148         int code = 0;
149         for (int i = 0; i < key.length; i += 1) {
150             code += key[i];
151         }
152         return code;
153     }
154 
155     /**
156      * Compare keys with an optional comparator.
157      */
compareKeys(byte[] key1, int off1, int len1, byte[] key2, int off2, int len2, Comparator<byte[]> comparator)158     public static int compareKeys(byte[] key1,
159                                   int off1,
160                                   int len1,
161                                   byte[] key2,
162                                   int off2,
163                                   int len2,
164                                   Comparator<byte[]> comparator) {
165         if (comparator == null) {
166             return compareUnsignedBytes(key1, off1, len1,
167                                         key2, off2, len2);
168         }
169         if (off1 != 0 || len1 != key1.length) {
170             final byte[] b = new byte[len1];
171             System.arraycopy(key1, off1, b, 0, len1);
172             key1 = b;
173         }
174         if (off2 != 0 || len2 != key2.length) {
175             final byte[] b = new byte[len2];
176             System.arraycopy(key2, off2, b, 0, len2);
177             key2 = b;
178         }
179         return comparator.compare(key1, key2);
180     }
181 
182     /**
183      * Compare keys with an optional comparator.
184      */
compareKeys(byte[] key1, byte[] key2, Comparator<byte[]> comparator)185     public static int compareKeys(byte[] key1,
186                                   byte[] key2,
187                                   Comparator<byte[]> comparator) {
188         if (comparator != null) {
189             return comparator.compare(key1, key2);
190         } else {
191             return compareUnsignedBytes(key1, key2);
192         }
193     }
194 
195     /**
196      * Compare keys with an optional comparator.
197      */
compareKeys(DatabaseEntry entry1, DatabaseEntry entry2, Comparator<byte[]> comparator)198     public static int compareKeys(DatabaseEntry entry1,
199                                   DatabaseEntry entry2,
200                                   Comparator<byte[]> comparator) {
201         byte[] key1 = Key.makeKey(entry1);
202         byte[] key2 = Key.makeKey(entry2);
203         if (comparator != null) {
204             return comparator.compare(key1, key2);
205         } else {
206             return compareUnsignedBytes(key1, key2);
207         }
208     }
209 
210     /**
211      * Compare using a default unsigned byte comparison.
212      */
compareUnsignedBytes(byte[] key1, byte[] key2)213     private static int compareUnsignedBytes(byte[] key1, byte[] key2) {
214         return compareUnsignedBytes(key1, 0, key1.length,
215                                     key2, 0, key2.length);
216     }
217 
218     /**
219      * Compare using a default unsigned byte comparison.
220      */
compareUnsignedBytes(byte[] key1, int off1, int len1, byte[] key2, int off2, int len2)221     public static int compareUnsignedBytes(byte[] key1,
222                                            int off1,
223                                            int len1,
224                                            byte[] key2,
225                                            int off2,
226                                            int len2) {
227         int limit = Math.min(len1, len2);
228 
229         for (int i = 0; i < limit; i++) {
230             byte b1 = key1[i + off1];
231             byte b2 = key2[i + off2];
232             if (b1 == b2) {
233                 continue;
234             } else {
235 
236                 /*
237                  * Remember, bytes are signed, so convert to shorts so that we
238                  * effectively do an unsigned byte comparison.
239                  */
240                 return (b1 & 0xff) - (b2 & 0xff);
241             }
242         }
243 
244         return (len1 - len2);
245     }
246 
247     /*
248      * Return the number of leading bytes that key1 and key2 have in common
249      * (i.e. the length of their common prefix).
250      */
getKeyPrefixLength(byte[] key1, int a1Len, byte[] key2)251     public static int getKeyPrefixLength(byte[] key1, int a1Len, byte[] key2) {
252         assert key1 != null && key2 != null;
253 
254         int a2Len = key2.length;
255 
256         int limit = Math.min(a1Len, a2Len);
257 
258         for (int i = 0; i < limit; i++) {
259             byte b1 = key1[i];
260             byte b2 = key2[i];
261             if (b1 != b2) {
262                 return i;
263             }
264         }
265 
266         return limit;
267     }
268 
269     /*
270      * Return a new byte[] containing the common prefix of key1 and key2.
271      * Return null if there is no common prefix.
272      */
createKeyPrefix(byte[] key1, byte[] key2)273     public static byte[] createKeyPrefix(byte[] key1, byte[] key2) {
274         int len = getKeyPrefixLength(key1, key1.length, key2);
275         if (len == 0) {
276             return null;
277         }
278 
279         byte[] ret = new byte[len];
280         System.arraycopy(key1, 0, ret, 0, len);
281 
282         return ret;
283     }
284 
dumpString(byte[] key, int nspaces)285     public static String dumpString(byte[] key, int nspaces) {
286         StringBuilder sb = new StringBuilder();
287         sb.append(TreeUtils.indent(nspaces));
288         sb.append("<key v=\"");
289 
290         if (DUMP_TYPE == DumpType.BINARY ||
291             DUMP_TYPE == DumpType.HEX) {
292             if (key == null) {
293                 sb.append("<null>");
294             } else {
295                 sb.append(DUMP_TYPE.dumpByteArray(key));
296             }
297         } else if (DUMP_TYPE == DumpType.TEXT) {
298             sb.append(key == null ? "" : StringUtils.fromUTF8(key));
299         } else if (DUMP_TYPE == DumpType.OBFUSCATE) {
300             int len = key.length;
301             sb.append("[").append(len).append(len == 1 ? " byte]" : " bytes]");
302         }
303         sb.append("\"/>");
304 
305         return sb.toString();
306     }
307 
308     /**
309      * Print the string w/out XML format.
310      */
getNoFormatString(byte[] key)311     public static String getNoFormatString(byte[] key) {
312         return "key=" + dumpString(key, 0);
313     }
314 }
315