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