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 }