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}