1 /**
2  *  Copyright Terracotta, Inc.
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 package net.sf.ehcache.store.chm;
17
18 import java.io.Serializable;
19 import java.util.AbstractCollection;
20 import java.util.AbstractSet;
21 import java.util.ArrayList;
22 import java.util.Arrays;
23 import java.util.Collection;
24 import java.util.Collections;
25 import java.util.Iterator;
26 import java.util.List;
27 import java.util.Map;
28 import java.util.Map.Entry;
29 import java.util.NoSuchElementException;
30 import java.util.Random;
31 import java.util.Set;
32 import java.util.concurrent.locks.ReentrantReadWriteLock;
33
34 import net.sf.ehcache.Element;
35 import net.sf.ehcache.event.RegisteredEventListeners;
36 import net.sf.ehcache.pool.PoolAccessor;
37 import net.sf.ehcache.pool.sizeof.annotations.IgnoreSizeOf;
38
39 /**
40  * SelectableConcurrentHashMap subclasses a repackaged version of ConcurrentHashMap
41  * ito allow efficient random sampling of the map values.
42  * <p>
43  * The random sampling technique involves randomly selecting a map Segment, and then
44  * selecting a number of random entry chains from that segment.
45  *
46  * @author Chris Dennis
47  */
48 public class SelectableConcurrentHashMap {
49
50     protected static final Element DUMMY_PINNED_ELEMENT = new Element(new DummyPinnedKey(), new DummyPinnedValue());
51
52     /**
53      * The default initial capacity for this table,
54      * used when not otherwise specified in a constructor.
55      */
56     static final int DEFAULT_INITIAL_CAPACITY = 16;
57
58     /**
59      * The default load factor for this table, used when not
60      * otherwise specified in a constructor.
61      */
62     static final float DEFAULT_LOAD_FACTOR = 0.75f;
63
64     /**
65      * The maximum capacity, used if a higher value is implicitly
66      * specified by either of the constructors with arguments.  MUST
67      * be a power of two <= 1<<30 to ensure that entries are indexable
68      * using ints.
69      */
70     private static final int MAXIMUM_CAPACITY = 1 << 30;
71
72     /**
73      * The maximum number of segments to allow; used to bound
74      * constructor arguments.
75      */
76     private static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
77
78     /**
79      * Number of unsynchronized retries in size and containsValue
80      * methods before resorting to locking. This is used to avoid
81      * unbounded retries if tables undergo continuous modification
82      * which would make it impossible to obtain an accurate result.
83      */
84     private static final int RETRIES_BEFORE_LOCK = 2;
85
86     /**
87      * Mask value for indexing into segments. The upper bits of a
88      * key's hash code are used to choose the segment.
89      */
90     private final int segmentMask;
91
92     /**
93      * Shift value for indexing within segments.
94      */
95     private final int segmentShift;
96
97     /**
98      * The segments, each of which is a specialized hash table
99      */
100     private final Segment[] segments;
101
102     private final Random rndm = new Random();
103     private final PoolAccessor poolAccessor;
104     private final boolean elementPinningEnabled;
105     private volatile long maxSize;
106     private volatile SelectableConcurrentHashMap.PinnedKeySet pinnedKeySet;
107     private final RegisteredEventListeners cacheEventNotificationService;
108
109     private Set<Object> keySet;
110     private Set<Map.Entry<Object,Element>> entrySet;
111     private Collection<Element> values;
112
113     public SelectableConcurrentHashMap(PoolAccessor poolAccessor, boolean elementPinningEnabled, int concurrency, final long maximumSize, final RegisteredEventListeners cacheEventNotificationService) {
114       this(poolAccessor, elementPinningEnabled, DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, concurrency, maximumSize, cacheEventNotificationService);
115     }
116     
117     public SelectableConcurrentHashMap(PoolAccessor poolAccessor, boolean elementPinningEnabled, int initialCapacity, float loadFactor, int concurrency, final long maximumSize, final RegisteredEventListeners cacheEventNotificationService) {
118         if (!(loadFactor > 0) || initialCapacity < 0 || concurrency <= 0)
119             throw new IllegalArgumentException();
120
121         if (concurrency > MAX_SEGMENTS)
122             concurrency = MAX_SEGMENTS;
123
124         // Find power-of-two sizes best matching arguments
125         int sshift = 0;
126         int ssize = 1;
127         while (ssize < concurrency) {
128             ++sshift;
129             ssize <<= 1;
130         }
131         segmentShift = 32 - sshift;
132         segmentMask = ssize - 1;
133         this.segments = new Segment[ssize];
134
135         if (initialCapacity > MAXIMUM_CAPACITY)
136             initialCapacity = MAXIMUM_CAPACITY;
137         int c = initialCapacity / ssize;
138         if (c * ssize < initialCapacity)
139             ++c;
140         int cap = 1;
141         while (cap < c)
142             cap <<= 1;
143
144         for (int i = 0; i < this.segments.length; ++i)
145             this.segments[i] = createSegment(cap, loadFactor);
146
147         this.poolAccessor = poolAccessor;
148         this.elementPinningEnabled = elementPinningEnabled;
149         this.maxSize = maximumSize;
150         this.cacheEventNotificationService = cacheEventNotificationService;
151         pinnedKeySet = new PinnedKeySet();
152     }
153
154     public void setMaxSize(final long maxSize) {
155         this.maxSize = maxSize;
156     }
157
158     public Element[] getRandomValues(final int size, Object keyHint) {
159         ArrayList<Element> sampled = new ArrayList<Element>(size * 2);
160
161         // pick a random starting point in the map
162         int randomHash = rndm.nextInt();
163
164         final int segmentStart;
165         if (keyHint == null) {
166             segmentStart = (randomHash >>> segmentShift) & segmentMask;
167         } else {
168             segmentStart = (hash(keyHint.hashCode()) >>> segmentShift) & segmentMask;
169         }
170
171         int segmentIndex = segmentStart;
172         do {
173             final HashEntry[] table = segments[segmentIndex].table;
174             final int tableStart = randomHash & (table.length - 1);
175             int tableIndex = tableStart;
176             do {
177                 for (HashEntry e = table[tableIndex]; e != null; e = e.next) {
178                     Element value = e.value;
179                     if (value != null && (!(e.pinned && elementPinningEnabled) || value.isExpired())) {
180                         sampled.add(value);
181                     }
182                 }
183
184                 if (sampled.size() >= size) {
185                     return sampled.toArray(new Element[sampled.size()]);
186                 }
187
188                 //move to next table slot
189                 tableIndex = (tableIndex + 1) & (table.length - 1);
190             } while (tableIndex != tableStart);
191
192             //move to next segment
193             segmentIndex = (segmentIndex + 1) & segmentMask;
194         } while (segmentIndex != segmentStart);
195
196         return sampled.toArray(new Element[sampled.size()]);
197     }
198
199     /**
200      * Return an object of the kind which will be stored when
201      * the element is going to be inserted
202      * @param e the element
203      * @return an object looking-alike the stored one
204      */
205     public Object storedObject(Element e) {
206         return new HashEntry(null, 0, null, e, 0, false);
207     }
208
209     /**
210      * Returns the number of key-value mappings in this map without locking anything.
211      * This may not give the exact element count as locking is avoided.
212      * If the map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
213      * <tt>Integer.MAX_VALUE</tt>.
214      *
215      * @return the number of key-value mappings in this map
216      */
217     public int quickSize() {
218         final Segment[] segments = this.segments;
219         long sum = 0;
220         for (Segment seg : segments) {
221             sum += seg.count - seg.numDummyPinnedKeys;
222         }
223
224         if (sum > Integer.MAX_VALUE) {
225             return Integer.MAX_VALUE;
226         } else {
227             return (int)sum;
228         }
229     }
230
231     public boolean isEmpty() {
232         final Segment[] segments = this.segments;
233         /*
234          * We keep track of per-segment modCounts to avoid ABA
235          * problems in which an element in one segment was added and
236          * in another removed during traversal, in which case the
237          * table was never actually empty at any point. Note the
238          * similar use of modCounts in the size() and containsValue()
239          * methods, which are the only other methods also susceptible
240          * to ABA problems.
241          */
242         int[] mc = new int[segments.length];
243         int mcsum = 0;
244         for (int i = 0; i < segments.length; ++i) {
245             if (segments[i].count != 0)
246                 return false;
247             else
248                 mcsum += mc[i] = segments[i].modCount;
249         }
250         // If mcsum happens to be zero, then we know we got a snapshot
251         // before any modifications at all were made.  This is
252         // probably common enough to bother tracking.
253         if (mcsum != 0) {
254             for (int i = 0; i < segments.length; ++i) {
255                 if (segments[i].count != 0 ||
256                     mc[i] != segments[i].modCount)
257                     return false;
258             }
259         }
260         return true;
261     }
262
263     public int size() {
264         final Segment[] segments = this.segments;
265
266         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
267             int[] mc = new int[segments.length];
268             long check = 0;
269             long sum = 0;
270             int mcsum = 0;
271             for (int i = 0; i < segments.length; ++i) {
272                 sum += segments[i].count - segments[i].numDummyPinnedKeys;
273                 mcsum += mc[i] = segments[i].modCount;
274             }
275             if (mcsum != 0) {
276                 for (int i = 0; i < segments.length; ++i) {
277                     check += segments[i].count - segments[i].numDummyPinnedKeys;
278                     if (mc[i] != segments[i].modCount) {
279                         check = -1; // force retry
280                         break;
281                     }
282                 }
283             }
284             if (check == sum) {
285                 if (sum > Integer.MAX_VALUE) {
286                     return Integer.MAX_VALUE;
287                 } else {
288                     return (int)sum;
289                 }
290             }
291         }
292
293         long sum = 0;
294         for (int i = 0; i < segments.length; ++i) {
295             segments[i].readLock().lock();
296         }
297         try {
298             for (int i = 0; i < segments.length; ++i) {
299                 sum += segments[i].count - segments[i].numDummyPinnedKeys;
300             }
301         } finally {
302             for (int i = 0; i < segments.length; ++i) {
303                 segments[i].readLock().unlock();
304             }
305         }
306
307         if (sum > Integer.MAX_VALUE) {
308             return Integer.MAX_VALUE;
309         } else {
310             return (int)sum;
311         }
312     }
313
314     public int pinnedSize() {
315         final Segment[] segments = this.segments;
316
317         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
318             int[] mc = new int[segments.length];
319             long check = 0;
320             long sum = 0;
321             int mcsum = 0;
322             for (int i = 0; i < segments.length; ++i) {
323                 sum += segments[i].pinnedCount - segments[i].numDummyPinnedKeys;
324                 mcsum += mc[i] = segments[i].modCount;
325             }
326             if (mcsum != 0) {
327                 for (int i = 0; i < segments.length; ++i) {
328                     check += segments[i].pinnedCount - segments[i].numDummyPinnedKeys;
329                     if (mc[i] != segments[i].modCount) {
330                         check = -1; // force retry
331                         break;
332                     }
333                 }
334             }
335             if (check == sum) {
336                 if (sum > Integer.MAX_VALUE) {
337                     return Integer.MAX_VALUE;
338                 } else {
339                     return (int)sum;
340                 }
341             }
342         }
343
344         long sum = 0;
345         for (int i = 0; i < segments.length; ++i) {
346             segments[i].readLock().lock();
347         }
348         try {
349             for (int i = 0; i < segments.length; ++i) {
350                 sum += segments[i].pinnedCount - segments[i].numDummyPinnedKeys;
351             }
352         } finally {
353             for (int i = 0; i < segments.length; ++i) {
354                 segments[i].readLock().unlock();
355             }
356         }
357
358         if (sum > Integer.MAX_VALUE) {
359             return Integer.MAX_VALUE;
360         } else {
361             return (int)sum;
362         }
363     }
364
365     public ReentrantReadWriteLock lockFor(Object key) {
366         int hash = hash(key.hashCode());
367         return segmentFor(hash);
368     }
369
370     public ReentrantReadWriteLock[] locks() {
371         return segments;
372     }
373
374     public Element get(Object key) {
375         int hash = hash(key.hashCode());
376         return segmentFor(hash).get(key, hash);
377     }
378
379     public boolean containsKey(Object key) {
380         int hash = hash(key.hashCode());
381         return segmentFor(hash).containsKey(key, hash);
382     }
383
384     public boolean containsValue(Object value) {
385         if (value == null)
386             throw new NullPointerException();
387
388         // See explanation of modCount use above
389
390         final Segment[] segments = this.segments;
391         int[] mc = new int[segments.length];
392
393         // Try a few times without locking
394         for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) {
395             int sum = 0;
396             int mcsum = 0;
397             for (int i = 0; i < segments.length; ++i) {
398                 int c = segments[i].count;
399                 mcsum += mc[i] = segments[i].modCount;
400                 if (segments[i].containsValue(value))
401                     return true;
402             }
403             boolean cleanSweep = true;
404             if (mcsum != 0) {
405                 for (int i = 0; i < segments.length; ++i) {
406                     int c = segments[i].count;
407                     if (mc[i] != segments[i].modCount) {
408                         cleanSweep = false;
409                         break;
410                     }
411                 }
412             }
413             if (cleanSweep)
414                 return false;
415         }
416
417         // Resort to locking all segments
418         for (int i = 0; i < segments.length; ++i)
419             segments[i].readLock().lock();
420         try {
421             for (int i = 0; i < segments.length; ++i) {
422                 if (segments[i].containsValue(value)) {
423                     return true;
424                 }
425             }
426         } finally {
427             for (int i = 0; i < segments.length; ++i)
428                 segments[i].readLock().unlock();
429         }
430         return false;
431     }
432
433     public Element put(Object key, Element element, long sizeOf) {
434         int hash = hash(key.hashCode());
435         return segmentFor(hash).put(key, hash, element, sizeOf, false, false, true);
436     }
437
438     public Element putIfAbsent(Object key, Element element, long sizeOf) {
439         int hash = hash(key.hashCode());
440         return segmentFor(hash).put(key, hash, element, sizeOf, true, false, true);
441     }
442
443     public Element remove(Object key) {
444         int hash = hash(key.hashCode());
445         return segmentFor(hash).remove(key, hash, null);
446     }
447
448     public boolean remove(Object key, Object value) {
449         int hash = hash(key.hashCode());
450         if (value == null)
451             return false;
452         return segmentFor(hash).remove(key, hash, value) != null;
453     }
454
455     public void clear() {
456         for (int i = 0; i < segments.length; ++i)
457             segments[i].clear();
458     }
459
460     public void unpinAll() {
461         for (Segment segment : this.segments) {
462             segment.unpinAll();
463         }
464     }
465
466     public void setPinned(Object key, boolean pinned) {
467         int hash = hash(key.hashCode());
468         segmentFor(hash).setPinned(key, pinned, hash);
469     }
470
471     public boolean isPinned(Object key) {
472         int hash = hash(key.hashCode());
473         return segmentFor(hash).isPinned(key, hash);
474     }
475
476     public Set<Object> keySet() {
477         Set<Object> ks = keySet;
478         return (ks != null) ? ks : (keySet = new KeySet());
479     }
480
481     public Collection<Element> values() {
482         Collection<Element> vs = values;
483         return (vs != null) ? vs : (values = new Values());
484     }
485
486     public Set<Entry<Object, Element>> entrySet() {
487         Set<Entry<Object, Element>> es = entrySet;
488         return (es != null) ? es : (entrySet = new EntrySet());
489     }
490
491     protected Segment createSegment(int initialCapacity, float lf) {
492         return new Segment(initialCapacity, lf);
493     }
494
495     public boolean evict() {
496         return getRandomSegment().evict();
497     }
498
499     private Segment getRandomSegment() {
500         int randomHash = rndm.nextInt();
501         return segments[((randomHash >>> segmentShift) & segmentMask)];
502     }
503
504     public void recalculateSize(Object key) {
505         int hash = hash(key.hashCode());
506         segmentFor(hash).recalculateSize(key, hash);
507     }
508
509     public Set pinnedKeySet() {
510         Set<Object> pks = pinnedKeySet;
511         return (pks != null) ? pks : (pinnedKeySet = new PinnedKeySet());
512     }
513
514     /**
515      * Returns the segment that should be used for key with given hash
516      * @param hash the hash code for the key
517      * @return the segment
518      */
519     protected final Segment segmentFor(int hash) {
520         return segments[(hash >>> segmentShift) & segmentMask];
521     }
522
523     protected final List<Segment> segments() {
524         return Collections.unmodifiableList(Arrays.asList(segments));
525     }
526
527     public class Segment extends ReentrantReadWriteLock {
528
529         private static final int MAX_EVICTION = 5;
530
531         /**
532          * The number of elements in this segment's region.
533          */
534         protected volatile int count;
535
536         /**
537          * Number of updates that alter the size of the table. This is
538          * used during bulk-read methods to make sure they see a
539          * consistent snapshot: If modCounts change during a traversal
540          * of segments computing size or checking containsValue, then
541          * we might have an inconsistent view of state so (usually)
542          * must retry.
543          */
544         int modCount;
545
546         /**
547          * The table is rehashed when its size exceeds this threshold.
548          * (The value of this field is always <tt>(int)(capacity *
549          * loadFactor)</tt>.)
550          */
551         int threshold;
552
553         /**
554          * The per-segment table.
555          */
556         protected volatile HashEntry[] table;
557
558         /**
559          * The load factor for the hash table.  Even though this value
560          * is same for all segments, it is replicated to avoid needing
561          * links to outer object.
562          * @serial
563          */
564         final float loadFactor;
565
566         private Iterator<HashEntry> evictionIterator;
567         private boolean fullyPinned;
568         protected volatile int pinnedCount;
569         protected volatile int numDummyPinnedKeys;
570
571         protected Segment(int initialCapacity, float lf) {
572             loadFactor = lf;
573             setTable(new HashEntry[initialCapacity]);
574         }
575
576         protected void preRemove(HashEntry e) {
577
578         }
579
580         protected void postInstall(Object key, Element value, boolean pinned) {
581
582         }
583
584         /**
585          * Sets table to new HashEntry array.
586          * Call only while holding lock or in constructor.
587          */
588         void setTable(HashEntry[] newTable) {
589             threshold = (int)(newTable.length * loadFactor);
590             table = newTable;
591         }
592
593         /**
594          * Returns properly casted first entry of bin for given hash.
595          */
596         protected HashEntry getFirst(int hash) {
597             HashEntry[] tab = table;
598             return tab[hash & (tab.length - 1)];
599         }
600
601         public void setPinned(Object key, boolean pinned, int hash) {
602             writeLock().lock();
603             try {
604                 HashEntry e = getFirst(hash);
605                 while (e != null && (e.hash != hash || !key.equals(e.key)))
606                     e = e.next;
607                 if (e != null) {
608                     if (pinned && !e.pinned) {
609                         pinnedCount++;
610                         e.pinned = true;
611                         postInstall(e.key, e.value, true);
612                     } else if (!pinned && e.pinned) {
613                         pinnedCount--;
614                         if(!e.checkAndAssertDummyPinnedEntry()) {
615                             e.pinned = false;
616                             postInstall(e.key, e.value, false);
617                         } else {
618                             HashEntry[] tab = table;
619                             int index = hash & (tab.length - 1);
620                             HashEntry first = tab[index];
621                             tab[index] = removeAndGetFirst(e, first);
622                             --count;
623                             --numDummyPinnedKeys;
624                             ++modCount;
625                         }
626                     }
627                 } else if (pinned) {
628                     put(key, hash, DUMMY_PINNED_ELEMENT, 0, false, true, true);
629                     pinnedCount++;
630                     numDummyPinnedKeys++;
631                 }
632             } finally {
633                 writeLock().unlock();
634             }
635         }
636
637         private HashEntry removeAndGetFirst(HashEntry e, HashEntry first) {
638             preRemove(e);
639             // All entries following removed node can stay
640             // in list, but all preceding ones need to be
641             // cloned.
642             HashEntry newFirst = e.next;
643             for (HashEntry p = first; p != e; p = p.next)
644                 newFirst = relinkHashEntry(p, newFirst);
645             return newFirst;
646         }
647
648         public boolean isPinned(Object key, int hash) {
649             readLock().lock();
650             try {
651                 HashEntry e = getFirst(hash);
652                 while (e != null && (e.hash != hash || !key.equals(e.key)))
653                     e = e.next;
654                 if (e != null) {
655                     return e.pinned;
656                 }
657                 return false;
658             } finally {
659                 readLock().unlock();
660             }
661         }
662
663         public void unpinAll() {
664             writeLock().lock();
665             try {
666                 if(numDummyPinnedKeys == count) {
667                     clear();
668                     return;
669                 }
670
671                 // using clock iterator here so maintaining number of visited entries
672                 int numVisited = 0;
673                 int dummyPinnedKeys = 0;
674                 for(int i=0; i < table.length && numVisited < count; ++i) {
675                     HashEntry newFirst = null;
676                     HashEntry current = table[i];
677                     while(current != null && numVisited < count) {
678                         if(!current.checkAndAssertDummyPinnedEntry()) {
679                             current.pinned = false;
680                             newFirst = relinkHashEntry(current, newFirst);
681                         } else {
682                             preRemove(current);
683                             ++dummyPinnedKeys;
684                         }
685                         ++numVisited;
686                         current = current.next;
687                     }
688                     table[i] = newFirst;
689                 }
690                 if(numDummyPinnedKeys != dummyPinnedKeys) {
691                     throw new IllegalStateException("numDummyPinnedKeys "+numDummyPinnedKeys+" but dummyPinnedKeys "+dummyPinnedKeys);
692                 }
693                 if(dummyPinnedKeys > 0) {
694                     count -= dummyPinnedKeys;
695                     ++modCount;
696                 }
697                 pinnedCount = numDummyPinnedKeys = 0;
698             } finally {
699                 writeLock().unlock();
700             }
701         }
702
703         protected HashEntry createHashEntry(Object key, int hash, HashEntry next, Element value, long sizeOf, boolean pinned) {
704             return new HashEntry(key, hash, next, value, sizeOf, pinned);
705         }
706
707         protected HashEntry relinkHashEntry(HashEntry e, HashEntry next) {
708             return new HashEntry(e.key, e.hash, next, e.value, e.sizeOf, e.pinned);
709         }
710
711         protected void clear() {
712             writeLock().lock();
713             try {
714                 if (count != 0) {
715                     HashEntry[] tab = table;
716                     for (int i = 0; i < tab.length ; i++)
717                         tab[i] = null;
718                     ++modCount;
719                     numDummyPinnedKeys = 0;
720                     pinnedCount = 0;
721                     count = 0; // write-volatile
722                 }
723                 evictionIterator = null;
724             } finally {
725                 writeLock().unlock();
726             }
727         }
728
729         Element remove(Object key, int hash, Object value) {
730             writeLock().lock();
731             try {
732                 int c = count - 1;
733                 HashEntry[] tab = table;
734                 int index = hash & (tab.length - 1);
735                 HashEntry first = tab[index];
736                 HashEntry e = first;
737                 while (e != null && (e.hash != hash || !key.equals(e.key)))
738                     e = e.next;
739
740                 Element oldValue = null;
741                 if (e != null) {
742                     Element v = e.value;
743                     if (value == null || value.equals(v)) {
744                         oldValue = v;
745                         ++modCount;
746                         if(!e.pinned) {
747                             tab[index] = removeAndGetFirst(e, first);
748                         } else {
749                             ++c;
750                             if (oldValue == DUMMY_PINNED_ELEMENT) {
751                                oldValue = null;
752                             } else {
753                                 preRemove(e);
754                                 e.value = DUMMY_PINNED_ELEMENT;
755                                 ++numDummyPinnedKeys;
756                             }
757                         }
758                         count = c; // write-volatile
759                         poolAccessor.delete(e.sizeOf);
760                         if(evictionIterator != null && ((SegmentIterator)evictionIterator).nextEntry == e) {
761                             evictionIterator.next();
762                         }
763                     }
764                 }
765                 return oldValue;
766             } finally {
767                 writeLock().unlock();
768             }
769         }
770
771         public void recalculateSize(Object key, int hash) {
772             Element value = null;
773             long oldSize = 0;
774             readLock().lock();
775             try {
776                 HashEntry[] tab = table;
777                 int index = hash & (tab.length - 1);
778                 HashEntry first = tab[index];
779                 HashEntry e = first;
780                 while (e != null && (e.hash != hash || !key.equals(e.key))) {
781                     e = e.next;
782                 }
783                 if (e != null) {
784                     key = e.key;
785                     value = e.value;
786                     oldSize = e.sizeOf;
787                 }
788             } finally {
789                 readLock().unlock();
790             }
791             if (value != null) {
792                 long delta = poolAccessor.replace(oldSize, key, value, storedObject(value), true);
793                 writeLock().lock();
794                 try {
795                     HashEntry e = getFirst(hash);
796                     while (e != null && key != e.key) {
797                         e = e.next;
798                     }
799
800                     if (e != null && e.value == value && oldSize == e.sizeOf) {
801                         e.sizeOf = oldSize + delta;
802                     } else {
803                         poolAccessor.delete(delta);
804                     }
805                 } finally {
806                     writeLock().unlock();
807                 }
808             }
809         }
810
811         protected Element put(Object key, int hash, Element value, long sizeOf, boolean onlyIfAbsent, boolean pinned, boolean fire) {
812             Element[] evicted = new Element[MAX_EVICTION];
813             writeLock().lock();
814             try {
815                 int c = count;
816                 if (c++ > threshold) // ensure capacity
817                     rehash();
818                 HashEntry[] tab = table;
819                 int index = hash & (tab.length - 1);
820                 HashEntry first = tab[index];
821                 HashEntry e = first;
822                 while (e != null && (e.hash != hash || !key.equals(e.key)))
823                     e = e.next;
824
825                 Element oldValue;
826                 if (e != null) {
827                     oldValue = e.value;
828                     if (e.value == DUMMY_PINNED_ELEMENT || !onlyIfAbsent) {
829                         poolAccessor.delete(e.sizeOf);
830                         e.value = value;
831                         e.sizeOf = sizeOf;
832                         if (oldValue == DUMMY_PINNED_ELEMENT && value != DUMMY_PINNED_ELEMENT) {
833                             --numDummyPinnedKeys;
834                             oldValue = null;
835                         }
836                         if (fire) {
837                             postInstall(key, value, e.pinned);
838                         }
839                     }
840                 } else {
841                     oldValue = null;
842                     ++modCount;
843                     tab[index] = createHashEntry(key, hash, first, value, sizeOf, pinned);
844                     count = c; // write-volatile
845                     if (fire) {
846                         postInstall(key, value, pinned);
847                     }
848                 }
849
850                 if(!pinned && (onlyIfAbsent && oldValue != null || !onlyIfAbsent)) {
851                     if (!isPinned(key, hash)) {
852                         this.fullyPinned = false;
853                     }
854                     if (!fullyPinned && SelectableConcurrentHashMap.this.maxSize > 0) {
855                         int runs = Math.min(MAX_EVICTION, SelectableConcurrentHashMap.this.quickSize() - (int) SelectableConcurrentHashMap.this.maxSize);
856                         while (runs-- > 0) {
857                             Element evict = nextExpiredOrToEvict(value);
858                             if (evict != null) {
859                                 Element removed;
860                                 while ((removed = remove(evict.getKey(), hash(evict.getKey().hashCode()), null)) == null) {
861                                     evict = nextExpiredOrToEvict(value);
862                                     if (evict == null) {
863                                         break;
864                                     }
865                                 }
866                                 evicted[runs] = removed;
867                             }
868                         }
869                     }
870                 }
871                 return oldValue;
872             } finally {
873                 writeLock().unlock();
874                 for (Element element : evicted) {
875                     notifyEvictionOrExpiry(element);
876                 }
877             }
878         }
879
880         private void notifyEvictionOrExpiry(final Element element) {
881             if(element != null && cacheEventNotificationService != null) {
882                 if (element.isExpired()) {
883                     cacheEventNotificationService.notifyElementExpiry(element, false);
884                 } else {
885                     cacheEventNotificationService.notifyElementEvicted(element, false);
886                 }
887             }
888         }
889
890         Element get(final Object key, final int hash) {
891             readLock().lock();
892             try {
893                 if (count != 0) { // read-volatile
894                     HashEntry e = getFirst(hash);
895                     while (e != null) {
896                         if (e.hash == hash && key.equals(e.key) && !e.value.equals(DUMMY_PINNED_ELEMENT)) {
897                             e.accessed = true;
898                             return e.value;
899                         }
900                         e = e.next;
901                     }
902                 }
903                 return null;
904             } finally {
905                 readLock().unlock();
906             }
907         }
908
909         boolean containsKey(final Object key, final int hash) {
910             readLock().lock();
911             try {
912                 if (count != 0) { // read-volatile
913                     HashEntry e = getFirst(hash);
914                     while (e != null) {
915                         if (e.hash == hash && key.equals(e.key) && !e.value.equals(DUMMY_PINNED_ELEMENT))
916                             return true;
917                         e = e.next;
918                     }
919                 }
920                 return false;
921             } finally {
922                 readLock().unlock();
923             }
924         }
925
926         boolean containsValue(Object value) {
927             readLock().lock();
928             try {
929                 if (count != 0) { // read-volatile
930                     HashEntry[] tab = table;
931                     int len = tab.length;
932                     for (int i = 0 ; i < len; i++) {
933                         for (HashEntry e = tab[i]; e != null; e = e.next) {
934                             Element v = e.value;
935                             if (value.equals(v))
936                                 return true;
937                         }
938                     }
939                 }
940                 return false;
941             } finally {
942                 readLock().unlock();
943             }
944         }
945
946         private Element nextExpiredOrToEvict(final Element justAdded) {
947
948             Element lastUnpinned = null;
949             int i = 0;
950
951             while (!fullyPinned && i++ < count) {
952                 if (evictionIterator == null || !evictionIterator.hasNext()) {
953                     evictionIterator = iterator();
954                 }
955                 final HashEntry next = evictionIterator.next();
956                 if (next.value.isExpired() || !next.accessed) {
957                     return next.value;
958                 } else {
959                     final boolean pinned = next.pinned;
960                     if (!pinned && next.value != justAdded) {
961                         lastUnpinned = next.value;
962                     }
963                     next.accessed = pinned;
964                 }
965             }
966
967             this.fullyPinned = !this.fullyPinned && i >= count && lastUnpinned == null;
968
969             return lastUnpinned;
970         }
971
972         protected Iterator<HashEntry> iterator() {
973             return new SegmentIterator(this);
974         }
975
976         boolean evict() {
977             Element remove = null;
978             writeLock().lock();
979             try {
980                 Element evict = nextExpiredOrToEvict(null);
981                 if (evict != null) {
982                     remove = remove(evict.getKey(), hash(evict.getKey().hashCode()), null);
983                 }
984             } finally {
985                 writeLock().unlock();
986             }
987             notifyEvictionOrExpiry(remove);
988             return remove != null;
989         }
990
991         void rehash() {
992             HashEntry[] oldTable = table;
993             int oldCapacity = oldTable.length;
994             if (oldCapacity >= MAXIMUM_CAPACITY)
995                 return;
996
997             /*
998              * Reclassify nodes in each list to new Map.  Because we are
999              * using power-of-two expansion, the elements from each bin
1000              * must either stay at same index, or move with a power of two
1001              * offset. We eliminate unnecessary node creation by catching
1002              * cases where old nodes can be reused because their next
1003              * fields won't change. Statistically, at the default
1004              * threshold, only about one-sixth of them need cloning when
1005              * a table doubles. The nodes they replace will be garbage
1006              * collectable as soon as they are no longer referenced by any
1007              * reader thread that may be in the midst of traversing table
1008              * right now.
1009              */
1010
1011             HashEntry[] newTable = new HashEntry[oldCapacity << 1];
1012             threshold = (int)(newTable.length * loadFactor);
1013             int sizeMask = newTable.length - 1;
1014             for (int i = 0; i < oldCapacity ; i++) {
1015                 // We need to guarantee that any existing reads of old Map can
1016                 //  proceed. So we cannot yet null out each bin.
1017                 HashEntry e = oldTable[i];
1018
1019                 if (e != null) {
1020                     HashEntry next = e.next;
1021                     int idx = e.hash & sizeMask;
1022
1023                     //  Single node on list
1024                     if (next == null)
1025                         newTable[idx] = e;
1026
1027                     else {
1028                         // Reuse trailing consecutive sequence at same slot
1029                         HashEntry lastRun = e;
1030                         int lastIdx = idx;
1031                         for (HashEntry last = next;
1032                              last != null;
1033                              last = last.next) {
1034                             int k = last.hash & sizeMask;
1035                             if (k != lastIdx) {
1036                                 lastIdx = k;
1037                                 lastRun = last;
1038                             }
1039                         }
1040                         newTable[lastIdx] = lastRun;
1041
1042                         // Clone all remaining nodes
1043                         for (HashEntry p = e; p != lastRun; p = p.next) {
1044                             int k = p.hash & sizeMask;
1045                             HashEntry n = newTable[k];
1046                             newTable[k] = relinkHashEntry(p, n);
1047                         }
1048                     }
1049                 }
1050             }
1051             table = newTable;
1052             if (evictionIterator != null) {
1053                 evictionIterator = iterator();
1054             }
1055         }
1056
1057         Iterator<HashEntry> getEvictionIterator() {
1058             return evictionIterator;
1059         }
1060     }
1061
1062     public static class HashEntry {
1063         public final Object key;
1064         public final int hash;
1065         public final HashEntry next;
1066
1067         public volatile Element value;
1068
1069         public volatile boolean pinned;
1070         public volatile long sizeOf;
1071         public volatile boolean accessed = true;
1072
1073         protected HashEntry(Object key, int hash, HashEntry next, Element value, long sizeOf, boolean pinned) {
1074             this.key = key;
1075             this.hash = hash;
1076             this.next = next;
1077             this.value = value;
1078             this.sizeOf = sizeOf;
1079             this.pinned = pinned;
1080         }
1081
1082         boolean checkAndAssertDummyPinnedEntry() {
1083             if(value == DUMMY_PINNED_ELEMENT && !pinned) {
1084                 throw new IllegalStateException("HashEntry value is DUMMY_PINNED_ELEMENT but pinned "+pinned);
1085             }
1086             return value == DUMMY_PINNED_ELEMENT;
1087         }
1088     }
1089
1090     static class SegmentIterator implements Iterator<HashEntry> {
1091
1092         int nextTableIndex;
1093         HashEntry[] currentTable;
1094         HashEntry nextEntry;
1095         private final Segment seg;
1096
1097         private SegmentIterator(final Segment memoryStoreSegment) {
1098             nextTableIndex = -1;
1099             this.seg = memoryStoreSegment;
1100             advance();
1101         }
1102
1103         public boolean hasNext() {
1104             return nextEntry != null;
1105         }
1106
1107         public HashEntry next() {
1108             if (nextEntry == null)
1109                 return null;
1110             HashEntry lastReturned = nextEntry;
1111             advance();
1112             return lastReturned;
1113         }
1114
1115         public void remove() {
1116             throw new UnsupportedOperationException("remove is not supported");
1117         }
1118
1119         final void advance() {
1120             if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1121                 return;
1122             while (nextTableIndex >= 0) {
1123                 if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1124                     return;
1125             }
1126             if (seg.count != 0) {
1127                 currentTable = seg.table;
1128                 for (int j = currentTable.length - 1; j >= 0; --j) {
1129                     if ( (nextEntry = currentTable[j]) != null) {
1130                         nextTableIndex = j - 1;
1131                         return;
1132                     }
1133                 }
1134             }
1135         }
1136     }
1137
1138     @IgnoreSizeOf
1139     protected static class DummyPinnedKey implements Serializable {
1140
1141     }
1142
1143     @IgnoreSizeOf
1144     protected static class DummyPinnedValue implements Serializable {
1145
1146     }
1147
1148     final class KeySet extends AbstractSet<Object> {
1149
1150         @Override
1151         public Iterator<Object> iterator() {
1152             return new KeyIterator();
1153         }
1154
1155         @Override
1156         public int size() {
1157             return SelectableConcurrentHashMap.this.size();
1158         }
1159
1160         @Override
1161         public boolean isEmpty() {
1162             return SelectableConcurrentHashMap.this.isEmpty();
1163         }
1164
1165         @Override
1166         public boolean contains(Object o) {
1167             return SelectableConcurrentHashMap.this.containsKey(o);
1168         }
1169
1170         @Override
1171         public boolean remove(Object o) {
1172             return SelectableConcurrentHashMap.this.remove(o) != null;
1173         }
1174
1175         @Override
1176         public void clear() {
1177             SelectableConcurrentHashMap.this.clear();
1178         }
1179
1180         @Override
1181         public Object[] toArray() {
1182             Collection<Object> c = new ArrayList<Object>();
1183             for (Object object : this)
1184                 c.add(object);
1185             return c.toArray();
1186         }
1187         @Override
1188         public <T> T[] toArray(T[] a) {
1189             Collection<Object> c = new ArrayList<Object>();
1190             for (Object object : this)
1191                 c.add(object);
1192             return c.toArray(a);
1193         }
1194     }
1195
1196     final class Values extends AbstractCollection<Element> {
1197
1198         @Override
1199         public Iterator<Element> iterator() {
1200             return new ValueIterator();
1201         }
1202
1203         @Override
1204         public int size() {
1205             return SelectableConcurrentHashMap.this.size();
1206         }
1207
1208         @Override
1209         public boolean isEmpty() {
1210             return SelectableConcurrentHashMap.this.isEmpty();
1211         }
1212
1213         @Override
1214         public boolean contains(Object o) {
1215             return SelectableConcurrentHashMap.this.containsValue(o);
1216         }
1217
1218         @Override
1219         public void clear() {
1220             SelectableConcurrentHashMap.this.clear();
1221         }
1222
1223         @Override
1224         public Object[] toArray() {
1225             Collection<Object> c = new ArrayList<Object>();
1226             for (Object object : this)
1227                 c.add(object);
1228             return c.toArray();
1229         }
1230
1231         @Override
1232         public <T> T[] toArray(T[] a) {
1233             Collection<Object> c = new ArrayList<Object>();
1234             for (Object object : this)
1235                 c.add(object);
1236             return c.toArray(a);
1237         }
1238     }
1239
1240     final class EntrySet extends AbstractSet<Entry<Object, Element>> {
1241
1242         @Override
1243         public Iterator<Entry<Object, Element>> iterator() {
1244             return new EntryIterator();
1245         }
1246
1247         @Override
1248         public int size() {
1249             return SelectableConcurrentHashMap.this.size();
1250         }
1251
1252         @Override
1253         public boolean isEmpty() {
1254             return SelectableConcurrentHashMap.this.isEmpty();
1255         }
1256
1257         @Override
1258         public boolean contains(Object o) {
1259             if (!(o instanceof Entry))
1260                 return false;
1261             Entry<?,?> e = (Entry<?,?>)o;
1262             Element v = SelectableConcurrentHashMap.this.get(e.getKey());
1263             return v != null && v.equals(e.getValue());
1264         }
1265
1266         @Override
1267         public boolean remove(Object o) {
1268             if (!(o instanceof Entry))
1269                 return false;
1270             Entry<?,?> e = (Entry<?,?>)o;
1271             return SelectableConcurrentHashMap.this.remove(e.getKey(), e.getValue());
1272         }
1273
1274         @Override
1275         public void clear() {
1276             SelectableConcurrentHashMap.this.clear();
1277         }
1278
1279         @Override
1280         public Object[] toArray() {
1281             Collection<Object> c = new ArrayList<Object>();
1282             for (Object object : this)
1283                 c.add(object);
1284             return c.toArray();
1285         }
1286         @Override
1287         public <T> T[] toArray(T[] a) {
1288             Collection<Object> c = new ArrayList<Object>();
1289             for (Object object : this)
1290                 c.add(object);
1291             return c.toArray(a);
1292         }
1293     }
1294
1295     class KeyIterator extends HashEntryIterator implements Iterator<Object> {
1296
1297         @Override
1298         public Object next() {
1299             return nextEntry().key;
1300         }
1301     }
1302
1303     final class ValueIterator extends HashEntryIterator implements Iterator<Element> {
1304
1305         @Override
1306         public Element next() {
1307             return nextEntry().value;
1308         }
1309     }
1310
1311     final class EntryIterator extends HashEntryIterator implements Iterator<Entry<Object, Element>> {
1312
1313         @Override
1314         public Entry<Object, Element> next() {
1315             HashEntry entry = nextEntry();
1316             final Object key = entry.key;
1317             final Element value = entry.value;
1318             return new Entry<Object, Element>() {
1319
1320                 public Object getKey() {
1321                     return key;
1322                 }
1323
1324                 public Element getValue() {
1325                     return value;
1326                 }
1327
1328                 public Element setValue(Element value) {
1329                   throw new UnsupportedOperationException();
1330                 }
1331             };
1332         }
1333     }
1334
1335     abstract class HashEntryIterator extends HashIterator {
1336         private HashEntry myNextEntry;
1337
1338         public HashEntryIterator() {
1339             myNextEntry = advanceToNextEntry();
1340         }
1341
1342         @Override
1343         public void remove() {
1344             throw new UnsupportedOperationException("remove is not supported");
1345         }
1346
1347         @Override
1348         public HashEntry nextEntry() {
1349             if (myNextEntry == null) {
1350                 throw new NoSuchElementException();
1351             }
1352             HashEntry entry = myNextEntry;
1353             myNextEntry = advanceToNextEntry();
1354             return entry;
1355         }
1356
1357         @Override
1358         public boolean hasNext() {
1359             return myNextEntry != null;
1360         }
1361
1362         private HashEntry advanceToNextEntry() {
1363             HashEntry myEntry = null;
1364             while (super.hasNext()) {
1365                 myEntry = super.nextEntry();
1366                 if (myEntry != null && !hideValue(myEntry)) {
1367                     break;
1368                 } else {
1369                     myEntry = null;
1370                 }
1371             }
1372             return myEntry;
1373         }
1374
1375         protected boolean hideValue(HashEntry hashEntry) {
1376             return hashEntry.value == DUMMY_PINNED_ELEMENT;
1377         }
1378     }
1379
1380     abstract class HashIterator {
1381         int nextSegmentIndex;
1382         int nextTableIndex;
1383         HashEntry[] currentTable;
1384         HashEntry nextEntry;
1385         HashEntry lastReturned;
1386
1387         HashIterator() {
1388             nextSegmentIndex = segments.length - 1;
1389             nextTableIndex = -1;
1390             advance();
1391         }
1392
1393         public boolean hasMoreElements() { return hasNext(); }
1394
1395         final void advance() {
1396             if (nextEntry != null && (nextEntry = nextEntry.next) != null)
1397                 return;
1398
1399             while (nextTableIndex >= 0) {
1400                 if ( (nextEntry = currentTable[nextTableIndex--]) != null)
1401                     return;
1402             }
1403
1404             while (nextSegmentIndex >= 0) {
1405                 Segment seg = segments[nextSegmentIndex--];
1406                 if (seg.count != 0) {
1407                     currentTable = seg.table;
1408                     for (int j = currentTable.length - 1; j >= 0; --j) {
1409                         if ( (nextEntry = currentTable[j]) != null) {
1410                             nextTableIndex = j - 1;
1411                             return;
1412                         }
1413                     }
1414                 }
1415             }
1416         }
1417
1418         public boolean hasNext() { return nextEntry != null; }
1419
1420         HashEntry nextEntry() {
1421             if (nextEntry == null)
1422                 throw new NoSuchElementException();
1423             lastReturned = nextEntry;
1424             advance();
1425             return lastReturned;
1426         }
1427
1428         public void remove() {
1429             if (lastReturned == null)
1430                 throw new IllegalStateException();
1431             SelectableConcurrentHashMap.this.remove(lastReturned.key);
1432             lastReturned = null;
1433         }
1434     }
1435
1436     private class PinnedKeySet extends AbstractSet<Object> {
1437         @Override
1438         public Iterator<Object> iterator() {
1439             return new PinnedKeyIterator();
1440         }
1441
1442         @Override
1443         public int size() {
1444             return pinnedSize();
1445         }
1446
1447         @Override
1448         public boolean contains(final Object o) {
1449             return SelectableConcurrentHashMap.this.isPinned(o) && SelectableConcurrentHashMap.this.containsKey(o);
1450         }
1451     }
1452
1453     private class PinnedKeyIterator extends KeyIterator {
1454         @Override
1455         protected boolean hideValue(final HashEntry hashEntry) {
1456             return super.hideValue(hashEntry) || !hashEntry.pinned;
1457         }
1458     }
1459
1460     protected static int hash(int h) {
1461         // Spread bits to regularize both segment and index locations,
1462         // using variant of single-word Wang/Jenkins hash.
1463         h += (h <<  15) ^ 0xffffcd7d;
1464         h ^= (h >>> 10);
1465         h += (h <<   3);
1466         h ^= (h >>>  6);
1467         h += (h <<   2) + (h << 14);
1468         return h ^ (h >>> 16);
1469     }
1470 }
1471