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