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