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 }