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    }