|
|||||||||||||||||||
Source file | Conditionals | Statements | Methods | TOTAL | |||||||||||||||
ConcurrentReaderHashMap.java | 25,4% | 28% | 17,5% | 26% |
|
1 | /* | |
2 | File: ConcurrentReaderHashMap | |
3 | ||
4 | Written by Doug Lea. Adapted and released, under explicit | |
5 | permission, from JDK1.2 HashMap.java and Hashtable.java which | |
6 | carries the following copyright: | |
7 | ||
8 | * Copyright 1997 by Sun Microsystems, Inc., | |
9 | * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. | |
10 | * All rights reserved. | |
11 | * | |
12 | * This software is the confidential and proprietary information | |
13 | * of Sun Microsystems, Inc. ("Confidential Information"). You | |
14 | * shall not disclose such Confidential Information and shall use | |
15 | * it only in accordance with the terms of the license agreement | |
16 | * you entered into with Sun. | |
17 | ||
18 | History: | |
19 | Date Who What | |
20 | 28oct1999 dl Created | |
21 | 14dec1999 dl jmm snapshot | |
22 | 19apr2000 dl use barrierLock | |
23 | 12jan2001 dl public release | |
24 | 17nov2001 dl Minor tunings | |
25 | 20may2002 dl BarrierLock can now be serialized. | |
26 | 09dec2002 dl Fix interference checks. | |
27 | */ | |
28 | ||
29 | package org.dom4j.tree; | |
30 | ||
31 | import java.io.IOException; | |
32 | import java.io.Serializable; | |
33 | import java.util.AbstractCollection; | |
34 | import java.util.AbstractMap; | |
35 | import java.util.AbstractSet; | |
36 | import java.util.Collection; | |
37 | import java.util.Enumeration; | |
38 | import java.util.Iterator; | |
39 | import java.util.Map; | |
40 | import java.util.NoSuchElementException; | |
41 | import java.util.Set; | |
42 | ||
43 | ||
44 | /** | |
45 | * A version of Hashtable that supports mostly-concurrent reading, but | |
46 | * exclusive writing. Because reads are not limited to periods | |
47 | * without writes, a concurrent reader policy is weaker than a classic | |
48 | * reader/writer policy, but is generally faster and allows more | |
49 | * concurrency. This class is a good choice especially for tables that | |
50 | * are mainly created by one thread during the start-up phase of a | |
51 | * program, and from then on, are mainly read (with perhaps occasional | |
52 | * additions or removals) in many threads. If you also need concurrency | |
53 | * among writes, consider instead using ConcurrentHashMap. | |
54 | * <p> | |
55 | * | |
56 | * Successful retrievals using get(key) and containsKey(key) usually | |
57 | * run without locking. Unsuccessful ones (i.e., when the key is not | |
58 | * present) do involve brief synchronization (locking). Also, the | |
59 | * size and isEmpty methods are always synchronized. | |
60 | * | |
61 | * <p> Because retrieval operations can ordinarily overlap with | |
62 | * writing operations (i.e., put, remove, and their derivatives), | |
63 | * retrievals can only be guaranteed to return the results of the most | |
64 | * recently <em>completed</em> operations holding upon their | |
65 | * onset. Retrieval operations may or may not return results | |
66 | * reflecting in-progress writing operations. However, the retrieval | |
67 | * operations do always return consistent results -- either those | |
68 | * holding before any single modification or after it, but never a | |
69 | * nonsense result. For aggregate operations such as putAll and | |
70 | * clear, concurrent reads may reflect insertion or removal of only | |
71 | * some entries. In those rare contexts in which you use a hash table | |
72 | * to synchronize operations across threads (for example, to prevent | |
73 | * reads until after clears), you should either encase operations | |
74 | * in synchronized blocks, or instead use java.util.Hashtable. | |
75 | * | |
76 | * <p> | |
77 | * | |
78 | * This class also supports optional guaranteed | |
79 | * exclusive reads, simply by surrounding a call within a synchronized | |
80 | * block, as in <br> | |
81 | * <code>ConcurrentReaderHashMap t; ... Object v; <br> | |
82 | * synchronized(t) { v = t.get(k); } </code> <br> | |
83 | * | |
84 | * But this is not usually necessary in practice. For | |
85 | * example, it is generally inefficient to write: | |
86 | * | |
87 | * <pre> | |
88 | * ConcurrentReaderHashMap t; ... // Inefficient version | |
89 | * Object key; ... | |
90 | * Object value; ... | |
91 | * synchronized(t) { | |
92 | * if (!t.containsKey(key)) | |
93 | * t.put(key, value); | |
94 | * // other code if not previously present | |
95 | * } | |
96 | * else { | |
97 | * // other code if it was previously present | |
98 | * } | |
99 | * } | |
100 | *</pre> | |
101 | * Instead, if the values are intended to be the same in each case, just take advantage of the fact that put returns | |
102 | * null if the key was not previously present: | |
103 | * <pre> | |
104 | * ConcurrentReaderHashMap t; ... // Use this instead | |
105 | * Object key; ... | |
106 | * Object value; ... | |
107 | * Object oldValue = t.put(key, value); | |
108 | * if (oldValue == null) { | |
109 | * // other code if not previously present | |
110 | * } | |
111 | * else { | |
112 | * // other code if it was previously present | |
113 | * } | |
114 | *</pre> | |
115 | * <p> | |
116 | * | |
117 | * Iterators and Enumerations (i.e., those returned by | |
118 | * keySet().iterator(), entrySet().iterator(), values().iterator(), | |
119 | * keys(), and elements()) return elements reflecting the state of the | |
120 | * hash table at some point at or since the creation of the | |
121 | * iterator/enumeration. They will return at most one instance of | |
122 | * each element (via next()/nextElement()), but might or might not | |
123 | * reflect puts and removes that have been processed since they were | |
124 | * created. They do <em>not</em> throw ConcurrentModificationException. | |
125 | * However, these iterators are designed to be used by only one | |
126 | * thread at a time. Sharing an iterator across multiple threads may | |
127 | * lead to unpredictable results if the table is being concurrently | |
128 | * modified. Again, you can ensure interference-free iteration by | |
129 | * enclosing the iteration in a synchronized block. <p> | |
130 | * | |
131 | * This class may be used as a direct replacement for any use of | |
132 | * java.util.Hashtable that does not depend on readers being blocked | |
133 | * during updates. Like Hashtable but unlike java.util.HashMap, | |
134 | * this class does NOT allow <tt>null</tt> to be used as a key or | |
135 | * value. This class is also typically faster than ConcurrentHashMap | |
136 | * when there is usually only one thread updating the table, but | |
137 | * possibly many retrieving values from it. | |
138 | * <p> | |
139 | * | |
140 | * Implementation note: A slightly faster implementation of | |
141 | * this class will be possible once planned Java Memory Model | |
142 | * revisions are in place. | |
143 | * | |
144 | * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] | |
145 | ||
146 | **/ | |
147 | ||
148 | ||
149 | class ConcurrentReaderHashMap | |
150 | extends AbstractMap | |
151 | implements Map, Cloneable, Serializable { | |
152 | ||
153 | ||
154 | /* | |
155 | The basic strategy is an optimistic-style scheme based on | |
156 | the guarantee that the hash table and its lists are always | |
157 | kept in a consistent enough state to be read without locking: | |
158 | ||
159 | * Read operations first proceed without locking, by traversing the | |
160 | apparently correct list of the apparently correct bin. If an | |
161 | entry is found, but not invalidated (value field null), it is | |
162 | returned. If not found, operations must recheck (after a memory | |
163 | barrier) to make sure they are using both the right list and | |
164 | the right table (which can change under resizes). If | |
165 | invalidated, reads must acquire main update lock to wait out | |
166 | the update, and then re-traverse. | |
167 | ||
168 | * All list additions are at the front of each bin, making it easy | |
169 | to check changes, and also fast to traverse. Entry next | |
170 | pointers are never assigned. Remove() builds new nodes when | |
171 | necessary to preserve this. | |
172 | ||
173 | * Remove() (also clear()) invalidates removed nodes to alert read | |
174 | operations that they must wait out the full modifications. | |
175 | ||
176 | */ | |
177 | ||
178 | /** A Serializable class for barrier lock **/ | |
179 | protected static class BarrierLock implements java.io.Serializable { } | |
180 | ||
181 | /** | |
182 | * Lock used only for its memory effects. | |
183 | **/ | |
184 | protected final BarrierLock barrierLock = new BarrierLock(); | |
185 | ||
186 | /** | |
187 | * field written to only to guarantee lock ordering. | |
188 | **/ | |
189 | ||
190 | protected transient Object lastWrite; | |
191 | ||
192 | /** | |
193 | * Force a memory synchronization that will cause | |
194 | * all readers to see table. Call only when already | |
195 | * holding main synch lock. | |
196 | **/ | |
197 | 41150 | protected final void recordModification(Object x) { |
198 | 41150 | synchronized(barrierLock) { |
199 | 41150 | lastWrite = x; |
200 | } | |
201 | } | |
202 | ||
203 | /** | |
204 | * Get ref to table; the reference and the cells it | |
205 | * accesses will be at least as fresh as from last | |
206 | * use of barrierLock | |
207 | **/ | |
208 | 82300 | protected final Entry[] getTableForReading() { |
209 | 82300 | synchronized(barrierLock) { |
210 | 82300 | return table; |
211 | } | |
212 | } | |
213 | ||
214 | ||
215 | /** | |
216 | * The default initial number of table slots for this table (32). | |
217 | * Used when not otherwise specified in constructor. | |
218 | **/ | |
219 | public static int DEFAULT_INITIAL_CAPACITY = 32; | |
220 | ||
221 | ||
222 | /** | |
223 | * The minimum capacity, used if a lower value is implicitly specified | |
224 | * by either of the constructors with arguments. | |
225 | * MUST be a power of two. | |
226 | */ | |
227 | private static final int MINIMUM_CAPACITY = 4; | |
228 | ||
229 | /** | |
230 | * The maximum capacity, used if a higher value is implicitly specified | |
231 | * by either of the constructors with arguments. | |
232 | * MUST be a power of two <= 1<<30. | |
233 | */ | |
234 | private static final int MAXIMUM_CAPACITY = 1 << 30; | |
235 | ||
236 | /** | |
237 | * The default load factor for this table (1.0). | |
238 | * Used when not otherwise specified in constructor. | |
239 | **/ | |
240 | ||
241 | public static final float DEFAULT_LOAD_FACTOR = 0.75f; | |
242 | ||
243 | ||
244 | /** | |
245 | * The hash table data. | |
246 | */ | |
247 | protected transient Entry[] table; | |
248 | ||
249 | /** | |
250 | * The total number of mappings in the hash table. | |
251 | */ | |
252 | protected transient int count; | |
253 | ||
254 | /** | |
255 | * The table is rehashed when its size exceeds this threshold. (The | |
256 | * value of this field is always (int)(capacity * loadFactor).) | |
257 | * | |
258 | * @serial | |
259 | */ | |
260 | protected int threshold; | |
261 | ||
262 | /** | |
263 | * The load factor for the hash table. | |
264 | * | |
265 | * @serial | |
266 | */ | |
267 | protected float loadFactor; | |
268 | ||
269 | /** | |
270 | * Returns the appropriate capacity (power of two) for the specified | |
271 | * initial capacity argument. | |
272 | */ | |
273 | 20878 | private int p2capacity(int initialCapacity) { |
274 | 20878 | int cap = initialCapacity; |
275 | ||
276 | // Compute the appropriate capacity | |
277 | 20878 | int result; |
278 | 20878 | if (cap > MAXIMUM_CAPACITY || cap < 0) { |
279 | 0 | result = MAXIMUM_CAPACITY; |
280 | } else { | |
281 | 20878 | result = MINIMUM_CAPACITY; |
282 | 20878 | while (result < cap) |
283 | 62634 | result <<= 1; |
284 | } | |
285 | 20878 | return result; |
286 | } | |
287 | ||
288 | /** | |
289 | * Return hash code for Object x. Since we are using power-of-two | |
290 | * tables, it is worth the effort to improve hashcode via | |
291 | * the same multiplicative scheme as used in IdentityHashMap. | |
292 | */ | |
293 | 4558360 | private static int hash(Object x) { |
294 | 4558360 | int h = x.hashCode(); |
295 | // Multiply by 127 (quickly, via shifts), and mix in some high | |
296 | // bits to help guard against bunching of codes that are | |
297 | // consecutive or equally spaced. | |
298 | 4558360 | return ((h << 7) - h + (h >>> 9) + (h >>> 17)); |
299 | } | |
300 | ||
301 | /** | |
302 | * Check for equality of non-null references x and y. | |
303 | **/ | |
304 | 4434910 | protected boolean eq(Object x, Object y) { |
305 | 4434910 | return x == y || x.equals(y); |
306 | } | |
307 | ||
308 | /** | |
309 | * Constructs a new, empty map with the specified initial | |
310 | * capacity and the specified load factor. | |
311 | * | |
312 | * @param initialCapacity the initial capacity | |
313 | * The actual initial capacity is rounded to the nearest power of two. | |
314 | * @param loadFactor the load factor of the ConcurrentReaderHashMap | |
315 | * @throws IllegalArgumentException if the initial maximum number | |
316 | * of elements is less | |
317 | * than zero, or if the load factor is nonpositive. | |
318 | */ | |
319 | ||
320 | 20878 | public ConcurrentReaderHashMap(int initialCapacity, float loadFactor) { |
321 | 20878 | if (loadFactor <= 0) |
322 | 0 | throw new IllegalArgumentException("Illegal Load factor: "+ |
323 | loadFactor); | |
324 | 20878 | this.loadFactor = loadFactor; |
325 | ||
326 | 20878 | int cap = p2capacity(initialCapacity); |
327 | ||
328 | 20878 | table = new Entry[cap]; |
329 | 20878 | threshold = (int)(cap * loadFactor); |
330 | } | |
331 | ||
332 | /** | |
333 | * Constructs a new, empty map with the specified initial | |
334 | * capacity and default load factor. | |
335 | * | |
336 | * @param initialCapacity the initial capacity of the | |
337 | * ConcurrentReaderHashMap. | |
338 | * @throws IllegalArgumentException if the initial maximum number | |
339 | * of elements is less | |
340 | * than zero. | |
341 | */ | |
342 | ||
343 | 0 | public ConcurrentReaderHashMap(int initialCapacity) { |
344 | 0 | this(initialCapacity, DEFAULT_LOAD_FACTOR); |
345 | } | |
346 | ||
347 | /** | |
348 | * Constructs a new, empty map with a default initial capacity | |
349 | * and load factor. | |
350 | */ | |
351 | ||
352 | 20878 | public ConcurrentReaderHashMap() { |
353 | 20878 | this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); |
354 | } | |
355 | ||
356 | /** | |
357 | * Constructs a new map with the same mappings as the given map. The | |
358 | * map is created with a capacity of twice the number of mappings in | |
359 | * the given map or 16 (whichever is greater), and a default load factor. | |
360 | */ | |
361 | ||
362 | 0 | public ConcurrentReaderHashMap(Map t) { |
363 | 0 | this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16), |
364 | DEFAULT_LOAD_FACTOR); | |
365 | 0 | putAll(t); |
366 | } | |
367 | ||
368 | /** | |
369 | * Returns the number of key-value mappings in this map. | |
370 | * | |
371 | * @return the number of key-value mappings in this map. | |
372 | */ | |
373 | ||
374 | 0 | public synchronized int size() { |
375 | 0 | return count; |
376 | } | |
377 | ||
378 | /** | |
379 | * Returns <tt>true</tt> if this map contains no key-value mappings. | |
380 | * | |
381 | * @return <tt>true</tt> if this map contains no key-value mappings. | |
382 | */ | |
383 | ||
384 | 0 | public synchronized boolean isEmpty() { |
385 | 0 | return count == 0; |
386 | } | |
387 | ||
388 | ||
389 | ||
390 | /** | |
391 | * Returns the value to which the specified key is mapped in this table. | |
392 | * | |
393 | * @param key a key in the table. | |
394 | * @return the value to which the key is mapped in this table; | |
395 | * <code>null</code> if the key is not mapped to any value in | |
396 | * this table. | |
397 | * @exception NullPointerException if the key is | |
398 | * <code>null</code>. | |
399 | * @see #put(Object, Object) | |
400 | */ | |
401 | ||
402 | ||
403 | 4517210 | public Object get(Object key) { |
404 | ||
405 | // throw null pointer exception if key null | |
406 | 4517210 | int hash = hash(key); |
407 | ||
408 | /* | |
409 | Start off at the apparently correct bin. If entry is found, we | |
410 | need to check after a barrier anyway. If not found, we need a | |
411 | barrier to check if we are actually in right bin. So either | |
412 | way, we encounter only one barrier unless we need to retry. | |
413 | And we only need to fully synchronize if there have been | |
414 | concurrent modifications. | |
415 | */ | |
416 | ||
417 | 4517210 | Entry[] tab = table; |
418 | 4517210 | int index = hash & (tab.length - 1); |
419 | 4517210 | Entry first = tab[index]; |
420 | 4517210 | Entry e = first; |
421 | ||
422 | 4517210 | for (;;) { |
423 | 4536134 | if (e == null) { |
424 | ||
425 | // If key apparently not there, check to | |
426 | // make sure this was a valid read | |
427 | ||
428 | 82300 | Entry[] reread = getTableForReading(); |
429 | 82300 | if (tab == reread && first == tab[index]) |
430 | 82300 | return null; |
431 | else { | |
432 | // Wrong list -- must restart traversal at new first | |
433 | 0 | tab = reread; |
434 | 0 | e = first = tab[index = hash & (tab.length-1)]; |
435 | } | |
436 | ||
437 | } | |
438 | ||
439 | 4453878 | else if (e.hash == hash && eq(key, e.key)) { |
440 | 4434910 | Object value = e.value; |
441 | 4434910 | if (value != null) |
442 | 4434910 | return value; |
443 | ||
444 | // Entry was invalidated during deletion. But it could | |
445 | // have been re-inserted, so we must retraverse. | |
446 | // To avoid useless contention, get lock to wait out modifications | |
447 | // before retraversing. | |
448 | ||
449 | 0 | synchronized(this) { |
450 | 0 | tab = table; |
451 | } | |
452 | 0 | e = first = tab[index = hash & (tab.length-1)]; |
453 | ||
454 | } | |
455 | else | |
456 | 18968 | e = e.next; |
457 | } | |
458 | } | |
459 | ||
460 | ||
461 | /** | |
462 | * Tests if the specified object is a key in this table. | |
463 | * | |
464 | * @param key possible key. | |
465 | * @return <code>true</code> if and only if the specified object | |
466 | * is a key in this table, as determined by the | |
467 | * <tt>equals</tt> method; <code>false</code> otherwise. | |
468 | * @exception NullPointerException if the key is | |
469 | * <code>null</code>. | |
470 | * @see #contains(Object) | |
471 | */ | |
472 | ||
473 | ||
474 | 0 | public boolean containsKey(Object key) { |
475 | 0 | return get(key) != null; |
476 | } | |
477 | ||
478 | /** | |
479 | * Maps the specified <code>key</code> to the specified | |
480 | * <code>value</code> in this table. Neither the key nor the | |
481 | * value can be <code>null</code>. <p> | |
482 | * | |
483 | * The value can be retrieved by calling the <code>get</code> method | |
484 | * with a key that is equal to the original key. | |
485 | * | |
486 | * @param key the table key. | |
487 | * @param value the value. | |
488 | * @return the previous value of the specified key in this table, | |
489 | * or <code>null</code> if it did not have one. | |
490 | * @exception NullPointerException if the key or value is | |
491 | * <code>null</code>. | |
492 | * @see Object#equals(Object) | |
493 | * @see #get(Object) | |
494 | */ | |
495 | ||
496 | 41150 | public Object put(Object key, Object value) { |
497 | 41150 | if (value == null) |
498 | 0 | throw new NullPointerException(); |
499 | ||
500 | 41150 | int hash = hash(key); |
501 | 41150 | Entry[] tab = table; |
502 | 41150 | int index = hash & (tab.length-1); |
503 | 41150 | Entry first = tab[index]; |
504 | 41150 | Entry e; |
505 | ||
506 | 41150 | for (e = first; e != null; e = e.next) |
507 | 8564 | if (e.hash == hash && eq(key, e.key)) |
508 | 0 | break; |
509 | ||
510 | 41150 | synchronized(this) { |
511 | 41150 | if (tab == table) { |
512 | 41150 | if (e == null) { |
513 | // make sure we are adding to correct list | |
514 | 41150 | if (first == tab[index]) { |
515 | // Add to front of list | |
516 | 41150 | Entry newEntry = new Entry(hash, key, value, first); |
517 | 41150 | tab[index] = newEntry; |
518 | 18 | if (++count >= threshold) rehash(); |
519 | 41132 | else recordModification(newEntry); |
520 | 41150 | return null; |
521 | } | |
522 | } | |
523 | else { | |
524 | 0 | Object oldValue = e.value; |
525 | 0 | if (first == tab[index] && oldValue != null) { |
526 | 0 | e.value = value; |
527 | 0 | return oldValue; |
528 | } | |
529 | } | |
530 | } | |
531 | ||
532 | // retry if wrong list or lost race against concurrent remove | |
533 | 0 | return sput(key, value, hash); |
534 | } | |
535 | } | |
536 | ||
537 | ||
538 | /** | |
539 | * Continuation of put(), called only when synch lock is | |
540 | * held and interference has been detected. | |
541 | **/ | |
542 | 0 | protected Object sput(Object key, Object value, int hash) { |
543 | ||
544 | 0 | Entry[] tab = table; |
545 | 0 | int index = hash & (tab.length-1); |
546 | 0 | Entry first = tab[index]; |
547 | 0 | Entry e = first; |
548 | ||
549 | 0 | for (;;) { |
550 | 0 | if (e == null) { |
551 | 0 | Entry newEntry = new Entry(hash, key, value, first); |
552 | 0 | tab[index] = newEntry; |
553 | 0 | if (++count >= threshold) rehash(); |
554 | 0 | else recordModification(newEntry); |
555 | 0 | return null; |
556 | } | |
557 | 0 | else if (e.hash == hash && eq(key, e.key)) { |
558 | 0 | Object oldValue = e.value; |
559 | 0 | e.value = value; |
560 | 0 | return oldValue; |
561 | } | |
562 | else | |
563 | 0 | e = e.next; |
564 | } | |
565 | } | |
566 | ||
567 | ||
568 | /** | |
569 | * Rehashes the contents of this map into a new table | |
570 | * with a larger capacity. This method is called automatically when the | |
571 | * number of keys in this map exceeds its capacity and load factor. | |
572 | */ | |
573 | 18 | protected void rehash() { |
574 | 18 | Entry[] oldTable = table; |
575 | 18 | int oldCapacity = oldTable.length; |
576 | 18 | if (oldCapacity >= MAXIMUM_CAPACITY) { |
577 | 0 | threshold = Integer.MAX_VALUE; // avoid retriggering |
578 | 0 | return; |
579 | } | |
580 | ||
581 | 18 | int newCapacity = oldCapacity << 1; |
582 | 18 | int mask = newCapacity - 1; |
583 | 18 | threshold = (int)(newCapacity * loadFactor); |
584 | ||
585 | 18 | Entry[] newTable = new Entry[newCapacity]; |
586 | /* | |
587 | * Reclassify nodes in each list to new Map. Because we are | |
588 | * using power-of-two expansion, the elements from each bin | |
589 | * must either stay at same index, or move to | |
590 | * oldCapacity+index. We also eliminate unnecessary node | |
591 | * creation by catching cases where old nodes can be reused | |
592 | * because their next fields won't change. Statistically, at | |
593 | * the default threshhold, only about one-sixth of them need | |
594 | * cloning. (The nodes they replace will be garbage | |
595 | * collectable as soon as they are no longer referenced by any | |
596 | * reader thread that may be in the midst of traversing table | |
597 | * right now.) | |
598 | */ | |
599 | ||
600 | 18 | for (int i = 0; i < oldCapacity ; i++) { |
601 | // We need to guarantee that any existing reads of old Map can | |
602 | // proceed. So we cannot yet null out each bin. | |
603 | 32704 | Entry e = oldTable[i]; |
604 | ||
605 | 32704 | if (e != null) { |
606 | 17642 | int idx = e.hash & mask; |
607 | 17642 | Entry next = e.next; |
608 | ||
609 | // Single node on list | |
610 | 17642 | if (next == null) |
611 | 11960 | newTable[idx] = e; |
612 | ||
613 | else { | |
614 | // Reuse trailing consecutive sequence of all same bit | |
615 | 5682 | Entry lastRun = e; |
616 | 5682 | int lastIdx = idx; |
617 | 5682 | for (Entry last = next; last != null; last = last.next) { |
618 | 6886 | int k = last.hash & mask; |
619 | 6886 | if (k != lastIdx) { |
620 | 3842 | lastIdx = k; |
621 | 3842 | lastRun = last; |
622 | } | |
623 | } | |
624 | 5682 | newTable[lastIdx] = lastRun; |
625 | ||
626 | // Clone all remaining nodes | |
627 | 5682 | for (Entry p = e; p != lastRun; p = p.next) { |
628 | 4232 | int k = p.hash & mask; |
629 | 4232 | newTable[k] = new Entry(p.hash, p.key, |
630 | p.value, newTable[k]); | |
631 | } | |
632 | } | |
633 | } | |
634 | } | |
635 | ||
636 | 18 | table = newTable; |
637 | 18 | recordModification(newTable); |
638 | } | |
639 | ||
640 | /** | |
641 | * Removes the key (and its corresponding value) from this | |
642 | * table. This method does nothing if the key is not in the table. | |
643 | * | |
644 | * @param key the key that needs to be removed. | |
645 | * @return the value to which the key had been mapped in this table, | |
646 | * or <code>null</code> if the key did not have a mapping. | |
647 | * @exception NullPointerException if the key is | |
648 | * <code>null</code>. | |
649 | */ | |
650 | ||
651 | 0 | public Object remove(Object key) { |
652 | /* | |
653 | Find the entry, then | |
654 | 1. Set value field to null, to force get() to retry | |
655 | 2. Rebuild the list without this entry. | |
656 | All entries following removed node can stay in list, but | |
657 | all preceeding ones need to be cloned. Traversals rely | |
658 | on this strategy to ensure that elements will not be | |
659 | repeated during iteration. | |
660 | */ | |
661 | ||
662 | ||
663 | 0 | int hash = hash(key); |
664 | 0 | Entry[] tab = table; |
665 | 0 | int index = hash & (tab.length-1); |
666 | 0 | Entry first = tab[index]; |
667 | 0 | Entry e = first; |
668 | ||
669 | 0 | for (e = first; e != null; e = e.next) |
670 | 0 | if (e.hash == hash && eq(key, e.key)) |
671 | 0 | break; |
672 | ||
673 | ||
674 | 0 | synchronized(this) { |
675 | 0 | if (tab == table) { |
676 | 0 | if (e == null) { |
677 | 0 | if (first == tab[index]) |
678 | 0 | return null; |
679 | } | |
680 | else { | |
681 | 0 | Object oldValue = e.value; |
682 | 0 | if (first == tab[index] && oldValue != null) { |
683 | 0 | e.value = null; |
684 | 0 | count--; |
685 | ||
686 | 0 | Entry head = e.next; |
687 | 0 | for (Entry p = first; p != e; p = p.next) |
688 | 0 | head = new Entry(p.hash, p.key, p.value, head); |
689 | ||
690 | 0 | tab[index] = head; |
691 | 0 | recordModification(head); |
692 | 0 | return oldValue; |
693 | } | |
694 | } | |
695 | } | |
696 | ||
697 | // Wrong list or interference | |
698 | 0 | return sremove(key, hash); |
699 | } | |
700 | } | |
701 | ||
702 | /** | |
703 | * Continuation of remove(), called only when synch lock is | |
704 | * held and interference has been detected. | |
705 | **/ | |
706 | ||
707 | 0 | protected Object sremove(Object key, int hash) { |
708 | 0 | Entry[] tab = table; |
709 | 0 | int index = hash & (tab.length-1); |
710 | 0 | Entry first = tab[index]; |
711 | ||
712 | 0 | for (Entry e = first; e != null; e = e.next) { |
713 | 0 | if (e.hash == hash && eq(key, e.key)) { |
714 | 0 | Object oldValue = e.value; |
715 | 0 | e.value = null; |
716 | 0 | count--; |
717 | 0 | Entry head = e.next; |
718 | 0 | for (Entry p = first; p != e; p = p.next) |
719 | 0 | head = new Entry(p.hash, p.key, p.value, head); |
720 | ||
721 | 0 | tab[index] = head; |
722 | 0 | recordModification(head); |
723 | 0 | return oldValue; |
724 | } | |
725 | } | |
726 | 0 | return null; |
727 | } | |
728 | ||
729 | ||
730 | /** | |
731 | * Returns <tt>true</tt> if this map maps one or more keys to the | |
732 | * specified value. Note: This method requires a full internal | |
733 | * traversal of the hash table, and so is much slower than | |
734 | * method <tt>containsKey</tt>. | |
735 | * | |
736 | * @param value value whose presence in this map is to be tested. | |
737 | * @return <tt>true</tt> if this map maps one or more keys to the | |
738 | * specified value. | |
739 | * @exception NullPointerException if the value is <code>null</code>. | |
740 | */ | |
741 | ||
742 | 0 | public boolean containsValue(Object value) { |
743 | 0 | if (value == null) throw new NullPointerException(); |
744 | ||
745 | 0 | Entry tab[] = getTableForReading(); |
746 | ||
747 | 0 | for (int i = 0 ; i < tab.length; ++i) { |
748 | 0 | for (Entry e = tab[i] ; e != null ; e = e.next) |
749 | 0 | if (value.equals(e.value)) |
750 | 0 | return true; |
751 | } | |
752 | ||
753 | 0 | return false; |
754 | } | |
755 | ||
756 | /** | |
757 | * Tests if some key maps into the specified value in this table. | |
758 | * This operation is more expensive than the <code>containsKey</code> | |
759 | * method.<p> | |
760 | * | |
761 | * Note that this method is identical in functionality to containsValue, | |
762 | * (which is part of the Map interface in the collections framework). | |
763 | * | |
764 | * @param value a value to search for. | |
765 | * @return <code>true</code> if and only if some key maps to the | |
766 | * <code>value</code> argument in this table as | |
767 | * determined by the <tt>equals</tt> method; | |
768 | * <code>false</code> otherwise. | |
769 | * @exception NullPointerException if the value is <code>null</code>. | |
770 | * @see #containsKey(Object) | |
771 | * @see #containsValue(Object) | |
772 | * @see Map | |
773 | */ | |
774 | ||
775 | 0 | public boolean contains(Object value) { |
776 | 0 | return containsValue(value); |
777 | } | |
778 | ||
779 | ||
780 | /** | |
781 | * Copies all of the mappings from the specified map to this one. | |
782 | * | |
783 | * These mappings replace any mappings that this map had for any of the | |
784 | * keys currently in the specified Map. | |
785 | * | |
786 | * @param t Mappings to be stored in this map. | |
787 | */ | |
788 | ||
789 | 0 | public synchronized void putAll(Map t) { |
790 | 0 | int n = t.size(); |
791 | 0 | if (n == 0) |
792 | 0 | return; |
793 | ||
794 | // Expand enough to hold at least n elements without resizing. | |
795 | // We can only resize table by factor of two at a time. | |
796 | // It is faster to rehash with fewer elements, so do it now. | |
797 | 0 | while (n >= threshold) |
798 | 0 | rehash(); |
799 | ||
800 | 0 | for (Iterator it = t.entrySet().iterator(); it.hasNext();) { |
801 | 0 | Map.Entry entry = (Map.Entry) it.next(); |
802 | 0 | Object key = entry.getKey(); |
803 | 0 | Object value = entry.getValue(); |
804 | 0 | put(key, value); |
805 | } | |
806 | } | |
807 | ||
808 | ||
809 | /** | |
810 | * Removes all mappings from this map. | |
811 | */ | |
812 | 0 | public synchronized void clear() { |
813 | 0 | Entry tab[] = table; |
814 | 0 | for (int i = 0; i < tab.length ; ++i) { |
815 | ||
816 | // must invalidate all to force concurrent get's to wait and then retry | |
817 | 0 | for (Entry e = tab[i]; e != null; e = e.next) |
818 | 0 | e.value = null; |
819 | ||
820 | 0 | tab[i] = null; |
821 | } | |
822 | 0 | count = 0; |
823 | 0 | recordModification(tab); |
824 | } | |
825 | ||
826 | /** | |
827 | * Returns a shallow copy of this | |
828 | * <tt>ConcurrentReaderHashMap</tt> instance: the keys and | |
829 | * values themselves are not cloned. | |
830 | * | |
831 | * @return a shallow copy of this map. | |
832 | */ | |
833 | ||
834 | 0 | public synchronized Object clone() { |
835 | 0 | try { |
836 | 0 | ConcurrentReaderHashMap t = (ConcurrentReaderHashMap)super.clone(); |
837 | ||
838 | 0 | t.keySet = null; |
839 | 0 | t.entrySet = null; |
840 | 0 | t.values = null; |
841 | ||
842 | 0 | Entry[] tab = table; |
843 | 0 | t.table = new Entry[tab.length]; |
844 | 0 | Entry[] ttab = t.table; |
845 | ||
846 | 0 | for (int i = 0; i < tab.length; ++i) { |
847 | 0 | Entry first = null; |
848 | 0 | for (Entry e = tab[i]; e != null; e = e.next) |
849 | 0 | first = new Entry(e.hash, e.key, e.value, first); |
850 | 0 | ttab[i] = first; |
851 | } | |
852 | ||
853 | 0 | return t; |
854 | } | |
855 | catch (CloneNotSupportedException e) { | |
856 | // this shouldn't happen, since we are Cloneable | |
857 | 0 | throw new InternalError(); |
858 | } | |
859 | } | |
860 | ||
861 | // Views | |
862 | ||
863 | protected transient Set keySet = null; | |
864 | protected transient Set entrySet = null; | |
865 | protected transient Collection values = null; | |
866 | ||
867 | /** | |
868 | * Returns a set view of the keys contained in this map. The set is | |
869 | * backed by the map, so changes to the map are reflected in the set, and | |
870 | * vice-versa. The set supports element removal, which removes the | |
871 | * corresponding mapping from this map, via the <tt>Iterator.remove</tt>, | |
872 | * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and | |
873 | * <tt>clear</tt> operations. It does not support the <tt>add</tt> or | |
874 | * <tt>addAll</tt> operations. | |
875 | * | |
876 | * @return a set view of the keys contained in this map. | |
877 | */ | |
878 | ||
879 | 0 | public Set keySet() { |
880 | 0 | Set ks = keySet; |
881 | 0 | return (ks != null)? ks : (keySet = new KeySet()); |
882 | } | |
883 | ||
884 | private class KeySet extends AbstractSet { | |
885 | 0 | public Iterator iterator() { |
886 | 0 | return new KeyIterator(); |
887 | } | |
888 | 0 | public int size() { |
889 | 0 | return ConcurrentReaderHashMap.this.size(); |
890 | } | |
891 | 0 | public boolean contains(Object o) { |
892 | 0 | return ConcurrentReaderHashMap.this.containsKey(o); |
893 | } | |
894 | 0 | public boolean remove(Object o) { |
895 | 0 | return ConcurrentReaderHashMap.this.remove(o) != null; |
896 | } | |
897 | 0 | public void clear() { |
898 | 0 | ConcurrentReaderHashMap.this.clear(); |
899 | } | |
900 | } | |
901 | ||
902 | /** | |
903 | * Returns a collection view of the values contained in this map. The | |
904 | * collection is backed by the map, so changes to the map are reflected in | |
905 | * the collection, and vice-versa. The collection supports element | |
906 | * removal, which removes the corresponding mapping from this map, via the | |
907 | * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
908 | * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
909 | * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
910 | * | |
911 | * @return a collection view of the values contained in this map. | |
912 | */ | |
913 | ||
914 | 0 | public Collection values() { |
915 | 0 | Collection vs = values; |
916 | 0 | return (vs != null)? vs : (values = new Values()); |
917 | } | |
918 | ||
919 | private class Values extends AbstractCollection { | |
920 | 0 | public Iterator iterator() { |
921 | 0 | return new ValueIterator(); |
922 | } | |
923 | 0 | public int size() { |
924 | 0 | return ConcurrentReaderHashMap.this.size(); |
925 | } | |
926 | 0 | public boolean contains(Object o) { |
927 | 0 | return ConcurrentReaderHashMap.this.containsValue(o); |
928 | } | |
929 | 0 | public void clear() { |
930 | 0 | ConcurrentReaderHashMap.this.clear(); |
931 | } | |
932 | } | |
933 | ||
934 | /** | |
935 | * Returns a collection view of the mappings contained in this map. Each | |
936 | * element in the returned collection is a <tt>Map.Entry</tt>. The | |
937 | * collection is backed by the map, so changes to the map are reflected in | |
938 | * the collection, and vice-versa. The collection supports element | |
939 | * removal, which removes the corresponding mapping from the map, via the | |
940 | * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>, | |
941 | * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations. | |
942 | * It does not support the <tt>add</tt> or <tt>addAll</tt> operations. | |
943 | * | |
944 | * @return a collection view of the mappings contained in this map. | |
945 | */ | |
946 | ||
947 | 0 | public Set entrySet() { |
948 | 0 | Set es = entrySet; |
949 | 0 | return (es != null) ? es : (entrySet = new EntrySet()); |
950 | } | |
951 | ||
952 | private class EntrySet extends AbstractSet { | |
953 | 0 | public Iterator iterator() { |
954 | 0 | return new HashIterator(); |
955 | } | |
956 | 0 | public boolean contains(Object o) { |
957 | 0 | if (!(o instanceof Map.Entry)) |
958 | 0 | return false; |
959 | 0 | Map.Entry entry = (Map.Entry)o; |
960 | 0 | Object v = ConcurrentReaderHashMap.this.get(entry.getKey()); |
961 | 0 | return v != null && v.equals(entry.getValue()); |
962 | } | |
963 | 0 | public boolean remove(Object o) { |
964 | 0 | if (!(o instanceof Map.Entry)) |
965 | 0 | return false; |
966 | 0 | return ConcurrentReaderHashMap.this.findAndRemoveEntry((Map.Entry)o); |
967 | } | |
968 | 0 | public int size() { |
969 | 0 | return ConcurrentReaderHashMap.this.size(); |
970 | } | |
971 | 0 | public void clear() { |
972 | 0 | ConcurrentReaderHashMap.this.clear(); |
973 | } | |
974 | } | |
975 | ||
976 | /** | |
977 | * Helper method for entrySet.remove | |
978 | **/ | |
979 | 0 | protected synchronized boolean findAndRemoveEntry(Map.Entry entry) { |
980 | 0 | Object key = entry.getKey(); |
981 | 0 | Object v = get(key); |
982 | 0 | if (v != null && v.equals(entry.getValue())) { |
983 | 0 | remove(key); |
984 | 0 | return true; |
985 | } | |
986 | else | |
987 | 0 | return false; |
988 | } | |
989 | ||
990 | /** | |
991 | * Returns an enumeration of the keys in this table. | |
992 | * | |
993 | * @return an enumeration of the keys in this table. | |
994 | * @see Enumeration | |
995 | * @see #elements() | |
996 | * @see #keySet() | |
997 | * @see Map | |
998 | */ | |
999 | 0 | public Enumeration keys() { |
1000 | 0 | return new KeyIterator(); |
1001 | } | |
1002 | ||
1003 | /** | |
1004 | * Returns an enumeration of the values in this table. | |
1005 | * Use the Enumeration methods on the returned object to fetch the elements | |
1006 | * sequentially. | |
1007 | * | |
1008 | * @return an enumeration of the values in this table. | |
1009 | * @see java.util.Enumeration | |
1010 | * @see #keys() | |
1011 | * @see #values() | |
1012 | * @see Map | |
1013 | */ | |
1014 | ||
1015 | 0 | public Enumeration elements() { |
1016 | 0 | return new ValueIterator(); |
1017 | } | |
1018 | ||
1019 | ||
1020 | /** | |
1021 | * ConcurrentReaderHashMap collision list entry. | |
1022 | */ | |
1023 | ||
1024 | protected static class Entry implements Map.Entry { | |
1025 | ||
1026 | /* | |
1027 | The use of volatile for value field ensures that | |
1028 | we can detect status changes without synchronization. | |
1029 | The other fields are never changed, and are | |
1030 | marked as final. | |
1031 | */ | |
1032 | ||
1033 | protected final int hash; | |
1034 | protected final Object key; | |
1035 | protected final Entry next; | |
1036 | protected volatile Object value; | |
1037 | ||
1038 | 45382 | Entry(int hash, Object key, Object value, Entry next) { |
1039 | 45382 | this.hash = hash; |
1040 | 45382 | this.key = key; |
1041 | 45382 | this.next = next; |
1042 | 45382 | this.value = value; |
1043 | } | |
1044 | ||
1045 | // Map.Entry Ops | |
1046 | ||
1047 | 0 | public Object getKey() { |
1048 | 0 | return key; |
1049 | } | |
1050 | ||
1051 | /** | |
1052 | * Get the value. Note: In an entrySet or entrySet.iterator, | |
1053 | * unless the set or iterator is used under synchronization of the | |
1054 | * table as a whole (or you can otherwise guarantee lack of | |
1055 | * concurrent modification), <tt>getValue</tt> <em>might</em> | |
1056 | * return null, reflecting the fact that the entry has been | |
1057 | * concurrently removed. However, there are no assurances that | |
1058 | * concurrent removals will be reflected using this method. | |
1059 | * | |
1060 | * @return the current value, or null if the entry has been | |
1061 | * detectably removed. | |
1062 | **/ | |
1063 | 0 | public Object getValue() { |
1064 | 0 | return value; |
1065 | } | |
1066 | ||
1067 | /** | |
1068 | * Set the value of this entry. Note: In an entrySet or | |
1069 | * entrySet.iterator), unless the set or iterator is used under | |
1070 | * synchronization of the table as a whole (or you can otherwise | |
1071 | * guarantee lack of concurrent modification), <tt>setValue</tt> | |
1072 | * is not strictly guaranteed to actually replace the value field | |
1073 | * obtained via the <tt>get</tt> operation of the underlying hash | |
1074 | * table in multithreaded applications. If iterator-wide | |
1075 | * synchronization is not used, and any other concurrent | |
1076 | * <tt>put</tt> or <tt>remove</tt> operations occur, sometimes | |
1077 | * even to <em>other</em> entries, then this change is not | |
1078 | * guaranteed to be reflected in the hash table. (It might, or it | |
1079 | * might not. There are no assurances either way.) | |
1080 | * | |
1081 | * @param value the new value. | |
1082 | * @return the previous value, or null if entry has been detectably | |
1083 | * removed. | |
1084 | * @exception NullPointerException if the value is <code>null</code>. | |
1085 | * | |
1086 | **/ | |
1087 | ||
1088 | 0 | public Object setValue(Object value) { |
1089 | 0 | if (value == null) |
1090 | 0 | throw new NullPointerException(); |
1091 | 0 | Object oldValue = this.value; |
1092 | 0 | this.value = value; |
1093 | 0 | return oldValue; |
1094 | } | |
1095 | ||
1096 | 0 | public boolean equals(Object o) { |
1097 | 0 | if (!(o instanceof Map.Entry)) |
1098 | 0 | return false; |
1099 | 0 | Map.Entry e = (Map.Entry)o; |
1100 | 0 | return (key.equals(e.getKey()) && value.equals(e.getValue())); |
1101 | } | |
1102 | ||
1103 | 0 | public int hashCode() { |
1104 | 0 | return key.hashCode() ^ value.hashCode(); |
1105 | } | |
1106 | ||
1107 | 0 | public String toString() { |
1108 | 0 | return key + "=" + value; |
1109 | } | |
1110 | ||
1111 | } | |
1112 | ||
1113 | protected class HashIterator implements Iterator, Enumeration { | |
1114 | protected final Entry[] tab; // snapshot of table | |
1115 | protected int index; // current slot | |
1116 | protected Entry entry = null; // current node of slot | |
1117 | protected Object currentKey; // key for current node | |
1118 | protected Object currentValue; // value for current node | |
1119 | protected Entry lastReturned = null; // last node returned by next | |
1120 | ||
1121 | 0 | protected HashIterator() { |
1122 | 0 | tab = ConcurrentReaderHashMap.this.getTableForReading(); |
1123 | 0 | index = tab.length - 1; |
1124 | } | |
1125 | ||
1126 | 0 | public boolean hasMoreElements() { return hasNext(); } |
1127 | 0 | public Object nextElement() { return next(); } |
1128 | ||
1129 | ||
1130 | 0 | public boolean hasNext() { |
1131 | ||
1132 | /* | |
1133 | currentkey and currentValue are set here to ensure that next() | |
1134 | returns normally if hasNext() returns true. This avoids | |
1135 | surprises especially when final element is removed during | |
1136 | traversal -- instead, we just ignore the removal during | |
1137 | current traversal. | |
1138 | */ | |
1139 | ||
1140 | 0 | for (;;) { |
1141 | 0 | if (entry != null) { |
1142 | 0 | Object v = entry.value; |
1143 | 0 | if (v != null) { |
1144 | 0 | currentKey = entry.key; |
1145 | 0 | currentValue = v; |
1146 | 0 | return true; |
1147 | } | |
1148 | else | |
1149 | 0 | entry = entry.next; |
1150 | } | |
1151 | ||
1152 | 0 | while (entry == null && index >= 0) |
1153 | 0 | entry = tab[index--]; |
1154 | ||
1155 | 0 | if (entry == null) { |
1156 | 0 | currentKey = currentValue = null; |
1157 | 0 | return false; |
1158 | } | |
1159 | } | |
1160 | } | |
1161 | ||
1162 | 0 | protected Object returnValueOfNext() { return entry; } |
1163 | ||
1164 | 0 | public Object next() { |
1165 | 0 | if (currentKey == null && !hasNext()) |
1166 | 0 | throw new NoSuchElementException(); |
1167 | ||
1168 | 0 | Object result = returnValueOfNext(); |
1169 | 0 | lastReturned = entry; |
1170 | 0 | currentKey = currentValue = null; |
1171 | 0 | entry = entry.next; |
1172 | 0 | return result; |
1173 | } | |
1174 | ||
1175 | 0 | public void remove() { |
1176 | 0 | if (lastReturned == null) |
1177 | 0 | throw new IllegalStateException(); |
1178 | 0 | ConcurrentReaderHashMap.this.remove(lastReturned.key); |
1179 | 0 | lastReturned = null; |
1180 | } | |
1181 | ||
1182 | } | |
1183 | ||
1184 | ||
1185 | protected class KeyIterator extends HashIterator { | |
1186 | 0 | protected Object returnValueOfNext() { return currentKey; } |
1187 | } | |
1188 | ||
1189 | protected class ValueIterator extends HashIterator { | |
1190 | 0 | protected Object returnValueOfNext() { return currentValue; } |
1191 | } | |
1192 | ||
1193 | ||
1194 | ||
1195 | /** | |
1196 | * Save the state of the <tt>ConcurrentReaderHashMap</tt> | |
1197 | * instance to a stream (i.e., | |
1198 | * serialize it). | |
1199 | * | |
1200 | * @serialData The <i>capacity</i> of the | |
1201 | * ConcurrentReaderHashMap (the length of the | |
1202 | * bucket array) is emitted (int), followed by the | |
1203 | * <i>size</i> of the ConcurrentReaderHashMap (the number of key-value | |
1204 | * mappings), followed by the key (Object) and value (Object) | |
1205 | * for each key-value mapping represented by the ConcurrentReaderHashMap | |
1206 | * The key-value mappings are emitted in no particular order. | |
1207 | */ | |
1208 | ||
1209 | 0 | private synchronized void writeObject(java.io.ObjectOutputStream s) |
1210 | throws IOException { | |
1211 | // Write out the threshold, loadfactor, and any hidden stuff | |
1212 | 0 | s.defaultWriteObject(); |
1213 | ||
1214 | // Write out number of buckets | |
1215 | 0 | s.writeInt(table.length); |
1216 | ||
1217 | // Write out size (number of Mappings) | |
1218 | 0 | s.writeInt(count); |
1219 | ||
1220 | // Write out keys and values (alternating) | |
1221 | 0 | for (int index = table.length-1; index >= 0; index--) { |
1222 | 0 | Entry entry = table[index]; |
1223 | ||
1224 | 0 | while (entry != null) { |
1225 | 0 | s.writeObject(entry.key); |
1226 | 0 | s.writeObject(entry.value); |
1227 | 0 | entry = entry.next; |
1228 | } | |
1229 | } | |
1230 | } | |
1231 | ||
1232 | /** | |
1233 | * Reconstitute the <tt>ConcurrentReaderHashMap</tt> | |
1234 | * instance from a stream (i.e., | |
1235 | * deserialize it). | |
1236 | */ | |
1237 | 0 | private synchronized void readObject(java.io.ObjectInputStream s) |
1238 | throws IOException, ClassNotFoundException { | |
1239 | // Read in the threshold, loadfactor, and any hidden stuff | |
1240 | 0 | s.defaultReadObject(); |
1241 | ||
1242 | // Read in number of buckets and allocate the bucket array; | |
1243 | 0 | int numBuckets = s.readInt(); |
1244 | 0 | table = new Entry[numBuckets]; |
1245 | ||
1246 | // Read in size (number of Mappings) | |
1247 | 0 | int size = s.readInt(); |
1248 | ||
1249 | // Read the keys and values, and put the mappings in the table | |
1250 | 0 | for (int i=0; i<size; i++) { |
1251 | 0 | Object key = s.readObject(); |
1252 | 0 | Object value = s.readObject(); |
1253 | 0 | put(key, value); |
1254 | } | |
1255 | } | |
1256 | ||
1257 | /** | |
1258 | * Return the number of slots in this table | |
1259 | **/ | |
1260 | ||
1261 | 0 | public synchronized int capacity() { |
1262 | 0 | return table.length; |
1263 | } | |
1264 | ||
1265 | /** | |
1266 | * Return the load factor | |
1267 | **/ | |
1268 | 0 | public float loadFactor() { |
1269 | 0 | return loadFactor; |
1270 | } | |
1271 | } |
|