Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
BEGIN LICENSE BLOCK ***** Version: CPL 1.0/GPL 2.0/LGPL 2.1 The contents of this file are subject to the Common Public License Version 1.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.eclipse.org/legal/cpl-v10.html Software distributed under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for the specific language governing rights and limitations under the License. Copyright (C) 2006 Kresten Krab Thorup <krab@gnu.org> Alternatively, the contents of this file may be used under the terms of either of the GNU General Public License Version 2 or later (the "GPL"), or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which case the provisions of the GPL or the LGPL are applicable instead of those above. If you wish to allow use of your version of this file only under the terms of either the GPL or the LGPL, and not to allow others to use your version of this file under the terms of the CPL, indicate your decision by deleting the provisions above and replace them with the notice and other provisions required by the GPL or the LGPL. If you do not delete the provisions above, a recipient may use your version of this file under the terms of any one of the CPL, the GPL or the LGPL. END LICENSE BLOCK ***
 
 
 package org.jruby.util;
 
 import java.util.Map;
Class WeakIdentityHashMap is a hash map that hashes objects based on System.identityHashMap, and holds weakly onto the key. This fails if values make reference to the keys!

Author(s):
Kresten Krab Thorup
Version:
2.0
Since:
1.0
 
 public class WeakIdentityHashMap extends GenericMap implements Map {
 
     private static final float DEFAULT_RATIO = 0.75F;
 
     private static final Object NULL_KEY = new Object();
 
     private final ReferenceQueue queue = new ReferenceQueue();
 
     private static Object unmaskKey(Object key) {
         if (key == ) {
             return null;
         } else {
             return key;
         }
     }
 
     private Object maskKey(Object key) {
         if (key == null) {
             return ;
         } else {
             return key;
         }
     }
 
     class Entry extends WeakReference implements Map.Entry {
         private final int key_hash;
         private Entry next;
         private Object value;
 
         @Override
         public int hashCode() {
             return  ^ valueHash(getValue());
         }
 
         @Override
         public boolean equals(Object other) {
             if (other instanceof Map.Entry) {
                 Map.Entry ent = (Map.Entryother;
                 return getKey() == ent.getKey()
                         && valueEquals(getValue(), ent.getValue());
             } else {
                 return false;
             }
         }
 
         Entry(int key_hashObject masked_keyObject valueEntry nextReferenceQueue q) {
             super(masked_keyq);
             this. = key_hash;
             this. = value;
             this. = next;
         }
 
         Object getMaskedKey() {
             return super.get();
        }
        
        public Object getKey() {
            return unmaskKey(getMaskedKey());
        }
        public Object getValue() {
            return ;
        }
        public Object setValue(Object value) {
            Object result = this.;
            this. = value;
            return result;
        }
        boolean sameKey(int hashObject masked_key) {
            return getMaskedKey() == masked_key;
        }
    }

    
the hash index
    private Entry[] table;

    
the current range for table.
    private int range;
    private float ratio;

    
translate hash code bucket to index
    private int index(int hash) {
        return (hash & 0x7ffffff) % ;
    }

    
the default and only constructor
    public WeakIdentityHashMap() {
        clear(3);
    }
    public WeakIdentityHashMap(int size) {
        clear(Math.max(3, Math.round(size/)));
    }
    public void clear() {
        clear(3);
    }
    
    private void clear(int size) {
         = size;
        this. = 0;
         = ;
         = new Entry[];
    }
    private void expunge() {
        Entry e;
        while ((e = (Entry.poll()) != null) {
            removeEntry(e);
        }
    }

    
return the element with the given key
    public Object get(Object key) {
        Object masked_key = maskKey(key);
        int hash = keyHash(masked_key);
        return get(hashmasked_key);
    }
    private Object get(int hashObject masked_key) {
        int idx = index(hash);
        expunge();
        for (Entry ent = [idx]; ent != nullent = ent.next) {
            if (ent.sameKey(hashmasked_key)) {
                return ent.value;
            }
        }
        return null;
    }

    
return the element with the given key
    @Override
    public boolean containsKey(Object key) {
        Object masked_key = maskKey(key);
        int hash = keyHash(masked_key);
        return containsKey(hashmasked_key);
    }
    private boolean containsKey(int hashObject masked_key) {
        int idx = index(hash);
        expunge();
        for (Entry ent = [idx]; ent != nullent = ent.next) {
            if (ent.sameKey(hashmasked_key)) {
                return true;
            }
        }
        return false;
    }
    public Object put(Object keyObject value) {
        Object masked_key = maskKey(key);
        int hash = keyHash(masked_key);
        return put(hashmasked_keyvalue);
    }
    private Object put(int hashObject masked_keyObject value) {
        int idx = index(hash);
        for (Entry ent = [idx]; ent != nullent = ent.next) {
            if (ent.sameKey(hashmasked_key)) {
                return ent.setValue(value);
            }
        }
        expunge();
        if (1.0F *  /  > ) {
            grow();
            idx = index(hash);
        }
        [idx] = new Entry(hashmasked_keyvalue[idx], );
         += 1;
        return null;
    }
    public Object remove(Object key) {
        key = maskKey(key);
        int hash = keyHash(key);
        return remove(hashkey);
    }
    public Object remove(int hashObject key) {
        key = maskKey(key);
        int idx = index(hash);
        Entry entry = [idx];
        if (entry != null) {
            if (entry.sameKey(hashkey)) {
                [idx] = entry.next;
                 -= 1;
                return entry.getValue();
            } else {
                Entry ahead = entry.next;
                while (ahead != null) {
                    if (ahead.sameKey(hashkey)) {
                        entry.next = ahead.next;
                         -= 1;
                        return ahead.getValue();
                    }
                    entry = ahead;
                    ahead = ahead.next;
                }
            }
        }
        // it was not found at all!
        return null;
    }
    private void removeEntry(Entry ent) {
        int idx = index(ent.key_hash);
        Entry entry = [idx];
        if (entry != null) {
            if (entry == ent) {
                [idx] = entry.next;
                 -= 1;
                return;
            } else {
                Entry ahead = entry.next;
                while (ahead != null) {
                    if (ahead == ent) {
                        entry.next = ahead.next;
                         -= 1;
                        return;
                    }
                    entry = ahead;
                    ahead = ahead.next;
                }
            }
        }
        
        valueRemoved(ent.value);
    }
    // can be overridden to be informed when objects are removed
    protected void valueRemoved(Object value) {
	}
	private void grow() {
        int old_range = ;
        Entry[] old_table = ;
         = old_range * 2 + 1;
         = new Entry[];
        for (int i = 0; i < old_rangei++) {
            Entry entry = old_table[i];
            while (entry != null) {
                Entry ahead = entry.next;
                int idx = index(entry.key_hash);
                entry.next = [idx];
                [idx] = entry;
                entry = ahead;
            }
        }
    }
    final class EntryIterator implements Iterator {
        private int idx;
        private Entry entry;
        EntryIterator() {
             = 0;
            expunge();
             = [0];
            locateNext();
        }
        private void locateNext() {
            // we reached the end of a list
            while ( == null) {
                // goto next bucket
                 += 1;
                if ( == ) {
                    // we reached the end
                    return;
                }
                // entry is the first element of this bucket
                 = [];
            }
        }
        public boolean hasNext() {
            return ( != null);
        }
        public Object next() {
            Object result = ;
            if (result == null) {
                throw new NoSuchElementException();
            } else {
                 = .;
                locateNext();
                return result;
            }
        }
        public void remove() {
            Entry remove = ;
            expunge();
             = .;
            locateNext();
            WeakIdentityHashMap.this.removeEntry(remove);
        }
    }
    protected Iterator entryIterator() {
        return new EntryIterator();
    }
    @Override
    protected final int keyHash(Object key) {
        return System.identityHashCode(key);
    }
    @Override
    protected final boolean keyEquals(Object key1Object key2) {
        return key1 == key2;
    }
    @Override
    public int size() {
        expunge();
        return super.size();
    }
    
    @Override
    public boolean isEmpty() {
        return size() == 0;
    }
New to GrepCode? Check out our FAQ X