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