001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm; 003 004import java.util.AbstractSet; 005import java.util.Collection; 006import java.util.ConcurrentModificationException; 007import java.util.Iterator; 008import java.util.Map; 009import java.util.NoSuchElementException; 010import java.util.Set; 011 012/** 013 * A Set-like class that allows looking up equivalent preexising instance. 014 * It is useful whereever one would use self-mapping construct like 015 * <code>Map<T,T>.put(t,t), that is, for caches, uniqueness filters or similar. 016 * 017 * The semantics of equivalency can be external to the object, using the 018 * {@link Hash} interface. The set also supports querying for entries using 019 * different key type, in case you can provide a Hash implementation 020 * that can resolve the equality. 021 * 022 * <h2>Examples</h2> 023 * <ul><li>A String cache: 024 * <pre> 025 * Storage<String> cache = new Storage(); // use default Hash 026 * for (String input : data) { 027 * String onlyOne = cache.putIfUnique(input); 028 * .... 029 * } 030 * </pre></li> 031 * <li>Identity-based set: 032 * <pre> 033 * Storage<Object> identity = new Storage(new Hash<Object,Object> { 034 * public int getHashCode(Object o) { 035 * return System.identityHashCode(o); 036 * } 037 * public boolean equals(Object o1, Object o2) { 038 * return o1 == o2; 039 * } 040 * }); 041 * </pre></li> 042 * <li>An object with int ID and id-based lookup: 043 * <pre> 044 * class Thing { int id; } 045 * Storage<Thing> things = new Storage(new Hash<Thing,Thing>() { 046 * public int getHashCode(Thing t) { 047 * return t.id; 048 * } 049 * public boolean equals(Thing t1, Thing t2) { 050 * return t1 == t2; 051 * } 052 * }); 053 * Map<Integer,Thing> fk = things.foreignKey(new Hash<Integer,Thing>() { 054 * public int getHashCode(Integer i) { 055 * return i.getIntValue(); 056 * } 057 * public boolean equals(Integer k, Thing t) { 058 * return t.id == k.getIntvalue(); 059 * } 060 * } 061 * 062 * things.put(new Thing(3)); 063 * assert things.get(new Thing(3)) == fk.get(3); 064 * </pre></li> 065 * 066 * 067 * @author nenik 068 */ 069public class Storage<T> extends AbstractSet<T> { 070 071 public static class PrimitiveIdHash implements Hash<PrimitiveId, PrimitiveId> { 072 073 @Override 074 public int getHashCode(PrimitiveId k) { 075 return (int)k.getUniqueId() ^ k.getType().hashCode(); 076 } 077 078 @Override 079 public boolean equals(PrimitiveId key, PrimitiveId value) { 080 if (key == null || value == null) return false; 081 return key.getUniqueId() == value.getUniqueId() && key.getType() == value.getType(); 082 } 083 } 084 085 private final Hash<? super T,? super T> hash; 086 private T[] data; 087 private int mask; 088 private int size; 089 private transient volatile int modCount = 0; 090 private float loadFactor = 0.6f; 091 private static final int DEFAULT_CAPACITY = 16; 092 private final boolean safeIterator; 093 private boolean arrayCopyNecessary; 094 095 /** 096 * Constructs a new {@code Storage} with default capacity (16). 097 */ 098 public Storage() { 099 this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, false); 100 } 101 102 /** 103 * Constructs a new {@code Storage} with given capacity. 104 */ 105 public Storage(int capacity) { 106 this(Storage.<T>defaultHash(), capacity, false); 107 } 108 109 public Storage(Hash<? super T,? super T> ha) { 110 this(ha, DEFAULT_CAPACITY, false); 111 } 112 113 public Storage(boolean safeIterator) { 114 this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, safeIterator); 115 } 116 117 public Storage(int capacity, boolean safeIterator) { 118 this(Storage.<T>defaultHash(), capacity, safeIterator); 119 } 120 121 public Storage(Hash<? super T,? super T> ha, boolean safeIterator) { 122 this(ha, DEFAULT_CAPACITY, safeIterator); 123 } 124 125 public Storage(Hash<? super T, ? super T> ha, int capacity) { 126 this(ha, capacity, false); 127 } 128 /** 129 * constructor 130 * @param ha 131 * @param capacity 132 * @param safeIterator If set to false, you must not modify the Storage 133 * while iterating over it. If set to true, you can safely 134 * modify, but the read-only iteration will happen on a copy 135 * of the unmodified Storage. 136 * This is similar to CopyOnWriteArrayList. 137 */ 138 public Storage(Hash<? super T, ? super T> ha, int capacity, boolean safeIterator) { 139 this.hash = ha; 140 int cap = 1 << (int)(Math.ceil(Math.log(capacity/loadFactor) / Math.log(2))); 141 @SuppressWarnings("unchecked") T[] newData = (T[]) new Object[cap]; 142 data = newData; 143 mask = data.length - 1; 144 this.safeIterator = safeIterator; 145 } 146 147 private void copyArray() { 148 if (arrayCopyNecessary) { 149 @SuppressWarnings("unchecked") T[] newData = (T[]) new Object[data.length]; 150 System.arraycopy(data, 0, newData, 0, data.length); 151 data = newData; 152 arrayCopyNecessary = false; 153 } 154 } 155 156 // --------------- Collection implementation ------------------------ 157 @Override 158 public synchronized int size() { 159 return size; 160 } 161 162 @Override 163 public synchronized Iterator<T> iterator() { 164 if (safeIterator) { 165 arrayCopyNecessary = true; 166 return new SafeReadonlyIter(data); 167 } else 168 return new Iter(); 169 170 } 171 172 @Override 173 public synchronized boolean contains(Object o) { 174 @SuppressWarnings("unchecked") T t = (T) o; 175 int bucket = getBucket(hash, t); 176 return bucket >= 0; 177 } 178 179 @Override 180 public synchronized boolean add(T t) { 181 T orig = putUnique(t); 182 return orig == t; 183 } 184 185 @Override 186 public synchronized boolean remove(Object o) { 187 @SuppressWarnings("unchecked") T t = (T) o; 188 T tOrig = removeElem(t); 189 return tOrig != null; 190 } 191 192 @Override 193 public synchronized void clear() { 194 copyArray(); 195 modCount++; 196 size = 0; 197 for (int i = 0; i<data.length; i++) { 198 data[i] = null; 199 } 200 } 201 202 @Override 203 public synchronized int hashCode() { 204 int h = 0; 205 for (T t : this) { 206 h += hash.getHashCode(t); 207 } 208 return h; 209 } 210 211 // ----------------- Extended API ---------------------------- 212 213 public synchronized T put(T t) { 214 copyArray(); 215 modCount++; 216 ensureSpace(); 217 218 int bucket = getBucket(hash, t); 219 if (bucket < 0) { 220 size++; 221 bucket = ~bucket; 222 assert data[bucket] == null; 223 } 224 225 T old = data[bucket]; 226 data[bucket] = t; 227 228 return old; 229 } 230 231 public synchronized T get(T t) { 232 int bucket = getBucket(hash, t); 233 return bucket < 0 ? null : data[bucket]; 234 } 235 236 public synchronized T putUnique(T t) { 237 copyArray(); 238 modCount++; 239 ensureSpace(); 240 241 int bucket = getBucket(hash, t); 242 if (bucket < 0) { // unique 243 size++; 244 assert data[~bucket] == null; 245 data[~bucket] = t; 246 return t; 247 } 248 249 return data[bucket]; 250 } 251 252 public synchronized T removeElem(T t) { 253 copyArray(); 254 modCount++; 255 int bucket = getBucket(hash, t); 256 return bucket < 0 ? null : doRemove(bucket); 257 } 258 259 public <K> Map<K,T> foreignKey(Hash<K,? super T> h) { 260 return new FMap<K>(h); 261 } 262 263 // ---------------- Implementation 264 265 /** 266 * Additional mixing of hash 267 */ 268 private int rehash(int h) { 269 //return 54435761*h; 270 return 1103515245*h >> 2; 271 } 272 273 /** 274 * Finds a bucket for given key. 275 * 276 * @param key The key to compare 277 * @return the bucket equivalent to the key or -(bucket) as an empty slot 278 * where such an entry can be stored. 279 */ 280 private <K> int getBucket(Hash<K,? super T> ha, K key) { 281 T entry; 282 int hcode = rehash(ha.getHashCode(key)); 283 int bucket = hcode & mask; 284 while ((entry = data[bucket]) != null) { 285 if (ha.equals(key, entry)) 286 return bucket; 287 bucket = (bucket+1) & mask; 288 } 289 return ~bucket; 290 } 291 292 private T doRemove(int slot) { 293 T t = data[slot]; 294 assert t != null; 295 296 fillTheHole(slot); // fill the hole (or null it) 297 size--; 298 return t; 299 } 300 301 private void fillTheHole(int hole) { 302 int bucket = (hole+1) & mask; 303 T entry; 304 305 while ((entry = data[bucket]) != null) { 306 int right = rehash(hash.getHashCode(entry)) & mask; 307 // if the entry should be in <hole+1,bucket-1> (circular-wise) 308 // we can't move it. The move can be proved safe otherwise, 309 // because the entry safely belongs to <previous_null+1,hole> 310 if ((bucket < right && (right <= hole || hole <= bucket)) || 311 (right <=hole && hole <= bucket)) { 312 313 data[hole] = data[bucket]; 314 hole = bucket; 315 } 316 bucket = (bucket+1) & mask; 317 } 318 319 // no entry belongs here, just null out the slot 320 data[hole] = null; 321 } 322 323 private void ensureSpace() { 324 if (size > data.length*loadFactor) { // rehash 325 @SuppressWarnings("unchecked") T[] big = (T[]) new Object[data.length * 2]; 326 int nMask = big.length - 1; 327 328 for (T o : data) { 329 if (o == null) { 330 continue; 331 } 332 int bucket = rehash(hash.getHashCode(o)) & nMask; 333 while (big[bucket] != null) { 334 bucket = (bucket+1) & nMask; 335 } 336 big[bucket] = o; 337 } 338 339 data = big; 340 mask = nMask; 341 } 342 } 343 344 // -------------- factories -------------------- 345 /** 346 * A factory for default hash implementation. 347 * @return a hash implementation that just delegates to object's own 348 * hashCode and equals. 349 */ 350 public static <O> Hash<O,O> defaultHash() { 351 return new Hash<O,O>() { 352 @Override 353 public int getHashCode(O t) { 354 return t.hashCode(); 355 } 356 @Override 357 public boolean equals(O t1, O t2) { 358 return t1.equals(t2); 359 } 360 }; 361 } 362 /* 363 public static <O> Hash<O,O> identityHash() { 364 return new Hash<O,O>() { 365 public int getHashCode(O t) { 366 return System.identityHashCode(t); 367 } 368 public boolean equals(O t1, O t2) { 369 return t1 == t2; 370 } 371 }; 372 } 373 */ 374 375 private final class FMap<K> implements Map<K,T> { 376 Hash<K,? super T> fHash; 377 378 private FMap(Hash<K,? super T> h) { 379 fHash = h; 380 } 381 382 @Override 383 public int size() { 384 return Storage.this.size(); 385 } 386 387 @Override 388 public boolean isEmpty() { 389 return Storage.this.isEmpty(); 390 } 391 392 @Override 393 public boolean containsKey(Object o) { 394 @SuppressWarnings("unchecked") K key = (K) o; 395 int bucket = getBucket(fHash, key); 396 return bucket >= 0; 397 } 398 399 @Override 400 public boolean containsValue(Object value) { 401 return Storage.this.contains(value); 402 } 403 404 @Override 405 public T get(Object o) { 406 @SuppressWarnings("unchecked") K key = (K) o; 407 int bucket = getBucket(fHash, key); 408 return bucket < 0 ? null : data[bucket]; 409 } 410 411 @Override 412 public T put(K key, T value) { 413 if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key"); 414 return Storage.this.put(value); 415 } 416 417 @Override 418 public T remove(Object o) { 419 modCount++; 420 @SuppressWarnings("unchecked") K key = (K) o; 421 int bucket = getBucket(fHash, key); 422 423 return bucket < 0 ? null : doRemove(bucket); 424 } 425 426 @Override 427 public void putAll(Map<? extends K, ? extends T> m) { 428 if (m instanceof Storage.FMap) { 429 Storage.this.addAll(m.values()); 430 } else { 431 for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) { 432 put(e.getKey(), e.getValue()); 433 } 434 } 435 } 436 437 @Override 438 public void clear() { 439 Storage.this.clear(); 440 } 441 442 @Override 443 public Set<K> keySet() { 444 throw new UnsupportedOperationException(); 445 } 446 447 @Override 448 public Collection<T> values() { 449 return Storage.this; 450 } 451 452 @Override 453 public Set<Entry<K, T>> entrySet() { 454 throw new UnsupportedOperationException(); 455 } 456 } 457 458 private final class SafeReadonlyIter implements Iterator<T> { 459 final T[] data; 460 int slot = 0; 461 462 SafeReadonlyIter(T[] data) { 463 this.data = data; 464 } 465 466 @Override 467 public boolean hasNext() { 468 align(); 469 return slot < data.length; 470 } 471 472 @Override 473 public T next() { 474 if (!hasNext()) throw new NoSuchElementException(); 475 return data[slot++]; 476 } 477 478 @Override 479 public void remove() { 480 throw new UnsupportedOperationException(); 481 } 482 483 private void align() { 484 while (slot < data.length && data[slot] == null) { 485 slot++; 486 } 487 } 488 } 489 490 491 private final class Iter implements Iterator<T> { 492 private final int mods; 493 int slot = 0; 494 int removeSlot = -1; 495 496 Iter() { 497 mods = modCount; 498 } 499 500 @Override 501 public boolean hasNext() { 502 align(); 503 return slot < data.length; 504 } 505 506 @Override 507 public T next() { 508 if (!hasNext()) throw new NoSuchElementException(); 509 removeSlot = slot; 510 return data[slot++]; 511 } 512 513 @Override 514 public void remove() { 515 if (removeSlot == -1) throw new IllegalStateException(); 516 517 doRemove(removeSlot); 518 slot = removeSlot; // some entry might have been relocated here 519 removeSlot = -1; 520 } 521 522 private void align() { 523 if (mods != modCount) 524 throw new ConcurrentModificationException(); 525 while (slot < data.length && data[slot] == null) { 526 slot++; 527 } 528 } 529 } 530 531}