1 /*
2 * Copyright (c) 1999, 2004, 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 /*
27 * Licensed Materials - Property of IBM
28 * RMI-IIOP v1.0
29 * Copyright IBM Corp. 1998 1999 All Rights Reserved
30 *
31 */
32
33 package com.sun.corba.se.impl.util;
34
35 import java.util.Dictionary;
36 import java.util.Enumeration;
37 import java.util.NoSuchElementException;
38
39 /**
40 * IdentityHashtable is a modified copy of the 1.1.6 Hashtable class which
41 * does not rely on the hashCode() and equals() methods of the key or value;
42 * instead, it uses the System.identityHashcode() method and pointer comparison.
43 * In addition, all synchronization has been removed.
44 */
45 public final class IdentityHashtable extends Dictionary {
46 /**
47 * The hash table data.
48 */
49 private transient IdentityHashtableEntry table[];
50
51 /**
52 * The total number of entries in the hash table.
53 */
54 private transient int count;
55
56 /**
57 * Rehashes the table when count exceeds this threshold.
58 */
59 private int threshold;
60
61 /**
62 * The load factor for the hashtable.
63 */
64 private float loadFactor;
65
66 /**
67 * Constructs a new, empty hashtable with the specified initial
68 * capacity and the specified load factor.
69 *
70 * @param initialCapacity the initial capacity of the hashtable.
71 * @param loadFactor a number between 0.0 and 1.0.
72 * @exception IllegalArgumentException if the initial capacity is less
73 * than or equal to zero, or if the load factor is less than
74 * or equal to zero.
75 * @since 1.0
76 */
77 public IdentityHashtable(int initialCapacity, float loadFactor) {
78 if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
79 throw new IllegalArgumentException();
80 }
81 this.loadFactor = loadFactor;
82 table = new IdentityHashtableEntry[initialCapacity];
83 threshold = (int)(initialCapacity * loadFactor);
84 }
85
86 /**
87 * Constructs a new, empty hashtable with the specified initial capacity
88 * and default load factor.
89 *
90 * @param initialCapacity the initial capacity of the hashtable.
91 * @since 1.0
92 */
93 public IdentityHashtable(int initialCapacity) {
94 this(initialCapacity, 0.75f);
95 }
96
97 /**
98 * Constructs a new, empty hashtable with a default capacity and load
99 * factor.
100 *
101 * @since 1.0
102 */
103 public IdentityHashtable() {
104 this(101, 0.75f);
105 }
106
107 /**
108 * Returns the number of keys in this hashtable.
109 *
110 * @return the number of keys in this hashtable.
111 * @since 1.0
112 */
113 public int size() {
114 return count;
115 }
116
117 /**
118 * Tests if this hashtable maps no keys to values.
119 *
120 * @return <code>true</code> if this hashtable maps no keys to values;
121 * <code>false</code> otherwise.
122 * @since 1.0
123 */
124 public boolean isEmpty() {
125 return count == 0;
126 }
127
128 /**
129 * Returns an enumeration of the keys in this hashtable.
130 *
131 * @return an enumeration of the keys in this hashtable.
132 * @see java.util.Enumeration
133 * @see java.util.Hashtable#elements()
134 * @since 1.0
135 */
136 public Enumeration keys() {
137 return new IdentityHashtableEnumerator(table, true);
138 }
139
140 /**
141 * Returns an enumeration of the values in this hashtable.
142 * Use the Enumeration methods on the returned object to fetch the elements
143 * sequentially.
144 *
145 * @return an enumeration of the values in this hashtable.
146 * @see java.util.Enumeration
147 * @see java.util.Hashtable#keys()
148 * @since 1.0
149 */
150 public Enumeration elements() {
151 return new IdentityHashtableEnumerator(table, false);
152 }
153
154 /**
155 * Tests if some key maps into the specified value in this hashtable.
156 * This operation is more expensive than the <code>containsKey</code>
157 * method.
158 *
159 * @param value a value to search for.
160 * @return <code>true</code> if some key maps to the
161 * <code>value</code> argument in this hashtable;
162 * <code>false</code> otherwise.
163 * @exception NullPointerException if the value is <code>null</code>.
164 * @see java.util.Hashtable#containsKey(java.lang.Object)
165 * @since 1.0
166 */
167 public boolean contains(Object value) {
168 if (value == null) {
169 throw new NullPointerException();
170 }
171
172 IdentityHashtableEntry tab[] = table;
173 for (int i = tab.length ; i-- > 0 ;) {
174 for (IdentityHashtableEntry e = tab[i] ; e != null ; e = e.next) {
175 if (e.value == value) {
176 return true;
177 }
178 }
179 }
180 return false;
181 }
182
183 /**
184 * Tests if the specified object is a key in this hashtable.
185 *
186 * @param key possible key.
187 * @return <code>true</code> if the specified object is a key in this
188 * hashtable; <code>false</code> otherwise.
189 * @see java.util.Hashtable#contains(java.lang.Object)
190 * @since 1.0
191 */
192 public boolean containsKey(Object key) {
193 IdentityHashtableEntry tab[] = table;
194 int hash = System.identityHashCode(key);
195 int index = (hash & 0x7FFFFFFF) % tab.length;
196 for (IdentityHashtableEntry e = tab[index] ; e != null ; e = e.next) {
197 if ((e.hash == hash) && e.key == key) {
198 return true;
199 }
200 }
201 return false;
202 }
203
204 /**
205 * Returns the value to which the specified key is mapped in this hashtable.
206 *
207 * @param key a key in the hashtable.
208 * @return the value to which the key is mapped in this hashtable;
209 * <code>null</code> if the key is not mapped to any value in
210 * this hashtable.
211 * @see java.util.Hashtable#put(java.lang.Object, java.lang.Object)
212 * @since 1.0
213 */
214 public Object get(Object key) {
215 IdentityHashtableEntry tab[] = table;
216 int hash = System.identityHashCode(key);
217 int index = (hash & 0x7FFFFFFF) % tab.length;
218 for (IdentityHashtableEntry e = tab[index] ; e != null ; e = e.next) {
219 if ((e.hash == hash) && e.key == key) {
220 return e.value;
221 }
222 }
223 return null;
224 }
225
226 /**
227 * Rehashes the contents of the hashtable into a hashtable with a
228 * larger capacity. This method is called automatically when the
229 * number of keys in the hashtable exceeds this hashtable's capacity
230 * and load factor.
231 *
232 * @since 1.0
233 */
234 protected void rehash() {
235 int oldCapacity = table.length;
236 IdentityHashtableEntry oldTable[] = table;
237
238 int newCapacity = oldCapacity * 2 + 1;
239 IdentityHashtableEntry newTable[] = new IdentityHashtableEntry[newCapacity];
240
241 threshold = (int)(newCapacity * loadFactor);
242 table = newTable;
243
244 //System.out.println("rehash old=" + oldCapacity + ", new=" + newCapacity + ", thresh=" + threshold + ", count=" + count);
245
246 for (int i = oldCapacity ; i-- > 0 ;) {
247 for (IdentityHashtableEntry old = oldTable[i] ; old != null ; ) {
248 IdentityHashtableEntry e = old;
249 old = old.next;
250
251 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
252 e.next = newTable[index];
253 newTable[index] = e;
254 }
255 }
256 }
257
258 /**
259 * Maps the specified <code>key</code> to the specified
260 * <code>value</code> in this hashtable. Neither the key nor the
261 * value can be <code>null</code>.
262 * <p>
263 * The value can be retrieved by calling the <code>get</code> method
264 * with a key that is equal to the original key.
265 *
266 * @param key the hashtable key.
267 * @param value the value.
268 * @return the previous value of the specified key in this hashtable,
269 * or <code>null</code> if it did not have one.
270 * @exception NullPointerException if the key or value is
271 * <code>null</code>.
272 * @see java.util.Hashtable#get(java.lang.Object)
273 * @since 1.0
274 */
275 public Object put(Object key, Object value) {
276 // Make sure the value is not null
277 if (value == null) {
278 throw new NullPointerException();
279 }
280
281 // Makes sure the key is not already in the hashtable.
282 IdentityHashtableEntry tab[] = table;
283 int hash = System.identityHashCode(key);
284 int index = (hash & 0x7FFFFFFF) % tab.length;
285 for (IdentityHashtableEntry e = tab[index] ; e != null ; e = e.next) {
286 if ((e.hash == hash) && e.key == key) {
287 Object old = e.value;
288 e.value = value;
289 return old;
290 }
291 }
292
293 if (count >= threshold) {
294 // Rehash the table if the threshold is exceeded
295 rehash();
296 return put(key, value);
297 }
298
299 // Creates the new entry.
300 IdentityHashtableEntry e = new IdentityHashtableEntry();
301 e.hash = hash;
302 e.key = key;
303 e.value = value;
304 e.next = tab[index];
305 tab[index] = e;
306 count++;
307 return null;
308 }
309
310 /**
311 * Removes the key (and its corresponding value) from this
312 * hashtable. This method does nothing if the key is not in the hashtable.
313 *
314 * @param key the key that needs to be removed.
315 * @return the value to which the key had been mapped in this hashtable,
316 * or <code>null</code> if the key did not have a mapping.
317 * @since 1.0
318 */
319 public Object remove(Object key) {
320 IdentityHashtableEntry tab[] = table;
321 int hash = System.identityHashCode(key);
322 int index = (hash & 0x7FFFFFFF) % tab.length;
323 for (IdentityHashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
324 if ((e.hash == hash) && e.key == key) {
325 if (prev != null) {
326 prev.next = e.next;
327 } else {
328 tab[index] = e.next;
329 }
330 count--;
331 return e.value;
332 }
333 }
334 return null;
335 }
336
337 /**
338 * Clears this hashtable so that it contains no keys.
339 *
340 * @since 1.0
341 */
342 public void clear() {
343 IdentityHashtableEntry tab[] = table;
344 for (int index = tab.length; --index >= 0; )
345 tab[index] = null;
346 count = 0;
347 }
348
349 /**
350 * Returns a rather long string representation of this hashtable.
351 *
352 * @return a string representation of this hashtable.
353 * @since 1.0
354 */
355 public String toString() {
356 int max = size() - 1;
357 StringBuffer buf = new StringBuffer();
358 Enumeration k = keys();
359 Enumeration e = elements();
360 buf.append("{");
361
362 for (int i = 0; i <= max; i++) {
363 String s1 = k.nextElement().toString();
364 String s2 = e.nextElement().toString();
365 buf.append(s1 + "=" + s2);
366 if (i < max) {
367 buf.append(", ");
368 }
369 }
370 buf.append("}");
371 return buf.toString();
372 }
373 }