persistentmapimpl.java

这个是perst-269.zip下面的SOURCECODE,和大家分享了。

package org.garret.perst.impl;
import  org.garret.perst.*;
import  java.util.*;

class PersistentMapImpl<K extends Comparable, V extends IPersistent> extends PersistentResource implements IPersistentMap<K, V>
{
    Index<V> index;
    Object   keys;
    Link<V>  values;
    int      type;

    transient volatile Set<Entry<K,V>> entrySet;
    transient volatile Set<K>          keySet;
    transient volatile Collection<V>   valuesCol;

    static final int BTREE_TRESHOLD = 128;

    PersistentMapImpl(Storage storage, Class keyType, int initialSize) { 
        super(storage);
        type = getTypeCode(keyType);
        keys = new Comparable[initialSize];
        values = storage.<V>createLink(initialSize);
    }

    PersistentMapImpl() {}

    protected int getTypeCode(Class c) { 
        if (c.equals(byte.class) || c.equals(Byte.class)) { 
            return ClassDescriptor.tpByte;
        } else if (c.equals(short.class) || c.equals(Short.class)) {
            return ClassDescriptor.tpShort;
        } else if (c.equals(char.class) || c.equals(Character.class)) {
            return ClassDescriptor.tpChar;
        } else if (c.equals(int.class) || c.equals(Integer.class)) {
            return ClassDescriptor.tpInt;
        } else if (c.equals(long.class) || c.equals(Long.class)) {
            return ClassDescriptor.tpLong;
        } else if (c.equals(float.class) || c.equals(Float.class)) {
            return ClassDescriptor.tpFloat;
        } else if (c.equals(double.class) || c.equals(Double.class)) {
            return ClassDescriptor.tpDouble;
        } else if (c.equals(String.class)) {
            return ClassDescriptor.tpString;
        } else if (c.equals(boolean.class) || c.equals(Boolean.class)) {
            return ClassDescriptor.tpBoolean;
        } else if (c.isEnum()) {
            return ClassDescriptor.tpEnum;
        } else if (c.equals(java.util.Date.class)) {
            return ClassDescriptor.tpDate;
        } else if (IPersistent.class.isAssignableFrom(c)) {
            return ClassDescriptor.tpObject;
        } else if (Comparable.class.isAssignableFrom(c)) {
            return ClassDescriptor.tpRaw;
        } else { 
            throw new StorageError(StorageError.UNSUPPORTED_TYPE, c);
        }
    }

    public int size() {
        return index != null ? index.size() : values.size();
    }

    public boolean isEmpty() {
	return size() == 0;
    }

