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