001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: KeyRange.java,v 1.4.2.2 2008/01/07 15:14:21 cwl Exp $
007: */
008:
009: package com.sleepycat.util.keyrange;
010:
011: import java.util.Comparator;
012:
013: import com.sleepycat.je.DatabaseEntry;
014:
015: /**
016: * Encapsulates a key range for use with a RangeCursor.
017: */
018: public class KeyRange {
019:
020: /*
021: * We can return the same byte[] for 0 length arrays.
022: */
023: public static final byte[] ZERO_LENGTH_BYTE_ARRAY = new byte[0];
024:
025: Comparator comparator;
026: DatabaseEntry beginKey;
027: DatabaseEntry endKey;
028: boolean singleKey;
029: boolean beginInclusive;
030: boolean endInclusive;
031:
032: /**
033: * Creates an unconstrained key range.
034: */
035: public KeyRange(Comparator comparator) {
036: this .comparator = comparator;
037: }
038:
039: /**
040: * Creates a range for a single key.
041: */
042: public KeyRange subRange(DatabaseEntry key)
043: throws KeyRangeException {
044:
045: if (!check(key)) {
046: throw new KeyRangeException("singleKey out of range");
047: }
048: KeyRange range = new KeyRange(comparator);
049: range.beginKey = key;
050: range.endKey = key;
051: range.beginInclusive = true;
052: range.endInclusive = true;
053: range.singleKey = true;
054: return range;
055: }
056:
057: /**
058: * Creates a range that is the intersection of this range and the given
059: * range parameters.
060: */
061: public KeyRange subRange(DatabaseEntry beginKey,
062: boolean beginInclusive, DatabaseEntry endKey,
063: boolean endInclusive) throws KeyRangeException {
064:
065: if (beginKey == null) {
066: beginKey = this .beginKey;
067: beginInclusive = this .beginInclusive;
068: } else if (!check(beginKey, beginInclusive)) {
069: throw new KeyRangeException("beginKey out of range");
070: }
071: if (endKey == null) {
072: endKey = this .endKey;
073: endInclusive = this .endInclusive;
074: } else if (!check(endKey, endInclusive)) {
075: throw new KeyRangeException("endKey out of range");
076: }
077: KeyRange range = new KeyRange(comparator);
078: range.beginKey = beginKey;
079: range.endKey = endKey;
080: range.beginInclusive = beginInclusive;
081: range.endInclusive = endInclusive;
082: return range;
083: }
084:
085: /**
086: * Returns whether this is a single-key range.
087: */
088: public final boolean isSingleKey() {
089: return singleKey;
090: }
091:
092: /**
093: * Returns the key of a single-key range, or null if not a single-key
094: * range.
095: */
096: public final DatabaseEntry getSingleKey() {
097:
098: return singleKey ? beginKey : null;
099: }
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 + endKey
115: + ' ' + endInclusive + (singleKey ? " single" : "");
116: }
117:
118: /**
119: * Returns whether a given key is within range.
120: */
121: public boolean check(DatabaseEntry key) {
122:
123: if (singleKey) {
124: return (compare(key, beginKey) == 0);
125: } else {
126: return checkBegin(key, true) && checkEnd(key, true);
127: }
128: }
129:
130: /**
131: * Returns whether a given key is within range.
132: */
133: public boolean check(DatabaseEntry key, boolean inclusive) {
134:
135: if (singleKey) {
136: return (compare(key, beginKey) == 0);
137: } else {
138: return checkBegin(key, inclusive)
139: && 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),
192: getByteArray(key2));
193: } else {
194: return compareBytes(key1.getData(), key1.getOffset(), key1
195: .getSize(), key2.getData(), key2.getOffset(), key2
196: .getSize());
197:
198: }
199: }
200:
201: /**
202: * Copies a byte array.
203: */
204: public static byte[] copyBytes(byte[] bytes) {
205:
206: byte[] a = new byte[bytes.length];
207: System.arraycopy(bytes, 0, a, 0, a.length);
208: return a;
209: }
210:
211: /**
212: * Compares two keys as unsigned byte arrays, which is the default
213: * comparison used by JE/DB.
214: */
215: public static int compareBytes(byte[] data1, int offset1,
216: int size1, byte[] data2, int offset2, int size2) {
217:
218: for (int i = 0; i < size1 && i < size2; i++) {
219:
220: int b1 = 0xFF & data1[offset1 + i];
221: int b2 = 0xFF & data2[offset2 + i];
222: if (b1 < b2)
223: return -1;
224: else if (b1 > b2)
225: return 1;
226: }
227:
228: if (size1 < size2)
229: return -1;
230: else if (size1 > size2)
231: return 1;
232: else
233: return 0;
234: }
235:
236: /**
237: * Compares two byte arrays for equality.
238: */
239: public static boolean equalBytes(byte[] data1, int offset1,
240: int size1, byte[] data2, int offset2, int size2) {
241: if (size1 != size2) {
242: return false;
243: }
244: for (int i = 0; i < size1; i += 1) {
245: if (data1[i + offset1] != data2[i + offset2]) {
246: return false;
247: }
248: }
249: return true;
250: }
251:
252: /**
253: * Returns a copy of an entry.
254: */
255: public static DatabaseEntry copy(DatabaseEntry from) {
256: return new DatabaseEntry(getByteArray(from));
257: }
258:
259: /**
260: * Copies one entry to another.
261: */
262: public static void copy(DatabaseEntry from, DatabaseEntry to) {
263: to.setData(getByteArray(from));
264: to.setOffset(0);
265: }
266:
267: /**
268: * Returns an entry's byte array, copying it if the entry offset is
269: * non-zero.
270: */
271: public static byte[] getByteArray(DatabaseEntry entry) {
272: return getByteArrayInternal(entry, Integer.MAX_VALUE);
273: }
274:
275: public static byte[] getByteArray(DatabaseEntry entry, int maxBytes) {
276: return getByteArrayInternal(entry, maxBytes);
277: }
278:
279: private static byte[] getByteArrayInternal(DatabaseEntry entry,
280: int maxBytes) {
281:
282: byte[] bytes = entry.getData();
283: if (bytes == null)
284: return null;
285: int size = Math.min(entry.getSize(), maxBytes);
286: byte[] data;
287: if (size == 0) {
288: data = ZERO_LENGTH_BYTE_ARRAY;
289: } else {
290: data = new byte[size];
291: System.arraycopy(bytes, entry.getOffset(), data, 0, size);
292: }
293: return data;
294: }
295:
296: /**
297: * Returns the two DatabaseEntry objects have the same data value.
298: */
299: public static boolean equalBytes(DatabaseEntry e1, DatabaseEntry e2) {
300:
301: if (e1 == null && e2 == null) {
302: return true;
303: }
304: if (e1 == null || e2 == null) {
305: return false;
306: }
307:
308: byte[] d1 = e1.getData();
309: byte[] d2 = e2.getData();
310: int s1 = e1.getSize();
311: int s2 = e2.getSize();
312: int o1 = e1.getOffset();
313: int o2 = e2.getOffset();
314:
315: if (d1 == null && d2 == null) {
316: return true;
317: }
318: if (d1 == null || d2 == null) {
319: return false;
320: }
321: if (s1 != s2) {
322: return false;
323: }
324: for (int i = 0; i < s1; i += 1) {
325: if (d1[o1 + i] != d2[o2 + i]) {
326: return false;
327: }
328: }
329: return true;
330: }
331:
332: /**
333: * Converts the byte array of this thang to space-separated integers,
334: * and suffixed by the record number if applicable.
335: *
336: * @param dbt the thang to convert.
337: *
338: * @param the resulting string.
339: */
340: public static String toString(DatabaseEntry dbt) {
341:
342: int len = dbt.getOffset() + dbt.getSize();
343: StringBuffer buf = new StringBuffer(len * 2);
344: byte[] data = dbt.getData();
345: for (int i = dbt.getOffset(); i < len; i++) {
346: String num = Integer.toHexString(data[i]);
347: if (num.length() < 2)
348: buf.append('0');
349: buf.append(num);
350: }
351: return buf.toString();
352: }
353: }
|