Save This Page
Home » openjdk-7 » sun » misc » [javadoc | source]
    1   /*
    2    * Copyright (c) 1995, 1996, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package sun.misc;
   27   
   28   import java.util.Dictionary;
   29   import java.util.Enumeration;
   30   import java.util.NoSuchElementException;
   31   
   32   /**
   33    * Caches the collision list.
   34    */
   35   class CacheEntry extends Ref {
   36       int hash;
   37       Object key;
   38       CacheEntry next;
   39       public Object reconstitute() {
   40           return null;
   41       }
   42   }
   43   
   44   /**
   45    * The Cache class. Maps keys to values. Any object can be used as
   46    * a key and/or value.  This is very similar to the Hashtable
   47    * class, except that after putting an object into the Cache,
   48    * it is not guaranteed that a subsequent get will return it.
   49    * The Cache will automatically remove entries if memory is
   50    * getting tight and if the entry is not referenced from outside
   51    * the Cache.<p>
   52    *
   53    * To sucessfully store and retrieve objects from a hash table the
   54    * object used as the key must implement the hashCode() and equals()
   55    * methods.<p>
   56    *
   57    * This example creates a Cache of numbers. It uses the names of
   58    * the numbers as keys:
   59    * <pre>
   60    *      Cache numbers = new Cache();
   61    *      numbers.put("one", new Integer(1));
   62    *      numbers.put("two", new Integer(1));
   63    *      numbers.put("three", new Integer(1));
   64    * </pre>
   65    * To retrieve a number use:
   66    * <pre>
   67    *      Integer n = (Integer)numbers.get("two");
   68    *      if (n != null) {
   69    *          System.out.println("two = " + n);
   70    *      }
   71    * </pre>
   72    *
   73    * @see java.lang.Object#hashCode
   74    * @see java.lang.Object#equals
   75    * @see sun.misc.Ref
   76    */
   77   public
   78   class Cache extends Dictionary {
   79       /**
   80        * The hash table data.
   81        */
   82       private CacheEntry table[];
   83   
   84       /**
   85        * The total number of entries in the hash table.
   86        */
   87       private int count;
   88   
   89       /**
   90        * Rehashes the table when count exceeds this threshold.
   91        */
   92       private int threshold;
   93   
   94       /**
   95        * The load factor for the hashtable.
   96        */
   97       private float loadFactor;
   98   
   99       private void init(int initialCapacity, float loadFactor) {
  100           if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
  101               throw new IllegalArgumentException();
  102           }
  103           this.loadFactor = loadFactor;
  104           table = new CacheEntry[initialCapacity];
  105           threshold = (int) (initialCapacity * loadFactor);
  106       }
  107   
  108       /**
  109        * Constructs a new, empty Cache with the specified initial
  110        * capacity and the specified load factor.
  111        * @param initialCapacity the initial number of buckets
  112        * @param loadFactor a number between 0.0 and 1.0, it defines
  113        *          the threshold for rehashing the Cache into
  114        *          a bigger one.
  115        * @exception IllegalArgumentException If the initial capacity
  116        * is less than or equal to zero.
  117        * @exception IllegalArgumentException If the load factor is
  118        * less than or equal to zero.
  119        */
  120       public Cache (int initialCapacity, float loadFactor) {
  121           init(initialCapacity, loadFactor);
  122       }
  123   
  124       /**
  125        * Constructs a new, empty Cache with the specified initial
  126        * capacity.
  127        * @param initialCapacity the initial number of buckets
  128        */
  129       public Cache (int initialCapacity) {
  130           init(initialCapacity, 0.75f);
  131       }
  132   
  133       /**
  134        * Constructs a new, empty Cache. A default capacity and load factor
  135        * is used. Note that the Cache will automatically grow when it gets
  136        * full.
  137        */
  138       public Cache () {
  139           try {
  140               init(101, 0.75f);
  141           } catch (IllegalArgumentException ex) {
  142               // This should never happen
  143               throw new Error("panic");
  144           }
  145       }
  146   
  147       /**
  148        * Returns the number of elements contained within the Cache.
  149        */
  150       public int size() {
  151           return count;
  152       }
  153   
  154       /**
  155        * Returns true if the Cache contains no elements.
  156        */
  157       public boolean isEmpty() {
  158           return count == 0;
  159       }
  160   
  161       /**
  162        * Returns an enumeration of the Cache's keys.
  163        * @see Cache#elements
  164        * @see Enumeration
  165        */
  166       public synchronized Enumeration keys() {
  167           return new CacheEnumerator(table, true);
  168       }
  169   
  170       /**
  171        * Returns an enumeration of the elements. Use the Enumeration methods
  172        * on the returned object to fetch the elements sequentially.
  173        * @see Cache#keys
  174        * @see Enumeration
  175        */
  176       public synchronized Enumeration elements() {
  177           return new CacheEnumerator(table, false);
  178       }
  179   
  180       /**
  181        * Gets the object associated with the specified key in the Cache.
  182        * @param key the key in the hash table
  183        * @returns the element for the key or null if the key
  184        *          is not defined in the hash table.
  185        * @see Cache#put
  186        */
  187       public synchronized Object get(Object key) {
  188           CacheEntry tab[] = table;
  189           int hash = key.hashCode();
  190           int index = (hash & 0x7FFFFFFF) % tab.length;
  191           for (CacheEntry e = tab[index]; e != null; e = e.next) {
  192               if ((e.hash == hash) && e.key.equals(key)) {
  193                   return e.check();
  194               }
  195           }
  196           return null;
  197       }
  198   
  199       /**
  200        * Rehashes the contents of the table into a bigger table.
  201        * This is method is called automatically when the Cache's
  202        * size exceeds the threshold.
  203        */
  204       protected void rehash() {
  205           int oldCapacity = table.length;
  206           CacheEntry oldTable[] = table;
  207   
  208           int newCapacity = oldCapacity * 2 + 1;
  209           CacheEntry newTable[] = new CacheEntry[newCapacity];
  210   
  211           threshold = (int) (newCapacity * loadFactor);
  212           table = newTable;
  213   
  214           // System.out.println("rehash old=" + oldCapacity + ", new=" +
  215           // newCapacity + ", thresh=" + threshold + ", count=" + count);
  216   
  217           for (int i = oldCapacity; i-- > 0;) {
  218               for (CacheEntry old = oldTable[i]; old != null;) {
  219                   CacheEntry e = old;
  220                   old = old.next;
  221                   if (e.check() != null) {
  222                       int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  223                       e.next = newTable[index];
  224                       newTable[index] = e;
  225                   } else
  226                       count--;    /* remove entries that have disappeared */
  227               }
  228           }
  229       }
  230   
  231       /**
  232        * Puts the specified element into the Cache, using the specified
  233        * key.  The element may be retrieved by doing a get() with the same
  234        * key.  The key and the element cannot be null.
  235        * @param key the specified hashtable key
  236        * @param value the specified element
  237        * @return the old value of the key, or null if it did not have one.
  238        * @exception NullPointerException If the value of the specified
  239        * element is null.
  240        * @see Cache#get
  241        */
  242       public synchronized Object put(Object key, Object value) {
  243           // Make sure the value is not null
  244           if (value == null) {
  245               throw new NullPointerException();
  246           }
  247           // Makes sure the key is not already in the cache.
  248           CacheEntry tab[] = table;
  249           int hash = key.hashCode();
  250           int index = (hash & 0x7FFFFFFF) % tab.length;
  251           CacheEntry ne = null;
  252           for (CacheEntry e = tab[index]; e != null; e = e.next) {
  253               if ((e.hash == hash) && e.key.equals(key)) {
  254                   Object old = e.check();
  255                   e.setThing(value);
  256                   return old;
  257               } else if (e.check() == null)
  258                   ne = e;         /* reuse old flushed value */
  259           }
  260   
  261           if (count >= threshold) {
  262               // Rehash the table if the threshold is exceeded
  263               rehash();
  264               return put(key, value);
  265           }
  266           // Creates the new entry.
  267           if (ne == null) {
  268               ne = new CacheEntry ();
  269               ne.next = tab[index];
  270               tab[index] = ne;
  271               count++;
  272           }
  273           ne.hash = hash;
  274           ne.key = key;
  275           ne.setThing(value);
  276           return null;
  277       }
  278   
  279       /**
  280        * Removes the element corresponding to the key. Does nothing if the
  281        * key is not present.
  282        * @param key the key that needs to be removed
  283        * @return the value of key, or null if the key was not found.
  284        */
  285       public synchronized Object remove(Object key) {
  286           CacheEntry tab[] = table;
  287           int hash = key.hashCode();
  288           int index = (hash & 0x7FFFFFFF) % tab.length;
  289           for (CacheEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
  290               if ((e.hash == hash) && e.key.equals(key)) {
  291                   if (prev != null) {
  292                       prev.next = e.next;
  293                   } else {
  294                       tab[index] = e.next;
  295                   }
  296                   count--;
  297                   return e.check();
  298               }
  299           }
  300           return null;
  301       }
  302   }
  303   
  304   /**
  305    * A Cache enumerator class.  This class should remain opaque
  306    * to the client. It will use the Enumeration interface.
  307    */
  308   class CacheEnumerator implements Enumeration {
  309       boolean keys;
  310       int index;
  311       CacheEntry table[];
  312       CacheEntry entry;
  313   
  314       CacheEnumerator (CacheEntry table[], boolean keys) {
  315           this.table = table;
  316           this.keys = keys;
  317           this.index = table.length;
  318       }
  319   
  320       public boolean hasMoreElements() {
  321           while (index >= 0) {
  322               while (entry != null)
  323                   if (entry.check() != null)
  324                       return true;
  325                   else
  326                       entry = entry.next;
  327               while (--index >= 0 && (entry = table[index]) == null) ;
  328           }
  329           return false;
  330       }
  331   
  332       public Object nextElement() {
  333           while (index >= 0) {
  334               if (entry == null)
  335                   while (--index >= 0 && (entry = table[index]) == null) ;
  336               if (entry != null) {
  337                   CacheEntry e = entry;
  338                   entry = e.next;
  339                   if (e.check() != null)
  340                       return keys ? e.key : e.check();
  341               }
  342           }
  343           throw new NoSuchElementException("CacheEnumerator");
  344       }
  345   
  346   }

Save This Page
Home » openjdk-7 » sun » misc » [javadoc | source]