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