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 }