UnifyHash


1   /* UnifyHash Copyright (C) 1999-2002 Jochen Hoenicke.
2    *
3    * This program is free software; you can redistribute it and/or modify
4    * it under the terms of the GNU Lesser General Public License as published by
5    * the Free Software Foundation; either version 2, or (at your option)
6    * any later version.
7    *
8    * This program is distributed in the hope that it will be useful,
9    * but WITHOUT ANY WARRANTY; without even the implied warranty of
10   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11   * GNU General Public License for more details.
12   *
13   * You should have received a copy of the GNU Lesser General Public License
14   * along with this program; see the file COPYING.LESSER.  If not, write to
15   * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
16   *
17   * $Id: UnifyHash.java.in,v 1.3.2.2 2002/05/28 17:34:24 hoenicke Exp $
18   */
19  
20  package jode.util;
21  ///#ifdef JDK12
22  import java.lang.ref.WeakReference  ;
23  import java.lang.ref.ReferenceQueue  ;
24  ///#endif
25  
26  import java.util.Comparator  ;
27  import java.util.AbstractCollection  ;
28  import java.util.Iterator  ;
29  import java.util.NoSuchElementException  ;
30  import java.util.ConcurrentModificationException  ;
31  import java.lang.UnsupportedOperationException  ;
32  
33  public class UnifyHash extends AbstractCollection   {
34      /** 
35       * the default capacity
36       */
37      private static final int DEFAULT_CAPACITY = 11;
38  
39      /** the default load factor of a HashMap */
40      private static final float DEFAULT_LOAD_FACTOR = 0.75F;
41  
42  ///#ifdef JDK12
43      private ReferenceQueue   queue = new ReferenceQueue  ();
44  ///#endif
45  
46      static class Bucket
47  ///#ifdef JDK12
48      extends WeakReference  
49  ///#endif
50      {
51  ///#ifdef JDK12
52      public Bucket(Object   o, ReferenceQueue   q) {
53          super(o, q);
54      }
55  ///#else
56  /// public Bucket(Object o) {
57  ///     this.obj = o;
58  /// }
59  ///
60  /// Object obj;
61  ///
62  /// public Object get() {
63  ///     return obj;
64  /// }
65  ///#endif
66  
67      int hash;
68      Bucket next;
69      }
70  
71      private Bucket[] buckets;
72      int modCount = 0;
73      int size = 0;
74      int threshold;
75      float loadFactor;
76  
77      public UnifyHash(int initialCapacity, float loadFactor) {
78      this.loadFactor = loadFactor;
79      buckets = new Bucket[initialCapacity];
80      threshold = (int) (loadFactor * initialCapacity);
81      }
82  
83      public UnifyHash(int initialCapacity) {
84      this(initialCapacity, DEFAULT_LOAD_FACTOR);
85      }
86  
87      public UnifyHash() {
88      this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
89      }
90  
91      private void grow() {
92      Bucket[] oldBuckets = buckets;
93      int newCap = buckets.length * 2 + 1;
94      threshold = (int) (loadFactor * newCap);
95      buckets = new Bucket[newCap];
96      for (int i = 0; i < oldBuckets.length; i++) {
97          Bucket nextBucket;
98          for (Bucket b = oldBuckets[i]; b != null; b = nextBucket) {
99          if (i != Math.abs(b.hash % oldBuckets.length))
100             throw new RuntimeException  (""+i+", hash: "+b.hash+", oldlength: "+oldBuckets.length);
101         int newSlot = Math.abs(b.hash % newCap);
102         nextBucket = b.next;
103         b.next = buckets[newSlot];
104         buckets[newSlot] = b;
105         }
106     }
107     }
108 
109 ///#ifdef JDK12
110     public final void cleanUp() {
111     Bucket died;
112     while ((died = (Bucket)queue.poll()) != null) {
113         int diedSlot = Math.abs(died.hash % buckets.length);
114         if (buckets[diedSlot] == died)
115         buckets[diedSlot] = died.next;
116         else {
117         Bucket b = buckets[diedSlot];
118         while (b.next != died)
119             b = b.next;
120         b.next = died.next;
121         }
122         size--;
123     }
124     }
125 ///#endif
126 
127 
128     public int size() {
129     return size;
130     }
131 
132     public Iterator   iterator() {
133 ///#ifdef JDK12
134     cleanUp();
135 ///#endif
136 
137     return new Iterator  () {
138         private int bucket = 0;
139         private int known = modCount;
140         private Bucket nextBucket;
141         private Object   nextVal;
142 
143         {
144         internalNext();
145         }
146 
147         private void internalNext() {
148         while (true) {
149             while (nextBucket == null) {
150             if (bucket == buckets.length)
151                 return;
152             nextBucket = buckets[bucket++];
153             }
154             
155             nextVal = nextBucket.get();
156             if (nextVal != null)
157             return;
158 
159             nextBucket = nextBucket.next;
160         }
161         }
162 
163         public boolean hasNext() {
164         return nextBucket != null;
165         }
166 
167         public Object   next() {
168         if (known != modCount)
169             throw new ConcurrentModificationException  ();
170         if (nextBucket == null)
171             throw new NoSuchElementException  ();
172         Object   result = nextVal;
173         nextBucket = nextBucket.next;
174         internalNext();
175         return result;
176         }
177 
178         public void remove() {
179         throw new UnsupportedOperationException  ();
180         }
181     };
182     }
183 
184     public Iterator   iterateHashCode(final int hash) {
185 ///#ifdef JDK12
186     cleanUp();
187 ///#endif
188     return new Iterator  () {
189         private int known = modCount;
190         private Bucket nextBucket
191         = buckets[Math.abs(hash % buckets.length)];
192         private Object   nextVal;
193 
194         {
195         internalNext();
196         }
197 
198         private void internalNext() {
199         while (nextBucket != null) {
200             if (nextBucket.hash == hash) {
201             nextVal = nextBucket.get();
202             if (nextVal != null)
203                 return;
204             }
205 
206             nextBucket = nextBucket.next;
207         }
208         }
209 
210         public boolean hasNext() {
211         return nextBucket != null;
212         }
213 
214         public Object   next() {
215         if (known != modCount)
216             throw new ConcurrentModificationException  ();
217         if (nextBucket == null)
218             throw new NoSuchElementException  ();
219         Object   result = nextVal;
220         nextBucket = nextBucket.next;
221         internalNext();
222         return result;
223         }
224 
225         public void remove() {
226         throw new UnsupportedOperationException  ();
227         }
228     };
229     }
230 
231     public void put(int hash, Object   o) {
232     if (size++ > threshold)
233         grow();
234     modCount++;
235 
236     int slot = Math.abs(hash % buckets.length);
237 ///#ifdef JDK12
238     Bucket b = new Bucket(o, queue);
239 ///#else
240 /// Bucket b = new Bucket(o);
241 ///#endif
242     b.hash = hash;
243     b.next = buckets[slot];
244     buckets[slot] = b;
245     }
246 
247     public Object   unify(Object   o, int hash, Comparator   comparator) {
248 ///#ifdef JDK12
249     cleanUp();
250 ///#endif
251     int slot = Math.abs(hash % buckets.length);
252     for (Bucket b = buckets[slot]; b != null; b = b.next) {
253         Object   old = b.get();
254         if (old != null && comparator.compare(o, old) == 0)
255         return old;
256     }
257 
258     put(hash, o);
259     return o;
260     }
261 }
262 
263
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags