Mutable Map implementation with small memory footprint.
package bayou.util; | |
import java.util.*; | |
/** | |
* Mutable Map implementation with small memory footprint. | |
* <p> | |
* This class is suitable for maps with small number of entries. | |
* The implementation stores keys and values in an array; | |
* searching a key will be a linear operation. | |
* </p> | |
*/ | |
@SuppressWarnings("unchecked") | |
class SmallMap<K,V> extends AbstractMap<K,V> | |
{ | |
// keys and values | |
Object[] kvs; // k1,v1,k2,v2,... | |
int size; | |
// return -1 if not found | |
int index(K key) | |
{ | |
int h = key.hashCode(); | |
// we compare hash codes of 2 keys, to fail fast if they are not equal (the usual case) | |
for(int i=0; i< size; i++) | |
{ | |
K n = (K) kvs[2*i]; // kvs!=null, because size>0 here | |
if(h==n.hashCode() && key.equals(n)) | |
return i; | |
} | |
return -1; | |
} | |
@Override | |
public V put(K key, V value) | |
{ | |
int index = index(key); | |
if(index!=-1) | |
{ | |
V old = (V) kvs[2*index+1]; | |
kvs[2*index+1] = value; | |
return old; | |
} | |
// new key | |
if(kvs ==null) | |
kvs = new Object[2*4]; // usually not many keys | |
else if(kvs.length==2* size) // full | |
kvs = Arrays.copyOf(kvs, 2*(size +4)); // we don't expect many more keys | |
kvs[2* size] = key; | |
kvs[2* size +1] = value; | |
size++; | |
return null; | |
} | |
// AbstractMap does get() by linear search thru entrySet, which is generally not good. | |
// but it works for us, since we store entries as an array (reasoning that there aren't many entries) | |
@Override | |
public Set<Entry<K, V>> entrySet() | |
{ | |
return new EntrySet(); | |
} | |
class EntrySet extends AbstractSet<Entry<K, V>> | |
{ | |
@Override | |
public Iterator<Entry<K, V>> iterator() | |
{ | |
return new EntryIterator(); | |
} | |
@Override | |
public int size() | |
{ | |
return size; | |
} | |
} | |
class EntryIterator implements Iterator<Entry<K, V>> | |
{ | |
int x; | |
MyEntry current; | |
@Override | |
public boolean hasNext() | |
{ | |
return x < size; | |
} | |
@Override | |
public Entry<K, V> next() | |
{ | |
if(!hasNext()) | |
throw new NoSuchElementException(); | |
return current = new MyEntry(x++); | |
} | |
@Override | |
public void remove() | |
{ | |
if(current==null) | |
throw new IllegalStateException(); | |
current.remove(); | |
current = null; | |
x--; // adjust pointer | |
} | |
} | |
class MyEntry extends SimpleEntry<K, V> | |
{ | |
int index; // -1 if removed | |
MyEntry(int index) | |
{ | |
super( (K) kvs[2*index], (V) kvs[2*index+1] ); | |
this.index = index; | |
} | |
void remove() | |
{ | |
validateIndex(); | |
int remain = size - index - 1; | |
if(remain>0) | |
System.arraycopy(kvs, 2*index+2, kvs, 2*index, 2*remain); | |
kvs[2* size -2]=null; | |
kvs[2* size -1]=null; | |
size--; | |
index = -1; | |
} | |
// the table cell pointed to by the index may no longer represent this entry | |
void validateIndex() throws ConcurrentModificationException | |
{ | |
if(index>= size) // likely some attrs were removed by someone else. | |
throw new ConcurrentModificationException(); | |
Object prevKey = this.getKey(); // as seen in the constructor | |
Object currKey = kvs[2* index]; | |
if(prevKey!=currKey) // identity comparison! | |
throw new ConcurrentModificationException(); | |
// even if prevKey==currKey, table might have been modified. | |
// we cannot detect that case, but it's not harmful. | |
// we could also do prevKey.equals(currKey) to be more lenient, since it's not harmful either. | |
} | |
// getKey()/getValue() still works after remove(). but setValue() does not. | |
@Override | |
public V setValue(V value) | |
{ | |
if(index==-1) | |
throw new IllegalStateException("this entry has been removed from the map"); | |
// setValue() after remove() is very likely a programming error. | |
validateIndex(); | |
V old = super.setValue(value); // local copy | |
kvs[2* index +1] = value; // write through | |
return old; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment