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.importLDIF;
028    
029    import com.sleepycat.je.dbi.MemoryBudget;
030    import org.opends.server.util.RuntimeInformation;
031    import org.opends.server.backends.jeb.EntryID;
032    import org.opends.server.backends.jeb.JebFormat;
033    
034    
035    /**
036     * A import ID set backed by an array of longs.
037     */
038    public class LongImportIDSet implements ImportIDSet {
039    
040    
041      //Overhead values gleamed from JHAT.
042      private final static int LONGS_OVERHEAD;
043      private final static int LONGS_OVERHEAD_32 = 25;
044      private final static int LONGS_OVERHEAD_64 = 25;
045    
046      /**
047       * The internal array where elements are stored.
048       */
049      private long[] array = null;
050    
051    
052      /**
053       * The number of valid elements in the array.
054       */
055      private int count = 0;
056    
057    
058      //Boolean to keep track if the instance is defined or not.
059      boolean isDefined=true;
060    
061    
062      //Size of the undefines.
063      private long undefinedSize = 0;
064    
065    
066      static {
067        if(RuntimeInformation.is64Bit()) {
068          LONGS_OVERHEAD = LONGS_OVERHEAD_64;
069        } else {
070          LONGS_OVERHEAD = LONGS_OVERHEAD_32;
071        }
072      }
073    
074      /**
075       * Create an empty instance.
076       */
077      public LongImportIDSet() {
078      }
079    
080      /**
081       * Create instance and add specified entry ID to the set.
082       *
083       * @param id The entry ID.
084       */
085      public LongImportIDSet(EntryID id) {
086         this.array = new long[1];
087         this.array[0] = id.longValue();
088         count=1;
089       }
090    
091      /**
092       * {@inheritDoc}
093       */
094      public void setEntryID(EntryID id) {
095        if(array == null) {
096          this.array = new long[1];
097        }
098        reset();
099        this.array[0] = id.longValue();
100        count=1;
101      }
102    
103    
104        /**
105       * {@inheritDoc}
106       */
107      public void reset() {
108        count = 0;
109        isDefined = true;
110        undefinedSize = 0;
111      }
112    
113      /**
114       * {@inheritDoc}
115       */
116       public boolean isDefined() {
117        return isDefined;
118      }
119    
120      /**
121       * {@inheritDoc}
122       */
123      public void setUndefined() {
124        array = null;
125        isDefined = false;
126      }
127    
128       /**
129       * {@inheritDoc}
130       */
131      public long getUndefinedSize() {
132        return undefinedSize;
133      }
134    
135      /**
136       * {@inheritDoc}
137       */
138      public int getMemorySize() {
139        if(array != null) {
140          return LONGS_OVERHEAD + MemoryBudget.byteArraySize(array.length * 8);
141        } else {
142          return LONGS_OVERHEAD;
143        }
144      }
145    
146      /**
147       * {@inheritDoc}
148       */
149      public void
150      merge(ImportIDSet importIDSet, int limit, boolean maintainCount) {
151        if(!isDefined()) {
152          if(maintainCount)  {
153            if(importIDSet.isDefined()) {
154              undefinedSize += importIDSet.size();
155            } else {
156              undefinedSize += importIDSet.getUndefinedSize();
157            }
158          }
159          return;
160        }
161        if(isDefined() && ((count + importIDSet.size()) > limit)) {
162          isDefined = false;
163          if(maintainCount)  {
164            undefinedSize = size() + importIDSet.size();
165          } else {
166            undefinedSize = Long.MAX_VALUE;
167          }
168          array = null;
169          count = 0;
170        } else {
171          addAll((LongImportIDSet) importIDSet);
172        }
173      }
174    
175    
176      /**
177       * {@inheritDoc}
178       */
179      public boolean merge(byte[] DBbytes, ImportIDSet importIdSet,
180                           int limit, boolean maintainCount) {
181        boolean incrLimitCount=false;
182        boolean dbUndefined = ((DBbytes[0] & 0x80) == 0x80);
183    
184        if(dbUndefined) {
185          isDefined=false;
186        } else if(!importIdSet.isDefined()) {
187          isDefined=false;
188          incrLimitCount=true;
189        } else {
190          array = JebFormat.entryIDListFromDatabase(DBbytes);
191          if(array.length + importIdSet.size() > limit) {
192              isDefined=false;
193              incrLimitCount=true;
194              importIdSet.setUndefined();
195          } else {
196            count = array.length;
197            addAll((LongImportIDSet) importIdSet);
198          }
199        }
200        return incrLimitCount;
201      }
202    
203    
204      /**
205       * {@inheritDoc}
206       */
207      public void addEntryID(EntryID entryID, int limit, boolean maintainCount) {
208        if(!isDefined()) {
209          if(maintainCount)  {
210            undefinedSize++;
211          }
212          return;
213        }
214        if(isDefined() && ((count + 1) > limit)) {
215          isDefined = false;
216          array = null;
217          if(maintainCount)  {
218            undefinedSize = count + 1;
219          } else {
220            undefinedSize = Long.MAX_VALUE;
221          }
222          count = 0;
223        } else {
224           add(entryID.longValue());
225        }
226      }
227    
228    
229      /**
230       * {@inheritDoc}
231       */
232      public byte[] toDatabase() {
233        if (isDefined()) {
234          return encode(null);
235        } else {
236          return JebFormat.entryIDUndefinedSizeToDatabase(undefinedSize);
237        }
238      }
239    
240      /**
241       * Decodes a set from a byte array.
242       * @param bytes The encoded value.
243       */
244      void decode(byte[] bytes)
245      {
246        if (bytes == null)
247        {
248          count = 0;
249          return;
250        }
251    
252        int count = bytes.length / 8;
253        resize(count);
254    
255        for (int pos = 0, i = 0; i < count; i++)
256        {
257          long v = 0;
258          v |= (bytes[pos++] & 0xFFL) << 56;
259          v |= (bytes[pos++] & 0xFFL) << 48;
260          v |= (bytes[pos++] & 0xFFL) << 40;
261          v |= (bytes[pos++] & 0xFFL) << 32;
262          v |= (bytes[pos++] & 0xFFL) << 24;
263          v |= (bytes[pos++] & 0xFFL) << 16;
264          v |= (bytes[pos++] & 0xFFL) << 8;
265          v |= (bytes[pos++] & 0xFFL);
266          array[i] = v;
267        }
268        this.count = count;
269      }
270    
271    
272      /**
273       * Encode this value into a byte array.
274       * @param bytes The array into which the value will be encoded.  If the
275       * provided array is null, or is not big enough, a new array will be
276       * allocated.
277       * @return The encoded array. If the provided array was bigger than needed
278       * to encode the value then the provided array is returned and the number
279       * of bytes of useful data is given by the encodedSize method.
280       */
281      byte[] encode(byte[] bytes) {
282        int encodedSize = count * 8;
283        if (bytes == null || bytes.length < encodedSize)
284        {
285          bytes = new byte[encodedSize];
286        }
287    
288        for (int pos = 0, i = 0; i < count; i++)
289        {
290          long v = array[i];
291          bytes[pos++] = (byte) ((v >>> 56) & 0xFF);
292          bytes[pos++] = (byte) ((v >>> 48) & 0xFF);
293          bytes[pos++] = (byte) ((v >>> 40) & 0xFF);
294          bytes[pos++] = (byte) ((v >>> 32) & 0xFF);
295          bytes[pos++] = (byte) ((v >>> 24) & 0xFF);
296          bytes[pos++] = (byte) ((v >>> 16) & 0xFF);
297          bytes[pos++] = (byte) ((v >>> 8) & 0xFF);
298          bytes[pos++] = (byte) (v & 0xFF);
299        }
300    
301        return bytes;
302      }
303    
304    
305    
306      /**
307       * This is very much like Arrays.binarySearch except that it searches only
308       * an initial portion of the provided array.
309       * @param a The array to be searched.
310       * @param count The number of initial elements in the array to be searched.
311       * @param key The element to search for.
312       * @return See Arrays.binarySearch.
313       */
314      private static int binarySearch(long[] a, int count, long key) {
315        int low = 0;
316        int high = count-1;
317    
318        while (low <= high)
319        {
320          int mid = (low + high) >> 1;
321          long midVal = a[mid];
322    
323          if (midVal < key)
324            low = mid + 1;
325          else if (midVal > key)
326            high = mid - 1;
327          else
328            return mid; // key found
329        }
330        return -(low + 1);  // key not found.
331      }
332    
333    
334    
335      /**
336       * Add a new value to the set.
337       * @param v The value to be added.
338       * @return true if the value was added, false if it was already present
339       * in the set.
340       */
341      private boolean add(long v) {
342        resize(count+1);
343    
344        if (count == 0 || v > array[count-1])
345        {
346          array[count++] = v;
347          return true;
348        }
349    
350        int pos = binarySearch(array, count, v);
351        if (pos >=0)
352        {
353          return false;
354        }
355    
356        // For a negative return value r, the index -(r+1) gives the array
357        // index at which the specified value can be inserted to maintain
358        // the sorted order of the array.
359        pos = -(pos+1);
360    
361        System.arraycopy(array, pos, array, pos+1, count-pos);
362        array[pos] = v;
363        count++;
364        return true;
365      }
366    
367      /**
368       * Adds all the elements of a provided set to this set if they are not
369       * already present.
370       * @param that The set of elements to be added.
371       */
372      private void addAll(LongImportIDSet that) {
373        resize(this.count+that.count);
374    
375        if (that.count == 0)
376        {
377          return;
378        }
379    
380        // Optimize for the case where the two sets are sure to have no overlap.
381        if (this.count == 0 || that.array[0] > this.array[this.count-1])
382        {
383          System.arraycopy(that.array, 0, this.array, this.count, that.count);
384          count += that.count;
385          return;
386        }
387    
388        if (this.array[0] > that.array[that.count-1])
389        {
390          System.arraycopy(this.array, 0, this.array, that.count, this.count);
391          System.arraycopy(that.array, 0, this.array, 0, that.count);
392          count += that.count;
393          return;
394        }
395    
396        int destPos = binarySearch(this.array, this.count, that.array[0]);
397        if (destPos < 0)
398        {
399          destPos = -(destPos+1);
400        }
401    
402        // Make space for the copy.
403        int aCount = this.count - destPos;
404        int aPos = destPos + that.count;
405        int aEnd = aPos + aCount;
406        System.arraycopy(this.array, destPos, this.array, aPos, aCount);
407    
408        // Optimize for the case where there is no overlap.
409        if (this.array[aPos] > that.array[that.count-1])
410        {
411          System.arraycopy(that.array, 0, this.array, destPos, that.count);
412          count += that.count;
413          return;
414        }
415    
416        int bPos;
417        for ( bPos = 0; aPos < aEnd && bPos < that.count; )
418        {
419          if ( this.array[aPos] < that.array[bPos] )
420          {
421            this.array[destPos++] = this.array[aPos++];
422          }
423          else if ( this.array[aPos] > that.array[bPos] )
424          {
425            this.array[destPos++] = that.array[bPos++];
426          }
427          else
428          {
429            this.array[destPos++] = this.array[aPos++];
430            bPos++;
431          }
432        }
433    
434        // Copy any remainder.
435        int aRemain = aEnd - aPos;
436        if (aRemain > 0)
437        {
438          System.arraycopy(this.array, aPos, this.array, destPos, aRemain);
439          destPos += aRemain;
440        }
441    
442        int bRemain = that.count - bPos;
443        if (bRemain > 0)
444        {
445          System.arraycopy(that.array, bPos, this.array, destPos, bRemain);
446          destPos += bRemain;
447        }
448    
449        count = destPos;
450      }
451    
452    
453    
454      /**
455       * {@inheritDoc}
456       */
457      public int size() {
458        return count;
459      }
460    
461    
462      /**
463       * Ensures capacity of the internal array for a given number of elements.
464       * @param size The internal array will be guaranteed to be at least this
465       * size.
466       */
467      private void resize(int size) {
468        if (array == null)
469        {
470          array = new long[size];
471        }
472        else if (array.length < size)
473        {
474          // Expand the size of the array in powers of two.
475          int newSize = array.length == 0 ? 1 : array.length;
476          do
477          {
478            newSize *= 2;
479          } while (newSize < size);
480    
481          long[] newBytes = new long[newSize];
482          System.arraycopy(array, 0, newBytes, 0, count);
483          array = newBytes;
484        }
485      }
486    
487    }