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 }