EntrySet


1   
2   /*
3    * Copyright (c) 1998 - 2005 Versant Corporation
4    * All rights reserved. This program and the accompanying materials
5    * are made available under the terms of the Eclipse Public License v1.0
6    * which accompanies this distribution, and is available at
7    * http://www.eclipse.org/legal/epl-v10.html
8    *
9    * Contributors:
10   * Versant Corporation - initial API and implementation
11   */
12  package com.versant.core.ejb.common;
13  
14  import com.versant.core.common.BindingSupportImpl;
15  
16  import java.util.Iterator  ;
17  import java.util.ConcurrentModificationException  ;
18  import java.util.NoSuchElementException  ;
19  
20  /**
21   * This is a Hashed based collection that contain Entry elements.
22   * Equality is key based.
23   */
24  public class EntrySet {
25      /**
26       * The default initial capacity - MUST be a power of two.
27       */
28      static final int DEFAULT_INITIAL_CAPACITY = 16;
29      /**
30       * The load factor used when none specified in constructor.
31       **/
32      static final float DEFAULT_LOAD_FACTOR = 0.75f;
33      /**
34       * The load factor for the hash table.
35       */
36      final float loadFactor;
37      /**
38       * The next size value at which to resize (capacity * load factor).
39       */
40      int threshold;
41      /**
42       * The maximum capacity, used if a higher value is implicitly specified
43       * by either of the constructors with arguments.
44       * MUST be a power of two <= 1<<30.
45       */
46      static final int MAXIMUM_CAPACITY = 1 << 30;
47  
48      /**
49       * Array of value table slots.
50       */
51      private Entry[] m_keyTable;
52  
53      /**
54       * The number of key-value mappings contained in this identity hash map.
55       */
56      transient int size;
57      private int modCount;
58  
59      public EntrySet() {
60          this.loadFactor = DEFAULT_LOAD_FACTOR;
61          threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
62          m_keyTable = new Entry[DEFAULT_INITIAL_CAPACITY];
63      }
64  
65      public EntrySet(int initialCapacity) {
66          this(initialCapacity, DEFAULT_LOAD_FACTOR);
67      }
68  
69      public EntrySet(int initialCapacity, float loadFactor) {
70          if (initialCapacity < 0)
71              throw new IllegalArgumentException  ("Illegal initial capacity: " +
72                                                 initialCapacity);
73          if (initialCapacity > MAXIMUM_CAPACITY)
74              initialCapacity = MAXIMUM_CAPACITY;
75          if (loadFactor <= 0 || Float.isNaN(loadFactor))
76              throw new IllegalArgumentException  ("Illegal load factor: " +
77                                                 loadFactor);
78  
79          // Find a power of 2 >= initialCapacity
80          int capacity = 1;
81          while (capacity < initialCapacity)
82              capacity <<= 1;
83  
84          this.loadFactor = loadFactor;
85          threshold = (int)(capacity * loadFactor);
86          m_keyTable = new Entry[capacity];
87      }
88  
89      /**
90       * Add this entry to the set.
91       * @param ne
92       */
93      public Entry addEntry(Entry ne) {
94          int i = indexFor(ne.hash, m_keyTable.length);
95  
96          for (Entry e = m_keyTable[i]; e != null; e = e.next) {
97              if (e.hash == ne.hash && eq(ne.key, e.key)) {
98                  //same instance
99                  if (ne == e) return null;
100                 else throw new IllegalArgumentException  ("Entry with equal key is already in the set");
101 
102             }
103         }
104         modCount++;
105         addEntry(ne, i);
106         return ne;
107     }
108 
109     public boolean add(Object   o) {
110         if (!contains(o)) {
111             addEntry(createEntry(o));
112             return true;
113         }
114         return false;
115     }
116 
117     /**
118      * If the instance is present then return the entry, else add it and return the
119      * new entry.
120      * @param o
121      * @return
122      */
123     public Entry addAndReturnEntry(Object   o) {
124         Entry e = get(o);
125         if (e == null) {
126             return addEntry(createEntry(o));
127         }
128         return e;
129     }
130 
131     public Entry createEntry(Object   key) {
132         return new Entry(key);
133     }
134 
135     private void addEntry(Entry e, int index) {
136         e.next = m_keyTable[index];
137         m_keyTable[index] = e;
138 
139         if (size++ >= threshold) {
140             resize(2 * m_keyTable.length);
141         }
142     }
143 
144     public boolean contains(Object   key) {
145         return (get(key) != null);
146     }
147 
148     public Entry get(Object   key) {
149         final int hash = key.hashCode();
150         for (Entry e = m_keyTable[indexFor(hash, m_keyTable.length)]; e != null; e = e.next) {
151             if (e.hash == hash && eq(key, e.key)) {
152                 return e;
153             }
154         }
155         return null;
156     }
157 
158     public Iterator   iterator() {
159         return new EntryIterator();
160     }
161 
162     // Subclass overrides these to alter behavior of views' iterator() method
163     public Iterator   newKeyIterator()   {
164         return new KeyIterator();
165     }
166 
167     public Iterator   newEntryIterator()   {
168         return new EntryIterator();
169     }
170 
171     void resize(int newCapacity) {
172         Entry[] oldTable = m_keyTable;
173         int oldCapacity = oldTable.length;
174         if (oldCapacity == MAXIMUM_CAPACITY) {
175             threshold = Integer.MAX_VALUE;
176             return;
177         }
178 
179         Entry[] newTable = new Entry[newCapacity];
180         transfer(newTable);
181         m_keyTable = newTable;
182         threshold = (int)(newCapacity * loadFactor);
183     }
184 
185     /**
186      * Transfer all entries from current table to newTable.
187      */
188     void transfer(Entry[] newTable) {
189         Entry[] src = m_keyTable;
190         int newCapacity = newTable.length;
191         for (int j = 0; j < src.length; j++) {
192             Entry e = src[j];
193             if (e != null) {
194                 src[j] = null;
195                 do {
196                     Entry next = e.next;
197                     int i = indexFor(e.hash, newCapacity);
198                     e.next = newTable[i];
199                     newTable[i] = e;
200                     e = next;
201                 } while (e != null);
202             }
203         }
204     }
205 
206     /**
207      * Check for equality of non-null reference x and possibly-null y.
208      */
209     static boolean eq(Object   x, Object   y) {
210         return x == y || x.equals(y);
211     }
212 
213     /**
214      * Returns index for hash code h.
215      */
216     static int indexFor(int h, int length) {
217         return h & (length-1);
218     }
219 
220     /**
221      * How many keys are in the cache?
222      */
223     public int size() {
224         return size;
225     }
226 
227     /**
228      * Removes all mappings from this map.
229      */
230     public void clear() {
231         modCount++;
232         Entry[] tab = m_keyTable;
233         for (int i = 0; i < tab.length; i++) {
234             tab[i] = null;
235         }
236         size = 0;
237     }
238 
239     public static class Entry {
240         final Object   key;
241         private final int hash;
242         private Entry next;
243 
244         public Entry(Object   key) {
245             this.key = key;
246             this.hash = key.hashCode();
247         }
248 
249         public Object   getKey() {
250             return key;
251         }
252 
253         public boolean equals(Object   o) {
254             if (!(o instanceof Entry)) {
255                 return false;
256             }
257 
258             Entry e = (Entry)o;
259             Object   k1 = getKey();
260             Object   k2 = e.getKey();
261             if (k1 == k2 || k1.equals(k2)) {
262                 return true;
263             }
264             return false;
265         }
266 
267         public int hashCode() {
268             return hash;
269         }
270     }
271 
272     class Iter implements Iterator   {
273         /**
274          * The amount that we have iterated over.
275          */
276         private int iterCount;
277 
278         private Entry lastEntry;
279         private int currentIndex;
280 
281         public Iter() {
282         }
283 
284         public void remove() {
285             throw BindingSupportImpl.getInstance().invalidOperation("Remove not allowed");
286         }
287 
288         public boolean hasNext() {
289             return (iterCount < size);
290         }
291 
292         private Entry getFirstHeadFrom(int index) {
293             for(int i = index; i < size; i++) {
294                 if (m_keyTable[i] != null) {
295                     return m_keyTable[i];
296                 }
297             }
298             return null;
299         }
300 
301         public Object   next() {
302             if (hasNext()) {
303                 if (lastEntry != null) {
304                     lastEntry = lastEntry.next;
305                     if (lastEntry == null) {
306                         lastEntry = getFirstHeadFrom(currentIndex++);
307                     }
308                 } else {
309                     lastEntry = getFirstHeadFrom(currentIndex++);
310                 }
311                 if (lastEntry == null) {
312                     throw BindingSupportImpl.getInstance().noSuchElement("");
313                 }
314                 iterCount++;
315                 return lastEntry;
316             } else {
317                 throw BindingSupportImpl.getInstance().noSuchElement("");
318             }
319         }
320     }
321 
322     private abstract class HashIterator implements Iterator   {
323         Entry next;                  // next entry to return
324         int expectedModCount;        // For fast-fail
325         int index;                   // current slot
326         Entry current;               // current entry
327 
328         HashIterator() {
329             expectedModCount = modCount;
330             Entry[] t = m_keyTable;
331             int i = t.length;
332             Entry n = null;
333             if (size != 0) { // advance to first entry
334                 while (i > 0 && (n = t[--i]) == null);
335             }
336             next = n;
337             index = i;
338         }
339 
340         public boolean hasNext() {
341             return next != null;
342         }
343 
344         Entry nextEntry() {
345             if (modCount != expectedModCount)
346                 throw new ConcurrentModificationException  ();
347             Entry e = next;
348             if (e == null)
349                 throw new NoSuchElementException  ();
350 
351             Entry n = e.next;
352             Entry[] t = m_keyTable;
353             int i = index;
354             while (n == null && i > 0) {
355                 n = t[--i];
356             }
357             index = i;
358             next = n;
359             return current = e;
360         }
361 
362         public void remove() {
363         }
364     }
365 
366     private class EntryIterator extends HashIterator {
367         public Object   next() {
368             return nextEntry();
369         }
370     }
371 
372     private class KeyIterator extends HashIterator {
373         public Object   next() {
374             return nextEntry().getKey();
375         }
376     }
377 
378 }
379
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags