001 /* 002 * JOSMng - a Java Open Street Map editor, the next generation. 003 * 004 * Copyright (C) 2008 Petr Nejedly <P.Nejedly@sh.cvut.cz> 005 * 006 * This program is free software; you can redistribute it and/or modify 007 * it under the terms of the GNU General Public License as published by 008 * the Free Software Foundation; either version 2 of the License, or 009 * (at your option) any later version. 010 * 011 * This program is distributed in the hope that it will be useful, 012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 014 * GNU General Public License for more details. 015 016 * You should have received a copy of the GNU General Public License along 017 * with this program; if not, write to the Free Software Foundation, Inc., 018 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 019 */ 020 021 package org.openstreetmap.josm.data.osm; 022 023 import java.util.AbstractSet; 024 import java.util.Collection; 025 import java.util.ConcurrentModificationException; 026 import java.util.Iterator; 027 import java.util.Map; 028 import java.util.NoSuchElementException; 029 import java.util.Set; 030 031 /** 032 * A Set-like class that allows looking up equivalent preexising instance. 033 * It is useful whereever one would use self-mapping construct like 034 * <code>Map<T,T>.put(t,t), that is, for caches, uniqueness filters or similar. 035 * 036 * The semantics of equivalency can be external to the object, using the 037 * {@link Hash} interface. The set also supports querying for entries using 038 * different key type, in case you can provide a Hash implementation 039 * that can resolve the equality. 040 * 041 * <h2>Examples</h2> 042 * <ul><li>A String cache: 043 * <pre> 044 * Storage<String> cache = new Storage(); // use default Hash 045 * for (String input : data) { 046 * String onlyOne = cache.putIfUnique(input); 047 * .... 048 * } 049 * </pre></li> 050 * <li>Identity-based set: 051 * <pre> 052 * Storage<Object> identity = new Storage(new Hash<Object,Object> { 053 * public int getHashCode(Object o) { 054 * return System.identityHashCode(o); 055 * } 056 * public boolean equals(Object o1, Object o2) { 057 * return o1 == o2; 058 * } 059 * }); 060 * </pre></li> 061 * <li>An object with int ID and id-based lookup: 062 * <pre> 063 * class Thing { int id; } 064 * Storage<Thing> things = new Storage(new Hash<Thing,Thing>() { 065 * public int getHashCode(Thing t) { 066 * return t.id; 067 * } 068 * public boolean equals(Thing t1, Thing t2) { 069 * return t1 == t2; 070 * } 071 * }); 072 * Map<Integer,Thing> fk = things.foreignKey(new Hash<Integer,Thing>() { 073 * public int getHashCode(Integer i) { 074 * return i.getIntValue(); 075 * } 076 * public boolean equals(Integer k, Thing t) { 077 * return t.id == k.getIntvalue(); 078 * } 079 * } 080 * 081 * things.put(new Thing(3)); 082 * assert things.get(new Thing(3)) == fk.get(3); 083 * </pre></li> 084 * 085 * 086 * @author nenik 087 */ 088 public class Storage<T> extends AbstractSet<T> { 089 private final Hash<? super T,? super T> hash; 090 private T[] data; 091 private int mask; 092 private int size; 093 private transient volatile int modCount = 0; 094 private float loadFactor = 0.6f; 095 private static final int DEFAULT_CAPACITY = 16; 096 private final boolean safeIterator; 097 private boolean arrayCopyNecessary; 098 099 public Storage() { 100 this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, false); 101 } 102 103 public Storage(int capacity) { 104 this(Storage.<T>defaultHash(), capacity, false); 105 } 106 107 public Storage(Hash<? super T,? super T> ha) { 108 this(ha, DEFAULT_CAPACITY, false); 109 } 110 111 public Storage(boolean safeIterator) { 112 this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, safeIterator); 113 } 114 115 public Storage(int capacity, boolean safeIterator) { 116 this(Storage.<T>defaultHash(), capacity, safeIterator); 117 } 118 119 public Storage(Hash<? super T,? super T> ha, boolean safeIterator) { 120 this(ha, DEFAULT_CAPACITY, safeIterator); 121 } 122 123 public Storage(Hash<? super T, ? super T> ha, int capacity) { 124 this(ha, capacity, false); 125 } 126 /** 127 * constructor 128 * @param ha 129 * @param capacity 130 * @param safeIterator If set to false, you must not modify the Storage 131 * while iterating over it. If set to true, you can savely 132 * modify, but the read-only iteration will happen on a copy 133 * of the unmodified Storage. 134 * This is similar to CopyOnWriteArrayList. 135 */ 136 public Storage(Hash<? super T, ? super T> ha, int capacity, boolean safeIterator) { 137 this.hash = ha; 138 int cap = 1 << (int)(Math.ceil(Math.log(capacity/loadFactor) / Math.log(2))); 139 @SuppressWarnings("unchecked") T[] newData = (T[]) new Object[cap]; 140 data = newData; 141 mask = data.length - 1; 142 this.safeIterator = safeIterator; 143 } 144 145 private void copyArray() { 146 if (arrayCopyNecessary) { 147 @SuppressWarnings("unchecked") T[] newData = (T[]) new Object[data.length]; 148 System.arraycopy(data, 0, newData, 0, data.length); 149 data = newData; 150 arrayCopyNecessary = false; 151 } 152 } 153 154 // --------------- Collection implementation ------------------------ 155 @Override 156 public synchronized int size() { 157 return size; 158 } 159 160 @Override 161 public synchronized Iterator<T> iterator() { 162 if (safeIterator) { 163 arrayCopyNecessary = true; 164 return new SafeReadonlyIter(data); 165 } else 166 return new Iter(); 167 168 } 169 170 @Override 171 public synchronized boolean contains(Object o) { 172 @SuppressWarnings("unchecked") T t = (T) o; 173 int bucket = getBucket(hash, t); 174 return bucket >= 0; 175 } 176 177 @Override 178 public synchronized boolean add(T t) { 179 T orig = putUnique(t); 180 return orig == t; 181 } 182 183 @Override 184 public synchronized boolean remove(Object o) { 185 @SuppressWarnings("unchecked") T t = (T) o; 186 T tOrig = removeElem(t); 187 return tOrig != null; 188 } 189 190 @Override 191 public synchronized void clear() { 192 copyArray(); 193 modCount++; 194 size = 0; 195 for (int i = 0; i<data.length; i++) { 196 data[i] = null; 197 } 198 } 199 200 @Override 201 public synchronized int hashCode() { 202 int h = 0; 203 for (T t : this) { 204 h += hash.getHashCode(t); 205 } 206 return h; 207 } 208 209 // ----------------- Extended API ---------------------------- 210 211 public synchronized T put(T t) { 212 copyArray(); 213 modCount++; 214 ensureSpace(); 215 216 int bucket = getBucket(hash, t); 217 if (bucket < 0) { 218 size++; 219 bucket = ~bucket; 220 assert data[bucket] == null; 221 } 222 223 T old = data[bucket]; 224 data[bucket] = t; 225 226 return old; 227 } 228 229 public synchronized T get(T t) { 230 int bucket = getBucket(hash, t); 231 return bucket < 0 ? null : data[bucket]; 232 } 233 234 public synchronized T putUnique(T t) { 235 copyArray(); 236 modCount++; 237 ensureSpace(); 238 239 int bucket = getBucket(hash, t); 240 if (bucket < 0) { // unique 241 size++; 242 assert data[~bucket] == null; 243 data[~bucket] = t; 244 return t; 245 } 246 247 return data[bucket]; 248 } 249 250 public synchronized T removeElem(T t) { 251 copyArray(); 252 modCount++; 253 int bucket = getBucket(hash, t); 254 return bucket < 0 ? null : doRemove(bucket); 255 } 256 257 public <K> Map<K,T> foreignKey(Hash<K,? super T> h) { 258 return new FMap<K>(h); 259 } 260 261 // ---------------- Implementation 262 263 /** 264 * Additional mixing of hash 265 */ 266 private int rehash(int h) { 267 //return 54435761*h; 268 return 1103515245*h >> 2; 269 } 270 271 /** 272 * Finds a bucket for given key. 273 * 274 * @param key The key to compare 275 * @return the bucket equivalent to the key or -(bucket) as an empty slot 276 * where such an entry can be stored. 277 */ 278 private <K> int getBucket(Hash<K,? super T> ha, K key) { 279 T entry; 280 int hcode = rehash(ha.getHashCode(key)); 281 int bucket = hcode & mask; 282 while ((entry = data[bucket]) != null) { 283 if (ha.equals(key, entry)) 284 return bucket; 285 bucket = (bucket+1) & mask; 286 } 287 return ~bucket; 288 } 289 290 private T doRemove(int slot) { 291 T t = data[slot]; 292 assert t != null; 293 294 fillTheHole(slot); // fill the hole (or null it) 295 size--; 296 return t; 297 } 298 299 private void fillTheHole(int hole) { 300 int bucket = (hole+1) & mask; 301 T entry; 302 303 while ((entry = data[bucket]) != null) { 304 int right = rehash(hash.getHashCode(entry)) & mask; 305 // if the entry should be in <hole+1,bucket-1> (circular-wise) 306 // we can't move it. The move can be proved safe otherwise, 307 // because the entry safely belongs to <previous_null+1,hole> 308 if ((bucket < right && (right <= hole || hole <= bucket)) || 309 (right <=hole && hole <= bucket)) { 310 311 data[hole] = data[bucket]; 312 hole = bucket; 313 } 314 bucket = (bucket+1) & mask; 315 } 316 317 // no entry belongs here, just null out the slot 318 data[hole] = null; 319 } 320 321 private void ensureSpace() { 322 if (size > data.length*loadFactor) { // rehash 323 @SuppressWarnings("unchecked") T[] big = (T[]) new Object[data.length * 2]; 324 int nMask = big.length - 1; 325 326 for (T o : data) { 327 if (o == null) { 328 continue; 329 } 330 int bucket = rehash(hash.getHashCode(o)) & nMask; 331 while (big[bucket] != null) { 332 bucket = (bucket+1) & nMask; 333 } 334 big[bucket] = o; 335 } 336 337 data = big; 338 mask = nMask; 339 } 340 } 341 342 // -------------- factories -------------------- 343 /** 344 * A factory for default hash implementation. 345 * @return a hash implementation that just delegates to object's own 346 * hashCode and equals. 347 */ 348 public static <O> Hash<O,O> defaultHash() { 349 return new Hash<O,O>() { 350 public int getHashCode(O t) { 351 return t.hashCode(); 352 } 353 public boolean equals(O t1, O t2) { 354 return t1.equals(t2); 355 } 356 }; 357 } 358 /* 359 public static <O> Hash<O,O> identityHash() { 360 return new Hash<O,O>() { 361 public int getHashCode(O t) { 362 return System.identityHashCode(t); 363 } 364 public boolean equals(O t1, O t2) { 365 return t1 == t2; 366 } 367 }; 368 } 369 */ 370 371 private class FMap<K> implements Map<K,T> { 372 Hash<K,? super T> fHash; 373 374 private FMap(Hash<K,? super T> h) { 375 fHash = h; 376 } 377 378 public int size() { 379 return Storage.this.size(); 380 } 381 382 public boolean isEmpty() { 383 return Storage.this.isEmpty(); 384 } 385 386 public boolean containsKey(Object o) { 387 @SuppressWarnings("unchecked") K key = (K) o; 388 int bucket = getBucket(fHash, key); 389 return bucket >= 0; 390 } 391 392 public boolean containsValue(Object value) { 393 return Storage.this.contains(value); 394 } 395 396 public T get(Object o) { 397 @SuppressWarnings("unchecked") K key = (K) o; 398 int bucket = getBucket(fHash, key); 399 return bucket < 0 ? null : data[bucket]; 400 } 401 402 public T put(K key, T value) { 403 if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key"); 404 return Storage.this.put(value); 405 } 406 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 public void putAll(Map<? extends K, ? extends T> m) { 416 if (m instanceof Storage.FMap) { 417 Storage.this.addAll(((Storage.FMap)m).values()); 418 } else { 419 for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) { 420 put(e.getKey(), e.getValue()); 421 } 422 } 423 } 424 425 public void clear() { 426 Storage.this.clear(); 427 } 428 429 public Set<K> keySet() { 430 throw new UnsupportedOperationException(); 431 } 432 433 public Collection<T> values() { 434 return Storage.this; 435 } 436 437 public Set<Entry<K, T>> entrySet() { 438 throw new UnsupportedOperationException(); 439 } 440 } 441 442 private final class SafeReadonlyIter implements Iterator<T> { 443 final T[] data; 444 int slot = 0; 445 446 SafeReadonlyIter(T[] data) { 447 this.data = data; 448 } 449 450 public boolean hasNext() { 451 align(); 452 return slot < data.length; 453 } 454 455 public T next() { 456 if (!hasNext()) throw new NoSuchElementException(); 457 return data[slot++]; 458 } 459 460 public void remove() { 461 throw new UnsupportedOperationException(); 462 } 463 464 private void align() { 465 while (slot < data.length && data[slot] == null) { 466 slot++; 467 } 468 } 469 } 470 471 472 private final class Iter implements Iterator<T> { 473 private final int mods; 474 int slot = 0; 475 int removeSlot = -1; 476 477 Iter() { 478 mods = modCount; 479 } 480 481 public boolean hasNext() { 482 align(); 483 return slot < data.length; 484 } 485 486 public T next() { 487 if (!hasNext()) throw new NoSuchElementException(); 488 removeSlot = slot; 489 return data[slot++]; 490 } 491 492 public void remove() { 493 if (removeSlot == -1) throw new IllegalStateException(); 494 495 doRemove(removeSlot); 496 slot = removeSlot; // some entry might have been relocated here 497 removeSlot = -1; 498 } 499 500 private void align() { 501 if (mods != modCount) 502 throw new ConcurrentModificationException(); 503 while (slot < data.length && data[slot] == null) { 504 slot++; 505 } 506 } 507 } 508 509 }