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