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&lt;T,T&gt;.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&lt;String&gt; 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&lt;Object&gt; identity = new Storage(new Hash&lt;Object,Object&gt; {
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&lt;Thing&gt; things = new Storage(new Hash&lt;Thing,Thing&gt;() {
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&lt;Integer,Thing&gt; fk = things.foreignKey(new Hash&lt;Integer,Thing&gt;() {
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}