TopLinkIdentityHashSet


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 Set} that tests equality by reference,
29   * not equals(). This is required to track objects throughout the lifecycle
30   * of a {@link oracle.toplink.essentials.sessions.UnitOfWork}, regardless if the domain
31   * object redefines its equals() method. Additionally, this implementation does
32   * <b>not</b> allow null elements.
33   * <p>
34   * This class does <b>not</b> inherit from {@link AbstractSet} because the
35   * method {@link AbstractSet#removeAll removeAll(Collection c)} does not work
36   * correctly with reference equality testing (NB the Javadocs for
37   * {@link AbstractCollection} indicates that removeAll is an optional method).
38   *
39   * @author Mike Norman (since TopLink 10.1.3)
40   *
41   */
42  
43  // J2SE imports
44  import java.io.*;
45  import java.util.*;
46  
47  public class TopLinkIdentityHashSet extends AbstractCollection implements Set, Cloneable  , Serializable {
48      static final long serialVersionUID = 1619330892277906704L;
49  
50      // the default initial capacity
51      static final int DEFAULT_INITIAL_CAPACITY = 32;
52  
53      // the maximum capacity.
54      static final int MAXIMUM_CAPACITY = 1 << 30;
55  
56      // the loadFactor used when none specified in constructor.
57      static final float DEFAULT_LOAD_FACTOR = 0.75f;
58      protected transient Entry[] entries;// internal array of Entry's
59      protected transient int count = 0;
60      protected int threshold = 0;
61      protected float loadFactor = 0;
62  
63      /**
64       * Constructs a new <tt>TopLinkIdentityHashSet</tt> with the given initial
65       * capacity and the given loadFactor.
66       *
67       * @param initialCapacity the initial capacity of the
68       * <tt>TopLinkIdentityHashSet</tt>.
69       * @param loadFactor the loadFactor of the <tt>TopLinkIdentityHashSet</tt>.
70       * @throws <tt>IllegalArgumentException</tt> if the initial capacity is less
71       * than zero, or if the loadFactor is nonpositive.
72       */
73      public TopLinkIdentityHashSet(int initialCapacity, float loadFactor) {
74          if (initialCapacity < 0) {
75              throw new IllegalArgumentException  ("Illegal initialCapacity: " + initialCapacity);
76          }
77          if (initialCapacity > MAXIMUM_CAPACITY) {
78              initialCapacity = MAXIMUM_CAPACITY;
79          }
80          if ((loadFactor <= 0) || Float.isNaN(loadFactor)) {
81              throw new IllegalArgumentException  ("Illegal loadFactor: " + loadFactor);
82          }
83  
84          // Find a power of 2 >= initialCapacity
85          int capacity = 1;
86          while (capacity < initialCapacity) {
87              capacity <<= 1;
88          }
89          this.loadFactor = loadFactor;
90          threshold = (int)(capacity * loadFactor);
91          entries = new Entry[capacity];
92      }
93  
94      /**
95       * Constructs a new <tt>TopLinkIdentityHashSet</tt> with the given
96       * initial capacity and a default loadFactor of <tt>0.75</tt>.
97       *
98       * @param initialCapacity the initial capacity of the TopLinkIdentityHashSet.
99       * @throws <tt>IllegalArgumentException</tt> if the initial capacity is less
100      * than zero.
101      */
102     public TopLinkIdentityHashSet(int initialCapacity) {
103         this(initialCapacity, DEFAULT_LOAD_FACTOR);
104     }
105 
106     /**
107      * Constructs a new <tt>TopLinkIdentityHashSet</tt> with a default initial
108      * capacity of <tt>32</tt> and a loadfactor of <tt>0.75</tt>.
109      */
110     public TopLinkIdentityHashSet() {
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      * Constructs a new <tt>TopLinkIdentityHashSet</tt> with the same contents
118      * as the given <tt>Collection</tt>. The new <tt>TopLinkIdentityHashSet</tt>
119      * is created with an initial capacity sufficient to hold the elements of
120      * the given <tt>Collection</tt>.
121      *
122      * @param c the <tt>Collection</tt> whose contents are to be placed in the
123      * new <tt>TopLinkIdentityHashSet</tt>.
124      */
125     public TopLinkIdentityHashSet(Collection c) {
126         this(Math.max((int)(c.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
127         addAll(c);
128     }
129 
130     /**
131      * @return the size of this <tt>TopLinkIdentityHashSet</tt>.
132      */
133     public int size() {
134         return count;
135     }
136 
137     /**
138      * @return <tt>true</tt> if this <tt>TopLinkIdentityHashSet</tt> is empty.
139      */
140     public boolean isEmpty() {
141         return (count == 0);
142     }
143 
144     /**
145      * Returns <tt>true</tt> if this <tt>TopLinkIdentityHashSet</tt> contains
146      * the given object.
147      *
148      * @param obj the object to find.
149      * @return <tt>true</tt> if this <tt>TopLinkIdentityHashSet</tt> contains
150      * obj by reference.
151      */
152     public boolean contains(Object   obj) {
153         if (obj == null) {
154             return false;
155         }
156 
157         Entry[] copyOfEntries = entries;
158         int hash = System.identityHashCode(obj);
159         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
160         for (Entry e = copyOfEntries[index]; e != null; e = e.next) {
161             if ((e.hash == hash) && (obj == e.value)) {
162                 return true;
163             }
164         }
165         return false;
166     }
167 
168     /**
169      * INTERNAL:
170      * Re-builds the internal array of Entry's with a larger capacity.
171      * This method is called automatically when the number of objects in this
172      * TopLinkIdentityHashSet exceeds its current threshold.
173      */
174     private void rehash() {
175         int oldCapacity = entries.length;
176         Entry[] oldEntries = entries;
177         int newCapacity = (oldCapacity * 2) + 1;
178         Entry[] newEntries = new Entry[newCapacity];
179         threshold = (int)(newCapacity * loadFactor);
180         entries = newEntries;
181         for (int i = oldCapacity; i-- > 0;) {
182             for (Entry old = oldEntries[i]; old != null;) {
183                 Entry e = old;
184                 old = old.next;
185                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
186                 e.next = newEntries[index];
187                 newEntries[index] = e;
188             }
189         }
190     }
191 
192     /**
193      * Adds the given object to this <tt>TopLinkIdentityHashSet</tt>.
194      *
195      * @param obj object to add.
196      * @return <tt>true</tt> if this <tt>TopLinkIdentityHashSet</tt> did not
197      * already contain obj.
198      * @throws <tt>NullPointerException</tt> if obj is null.
199      */
200     public boolean add(Object   obj) {
201         if (obj == null) {
202             throw new NullPointerException  ();
203         }
204 
205         // Makes sure the object is not already in the TopLinkIdentityHashSet.
206         Entry[] copyOfEntries = entries;
207         int hash = System.identityHashCode(obj);
208         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
209         for (Entry e = copyOfEntries[index]; e != null; e = e.next) {
210             if ((e.hash == hash) && (obj == e.value)) {
211                 return false;
212             }
213         }
214 
215         if (count >= threshold) {
216             // Rehash the table if the threshold is exceeded
217             rehash();
218             copyOfEntries = entries;
219             index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
220         }
221 
222         // Creates the new entry.
223         Entry e = new Entry(hash, obj, copyOfEntries[index]);
224         copyOfEntries[index] = e;
225         count++;
226         return true;
227     }
228 
229     /**
230      * Removes the given object from this <tt>TopLinkIdentityHashSet</tt>, if
231      * present.
232      *
233      * @param obj the object to be removed from this <tt>TopLinkIdentityHashSet</tt>.
234      * @return <tt>true</tt> if this <tt>TopLinkIdentityHashSet</tt> contained
235      * obj.
236      */
237     public boolean remove(Object   obj) {
238         if (obj == null) {
239             return false;
240         }
241 
242         Entry[] copyOfEntries = entries;
243         int hash = System.identityHashCode(obj);
244         int index = (hash & 0x7FFFFFFF) % copyOfEntries.length;
245         for (Entry e = copyOfEntries[index], prev = null; e != null; prev = e, e = e.next) {
246             if ((e.hash == hash) && (obj == e.value)) {
247                 if (prev != null) {
248                     prev.next = e.next;
249                 } else {
250                     copyOfEntries[index] = e.next;
251                 }
252                 count--;
253                 return true;
254             }
255         }
256         return false;
257     }
258 
259     /**
260      * This implementation throws an <tt>UnsupportedOperationException</tt>
261      * because <tt>removeAll</tt> does not work correctly with reference
262      * equality testing.<p>
263      */
264     public boolean removeAll(Collection c) {
265         throw new UnsupportedOperationException  ("TopLinkIdentityHashSet removeAll");
266     }
267 
268     /**
269      * This implementation throws an <tt>UnsupportedOperationException</tt>.
270      * The Javadocs for {@link AbstractCollection} indicates that <tt>retainAll</tt>
271      * is an optional method.<p>
272      */
273     public boolean retainAll(Collection c) {
274         throw new UnsupportedOperationException  ("TopLinkIdentityHashSet retainAll");
275     }
276 
277     /**
278      * Removes all of the objects from this <tt>TopLinkIdentityHashSet</tt>.
279      */
280     public void clear() {
281         if (count > 0) {
282             Entry[] copyOfEntries = entries;
283             for (int i = copyOfEntries.length; --i >= 0;) {
284                 copyOfEntries[i] = null;
285             }
286             count = 0;
287         }
288     }
289 
290     /**
291      * Returns a shallow copy of this <tt>TopLinkIdentityHashSet</tt> (the
292      * elements are not cloned).
293      *
294      * @return a shallow copy of this <tt>TopLinkIdentityHashSet</tt>.
295      */
296     public Object   clone() {
297         try {
298             Entry[] copyOfEntries = entries;
299             TopLinkIdentityHashSet clone = (TopLinkIdentityHashSet)super.clone();
300             clone.entries = new Entry[copyOfEntries.length];
301             for (int i = copyOfEntries.length; i-- > 0;) {
302                 clone.entries[i] = (copyOfEntries[i] != null) ? (Entry)copyOfEntries[i].clone() : null;
303             }
304             return clone;
305         } catch (CloneNotSupportedException   e) {
306             // this shouldn't happen, since we are Cloneable
307             throw new InternalError  ();
308         }
309     }
310 
311     /**
312      * Get an iterator for this <tt>TopLinkIdentityHashSet</tt>
313      */
314     public Iterator iterator() {
315         return new TopLinkIdentityHashSetIterator();
316     }
317 
318     /**
319      * TopLinkIdentityHashSet entry.
320      */
321     static class Entry {
322         int hash;
323         Object   value;
324         Entry next;
325 
326         Entry(int hash, Object   value, Entry next) {
327             this.hash = hash;
328             this.value = value;
329             this.next = next;
330         }
331 
332         protected Object   clone() {
333             return new Entry(hash, value, ((next == null) ? null : (Entry)next.clone()));
334         }
335     }
336 
337     class TopLinkIdentityHashSetIterator implements Iterator {
338         Entry[] copyOfEntries = TopLinkIdentityHashSet.this.entries;
339         int index = copyOfEntries.length;
340         Entry entry = null;
341         Entry lastReturned = null;
342 
343         TopLinkIdentityHashSetIterator() {
344         }
345 
346         public boolean hasNext() {
347             Entry e = entry;
348             int i = index;
349             Entry[] tmp = copyOfEntries;
350             while ((e == null) && (i > 0)) {
351                 e = tmp[--i];
352             }
353             entry = e;
354             index = i;
355             return e != null;
356         }
357 
358         public Object   next() {
359             Entry et = entry;
360             int i = index;
361             Entry[] tmp = copyOfEntries;
362 
363             while ((et == null) && (i > 0)) {
364                 et = tmp[--i];
365             }
366             entry = et;
367             index = i;
368             if (et != null) {
369                 Entry e = lastReturned = entry;
370                 entry = e.next;
371                 return e.value;
372             }
373             throw new NoSuchElementException();
374         }
375 
376         public void remove() {
377             if (lastReturned == null) {
378                 throw new IllegalStateException  ();
379             }
380 
381             Entry[] copyOfEntries = TopLinkIdentityHashSet.this.entries;
382             int index = (lastReturned.hash & 0x7FFFFFFF) % copyOfEntries.length;
383             for (Entry e = copyOfEntries[index], prev = null; e != null; prev = e, e = e.next) {
384                 if (e == lastReturned) {
385                     if (prev == null) {
386                         copyOfEntries[index] = e.next;
387                     } else {
388                         prev.next = e.next;
389                     }
390                     count--;
391                     lastReturned = null;
392                     return;
393                 }
394             }
395             throw new ConcurrentModificationException();
396         }
397     }
398 
399     /**
400      * Serialize the state of this <tt>TopLinkIdentityHashSet</tt> to a stream.
401      *
402      * @serialData The <i>capacity</i> of the <tt>TopLinkIdentityHashSet</tt>
403      * (the length of the bucket array) is emitted (int), followed by the
404      * <i>size</i> of the <tt>TopLinkIdentityHashSet</tt>, followed by the
405      * contents (in no particular order).
406      */
407     private void writeObject(ObjectOutputStream s) throws IOException, ClassNotFoundException   {
408         // Write out the threshold, loadfactor (and any hidden 'magic' stuff).
409         s.defaultWriteObject();
410 
411         // Write out number of buckets
412         s.writeInt(entries.length);
413         // Write out count
414         s.writeInt(count);
415         // Write out contents
416         for (Iterator i = iterator(); i.hasNext();) {
417             s.writeObject(i.next());
418         }
419     }
420 
421     /**
422      * Deserialize the <tt>TopLinkIdentityHashSet</tt> from a stream.
423      */
424     private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException   {
425         // Read in the threshold, loadfactor (and any hidden 'magic' stuff).
426         s.defaultReadObject();
427 
428         // Read in number of buckets and allocate the bucket array;
429         int numBuckets = s.readInt();
430         entries = new Entry[numBuckets];
431         // Read in size (count)
432         int size = s.readInt();
433 
434         // Read the objects and add to the TopLinkIdentityHashSet
435         for (int i = 0; i < size; i++) {
436             add(s.readObject());
437         }
438     }
439 }
440
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags