[6380] | 1 | // License: GPL. For details, see LICENSE file.
|
---|
[2399] | 2 | package org.openstreetmap.josm.data.osm;
|
---|
| 3 |
|
---|
| 4 | import java.util.AbstractSet;
|
---|
[11392] | 5 | import java.util.Arrays;
|
---|
[2399] | 6 | import java.util.Collection;
|
---|
[3207] | 7 | import java.util.ConcurrentModificationException;
|
---|
[2399] | 8 | import java.util.Iterator;
|
---|
| 9 | import java.util.Map;
|
---|
| 10 | import java.util.NoSuchElementException;
|
---|
| 11 | import java.util.Set;
|
---|
| 12 |
|
---|
[7436] | 13 | import org.openstreetmap.josm.tools.Utils;
|
---|
| 14 |
|
---|
[2399] | 15 | /**
|
---|
| 16 | * A Set-like class that allows looking up equivalent preexising instance.
|
---|
| 17 | * It is useful whereever one would use self-mapping construct like
|
---|
[6830] | 18 | * <code>Map<T,T>.put(t,t)</code>, that is, for caches, uniqueness filters or similar.
|
---|
[2399] | 19 | *
|
---|
| 20 | * The semantics of equivalency can be external to the object, using the
|
---|
| 21 | * {@link Hash} interface. The set also supports querying for entries using
|
---|
| 22 | * different key type, in case you can provide a Hash implementation
|
---|
| 23 | * that can resolve the equality.
|
---|
| 24 | *
|
---|
| 25 | * <h2>Examples</h2>
|
---|
| 26 | * <ul><li>A String cache:
|
---|
| 27 | * <pre>
|
---|
[6830] | 28 | * Storage<String> cache = new Storage(); // use default Hash
|
---|
[2399] | 29 | * for (String input : data) {
|
---|
| 30 | * String onlyOne = cache.putIfUnique(input);
|
---|
| 31 | * ....
|
---|
| 32 | * }
|
---|
| 33 | * </pre></li>
|
---|
| 34 | * <li>Identity-based set:
|
---|
| 35 | * <pre>
|
---|
[6830] | 36 | * Storage<Object> identity = new Storage(new Hash<Object,Object> {
|
---|
[2399] | 37 | * public int getHashCode(Object o) {
|
---|
| 38 | * return System.identityHashCode(o);
|
---|
| 39 | * }
|
---|
| 40 | * public boolean equals(Object o1, Object o2) {
|
---|
| 41 | * return o1 == o2;
|
---|
| 42 | * }
|
---|
| 43 | * });
|
---|
| 44 | * </pre></li>
|
---|
| 45 | * <li>An object with int ID and id-based lookup:
|
---|
| 46 | * <pre>
|
---|
| 47 | * class Thing { int id; }
|
---|
[6830] | 48 | * Storage<Thing> things = new Storage(new Hash<Thing,Thing>() {
|
---|
[2399] | 49 | * public int getHashCode(Thing t) {
|
---|
| 50 | * return t.id;
|
---|
| 51 | * }
|
---|
| 52 | * public boolean equals(Thing t1, Thing t2) {
|
---|
| 53 | * return t1 == t2;
|
---|
| 54 | * }
|
---|
| 55 | * });
|
---|
[6830] | 56 | * Map<Integer,Thing> fk = things.foreignKey(new Hash<Integer,Thing>() {
|
---|
[2399] | 57 | * public int getHashCode(Integer i) {
|
---|
| 58 | * return i.getIntValue();
|
---|
| 59 | * }
|
---|
| 60 | * public boolean equals(Integer k, Thing t) {
|
---|
| 61 | * return t.id == k.getIntvalue();
|
---|
| 62 | * }
|
---|
| 63 | * }
|
---|
| 64 | *
|
---|
| 65 | * things.put(new Thing(3));
|
---|
| 66 | * assert things.get(new Thing(3)) == fk.get(3);
|
---|
| 67 | * </pre></li>
|
---|
[6830] | 68 | * </ul>
|
---|
[2399] | 69 | *
|
---|
| 70 | * @author nenik
|
---|
[9243] | 71 | * @param <T> type of stored objects
|
---|
[2399] | 72 | */
|
---|
| 73 | public class Storage<T> extends AbstractSet<T> {
|
---|
[5674] | 74 |
|
---|
[11342] | 75 | /**
|
---|
| 76 | * Hash for {@link PrimitiveId}.
|
---|
| 77 | */
|
---|
[5674] | 78 | public static class PrimitiveIdHash implements Hash<PrimitiveId, PrimitiveId> {
|
---|
| 79 |
|
---|
[6084] | 80 | @Override
|
---|
[5674] | 81 | public int getHashCode(PrimitiveId k) {
|
---|
[8510] | 82 | return (int) k.getUniqueId() ^ k.getType().hashCode();
|
---|
[5674] | 83 | }
|
---|
| 84 |
|
---|
[6084] | 85 | @Override
|
---|
[5674] | 86 | public boolean equals(PrimitiveId key, PrimitiveId value) {
|
---|
| 87 | if (key == null || value == null) return false;
|
---|
| 88 | return key.getUniqueId() == value.getUniqueId() && key.getType() == value.getType();
|
---|
| 89 | }
|
---|
| 90 | }
|
---|
| 91 |
|
---|
[8510] | 92 | private final Hash<? super T, ? super T> hash;
|
---|
[3398] | 93 | private T[] data;
|
---|
[2399] | 94 | private int mask;
|
---|
| 95 | private int size;
|
---|
[8840] | 96 | private volatile int modCount;
|
---|
[9975] | 97 | private static final double LOAD_FACTOR = 0.6d;
|
---|
[3503] | 98 | private static final int DEFAULT_CAPACITY = 16;
|
---|
[3207] | 99 | private final boolean safeIterator;
|
---|
| 100 | private boolean arrayCopyNecessary;
|
---|
[2399] | 101 |
|
---|
[6137] | 102 | /**
|
---|
| 103 | * Constructs a new {@code Storage} with default capacity (16).
|
---|
| 104 | */
|
---|
[2399] | 105 | public Storage() {
|
---|
[3503] | 106 | this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, false);
|
---|
[2399] | 107 | }
|
---|
| 108 |
|
---|
[6137] | 109 | /**
|
---|
| 110 | * Constructs a new {@code Storage} with given capacity.
|
---|
[9243] | 111 | * @param capacity capacity
|
---|
[6137] | 112 | */
|
---|
[2399] | 113 | public Storage(int capacity) {
|
---|
[3207] | 114 | this(Storage.<T>defaultHash(), capacity, false);
|
---|
[2399] | 115 | }
|
---|
| 116 |
|
---|
[11342] | 117 | /**
|
---|
| 118 | * Constructs a new {@code Storage} with given hash.
|
---|
| 119 | * @param ha hash
|
---|
| 120 | */
|
---|
[8510] | 121 | public Storage(Hash<? super T, ? super T> ha) {
|
---|
[3503] | 122 | this(ha, DEFAULT_CAPACITY, false);
|
---|
[2399] | 123 | }
|
---|
| 124 |
|
---|
[11342] | 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 | */
|
---|
[3503] | 131 | public Storage(boolean safeIterator) {
|
---|
| 132 | this(Storage.<T>defaultHash(), DEFAULT_CAPACITY, safeIterator);
|
---|
| 133 | }
|
---|
| 134 |
|
---|
[11342] | 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 | */
|
---|
[3503] | 142 | public Storage(int capacity, boolean safeIterator) {
|
---|
| 143 | this(Storage.<T>defaultHash(), capacity, safeIterator);
|
---|
| 144 | }
|
---|
| 145 |
|
---|
[11342] | 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 | */
|
---|
[8510] | 153 | public Storage(Hash<? super T, ? super T> ha, boolean safeIterator) {
|
---|
[3503] | 154 | this(ha, DEFAULT_CAPACITY, safeIterator);
|
---|
| 155 | }
|
---|
| 156 |
|
---|
[11342] | 157 | /**
|
---|
| 158 | * Constructs a new {@code Storage} with given hash and capacity.
|
---|
| 159 | * @param ha hash
|
---|
| 160 | * @param capacity capacity
|
---|
| 161 | */
|
---|
[3503] | 162 | public Storage(Hash<? super T, ? super T> ha, int capacity) {
|
---|
| 163 | this(ha, capacity, false);
|
---|
| 164 | }
|
---|
[9059] | 165 |
|
---|
[3503] | 166 | /**
|
---|
[11342] | 167 | * Constructs a new {@code Storage} with given hash and capacity.
|
---|
[8470] | 168 | * @param ha hash
|
---|
| 169 | * @param capacity capacity
|
---|
[11342] | 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.
|
---|
[3503] | 173 | */
|
---|
[3207] | 174 | public Storage(Hash<? super T, ? super T> ha, int capacity, boolean safeIterator) {
|
---|
[2399] | 175 | this.hash = ha;
|
---|
[9975] | 176 | int cap = 1 << (int) (Math.ceil(Math.log(capacity/LOAD_FACTOR) / Math.log(2)));
|
---|
[9980] | 177 | @SuppressWarnings("unchecked")
|
---|
| 178 | T[] newData = (T[]) new Object[cap];
|
---|
[3453] | 179 | data = newData;
|
---|
[2399] | 180 | mask = data.length - 1;
|
---|
[3207] | 181 | this.safeIterator = safeIterator;
|
---|
[2399] | 182 | }
|
---|
| 183 |
|
---|
[3207] | 184 | private void copyArray() {
|
---|
| 185 | if (arrayCopyNecessary) {
|
---|
[7436] | 186 | data = Utils.copyArray(data);
|
---|
[3207] | 187 | arrayCopyNecessary = false;
|
---|
| 188 | }
|
---|
| 189 | }
|
---|
| 190 |
|
---|
[2399] | 191 | // --------------- Collection implementation ------------------------
|
---|
[3158] | 192 | @Override
|
---|
[3207] | 193 | public synchronized int size() {
|
---|
[2399] | 194 | return size;
|
---|
| 195 | }
|
---|
| 196 |
|
---|
[3158] | 197 | @Override
|
---|
[3207] | 198 | public synchronized Iterator<T> iterator() {
|
---|
| 199 | if (safeIterator) {
|
---|
| 200 | arrayCopyNecessary = true;
|
---|
| 201 | return new SafeReadonlyIter(data);
|
---|
| 202 | } else
|
---|
| 203 | return new Iter();
|
---|
| 204 |
|
---|
[2399] | 205 | }
|
---|
| 206 |
|
---|
[3398] | 207 | @Override
|
---|
| 208 | public synchronized boolean contains(Object o) {
|
---|
[9980] | 209 | @SuppressWarnings("unchecked")
|
---|
| 210 | T t = (T) o;
|
---|
[3453] | 211 | int bucket = getBucket(hash, t);
|
---|
[2399] | 212 | return bucket >= 0;
|
---|
| 213 | }
|
---|
| 214 |
|
---|
[3530] | 215 | @Override
|
---|
[3398] | 216 | public synchronized boolean add(T t) {
|
---|
[2399] | 217 | T orig = putUnique(t);
|
---|
[3158] | 218 | return orig == t;
|
---|
[2399] | 219 | }
|
---|
| 220 |
|
---|
[3398] | 221 | @Override
|
---|
| 222 | public synchronized boolean remove(Object o) {
|
---|
[9980] | 223 | @SuppressWarnings("unchecked")
|
---|
| 224 | T t = (T) o;
|
---|
[3453] | 225 | T tOrig = removeElem(t);
|
---|
| 226 | return tOrig != null;
|
---|
[2399] | 227 | }
|
---|
[3530] | 228 |
|
---|
[3398] | 229 | @Override
|
---|
| 230 | public synchronized void clear() {
|
---|
[3207] | 231 | copyArray();
|
---|
[2399] | 232 | modCount++;
|
---|
| 233 | size = 0;
|
---|
[8510] | 234 | for (int i = 0; i < data.length; i++) {
|
---|
[3158] | 235 | data[i] = null;
|
---|
| 236 | }
|
---|
[2399] | 237 | }
|
---|
| 238 |
|
---|
[3398] | 239 | @Override
|
---|
| 240 | public synchronized int hashCode() {
|
---|
[2512] | 241 | int h = 0;
|
---|
[11392] | 242 | if (hash != null) {
|
---|
| 243 | for (T t : this) {
|
---|
| 244 | h += hash.getHashCode(t);
|
---|
| 245 | }
|
---|
[3158] | 246 | }
|
---|
[2512] | 247 | return h;
|
---|
[2399] | 248 | }
|
---|
| 249 |
|
---|
[11392] | 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 |
|
---|
[2399] | 261 | // ----------------- Extended API ----------------------------
|
---|
| 262 |
|
---|
[3207] | 263 | public synchronized T put(T t) {
|
---|
| 264 | copyArray();
|
---|
[2399] | 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 |
|
---|
[3398] | 275 | T old = data[bucket];
|
---|
[2399] | 276 | data[bucket] = t;
|
---|
| 277 |
|
---|
| 278 | return old;
|
---|
| 279 | }
|
---|
| 280 |
|
---|
[3207] | 281 | public synchronized T get(T t) {
|
---|
[2399] | 282 | int bucket = getBucket(hash, t);
|
---|
[3398] | 283 | return bucket < 0 ? null : data[bucket];
|
---|
[2399] | 284 | }
|
---|
| 285 |
|
---|
[3207] | 286 | public synchronized T putUnique(T t) {
|
---|
| 287 | copyArray();
|
---|
[2399] | 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 |
|
---|
[3398] | 299 | return data[bucket];
|
---|
[2399] | 300 | }
|
---|
| 301 |
|
---|
[3207] | 302 | public synchronized T removeElem(T t) {
|
---|
| 303 | copyArray();
|
---|
[2399] | 304 | modCount++;
|
---|
| 305 | int bucket = getBucket(hash, t);
|
---|
| 306 | return bucket < 0 ? null : doRemove(bucket);
|
---|
| 307 | }
|
---|
| 308 |
|
---|
[8510] | 309 | public <K> Map<K, T> foreignKey(Hash<K, ? super T> h) {
|
---|
[7005] | 310 | return new FMap<>(h);
|
---|
[2399] | 311 | }
|
---|
| 312 |
|
---|
| 313 | // ---------------- Implementation
|
---|
| 314 |
|
---|
| 315 | /**
|
---|
| 316 | * Additional mixing of hash
|
---|
[9243] | 317 | * @param h hash
|
---|
| 318 | * @return new hash
|
---|
[2399] | 319 | */
|
---|
[8870] | 320 | private static int rehash(int h) {
|
---|
[11100] | 321 | return (1_103_515_245*h) >> 2;
|
---|
[2399] | 322 | }
|
---|
| 323 |
|
---|
| 324 | /**
|
---|
| 325 | * Finds a bucket for given key.
|
---|
[9246] | 326 | * @param <K> type for hashCode and first equals parameter
|
---|
[9243] | 327 | * @param ha hash function
|
---|
[2399] | 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 | */
|
---|
[8510] | 333 | private <K> int getBucket(Hash<K, ? super T> ha, K key) {
|
---|
[2399] | 334 | T entry;
|
---|
| 335 | int hcode = rehash(ha.getHashCode(key));
|
---|
| 336 | int bucket = hcode & mask;
|
---|
[11392] | 337 | while (bucket < data.length && (entry = data[bucket]) != null) {
|
---|
[3158] | 338 | if (ha.equals(key, entry))
|
---|
[2399] | 339 | return bucket;
|
---|
| 340 | bucket = (bucket+1) & mask;
|
---|
| 341 | }
|
---|
| 342 | return ~bucket;
|
---|
| 343 | }
|
---|
| 344 |
|
---|
| 345 | private T doRemove(int slot) {
|
---|
[3398] | 346 | T t = data[slot];
|
---|
[2399] | 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 |
|
---|
[3398] | 358 | while ((entry = data[bucket]) != null) {
|
---|
[2399] | 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)) ||
|
---|
[8510] | 364 | (right <= hole && hole <= bucket)) {
|
---|
[2399] | 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() {
|
---|
[9975] | 377 | if (size > data.length*LOAD_FACTOR) { // rehash
|
---|
[9980] | 378 | @SuppressWarnings("unchecked")
|
---|
| 379 | T[] big = (T[]) new Object[data.length * 2];
|
---|
[2399] | 380 | int nMask = big.length - 1;
|
---|
| 381 |
|
---|
[3398] | 382 | for (T o : data) {
|
---|
[3158] | 383 | if (o == null) {
|
---|
| 384 | continue;
|
---|
| 385 | }
|
---|
[3398] | 386 | int bucket = rehash(hash.getHashCode(o)) & nMask;
|
---|
[3158] | 387 | while (big[bucket] != null) {
|
---|
| 388 | bucket = (bucket+1) & nMask;
|
---|
| 389 | }
|
---|
[2399] | 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.
|
---|
[9246] | 401 | * @param <O> type for hash
|
---|
| 402 | * @return a hash implementation that just delegates to object's own hashCode and equals.
|
---|
[2399] | 403 | */
|
---|
[8510] | 404 | public static <O> Hash<O, O> defaultHash() {
|
---|
| 405 | return new Hash<O, O>() {
|
---|
[6084] | 406 | @Override
|
---|
[2399] | 407 | public int getHashCode(O t) {
|
---|
| 408 | return t.hashCode();
|
---|
| 409 | }
|
---|
[8510] | 410 |
|
---|
[6084] | 411 | @Override
|
---|
[2399] | 412 | public boolean equals(O t1, O t2) {
|
---|
| 413 | return t1.equals(t2);
|
---|
| 414 | }
|
---|
| 415 | };
|
---|
| 416 | }
|
---|
| 417 |
|
---|
[8510] | 418 | private final class FMap<K> implements Map<K, T> {
|
---|
[9067] | 419 | private final Hash<K, ? super T> fHash;
|
---|
[2399] | 420 |
|
---|
[8510] | 421 | private FMap(Hash<K, ? super T> h) {
|
---|
[2399] | 422 | fHash = h;
|
---|
| 423 | }
|
---|
| 424 |
|
---|
[6084] | 425 | @Override
|
---|
[2399] | 426 | public int size() {
|
---|
| 427 | return Storage.this.size();
|
---|
| 428 | }
|
---|
| 429 |
|
---|
[6084] | 430 | @Override
|
---|
[2399] | 431 | public boolean isEmpty() {
|
---|
| 432 | return Storage.this.isEmpty();
|
---|
| 433 | }
|
---|
| 434 |
|
---|
[6084] | 435 | @Override
|
---|
[3453] | 436 | public boolean containsKey(Object o) {
|
---|
[9980] | 437 | @SuppressWarnings("unchecked")
|
---|
| 438 | K key = (K) o;
|
---|
[3453] | 439 | int bucket = getBucket(fHash, key);
|
---|
[2399] | 440 | return bucket >= 0;
|
---|
| 441 | }
|
---|
| 442 |
|
---|
[6084] | 443 | @Override
|
---|
[2399] | 444 | public boolean containsValue(Object value) {
|
---|
| 445 | return Storage.this.contains(value);
|
---|
| 446 | }
|
---|
| 447 |
|
---|
[6084] | 448 | @Override
|
---|
[3453] | 449 | public T get(Object o) {
|
---|
[9980] | 450 | @SuppressWarnings("unchecked")
|
---|
| 451 | K key = (K) o;
|
---|
[3453] | 452 | int bucket = getBucket(fHash, key);
|
---|
[3398] | 453 | return bucket < 0 ? null : data[bucket];
|
---|
[2399] | 454 | }
|
---|
| 455 |
|
---|
[6084] | 456 | @Override
|
---|
[2399] | 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 |
|
---|
[6084] | 462 | @Override
|
---|
[3453] | 463 | public T remove(Object o) {
|
---|
[9703] | 464 | synchronized (Storage.this) {
|
---|
| 465 | modCount++;
|
---|
[9980] | 466 | @SuppressWarnings("unchecked")
|
---|
| 467 | K key = (K) o;
|
---|
[9703] | 468 | int bucket = getBucket(fHash, key);
|
---|
[2399] | 469 |
|
---|
[9703] | 470 | return bucket < 0 ? null : doRemove(bucket);
|
---|
| 471 | }
|
---|
[2399] | 472 | }
|
---|
| 473 |
|
---|
[6084] | 474 | @Override
|
---|
[2399] | 475 | public void putAll(Map<? extends K, ? extends T> m) {
|
---|
| 476 | if (m instanceof Storage.FMap) {
|
---|
[6137] | 477 | Storage.this.addAll(m.values());
|
---|
[2399] | 478 | } else {
|
---|
[3158] | 479 | for (Map.Entry<? extends K, ? extends T> e : m.entrySet()) {
|
---|
[2399] | 480 | put(e.getKey(), e.getValue());
|
---|
[3158] | 481 | }
|
---|
[2399] | 482 | }
|
---|
| 483 | }
|
---|
| 484 |
|
---|
[6084] | 485 | @Override
|
---|
[2399] | 486 | public void clear() {
|
---|
| 487 | Storage.this.clear();
|
---|
| 488 | }
|
---|
| 489 |
|
---|
[6084] | 490 | @Override
|
---|
[2399] | 491 | public Set<K> keySet() {
|
---|
| 492 | throw new UnsupportedOperationException();
|
---|
| 493 | }
|
---|
| 494 |
|
---|
[6084] | 495 | @Override
|
---|
[2399] | 496 | public Collection<T> values() {
|
---|
| 497 | return Storage.this;
|
---|
| 498 | }
|
---|
| 499 |
|
---|
[6084] | 500 | @Override
|
---|
[2399] | 501 | public Set<Entry<K, T>> entrySet() {
|
---|
| 502 | throw new UnsupportedOperationException();
|
---|
| 503 | }
|
---|
| 504 | }
|
---|
| 505 |
|
---|
[11395] | 506 | private abstract class AbstractIter implements Iterator<T> {
|
---|
| 507 | protected int slot;
|
---|
[3207] | 508 |
|
---|
[11408] | 509 | protected final boolean doHasNext(T[] data) {
|
---|
[11392] | 510 | if (data == null) return false;
|
---|
[11408] | 511 | align(data);
|
---|
[3207] | 512 | return slot < data.length;
|
---|
| 513 | }
|
---|
| 514 |
|
---|
[11408] | 515 | protected void align(T[] data) {
|
---|
[11395] | 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 |
|
---|
[6084] | 529 | @Override
|
---|
[11408] | 530 | public boolean hasNext() {
|
---|
| 531 | return doHasNext(data);
|
---|
| 532 | }
|
---|
| 533 |
|
---|
| 534 | @Override
|
---|
[3207] | 535 | public T next() {
|
---|
| 536 | if (!hasNext()) throw new NoSuchElementException();
|
---|
[3398] | 537 | return data[slot++];
|
---|
[3207] | 538 | }
|
---|
| 539 |
|
---|
[6084] | 540 | @Override
|
---|
[3207] | 541 | public void remove() {
|
---|
| 542 | throw new UnsupportedOperationException();
|
---|
| 543 | }
|
---|
| 544 | }
|
---|
| 545 |
|
---|
[11395] | 546 | private final class Iter extends AbstractIter {
|
---|
[2399] | 547 | private final int mods;
|
---|
[8285] | 548 | private int removeSlot = -1;
|
---|
[2399] | 549 |
|
---|
| 550 | Iter() {
|
---|
| 551 | mods = modCount;
|
---|
| 552 | }
|
---|
| 553 |
|
---|
[6084] | 554 | @Override
|
---|
[11408] | 555 | public boolean hasNext() {
|
---|
| 556 | return doHasNext(data);
|
---|
| 557 | }
|
---|
| 558 |
|
---|
| 559 | @Override
|
---|
[2399] | 560 | public T next() {
|
---|
| 561 | if (!hasNext()) throw new NoSuchElementException();
|
---|
| 562 | removeSlot = slot;
|
---|
[3398] | 563 | return data[slot++];
|
---|
[2399] | 564 | }
|
---|
| 565 |
|
---|
[6084] | 566 | @Override
|
---|
[2399] | 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 |
|
---|
[11395] | 575 | @Override
|
---|
[11408] | 576 | protected void align(T[] data) {
|
---|
[3207] | 577 | if (mods != modCount)
|
---|
| 578 | throw new ConcurrentModificationException();
|
---|
[11408] | 579 | super.align(data);
|
---|
[2399] | 580 | }
|
---|
| 581 | }
|
---|
| 582 | }
|
---|