KeyRange


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