Home » openjdk-7 » java » util » [javadoc | source]

    1   /*
    2    * Copyright 2008 Google Inc.
    3    * 
    4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not
    5    * use this file except in compliance with the License. You may obtain a copy of
    6    * the License at
    7    * 
    8    * http://www.apache.org/licenses/LICENSE-2.0
    9    * 
   10    * Unless required by applicable law or agreed to in writing, software
   11    * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
   12    * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
   13    * License for the specific language governing permissions and limitations under
   14    * the License.
   15    */
   16   package java.util;
   17   
   18   import com.google.gwt.core.client.JavaScriptObject;
   19   
   20   /**
   21    * Implementation of Map interface based on a hash table. <a
   22    * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html">[Sun
   23    * docs]</a>
   24    * 
   25    * @param <K> key type
   26    * @param <V> value type
   27    */
   28   abstract class AbstractHashMap<K, V> extends AbstractMap<K, V> {
   29     /*
   30      * Implementation notes:
   31      * 
   32      * String keys are stored in a separate map from non-String keys. String keys
   33      * are mapped to their values via a JS associative map, stringMap. String keys
   34      * could collide with intrinsic properties (like watch, constructor) so we
   35      * prepend each key with a ':' inside of stringMap.
   36      * 
   37      * Integer keys are used to index all non-string keys. A key's hashCode is the
   38      * index in hashCodeMap which should contain that key. Since several keys may
   39      * have the same hash, each value in hashCodeMap is actually an array
   40      * containing all entries whose keys share the same hash.
   41      */
   42     private final class EntrySet extends AbstractSet<Entry<K, V>> {
   43   
   44       @Override
   45       public void clear() {
   46         AbstractHashMap.this.clear();
   47       }
   48   
   49       @Override
   50       public boolean contains(Object o) {
   51         if (o instanceof Map.Entry) {
   52           Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
   53           Object key = entry.getKey();
   54           if (AbstractHashMap.this.containsKey(key)) {
   55             Object value = AbstractHashMap.this.get(key);
   56             return AbstractHashMap.this.equals(entry.getValue(), value);
   57           }
   58         }
   59         return false;
   60       }
   61   
   62       @Override
   63       public Iterator<Entry<K, V>> iterator() {
   64         return new EntrySetIterator();
   65       }
   66   
   67       @Override
   68       public boolean remove(Object entry) {
   69         if (contains(entry)) {
   70           Object key = ((Map.Entry<?, ?>) entry).getKey();
   71           AbstractHashMap.this.remove(key);
   72           return true;
   73         }
   74         return false;
   75       }
   76   
   77       @Override
   78       public int size() {
   79         return AbstractHashMap.this.size();
   80       }
   81     }
   82   
   83     /**
   84      * Iterator for <code>EntrySetImpl</code>.
   85      */
   86     private final class EntrySetIterator implements Iterator<Entry<K, V>> {
   87       private final Iterator<Map.Entry<K, V>> iter;
   88       private Map.Entry<K, V> last = null;
   89   
   90       /**
   91        * Constructor for <code>EntrySetIterator</code>.
   92        */
   93       public EntrySetIterator() {
   94         List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
   95         if (nullSlotLive) {
   96           list.add(new MapEntryNull());
   97         }
   98         addAllStringEntries(list);
   99         addAllHashEntries(list);
  100         this.iter = list.iterator();
  101       }
  102   
  103       public boolean hasNext() {
  104         return iter.hasNext();
  105       }
  106   
  107       public Map.Entry<K, V> next() {
  108         return last = iter.next();
  109       }
  110   
  111       public void remove() {
  112         if (last == null) {
  113           throw new IllegalStateException("Must call next() before remove().");
  114         } else {
  115           iter.remove();
  116           AbstractHashMap.this.remove(last.getKey());
  117           last = null;
  118         }
  119       }
  120     }
  121   
  122     private final class MapEntryNull extends AbstractMapEntry<K, V> {
  123   
  124       public K getKey() {
  125         return null;
  126       }
  127   
  128       public V getValue() {
  129         return nullSlot;
  130       }
  131   
  132       public V setValue(V object) {
  133         return putNullSlot(object);
  134       }
  135     }
  136   
  137     // Instantiated from JSNI
  138     @SuppressWarnings("unused")
  139     private final class MapEntryString extends AbstractMapEntry<K, V> {
  140   
  141       private final String key;
  142   
  143       public MapEntryString(String key) {
  144         this.key = key;
  145       }
  146   
  147       @SuppressWarnings("unchecked")
  148       public K getKey() {
  149         return (K) key;
  150       }
  151   
  152       public V getValue() {
  153         return getStringValue(key);
  154       }
  155   
  156       public V setValue(V object) {
  157         return putStringValue(key, object);
  158       }
  159     }
  160   
  161     /**
  162      * A map of integral hashCodes onto entries.
  163      */
  164     // Used from JSNI.
  165     @SuppressWarnings("unused")
  166     private transient JavaScriptObject hashCodeMap;
  167   
  168     /**
  169      * This is the slot that holds the value associated with the "null" key.
  170      */
  171     private transient V nullSlot;
  172   
  173     private transient boolean nullSlotLive;
  174   
  175     private int size;
  176   
  177     /**
  178      * A map of Strings onto values.
  179      */
  180     // Used from JSNI.
  181     @SuppressWarnings("unused")
  182     private transient JavaScriptObject stringMap;
  183   
  184     {
  185       clearImpl();
  186     }
  187   
  188     public AbstractHashMap() {
  189     }
  190   
  191     public AbstractHashMap(int ignored) {
  192       // This implementation of HashMap has no need of initial capacities.
  193       this(ignored, 0);
  194     }
  195   
  196     public AbstractHashMap(int ignored, float alsoIgnored) {
  197       // This implementation of HashMap has no need of load factors or capacities.
  198       if (ignored < 0 || alsoIgnored < 0) {
  199         throw new IllegalArgumentException(
  200             "initial capacity was negative or load factor was non-positive");
  201       }
  202     }
  203   
  204     public AbstractHashMap(Map<? extends K, ? extends V> toBeCopied) {
  205       this.putAll(toBeCopied);
  206     }
  207   
  208     @Override
  209     public void clear() {
  210       clearImpl();
  211     }
  212   
  213     public abstract Object clone();
  214   
  215     @Override
  216     public boolean containsKey(Object key) {
  217       return (key == null) ? nullSlotLive : (!(key instanceof String)
  218           ? hasHashValue(key, getHashCode(key)) : hasStringValue((String) key));
  219     }
  220   
  221     @Override
  222     public boolean containsValue(Object value) {
  223       if (nullSlotLive && equals(nullSlot, value)) {
  224         return true;
  225       } else if (containsStringValue(value)) {
  226         return true;
  227       } else if (containsHashValue(value)) {
  228         return true;
  229       }
  230       return false;
  231     }
  232   
  233     @Override
  234     public Set<Map.Entry<K, V>> entrySet() {
  235       return new EntrySet();
  236     }
  237   
  238     @Override
  239     public V get(Object key) {
  240       return (key == null) ? nullSlot : (!(key instanceof String) ? getHashValue(
  241           key, getHashCode(key)) : getStringValue((String) key));
  242     }
  243   
  244     @Override
  245     public V put(K key, V value) {
  246       return (key == null) ? putNullSlot(value) : (!(key instanceof String)
  247           ? putHashValue(key, value, getHashCode(key)) : putStringValue(
  248               (String) key, value));
  249     }
  250   
  251     @Override
  252     public V remove(Object key) {
  253       return (key == null) ? removeNullSlot() : (!(key instanceof String)
  254           ? removeHashValue(key, getHashCode(key))
  255           : removeStringValue((String) key));
  256     }
  257   
  258     @Override
  259     public int size() {
  260       return size;
  261     }
  262   
  263     /**
  264      * Subclasses must override to return a whether or not two keys or values are
  265      * equal.
  266      */
  267     protected abstract boolean equals(Object value1, Object value2);
  268   
  269     /**
  270      * Subclasses must override to return a hash code for a given key. The key is
  271      * guaranteed to be non-null and not a String.
  272      */
  273     protected abstract int getHashCode(Object key);
  274   
  275     private native void addAllHashEntries(Collection<?> dest) /*-{
  276       var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
  277       for (var hashCode in hashCodeMap) {
  278         // sanity check that it's really an integer
  279         if (hashCode == parseInt(hashCode)) {
  280           var array = hashCodeMap[hashCode];
  281           for (var i = 0, c = array.length; i < c; ++i) {
  282             dest.@java.util.Collection::add(Ljava/lang/Object;)(array[i]);
  283           }
  284         }
  285       }
  286     }-*/;
  287   
  288     private native void addAllStringEntries(Collection<?> dest) /*-{
  289       var stringMap = this.@java.util.AbstractHashMap::stringMap;
  290       for (var key in stringMap) {
  291         // only keys that start with a colon ':' count
  292         if (key.charCodeAt(0) == 58) {
  293           var entry = @java.util.AbstractHashMap$MapEntryString::new(Ljava/util/AbstractHashMap;Ljava/lang/String;)(this, key.substring(1));
  294           dest.@java.util.Collection::add(Ljava/lang/Object;)(entry);
  295         }
  296       }
  297     }-*/;
  298   
  299     private void clearImpl() {
  300       hashCodeMap = JavaScriptObject.createArray();
  301       stringMap = JavaScriptObject.createObject();
  302       nullSlotLive = false;
  303       nullSlot = null;
  304       size = 0;
  305     }
  306   
  307     /**
  308      * Returns true if hashCodeMap contains any Map.Entry whose value is Object
  309      * equal to <code>value</code>.
  310      */
  311     private native boolean containsHashValue(Object value) /*-{
  312       var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap;
  313       for (var hashCode in hashCodeMap) {
  314         // sanity check that it's really one of ours
  315         if (hashCode == parseInt(hashCode)) {
  316           var array = hashCodeMap[hashCode];
  317           for (var i = 0, c = array.length; i < c; ++i) {
  318             var entry = array[i];
  319             var entryValue = entry.@java.util.Map$Entry::getValue()();
  320             if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
  321               return true;
  322             }
  323           }
  324         }
  325       }
  326       return false;
  327     }-*/;
  328   
  329     /**
  330      * Returns true if stringMap contains any key whose value is Object equal to
  331      * <code>value</code>.
  332      */
  333     private native boolean containsStringValue(Object value) /*-{
  334       var stringMap = this.@java.util.AbstractHashMap::stringMap;
  335       for (var key in stringMap) {
  336         // only keys that start with a colon ':' count
  337         if (key.charCodeAt(0) == 58) {
  338           var entryValue = stringMap[key];
  339           if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
  340             return true;
  341           }
  342         }
  343       }
  344       return false;
  345     }-*/;
  346   
  347     /**
  348      * Bridge method from JSNI that keeps us from having to make polymorphic calls
  349      * in JSNI. By putting the polymorphism in Java code, the compiler can do a
  350      * better job of optimizing in most cases.
  351      */
  352     @SuppressWarnings("unused")
  353     private boolean equalsBridge(Object value1, Object value2) {
  354       return equals(value1, value2);
  355     }
  356   
  357     /**
  358      * Returns the Map.Entry whose key is Object equal to <code>key</code>,
  359      * provided that <code>key</code>'s hash code is <code>hashCode</code>;
  360      * or <code>null</code> if no such Map.Entry exists at the specified
  361      * hashCode.
  362      */
  363     private native V getHashValue(Object key, int hashCode) /*-{
  364       var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
  365       if (array) {
  366         for (var i = 0, c = array.length; i < c; ++i) {
  367           var entry = array[i];
  368           var entryKey = entry.@java.util.Map$Entry::getKey()();
  369           if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
  370             return entry.@java.util.Map$Entry::getValue()();
  371           }
  372         }
  373       }
  374       return null;
  375     }-*/;
  376   
  377     /**
  378      * Returns the value for the given key in the stringMap. Returns
  379      * <code>null</code> if the specified key does not exist.
  380      */
  381     private native V getStringValue(String key) /*-{
  382       return this.@java.util.AbstractHashMap::stringMap[':' + key];
  383     }-*/;
  384   
  385     /**
  386      * Returns true if the a key exists in the hashCodeMap that is Object equal to
  387      * <code>key</code>, provided that <code>key</code>'s hash code is
  388      * <code>hashCode</code>.
  389      */
  390     private native boolean hasHashValue(Object key, int hashCode) /*-{
  391       var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
  392       if (array) {
  393         for (var i = 0, c = array.length; i < c; ++i) {
  394           var entry = array[i];
  395           var entryKey = entry.@java.util.Map$Entry::getKey()();
  396           if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
  397             return true;
  398           }
  399         }
  400       }
  401       return false;
  402     }-*/;
  403   
  404     /**
  405      * Returns true if the given key exists in the stringMap.
  406      */
  407     private native boolean hasStringValue(String key) /*-{
  408       return (':' + key) in this.@java.util.AbstractHashMap::stringMap;
  409     }-*/;
  410   
  411     /**
  412      * Sets the specified key to the specified value in the hashCodeMap. Returns
  413      * the value previously at that key. Returns <code>null</code> if the
  414      * specified key did not exist.
  415      */
  416     private native V putHashValue(K key, V value, int hashCode) /*-{
  417       var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
  418       if (array) {
  419         for (var i = 0, c = array.length; i < c; ++i) {
  420           var entry = array[i];
  421           var entryKey = entry.@java.util.Map$Entry::getKey()();
  422           if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
  423             // Found an exact match, just update the existing entry
  424             var previous = entry.@java.util.Map$Entry::getValue()();
  425             entry.@java.util.Map$Entry::setValue(Ljava/lang/Object;)(value);
  426             return previous;
  427           }
  428         }
  429       } else {
  430         array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode] = [];
  431       }
  432       var entry = @java.util.MapEntryImpl::new(Ljava/lang/Object;Ljava/lang/Object;)(key, value);
  433       array.push(entry);
  434       ++this.@java.util.AbstractHashMap::size;
  435       return null;
  436     }-*/;
  437   
  438     private V putNullSlot(V value) {
  439       V result = nullSlot;
  440       nullSlot = value;
  441       if (!nullSlotLive) {
  442         nullSlotLive = true;
  443         ++size;
  444       }
  445       return result;
  446     }
  447   
  448     /**
  449      * Sets the specified key to the specified value in the stringMap. Returns the
  450      * value previously at that key. Returns <code>null</code> if the specified
  451      * key did not exist.
  452      */
  453     private native V putStringValue(String key, V value) /*-{
  454       var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
  455       key = ':' + key;
  456       if (key in stringMap) {
  457         result = stringMap[key];
  458       } else {
  459         ++this.@java.util.AbstractHashMap::size;
  460       }
  461       stringMap[key] = value;
  462       return result;
  463     }-*/;
  464   
  465     /**
  466      * Removes the pair whose key is Object equal to <code>key</code> from
  467      * <code>hashCodeMap</code>, provided that <code>key</code>'s hash code
  468      * is <code>hashCode</code>. Returns the value that was associated with the
  469      * removed key, or null if no such key existed.
  470      */
  471     private native V removeHashValue(Object key, int hashCode) /*-{
  472       var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
  473       if (array) {
  474         for (var i = 0, c = array.length; i < c; ++i) {
  475           var entry = array[i];
  476           var entryKey = entry.@java.util.Map$Entry::getKey()();
  477           if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
  478             if (array.length == 1) {
  479               // remove the whole array
  480               delete this.@java.util.AbstractHashMap::hashCodeMap[hashCode];
  481             } else {
  482               // splice out the entry we're removing
  483               array.splice(i, 1);
  484             }
  485             --this.@java.util.AbstractHashMap::size;
  486             return entry.@java.util.Map$Entry::getValue()();
  487           }
  488         }
  489       }
  490       return null;
  491     }-*/;
  492   
  493     private V removeNullSlot() {
  494       V result = nullSlot;
  495       nullSlot = null;
  496       if (nullSlotLive) {
  497         nullSlotLive = false;
  498         --size;
  499       }
  500       return result;
  501     }
  502   
  503     /**
  504      * Removes the specified key from the stringMap and returns the value that was
  505      * previously there. Returns <code>null</code> if the specified key does not
  506      * exist.
  507      */
  508     private native V removeStringValue(String key) /*-{
  509       var result, stringMap = this.@java.util.AbstractHashMap::stringMap;
  510       key = ':' + key;
  511       if (key in stringMap) {
  512         result = stringMap[key];
  513         --this.@java.util.AbstractHashMap::size;
  514         delete stringMap[key];
  515       }
  516       return result;
  517     }-*/;
  518   }

Home » openjdk-7 » java » util » [javadoc | source]