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 }