1 /*

     2  * Copyright 1995-1996 Sun Microsystems, Inc.  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.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any 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 }