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