001 /*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License"). You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at
010 * trunk/opends/resource/legal-notices/OpenDS.LICENSE
011 * or https://OpenDS.dev.java.net/OpenDS.LICENSE.
012 * See the License for the specific language governing permissions
013 * and limitations under the License.
014 *
015 * When distributing Covered Code, include this CDDL HEADER in each
016 * file and include the License file at
017 * trunk/opends/resource/legal-notices/OpenDS.LICENSE. If applicable,
018 * add the following below this CDDL HEADER, with the fields enclosed
019 * by brackets "[]" replaced with your own identifying information:
020 * Portions Copyright [yyyy] [name of copyright owner]
021 *
022 * CDDL HEADER END
023 *
024 *
025 * Copyright 2006-2008 Sun Microsystems, Inc.
026 */
027 package org.opends.server.backends.jeb;
028
029 import org.opends.server.api.OrderingMatchingRule;
030 import org.opends.server.types.AttributeValue;
031 import org.opends.server.types.DirectoryException;
032
033 import java.util.Comparator;
034 import java.io.Serializable;
035
036 import com.sleepycat.je.DatabaseException;
037
038 /**
039 * This class is used to compare the keys used in a VLV index. Each key is
040 * made up the sort values and the entry ID of the largest entry in the sorted
041 * set stored in the data for the key.
042 */
043 public class VLVKeyComparator implements Comparator<byte[]>, Serializable
044 {
045 /**
046 * The serial version identifier required to satisfy the compiler because this
047 * class implements the <CODE>java.io.Serializable</CODE> interface. This
048 * value was generated using the <CODE>serialver</CODE> command-line utility
049 * included with the Java SDK.
050 */
051 static final long serialVersionUID = 1585167927344130604L;
052
053 private OrderingMatchingRule[] orderingRules;
054
055 private boolean[] ascending;
056
057 /**
058 * Construst a new VLV Key Comparator object.
059 *
060 * @param orderingRules The array of ordering rules to use when comparing
061 * the decoded values in the key.
062 * @param ascending The array of booleans indicating the ordering for
063 * each value.
064 */
065 public VLVKeyComparator(OrderingMatchingRule[] orderingRules,
066 boolean[] ascending)
067 {
068 this.orderingRules = orderingRules;
069 this.ascending = ascending;
070 }
071
072 /**
073 * Compares the contents of the provided byte arrays to determine their
074 * relative order. A key in the VLV index contains the sorted attribute values
075 * in order followed by the 8 byte entry ID. A attribute value of length 0
076 * means that value is null and the attribute type was not part of the entry.
077 * A null value is always considered greater then a non null value. If all
078 * attribute values are the same, the entry ID will be used to determine the
079 * ordering.
080 *
081 * When comparing partial keys (ie. keys with only the first attribute value
082 * encoded for evaluating VLV assertion value offsets or keys with no entry
083 * IDs), only information available in both byte keys will be used to
084 * determine the ordering. If all available information is the same, 0 will
085 * be returned.
086 *
087 * @param b1 The first byte array to use in the comparison.
088 * @param b2 The second byte array to use in the comparison.
089 *
090 * @return A negative integer if <CODE>b1</CODE> should come before
091 * <CODE>b2</CODE> in ascending order, a positive integer if
092 * <CODE>b1</CODE> should come after <CODE>b2</CODE> in ascending
093 * order, or zero if there is no difference between the values with
094 * regard to ordering.
095 */
096 public int compare(byte[] b1, byte[] b2)
097 {
098 // A 0 length byte array is a special key used for the unbound max
099 // sort values set. It always comes after a non length byte array.
100 if(b1.length == 0)
101 {
102 if(b2.length == 0)
103 {
104 return 0;
105 }
106 else
107 {
108 return 1;
109 }
110 }
111 else if(b2.length == 0)
112 {
113 return -1;
114 }
115
116 int b1Pos = 0;
117 int b2Pos = 0;
118 for (int j=0;
119 j < orderingRules.length && b1Pos < b1.length && b2Pos < b2.length;
120 j++)
121 {
122 int b1Length = b1[b1Pos] & 0x7F;
123 if (b1[b1Pos++] != b1Length)
124 {
125 int b1NumLengthBytes = b1Length;
126 b1Length = 0;
127 for (int k=0; k < b1NumLengthBytes; k++, b1Pos++)
128 {
129 b1Length = (b1Length << 8) |
130 (b1[b1Pos] & 0xFF);
131 }
132 }
133
134 int b2Length = b2[b2Pos] & 0x7F;
135 if (b2[b2Pos++] != b2Length)
136 {
137 int b2NumLengthBytes = b2Length;
138 b2Length = 0;
139 for (int k=0; k < b2NumLengthBytes; k++, b2Pos++)
140 {
141 b2Length = (b2Length << 8) |
142 (b2[b2Pos] & 0xFF);
143 }
144 }
145
146 byte[] b1Bytes;
147 byte[] b2Bytes;
148 if(b1Length > 0)
149 {
150 b1Bytes = new byte[b1Length];
151 System.arraycopy(b1, b1Pos, b1Bytes, 0, b1Length);
152 b1Pos += b1Length;
153 }
154 else
155 {
156 b1Bytes = null;
157 }
158
159 if(b2Length > 0)
160 {
161 b2Bytes = new byte[b2Length];
162 System.arraycopy(b2, b2Pos, b2Bytes, 0, b2Length);
163 b2Pos += b2Length;
164 }
165 else
166 {
167 b2Bytes = null;
168 }
169
170 // A null value will always come after a non-null value.
171 if (b1Bytes == null)
172 {
173 if (b2Bytes == null)
174 {
175 continue;
176 }
177 else
178 {
179 return 1;
180 }
181 }
182 else if (b2Bytes == null)
183 {
184 return -1;
185 }
186
187 int result;
188 if(ascending[j])
189 {
190 result = orderingRules[j].compare(b1Bytes, b2Bytes);
191 }
192 else
193 {
194 result = orderingRules[j].compare(b2Bytes, b1Bytes);
195 }
196
197 if(result != 0)
198 {
199 return result;
200 }
201 }
202
203 // If we've gotten here, then we can't tell a difference between the sets
204 // of available values, so sort based on entry ID if its in the key.
205
206 if(b1Pos + 8 <= b1.length && b2Pos + 8 <= b2.length)
207 {
208 long b1ID = 0;
209 for (int i = b1Pos; i < b1Pos + 8; i++)
210 {
211 b1ID <<= 8;
212 b1ID |= (b1[i] & 0xFF);
213 }
214
215 long b2ID = 0;
216 for (int i = b2Pos; i < b2Pos + 8; i++)
217 {
218 b2ID <<= 8;
219 b2ID |= (b2[i] & 0xFF);
220 }
221
222 long idDifference = (b1ID - b2ID);
223 if (idDifference < 0)
224 {
225 return -1;
226 }
227 else if (idDifference > 0)
228 {
229 return 1;
230 }
231 else
232 {
233 return 0;
234 }
235 }
236
237 // If we've gotten here, then we can't tell the difference between the sets
238 // of available values and entry IDs are not all available, so just return
239 // 0
240 return 0;
241
242 }
243
244 /**
245 * Compares the contents in the provided values set with the given values to
246 * determine their relative order. A null value is always considered greater
247 * then a non null value. If all attribute values are the same, the entry ID
248 * will be used to determine the ordering.
249 *
250 * If the given attribute values array does not contain all the values in the
251 * sort order, any missing values will be considered as a unknown or
252 * wildcard value instead of a nonexistant value. When comparing partial
253 * information, only values available in both the values set and the
254 * given values will be used to determine the ordering. If all available
255 * information is the same, 0 will be returned.
256 *
257 * @param set The sort values set to containing the values.
258 * @param index The index of the values in the set.
259 * @param entryID The entry ID to use in the comparasion.
260 * @param values The values to use in the comparasion.
261 *
262 * @return A negative integer if the values in the set should come before
263 * the given values in ascending order, a positive integer if
264 * the values in the set should come after the given values in
265 * ascending order, or zero if there is no difference between the
266 * values with regard to ordering.
267 * @throws DatabaseException If an error occurs during an operation on a
268 * JE database.
269 * @throws JebException If an error occurs during an operation on a
270 * JE database.
271 * @throws DirectoryException If an error occurs while trying to
272 * normalize the value (e.g., if it is
273 * not acceptable for use with the
274 * associated equality matching rule).
275 */
276 public int compare(SortValuesSet set, int index,
277 long entryID, AttributeValue[] values)
278 throws JebException, DatabaseException, DirectoryException
279 {
280 for (int j=0; j < orderingRules.length; j++)
281 {
282 if(j >= values.length)
283 {
284 break;
285 }
286
287 byte[] b1Bytes = set.getValue((index * orderingRules.length) + j);
288 byte[] b2Bytes = null;
289
290 if(values[j] != null)
291 {
292 b2Bytes = values[j].getNormalizedValueBytes();
293 }
294
295 // A null value will always come after a non-null value.
296 if (b1Bytes == null)
297 {
298 if (b2Bytes == null)
299 {
300 continue;
301 }
302 else
303 {
304 return 1;
305 }
306 }
307 else if (b2Bytes == null)
308 {
309 return -1;
310 }
311
312 int result;
313 if(ascending[j])
314 {
315 result = orderingRules[j].compare(b1Bytes, b2Bytes);
316 }
317 else
318 {
319 result = orderingRules[j].compare(b2Bytes, b1Bytes);
320 }
321
322 if(result != 0)
323 {
324 return result;
325 }
326 }
327
328 if(entryID != -1)
329 {
330 // If we've gotten here, then we can't tell a difference between the sets
331 // of values, so sort based on entry ID.
332
333 long idDifference = (set.getEntryIDs()[index] - entryID);
334 if (idDifference < 0)
335 {
336 return -1;
337 }
338 else if (idDifference > 0)
339 {
340 return 1;
341 }
342 else
343 {
344 return 0;
345 }
346 }
347
348 // If we've gotten here, then we can't tell the difference between the sets
349 // of available values and the entry ID is not available. Just return 0.
350 return 0;
351 }
352 }