ohair@286: /*
mkos@397:  * Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved.
ohair@286:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
ohair@286:  *
ohair@286:  * This code is free software; you can redistribute it and/or modify it
ohair@286:  * under the terms of the GNU General Public License version 2 only, as
ohair@286:  * published by the Free Software Foundation.  Oracle designates this
ohair@286:  * particular file as subject to the "Classpath" exception as provided
ohair@286:  * by Oracle in the LICENSE file that accompanied this code.
ohair@286:  *
ohair@286:  * This code is distributed in the hope that it will be useful, but WITHOUT
ohair@286:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
ohair@286:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
ohair@286:  * version 2 for more details (a copy is included in the LICENSE file that
ohair@286:  * accompanied this code).
ohair@286:  *
ohair@286:  * You should have received a copy of the GNU General Public License version
ohair@286:  * 2 along with this work; if not, write to the Free Software Foundation,
ohair@286:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
ohair@286:  *
ohair@286:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
ohair@286:  * or visit www.oracle.com if you need additional information or have any
ohair@286:  * questions.
ohair@286:  */
ohair@286: 
ohair@286: package com.sun.xml.internal.dtdparser;
ohair@286: 
ohair@286: import java.util.Enumeration;
ohair@286: 
ohair@286: 
ohair@286: // This could be replaced by Collections class unless we want
ohair@286: // to be able to run on JDK 1.1
ohair@286: 
ohair@286: 
ohair@286: /**
ohair@286:  * This class implements a special purpose hashtable.  It works like a
ohair@286:  * normal <code>java.util.Hashtable</code> except that: <OL>
ohair@286:  * <p/>
ohair@286:  * <LI> Keys to "get" are strings which are known to be interned,
ohair@286:  * so that "==" is used instead of "String.equals".  (Interning
ohair@286:  * could be document-relative instead of global.)
ohair@286:  * <p/>
ohair@286:  * <LI> It's not synchronized, since it's to be used only by
ohair@286:  * one thread at a time.
ohair@286:  * <p/>
ohair@286:  * <LI> The keys () enumerator allocates no memory, with live
ohair@286:  * updates to the data disallowed.
ohair@286:  * <p/>
ohair@286:  * <LI> It's got fewer bells and whistles:  fixed threshold and
ohair@286:  * load factor, no JDK 1.2 collection support, only keys can be
ohair@286:  * enumerated, things can't be removed, simpler inheritance; more.
ohair@286:  * <p/>
ohair@286:  * </OL>
ohair@286:  * <p/>
ohair@286:  * <P> The overall result is that it's less expensive to use these in
ohair@286:  * performance-critical locations, in terms both of CPU and memory,
ohair@286:  * than <code>java.util.Hashtable</code> instances.  In this package
ohair@286:  * it makes a significant difference when normalizing attributes,
ohair@286:  * which is done for each start-element construct.
ohair@286:  *
ohair@286:  * @version $Revision: 1.2 $
ohair@286:  */
ohair@286: final class SimpleHashtable implements Enumeration {
ohair@286:     // entries ...
ohair@286:     private Entry table[];
ohair@286: 
ohair@286:     // currently enumerated key
ohair@286:     private Entry current = null;
ohair@286:     private int currentBucket = 0;
ohair@286: 
ohair@286:     private int count;
ohair@286:     private int threshold;
ohair@286: 
ohair@286:     private static final float loadFactor = 0.75f;
ohair@286: 
ohair@286: 
ohair@286:     /**
ohair@286:      * Constructs a new, empty hashtable with the specified initial
ohair@286:      * capacity.
ohair@286:      *
ohair@286:      * @param initialCapacity the initial capacity of the hashtable.
ohair@286:      */
ohair@286:     public SimpleHashtable(int initialCapacity) {
ohair@286:         if (initialCapacity < 0)
ohair@286:             throw new IllegalArgumentException("Illegal Capacity: " +
ohair@286:                     initialCapacity);
ohair@286:         if (initialCapacity == 0)
ohair@286:             initialCapacity = 1;
ohair@286:         table = new Entry[initialCapacity];
ohair@286:         threshold = (int) (initialCapacity * loadFactor);
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Constructs a new, empty hashtable with a default capacity.
ohair@286:      */
ohair@286:     public SimpleHashtable() {
ohair@286:         this(11);
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      */
ohair@286:     public void clear() {
ohair@286:         count = 0;
ohair@286:         currentBucket = 0;
ohair@286:         current = null;
ohair@286:         for (int i = 0; i < table.length; i++)
ohair@286:             table[i] = null;
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Returns the number of keys in this hashtable.
ohair@286:      *
ohair@286:      * @return the number of keys in this hashtable.
ohair@286:      */
ohair@286:     public int size() {
ohair@286:         return count;
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Returns an enumeration of the keys in this hashtable.
ohair@286:      *
ohair@286:      * @return an enumeration of the keys in this hashtable.
ohair@286:      * @see Enumeration
ohair@286:      */
ohair@286:     public Enumeration keys() {
ohair@286:         currentBucket = 0;
ohair@286:         current = null;
ohair@286:         return this;
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Used to view this as an enumeration; returns true if there
ohair@286:      * are more keys to be enumerated.
ohair@286:      */
ohair@286:     public boolean hasMoreElements() {
ohair@286:         if (current != null)
ohair@286:             return true;
ohair@286:         while (currentBucket < table.length) {
ohair@286:             current = table[currentBucket++];
ohair@286:             if (current != null)
ohair@286:                 return true;
ohair@286:         }
ohair@286:         return false;
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Used to view this as an enumeration; returns the next key
ohair@286:      * in the enumeration.
ohair@286:      */
ohair@286:     public Object nextElement() {
ohair@286:         Object retval;
ohair@286: 
ohair@286:         if (current == null)
ohair@286:             throw new IllegalStateException();
ohair@286:         retval = current.key;
ohair@286:         current = current.next;
ohair@286:         return retval;
ohair@286:     }
ohair@286: 
ohair@286: 
ohair@286:     /**
ohair@286:      * Returns the value to which the specified key is mapped in this hashtable.
ohair@286:      */
ohair@286:     public Object get(String key) {
ohair@286:         Entry tab[] = table;
ohair@286:         int hash = key.hashCode();
ohair@286:         int index = (hash & 0x7FFFFFFF) % tab.length;
ohair@286:         for (Entry e = tab[index]; e != null; e = e.next) {
ohair@286:             if ((e.hash == hash) && (e.key == key))
ohair@286:                 return e.value;
ohair@286:         }
ohair@286:         return null;
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Returns the value to which the specified key is mapped in this
ohair@286:      * hashtable ... the key isn't necessarily interned, though.
ohair@286:      */
ohair@286:     public Object getNonInterned(String key) {
ohair@286:         Entry tab[] = table;
ohair@286:         int hash = key.hashCode();
ohair@286:         int index = (hash & 0x7FFFFFFF) % tab.length;
ohair@286:         for (Entry e = tab[index]; e != null; e = e.next) {
ohair@286:             if ((e.hash == hash) && e.key.equals(key))
ohair@286:                 return e.value;
ohair@286:         }
ohair@286:         return null;
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Increases the capacity of and internally reorganizes this
ohair@286:      * hashtable, in order to accommodate and access its entries more
ohair@286:      * efficiently.  This method is called automatically when the
ohair@286:      * number of keys in the hashtable exceeds this hashtable's capacity
ohair@286:      * and load factor.
ohair@286:      */
ohair@286:     private void rehash() {
ohair@286:         int oldCapacity = table.length;
ohair@286:         Entry oldMap[] = table;
ohair@286: 
ohair@286:         int newCapacity = oldCapacity * 2 + 1;
ohair@286:         Entry newMap[] = new Entry[newCapacity];
ohair@286: 
ohair@286:         threshold = (int) (newCapacity * loadFactor);
ohair@286:         table = newMap;
ohair@286: 
ohair@286:         /*
ohair@286:         System.out.println("rehash old=" + oldCapacity
ohair@286:             + ", new=" + newCapacity
ohair@286:             + ", thresh=" + threshold
ohair@286:             + ", count=" + count);
ohair@286:         */
ohair@286: 
ohair@286:         for (int i = oldCapacity; i-- > 0;) {
ohair@286:             for (Entry old = oldMap[i]; old != null;) {
ohair@286:                 Entry e = old;
ohair@286:                 old = old.next;
ohair@286: 
ohair@286:                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
ohair@286:                 e.next = newMap[index];
ohair@286:                 newMap[index] = e;
ohair@286:             }
ohair@286:         }
ohair@286:     }
ohair@286: 
ohair@286:     /**
ohair@286:      * Maps the specified <code>key</code> to the specified
ohair@286:      * <code>value</code> in this hashtable. Neither the key nor the
ohair@286:      * value can be <code>null</code>.
ohair@286:      * <p/>
ohair@286:      * <P>The value can be retrieved by calling the <code>get</code> method
ohair@286:      * with a key that is equal to the original key.
ohair@286:      */
ohair@286:     public Object put(Object key, Object value) {
ohair@286:         // Make sure the value is not null
ohair@286:         if (value == null) {
ohair@286:             throw new NullPointerException();
ohair@286:         }
ohair@286: 
ohair@286:         // Makes sure the key is not already in the hashtable.
ohair@286:         Entry tab[] = table;
ohair@286:         int hash = key.hashCode();
ohair@286:         int index = (hash & 0x7FFFFFFF) % tab.length;
ohair@286:         for (Entry e = tab[index]; e != null; e = e.next) {
ohair@286:             // if ((e.hash == hash) && e.key.equals(key)) {
ohair@286:             if ((e.hash == hash) && (e.key == key)) {
ohair@286:                 Object old = e.value;
ohair@286:                 e.value = value;
ohair@286:                 return old;
ohair@286:             }
ohair@286:         }
ohair@286: 
ohair@286:         if (count >= threshold) {
ohair@286:             // Rehash the table if the threshold is exceeded
ohair@286:             rehash();
ohair@286: 
ohair@286:             tab = table;
ohair@286:             index = (hash & 0x7FFFFFFF) % tab.length;
ohair@286:         }
ohair@286: 
ohair@286:         // Creates the new entry.
ohair@286:         Entry e = new Entry(hash, key, value, tab[index]);
ohair@286:         tab[index] = e;
ohair@286:         count++;
ohair@286:         return null;
ohair@286:     }
ohair@286: 
ohair@286: 
ohair@286:     /**
ohair@286:      * Hashtable collision list.
ohair@286:      */
ohair@286:     private static class Entry {
ohair@286:         int hash;
ohair@286:         Object key;
ohair@286:         Object value;
ohair@286:         Entry next;
ohair@286: 
ohair@286:         protected Entry(int hash, Object key, Object value, Entry next) {
ohair@286:             this.hash = hash;
ohair@286:             this.key = key;
ohair@286:             this.value = value;
ohair@286:             this.next = next;
ohair@286:         }
ohair@286:     }
ohair@286: }