1 /* 2 * Copyright (c) 1998, 2011, 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 }