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; 028 029 import java.io.DataInputStream; 030 import java.io.IOException; 031 032 033 /** 034 * This class represents a sorted set of longs. Internally it uses an array 035 * that can grow when necessary. A goal of this class is to avoid memory 036 * allocations where possible. 037 */ 038 public class Longs 039 { 040 /** 041 * The internal array where elements are stored. 042 */ 043 private long[] array = null; 044 045 046 /** 047 * The number of valid elements in the array. 048 */ 049 private int count = 0; 050 051 052 053 /** 054 * Construct a new empty set. 055 */ 056 public Longs() 057 { 058 } 059 060 061 062 /** 063 * Decodes a set from a byte array. 064 * @param bytes The encoded value. 065 */ 066 void decode(byte[] bytes) 067 { 068 if (bytes == null) 069 { 070 count = 0; 071 return; 072 } 073 074 int count = bytes.length / 8; 075 resize(count); 076 077 for (int pos = 0, i = 0; i < count; i++) 078 { 079 long v = 0; 080 v |= (bytes[pos++] & 0xFFL) << 56; 081 v |= (bytes[pos++] & 0xFFL) << 48; 082 v |= (bytes[pos++] & 0xFFL) << 40; 083 v |= (bytes[pos++] & 0xFFL) << 32; 084 v |= (bytes[pos++] & 0xFFL) << 24; 085 v |= (bytes[pos++] & 0xFFL) << 16; 086 v |= (bytes[pos++] & 0xFFL) << 8; 087 v |= (bytes[pos++] & 0xFFL); 088 array[i] = v; 089 } 090 this.count = count; 091 } 092 093 094 095 /** 096 * Get the number of bytes needed to encode this value into a byte array. 097 * @return The number of bytes needed to encode this value into a byte array. 098 */ 099 public int encodedSize() 100 { 101 return count*8; 102 } 103 104 105 106 /** 107 * Encode this value into a byte array. 108 * @param bytes The array into which the value will be encoded. If the 109 * provided array is null, or is not big enough, a new array will be 110 * allocated. 111 * @return The encoded array. If the provided array was bigger than needed 112 * to encode the value then the provided array is returned and the number 113 * of bytes of useful data is given by the encodedSize method. 114 */ 115 byte[] encode(byte[] bytes) 116 { 117 int encodedSize = encodedSize(); 118 if (bytes == null || bytes.length < encodedSize) 119 { 120 bytes = new byte[encodedSize]; 121 } 122 123 for (int pos = 0, i = 0; i < count; i++) 124 { 125 long v = array[i]; 126 bytes[pos++] = (byte) ((v >>> 56) & 0xFF); 127 bytes[pos++] = (byte) ((v >>> 48) & 0xFF); 128 bytes[pos++] = (byte) ((v >>> 40) & 0xFF); 129 bytes[pos++] = (byte) ((v >>> 32) & 0xFF); 130 bytes[pos++] = (byte) ((v >>> 24) & 0xFF); 131 bytes[pos++] = (byte) ((v >>> 16) & 0xFF); 132 bytes[pos++] = (byte) ((v >>> 8) & 0xFF); 133 bytes[pos++] = (byte) (v & 0xFF); 134 } 135 136 return bytes; 137 } 138 139 140 141 /** 142 * This is very much like Arrays.binarySearch except that it searches only 143 * an initial portion of the provided array. 144 * @param a The array to be searched. 145 * @param count The number of initial elements in the array to be searched. 146 * @param key The element to search for. 147 * @return See Arrays.binarySearch. 148 */ 149 private static int binarySearch(long[] a, int count, long key) 150 { 151 int low = 0; 152 int high = count-1; 153 154 while (low <= high) 155 { 156 int mid = (low + high) >> 1; 157 long midVal = a[mid]; 158 159 if (midVal < key) 160 low = mid + 1; 161 else if (midVal > key) 162 high = mid - 1; 163 else 164 return mid; // key found 165 } 166 return -(low + 1); // key not found. 167 } 168 169 170 171 /** 172 * Add a new value to the set. 173 * @param v The value to be added. 174 * @return true if the value was added, false if it was already present 175 * in the set. 176 */ 177 public boolean add(long v) 178 { 179 resize(count+1); 180 181 if (count == 0 || v > array[count-1]) 182 { 183 array[count++] = v; 184 return true; 185 } 186 187 int pos = binarySearch(array, count, v); 188 if (pos >=0) 189 { 190 return false; 191 } 192 193 // For a negative return value r, the index -(r+1) gives the array 194 // index at which the specified value can be inserted to maintain 195 // the sorted order of the array. 196 pos = -(pos+1); 197 198 System.arraycopy(array, pos, array, pos+1, count-pos); 199 array[pos] = v; 200 count++; 201 return true; 202 } 203 204 /** 205 * Adds all the elements of a provided set to this set if they are not 206 * already present. 207 * @param that The set of elements to be added. 208 */ 209 public void addAll(Longs that) 210 { 211 resize(this.count+that.count); 212 213 if (that.count == 0) 214 { 215 return; 216 } 217 218 // Optimize for the case where the two sets are sure to have no overlap. 219 if (this.count == 0 || that.array[0] > this.array[this.count-1]) 220 { 221 System.arraycopy(that.array, 0, this.array, this.count, that.count); 222 count += that.count; 223 return; 224 } 225 226 if (this.array[0] > that.array[that.count-1]) 227 { 228 System.arraycopy(this.array, 0, this.array, that.count, this.count); 229 System.arraycopy(that.array, 0, this.array, 0, that.count); 230 count += that.count; 231 return; 232 } 233 234 int destPos = binarySearch(this.array, this.count, that.array[0]); 235 if (destPos < 0) 236 { 237 destPos = -(destPos+1); 238 } 239 240 // Make space for the copy. 241 int aCount = this.count - destPos; 242 int aPos = destPos + that.count; 243 int aEnd = aPos + aCount; 244 System.arraycopy(this.array, destPos, this.array, aPos, aCount); 245 246 // Optimize for the case where there is no overlap. 247 if (this.array[aPos] > that.array[that.count-1]) 248 { 249 System.arraycopy(that.array, 0, this.array, destPos, that.count); 250 count += that.count; 251 return; 252 } 253 254 int bPos; 255 for ( bPos = 0; aPos < aEnd && bPos < that.count; ) 256 { 257 if ( this.array[aPos] < that.array[bPos] ) 258 { 259 this.array[destPos++] = this.array[aPos++]; 260 } 261 else if ( this.array[aPos] > that.array[bPos] ) 262 { 263 this.array[destPos++] = that.array[bPos++]; 264 } 265 else 266 { 267 this.array[destPos++] = this.array[aPos++]; 268 bPos++; 269 } 270 } 271 272 // Copy any remainder. 273 int aRemain = aEnd - aPos; 274 if (aRemain > 0) 275 { 276 System.arraycopy(this.array, aPos, this.array, destPos, aRemain); 277 destPos += aRemain; 278 } 279 280 int bRemain = that.count - bPos; 281 if (bRemain > 0) 282 { 283 System.arraycopy(that.array, bPos, this.array, destPos, bRemain); 284 destPos += bRemain; 285 } 286 287 count = destPos; 288 } 289 290 291 /** 292 * Deletes all the elements of a provided set from this set if they are 293 * present. 294 * @param that The set of elements to be deleted. 295 */ 296 public void deleteAll(Longs that) 297 { 298 int thisPos, thatPos, destPos; 299 for ( destPos = 0, thisPos = 0, thatPos = 0; 300 thisPos < count && thatPos < that.count; ) 301 { 302 if ( array[thisPos] < that.array[thatPos] ) 303 { 304 array[destPos++] = array[thisPos++]; 305 } 306 else if ( array[thisPos] > that.array[thatPos] ) 307 { 308 thatPos++; 309 } 310 else 311 { 312 thisPos++; 313 thatPos++; 314 } 315 } 316 317 System.arraycopy(array, thisPos, array, destPos, count - thisPos); 318 destPos += count - thisPos; 319 320 count = destPos; 321 } 322 323 324 /** 325 * Return the number of elements in the set. 326 * @return The number of elements in the set. 327 */ 328 public int size() 329 { 330 return count; 331 } 332 333 334 /** 335 * Decode a value from a data input stream. 336 * @param dataInputStream The data input stream to read the value from. 337 * @throws IOException If an I/O error occurs while reading the value. 338 */ 339 public void decode(DataInputStream dataInputStream) 340 throws IOException 341 { 342 int len = dataInputStream.readInt(); 343 int count = len/8; 344 resize(count); 345 for (int i = 0; i < count; i++) 346 { 347 array[i] = dataInputStream.readLong(); 348 } 349 this.count = count; 350 } 351 352 353 /** 354 * Ensures capacity of the internal array for a given number of elements. 355 * @param size The internal array will be guaranteed to be at least this 356 * size. 357 */ 358 private void resize(int size) 359 { 360 if (array == null) 361 { 362 array = new long[size]; 363 } 364 else if (array.length < size) 365 { 366 // Expand the size of the array in powers of two. 367 int newSize = array.length == 0 ? 1 : array.length; 368 do 369 { 370 newSize *= 2; 371 } while (newSize < size); 372 373 long[] newBytes = new long[newSize]; 374 System.arraycopy(array, 0, newBytes, 0, count); 375 array = newBytes; 376 } 377 } 378 379 380 /** 381 * Clears the set leaving it empty. 382 */ 383 public void clear() 384 { 385 count = 0; 386 } 387 388 389 390 /** 391 * Convert the set to a new array of longs. 392 * @return An array of longs. 393 */ 394 public long[] toArray() 395 { 396 long[] dst = new long[count]; 397 398 System.arraycopy(array, 0, dst, 0, count); 399 return dst; 400 } 401 402 403 /** 404 * {@inheritDoc} 405 */ 406 @Override 407 public String toString() 408 { 409 StringBuilder b = new StringBuilder(); 410 b.append(count); 411 if (count > 0) 412 { 413 b.append('['); 414 b.append(array[0]); 415 if (count > 1) 416 { 417 b.append(':'); 418 b.append(array[count-1]); 419 } 420 b.append(']'); 421 } 422 return b.toString(); 423 } 424 425 }