    public boolean containsValue(Object value) {
	Iterator<Entry<K,V>> i = entrySet().iterator();
	if (value==null) {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (e.getValue()==null)
		    return true;
	    }
	} else {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (value.equals(e.getValue()))
		    return true;
	    }
	}
	return false;
    }

    private int binarySearch(Object key) {
        Comparable[] keys = (Comparable[])this.keys;
        int l = 0, r = values.size();
        while (l < r) {
            int i = (l + r) >> 1;
            if (keys[i].compareTo(key) < 0) { 
                l = i+1;
            } else { 
                r = i;
            }
        }
        return r;
    }

    public boolean containsKey(Object key) {
        if (index != null) { 
            Key k = generateKey(key);
            return index.entryIterator(k, k, Index.ASCENT_ORDER).hasNext();
        } else {
            int i = binarySearch(key);
            return i < values.size() && ((Comparable[])keys)[i].equals(key);
        }
    }

    public V get(Object key) {
        if (index != null) { 
            return index.get(generateKey(key));
        } else {
            int i = binarySearch(key);
            if (i < values.size() && ((Comparable[])keys)[i].equals(key)) {
                return values.get(i);
            }
            return null;
        }
    }

    public V put(K key, V value) {
        V prev = null;
        if (index == null) { 
            int size = values.size();
            int i = binarySearch(key);
            if (i < size && key.equals(((Comparable[])keys)[i])) {
                prev = values.set(i, value);
            } else {
                if (size == BTREE_TRESHOLD) { 
                    index = getStorage().<V>createIndex(Btree.mapKeyType(type), true);
                    Comparable[] keys = (Comparable[])this.keys;
                    for (i = 0; i < size; i++) { 
                        index.set(generateKey(keys[i]), values.get(i));
                    }                
                    index.set(generateKey(key), value);
                    this.keys = null;
                    this.values = null;                
                    modify();
                } else {
                    Object[] oldKeys = (Object[])keys;
                    if (size >= oldKeys.length) { 
                        Comparable[] newKeys = new Comparable[size+1 > oldKeys.length*2 ? size+1 : oldKeys.length*2];
                        System.arraycopy(oldKeys, 0, newKeys, 0, i);                
                        System.arraycopy(oldKeys, i, newKeys, i+1, size-i);
                        keys = newKeys;
                        newKeys[i] = key;
                    } else {
                        System.arraycopy(oldKeys, i, oldKeys, i+1, size-i);
                        oldKeys[i] = key;
                    }
                    values.insert(i, value);
                }
            }
        } else { 
            prev = index.set(generateKey(key), value);
        }
        return prev;
    }

    public V remove(Object key) {
        if (index == null) { 
            int size = values.size();
            int i = binarySearch(key);
            if (i < size && ((Comparable[])keys)[i].equals(key)) {
                System.arraycopy(keys, i+1, keys, i, size-i-1);
                ((Comparable[])keys)[size-1] = null;
                return values.remove(i);
            }
            return null;
        } else {
            try { 
                return index.remove(generateKey(key));
            } catch (StorageError x) { 
                if (x.getErrorCode() == StorageError.KEY_NOT_FOUND) { 
                    return null;
                }
                throw x;
            }
        }
    }

    public void putAll(Map<? extends K, ? extends V> t) {
	Iterator<? extends Entry<? extends K, ? extends V>> i = t.entrySet().iterator();
	while (i.hasNext()) {
	    Entry<? extends K, ? extends V> e = i.next();
	    put(e.getKey(), e.getValue());
	}
    }

    public void clear() {
        if (index != null) { 
            index.clear();
        } else {
            values.clear();
            keys = new Comparable[((Comparable[])keys).length];
        }
    }

    public Set<K> keySet() {
	if (keySet == null) {
	    keySet = new AbstractSet<K>() {
		public Iterator<K> iterator() {
		    return new Iterator<K>() {
			private Iterator<Entry<K,V>> i = entrySet().iterator();

			public boolean hasNext() {
			    return i.hasNext();
			}

			public K next() {
			    return i.next().getKey();
			}

			public void remove() {
			    i.remove();
			}
                    };
		}

		public int size() {
		    return PersistentMapImpl.this.size();
		}

		public boolean contains(Object k) {
		    return PersistentMapImpl.this.containsKey(k);
		}
	    };
	}
	return keySet;
    }

    public Collection<V> values() {
	if (valuesCol == null) {
	    valuesCol = new AbstractCollection<V>() {
		public Iterator<V> iterator() {
		    return new Iterator<V>() {
			private Iterator<Entry<K,V>> i = entrySet().iterator();

			public boolean hasNext() {
			    return i.hasNext();
			}

			public V next() {
			    return i.next().getValue();
			}

			public void remove() {
			    i.remove();
			}
                    };
                }

		public int size() {
		    return PersistentMapImpl.this.size();
		}

		public boolean contains(Object v) {
		    return PersistentMapImpl.this.containsValue(v);
		}
	    };
	}
	return valuesCol;
    }

    protected Iterator<Entry<K,V>> entryIterator() {
        if (index != null) { 
            return new Iterator<Entry<K,V>>() {                        
                private Iterator<Entry<Object,V>> i = index.entryIterator();

                public boolean hasNext() {
                    return i.hasNext();
                }

                public Entry<K,V> next() {
                    final Entry<Object,V> e = i.next();
                    return new Entry<K,V>() {
                        public K getKey() { 
                            return (K)e.getKey();
                        }
                        public V getValue() { 
                            return e.getValue();
                        }
                        public V setValue(V value) {
                            throw new UnsupportedOperationException("Entry.Map.setValue");
                        }
                    };                        
                }

                public void remove() {
                    i.remove();
                }
            };
        } else {
            return new Iterator<Entry<K,V>>() {                     
                private int i = -1;

                public boolean hasNext() {
                    return i+1 < values.size();
                }

                public Entry<K,V> next() {
                    if (!hasNext()) { 
                        throw new NoSuchElementException(); 
                    }
                    i += 1;
                    return new Entry<K,V>() {
                        public K getKey() { 
                            return (K)(((Comparable[])keys)[i]);
                        }
                        public V getValue() { 
                            return values.get(i);
                        }
                        public V setValue(V value) {
                            throw new UnsupportedOperationException("Entry.Map.setValue");
                        }
                    };  
                }

                public void remove() {
                    if (i < 0) {
                        throw new IllegalStateException();
                    }
                    int size = values.size();
                    System.arraycopy(keys, i+1, keys, i, size-i-1);
                    ((Comparable[])keys)[size-1] = null;
                    values.removeObject(i);
                    i -= 1;
                }
            };
        }
    }

    public Set<Entry<K,V>> entrySet() {
	if (entrySet == null) {
	    entrySet = new AbstractSet<Entry<K,V>>() {
		public Iterator<Entry<K,V>> iterator() {
		    return entryIterator();
		}

		public int size() {
		    return PersistentMapImpl.this.size();
		}

                public boolean remove(Object o) {
                    if (!(o instanceof Map.Entry)) {
                        return false;
                    }
                    Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                    K key = entry.getKey();
                    V value = entry.getValue();
                    if (value != null) { 
                        V v = PersistentMapImpl.this.get(key);
                        if (value.equals(v)) {
                            PersistentMapImpl.this.remove(key);
                            return true;
                        }
                    } else {
                        if (PersistentMapImpl.this.containsKey(key)
                            && PersistentMapImpl.this.get(key) == null)
                        {
                            PersistentMapImpl.this.remove(key);
                            return true;
                        }
                    }
                    return false;
                }
                
		public boolean contains(Object k) {
                    Entry<K,V> e = (Entry<K,V>)k;
                    if (e.getValue() != null) { 
                        return e.getValue().equals(PersistentMapImpl.this.get(e.getKey()));
                    } else {
                        return PersistentMapImpl.this.containsKey(e.getKey()) 
                            && PersistentMapImpl.this.get(e.getKey()) == null;
                    }
		}
	    };
	}
	return entrySet;
    }   

     
    public boolean equals(Object o) {
	if (o == this) {
	    return true;
        }
	if (!(o instanceof Map)) {
	    return false;
        }
	Map<K,V> t = (Map<K,V>) o;
	if (t.size() != size()) {
	    return false;
        }

        try {
            Iterator<Entry<K,V>> i = entrySet().iterator();
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
		K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
                    if (!(t.get(key)==null && t.containsKey(key))) {