1 /*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5 /*
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements. See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 */
21
22 package com.sun.org.apache.xerces.internal.util;
23
24
25 /**
26 * This class is an unsynchronized hash table primary used for String
27 * to Object mapping.
28 * <p>
29 * The hash code uses the same algorithm as SymbolTable class.
30 *
31 * @author Elena Litani
32 */
33 public class SymbolHash {
34
35 //
36 // Constants
37 //
38
39 /** Default table size. */
40 protected static final int TABLE_SIZE = 101;
41
42 /** Maximum hash collisions per bucket. */
43 protected static final int MAX_HASH_COLLISIONS = 40;
44
45 protected static final int MULTIPLIERS_SIZE = 1 << 5;
46 protected static final int MULTIPLIERS_MASK = MULTIPLIERS_SIZE - 1;
47
48 //
49 // Data
50 //
51
52 /** Actual table size **/
53 protected int fTableSize;
54
55 /** Buckets. */
56 protected Entry[] fBuckets;
57
58 /** Number of elements. */
59 protected int fNum = 0;
60
61 /**
62 * Array of randomly selected hash function multipliers or <code>null</code>
63 * if the default String.hashCode() function should be used.
64 */
65 protected int[] fHashMultipliers;
66
67 //
68 // Constructors
69 //
70
71 /** Constructs a key table with the default size. */
72 public SymbolHash() {
73 this(TABLE_SIZE);
74 }
75
76 /**
77 * Constructs a key table with a given size.
78 *
79 * @param size the size of the key table.
80 */
81 public SymbolHash(int size) {
82 fTableSize = size;
83 fBuckets = new Entry[fTableSize];
84 }
85
86 //
87 // Public methods
88 //
89
90 /**
91 * Adds the key/value mapping to the key table. If the key already exists,
92 * the previous value associated with this key is overwritten by the new
93 * value.
94 *
95 * @param key
96 * @param value
97 */
98 public void put(Object key, Object value) {
99
100 // search for identical key
101 int collisionCount = 0;
102 final int hash = hash(key);
103 int bucket = hash % fTableSize;
104 for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
105 if (key.equals(entry.key)) {
106 // replace old value
107 entry.value = value;
108 return;
109 }
110 ++collisionCount;
111 }
112
113 if (fNum >= fTableSize) {
114 // Rehash the table if the number of entries
115 // would exceed the number of buckets.
116 rehash();
117 bucket = hash % fTableSize;
118 }
119 else if (collisionCount >= MAX_HASH_COLLISIONS && key instanceof String) {
120 // Select a new hash function and rehash the table if
121 // MAX_HASH_COLLISIONS is exceeded.
122 rebalance();
123 bucket = hash(key) % fTableSize;
124 }
125
126 // create new entry
127 Entry entry = new Entry(key, value, fBuckets[bucket]);
128 fBuckets[bucket] = entry;
129 ++fNum;
130 }
131
132 /**
133 * Get the value associated with the given key.
134 *
135 * @param key
136 * @return the value associated with the given key.
137 */
138 public Object get(Object key) {
139 int bucket = hash(key) % fTableSize;
140 Entry entry = search(key, bucket);
141 if (entry != null) {
142 return entry.value;
143 }
144 return null;
145 }
146
147 /**
148 * Get the number of key/value pairs stored in this table.
149 *
150 * @return the number of key/value pairs stored in this table.
151 */
152 public int getLength() {
153 return fNum;
154 }
155
156 /**
157 * Add all values to the given array. The array must have enough entry.
158 *
159 * @param elements the array to store the elements
160 * @param from where to start store element in the array
161 * @return number of elements copied to the array
162 */
163 public int getValues(Object[] elements, int from) {
164 for (int i=0, j=0; i<fTableSize && j<fNum; i++) {
165 for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
166 elements[from+j] = entry.value;
167 j++;
168 }
169 }
170 return fNum;
171 }
172
173 /**
174 * Return key/value pairs of all entries in the map
175 */
176 public Object[] getEntries() {
177 Object[] entries = new Object[fNum << 1];
178 for (int i=0, j=0; i<fTableSize && j<fNum << 1; i++) {
179 for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
180 entries[j] = entry.key;
181 entries[++j] = entry.value;
182 j++;
183 }
184 }
185 return entries;
186 }
187
188 /**
189 * Make a clone of this object.
190 */
191 public SymbolHash makeClone() {
192 SymbolHash newTable = new SymbolHash(fTableSize);
193 newTable.fNum = fNum;
194 newTable.fHashMultipliers = fHashMultipliers != null ? (int[]) fHashMultipliers.clone() : null;
195 for (int i = 0; i < fTableSize; i++) {
196 if (fBuckets[i] != null) {
197 newTable.fBuckets[i] = fBuckets[i].makeClone();
198 }
199 }
200 return newTable;
201 }
202
203 /**
204 * Remove all key/value association. This tries to save a bit of GC'ing
205 * by at least keeping the fBuckets array around.
206 */
207 public void clear() {
208 for (int i=0; i<fTableSize; i++) {
209 fBuckets[i] = null;
210 }
211 fNum = 0;
212 fHashMultipliers = null;
213 } // clear(): void
214
215 protected Entry search(Object key, int bucket) {
216 // search for identical key
217 for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
218 if (key.equals(entry.key))
219 return entry;
220 }
221 return null;
222 }
223
224 /**
225 * Returns a hashcode value for the specified key.
226 *
227 * @param key The key to hash.
228 */
229 protected int hash(Object key) {
230 if (fHashMultipliers == null || !(key instanceof String)) {
231 return key.hashCode() & 0x7FFFFFFF;
232 }
233 return hash0((String) key);
234 } // hash(Object):int
235
236 private int hash0(String symbol) {
237 int code = 0;
238 final int length = symbol.length();
239 final int[] multipliers = fHashMultipliers;
240 for (int i = 0; i < length; ++i) {
241 code = code * multipliers[i & MULTIPLIERS_MASK] + symbol.charAt(i);
242 }
243 return code & 0x7FFFFFFF;
244 } // hash0(String):int
245
246 /**
247 * Increases the capacity of and internally reorganizes this
248 * SymbolHash, in order to accommodate and access its entries more
249 * efficiently. This method is called automatically when the
250 * number of keys in the SymbolHash exceeds its number of buckets.
251 */
252 protected void rehash() {
253 rehashCommon((fBuckets.length << 1) + 1);
254 }
255
256 /**
257 * Randomly selects a new hash function and reorganizes this SymbolHash
258 * in order to more evenly distribute its entries across the table. This
259 * method is called automatically when the number keys in one of the
260 * SymbolHash's buckets exceeds MAX_HASH_COLLISIONS.
261 */
262 protected void rebalance() {
263 if (fHashMultipliers == null) {
264 fHashMultipliers = new int[MULTIPLIERS_SIZE];
265 }
266 PrimeNumberSequenceGenerator.generateSequence(fHashMultipliers);
267 rehashCommon(fBuckets.length);
268 }
269
270 private void rehashCommon(final int newCapacity) {
271
272 final int oldCapacity = fBuckets.length;
273 final Entry[] oldTable = fBuckets;
274
275 final Entry[] newTable = new Entry[newCapacity];
276
277 fBuckets = newTable;
278 fTableSize = fBuckets.length;
279
280 for (int i = oldCapacity; i-- > 0;) {
281 for (Entry old = oldTable[i]; old != null; ) {
282 Entry e = old;
283 old = old.next;
284
285 int index = hash(e.key) % newCapacity;
286 e.next = newTable[index];
287 newTable[index] = e;
288 }
289 }
290 }
291
292 //
293 // Classes
294 //
295
296 /**
297 * This class is a key table entry. Each entry acts as a node
298 * in a linked list.
299 */
300 protected static final class Entry {
301 // key/value
302 public Object key;
303 public Object value;
304 /** The next entry. */
305 public Entry next;
306
307 public Entry() {
308 key = null;
309 value = null;
310 next = null;
311 }
312
313 public Entry(Object key, Object value, Entry next) {
314 this.key = key;
315 this.value = value;
316 this.next = next;
317 }
318
319 public Entry makeClone() {
320 Entry entry = new Entry();
321 entry.key = key;
322 entry.value = value;
323 if (next != null)
324 entry.next = next.makeClone();
325 return entry;
326 }
327 } // entry
328
329 } // class SymbolHash