1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 package org.archive.crawler.settings;
26
27 import java.lang.ref.Reference;
28 import java.lang.ref.ReferenceQueue;
29 import java.lang.ref.SoftReference;
30 import java.util.ConcurrentModificationException;
31 import java.util.Iterator;
32 import java.util.NoSuchElementException;
33
34
35 public class SoftSettingsHash {
36
37 /***
38 * The maximum capacity, used if a higher value is implicitly specified
39 * by either of the constructors with arguments.
40 * MUST be a power of two <= 1<<30.
41 */
42 private static final int MAXIMUM_CAPACITY = 1 << 30;
43
44 /***
45 * The load fast used.
46 */
47 private static final float LOAD_FACTOR = 0.75f;
48
49 /***
50 * The table, resized as necessary. Length MUST Always be a power of two.
51 */
52 private SettingsEntry[] table;
53
54 /***
55 * The number of key-value mappings contained in this hash.
56 */
57 private int size;
58
59 /***
60 * The next size value at which to resize (capacity * load factor).
61 */
62 private int threshold;
63
64 /***
65 * Reference queue for cleared entries
66 */
67 private final ReferenceQueue<? super String> queue
68 = new ReferenceQueue<String>();
69
70 /***
71 * The number of times this HashMap has been structurally modified
72 * Structural modifications are those that change the number of mappings in
73 * the HashMap or otherwise modify its internal structure (e.g.,
74 * rehash). This field is used to make iterators on Collection-views of
75 * the HashMap fail-fast. (See ConcurrentModificationException).
76 */
77 private volatile int modCount;
78
79 /***
80 * Constructs a new, empty <tt>SoftSettingsHash</tt> with the given initial
81 * capacity.
82 *
83 * @param initialCapacity The initial capacity of the
84 * <tt>SoftSettingsHash</tt>
85 * @throws IllegalArgumentException If the initial capacity is negative.
86 */
87 public SoftSettingsHash(int initialCapacity) {
88 if (initialCapacity < 0)
89 throw new IllegalArgumentException("Illegal Initial Capacity: "+
90 initialCapacity);
91 if (initialCapacity > MAXIMUM_CAPACITY)
92 initialCapacity = MAXIMUM_CAPACITY;
93
94 int capacity = 1;
95 while (capacity < initialCapacity)
96 capacity <<= 1;
97 table = new SettingsEntry[capacity];
98 threshold = (int)(capacity * LOAD_FACTOR);
99 }
100
101 /***
102 * Check for equality of non-null reference x and possibly-null y. By
103 * default uses Object.equals.
104 */
105 static boolean eq(Object x, Object y) {
106 return x == y || x.equals(y);
107 }
108
109 /***
110 * Return index for hash code h.
111 */
112 static int indexFor(int h, int length) {
113 return h & (length-1);
114 }
115
116 /***
117 * Expunge stale entries from the table.
118 */
119 private void expungeStaleEntries() {
120 SettingsEntry entry;
121 Reference ref;
122 while ( (ref = queue.poll()) != null) {
123 entry = (SettingsEntry)ref;
124 int h = entry.hash;
125 int i = indexFor(h, table.length);
126
127 SettingsEntry prev = table[i];
128 SettingsEntry p = prev;
129 while (p != null) {
130 SettingsEntry next = p.next;
131 if (p == entry) {
132 if (prev == entry)
133 table[i] = next;
134 else
135 prev.next = next;
136 entry.next = null;
137 entry.settings = null;
138 size--;
139 break;
140 }
141 prev = p;
142 p = next;
143 }
144 }
145 }
146
147 /***
148 * Returns the number of key-value mappings in this map.
149 * This result is a snapshot, and may not reflect unprocessed
150 * entries that will be removed before next attempted access
151 * because they are no longer referenced.
152 */
153 public int size() {
154 if (size == 0)
155 return 0;
156 expungeStaleEntries();
157 return size;
158 }
159
160 /***
161 * Returns the value to which the specified key is mapped in this weak
162 * hash map, or <tt>null</tt> if the map contains no mapping for
163 * this key. Null is also returned if the element has been GC'ed.
164 *
165 * @param key the key whose associated settings object is to be returned.
166 * @return the settings object represented by the key, or
167 * <tt>null</tt> if the map contains no mapping for this key.
168 * @see #put(String, CrawlerSettings)
169 */
170 public CrawlerSettings get(String key) {
171 if (key == null) {
172 throw new NullPointerException("Null key");
173 }
174 int hash = hash(key);
175 expungeStaleEntries();
176 int index = indexFor(hash, table.length);
177 SettingsEntry e = table[index];
178 while (e != null) {
179 if (e.hash == hash && eq(key, e.get()))
180 return e.settings;
181 e = e.next;
182 }
183 return null;
184 }
185
186 /***
187 * Associates the specified settings object with the specified key in this
188 * hash.
189 *
190 * If the hash previously contained a settings object for this key, the old
191 * object is replaced.
192 *
193 * @param key key with which the specified settings object is to be
194 * associated.
195 * @param settings settings object to be associated with the specified key.
196 * @return previous value associated with specified key, or <tt>null</tt>
197 * if there was no mapping for key.
198 */
199 public CrawlerSettings put(String key, CrawlerSettings settings) {
200 if (settings == null) {
201 throw new NullPointerException("Settings object was null");
202 }
203 if (key == null) {
204 throw new NullPointerException("Null key");
205 }
206 int hash = hash(key);
207 expungeStaleEntries();
208 int i = indexFor(hash, table.length);
209
210 for (SettingsEntry entry = table[i]; entry != null; entry = entry.next) {
211 if (hash == entry.hash && eq(key, entry.get())) {
212 CrawlerSettings oldValue = entry.settings;
213 if (settings != oldValue)
214 entry.settings = settings;
215 return oldValue;
216 }
217 }
218
219 modCount++;
220 table[i] = new SettingsEntry(key, settings, queue, hash, table[i]);
221 if (++size >= threshold)
222 resize(table.length * 2);
223 return null;
224 }
225
226 public CrawlerSettings put(SettingsEntry entry) {
227 return put(entry.getKey(), entry.getValue());
228 }
229
230 /***
231 * Rehashes the contents of this hash into a new <tt>HashMap</tt> instance
232 * with a larger capacity. This method is called automatically when the
233 * number of keys in this map exceeds its capacity and load factor.
234 *
235 * Note that this method is a no-op if it's called with newCapacity ==
236 * 2*MAXIMUM_CAPACITY (which is Integer.MIN_VALUE).
237 *
238 * @param newCapacity the new capacity, MUST be a power of two.
239 */
240 void resize(int newCapacity) {
241 expungeStaleEntries();
242 SettingsEntry[] oldTable = table;
243 int oldCapacity = oldTable.length;
244
245
246 if (size < threshold || oldCapacity > newCapacity)
247 return;
248
249 SettingsEntry[] newTable = new SettingsEntry[newCapacity];
250
251 transfer(oldTable, newTable);
252 table = newTable;
253
254
255
256
257
258
259 if (size >= threshold / 2) {
260 threshold = (int)(newCapacity * LOAD_FACTOR);
261 } else {
262 expungeStaleEntries();
263 transfer(newTable, oldTable);
264 table = oldTable;
265 }
266 }
267
268 /*** Transfer all entries from src to dest tables */
269 private void transfer(SettingsEntry[] src, SettingsEntry[] dest) {
270 for (int j = 0; j < src.length; ++j) {
271 SettingsEntry entry = src[j];
272 src[j] = null;
273 while (entry != null) {
274 SettingsEntry next = entry.next;
275 Object key = entry.get();
276 if (key == null) {
277 entry.next = null;
278 entry.settings = null;
279 size--;
280 } else {
281 int i = indexFor(entry.hash, dest.length);
282 entry.next = dest[i];
283 dest[i] = entry;
284 }
285 entry = next;
286 }
287 }
288 }
289
290 /***
291 * Removes the settings object identified by the key from this hash if
292 * present.
293 *
294 * @param key key whose element is to be removed from the hash.
295 * @return previous value associated with specified key, or <tt>null</tt>
296 * if there was no mapping for key.
297 */
298 public Object remove(String key) {
299 if (key == null) {
300 throw new NullPointerException("Null key");
301 }
302 int hash = hash(key);
303 expungeStaleEntries();
304 int i = indexFor(hash, table.length);
305 SettingsEntry prev = table[i];
306 SettingsEntry entry = prev;
307
308 while (entry != null) {
309 SettingsEntry next = entry.next;
310 if (hash == entry.hash && eq(key, entry.get())) {
311 modCount++;
312 size--;
313 if (prev == entry)
314 table[i] = next;
315 else
316 prev.next = next;
317 return entry.settings;
318 }
319 prev = entry;
320 entry = next;
321 }
322
323 return null;
324 }
325
326 /***
327 * Removes all settings object from this hash.
328 */
329 public void clear() {
330
331
332 while (queue.poll() != null)
333 ;
334
335 modCount++;
336 SettingsEntry tab[] = table;
337 for (int i = 0; i < tab.length; ++i)
338 tab[i] = null;
339 size = 0;
340
341
342
343
344 while (queue.poll() != null)
345 ;
346 }
347
348 /***
349 * The entries in this hash extend SoftReference, using the host string
350 * as the key.
351 */
352 static class SettingsEntry extends SoftReference<String> {
353 private CrawlerSettings settings;
354 private final int hash;
355 private SettingsEntry next;
356
357 /***
358 * Create new entry.
359 */
360 SettingsEntry(String key, CrawlerSettings settings,
361 ReferenceQueue<? super String> queue,
362 int hash, SettingsEntry next) {
363 super(key, queue);
364 this.settings = settings;
365 this.hash = hash;
366 this.next = next;
367 }
368
369 public String getKey() {
370 return (String) this.get();
371 }
372
373 public CrawlerSettings getValue() {
374 return settings;
375 }
376
377 public boolean equals(Object o) {
378 if (!(o instanceof SettingsEntry))
379 return false;
380 SettingsEntry e = (SettingsEntry)o;
381 String key1 = getKey();
382 String key2 = e.getKey();
383 if (key1 == key2 || (key1 != null && key1.equals(key2))) {
384 CrawlerSettings setting1 = getValue();
385 CrawlerSettings setting2 = e.getValue();
386 if (setting1 == setting2 || (setting1 != null && setting1.equals(setting2)))
387 return true;
388 }
389 return false;
390 }
391 }
392
393 /*** Iterator over all elements in hash.
394 */
395 class EntryIterator implements Iterator {
396 int index;
397 SettingsEntry entry = null;
398 SettingsEntry lastReturned = null;
399 int expectedModCount = modCount;
400
401 /***
402 * Strong reference needed to avoid disappearance of key
403 * between hasNext and next
404 */
405 String nextKey = null;
406
407 /***
408 * Strong reference needed to avoid disappearance of key
409 * between nextEntry() and any use of the entry
410 */
411 String currentKey = null;
412
413 EntryIterator() {
414 index = (size() != 0 ? table.length : 0);
415 }
416
417 public boolean hasNext() {
418 SettingsEntry[] t = table;
419
420 while (nextKey == null) {
421 SettingsEntry e = entry;
422 int i = index;
423 while (e == null && i > 0)
424 e = t[--i];
425 entry = e;
426 index = i;
427 if (e == null) {
428 currentKey = null;
429 return false;
430 }
431 nextKey = (String) e.get();
432 if (nextKey == null)
433 entry = entry.next;
434 }
435 return true;
436 }
437
438 /*** The common parts of next() across different types of iterators */
439 public Object next() {
440 return nextEntry();
441 }
442
443 public SettingsEntry nextEntry() {
444 if (modCount != expectedModCount)
445 throw new ConcurrentModificationException();
446 if (nextKey == null && !hasNext())
447 throw new NoSuchElementException();
448
449 lastReturned = entry;
450 entry = entry.next;
451 currentKey = nextKey;
452 nextKey = null;
453 return lastReturned;
454 }
455
456 public void remove() {
457 if (lastReturned == null)
458 throw new IllegalStateException();
459 if (modCount != expectedModCount)
460 throw new ConcurrentModificationException();
461
462 SoftSettingsHash.this.remove(currentKey);
463 expectedModCount = modCount;
464 lastReturned = null;
465 currentKey = null;
466 }
467
468 }
469
470 /*** Make hash value from a String.
471 *
472 * @param key the string for which to create hash value.
473 * @return the hash value.
474 */
475 static int hash(String key) {
476 int hash = key.hashCode();
477
478 hash += ~(hash << 9);
479 hash ^= (hash >>> 14);
480 hash += (hash << 4);
481 hash ^= (hash >>> 10);
482 return hash;
483 }
484
485 public EntryIterator iterator() {
486 return new EntryIterator();
487 }
488
489 }