1 /*
2 * Copyright (c) 2009, 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 com.sun.xml.internal.dtdparser;
27
28 import java.util.Enumeration;
29
30
31 // This could be replaced by Collections class unless we want
32 // to be able to run on JDK 1.1
33
34
35 /**
36 * This class implements a special purpose hashtable. It works like a
37 * normal <code>java.util.Hashtable</code> except that: <OL>
38 * <p/>
39 * <LI> Keys to "get" are strings which are known to be interned,
40 * so that "==" is used instead of "String.equals". (Interning
41 * could be document-relative instead of global.)
42 * <p/>
43 * <LI> It's not synchronized, since it's to be used only by
44 * one thread at a time.
45 * <p/>
46 * <LI> The keys () enumerator allocates no memory, with live
47 * updates to the data disallowed.
48 * <p/>
49 * <LI> It's got fewer bells and whistles: fixed threshold and
50 * load factor, no JDK 1.2 collection support, only keys can be
51 * enumerated, things can't be removed, simpler inheritance; more.
52 * <p/>
53 * </OL>
54 * <p/>
55 * <P> The overall result is that it's less expensive to use these in
56 * performance-critical locations, in terms both of CPU and memory,
57 * than <code>java.util.Hashtable</code> instances. In this package
58 * it makes a significant difference when normalizing attributes,
59 * which is done for each start-element construct.
60 *
61 * @version $Revision: 1.2 $
62 */
63 final class SimpleHashtable implements Enumeration {
64 // entries ...
65 private Entry table[];
66
67 // currently enumerated key
68 private Entry current = null;
69 private int currentBucket = 0;
70
71 private int count;
72 private int threshold;
73
74 private static final float loadFactor = 0.75f;
75
76
77 /**
78 * Constructs a new, empty hashtable with the specified initial
79 * capacity.
80 *
81 * @param initialCapacity the initial capacity of the hashtable.
82 */
83 public SimpleHashtable(int initialCapacity) {
84 if (initialCapacity < 0)
85 throw new IllegalArgumentException("Illegal Capacity: " +
86 initialCapacity);
87 if (initialCapacity == 0)
88 initialCapacity = 1;
89 table = new Entry[initialCapacity];
90 threshold = (int) (initialCapacity * loadFactor);
91 }
92
93 /**
94 * Constructs a new, empty hashtable with a default capacity.
95 */
96 public SimpleHashtable() {
97 this(11);
98 }
99
100 /**
101 */
102 public void clear() {
103 count = 0;
104 currentBucket = 0;
105 current = null;
106 for (int i = 0; i < table.length; i++)
107 table[i] = null;
108 }
109
110 /**
111 * Returns the number of keys in this hashtable.
112 *
113 * @return the number of keys in this hashtable.
114 */
115 public int size() {
116 return count;
117 }
118
119 /**
120 * Returns an enumeration of the keys in this hashtable.
121 *
122 * @return an enumeration of the keys in this hashtable.
123 * @see Enumeration
124 */
125 public Enumeration keys() {
126 currentBucket = 0;
127 current = null;
128 return this;
129 }
130
131 /**
132 * Used to view this as an enumeration; returns true if there
133 * are more keys to be enumerated.
134 */
135 public boolean hasMoreElements() {
136 if (current != null)
137 return true;
138 while (currentBucket < table.length) {
139 current = table[currentBucket++];
140 if (current != null)
141 return true;
142 }
143 return false;
144 }
145
146 /**
147 * Used to view this as an enumeration; returns the next key
148 * in the enumeration.
149 */
150 public Object nextElement() {
151 Object retval;
152
153 if (current == null)
154 throw new IllegalStateException();
155 retval = current.key;
156 current = current.next;
157 return retval;
158 }
159
160
161 /**
162 * Returns the value to which the specified key is mapped in this hashtable.
163 */
164 public Object get(String key) {
165 Entry tab[] = table;
166 int hash = key.hashCode();
167 int index = (hash & 0x7FFFFFFF) % tab.length;
168 for (Entry e = tab[index]; e != null; e = e.next) {
169 if ((e.hash == hash) && (e.key == key))
170 return e.value;
171 }
172 return null;
173 }
174
175 /**
176 * Returns the value to which the specified key is mapped in this
177 * hashtable ... the key isn't necessarily interned, though.
178 */
179 public Object getNonInterned(String key) {
180 Entry tab[] = table;
181 int hash = key.hashCode();
182 int index = (hash & 0x7FFFFFFF) % tab.length;
183 for (Entry e = tab[index]; e != null; e = e.next) {
184 if ((e.hash == hash) && e.key.equals(key))
185 return e.value;
186 }
187 return null;
188 }
189
190 /**
191 * Increases the capacity of and internally reorganizes this
192 * hashtable, in order to accommodate and access its entries more
193 * efficiently. This method is called automatically when the
194 * number of keys in the hashtable exceeds this hashtable's capacity
195 * and load factor.
196 */
197 private void rehash() {
198 int oldCapacity = table.length;
199 Entry oldMap[] = table;
200
201 int newCapacity = oldCapacity * 2 + 1;
202 Entry newMap[] = new Entry[newCapacity];
203
204 threshold = (int) (newCapacity * loadFactor);
205 table = newMap;
206
207 /*
208 System.out.println("rehash old=" + oldCapacity
209 + ", new=" + newCapacity
210 + ", thresh=" + threshold
211 + ", count=" + count);
212 */
213
214 for (int i = oldCapacity; i-- > 0;) {
215 for (Entry old = oldMap[i]; old != null;) {
216 Entry e = old;
217 old = old.next;
218
219 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
220 e.next = newMap[index];
221 newMap[index] = e;
222 }
223 }
224 }
225
226 /**
227 * Maps the specified <code>key</code> to the specified
228 * <code>value</code> in this hashtable. Neither the key nor the
229 * value can be <code>null</code>.
230 * <p/>
231 * <P>The value can be retrieved by calling the <code>get</code> method
232 * with a key that is equal to the original key.
233 */
234 public Object put(Object key, Object value) {
235 // Make sure the value is not null
236 if (value == null) {
237 throw new NullPointerException();
238 }
239
240 // Makes sure the key is not already in the hashtable.
241 Entry tab[] = table;
242 int hash = key.hashCode();
243 int index = (hash & 0x7FFFFFFF) % tab.length;
244 for (Entry e = tab[index]; e != null; e = e.next) {
245 // if ((e.hash == hash) && e.key.equals(key)) {
246 if ((e.hash == hash) && (e.key == key)) {
247 Object old = e.value;
248 e.value = value;
249 return old;
250 }
251 }
252
253 if (count >= threshold) {
254 // Rehash the table if the threshold is exceeded
255 rehash();
256
257 tab = table;
258 index = (hash & 0x7FFFFFFF) % tab.length;
259 }
260
261 // Creates the new entry.
262 Entry e = new Entry(hash, key, value, tab[index]);
263 tab[index] = e;
264 count++;
265 return null;
266 }
267
268
269 /**
270 * Hashtable collision list.
271 */
272 private static class Entry {
273 int hash;
274 Object key;
275 Object value;
276 Entry next;
277
278 protected Entry(int hash, Object key, Object value, Entry next) {
279 this.hash = hash;
280 this.key = key;
281 this.value = value;
282 this.next = next;
283 }
284 }
285 }