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