/* * JOSMng - a Java Open Street Map editor, the next generation. * * Copyright (C) 2008 Petr Nejedly
Map.put(t,t), that is, for caches, uniqueness filters or similar.
*
* The semantics of equivalency can be external to the object, using the
* {@link Hash} interface. The set also supports querying for entries using
* different key type, in case you can provide a Hash implementation
* that can resolve the equality.
*
* Examples
* - A String cache:
*
* Storage cache = new Storage(); // use default Hash
* for (String input : data) {
* String onlyOne = cache.putIfUnique(input);
* ....
* }
*
* - Identity-based set:
*
* Storage
* - An object with int ID and id-based lookup:
*
* class Thing { int id; }
* Storage things = new Storage(new Hash() {
* public int getHashCode(Thing t) {
* return t.id;
* }
* public boolean equals(Thing t1, Thing t2) {
* return t1 == t2;
* }
* });
* Map fk = things.foreignKey(new Hash() {
* public int getHashCode(Integer i) {
* return i.getIntValue();
* }
* public boolean equals(Integer k, Thing t) {
* return t.id == k.getIntvalue();
* }
* }
*
* things.put(new Thing(3));
* assert things.get(new Thing(3)) == fk.get(3);
*
*
*
* @author nenik
*/
public class Storage extends AbstractSet {
private final Hash super T,? super T> hash;
private T[] data;
private int mask;
private int size;
private transient volatile int modCount = 0;
private float loadFactor = 0.6f;
private static final int DEFAULT_CAPACITY = 16;
private final boolean safeIterator;
private boolean arrayCopyNecessary;
public Storage() {
this(Storage.defaultHash(), DEFAULT_CAPACITY, false);
}
public Storage(int capacity) {
this(Storage.defaultHash(), capacity, false);
}
public Storage(Hash super T,? super T> ha) {
this(ha, DEFAULT_CAPACITY, false);
}
public Storage(boolean safeIterator) {
this(Storage.defaultHash(), DEFAULT_CAPACITY, safeIterator);
}
public Storage(int capacity, boolean safeIterator) {
this(Storage.defaultHash(), capacity, safeIterator);
}
public Storage(Hash super T,? super T> ha, boolean safeIterator) {
this(ha, DEFAULT_CAPACITY, safeIterator);
}
public Storage(Hash super T, ? super T> ha, int capacity) {
this(ha, capacity, false);
}
/**
* constructor
* @param ha
* @param capacity
* @param safeIterator If set to false, you must not modify the Storage
* while iterating over it. If set to true, you can savely
* modify, but the read-only iteration will happen on a copy
* of the unmodified Storage.
* This is similar to CopyOnWriteArrayList.
*/
public Storage(Hash super T, ? super T> ha, int capacity, boolean safeIterator) {
this.hash = ha;
int cap = 1 << (int)(Math.ceil(Math.log(capacity/loadFactor) / Math.log(2)));
@SuppressWarnings("unchecked") T[] newData = (T[]) new Object[cap];
data = newData;
mask = data.length - 1;
this.safeIterator = safeIterator;
}
private void copyArray() {
if (arrayCopyNecessary) {
@SuppressWarnings("unchecked") T[] newData = (T[]) new Object[data.length];
System.arraycopy(data, 0, newData, 0, data.length);
data = newData;
arrayCopyNecessary = false;
}
}
// --------------- Collection implementation ------------------------
@Override
public synchronized int size() {
return size;
}
@Override
public synchronized Iterator iterator() {
if (safeIterator) {
arrayCopyNecessary = true;
return new SafeReadonlyIter(data);
} else
return new Iter();
}
@Override
public synchronized boolean contains(Object o) {
@SuppressWarnings("unchecked") T t = (T) o;
int bucket = getBucket(hash, t);
return bucket >= 0;
}
@Override
public synchronized boolean add(T t) {
T orig = putUnique(t);
return orig == t;
}
@Override
public synchronized boolean remove(Object o) {
@SuppressWarnings("unchecked") T t = (T) o;
T tOrig = removeElem(t);
return tOrig != null;
}
@Override
public synchronized void clear() {
copyArray();
modCount++;
size = 0;
for (int i = 0; i Map foreignKey(Hash h) {
return new FMap(h);
}
// ---------------- Implementation
/**
* Additional mixing of hash
*/
private int rehash(int h) {
//return 54435761*h;
return 1103515245*h >> 2;
}
/**
* Finds a bucket for given key.
*
* @param key The key to compare
* @return the bucket equivalent to the key or -(bucket) as an empty slot
* where such an entry can be stored.
*/
private int getBucket(Hash ha, K key) {
T entry;
int hcode = rehash(ha.getHashCode(key));
int bucket = hcode & mask;
while ((entry = data[bucket]) != null) {
if (ha.equals(key, entry))
return bucket;
bucket = (bucket+1) & mask;
}
return ~bucket;
}
private T doRemove(int slot) {
T t = data[slot];
assert t != null;
fillTheHole(slot); // fill the hole (or null it)
size--;
return t;
}
private void fillTheHole(int hole) {
int bucket = (hole+1) & mask;
T entry;
while ((entry = data[bucket]) != null) {
int right = rehash(hash.getHashCode(entry)) & mask;
// if the entry should be in (circular-wise)
// we can't move it. The move can be proved safe otherwise,
// because the entry safely belongs to
if ((bucket < right && (right <= hole || hole <= bucket)) ||
(right <=hole && hole <= bucket)) {
data[hole] = data[bucket];
hole = bucket;
}
bucket = (bucket+1) & mask;
}
// no entry belongs here, just null out the slot
data[hole] = null;
}
private void ensureSpace() {
if (size > data.length*loadFactor) { // rehash
@SuppressWarnings("unchecked") T[] big = (T[]) new Object[data.length * 2];
int nMask = big.length - 1;
for (T o : data) {
if (o == null) {
continue;
}
int bucket = rehash(hash.getHashCode(o)) & nMask;
while (big[bucket] != null) {
bucket = (bucket+1) & nMask;
}
big[bucket] = o;
}
data = big;
mask = nMask;
}
}
// -------------- factories --------------------
/**
* A factory for default hash implementation.
* @return a hash implementation that just delegates to object's own
* hashCode and equals.
*/
public static Hash defaultHash() {
return new Hash() {
public int getHashCode(O t) {
return t.hashCode();
}
public boolean equals(O t1, O t2) {
return t1.equals(t2);
}
};
}
/*
public static Hash identityHash() {
return new Hash() {
public int getHashCode(O t) {
return System.identityHashCode(t);
}
public boolean equals(O t1, O t2) {
return t1 == t2;
}
};
}
*/
private class FMap implements Map {
Hash fHash;
private FMap(Hash h) {
fHash = h;
}
public int size() {
return Storage.this.size();
}
public boolean isEmpty() {
return Storage.this.isEmpty();
}
public boolean containsKey(Object o) {
@SuppressWarnings("unchecked") K key = (K) o;
int bucket = getBucket(fHash, key);
return bucket >= 0;
}
public boolean containsValue(Object value) {
return Storage.this.contains(value);
}
public T get(Object o) {
@SuppressWarnings("unchecked") K key = (K) o;
int bucket = getBucket(fHash, key);
return bucket < 0 ? null : data[bucket];
}
public T put(K key, T value) {
if (!fHash.equals(key, value)) throw new IllegalArgumentException("inconsistent key");
return Storage.this.put(value);
}
public T remove(Object o) {
modCount++;
@SuppressWarnings("unchecked") K key = (K) o;
int bucket = getBucket(fHash, key);
return bucket < 0 ? null : doRemove(bucket);
}
public void putAll(Map extends K, ? extends T> m) {
if (m instanceof Storage.FMap) {
Storage.this.addAll(((Storage.FMap)m).values());
} else {
for (Map.Entry extends K, ? extends T> e : m.entrySet()) {
put(e.getKey(), e.getValue());
}
}
}
public void clear() {
Storage.this.clear();
}
public Set keySet() {
throw new UnsupportedOperationException();
}
public Collection values() {
return Storage.this;
}
public Set> entrySet() {
throw new UnsupportedOperationException();
}
}
private final class SafeReadonlyIter implements Iterator {
final T[] data;
int slot = 0;
SafeReadonlyIter(T[] data) {
this.data = data;
}
public boolean hasNext() {
align();
return slot < data.length;
}
public T next() {
if (!hasNext()) throw new NoSuchElementException();
return data[slot++];
}
public void remove() {
throw new UnsupportedOperationException();
}
private void align() {
while (slot < data.length && data[slot] == null) {
slot++;
}
}
}
private final class Iter implements Iterator {
private final int mods;
int slot = 0;
int removeSlot = -1;
Iter() {
mods = modCount;
}
public boolean hasNext() {
align();
return slot < data.length;
}
public T next() {
if (!hasNext()) throw new NoSuchElementException();
removeSlot = slot;
return data[slot++];
}
public void remove() {
if (removeSlot == -1) throw new IllegalStateException();
doRemove(removeSlot);
slot = removeSlot; // some entry might have been relocated here
removeSlot = -1;
}
private void align() {
if (mods != modCount)
throw new ConcurrentModificationException();
while (slot < data.length && data[slot] == null) {
slot++;
}
}
}
}