1 8 package org.ozoneDB.core.storage.gammaStore; 9 10 import java.io.Serializable ; 11 12 32 public class Loc implements Serializable { 33 34 protected long[] keys; 35 private int[] inUse; 36 private int capacity; 37 private int size; 38 private int handleToLast; 39 40 public Loc(int capacity, int slack) { 41 this.capacity = capacity; 42 keys = new long[capacity + slack]; 43 int inUseSize = keys.length / 32; 44 if (keys.length % 32 != 0) { 45 inUseSize++; 46 } 47 inUse = new int[inUseSize]; 48 handleToLast = -1; 49 } 50 51 public Loc(int capacity, float relSlack) { 52 this(capacity, (int) (relSlack * capacity) > 0 ? (int) (relSlack * capacity) : 1); 53 } 54 55 60 public int getKeyPos(long key) { 61 int result = search(key); 62 63 if (!isInUse(result) || key != keys[result]) { 64 result = -1; 65 } 66 return result; 67 } 68 69 74 public long getKey(int pos) { 75 if (!isInUse(pos)) { 76 throw new IllegalArgumentException ("position not in use"); 77 } 78 return keys[pos]; 79 } 80 81 87 public int getKeyPosOrNearestGreater(long key) { 88 int result = -1; 89 for(int handle = search(key); handle <= handleToLast; handle++) { 90 if (isInUse(handle) && keys[handle] >= key) { 91 result = handle; 92 break; 93 } 94 } 95 return result; 96 } 97 98 104 public int getKeyPosOrNearestSmaller(long key) { 105 int result = -1; 106 for(int handle = search(key); handle >= 0; handle--) { 107 if (isInUse(handle) && keys[handle] <= key) { 108 result = handle; 109 break; 110 } 111 } 112 return result; 113 } 114 115 121 public int removeKey(long key) { 122 int result = getKeyPos(key); 123 if (result < 0) { 124 return -1; 125 } 126 removePos(result); 127 return result; 128 } 129 130 141 public int putKey(long key) { 142 if (handleToLast == -1 || keys[handleToLast] < key) { 143 if (handleToLast == keys.length - 1) { 144 compress(); 145 } 146 if (size >= capacity) { 148 throw new IndexOutOfBoundsException ("cannot grow any larger"); 149 } 150 handleToLast++; 151 keys[handleToLast] = key; 152 setInUse(handleToLast, true); 153 size++; 154 return handleToLast; 155 } 156 157 compress(); 162 int result = getKeyPosOrNearestGreater(key); 163 if (result >= 0) { 164 if (isInUse(result) && keys[result] == key) { 165 return result; 166 } 167 } else { 168 result = handleToLast >= 0 ? handleToLast : 0; 169 } 170 171 if (size >= capacity) { 172 throw new IndexOutOfBoundsException ("cannot grow any larger (size = " + size + ", capacity = " + capacity); 173 } 174 175 for (int i = handleToLast; i >= result; i--) { 176 move(i, i + 1); 179 } 180 handleToLast++; 181 keys[result] = key; 182 setInUse(result, true); 183 size++; 184 return result; 185 } 186 187 193 public int next(int handle) { 194 if (handle >= 0 && !isInUse(handle)) { 195 throw new IllegalArgumentException ("handle is not in use"); 196 } 197 handle++; 198 int result; 199 for(result = -1; result < 0 && handle <= handleToLast; handle++) { 200 if (isInUse(handle)) { 201 result = handle; 202 } 203 } 204 return result; 205 } 206 207 210 protected final boolean isInUse(int handle) { 211 if (handle < 0 || handle >= keys.length) { 212 throw new IllegalArgumentException ("handle should be >= 0 and < " + keys.length + ", is " + handle); 213 } 214 int pos = handle / 32; 215 int mask = 1 << (handle % 32); 216 return (inUse[pos] & mask ) != 0; 217 } 218 219 222 private boolean setInUse(int handle, boolean inUse) { 223 int pos = handle / 32; 224 int mask = 1 << (handle % 32); 225 boolean result = (this.inUse[pos] | mask) != 0; 226 if (inUse) { 227 this.inUse[pos] |= mask; 228 } else { 229 this.inUse[pos] &= ~mask; 230 } 231 return result; 232 } 233 234 238 public void removePos(int handle) { 239 if (!setInUse(handle, false)) { 240 throw new IllegalArgumentException ("pos " + handle + " has already been removed"); 241 } 242 size--; 243 while (handleToLast >= 0 && !isInUse(handleToLast)) { 245 handleToLast--; 246 } 247 } 248 249 254 private int search(long key) { 255 return (handleToLast < 0) ? 0 : search(key, 0, handleToLast); 256 } 257 258 265 private int search(long key, int low, int high) { 266 if (low > high) { 267 throw new IllegalArgumentException ("low should be <= high; low == " + low + ", high == " + high + ", key == " + key + ", handleToLast == " + handleToLast); 268 } 269 for(;;) { 270 int result = (low + high) / 2; 271 if (low >= high || keys[result] == key) { 272 return result; 273 } 274 if (key < keys[result]) { 275 high = result - 1; 276 } else { 277 low = result + 1; 278 } 279 } 280 } 281 282 285 private void compress() { 286 handleToLast = -1; 287 for(int i = 0; i < keys.length; i++) { 288 if (isInUse(i)) { 289 handleToLast++; 290 if (i > handleToLast) { 291 move(i, handleToLast); 292 } 293 } else { 294 keys[i] = 0; 297 } 298 } 299 } 300 301 305 protected void move(int handleFrom, int handleTo) { 306 if (!isInUse(handleFrom)) { 307 throw new IllegalArgumentException ("handleFrom (" + handleFrom + ") must be in use"); 308 } 309 if (isInUse(handleTo)) { 310 throw new IllegalArgumentException ("handleTo (" + handleTo + ") must not be in use"); 311 } 312 keys[handleTo] = keys[handleFrom]; 313 keys[handleFrom] = 0; 316 setInUse(handleFrom, false); 317 setInUse(handleTo, true); 318 } 319 320 public String toString() { 321 StringBuffer result = new StringBuffer ("handleToLast="); 322 result.append(handleToLast).append("; ["); 323 for (int i = 0; i < keys.length; i++) { 324 result.append(keys[i]); 325 if (!isInUse(i)) { 326 result.append("D"); 327 } 328 if (i < keys.length - 1) { 329 result.append(", "); 330 } else { 331 result.append("]"); 332 } 333 } 334 return result.toString(); 335 } 336 337 340 public int size() { 341 return size; 342 } 343 344 public long getMinKey() { 345 return keys[getMinPos()]; 346 } 347 348 public long getMaxKey() { 349 return keys[getMaxPos()]; 350 } 351 352 public int getMinPos() { 353 for (int i = 0; i < keys.length; i++) { 354 if (isInUse(i)) { 355 return i; 356 } 357 } 358 throw new RuntimeException ("may not call getMinKey() when empty"); 359 } 360 361 public int getMaxPos() { 362 for (int i = handleToLast; i >= 0; i--) { 363 if (isInUse(i)) { 364 return i; 365 } 366 } 367 throw new RuntimeException ("may not call getMaxKey() when empty"); 368 } 369 370 } 371 | Popular Tags |