001: /*
002: * Copyright (c) 1998 Sun Microsystems, Inc. All Rights Reserved.
003: */
004:
005: package com.sun.xml.dtdparser;
006:
007: import java.util.Enumeration;
008:
009: // This could be replaced by Collections class unless we want
010: // to be able to run on JDK 1.1
011:
012: /**
013: * This class implements a special purpose hashtable. It works like a
014: * normal <code>java.util.Hashtable</code> except that: <OL>
015: * <p/>
016: * <LI> Keys to "get" are strings which are known to be interned,
017: * so that "==" is used instead of "String.equals". (Interning
018: * could be document-relative instead of global.)
019: * <p/>
020: * <LI> It's not synchronized, since it's to be used only by
021: * one thread at a time.
022: * <p/>
023: * <LI> The keys () enumerator allocates no memory, with live
024: * updates to the data disallowed.
025: * <p/>
026: * <LI> It's got fewer bells and whistles: fixed threshold and
027: * load factor, no JDK 1.2 collection support, only keys can be
028: * enumerated, things can't be removed, simpler inheritance; more.
029: * <p/>
030: * </OL>
031: * <p/>
032: * <P> The overall result is that it's less expensive to use these in
033: * performance-critical locations, in terms both of CPU and memory,
034: * than <code>java.util.Hashtable</code> instances. In this package
035: * it makes a significant difference when normalizing attributes,
036: * which is done for each start-element construct.
037: *
038: * @version $Revision: 1.1 $
039: */
040: final class SimpleHashtable implements Enumeration {
041: // entries ...
042: private Entry table[];
043:
044: // currently enumerated key
045: private Entry current = null;
046: private int currentBucket = 0;
047:
048: private int count;
049: private int threshold;
050:
051: private static final float loadFactor = 0.75f;
052:
053: /**
054: * Constructs a new, empty hashtable with the specified initial
055: * capacity.
056: *
057: * @param initialCapacity the initial capacity of the hashtable.
058: */
059: public SimpleHashtable(int initialCapacity) {
060: if (initialCapacity < 0)
061: throw new IllegalArgumentException("Illegal Capacity: "
062: + initialCapacity);
063: if (initialCapacity == 0)
064: initialCapacity = 1;
065: table = new Entry[initialCapacity];
066: threshold = (int) (initialCapacity * loadFactor);
067: }
068:
069: /**
070: * Constructs a new, empty hashtable with a default capacity.
071: */
072: public SimpleHashtable() {
073: this (11);
074: }
075:
076: /**
077: */
078: public void clear() {
079: count = 0;
080: currentBucket = 0;
081: current = null;
082: for (int i = 0; i < table.length; i++)
083: table[i] = null;
084: }
085:
086: /**
087: * Returns the number of keys in this hashtable.
088: *
089: * @return the number of keys in this hashtable.
090: */
091: public int size() {
092: return count;
093: }
094:
095: /**
096: * Returns an enumeration of the keys in this hashtable.
097: *
098: * @return an enumeration of the keys in this hashtable.
099: * @see Enumeration
100: */
101: public Enumeration keys() {
102: currentBucket = 0;
103: current = null;
104: return this ;
105: }
106:
107: /**
108: * Used to view this as an enumeration; returns true if there
109: * are more keys to be enumerated.
110: */
111: public boolean hasMoreElements() {
112: if (current != null)
113: return true;
114: while (currentBucket < table.length) {
115: current = table[currentBucket++];
116: if (current != null)
117: return true;
118: }
119: return false;
120: }
121:
122: /**
123: * Used to view this as an enumeration; returns the next key
124: * in the enumeration.
125: */
126: public Object nextElement() {
127: Object retval;
128:
129: if (current == null)
130: throw new IllegalStateException();
131: retval = current.key;
132: current = current.next;
133: return retval;
134: }
135:
136: /**
137: * Returns the value to which the specified key is mapped in this hashtable.
138: */
139: public Object get(String key) {
140: Entry tab[] = table;
141: int hash = key.hashCode();
142: int index = (hash & 0x7FFFFFFF) % tab.length;
143: for (Entry e = tab[index]; e != null; e = e.next) {
144: if ((e.hash == hash) && (e.key == key))
145: return e.value;
146: }
147: return null;
148: }
149:
150: /**
151: * Returns the value to which the specified key is mapped in this
152: * hashtable ... the key isn't necessarily interned, though.
153: */
154: public Object getNonInterned(String key) {
155: Entry tab[] = table;
156: int hash = key.hashCode();
157: int index = (hash & 0x7FFFFFFF) % tab.length;
158: for (Entry e = tab[index]; e != null; e = e.next) {
159: if ((e.hash == hash) && e.key.equals(key))
160: return e.value;
161: }
162: return null;
163: }
164:
165: /**
166: * Increases the capacity of and internally reorganizes this
167: * hashtable, in order to accommodate and access its entries more
168: * efficiently. This method is called automatically when the
169: * number of keys in the hashtable exceeds this hashtable's capacity
170: * and load factor.
171: */
172: private void rehash() {
173: int oldCapacity = table.length;
174: Entry oldMap[] = table;
175:
176: int newCapacity = oldCapacity * 2 + 1;
177: Entry newMap[] = new Entry[newCapacity];
178:
179: threshold = (int) (newCapacity * loadFactor);
180: table = newMap;
181:
182: /*
183: System.out.println("rehash old=" + oldCapacity
184: + ", new=" + newCapacity
185: + ", thresh=" + threshold
186: + ", count=" + count);
187: */
188:
189: for (int i = oldCapacity; i-- > 0;) {
190: for (Entry old = oldMap[i]; old != null;) {
191: Entry e = old;
192: old = old.next;
193:
194: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
195: e.next = newMap[index];
196: newMap[index] = e;
197: }
198: }
199: }
200:
201: /**
202: * Maps the specified <code>key</code> to the specified
203: * <code>value</code> in this hashtable. Neither the key nor the
204: * value can be <code>null</code>.
205: * <p/>
206: * <P>The value can be retrieved by calling the <code>get</code> method
207: * with a key that is equal to the original key.
208: */
209: public Object put(Object key, Object value) {
210: // Make sure the value is not null
211: if (value == null) {
212: throw new NullPointerException();
213: }
214:
215: // Makes sure the key is not already in the hashtable.
216: Entry tab[] = table;
217: int hash = key.hashCode();
218: int index = (hash & 0x7FFFFFFF) % tab.length;
219: for (Entry e = tab[index]; e != null; e = e.next) {
220: // if ((e.hash == hash) && e.key.equals(key)) {
221: if ((e.hash == hash) && (e.key == key)) {
222: Object old = e.value;
223: e.value = value;
224: return old;
225: }
226: }
227:
228: if (count >= threshold) {
229: // Rehash the table if the threshold is exceeded
230: rehash();
231:
232: tab = table;
233: index = (hash & 0x7FFFFFFF) % tab.length;
234: }
235:
236: // Creates the new entry.
237: Entry e = new Entry(hash, key, value, tab[index]);
238: tab[index] = e;
239: count++;
240: return null;
241: }
242:
243: /**
244: * Hashtable collision list.
245: */
246: private static class Entry {
247: int hash;
248: Object key;
249: Object value;
250: Entry next;
251:
252: protected Entry(int hash, Object key, Object value, Entry next) {
253: this.hash = hash;
254: this.key = key;
255: this.value = value;
256: this.next = next;
257: }
258: }
259: }
|