|
1
28
29 package org.jruby.util;
30
31 import java.lang.ref.ReferenceQueue  ;
32 import java.lang.ref.WeakReference ;
33 import java.util.Iterator ;
34 import java.util.Map ;
35 import java.util.NoSuchElementException ;
36
37
46 public class WeakIdentityHashMap extends GenericMap implements Map {
47
48 private static final float DEFAULT_RATIO = 0.75F;
49
50 private static final Object NULL_KEY = new Object ();
51
52 private ReferenceQueue queue = new ReferenceQueue ();
53
54 private static Object unmaskKey(Object key) {
55 if (key == NULL_KEY) {
56 return null;
57 } else {
58 return key;
59 }
60 }
61
62 private Object maskKey(Object key) {
63 if (key == null) {
64 return NULL_KEY;
65 } else {
66 return key;
67 }
68 }
69
70 class Entry extends WeakReference implements Map.Entry {
71 Entry next;
72
73 int key_hash;
74
75 Object value;
76
77 public int hashCode() {
78 return key_hash ^ valueHash(getValue());
79 }
80
81 public boolean equals(Object other) {
82 if (other instanceof Map.Entry ) {
83 Map.Entry ent = (Map.Entry ) other;
84 return getKey() == ent.getKey()
85 && valueEquals(getValue(), ent.getValue());
86 } else {
87 return false;
88 }
89 }
90
91 Entry(int key_hash, Object masked_key, Object value, Entry next, ReferenceQueue q) {
92 super(masked_key, q);
93 this.key_hash = key_hash;
94 this.value = value;
95 this.next = next;
96 }
97
98 Object getMaskedKey() {
99 return super.get();
100 }
101
102 public Object getKey() {
103 return unmaskKey(getMaskedKey());
104 }
105
106 public Object getValue() {
107 return value;
108 }
109
110 public Object setValue(Object value) {
111 Object result = this.value;
112 this.value = value;
113 return result;
114 }
115
116 boolean sameKey(int hash, Object masked_key) {
117 return getMaskedKey() == masked_key;
118 }
119 }
120
121
122 private Entry[] table;
123
124
125 private int range;
126
127 private float ratio;
128
129
130 private int index(int hash) {
131 return (hash & 0x7ffffff) % range;
132 }
133
134
135 public WeakIdentityHashMap() {
136 clear();
137 }
138
139 public WeakIdentityHashMap(int size) {
140 clear(Math.max(3, Math.round(size/DEFAULT_RATIO)));
141 }
142
143 public void clear() {
144 clear(3);
145 }
146
147 void clear(int size) {
148 range = size;
149 this.size = 0;
150 ratio = DEFAULT_RATIO;
151 table = new Entry[range];
152 }
153
154 private void expunge() {
155 Entry e;
156 while ((e = (Entry) queue.poll()) != null) {
157 removeEntry(e);
158 }
159 }
160
161
162 public Object get(Object key) {
163 Object masked_key = maskKey(key);
164 int hash = keyHash(masked_key);
165 return get(hash, masked_key);
166 }
167
168 private Object get(int hash, Object masked_key) {
169 int idx = index(hash);
170 expunge();
171 for (Entry ent = table[idx]; ent != null; ent = ent.next) {
172 if (ent.sameKey(hash, masked_key))
173 return ent.value;
174 }
175
176 return null;
177 }
178
179
180 public boolean containsKey(Object key) {
181 Object masked_key = maskKey(key);
182 int hash = keyHash(masked_key);
183 return containsKey(hash, masked_key);
184 }
185
186 private boolean containsKey(int hash, Object masked_key) {
187 int idx = index(hash);
188 expunge();
189 for (Entry ent = table[idx]; ent != null; ent = ent.next) {
190 if (ent.sameKey(hash, masked_key))
191 return true;
192 }
193
194 return false;
195 }
196
197 public Object put(Object key, Object value) {
198 Object masked_key = maskKey(key);
199 int hash = keyHash(masked_key);
200 return put(hash, masked_key, value);
201 }
202
203 private Object put(int hash, Object masked_key, Object value) {
204 int idx = index(hash);
205
206 for (Entry ent = table[idx]; ent != null; ent = ent.next) {
207 if (ent.sameKey(hash, masked_key)) {
208 return ent.setValue(value);
209 }
210 }
211
212 expunge();
213
214 if (1.0F * size / range > ratio) {
215 grow();
216 idx = index(hash);
217 }
218
219 table[idx] = new Entry(hash, masked_key, value, table[idx], queue);
220
221 size += 1;
222
223 return null;
224 }
225
226 public Object remove(Object key) {
227 key = maskKey(key);
228 int hash = keyHash(key);
229 return remove(hash, key);
230 }
231
232 public Object remove(int hash, Object key) {
233 key = maskKey(key);
234 int idx = index(hash);
235
236 Entry entry = table[idx];
237 if (entry != null) {
238
239 if (entry.sameKey(hash, key)) {
240 table[idx] = entry.next;
241 size -= 1;
242 return entry.getValue();
243
244 } else {
245 Entry ahead = entry.next;
246
247 while (ahead != null) {
248 if (ahead.sameKey(hash, key)) {
249 entry.next = ahead.next;
250 size -= 1;
251 return ahead.getValue();
252 }
253
254 entry = ahead;
255 ahead = ahead.next;
256 }
257 }
258 }
259
260 return null;
262 }
263
264 private void removeEntry(Entry ent) {
265 int idx = index(ent.key_hash);
266
267 Entry entry = table[idx];
268 if (entry != null) {
269
270 if (entry == ent) {
271 table[idx] = entry.next;
272 size -= 1;
273 return;
274
275 } else {
276 Entry ahead = entry.next;
277
278 while (ahead != null) {
279 if (ahead == ent) {
280 entry.next = ahead.next;
281 size -= 1;
282 return;
283 }
284
285 entry = ahead;
286 ahead = ahead.next;
287 }
288 }
289 }
290
291 valueRemoved(ent.value);
292 }
293
294 protected void valueRemoved(Object value) {
296 }
297
298 private void grow() {
299 int old_range = range;
300 Entry[] old_table = table;
301
302 range = old_range * 2 + 1;
303 table = new Entry[range];
304
305 for (int i = 0; i < old_range; i++) {
306 Entry entry = old_table[i];
307
308 while (entry != null) {
309 Entry ahead = entry.next;
310 int idx = index(entry.key_hash);
311 entry.next = table[idx];
312 table[idx] = entry;
313 entry = ahead;
314 }
315 }
316 }
317
318 final class EntryIterator implements Iterator {
319 int idx;
320
321 Entry entry;
322
323 EntryIterator() {
324 idx = 0;
325 expunge();
326 entry = table[0];
327 locateNext();
328 }
329
330 private void locateNext() {
331 while (entry == null) {
333 idx += 1;
335 if (idx == range) {
336 return;
338 }
339
340 entry = table[idx];
342 }
343 }
344
345 public boolean hasNext() {
346 return (entry != null);
347 }
348
349 public Object next() {
350 Object result = entry;
351
352 if (result == null) {
353 throw new NoSuchElementException ();
354 } else {
355 entry = entry.next;
356 locateNext();
357 return result;
358 }
359 }
360
361 public void remove() {
362 Entry remove = entry;
363 expunge();
364 entry = entry.next;
365 locateNext();
366
367 WeakIdentityHashMap.this.removeEntry(remove);
368 }
369 }
370
371 protected Iterator entryIterator() {
372 return new EntryIterator();
373 }
374
375 protected final int keyHash(Object key) {
376 return System.identityHashCode(key);
377 }
378
379 protected final boolean keyEquals(Object key1, Object key2) {
380 return key1 == key2;
381 }
382
383 public int size() {
384 expunge();
385 return super.size();
386 }
387
388 public boolean isEmpty() {
389 return size() == 0;
390 }
391 }
392 |
Popular Tags |
Java API By Example, From Geeks To Geeks.