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.ByteStringBuilder;
031import org.forgerock.opendj.ldap.DecodeException;
032import org.forgerock.opendj.ldap.ResultCode;
033import org.forgerock.opendj.ldap.schema.MatchingRule;
034import org.opends.server.types.AttributeType;
035import org.opends.server.types.DirectoryException;
036import org.opends.server.types.SortKey;
037
038import com.sleepycat.je.DatabaseException;
039
040/**
041 * This class represents a partial sorted set of sorted entries in a VLV index.
042 */
043public class SortValuesSet
044{
045  private long[] entryIDs;
046
047  private int[] valuesBytesOffsets;
048  private byte[] valuesBytes;
049
050  private byte[] keyBytes;
051
052  private VLVIndex vlvIndex;
053
054  /**
055   * Construct an empty sort values set with the given information.
056   *
057   * @param vlvIndex The VLV index using this set.
058   */
059  public SortValuesSet(VLVIndex vlvIndex)
060  {
061    this.keyBytes = new byte[0];
062    this.entryIDs = null;
063    this.valuesBytes = null;
064    this.valuesBytesOffsets = null;
065    this.vlvIndex = vlvIndex;
066  }
067
068  /**
069   * Construct a sort values set from the database.
070   *
071   * @param keyBytes The database key used to locate this set.
072   * @param dataBytes The bytes to decode and construct this set.
073   * @param vlvIndex The VLV index using this set.
074   */
075  public SortValuesSet(byte[] keyBytes, byte[] dataBytes, VLVIndex vlvIndex)
076  {
077    this.keyBytes = keyBytes;
078    this.vlvIndex = vlvIndex;
079    if(dataBytes == null)
080    {
081      entryIDs = new long[0];
082      return;
083    }
084
085    entryIDs = getEncodedIDs(dataBytes, 0);
086    int valuesBytesOffset = entryIDs.length * 8 + 4;
087    int valuesBytesLength = dataBytes.length - valuesBytesOffset;
088    valuesBytes = new byte[valuesBytesLength];
089    System.arraycopy(dataBytes, valuesBytesOffset, valuesBytes, 0,
090                     valuesBytesLength);
091    this.valuesBytesOffsets = null;
092  }
093
094  private SortValuesSet()
095  {}
096
097  /**
098   * Add the given entryID and values from these sort values.
099   *
100   * @param sv The sort values to add.
101   * @throws DirectoryException If a Directory Server error occurs.
102   * @throws DatabaseException If an error occurs in the JE database.
103   */
104  void add(SortValues sv) throws DatabaseException, DirectoryException
105  {
106    add(sv.getEntryID(), sv.getValues(), sv.getTypes());
107  }
108
109  /**
110   * Add the given entryID and values from this VLV index.
111   *
112   * @param entryID The entry ID to add.
113   * @param values The values to add.
114   * @param types The types of the values to add.
115   * @return True if the information was successfully added or False
116   * otherwise.
117   * @throws DirectoryException If a Directory Server error occurs.
118   * @throws DatabaseException If an error occurs in the JE database.
119   */
120  public boolean add(long entryID, ByteString[] values, AttributeType[] types)
121      throws DatabaseException, DirectoryException
122  {
123    if(values == null)
124    {
125      return false;
126    }
127
128    if(entryIDs == null || entryIDs.length == 0)
129    {
130      entryIDs = new long[] { entryID };
131      valuesBytes = attributeValuesToDatabase(values, types);
132      if(valuesBytesOffsets != null)
133      {
134        valuesBytesOffsets = new int[] { 0 };
135      }
136      return true;
137    }
138    if (vlvIndex.comparator.compare(
139        this, entryIDs.length - 1, entryID, values) < 0)
140    {
141      long[] updatedEntryIDs = new long[entryIDs.length + 1];
142      System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, entryIDs.length);
143      updatedEntryIDs[entryIDs.length] = entryID;
144
145      byte[] newValuesBytes = attributeValuesToDatabase(values, types);
146      byte[] updatedValuesBytes = new byte[valuesBytes.length +
147          newValuesBytes.length];
148      System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0,
149                       valuesBytes.length);
150      System.arraycopy(newValuesBytes, 0, updatedValuesBytes,
151                       valuesBytes.length,
152                       newValuesBytes.length);
153
154      if(valuesBytesOffsets != null)
155      {
156        int[] updatedValuesBytesOffsets =
157            new int[valuesBytesOffsets.length + 1];
158        System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
159            0, valuesBytesOffsets.length);
160        updatedValuesBytesOffsets[valuesBytesOffsets.length] =
161            updatedValuesBytes.length - newValuesBytes.length;
162        valuesBytesOffsets = updatedValuesBytesOffsets;
163      }
164
165      entryIDs = updatedEntryIDs;
166      valuesBytes = updatedValuesBytes;
167      return true;
168    }
169    else
170    {
171      int pos = binarySearch(entryID, values);
172      if(pos >= 0)
173      {
174        if(entryIDs[pos] == entryID)
175        {
176          // The entry ID is alreadly present.
177          return false;
178        }
179      }
180      else
181      {
182        // For a negative return value r, the vlvIndex -(r+1) gives the array
183        // ndex at which the specified value can be inserted to maintain
184        // the sorted order of the array.
185        pos = -(pos+1);
186      }
187
188      long[] updatedEntryIDs = new long[entryIDs.length + 1];
189      System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, pos);
190      System.arraycopy(entryIDs, pos, updatedEntryIDs, pos+1,
191                       entryIDs.length-pos);
192      updatedEntryIDs[pos] = entryID;
193
194      byte[] newValuesBytes = attributeValuesToDatabase(values, types);
195      // BUG valuesBytesOffsets might be null ? If not why testing below ?
196      int valuesPos = valuesBytesOffsets[pos];
197      byte[] updatedValuesBytes = new byte[valuesBytes.length +
198          newValuesBytes.length];
199      System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0, valuesPos);
200      System.arraycopy(valuesBytes, valuesPos,  updatedValuesBytes,
201                       valuesPos + newValuesBytes.length,
202                       valuesBytes.length - valuesPos);
203      System.arraycopy(newValuesBytes, 0, updatedValuesBytes, valuesPos,
204                       newValuesBytes.length);
205
206      if(valuesBytesOffsets != null)
207      {
208        int[] updatedValuesBytesOffsets =
209            new int[valuesBytesOffsets.length + 1];
210        System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
211            0, pos);
212        // Update the rest of the offsets one by one - Expensive!
213        for(int i = pos; i < valuesBytesOffsets.length; i++)
214        {
215          updatedValuesBytesOffsets[i+1] =
216              valuesBytesOffsets[i] + newValuesBytes.length;
217        }
218        updatedValuesBytesOffsets[pos] = valuesBytesOffsets[pos];
219        valuesBytesOffsets = updatedValuesBytesOffsets;
220      }
221
222      entryIDs = updatedEntryIDs;
223      valuesBytes = updatedValuesBytes;
224    }
225
226    return true;
227  }
228
229  /**
230   * Remove the given entryID and values from these sort values.
231   *
232   * @param sv The sort values to remove.
233   * @throws DirectoryException If a Directory Server error occurs.
234   * @throws DatabaseException If an error occurs in the JE database.
235   */
236  void remove(SortValues sv) throws DatabaseException, DirectoryException
237  {
238    if(entryIDs == null || entryIDs.length == 0)
239    {
240      return;
241    }
242
243    if(valuesBytesOffsets == null)
244    {
245      updateValuesBytesOffsets();
246    }
247
248    int pos = binarySearch(sv.getEntryID(), sv.getValues());
249    if(pos < 0)
250    {
251      // Not found.
252      return;
253    }
254
255    // Found it.
256    long[] updatedEntryIDs = new long[entryIDs.length - 1];
257    System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, pos);
258    System.arraycopy(entryIDs, pos+1, updatedEntryIDs, pos,
259                     entryIDs.length-pos-1);
260    int valuesLength;
261    int valuesPos = valuesBytesOffsets[pos];
262    if(pos < valuesBytesOffsets.length - 1)
263    {
264      valuesLength = valuesBytesOffsets[pos+1] - valuesPos;
265    }
266    else
267    {
268      valuesLength = valuesBytes.length - valuesPos;
269    }
270    byte[] updatedValuesBytes = new byte[valuesBytes.length - valuesLength];
271    System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0, valuesPos);
272    System.arraycopy(valuesBytes, valuesPos + valuesLength,
273                     updatedValuesBytes, valuesPos,
274                     valuesBytes.length - valuesPos - valuesLength);
275
276    int[] updatedValuesBytesOffsets = new int[valuesBytesOffsets.length - 1];
277    System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets, 0, pos);
278    // Update the rest of the offsets one by one - Expensive!
279    for(int i = pos + 1; i < valuesBytesOffsets.length; i++)
280    {
281      updatedValuesBytesOffsets[i - 1] = valuesBytesOffsets[i] - valuesLength;
282    }
283
284    entryIDs = updatedEntryIDs;
285    valuesBytes = updatedValuesBytes;
286    valuesBytesOffsets = updatedValuesBytesOffsets;
287  }
288
289  /**
290   * Split portions of this set into another set. The values of the new set is
291   * from the end of this set.
292   *
293   * @param splitLength The size of the new set.
294   * @return The split set.
295   */
296  public SortValuesSet split(int splitLength)
297  {
298    if(valuesBytesOffsets == null)
299    {
300      updateValuesBytesOffsets();
301    }
302
303    long[] splitEntryIDs = new long[splitLength];
304    byte[] splitValuesBytes = new byte[valuesBytes.length -
305        valuesBytesOffsets[valuesBytesOffsets.length - splitLength]];
306    int[] splitValuesBytesOffsets = new int[splitLength];
307
308    long[] updatedEntryIDs = new long[entryIDs.length - splitEntryIDs.length];
309    System.arraycopy(entryIDs, 0, updatedEntryIDs, 0, updatedEntryIDs.length);
310    System.arraycopy(entryIDs, updatedEntryIDs.length, splitEntryIDs, 0,
311                     splitEntryIDs.length);
312
313    byte[] updatedValuesBytes =
314        new byte[valuesBytesOffsets[valuesBytesOffsets.length - splitLength]];
315    System.arraycopy(valuesBytes, 0, updatedValuesBytes, 0,
316                     updatedValuesBytes.length);
317    System.arraycopy(valuesBytes, updatedValuesBytes.length, splitValuesBytes,
318                     0, splitValuesBytes.length);
319
320    int[] updatedValuesBytesOffsets =
321        new int[valuesBytesOffsets.length - splitValuesBytesOffsets.length];
322    System.arraycopy(valuesBytesOffsets, 0, updatedValuesBytesOffsets,
323        0, updatedValuesBytesOffsets.length);
324    for(int i = updatedValuesBytesOffsets.length;
325        i < valuesBytesOffsets.length; i++)
326    {
327      splitValuesBytesOffsets[i - updatedValuesBytesOffsets.length] =
328          valuesBytesOffsets[i] -
329              valuesBytesOffsets[updatedValuesBytesOffsets.length];
330    }
331
332    SortValuesSet splitValuesSet = new SortValuesSet();
333
334    splitValuesSet.entryIDs = splitEntryIDs;
335    splitValuesSet.keyBytes = this.keyBytes;
336    splitValuesSet.valuesBytes = splitValuesBytes;
337    splitValuesSet.valuesBytesOffsets = splitValuesBytesOffsets;
338    splitValuesSet.vlvIndex = this.vlvIndex;
339
340    entryIDs = updatedEntryIDs;
341    valuesBytes = updatedValuesBytes;
342    valuesBytesOffsets = updatedValuesBytesOffsets;
343    keyBytes = null;
344
345    return splitValuesSet;
346  }
347
348  /**
349   * Encode this set to its database format.
350   *
351   * @return The encoded bytes representing this set or null if
352   * this set is empty.
353   */
354  public byte[] toDatabase()
355  {
356    if(size() == 0)
357    {
358      return null;
359    }
360
361    byte[] entryIDBytes = JebFormat.entryIDListToDatabase(entryIDs);
362    byte[] concatBytes = new byte[entryIDBytes.length + valuesBytes.length + 4];
363    int v = entryIDs.length;
364
365    for (int j = 3; j >= 0; j--)
366    {
367      concatBytes[j] = (byte) (v & 0xFF);
368      v >>>= 8;
369    }
370
371    System.arraycopy(entryIDBytes, 0, concatBytes, 4, entryIDBytes.length);
372    System.arraycopy(valuesBytes, 0, concatBytes, entryIDBytes.length+4,
373                     valuesBytes.length);
374
375    return concatBytes;
376  }
377
378  /**
379   * Get the size of the provided encoded set.
380   *
381   * @param bytes The encoded bytes of a SortValuesSet to decode the size from.
382   * @param offset The byte offset to start decoding.
383   * @return The size of the provided encoded set.
384   */
385  public static int getEncodedSize(byte[] bytes, int offset)
386  {
387    int v = 0;
388    for (int i = offset; i < offset + 4; i++)
389    {
390      v <<= 8;
391      v |= bytes[i] & 0xFF;
392    }
393    return v;
394  }
395
396  /**
397   * Get the IDs from the provided encoded set.
398   *
399   * @param bytes The encoded bytes of a SortValuesSet to decode the IDs from.
400   * @param offset The byte offset to start decoding.
401   * @return The decoded IDs in the provided encoded set.
402   */
403  public static long[] getEncodedIDs(byte[] bytes, int offset)
404  {
405    int length = getEncodedSize(bytes, offset);
406    byte[] entryIDBytes = new byte[length * 8];
407    System.arraycopy(bytes, offset+4, entryIDBytes, 0, entryIDBytes.length);
408    return JebFormat.entryIDListFromDatabase(entryIDBytes);
409  }
410
411  /**
412   * Searches this set for the specified values and entry ID using the binary
413   * search algorithm.
414   *
415   * @param entryID The entry ID to match or -1 if not matching on entry ID.
416   * @param values The values to match.
417   * @return Index of the entry matching the values and optionally the entry ID
418   * if it is found or a negative index if its not found.
419   * @throws DirectoryException If a Directory Server error occurs.
420   * @throws DatabaseException If an error occurs in the JE database.
421   */
422  int binarySearch(long entryID, ByteString... values)
423      throws DatabaseException, DirectoryException
424  {
425    if(entryIDs == null || entryIDs.length == 0)
426    {
427      return -1;
428    }
429
430    int i = 0;
431    for(int j = entryIDs.length - 1; i <= j;)
432    {
433      int k = i + j >> 1;
434      int l = vlvIndex.comparator.compare(this, k, entryID, values);
435      if (l < 0)
436      {
437        i = k + 1;
438      }
439      else if (l > 0)
440      {
441        j = k - 1;
442      }
443      else
444      {
445        return k;
446      }
447    }
448
449    return -(i + 1);
450  }
451
452  /**
453   * Retrieve the size of this set.
454   *
455   * @return The size of this set.
456   */
457  public int size()
458  {
459    if(entryIDs == null)
460    {
461      return 0;
462    }
463
464    return entryIDs.length;
465  }
466
467  /**
468   * Retrieve the entry IDs in this set.
469   *
470   * @return The entry IDs in this set.
471   */
472  public long[] getEntryIDs()
473  {
474    return entryIDs;
475  }
476
477  private byte[] attributeValuesToDatabase(ByteString[] values,
478      AttributeType[] types) throws DirectoryException
479  {
480    try
481    {
482      final ByteStringBuilder builder = new ByteStringBuilder();
483
484      for (int i = 0; i < values.length; i++)
485      {
486        final ByteString v = values[i];
487        if (v == null)
488        {
489          builder.appendBERLength(0);
490        }
491        else
492        {
493          final MatchingRule eqRule = types[i].getEqualityMatchingRule();
494          final ByteString nv = eqRule.normalizeAttributeValue(v);
495          builder.appendBERLength(nv.length());
496          builder.append(nv);
497        }
498      }
499      builder.trimToSize();
500
501      return builder.getBackingArray();
502    }
503    catch (DecodeException e)
504    {
505      throw new DirectoryException(
506          ResultCode.INVALID_ATTRIBUTE_SYNTAX, e.getMessageObject(), e);
507    }
508  }
509
510  /**
511   * Returns the key to use for this set of sort values in the database.
512   *
513   * @return The key as an array of bytes that should be used for this set in
514   * the database or NULL if this set is empty.
515   * @throws DirectoryException If a Directory Server error occurs.
516   * @throws DatabaseException If an error occurs in the JE database.
517   */
518  public byte[] getKeyBytes()
519      throws DatabaseException, DirectoryException
520  {
521    if(entryIDs == null || entryIDs.length == 0)
522    {
523      return null;
524    }
525
526    if(keyBytes != null)
527    {
528      return keyBytes;
529    }
530
531    if(valuesBytesOffsets == null)
532    {
533      updateValuesBytesOffsets();
534    }
535
536    int vBytesPos = valuesBytesOffsets[valuesBytesOffsets.length - 1];
537    int vBytesLength = valuesBytes.length - vBytesPos;
538
539    byte[] idBytes =
540        JebFormat.entryIDToDatabase(entryIDs[entryIDs.length - 1]);
541    keyBytes =
542        new byte[vBytesLength + idBytes.length];
543
544    System.arraycopy(valuesBytes, vBytesPos, keyBytes, 0, vBytesLength);
545    System.arraycopy(idBytes, 0, keyBytes, vBytesLength, idBytes.length);
546
547    return keyBytes;
548  }
549
550  /**
551   * Returns the key to use for this set of sort values in the database.
552   *
553   * @return The key as a sort values object that should be used for this set in
554   * the database or NULL if this set is empty or unbounded.
555   * @throws DirectoryException If a Directory Server error occurs.
556   * @throws DatabaseException If an error occurs in the JE database.
557   */
558  public SortValues getKeySortValues()
559      throws DatabaseException, DirectoryException
560  {
561    if(entryIDs == null || entryIDs.length == 0)
562    {
563      return null;
564    }
565
566    if(keyBytes != null && keyBytes.length == 0)
567    {
568      return null;
569    }
570
571    EntryID id = new EntryID(entryIDs[entryIDs.length - 1]);
572    SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
573    int numValues = sortKeys.length;
574    ByteString[] values = new ByteString[numValues];
575    for (int i = (entryIDs.length - 1) * numValues, j = 0;
576         i < entryIDs.length * numValues;
577         i++, j++)
578    {
579      values[j] = getValue(i);
580    }
581
582    return new SortValues(id, values, vlvIndex.sortOrder);
583  }
584
585  /**
586   * Returns the sort values at the index in this set.
587   *
588   * @param index The index of the sort values to get.
589   * @return The sort values object at the specified index.
590   * @throws DirectoryException If a Directory Server error occurs.
591   * @throws DatabaseException If an error occurs in the JE database.
592   * @throws JebException If an error occurs in the JE database.
593   **/
594  public SortValues getSortValues(int index)
595      throws JebException, DatabaseException, DirectoryException
596  {
597    if(entryIDs == null || entryIDs.length == 0)
598    {
599      return null;
600    }
601
602    EntryID id = new EntryID(entryIDs[index]);
603    SortKey[] sortKeys = vlvIndex.sortOrder.getSortKeys();
604    int numValues = sortKeys.length;
605    ByteString[] values = new ByteString[numValues];
606    for (int i = index * numValues, j = 0;
607         i < (index + 1) * numValues;
608         i++, j++)
609    {
610      values[j] = getValue(i);
611    }
612
613    return new SortValues(id, values, vlvIndex.sortOrder);
614  }
615
616  private void updateValuesBytesOffsets()
617  {
618    valuesBytesOffsets = new int[entryIDs.length];
619    int vBytesPos = 0;
620    int numAttributes = vlvIndex.sortOrder.getSortKeys().length;
621
622    for(int pos = 0; pos < entryIDs.length; pos++)
623    {
624      valuesBytesOffsets[pos] = vBytesPos;
625
626      for(int i = 0; i < numAttributes; i++)
627      {
628        int valueLength = valuesBytes[vBytesPos] & 0x7F;
629        if (valueLength != valuesBytes[vBytesPos++])
630        {
631          int valueLengthBytes = valueLength;
632          valueLength = 0;
633          for (int j=0; j < valueLengthBytes; j++, vBytesPos++)
634          {
635            valueLength = (valueLength << 8) | (valuesBytes[vBytesPos] & 0xFF);
636          }
637        }
638
639        vBytesPos += valueLength;
640      }
641    }
642  }
643
644  /**
645   * Retrieve an attribute value from this values set. The index is the
646   * absolute index. (ie. for a sort on 3 attributes per entry, an vlvIndex of 6
647   * will be the 1st attribute value of the 3rd entry).
648   *
649   * @param index The vlvIndex of the attribute value to retrieve.
650   * @return The byte array representation of the attribute value.
651   * @throws DirectoryException If a Directory Server error occurs.
652   * @throws DatabaseException If an error occurs in the JE database.
653   */
654  public ByteString getValue(int index)
655      throws DatabaseException, DirectoryException
656  {
657    if(valuesBytesOffsets == null)
658    {
659      updateValuesBytesOffsets();
660    }
661    int numAttributes = vlvIndex.sortOrder.getSortKeys().length;
662    int vIndex = index / numAttributes;
663    int vOffset = index % numAttributes;
664    int vBytesPos = valuesBytesOffsets[vIndex];
665
666    // Find the desired value in the sort order set.
667    for(int i = 0; i <= vOffset; i++)
668    {
669      int valueLength = valuesBytes[vBytesPos] & 0x7F;
670      if (valueLength != valuesBytes[vBytesPos++])
671      {
672        int valueLengthBytes = valueLength;
673        valueLength = 0;
674        for (int j=0; j < valueLengthBytes; j++, vBytesPos++)
675        {
676          valueLength = (valueLength << 8) | (valuesBytes[vBytesPos] & 0xFF);
677        }
678      }
679
680      if(i == vOffset)
681      {
682        if(valueLength == 0)
683        {
684          return null;
685        }
686        else
687        {
688          byte[] valueBytes = new byte[valueLength];
689          System.arraycopy(valuesBytes, vBytesPos, valueBytes, 0, valueLength);
690          return ByteString.wrap(valueBytes);
691        }
692      }
693      else
694      {
695        vBytesPos += valueLength;
696      }
697    }
698    return ByteString.empty();
699  }
700}