Java > Open Source Codes > org > cojen > util > SoftValuedHashMap


1 /*
2  * Copyright 2004 Brian S O'Neill
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.cojen.util;
18
19 import java.lang.ref.Reference ;
20 import java.lang.ref.SoftReference ;
21 import java.util.AbstractCollection ;
22 import java.util.AbstractMap ;
23 import java.util.AbstractSet ;
24 import java.util.Collection ;
25 import java.util.Collections ;
26 import java.util.ConcurrentModificationException ;
27 import java.util.Iterator ;
28 import java.util.Map ;
29 import java.util.NoSuchElementException ;
30 import java.util.Set ;
31
32 /**
33  * A Map that softly references its values and can be used as a simple cache.
34  * SoftValuedHashMap is not thread-safe and must be wrapped with
35  * Collections.synchronizedMap to be made thread-safe.
36  * <p>
37  * Note: Softly referenced entries may be automatically removed during
38  * either accessor or mutator operations, possibly causing a concurrent
39  * modification to be detected. Therefore, even if multiple threads are only
40  * accessing this map, be sure to synchronize this map first. Also, do not
41  * rely on the value returned by size() when using an iterator from this map.
42  * The iterators may return less entries than the amount reported by size().
43  *
44  * @author Brian S O'Neill
45  */
46 public class SoftValuedHashMap extends AbstractMap implements Map , Cloneable {
47
48     private transient Entry[] table;
49     private transient int count;
50     private int threshold;
51     private final float loadFactor;
52     private transient volatile int modCount;
53
54     // Views
55
56     private transient Set keySet;
57     private transient Set entrySet;
58     private transient Collection values;
59
60     /**
61      * Constructs a new, empty map with the specified initial
62      * capacity and the specified load factor.
63      *
64      * @param initialCapacity the initial capacity of the HashMap.
65      * @param loadFactor the load factor of the HashMap
66      * @throws IllegalArgumentException if the initial capacity is less
67      * than zero, or if the load factor is nonpositive.
68      */
69     public SoftValuedHashMap(int initialCapacity, float loadFactor) {
70         if (initialCapacity < 0) {
71             throw new IllegalArgumentException ("Illegal Initial Capacity: "+
72                                                initialCapacity);
73         }
74
75         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
76             throw new IllegalArgumentException ("Illegal Load factor: "+
77                                                loadFactor);
78         }
79
80         if (initialCapacity == 0) {
81             initialCapacity = 1;
82         }
83
84         this.loadFactor = loadFactor;
85         this.table = new Entry[initialCapacity];
86         this.threshold = (int)(initialCapacity * loadFactor);
87     }
88
89     /**
90      * Constructs a new, empty map with the specified initial capacity
91      * and default load factor, which is <tt>0.75</tt>.
92      *
93      * @param initialCapacity the initial capacity of the HashMap.
94      * @throws IllegalArgumentException if the initial capacity is less
95      * than zero.
96      */
97     public SoftValuedHashMap(int initialCapacity) {
98         this(initialCapacity, 0.75f);
99     }
100
101     /**
102      * Constructs a new, empty map with a default capacity and load
103      * factor, which is <tt>0.75</tt>.
104      */
105     public SoftValuedHashMap() {
106         this(11, 0.75f);
107     }
108
109     /**
110      * Constructs a new map with the same mappings as the given map. The
111      * map is created with a capacity of twice the number of mappings in
112      * the given map or 11 (whichever is greater), and a default load factor,
113      * which is <tt>0.75</tt>.
114      */
115     public SoftValuedHashMap(Map t) {
116         this(Math.max(2 * t.size(), 11), 0.75f);
117         putAll(t);
118     }
119
120     public int size() {
121         return this.count;
122     }
123
124     public boolean isEmpty() {
125         return this.count == 0;
126     }
127
128     public boolean containsValue(Object value) {
129         if (value == null) {
130             value = KeyFactory.NULL;
131         }
132
133         Entry[] tab = this.table;
134
135         for (int i = tab.length ; i-- > 0 ;) {
136             for (Entry e = tab[i], prev = null; e != null; e = e.next) {
137                 Object entryValue = e.get();
138
139                 if (entryValue == null) {
140                     // Clean up after a cleared Reference.
141 this.modCount++;
142                     if (prev != null) {
143                         prev.next = e.next;
144                     } else {
145                         tab[i] = e.next;
146                     }
147                     this.count--;
148                 } else if (value.equals(entryValue)) {
149                     return true;
150                 } else {
151                     prev = e;
152                 }
153             }
154         }
155
156         return false;
157     }
158
159     public boolean containsKey(Object key) {
160         Entry[] tab = this.table;
161
162         if (key != null) {
163             int hash = key.hashCode();
164             int index = (hash & 0x7fffffff) % tab.length;
165             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
166                 if (e.get() == null) {
167                     // Clean up after a cleared Reference.
168 this.modCount++;
169                     if (prev != null) {
170                         prev.next = e.next;
171                     } else {
172                         tab[index] = e.next;
173                     }
174                     this.count--;
175                 } else if (e.hash == hash && key.equals(e.key)) {
176                     return true;
177                 } else {
178                     prev = e;
179                 }
180             }
181         } else {
182             for (Entry e = tab[0], prev = null; e != null; e = e.next) {
183                 if (e.get() == null) {
184                     // Clean up after a cleared Reference.
185 this.modCount++;
186                     if (prev != null) {
187                         prev.next = e.next;
188                     } else {
189                         tab[0] = e.next;
190                     }
191                     this.count--;
192                 } else if (e.key == null) {
193                     return true;
194                 } else {
195                     prev = e;
196                 }
197             }
198         }
199
200         return false;
201     }
202
203     public Object get(Object key) {
204         Entry[] tab = this.table;
205
206         if (key != null) {
207             int hash = key.hashCode();
208             int index = (hash & 0x7fffffff) % tab.length;
209
210             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
211                 Object entryValue = e.get();
212
213                 if (entryValue == null) {
214                     // Clean up after a cleared Reference.
215 this.modCount++;
216                     if (prev != null) {
217                         prev.next = e.next;
218                     } else {
219                         tab[index] = e.next;
220                     }
221                     count--;
222                 } else if (e.hash == hash && key.equals(e.key)) {
223                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
224                 } else {
225                     prev = e;
226                 }
227             }
228         } else {
229             for (Entry e = tab[0], prev = null; e != null; e = e.next) {
230                 Object entryValue = e.get();
231
232                 if (entryValue == null) {
233                     // Clean up after a cleared Reference.
234 this.modCount++;
235                     if (prev != null) {
236                         prev.next = e.next;
237                     }
238                     else {
239                         tab[0] = e.next;
240                     }
241                     this.count--;
242                 } else if (e.key == null) {
243                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
244                 } else {
245                     prev = e;
246                 }
247             }
248         }
249
250         return null;
251     }
252
253     /**
254      * Scans the contents of this map, removing all entries that have a
255      * cleared soft value.
256      */
257     private void cleanup() {
258         Entry[] tab = this.table;
259
260         for (int i = tab.length ; i-- > 0 ;) {
261             for (Entry e = tab[i], prev = null; e != null; e = e.next) {
262                 if (e.get() == null) {
263                     // Clean up after a cleared Reference.
264 this.modCount++;
265                     if (prev != null) {
266                         prev.next = e.next;
267                     } else {
268                         tab[i] = e.next;
269                     }
270                     this.count--;
271                 } else {
272                     prev = e;
273                 }
274             }
275         }
276     }
277
278     /**
279      * Rehashes the contents of this map into a new <tt>HashMap</tt> instance
280      * with a larger capacity. This method is called automatically when the
281      * number of keys in this map exceeds its capacity and load factor.
282      */
283     private void rehash() {
284         int oldCapacity = this.table.length;
285         Entry[] oldMap = this.table;
286
287         int newCapacity = oldCapacity * 2 + 1;
288         Entry[] newMap = new Entry[newCapacity];
289
290         this.modCount++;
291         this.threshold = (int)(newCapacity * this.loadFactor);
292         this.table = newMap;
293
294         for (int i = oldCapacity ; i-- > 0 ;) {
295             for (Entry old = oldMap[i] ; old != null ; ) {
296                 Entry e = old;
297                 old = old.next;
298
299                 // Only copy entry if its value hasn't been cleared.
300 if (e.get() == null) {
301                     this.count--;
302                 } else {
303                     int index = (e.hash & 0x7fffffff) % newCapacity;
304                     e.next = newMap[index];
305                     newMap[index] = e;
306                 }
307             }
308         }
309     }
310
311     public Object put(Object key, Object value) {
312         if (value == null) {
313             value = KeyFactory.NULL;
314         }
315
316         // Makes sure the key is not already in the HashMap.
317 Entry[] tab = this.table;
318         int hash;
319         int index;
320
321         if (key != null) {
322             hash = key.hashCode();
323             index = (hash & 0x7fffffff) % tab.length;
324             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
325                 Object entryValue = e.get();
326
327                 if (entryValue == null) {
328                     // Clean up after a cleared Reference.
329 this.modCount++;
330                     if (prev != null) {
331                         prev.next = e.next;
332                     } else {
333                         tab[index] = e.next;
334                     }
335                     this.count--;
336                 } else if (e.hash == hash && key.equals(e.key)) {
337                     e.setValue(value);
338                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
339                 } else {
340                     prev = e;
341                 }
342             }
343         } else {
344             hash = 0;
345             index = 0;
346             for (Entry e = tab[0], prev = null; e != null; e = e.next) {
347                 Object entryValue = e.get();
348
349                 if (entryValue == null) {
350                     // Clean up after a cleared Reference.
351 this.modCount++;
352                     if (prev != null) {
353                         prev.next = e.next;
354                     } else {
355                         tab[0] = e.next;
356                     }
357                     this.count--;
358                 } else if (e.key == null) {
359                     e.setValue(value);
360                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
361                 } else {
362                     prev = e;
363                 }
364             }
365         }
366
367         this.modCount++;
368
369         if (this.count >= this.threshold) {
370             // Cleanup the table if the threshold is exceeded.
371 cleanup();
372         }
373
374         if (this.count >= this.threshold) {
375             // Rehash the table if the threshold is still exceeded.
376 rehash();
377             tab = this.table;
378             index = (hash & 0x7fffffff) % tab.length;
379         }
380
381         // Creates the new entry.
382 Entry e = new Entry(hash, key, (Object )value, tab[index]);
383         tab[index] = e;
384         this.count++;
385         return null;
386     }
387
388     public Object remove(Object key) {
389         Entry[] tab = this.table;
390
391         if (key != null) {
392             int hash = key.hashCode();
393             int index = (hash & 0x7fffffff) % tab.length;
394
395             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
396                 Object entryValue = e.get();
397
398                 if (entryValue == null) {
399                     // Clean up after a cleared Reference.
400 this.modCount++;
401                     if (prev != null) {
402                         prev.next = e.next;
403                     } else {
404                         tab[index] = e.next;
405                     }
406                     this.count--;
407                 } else if (e.hash == hash && key.equals(e.key)) {
408                     this.modCount++;
409                     if (prev != null) {
410                         prev.next = e.next;
411                     } else {
412                         tab[index] = e.next;
413                     }
414                     this.count--;
415
416                     e.setValue(null);
417                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
418                 } else {
419                     prev = e;
420                 }
421             }
422         } else {
423             for (Entry e = tab[0], prev = null; e != null; e = e.next) {
424                 Object entryValue = e.get();
425
426                 if (entryValue == null) {
427                     // Clean up after a cleared Reference.
428 this.modCount++;
429                     if (prev != null) {
430                         prev.next = e.next;
431                     } else {
432                         tab[0] = e.next;
433                     }
434                     this.count--;
435                 } else if (e.key == null) {
436                     this.modCount++;
437                     if (prev != null) {
438                         prev.next = e.next;
439                     } else {
440                         tab[0] = e.next;
441                     }
442                     this.count--;
443
444                     e.setValue(null);
445                     return (entryValue == KeyFactory.NULL) ? null : entryValue;
446                 } else {
447                     prev = e;
448                 }
449             }
450         }
451
452         return null;
453     }
454
455     public void putAll(Map t) {
456         Iterator i = t.entrySet().iterator();
457         while (i.hasNext()) {
458             Map.Entry e = (Map.Entry ) i.next();
459             put(e.getKey(), e.getValue());
460         }
461     }
462
463     public void clear() {
464         Entry[] tab = this.table;
465         this.modCount++;
466         for (int index = tab.length; --index >= 0; ) {
467             tab[index] = null;
468         }
469         this.count = 0;
470     }
471
472     public Object clone() {
473         try {
474             SoftValuedHashMap t = (SoftValuedHashMap)super.clone();
475             t.table = new Entry[this.table.length];
476             for (int i = this.table.length ; i-- > 0 ; ) {
477                 t.table[i] = (this.table[i] != null)
478                     ? (Entry)this.table[i].clone() : null;
479             }
480             t.keySet = null;
481             t.entrySet = null;
482             t.values = null;
483             t.modCount = 0;
484             return t;
485         } catch (CloneNotSupportedException e) {
486             // this shouldn't happen, since we are Cloneable
487 throw new InternalError ();
488         }
489     }
490
491     public Set keySet() {
492         if (this.keySet == null) {
493             this.keySet = new AbstractSet () {
494                 public Iterator iterator() {
495                     return createHashIterator(WeakIdentityMap.KEYS);
496                 }
497                 public int size() {
498                     return SoftValuedHashMap.this.count;
499                 }
500                 public boolean contains(Object o) {
501                     return containsKey(o);
502                 }
503                 public boolean remove(Object o) {
504                     if (o == null) {
505                         if (SoftValuedHashMap.this.containsKey(null)) {
506                             SoftValuedHashMap.this.remove(null);
507                             return true;
508                         } else {
509                             return false;
510                         }
511                     } else {
512                         return SoftValuedHashMap.this.remove(o) != null;
513                     }
514                 }
515                 public void clear() {
516                     SoftValuedHashMap.this.clear();
517                 }
518                 public String toString() {
519                     return WeakIdentityMap.toString(this);
520                 }
521             };
522         }
523         return this.keySet;
524     }
525
526     public Collection values() {
527         if (this.values==null) {
528             this.values = new AbstractCollection () {
529                 public Iterator iterator() {
530                     return createHashIterator(WeakIdentityMap.VALUES);
531                 }
532                 public int size() {
533                     return SoftValuedHashMap.this.count;
534                 }
535                 public boolean contains(Object o) {
536                     return containsValue(o);
537                 }
538                 public void clear() {
539                     SoftValuedHashMap.this.clear();
540                 }
541                 public String toString() {
542                     return WeakIdentityMap.toString(this);
543                 }
544             };
545         }
546         return this.values;
547     }
548
549     public Set entrySet() {
550         if (this.entrySet==null) {
551             this.entrySet = new AbstractSet () {
552                 public Iterator iterator() {
553                     return createHashIterator(WeakIdentityMap.ENTRIES);
554                 }
555
556                 public boolean contains(Object o) {
557                     if (!(o instanceof Map.Entry )) {
558                         return false;
559                     }
560                     Map.Entry entry = (Map.Entry )o;
561                     Object key = entry.getKey();
562
563                     Entry[] tab = SoftValuedHashMap.this.table;
564                     int hash = key == null ? 0 : key.hashCode();
565                     int index = (hash & 0x7fffffff) % tab.length;
566
567                     for (Entry e = tab[index], prev = null; e != null; e = e.next) {
568                         Object entryValue = e.get();
569                         
570                         if (entryValue == null) {
571                             // Clean up after a cleared Reference.
572 SoftValuedHashMap.this.modCount++;
573                             if (prev != null) {
574                                 prev.next = e.next;
575                             } else {
576                                 tab[index] = e.next;
577                             }
578                             SoftValuedHashMap.this.count--;
579                         } else if (e.hash == hash && e.equals(entry)) {
580                             return true;
581                         } else {
582                             prev = e;
583                         }
584                     }
585
586                     return false;
587                 }
588
589                 public boolean remove(Object o) {
590                     if (!(o instanceof Map.Entry )) {
591                         return false;
592                     }
593                     Map.Entry entry = (Map.Entry )o;
594                     Object key = entry.getKey();
595                     Entry[] tab = SoftValuedHashMap.this.table;
596                     int hash = key == null ? 0 : key.hashCode();
597                     int index = (hash & 0x7fffffff) % tab.length;
598
599                     for (Entry e = tab[index], prev = null; e != null; e = e.next) {
600                         Object entryValue = e.get();
601
602                         if (entryValue == null) {
603                             // Clean up after a cleared Reference.
604 SoftValuedHashMap.this.modCount++;
605                             if (prev != null) {
606                                 prev.next = e.next;
607                             } else {
608                                 tab[index] = e.next;
609                             }
610                             SoftValuedHashMap.this.count--;
611                         } else if (e.hash == hash && e.equals(entry)) {
612                             SoftValuedHashMap.this.modCount++;
613                             if (prev != null) {
614                                 prev.next = e.next;
615                             } else {
616                                 tab[index] = e.next;
617                             }
618                             SoftValuedHashMap.this.count--;
619
620                             e.setValue(null);
621                             return true;
622                         } else {
623                             prev = e;
624                         }
625                     }
626                     return false;
627                 }
628
629                 public int size() {
630                     return SoftValuedHashMap.this.count;
631                 }
632
633                 public void clear() {
634                     SoftValuedHashMap.this.clear();
635                 }
636
637                 public String toString() {
638                     return WeakIdentityMap.toString(this);
639                 }
640             };
641         }
642
643         return this.entrySet;
644     }
645
646     public String toString() {
647         // Cleanup stale entries first, so as not to allocate a larger than
648 // necessary StringBuffer.
649 cleanup();
650         return WeakIdentityMap.toString(this);
651     }
652
653     private Iterator createHashIterator(int type) {
654         if (this.count == 0) {
655             return Collections.EMPTY_SET.iterator();
656         } else {
657             return new HashIterator(type);
658         }
659     }
660
661     /**
662      * HashMap collision list entry.
663      */
664     private static class Entry implements Map.Entry {
665         int hash;
666         Object key;
667         Entry next;
668
669         private Reference value;
670
671         Entry(int hash, Object key, Object value, Entry next) {
672             this.hash = hash;
673             this.key = key;
674             this.value = new SoftReference (value);
675             this.next = next;
676         }
677
678         private Entry(int hash, Object key, Reference value, Entry next) {
679             this.hash = hash;
680             this.key = key;
681             this.value = value;
682             this.next = next;
683         }
684
685         // Map.Entry Ops
686
687         public Object getKey() {
688             return this.key;
689         }
690
691         public Object getValue() {
692             Object value = this.value.get();
693             return value == KeyFactory.NULL ? null : value;
694         }
695
696         public Object setValue(Object value) {
697             Object oldValue = getValue();
698             this.value = new SoftReference (value == null ? KeyFactory.NULL : value);
699             return oldValue;
700         }
701
702         public boolean equals(Object obj) {
703             if (!(obj instanceof Map.Entry )) {
704                 return false;
705             }
706             return equals((Map.Entry )obj);
707         }
708         
709         boolean equals(Map.Entry e) {
710             Object thisValue = get();
711             if (thisValue == null) {
712                 return false;
713             } else if (thisValue == KeyFactory.NULL) {
714                 thisValue = null;
715             }
716             return (this.key == null ? e.getKey() == null : this.key.equals(e.getKey())) &&
717                 (thisValue == null ? e.getValue() == null : thisValue.equals(e.getValue()));
718         }
719
720         public int hashCode() {
721             return this.hash ^ get().hashCode();
722         }
723
724         public String toString() {
725             return this.key + "=" + getValue();
726         }
727
728         protected Object clone() {
729             return new Entry(this.hash, this.key, (Reference )this.value,
730                              (this.next == null ? null : (Entry)this.next.clone()));
731         }
732
733         // Like getValue(), except does not convert NULL to null.
734 Object get() {
735             return this.value.get();
736         }
737     }
738
739     private class HashIterator implements Iterator {
740         private final int type;
741         private final Entry[] table;
742
743         private int index;
744
745         // To ensure that the iterator doesn't return cleared entries, keep a
746 // hard reference to the value. Its existence will prevent the soft
747 // value from being cleared.
748 private Object entryValue;
749         private Entry entry;
750
751         private Entry last;
752
753         /**
754          * The modCount value that the iterator believes that the backing
755          * List should have. If this expectation is violated, the iterator
756          * has detected concurrent modification.
757          */
758         private int expectedModCount = SoftValuedHashMap.this.modCount;
759
760         HashIterator(int type) {
761             this.table = SoftValuedHashMap.this.table;
762             this.type = type;
763             this.index = table.length;
764         }
765
766         public boolean hasNext() {
767             while (this.entry == null || (this.entryValue = this.entry.get()) == null) {
768                 if (this.entry != null) {
769                     // Clean up after a cleared Reference.
770 remove(this.entry);
771                     this.entry = this.entry.next;
772                 }
773
774                 if (this.entry == null) {
775                     if (this.index <= 0) {
776                         return false;
777                     } else {
778                         this.entry = this.table[--this.index];
779                     }
780                 }
781             }
782
783             return true;
784         }
785
786         public Object next() {
787             if (SoftValuedHashMap.this.modCount != expectedModCount) {
788                 throw new ConcurrentModificationException ();
789             }
790
791             if (!hasNext()) {
792                 throw new NoSuchElementException ();
793             }
794
795             this.last = this.entry;
796             this.entry = this.entry.next;
797
798             return this.type == WeakIdentityMap.KEYS ? this.last.getKey() :
799                 (this.type == WeakIdentityMap.VALUES ? this.last.getValue() : this.last);
800         }
801
802         public void remove() {
803             if (this.last == null) {
804                 throw new IllegalStateException ();
805             }
806             if (SoftValuedHashMap.this.modCount != expectedModCount) {
807                 throw new ConcurrentModificationException ();
808             }
809             remove(this.last);
810             this.last = null;
811         }
812
813         private void remove(Entry toRemove) {
814             Entry[] tab = this.table;
815             int index = (toRemove.hash & 0x7fffffff) % tab.length;
816
817             for (Entry e = tab[index], prev = null; e != null; e = e.next) {
818                 if (e == toRemove) {
819                     SoftValuedHashMap.this.modCount++;
820                     expectedModCount++;
821                     if (prev == null) {
822                         tab[index] = e.next;
823                     } else {
824                         prev.next = e.next;
825                     }
826                     SoftValuedHashMap.this.count--;
827                     return;
828                 } else {
829                     prev = e;
830                 }
831             }
832             throw new ConcurrentModificationException ();
833         }
834     }
835 }
836

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags