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 ForgeRock AS 026 */ 027package org.opends.server.backends.jeb; 028 029import java.util.ArrayList; 030import java.util.Arrays; 031import java.util.Iterator; 032 033import org.forgerock.opendj.ldap.ByteString; 034 035/** 036 * Represents a set of Entry IDs. It can represent a set where the IDs are 037 * not defined, for example when the index entry limit has been exceeded. 038 */ 039public class EntryIDSet implements Iterable<EntryID> 040{ 041 042 /** 043 * The IDs are stored here in an array in ascending order. 044 * A null array implies not defined, rather than zero IDs. 045 */ 046 private long[] values; 047 048 /** 049 * The size of the set when it is not defined. This value is only maintained 050 * when the set is undefined. 051 */ 052 private long undefinedSize = Long.MAX_VALUE; 053 054 /** 055 * The database key containing this set, if the set was constructed 056 * directly from the database. 057 */ 058 private final ByteString keyBytes; 059 060 /** Create a new undefined set. */ 061 public EntryIDSet() 062 { 063 this.keyBytes = null; 064 this.undefinedSize = Long.MAX_VALUE; 065 } 066 067 /** 068 * Create a new undefined set with a initial size. 069 * 070 * @param size The undefined size for this set. 071 */ 072 public EntryIDSet(long size) 073 { 074 this.keyBytes = null; 075 this.undefinedSize = size; 076 } 077 078 /** 079 * Create a new entry ID set from the raw database value. 080 * 081 * @param keyBytes The database key that contains this value. 082 * @param bytes The database value, or null if there are no entry IDs. 083 */ 084 public EntryIDSet(byte[] keyBytes, byte[] bytes) 085 { 086 this(keyBytes != null ? ByteString.wrap(keyBytes) : null, 087 bytes != null ? ByteString.wrap(bytes) : null); 088 } 089 090 /** 091 * Create a new entry ID set from the raw database value. 092 * 093 * @param keyBytes 094 * The database key that contains this value. 095 * @param bytes 096 * The database value, or null if there are no entry IDs. 097 */ 098 public EntryIDSet(ByteString keyBytes, ByteString bytes) 099 { 100 this.keyBytes = keyBytes; 101 102 if (bytes == null) 103 { 104 values = new long[0]; 105 return; 106 } 107 108 if (bytes.length() == 0) 109 { 110 // Entry limit has exceeded and there is no encoded undefined set size. 111 undefinedSize = Long.MAX_VALUE; 112 } 113 else if ((bytes.byteAt(0) & 0x80) == 0x80) 114 { 115 // Entry limit has exceeded and there is an encoded undefined set size. 116 undefinedSize = 117 JebFormat.entryIDUndefinedSizeFromDatabase(bytes.toByteArray()); 118 } 119 else 120 { 121 // Seems like entry limit has not been exceeded and the bytes is a 122 // list of entry IDs. 123 values = JebFormat.entryIDListFromDatabase(bytes.toByteArray()); 124 } 125 } 126 127 /** 128 * Construct an EntryIDSet from an array of longs. 129 * 130 * @param values The array of IDs represented as longs. 131 * @param pos The position of the first ID to take from the array. 132 * @param len the number of IDs to take from the array. 133 */ 134 EntryIDSet(long[] values, int pos, int len) 135 { 136 this.keyBytes = null; 137 this.values = new long[len]; 138 System.arraycopy(values, pos, this.values, 0, len); 139 } 140 141 /** 142 * Create a new set of entry IDs that is the union of several entry ID sets. 143 * 144 * @param sets A list of entry ID sets. 145 * @param allowDuplicates true if duplicate IDs are allowed in the resulting 146 * set, or if the provided sets are sure not to overlap; false if 147 * duplicates should be eliminated. 148 * @return The union of the provided entry ID sets. 149 */ 150 public static EntryIDSet unionOfSets(ArrayList<EntryIDSet> sets, 151 boolean allowDuplicates) 152 { 153 int count = 0; 154 155 boolean undefined = false; 156 for (EntryIDSet l : sets) 157 { 158 if (!l.isDefined()) 159 { 160 if(l.undefinedSize == Long.MAX_VALUE) 161 { 162 return new EntryIDSet(); 163 } 164 undefined = true; 165 } 166 count += l.size(); 167 } 168 169 if(undefined) 170 { 171 return new EntryIDSet(count); 172 } 173 174 boolean needSort = false; 175 long[] n = new long[count]; 176 int pos = 0; 177 for (EntryIDSet l : sets) 178 { 179 if (l.values.length != 0) 180 { 181 if (!needSort && pos > 0 && l.values[0] < n[pos-1]) 182 { 183 needSort = true; 184 } 185 System.arraycopy(l.values, 0, n, pos, l.values.length); 186 pos += l.values.length; 187 } 188 } 189 if (needSort) 190 { 191 Arrays.sort(n); 192 } 193 if (allowDuplicates) 194 { 195 EntryIDSet ret = new EntryIDSet(); 196 ret.values = n; 197 return ret; 198 } 199 long[] n1 = new long[n.length]; 200 long last = -1; 201 int j = 0; 202 for (long l : n) 203 { 204 if (l != last) 205 { 206 last = n1[j++] = l; 207 } 208 } 209 if (j == n1.length) 210 { 211 EntryIDSet ret = new EntryIDSet(); 212 ret.values = n1; 213 return ret; 214 } 215 else 216 { 217 return new EntryIDSet(n1, 0, j); 218 } 219 } 220 221 /** 222 * Get the size of this entry ID set. 223 * 224 * @return The number of IDs in the set. 225 */ 226 public long size() 227 { 228 if (values != null) 229 { 230 return values.length; 231 } 232 return undefinedSize; 233 } 234 235 /** 236 * Get a string representation of this object. 237 * @return A string representation of this object. 238 */ 239 @Override 240 public String toString() 241 { 242 StringBuilder buffer = new StringBuilder(16); 243 toString(buffer); 244 return buffer.toString(); 245 } 246 247 /** 248 * Convert to a short string to aid with debugging. 249 * 250 * @param buffer The string is appended to this string builder. 251 */ 252 public void toString(StringBuilder buffer) 253 { 254 if (!isDefined()) 255 { 256 if (keyBytes != null) 257 { 258 // The index entry limit was exceeded 259 if(undefinedSize == Long.MAX_VALUE) 260 { 261 buffer.append("[LIMIT-EXCEEDED]"); 262 } 263 else 264 { 265 buffer.append("[LIMIT-EXCEEDED:"); 266 buffer.append(undefinedSize); 267 buffer.append("]"); 268 } 269 } 270 else 271 { 272 // Not indexed 273 buffer.append("[NOT-INDEXED]"); 274 } 275 } 276 else 277 { 278 buffer.append("[COUNT:"); 279 buffer.append(size()); 280 buffer.append("]"); 281 } 282 } 283 284 /** 285 * Determine whether this set of IDs is defined. 286 * 287 * @return true if the set of IDs is defined. 288 */ 289 public boolean isDefined() 290 { 291 return values != null; 292 } 293 294 /** 295 * Get a database representation of this object. 296 * @return A database representation of this object as a byte array. 297 */ 298 public byte[] toDatabase() 299 { 300 if(isDefined()) 301 { 302 return JebFormat.entryIDListToDatabase(values); 303 } 304 else 305 { 306 return JebFormat.entryIDUndefinedSizeToDatabase(undefinedSize); 307 } 308 } 309 310 /** 311 * Insert an ID into this set. 312 * 313 * @param entryID The ID to be inserted. 314 * @return true if the set was changed, false if it was not changed, 315 * for example if the set is undefined or the ID was already present. 316 */ 317 public boolean add(EntryID entryID) 318 { 319 if (values == null) 320 { 321 if(undefinedSize != Long.MAX_VALUE) 322 { 323 undefinedSize++; 324 } 325 return true; 326 } 327 328 long id = entryID.longValue(); 329 if (values.length == 0) 330 { 331 values = new long[] { id }; 332 return true; 333 } 334 335 if (id > values[values.length-1]) 336 { 337 long[] updatedValues = Arrays.copyOf(values, values.length + 1); 338 updatedValues[values.length] = id; 339 values = updatedValues; 340 } 341 else 342 { 343 int pos = Arrays.binarySearch(values, id); 344 if (pos >= 0) 345 { 346 // The ID is already present. 347 return false; 348 } 349 350 // For a negative return value r, the index -(r+1) gives the array 351 // index at which the specified value can be inserted to maintain 352 // the sorted order of the array. 353 pos = -(pos+1); 354 355 long[] updatedValues = new long[values.length+1]; 356 System.arraycopy(values, 0, updatedValues, 0, pos); 357 System.arraycopy(values, pos, updatedValues, pos+1, values.length-pos); 358 updatedValues[pos] = id; 359 values = updatedValues; 360 } 361 362 return true; 363 } 364 365 /** 366 * Remove an ID from this set. 367 * 368 * @param entryID The ID to be removed 369 * @return true if the set was changed, false if it was not changed, 370 * for example if the set was undefined or the ID was not present. 371 */ 372 public boolean remove(EntryID entryID) 373 { 374 if (values == null) 375 { 376 if(undefinedSize != Long.MAX_VALUE) 377 { 378 undefinedSize--; 379 } 380 return true; 381 } 382 383 if (values.length == 0) 384 { 385 return false; 386 } 387 388 // Binary search to locate the ID. 389 long id = entryID.longValue(); 390 int pos = Arrays.binarySearch(values, id); 391 if (pos >= 0) 392 { 393 // Found it. 394 long[] updatedValues = new long[values.length-1]; 395 System.arraycopy(values, 0, updatedValues, 0, pos); 396 System.arraycopy(values, pos+1, updatedValues, pos, values.length-pos-1); 397 values = updatedValues; 398 return true; 399 } 400 // Not found. 401 return false; 402 } 403 404 /** 405 * Check whether this set of entry IDs contains a given ID. 406 * 407 * @param entryID The ID to be checked. 408 * @return true if this set contains the given ID, 409 * or if the set is undefined. 410 */ 411 public boolean contains(EntryID entryID) 412 { 413 if (values == null) 414 { 415 return true; 416 } 417 418 final long id = entryID.longValue(); 419 return values.length != 0 420 && id <= values[values.length - 1] 421 && Arrays.binarySearch(values, id) >= 0; 422 } 423 424 /** 425 * Takes the intersection of this set with another. 426 * Retain those IDs that appear in the given set. 427 * 428 * @param that The set of IDs that are to be retained from this object. 429 */ 430 public void retainAll(EntryIDSet that) 431 { 432 if (!isDefined()) 433 { 434 this.values = that.values; 435 this.undefinedSize = that.undefinedSize; 436 return; 437 } 438 439 if (!that.isDefined()) 440 { 441 return; 442 } 443 444 // TODO Perhaps Arrays.asList and retainAll list method are more efficient? 445 446 long[] a = this.values; 447 long[] b = that.values; 448 449 int ai = 0, bi = 0, ci = 0; 450 long[] c = new long[Math.min(a.length,b.length)]; 451 while (ai < a.length && bi < b.length) 452 { 453 if (a[ai] == b[bi]) 454 { 455 c[ci] = a[ai]; 456 ai++; 457 bi++; 458 ci++; 459 } 460 else if (a[ai] > b[bi]) 461 { 462 bi++; 463 } 464 else 465 { 466 ai++; 467 } 468 } 469 if (ci < c.length) 470 { 471 values = Arrays.copyOf(c, ci); 472 } 473 else 474 { 475 values = c; 476 } 477 } 478 479 /** 480 * Add all the IDs from a given set that are not already present. 481 * 482 * @param that The set of IDs to be added. It MUST be defined 483 */ 484 public void addAll(EntryIDSet that) 485 { 486 if(!that.isDefined()) 487 { 488 return; 489 } 490 491 if (!isDefined()) 492 { 493 // Assume there are no overlap between IDs in that set with this set 494 if(undefinedSize != Long.MAX_VALUE) 495 { 496 undefinedSize += that.size(); 497 } 498 return; 499 } 500 501 long[] a = this.values; 502 long[] b = that.values; 503 504 if (a.length == 0) 505 { 506 values = b; 507 return; 508 } 509 510 if (b.length == 0) 511 { 512 return; 513 } 514 515 // Optimize for case where the two sets are sure to have no overlap. 516 if (b[0] > a[a.length-1]) 517 { 518 // All IDs in 'b' are greater than those in 'a'. 519 long[] n = new long[a.length + b.length]; 520 System.arraycopy(a, 0, n, 0, a.length); 521 System.arraycopy(b, 0, n, a.length, b.length); 522 values = n; 523 return; 524 } 525 526 if (a[0] > b[b.length-1]) 527 { 528 // All IDs in 'a' are greater than those in 'b'. 529 long[] n = new long[a.length + b.length]; 530 System.arraycopy(b, 0, n, 0, b.length); 531 System.arraycopy(a, 0, n, b.length, a.length); 532 values = n; 533 return; 534 } 535 536 long[] n; 537 if ( b.length < a.length ) { 538 n = a; 539 a = b; 540 b = n; 541 } 542 543 n = new long[a.length + b.length]; 544 545 int ai, bi, ni; 546 for ( ni = 0, ai = 0, bi = 0; ai < a.length && bi < b.length; ) { 547 if ( a[ai] < b[bi] ) { 548 n[ni++] = a[ai++]; 549 } else if ( b[bi] < a[ai] ) { 550 n[ni++] = b[bi++]; 551 } else { 552 n[ni++] = a[ai]; 553 ai++; 554 bi++; 555 } 556 } 557 558 // Copy any remainder from the first array. 559 int aRemain = a.length - ai; 560 if (aRemain > 0) 561 { 562 System.arraycopy(a, ai, n, ni, aRemain); 563 ni += aRemain; 564 } 565 566 // Copy any remainder from the second array. 567 int bRemain = b.length - bi; 568 if (bRemain > 0) 569 { 570 System.arraycopy(b, bi, n, ni, bRemain); 571 ni += bRemain; 572 } 573 574 if (ni < n.length) 575 { 576 values = Arrays.copyOf(n, ni); 577 } 578 else 579 { 580 values = n; 581 } 582 } 583 584 /** 585 * Delete all IDs in this set that are in a given set. 586 * 587 * @param that The set of IDs to be deleted. It MUST be defined. 588 */ 589 public void deleteAll(EntryIDSet that) 590 { 591 if(!that.isDefined()) 592 { 593 return; 594 } 595 596 if (!isDefined()) 597 { 598 // Assume all IDs in the given set exists in this set. 599 if(undefinedSize != Long.MAX_VALUE) 600 { 601 undefinedSize -= that.size(); 602 } 603 return; 604 } 605 606 long[] a = this.values; 607 long[] b = that.values; 608 609 if (a.length == 0 || b.length == 0 610 // Optimize for cases where the two sets are sure to have no overlap. 611 || b[0] > a[a.length-1] 612 || a[0] > b[b.length-1]) 613 { 614 return; 615 } 616 617 long[] n = new long[a.length]; 618 619 int ai, bi, ni; 620 for ( ni = 0, ai = 0, bi = 0; ai < a.length && bi < b.length; ) { 621 if ( a[ai] < b[bi] ) { 622 n[ni++] = a[ai++]; 623 } else if ( b[bi] < a[ai] ) { 624 bi++; 625 } else { 626 ai++; 627 bi++; 628 } 629 } 630 631 System.arraycopy(a, ai, n, ni, a.length - ai); 632 ni += a.length - ai; 633 634 if (ni < a.length) 635 { 636 values = Arrays.copyOf(n, ni); 637 } 638 else 639 { 640 values = n; 641 } 642 } 643 644 /** 645 * Create an iterator over the set or an empty iterator 646 * if the set is not defined. 647 * 648 * @return An EntryID iterator. 649 */ 650 @Override 651 public Iterator<EntryID> iterator() 652 { 653 return iterator(null); 654 } 655 656 /** 657 * Create an iterator over the set or an empty iterator 658 * if the set is not defined. 659 * 660 * @param begin The entry ID of the first entry to return in the list. 661 * 662 * @return An EntryID iterator. 663 */ 664 public Iterator<EntryID> iterator(EntryID begin) 665 { 666 if (values != null) 667 { 668 // The set is defined. 669 return new IDSetIterator(values, begin); 670 } 671 // The set is not defined. 672 return new IDSetIterator(new long[0]); 673 } 674 675}