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