SoftSettingsHash


1   /* SoftHashMap
2    *
3    * $Id: SoftSettingsHash.java,v 1.2.28.1 2007/01/13 01:31:27 stack-sf Exp $
4    *
5    * Created on Mar 18, 2004
6    *
7    * Copyright (C) 2004 Internet Archive.
8    *
9    * This file is part of the Heritrix web crawler (crawler.archive.org).
10   *
11   * Heritrix is free software; you can redistribute it and/or modify
12   * it under the terms of the GNU Lesser Public License as published by
13   * the Free Software Foundation; either version 2.1 of the License, or
14   * any later version.
15   *
16   * Heritrix is distributed in the hope that it will be useful,
17   * but WITHOUT ANY WARRANTY; without even the implied warranty of
18   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19   * GNU Lesser Public License for more details.
20   *
21   * You should have received a copy of the GNU Lesser Public License
22   * along with Heritrix; if not, write to the Free Software
23   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
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;  // Help GC
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         // check if needed
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          * If ignoring null elements and processing ref queue caused massive
256          * shrinkage, then restore old table.  This should be rare, but avoids
257          * unbounded expansion of garbage-filled tables.
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;  // Help GC
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         // clear out ref queue. We don't need to expunge entries
331         // since table is getting cleared.
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         // Allocation of array may have caused GC, which may have caused
342         // additional entries to go stale.  Removing these entries from the
343         // reference queue will make them eligible for reclamation.
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(); // hold on to key in strong ref
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 }
490
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags