KeyRange


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: KeyRange.java,v 1.4 2006/11/20 22:18:37 cwl Exp $
7    */
8   
9   package com.sleepycat.util.keyrange;
10  
11  import java.util.Comparator  ;
12  
13  import com.sleepycat.je.DatabaseEntry;
14  
15  /**
16   * Encapsulates a key range for use with a RangeCursor.
17   */
18  public class KeyRange {
19  
20      /*
21       * We can return the same byte[] for 0 length arrays.
22       */
23      public static final byte[] ZERO_LENGTH_BYTE_ARRAY = new byte[0];
24  
25      Comparator   comparator;
26      DatabaseEntry beginKey;
27      DatabaseEntry endKey;
28      boolean singleKey;
29      boolean beginInclusive;
30      boolean endInclusive;
31  
32      /**
33       * Creates an unconstrained key range.
34       */
35      public KeyRange(Comparator   comparator) {
36          this.comparator = comparator;
37      }
38  
39      /**
40       * Creates a range for a single key.
41       */
42      public KeyRange subRange(DatabaseEntry key)
43          throws KeyRangeException {
44  
45          if (!check(key)) {
46              throw new KeyRangeException("singleKey out of range");
47          }
48          KeyRange range = new KeyRange(comparator);
49          range.beginKey = key;
50          range.endKey = key;
51          range.beginInclusive = true;
52          range.endInclusive = true;
53          range.singleKey = true;
54          return range;
55      }
56  
57      /**
58       * Creates a range that is the intersection of this range and the given
59       * range parameters.
60       */
61      public KeyRange subRange(DatabaseEntry beginKey, boolean beginInclusive,
62                               DatabaseEntry endKey, boolean endInclusive)
63          throws KeyRangeException {
64  
65          if (beginKey == null) {
66              beginKey = this.beginKey;
67              beginInclusive = this.beginInclusive;
68          } else if (!check(beginKey, beginInclusive)) {
69              throw new KeyRangeException("beginKey out of range");
70          }
71          if (endKey == null) {
72              endKey = this.endKey;
73              endInclusive = this.endInclusive;
74          } else if (!check(endKey, endInclusive)) {
75              throw new KeyRangeException("endKey out of range");
76          }
77          KeyRange range = new KeyRange(comparator);
78          range.beginKey = beginKey;
79          range.endKey = endKey;
80          range.beginInclusive = beginInclusive;
81          range.endInclusive = endInclusive;
82          return range;
83      }
84  
85      /**
86       * Returns whether this is a single-key range.
87       */
88      public final boolean isSingleKey() {
89          return singleKey;
90      }
91  
92      /**
93       * Returns the key of a single-key range, or null if not a single-key
94       * range.
95       */
96      public final DatabaseEntry getSingleKey() {
97  
98          return singleKey ? beginKey : null;
99      }
100 
101     /**
102      * Returns whether this range has a begin or end bound.
103      */
104     public final boolean hasBound() {
105 
106         return endKey != null || beginKey != null;
107     }
108 
109     /**
110      * Formats this range as a string for debugging.
111      */
112     public String   toString() {
113 
114         return "[KeyRange " + beginKey + ' ' + beginInclusive +
115                               endKey + ' ' + endInclusive +
116                               (singleKey ? " single" : "");
117     }
118 
119     /**
120      * Returns whether a given key is within range.
121      */
122     public boolean check(DatabaseEntry key) {
123 
124         if (singleKey) {
125             return (compare(key, beginKey) == 0);
126         } else {
127             return checkBegin(key, true) && checkEnd(key, true);
128         }
129     }
130 
131     /**
132      * Returns whether a given key is within range.
133      */
134     public boolean check(DatabaseEntry key, boolean inclusive) {
135 
136         if (singleKey) {
137             return (compare(key, beginKey) == 0);
138         } else {
139             return checkBegin(key, inclusive) && checkEnd(key, inclusive);
140         }
141     }
142 
143     /**
144      * Returns whether the given key is within range with respect to the
145      * beginning of the range.
146      *
147      * <p>The inclusive parameter should be true for checking a key read from
148      * the database; this will require that the key is within range.  When
149      * inclusive=false the key is allowed to be equal to the beginKey for the
150      * range; this is used for checking a new exclusive bound of a
151      * sub-range.</p>
152      *
153      * <p>Note that when inclusive=false and beginInclusive=true our check is
154      * not exactly correct because in theory we should allow the key to be "one
155      * less" than the existing bound; however, checking for "one less"  is
156      * impossible so we do the best we can and test the bounds
157      * conservatively.</p>
158      */
159     public boolean checkBegin(DatabaseEntry key, boolean inclusive) {
160 
161         if (beginKey == null) {
162             return true;
163         } else if (!beginInclusive && inclusive) {
164             return compare(key, beginKey) > 0;
165         } else {
166             return compare(key, beginKey) >= 0;
167         }
168     }
169 
170     /**
171      * Returns whether the given key is within range with respect to the
172      * end of the range.  See checkBegin for details.
173      */
174     public boolean checkEnd(DatabaseEntry key, boolean inclusive) {
175 
176         if (endKey == null) {
177             return true;
178         } else if (!endInclusive && inclusive) {
179             return compare(key, endKey) < 0;
180         } else {
181             return compare(key, endKey) <= 0;
182         }
183     }
184 
185     /**
186      * Compares two keys, using the user comparator if there is one.
187      */
188     public int compare(DatabaseEntry key1, DatabaseEntry key2) {
189 
190         if (comparator != null) {
191             return comparator.compare(getByteArray(key1), getByteArray(key2));
192         } else {
193             return compareBytes
194                     (key1.getData(), key1.getOffset(), key1.getSize(),
195                      key2.getData(), key2.getOffset(), key2.getSize());
196 
197         }
198     }
199 
200     /**
201      * Copies a byte array.
202      */
203     public static byte[] copyBytes(byte[] bytes) {
204 
205         byte[] a = new byte[bytes.length];
206         System.arraycopy(bytes, 0, a, 0, a.length);
207         return a;
208     }
209 
210     /**
211      * Compares two keys as unsigned byte arrays, which is the default
212      * comparison used by JE/DB.
213      */
214     public static int compareBytes(byte[] data1, int offset1, int size1,
215                                    byte[] data2, int offset2, int size2) {
216 
217         for (int i = 0; i < size1 && i < size2; i++) {
218 
219             int b1 = 0xFF & data1[offset1 + i];
220             int b2 = 0xFF & data2[offset2 + i];
221             if (b1 < b2)
222                 return -1;
223             else if (b1 > b2)
224                 return 1;
225         }
226 
227         if (size1 < size2)
228             return -1;
229         else if (size1 > size2)
230             return 1;
231         else
232             return 0;
233     }
234 
235     /**
236      * Compares two byte arrays for equality.
237      */
238     public static boolean equalBytes(byte[] data1, int offset1, int size1,
239                                      byte[] data2, int offset2, int size2) {
240         if (size1 != size2) {
241             return false;
242         }
243         for (int i = 0; i < size1; i += 1) {
244             if (data1[i + offset1] != data2[i + offset2]) {
245                 return false;
246             }
247         }
248         return true;
249     }
250 
251     /**
252      * Returns a copy of an entry.
253      */
254     public static DatabaseEntry copy(DatabaseEntry from) {
255         return new DatabaseEntry(getByteArray(from));
256     }
257 
258     /**
259      * Copies one entry to another.
260      */
261     public static void copy(DatabaseEntry from, DatabaseEntry to) {
262         to.setData(getByteArray(from));
263         to.setOffset(0);
264     }
265 
266     /**
267      * Returns an entry's byte array, copying it if the entry offset is
268      * non-zero.
269      */
270     public static byte[] getByteArray(DatabaseEntry entry) {
271     return getByteArrayInternal(entry, Integer.MAX_VALUE);
272     }
273 
274     public static byte[] getByteArray(DatabaseEntry entry, int maxBytes) {
275     return getByteArrayInternal(entry, maxBytes);
276     }
277 
278     private static byte[] getByteArrayInternal(DatabaseEntry entry,
279                            int maxBytes) {
280 
281         byte[] bytes = entry.getData();
282         if (bytes == null) return null;
283         int size = Math.min(entry.getSize(), maxBytes);
284     byte[] data;
285     if (size == 0) {
286         data = ZERO_LENGTH_BYTE_ARRAY;
287     } else {
288         data = new byte[size];
289         System.arraycopy(bytes, entry.getOffset(), data, 0, size);
290     }
291         return data;
292     }
293 
294     /**
295      * Returns the two DatabaseEntry objects have the same data value.
296      */
297     public static boolean equalBytes(DatabaseEntry e1, DatabaseEntry e2) {
298 
299         if (e1 == null && e2 == null) {
300             return true;
301         }
302         if (e1 == null || e2 == null) {
303             return false;
304         }
305 
306         byte[] d1 = e1.getData();
307         byte[] d2 = e2.getData();
308         int s1 = e1.getSize();
309         int s2 = e2.getSize();
310         int o1 = e1.getOffset();
311         int o2 = e2.getOffset();
312 
313         if (d1 == null && d2 == null) {
314             return true;
315         }
316         if (d1 == null || d2 == null) {
317             return false;
318         }
319         if (s1 != s2) {
320             return false;
321         }
322         for (int i = 0; i < s1; i += 1) {
323             if (d1[o1 + i] != d2[o2 + i]) {
324                 return false;
325             }
326         }
327         return true;
328     }
329 
330     /**
331      * Converts the byte array of this thang to space-separated integers,
332      * and suffixed by the record number if applicable.
333      *
334      * @param dbt the thang to convert.
335      *
336      * @param the resulting string.
337      */
338     public static String   toString(DatabaseEntry dbt) {
339 
340         int len = dbt.getOffset() + dbt.getSize();
341         StringBuffer   buf = new StringBuffer  (len * 2);
342         byte[] data = dbt.getData();
343         for (int i = dbt.getOffset(); i < len; i++) {
344             String   num = Integer.toHexString(data[i]);
345             if (num.length() < 2) buf.append('0');
346             buf.append(num);
347         }
348         return buf.toString();
349     }
350 }
351
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags