1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/jaxws_classes/com/sun/xml/internal/dtdparser/SimpleHashtable.java Tue Mar 06 16:09:35 2012 -0800
1.3 @@ -0,0 +1,285 @@
1.4 +/*
1.5 + * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package com.sun.xml.internal.dtdparser;
1.30 +
1.31 +import java.util.Enumeration;
1.32 +
1.33 +
1.34 +// This could be replaced by Collections class unless we want
1.35 +// to be able to run on JDK 1.1
1.36 +
1.37 +
1.38 +/**
1.39 + * This class implements a special purpose hashtable. It works like a
1.40 + * normal <code>java.util.Hashtable</code> except that: <OL>
1.41 + * <p/>
1.42 + * <LI> Keys to "get" are strings which are known to be interned,
1.43 + * so that "==" is used instead of "String.equals". (Interning
1.44 + * could be document-relative instead of global.)
1.45 + * <p/>
1.46 + * <LI> It's not synchronized, since it's to be used only by
1.47 + * one thread at a time.
1.48 + * <p/>
1.49 + * <LI> The keys () enumerator allocates no memory, with live
1.50 + * updates to the data disallowed.
1.51 + * <p/>
1.52 + * <LI> It's got fewer bells and whistles: fixed threshold and
1.53 + * load factor, no JDK 1.2 collection support, only keys can be
1.54 + * enumerated, things can't be removed, simpler inheritance; more.
1.55 + * <p/>
1.56 + * </OL>
1.57 + * <p/>
1.58 + * <P> The overall result is that it's less expensive to use these in
1.59 + * performance-critical locations, in terms both of CPU and memory,
1.60 + * than <code>java.util.Hashtable</code> instances. In this package
1.61 + * it makes a significant difference when normalizing attributes,
1.62 + * which is done for each start-element construct.
1.63 + *
1.64 + * @version $Revision: 1.2 $
1.65 + */
1.66 +final class SimpleHashtable implements Enumeration {
1.67 + // entries ...
1.68 + private Entry table[];
1.69 +
1.70 + // currently enumerated key
1.71 + private Entry current = null;
1.72 + private int currentBucket = 0;
1.73 +
1.74 + private int count;
1.75 + private int threshold;
1.76 +
1.77 + private static final float loadFactor = 0.75f;
1.78 +
1.79 +
1.80 + /**
1.81 + * Constructs a new, empty hashtable with the specified initial
1.82 + * capacity.
1.83 + *
1.84 + * @param initialCapacity the initial capacity of the hashtable.
1.85 + */
1.86 + public SimpleHashtable(int initialCapacity) {
1.87 + if (initialCapacity < 0)
1.88 + throw new IllegalArgumentException("Illegal Capacity: " +
1.89 + initialCapacity);
1.90 + if (initialCapacity == 0)
1.91 + initialCapacity = 1;
1.92 + table = new Entry[initialCapacity];
1.93 + threshold = (int) (initialCapacity * loadFactor);
1.94 + }
1.95 +
1.96 + /**
1.97 + * Constructs a new, empty hashtable with a default capacity.
1.98 + */
1.99 + public SimpleHashtable() {
1.100 + this(11);
1.101 + }
1.102 +
1.103 + /**
1.104 + */
1.105 + public void clear() {
1.106 + count = 0;
1.107 + currentBucket = 0;
1.108 + current = null;
1.109 + for (int i = 0; i < table.length; i++)
1.110 + table[i] = null;
1.111 + }
1.112 +
1.113 + /**
1.114 + * Returns the number of keys in this hashtable.
1.115 + *
1.116 + * @return the number of keys in this hashtable.
1.117 + */
1.118 + public int size() {
1.119 + return count;
1.120 + }
1.121 +
1.122 + /**
1.123 + * Returns an enumeration of the keys in this hashtable.
1.124 + *
1.125 + * @return an enumeration of the keys in this hashtable.
1.126 + * @see Enumeration
1.127 + */
1.128 + public Enumeration keys() {
1.129 + currentBucket = 0;
1.130 + current = null;
1.131 + return this;
1.132 + }
1.133 +
1.134 + /**
1.135 + * Used to view this as an enumeration; returns true if there
1.136 + * are more keys to be enumerated.
1.137 + */
1.138 + public boolean hasMoreElements() {
1.139 + if (current != null)
1.140 + return true;
1.141 + while (currentBucket < table.length) {
1.142 + current = table[currentBucket++];
1.143 + if (current != null)
1.144 + return true;
1.145 + }
1.146 + return false;
1.147 + }
1.148 +
1.149 + /**
1.150 + * Used to view this as an enumeration; returns the next key
1.151 + * in the enumeration.
1.152 + */
1.153 + public Object nextElement() {
1.154 + Object retval;
1.155 +
1.156 + if (current == null)
1.157 + throw new IllegalStateException();
1.158 + retval = current.key;
1.159 + current = current.next;
1.160 + return retval;
1.161 + }
1.162 +
1.163 +
1.164 + /**
1.165 + * Returns the value to which the specified key is mapped in this hashtable.
1.166 + */
1.167 + public Object get(String key) {
1.168 + Entry tab[] = table;
1.169 + int hash = key.hashCode();
1.170 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.171 + for (Entry e = tab[index]; e != null; e = e.next) {
1.172 + if ((e.hash == hash) && (e.key == key))
1.173 + return e.value;
1.174 + }
1.175 + return null;
1.176 + }
1.177 +
1.178 + /**
1.179 + * Returns the value to which the specified key is mapped in this
1.180 + * hashtable ... the key isn't necessarily interned, though.
1.181 + */
1.182 + public Object getNonInterned(String key) {
1.183 + Entry tab[] = table;
1.184 + int hash = key.hashCode();
1.185 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.186 + for (Entry e = tab[index]; e != null; e = e.next) {
1.187 + if ((e.hash == hash) && e.key.equals(key))
1.188 + return e.value;
1.189 + }
1.190 + return null;
1.191 + }
1.192 +
1.193 + /**
1.194 + * Increases the capacity of and internally reorganizes this
1.195 + * hashtable, in order to accommodate and access its entries more
1.196 + * efficiently. This method is called automatically when the
1.197 + * number of keys in the hashtable exceeds this hashtable's capacity
1.198 + * and load factor.
1.199 + */
1.200 + private void rehash() {
1.201 + int oldCapacity = table.length;
1.202 + Entry oldMap[] = table;
1.203 +
1.204 + int newCapacity = oldCapacity * 2 + 1;
1.205 + Entry newMap[] = new Entry[newCapacity];
1.206 +
1.207 + threshold = (int) (newCapacity * loadFactor);
1.208 + table = newMap;
1.209 +
1.210 + /*
1.211 + System.out.println("rehash old=" + oldCapacity
1.212 + + ", new=" + newCapacity
1.213 + + ", thresh=" + threshold
1.214 + + ", count=" + count);
1.215 + */
1.216 +
1.217 + for (int i = oldCapacity; i-- > 0;) {
1.218 + for (Entry old = oldMap[i]; old != null;) {
1.219 + Entry e = old;
1.220 + old = old.next;
1.221 +
1.222 + int index = (e.hash & 0x7FFFFFFF) % newCapacity;
1.223 + e.next = newMap[index];
1.224 + newMap[index] = e;
1.225 + }
1.226 + }
1.227 + }
1.228 +
1.229 + /**
1.230 + * Maps the specified <code>key</code> to the specified
1.231 + * <code>value</code> in this hashtable. Neither the key nor the
1.232 + * value can be <code>null</code>.
1.233 + * <p/>
1.234 + * <P>The value can be retrieved by calling the <code>get</code> method
1.235 + * with a key that is equal to the original key.
1.236 + */
1.237 + public Object put(Object key, Object value) {
1.238 + // Make sure the value is not null
1.239 + if (value == null) {
1.240 + throw new NullPointerException();
1.241 + }
1.242 +
1.243 + // Makes sure the key is not already in the hashtable.
1.244 + Entry tab[] = table;
1.245 + int hash = key.hashCode();
1.246 + int index = (hash & 0x7FFFFFFF) % tab.length;
1.247 + for (Entry e = tab[index]; e != null; e = e.next) {
1.248 + // if ((e.hash == hash) && e.key.equals(key)) {
1.249 + if ((e.hash == hash) && (e.key == key)) {
1.250 + Object old = e.value;
1.251 + e.value = value;
1.252 + return old;
1.253 + }
1.254 + }
1.255 +
1.256 + if (count >= threshold) {
1.257 + // Rehash the table if the threshold is exceeded
1.258 + rehash();
1.259 +
1.260 + tab = table;
1.261 + index = (hash & 0x7FFFFFFF) % tab.length;
1.262 + }
1.263 +
1.264 + // Creates the new entry.
1.265 + Entry e = new Entry(hash, key, value, tab[index]);
1.266 + tab[index] = e;
1.267 + count++;
1.268 + return null;
1.269 + }
1.270 +
1.271 +
1.272 + /**
1.273 + * Hashtable collision list.
1.274 + */
1.275 + private static class Entry {
1.276 + int hash;
1.277 + Object key;
1.278 + Object value;
1.279 + Entry next;
1.280 +
1.281 + protected Entry(int hash, Object key, Object value, Entry next) {
1.282 + this.hash = hash;
1.283 + this.key = key;
1.284 + this.value = value;
1.285 + this.next = next;
1.286 + }
1.287 + }
1.288 +}
