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