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 static final double LOAD_FACTOR = 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/LOAD_FACTOR) / Math.log(2))); 146 @SuppressWarnings("unchecked") 147 T[] newData = (T[]) new Object[cap]; 148 data = newData; 149 mask = data.length - 1; 150 this.safeIterator = safeIterator; 151 } 152 153 private void copyArray() { 154 if (arrayCopyNecessary) { 155 data = Utils.copyArray(data); 156 arrayCopyNecessary = false; 157 } 158 } 159 160 // --------------- Collection implementation ------------------------ 161 @Override 162 public synchronized int size() { 163 return size; 164 } 165 166 @Override 167 public synchronized Iterator<T> iterator() { 168 if (safeIterator) { 169 arrayCopyNecessary = true; 170 return new SafeReadonlyIter(data); 171 } else 172 return new Iter(); 173 174 } 175 176 @Override 177 public synchronized boolean contains(Object o) { 178 @SuppressWarnings("unchecked") 179 T t = (T) o; 180 int bucket = getBucket(hash, t); 181 return bucket >= 0; 182 } 183 184 @Override 185 public synchronized boolean add(T t) { 186 T orig = putUnique(t); 187 return orig == t; 188 } 189 190 @Override 191 public synchronized boolean remove(Object o) { 192 @SuppressWarnings("unchecked") 193 T t = (T) o; 194 T tOrig = removeElem(t); 195 return tOrig != null; 196 } 197 198 @Override 199 public synchronized void clear() { 200 copyArray(); 201 modCount++; 202 size = 0; 203 for (int i = 0; i < data.length; i++) { 204 data[i] = null; 205 } 206 } 207 208 @Override 209 public synchronized int hashCode() { 210 int h = 0; 211 for (T t : this) { 212 h += hash.getHashCode(t); 213 } 214 return h; 215 } 216 217 // ----------------- Extended API ---------------------------- 218 219 public synchronized T put(T t) { 220 copyArray(); 221 modCount++; 222 ensureSpace(); 223 224 int bucket = getBucket(hash, t); 225 if (bucket < 0) { 226 size++; 227 bucket = ~bucket; 228 assert data[bucket] == null; 229 } 230 231 T old = data[bucket]; 232 data[bucket] = t; 233 234 return old; 235 } 236 237 public synchronized T get(T t) { 238 int bucket = getBucket(hash, t); 239 return bucket < 0 ? null : data[bucket]; 240 } 241 242 public synchronized T putUnique(T t) { 243 copyArray(); 244 modCount++; 245 ensureSpace(); 246 247 int bucket = getBucket(hash, t); 248 if (bucket < 0) { // unique 249 size++; 250 assert data[~bucket] == null; 251 data[~bucket] = t; 252 return t; 253 } 254 255 return data[bucket]; 256 } 257 258 public synchronized T removeElem(T t) { 259 copyArray(); 260 modCount++; 261 int bucket = getBucket(hash, t); 262 return bucket < 0 ? null : doRemove(bucket); 263 } 264 265 public <K> Map<K, T> foreignKey(Hash<K, ? super T> h) { 266 return new FMap<>(h); 267 } 268 269 // ---------------- Implementation 270 271 /** 272 * Additional mixing of hash 273 * @param h hash 274 * @return new hash 275 */ 276 private static int rehash(int h) { 277 return 1103515245*h >> 2; 278 } 279 280 /** 281 * Finds a bucket for given key. 282 * @param <K> type for hashCode and first equals parameter 283 * @param ha hash function 284 * 285 * @param key The key to compare 286 * @return the bucket equivalent to the key or -(bucket) as an empty slot 287 * where such an entry can be stored. 288 */ 289 private <K> int getBucket(Hash<K, ? super T> ha, K key) { 290 T entry; 291 int hcode = rehash(ha.getHashCode(key)); 292 int bucket = hcode & mask; 293 while ((entry = data[bucket]) != null) { 294 if (ha.equals(key, entry)) 295 return bucket; 296 bucket = (bucket+1) & mask; 297 } 298 return ~bucket; 299 } 300 301 private T doRemove(int slot) { 302 T t = data[slot]; 303 assert t != null; 304 305 fillTheHole(slot); // fill the hole (or null it) 306 size--; 307 return t; 308 } 309 310 private void fillTheHole(int hole) { 311 int bucket = (hole+1) & mask; 312 T entry; 313 314 while ((entry = data[bucket]) != null) { 315 int right = rehash(hash.getHashCode(entry)) & mask; 316 // if the entry should be in <hole+1,bucket-1> (circular-wise) 317 // we can't move it. The move can be proved safe otherwise, 318 // because the entry safely belongs to <previous_null+1,hole> 319 if ((bucket < right && (right <= hole || hole <= bucket)) || 320 (right <= hole && hole <= bucket)) { 321 322 data[hole] = data[bucket]; 323 hole = bucket; 324 } 325 bucket = (bucket+1) & mask; 326 } 327 328 // no entry belongs here, just null out the slot 329 data[hole] = null; 330 } 331 332 private void ensureSpace() { 333 if (size > data.length*LOAD_FACTOR) { // rehash 334 @SuppressWarnings("unchecked") 335 T[] big = (T[]) new Object[data.length * 2]; 336 int nMask = big.length - 1; 337 338 for (T o : data) { 339 if (o == null) { 340 continue; 341 } 342 int bucket = rehash(hash.getHashCode(o)) & nMask; 343 while (big[bucket] != null) { 344 bucket = (bucket+1) & nMask; 345 } 346 big[bucket] = o; 347 } 348 349 data = big; 350 mask = nMask; 351 } 352 } 353 354 // -------------- factories -------------------- 355 /** 356 * A factory for default hash implementation. 357 * @param <O> type for hash 358 * @return a hash implementation that just delegates to object's own hashCode and equals. 359 */ 360 public static <O> Hash<O, O> defaultHash() { 361 return new Hash<O, O>() { 362 @Override 363 public int getHashCode(O t) { 364 return t.hashCode(); 365 } 366 367 @Override 368 public boolean equals(O t1, O t2) { 369 return t1.equals(t2); 370 } 371 }; 372 } 373 374 private final class FMap<K> implements Map<K, T> { 375 private final 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") 394 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") 407 K key = (K) o; 408 int bucket = getBucket(fHash, key); 409 return bucket < 0 ? null : data[bucket]; 410 } 411 412 @Override 413 public T put(K key, T value) { 414 if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key"); 415 return Storage.this.put(value); 416 } 417 418 @Override 419 public T remove(Object o) { 420 synchronized (Storage.this) { 421 modCount++; 422 @SuppressWarnings("unchecked") 423 K key = (K) o; 424 int bucket = getBucket(fHash, key); 425 426 return bucket < 0 ? null : doRemove(bucket); 427 } 428 } 429 430 @Override 431 public void putAll(Map<? extends K, ? extends T> m) { 432 if (m instanceof Storage.FMap) { 433 Storage.this.addAll(m.values()); 434 } else { 435 for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) { 436 put(e.getKey(), e.getValue()); 437 } 438 } 439 } 440 441 @Override 442 public void clear() { 443 Storage.this.clear(); 444 } 445 446 @Override 447 public Set<K> keySet() { 448 throw new UnsupportedOperationException(); 449 } 450 451 @Override 452 public Collection<T> values() { 453 return Storage.this; 454 } 455 456 @Override 457 public Set<Entry<K, T>> entrySet() { 458 throw new UnsupportedOperationException(); 459 } 460 } 461 462 private final class SafeReadonlyIter implements Iterator<T> { 463 private final T[] data; 464 private int slot; 465 466 SafeReadonlyIter(T[] data) { 467 this.data = data; 468 } 469 470 @Override 471 public boolean hasNext() { 472 align(); 473 return slot < data.length; 474 } 475 476 @Override 477 public T next() { 478 if (!hasNext()) throw new NoSuchElementException(); 479 return data[slot++]; 480 } 481 482 @Override 483 public void remove() { 484 throw new UnsupportedOperationException(); 485 } 486 487 private void align() { 488 while (slot < data.length && data[slot] == null) { 489 slot++; 490 } 491 } 492 } 493 494 private final class Iter implements Iterator<T> { 495 private final int mods; 496 private int slot; 497 private int removeSlot = -1; 498 499 Iter() { 500 mods = modCount; 501 } 502 503 @Override 504 public boolean hasNext() { 505 align(); 506 return slot < data.length; 507 } 508 509 @Override 510 public T next() { 511 if (!hasNext()) throw new NoSuchElementException(); 512 removeSlot = slot; 513 return data[slot++]; 514 } 515 516 @Override 517 public void remove() { 518 if (removeSlot == -1) throw new IllegalStateException(); 519 520 doRemove(removeSlot); 521 slot = removeSlot; // some entry might have been relocated here 522 removeSlot = -1; 523 } 524 525 private void align() { 526 if (mods != modCount) 527 throw new ConcurrentModificationException(); 528 while (slot < data.length && data[slot] == null) { 529 slot++; 530 } 531 } 532 } 533 534}