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 }