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 }