persistentmapimpl.java

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

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

class PersistentMapImpl extends PersistentResource implements IPersistentMap
{
    Index  index;
    Object keys;
    Link   values;
    int    type;

    transient volatile Set        entrySet;
    transient volatile Set        keySet;
    transient volatile Collection 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.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.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 Iterator iterator() { 
        return values().iterator();
    }

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

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

    public boolean containsValue(Object value) {
	Iterator i = entrySet().iterator();
	if (value==null) {
	    while (i.hasNext()) {
		Entry e = (Entry)i.next();
		if (e.getValue()==null)
		    return true;
	    }
	} else {
	    while (i.hasNext()) {
		Entry e = (Entry)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 Object 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 Object put(Object key, Object value) {
        Object prev = null;
        if (index == null) { 
            int size = values.size();
            int i = binarySearch(key);
            if (i < size && key.equals(((Comparable[])keys)[i])) {
                prev = values.get(i);
                values.set(i, (IPersistent)value);
            } else {
                if (size == BTREE_TRESHOLD) { 
                    index = getStorage().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), (IPersistent)value);
                    this.keys = null;
                    this.values = null;                
                    modify();
                } else {
                    Comparable[] oldKeys = (Comparable[])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] = (Comparable)key;
                    } else {
                        System.arraycopy(oldKeys, i, oldKeys, i+1, size-i);
                        oldKeys[i] = (Comparable)key;
                    }
                    values.insert(i, (IPersistent)value);
                }
            }
        } else { 
            prev = index.set(generateKey(key), (IPersistent)value);
        }
        return prev;
    }

    public Object 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;
                Object prev = values.get(i);
                values.remove(i);
                return prev;
            }
            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 t) {
	Iterator i = t.entrySet().iterator();
	while (i.hasNext()) {
	    Entry e = (Entry)i.next();
	    put(e.getKey(), (IPersistent)e.getValue());
	}
    }

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

    public Set keySet() {
	if (keySet == null) {
	    keySet = new AbstractSet() {
		public Iterator iterator() {
		    return new Iterator() {
			private Iterator i = entrySet().iterator();

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

			public Object next() {
			    return ((Entry)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 values() {
	if (valuesCol == null) {
	    valuesCol = new AbstractCollection() {
		public Iterator iterator() {
		    return new Iterator() {
			private Iterator i = entrySet().iterator();

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

			public Object next() {
			    return ((Entry)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 entryIterator() {
        if (index != null) { 
            return index.entryIterator();
        } else {
            return new Iterator() {                     
                private int i = -1;

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

                public Object next() {
                    if (!hasNext()) { 
                        throw new NoSuchElementException(); 
                    }
                    i += 1;
                    return new Entry() {
                        public Object getKey() { 
                            return (((Comparable[])keys)[i]);
                        }
                        public Object getValue() { 
                            return values.get(i);
                        }
                        public Object setValue(Object 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.remove(i);
                    i -= 1;
                }
            };
        }
    }

    public Set entrySet() {
	if (entrySet == null) {
	    entrySet = new AbstractSet() {
		public Iterator iterator() {
		    return entryIterator();
		}

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

                public boolean remove(Object o) {
                    if (!(o instanceof Map.Entry)) {
                        return false;
                    }
                    Map.Entry entry = (Map.Entry) o;
                    Object key = entry.getKey();
                    Object value = entry.getValue();
                    if (value != null) { 
                        Object 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 e = (Entry)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 t = (Map) o;
	if (t.size() != size()) {
	    return false;
        }

        try {
            Iterator i = entrySet().iterator();
            while (i.hasNext()) {
                Entry e = (Entry)i.next();
		Object key = e.getKey();