1 /***
2 * Copyright 2003-2010 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.util.ArrayList;
19 import java.util.Random;
20 import java.util.concurrent.locks.ReentrantReadWriteLock;
21
22 import net.sf.ehcache.Element;
23
24 /***
25 * SelectableConcurrentHashMap subclasses a repackaged version of ConcurrentHashMap
26 * ito allow efficient random sampling of the map values.
27 * <p>
28 * The random sampling technique involves randomly selecting a map Segment, and then
29 * selecting a number of random entry chains from that segment.
30 *
31 * @author Chris Dennis
32 */
33 public class SelectableConcurrentHashMap extends ConcurrentHashMap<Object, Element> {
34
35 private final Random rndm = new Random();
36
37 public SelectableConcurrentHashMap(int initialCapacity, float loadFactor, int concurrency) {
38 super(initialCapacity, loadFactor, concurrency);
39 }
40
41 public Element[] getRandomValues(final int size, Object keyHint) {
42 ArrayList<Element> sampled = new ArrayList<Element>(size * 2);
43
44
45 int randomHash = rndm.nextInt();
46
47 final int segmentStart;
48 if (keyHint == null) {
49 segmentStart = (randomHash >>> segmentShift) & segmentMask;
50 } else {
51 segmentStart = (hash(keyHint.hashCode()) >>> segmentShift) & segmentMask;
52 }
53
54 int segmentIndex = segmentStart;
55 do {
56 final HashEntry<Object, Element>[] table = segments[segmentIndex].table;
57 final int tableStart = randomHash & (table.length - 1);
58 int tableIndex = tableStart;
59 do {
60 for (HashEntry<Object, Element> e = table[tableIndex]; e != null; e = e.next) {
61 Element value = e.value;
62 if (value != null && (value.isExpired() || !value.isPinned())) {
63 sampled.add(value);
64 }
65 }
66
67 if (sampled.size() >= size) {
68 return sampled.toArray(new Element[sampled.size()]);
69 }
70
71
72 tableIndex = (tableIndex + 1) & (table.length - 1);
73 } while (tableIndex != tableStart);
74
75
76 segmentIndex = (segmentIndex + 1) & segmentMask;
77 } while (segmentIndex != segmentStart);
78
79 return sampled.toArray(new Element[sampled.size()]);
80 }
81
82 /***
83 * Return an object of the kind which will be stored when
84 * the element is going to be inserted
85 * @param e the element
86 * @return an object looking-alike the stored one
87 */
88 public Object storedObject(Element e) {
89 return new HashEntry<Object, Element>(null, 0, null, e);
90 }
91
92 /***
93 * Returns the number of key-value mappings in this map without locking anything.
94 * This may not give the exact element count as locking is avoided.
95 * If the map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
96 * <tt>Integer.MAX_VALUE</tt>.
97 *
98 * @return the number of key-value mappings in this map
99 */
100 public int quickSize() {
101 long size = 0;
102
103 for (Segment<Object, Element> segment : this.segments) {
104 size += segment.count;
105 }
106
107 if (size > Integer.MAX_VALUE)
108 return Integer.MAX_VALUE;
109 return (int) size;
110 }
111
112
113 public ReentrantReadWriteLock lockFor(Object key) {
114 int hash = hash(key.hashCode());
115 return segmentFor(hash);
116 }
117
118 public ReentrantReadWriteLock[] locks() {
119 return segments;
120 }
121
122 }