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}