IdentityHashtable


1   /*
2    * The contents of this file are subject to the terms 
3    * of the Common Development and Distribution License 
4    * (the "License").  You may not use this file except 
5    * in compliance with the License.
6    * 
7    * You can obtain a copy of the license at 
8    * glassfish/bootstrap/legal/CDDLv1.0.txt or 
9    * https://glassfish.dev.java.net/public/CDDLv1.0.html. 
10   * See the License for the specific language governing 
11   * permissions and limitations under the License.
12   * 
13   * When distributing Covered Code, include this CDDL 
14   * HEADER in each file and include the License file at 
15   * glassfish/bootstrap/legal/CDDLv1.0.txt.  If applicable, 
16   * add the following below this CDDL HEADER, with the 
17   * fields enclosed by brackets "[]" replaced with your 
18   * own identifying information: Portions Copyright [yyyy] 
19   * [name of copyright owner]
20   */
21  // Copyright (c) 1998, 2005, Oracle. All rights reserved.  
22  package oracle.toplink.essentials.internal.helper;
23  
24  
25  /**
26   * INTERNAL:
27   * <p>
28   * <b>Purpose</b>: Define a {@link Hashtable} that manages key equality by
29   * reference, not equals(). This is required to track objects throughout the
30   * lifecycle of a {@link oracle.toplink.essentials.sessions.UnitOfWork}, regardless if the
31   * domain object redefines its equals() method. Additionally, this implementation
32   * does <b>not</b> permit nulls.
33   */
34  
35  // J2SE imports
36  import java.io.*;
37  import java.util.*;
38  
39  public class IdentityHashtable extends Dictionary implements Cloneable  , Serializable {
40      static final long serialVersionUID = 1421746759512286392L;
41  
42      // the default initial capacity
43      static final int DEFAULT_INITIAL_CAPACITY = 32;
44  
45      // the maximum capacity.
46      static final int MAXIMUM_CAPACITY = 1 << 30;
47  
48      // the loadFactor used when none specified in constructor.
49      static final float DEFAULT_LOAD_FACTOR = 0.75f;
50  
51      /** An "enum" of Enumeration types. */
52      static final int KEYS = 0;
53  
54      /** An "enum" of Enumeration types. */
55      static final int ELEMENTS = 1;
56      private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
57      protected transient Entry[] entries;// internal array of Entry's
58      protected transient int count = 0;
59      protected int threshold = 0;
60      protected float loadFactor = 0;
61  
62      /**
63       * Constructs a new <tt>IdentityHashtable</tt> with the given
64       * initial capacity and the given loadFactor.
65       *
66       * @param initialCapacity the initial capacity of this
67       * <tt>IdentityHashtable</tt>.
68       * @param loadFactor the loadFactor of the <tt>IdentityHashtable</tt>.
69       * @throws IllegalArgumentException  if the initial capacity is less
70       * than zero, or if the loadFactor is nonpositive.
71       */
72      public IdentityHashtable(int initialCapacity, float loadFactor) {
73          if (initialCapacity < 0) {
74              throw new IllegalArgumentException  ("Illegal initialCapacity: " + initialCapacity);
75          }
76          if (initialCapacity > MAXIMUM_CAPACITY) {
77              initialCapacity = MAXIMUM_CAPACITY;
78          }
79          if ((loadFactor <= 0) || Float.isNaN(loadFactor)) {
80              throw new IllegalArgumentException  ("Illegal loadFactor: " + loadFactor);
81          }
82  
83          // Find a power of 2 >= initialCapacity
84          int capacity = 1;
85          while (capacity < initialCapacity) {
86              capacity <<= 1;
87          }
88          this.loadFactor = loadFactor;
89          threshold = (int)(capacity * loadFactor);
90          entries = new Entry[capacity];
91      }
92  
93      /**
94       * Constructs a new <tt>IdentityHashtable</tt> with the given
95       * initial capacity and a default loadFactor of <tt>0.75</tt>.
96       *
97       * @param initialCapacity the initial capacity of the
98       * <tt>IdentityHashtable</tt>.
99       * @throws <tt>IllegalArgumentException</tt> if the initial capacity is less
100      * than zero.
101      */
102     public IdentityHashtable(int initialCapacity) {
103         this(initialCapacity, DEFAULT_LOAD_FACTOR);
104     }
105 
106     /**
107      * Constructs a new <tt>IdentityHashtable</tt> with a default initial
108      * capacity of <tt>32</tt> and a loadfactor of <tt>0.75</tt>.
109      */
110     public IdentityHashtable() {
111         loadFactor = DEFAULT_LOAD_FACTOR;
112         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
113         entries = new Entry[DEFAULT_INITIAL_CAPACITY];
114     }
115 
116     /**
117      * Removes all of the mappings from this <tt>IdentityHashtable</tt>.
118      */
119     public synchronized void clear() {
120         if (count > 0) {
121             Entry[] copyOfEntries = entries;
122             for (int i = copyOfEntries.length; --i >= 0;) {
123                 copyOfEntries[i] = null;
124             }
125             count = 0;
126         }
127     }
128 
129     /**
130      * Returns a shallow copy of this <tt>IdentityHashtable</tt> (the
131      * elements are not cloned).
132      *
133      * @return a shallow copy of this <tt>IdentityHashtable</tt>.
134      */
135     public synchronized Object   clone() {
136         try {
137             Entry[] copyOfEntries = entries;
138             IdentityHashtable clone = (IdentityHashtable)super.clone();
139             clone.entries = new Entry[copyOfEntries.length];
140             for (int i = copyOfEntries.length; i-- > 0;) {
141                 clone.entries[i] = (copyOfEntries[i] != null) ? (Entry)copyOfEntries[i].clone() : null;
142             }
143             return clone;
144         } catch (CloneNotSupportedException   e) {
145             // this shouldn't happen, since we are Cloneable
146             throw new InternalError  ();
147         }
148     }
149 
150     /**
151      * Returns <tt>true</tt> if this <tt>IdentityHashtable</tt> contains
152      * the given object. Equality is tested by the equals() method.
153      *
154      * @param obj the object to find.
155      * @return <tt>true</tt> if this <tt>IdentityHashtable</tt> contains
156      * obj.
157      * @throws <tt>NullPointerException</tt> if obj is null</tt>.
158      */
159     public synchronized boolean contains(Object   obj) {
160         if (obj == null) {
161             throw new NullPointerException  ();
162         }
163 
164         Entry[] copyOfEntries = entries;
165         for (int i = copyOfEntries.length; i-- > 0;) {
166             for (Entry e = copyOfEntries[i]; e != null; e = e.next) {
167                 if (e.value.equals(obj)) {
168                     return true;
169                 }
170             }
171         }
172         return false;
173     }
174 
175     /**
176      * Returns <tt>true</tt> if this <tt>IdentityHashtable</tt> contains a
177      * mapping for the given key. Equality is tested by reference.
178      *
179      * @param key object to be used as a key into this
180      * <tt>IdentityHashtable</tt>.
181      * @return <tt>true</tt> if this <tt>IdentityHashtable</tt> contains a
182      * mapping for key.
183      */
184     public synchronized boolean containsKey(Object   key) {
185         Entry[] copyOfEntries = entries;
186         int hash = System.identityHashCode(key);
187         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
188         for (Entry e = copyOfEntries[index]; e != null; e = e.next) {
189             if (e.key == key) {
190                 return true;
191             }
192         }
193         return false;
194     }
195 
196     public synchronized Enumeration elements() {
197         if (count == 0) {
198             return emptyEnumerator;
199         } else {
200             return new Enumerator(ELEMENTS);
201         }
202     }
203 
204     /**
205      * Returns the value to which the given key is mapped in this
206      * <tt>IdentityHashtable</tt>. Returns <tt>null</tt> if this
207      * <tt>IdentityHashtable</tt> contains no mapping for this key.
208      *
209      * @return the value to which this <tt>IdentityHashtable</tt> maps the
210      * given key.
211      * @param key key whose associated value is to be returned.
212      */
213     public synchronized Object   get(Object   key) {
214         Entry[] copyOfEntries = entries;
215         int hash = System.identityHashCode(key);
216         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
217         for (Entry e = copyOfEntries[index]; e != null; e = e.next) {
218             if (e.key == key) {
219                 return e.value;
220             }
221         }
222         return null;
223     }
224 
225     /**
226      * @return <tt>true</tt> if this <tt>IdentityHashtable</tt> is empty.
227      */
228     public boolean isEmpty() {
229         return (count == 0);
230     }
231 
232     public synchronized Enumeration keys() {
233         if (count == 0) {
234             return emptyEnumerator;
235         } else {
236             return new Enumerator(KEYS);
237         }
238     }
239 
240     /**
241      * Associate the given object with the given key in this
242      * <tt>IdentityHashtable</tt>, replacing any existing mapping.
243      *
244      * @param key key to map to given object.
245      * @param obj object to be associated with key.
246      * @return the previous object for key or <tt>null</tt> if this
247      * <tt>IdentityHashtable</tt> did not have one.
248      * @throws <tt>NullPointerException</tt> if obj is null</tt>.
249      */
250     public synchronized Object   put(Object   key, Object   obj) {
251         if (obj == null) {
252             throw new NullPointerException  ();
253         }
254 
255         Entry[] copyOfEntries = entries;
256         int hash = System.identityHashCode(key);
257         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
258         for (Entry e = copyOfEntries[index]; e != null; e = e.next) {
259             if (e.key == key) {
260                 Object   old = e.value;
261                 e.value = obj;
262                 return old;
263             }
264         }
265 
266         if (count >= threshold) {
267             rehash();
268             copyOfEntries = entries;
269             index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
270         }
271         Entry e = new Entry(hash, key, obj, copyOfEntries[index]);
272         copyOfEntries[index] = e;
273         count++;
274         return null;
275     }
276 
277     /**
278      * INTERNAL:
279      * Re-builds the internal array of Entry's with a larger capacity.
280      * This method is called automatically when the number of objects in this
281      * IdentityHashtable exceeds its current threshold.
282      */
283     private void rehash() {
284         int oldCapacity = entries.length;
285         Entry[] oldEntries = entries;
286         int newCapacity = (oldCapacity * 2) + 1;
287         Entry[] newEntries = new Entry[newCapacity];
288         threshold = (int)(newCapacity * loadFactor);
289         entries = newEntries;
290         for (int i = oldCapacity; i-- > 0;) {
291             for (Entry old = oldEntries[i]; old != null;) {
292                 Entry e = old;
293                 old = old.next;
294                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
295                 e.next = newEntries[index];
296                 newEntries[index] = e;
297             }
298         }
299     }
300 
301     /**
302      * Removes the mapping (key and its corresponding value) from this
303      * <tt>IdentityHashtable</tt>, if present.
304      *
305      * @param key key whose mapping is to be removed from the map.
306      * @return the previous object for key or <tt>null</tt> if this
307      * <tt>IdentityHashtable</tt> did not have one.
308      */
309     public synchronized Object   remove(Object   key) {
310         Entry[] copyOfEntries = entries;
311         int hash = System.identityHashCode(key);
312         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
313         for (Entry e = copyOfEntries[index], prev = null; e != null; prev = e, e = e.next) {
314             if (e.key == key) {
315                 if (prev != null) {
316                     prev.next = e.next;
317                 } else {
318                     copyOfEntries[index] = e.next;
319                 }
320                 count--;
321                 return e.value;
322             }
323         }
324         return null;
325     }
326 
327     /**
328      * @return the size of this <tt>IdentityHashtable</tt>.
329      */
330     public int size() {
331         return count;
332     }
333 
334     /**
335      * Return the string representation of this <tt>IdentityHashtable</tt>.
336      *
337      * @return the string representation of this <tt>IdentityHashtable</tt>.
338      */
339     public synchronized String   toString() {
340         int max = size() - 1;
341         StringBuffer   buf = new StringBuffer  ();
342         Enumeration k = keys();
343         Enumeration e = elements();
344         buf.append("{");
345         for (int i = 0; i <= max; i++) {
346             String   s1 = k.nextElement().toString();
347             String   s2 = e.nextElement().toString();
348             buf.append(s1 + "=" + s2);
349             if (i < max) {
350                 buf.append(", ");
351             }
352         }
353         buf.append("}");
354         return buf.toString();
355     }
356 
357     /**
358      * Serialize the state of this <tt>IdentityHashtable</tt> to a stream.
359      *
360      * @serialData The <i>capacity</i> of the <tt>IdentityHashtable</tt>
361      * (the length of the bucket array) is emitted (int), followed by the
362      * <i>size</i> of the <tt>IdentityHashtable</tt>, followed by the
363      * key-value mappings (in no particular order).
364      */
365     private void writeObject(ObjectOutputStream s) throws IOException {
366         // Write out the threshold, loadfactor (and any hidden 'magic' stuff).
367         s.defaultWriteObject();
368 
369         // Write out number of buckets
370         s.writeInt(entries.length);
371         // Write out count
372         s.writeInt(count);
373         // Write out contents
374         for (int i = entries.length - 1; i >= 0; i--) {
375             Entry entry = entries[i];
376             while (entry != null) {
377                 s.writeObject(entry.key);
378                 s.writeObject(entry.value);
379                 entry = entry.next;
380             }
381         }
382     }
383 
384     /**
385      * Deserialize the <tt>IdentityHashtable</tt> from a stream.
386      */
387     private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException   {
388         // Read in the threshold, loadfactor (and any hidden 'magic' stuff).
389         s.defaultReadObject();
390 
391         // Read in number of buckets and allocate the bucket array;
392         int numBuckets = s.readInt();
393         entries = new Entry[numBuckets];
394         // Read in size (count)
395         int size = s.readInt();
396 
397         // Read the mappings and add to the TopLinkIdentityHashMap
398         for (int i = 0; i < size; i++) {
399             Object   key = s.readObject();
400             Object   value = s.readObject();
401             put(key, value);
402         }
403     }
404 
405     private static class EmptyEnumerator implements Enumeration {
406         EmptyEnumerator() {
407         }
408 
409         public boolean hasMoreElements() {
410             return false;
411         }
412 
413         public Object   nextElement() {
414             throw new NoSuchElementException();
415         }
416     }
417 
418     class Enumerator implements Enumeration {
419         int enumeratorType;
420         int index;
421         Entry entry;
422 
423         Enumerator(int enumeratorType) {
424             this.enumeratorType = enumeratorType;
425             index = IdentityHashtable.this.entries.length;
426         }
427 
428         public boolean hasMoreElements() {
429             if (entry != null) {
430                 return true;
431             }
432             while (index-- > 0) {
433                 if ((entry = IdentityHashtable.this.entries[index]) != null) {
434                     return true;
435                 }
436             }
437             return false;
438         }
439 
440         public Object   nextElement() {
441             if (entry == null) {
442                 while ((index-- > 0) && ((entry = IdentityHashtable.this.entries[index]) == null)) {
443                     ;
444                 }
445             }
446             if (entry != null) {
447                 Entry e = entry;
448                 entry = e.next;
449                 if (enumeratorType == KEYS) {
450                     return e.key;
451                 } else {
452                     return e.value;
453                 }
454             }
455             throw new NoSuchElementException("IdentityHashtable.Enumerator");
456         }
457     }
458 
459     /**
460      * IdentityHashtable entry.
461      */
462     private static class Entry {
463         int hash;
464         Object   key;
465         Object   value;
466         Entry next;
467 
468         Entry(int hash, Object   key, Object   value, Entry next) {
469             this.hash = hash;
470             this.key = key;
471             this.value = value;
472             this.next = next;
473         }
474 
475         protected Object   clone() {
476             return new Entry(hash, key, value, ((next == null) ? null : (Entry)next.clone()));
477         }
478 
479         public Object   getKey() {
480             return key;
481         }
482 
483         public Object   getValue() {
484             return value;
485         }
486 
487         public Object   setValue(Object   value) {
488             Object   oldValue = this.value;
489             this.value = value;
490             return oldValue;
491         }
492 
493         public boolean equals(Object   o) {
494             if (!(o instanceof Entry)) {
495                 return false;
496             }
497 
498             Entry e = (Entry)o;
499             return (key == e.getKey()) && ((value == null) ? (e.getValue() == null) : value.equals(e.getValue()));
500         }
501 
502         public int hashCode() {
503             return hash ^ ((value == null) ? 0 : value.hashCode());
504         }
505 
506         public String   toString() {
507             return key + "=" + value;
508         }
509     }
510 }
511
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags