1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.cache;
16
17 import static com.google.common.base.Preconditions.checkNotNull;
18 import static junit.framework.Assert.assertEquals;
19 import static junit.framework.Assert.assertFalse;
20 import static junit.framework.Assert.assertNotNull;
21 import static junit.framework.Assert.assertNotSame;
22 import static junit.framework.Assert.assertNull;
23 import static junit.framework.Assert.assertSame;
24 import static junit.framework.Assert.assertTrue;
25
26 import com.google.common.base.Preconditions;
27 import com.google.common.cache.LocalCache.LocalLoadingCache;
28 import com.google.common.cache.LocalCache.ReferenceEntry;
29 import com.google.common.cache.LocalCache.Segment;
30 import com.google.common.cache.LocalCache.ValueReference;
31 import com.google.common.collect.ImmutableList;
32 import com.google.common.collect.ImmutableMap;
33 import com.google.common.collect.ImmutableSet;
34 import com.google.common.collect.Maps;
35 import com.google.common.collect.Sets;
36 import com.google.common.testing.EqualsTester;
37 import com.google.common.testing.FakeTicker;
38
39 import java.lang.ref.Reference;
40 import java.util.Collection;
41 import java.util.List;
42 import java.util.Map;
43 import java.util.Map.Entry;
44 import java.util.Set;
45 import java.util.concurrent.ConcurrentMap;
46 import java.util.concurrent.TimeUnit;
47 import java.util.concurrent.atomic.AtomicReferenceArray;
48
49 import javax.annotation.Nullable;
50
51
52
53
54
55
56 class CacheTesting {
57
58
59
60
61
62
63
64 @SuppressWarnings("unchecked")
65 static <K, V> void simulateValueReclamation(Cache<K, V> cache, K key) {
66 ReferenceEntry<K, V> entry = getReferenceEntry(cache, key);
67 if (entry != null) {
68 ValueReference<K, V> valueRef = entry.getValueReference();
69
70 Preconditions.checkState(valueRef instanceof Reference);
71 Reference<V> ref = (Reference<V>) valueRef;
72 if (ref != null) {
73 ref.clear();
74 }
75 }
76 }
77
78
79
80
81
82
83 @SuppressWarnings("unchecked")
84 static <K, V> void simulateKeyReclamation(Cache<K, V> cache, K key) {
85 ReferenceEntry<K, V> entry = getReferenceEntry(cache, key);
86
87 Preconditions.checkState(entry instanceof Reference);
88 Reference<?> ref = (Reference<?>) entry;
89 if (ref != null) {
90 ref.clear();
91 }
92 }
93
94 static <K, V> ReferenceEntry<K, V> getReferenceEntry(Cache<K, V> cache, K key) {
95 checkNotNull(cache);
96 checkNotNull(key);
97 LocalCache<K, V> map = toLocalCache(cache);
98 return map.getEntry(key);
99 }
100
101
102
103
104
105 static <K, V> void forceExpandSegment(Cache<K, V> cache, K key) {
106 checkNotNull(cache);
107 checkNotNull(key);
108 LocalCache<K, V> map = toLocalCache(cache);
109 int hash = map.hash(key);
110 Segment<K, V> segment = map.segmentFor(hash);
111 segment.expand();
112 }
113
114
115
116
117
118 static <K, V> LocalCache<K, V> toLocalCache(Cache<K, V> cache) {
119 if (cache instanceof LocalLoadingCache) {
120 return ((LocalLoadingCache<K, V>) cache).localCache;
121 }
122 throw new IllegalArgumentException("Cache of type " + cache.getClass()
123 + " doesn't have a LocalCache.");
124 }
125
126
127
128
129
130 static boolean hasLocalCache(Cache<?, ?> cache) {
131 return (checkNotNull(cache) instanceof LocalLoadingCache);
132 }
133
134 static void drainRecencyQueues(Cache<?, ?> cache) {
135 if (hasLocalCache(cache)) {
136 LocalCache<?, ?> map = toLocalCache(cache);
137 for (Segment<?, ?> segment : map.segments) {
138 drainRecencyQueue(segment);
139 }
140 }
141 }
142
143 static void drainRecencyQueue(Segment<?, ?> segment) {
144 segment.lock();
145 try {
146 segment.cleanUp();
147 } finally {
148 segment.unlock();
149 }
150 }
151
152 static void drainReferenceQueues(Cache<?, ?> cache) {
153 if (hasLocalCache(cache)) {
154 drainReferenceQueues(toLocalCache(cache));
155 }
156 }
157
158 static void drainReferenceQueues(LocalCache<?, ?> cchm) {
159 for (LocalCache.Segment<?, ?> segment : cchm.segments) {
160 drainReferenceQueue(segment);
161 }
162 }
163
164 static void drainReferenceQueue(LocalCache.Segment<?, ?> segment) {
165 segment.lock();
166 try {
167 segment.drainReferenceQueues();
168 } finally {
169 segment.unlock();
170 }
171 }
172
173 static int getTotalSegmentSize(Cache<?, ?> cache) {
174 LocalCache<?, ?> map = toLocalCache(cache);
175 int totalSize = 0;
176 for (Segment<?, ?> segment : map.segments) {
177 totalSize += segment.maxSegmentWeight;
178 }
179 return totalSize;
180 }
181
182
183
184
185
186
187
188 static void checkValidState(Cache<?, ?> cache) {
189 if (hasLocalCache(cache)) {
190 checkValidState(toLocalCache(cache));
191 }
192 }
193
194 static void checkValidState(LocalCache<?, ?> cchm) {
195 for (Segment<?, ?> segment : cchm.segments) {
196 segment.cleanUp();
197 assertFalse(segment.isLocked());
198 Map<?, ?> table = segmentTable(segment);
199
200 segment.cleanUp();
201
202 assertTrue(table.size() <= segment.count);
203 for (Entry<?, ?> entry : table.entrySet()) {
204 assertNotNull(entry.getKey());
205 assertNotNull(entry.getValue());
206 assertSame(entry.getValue(), cchm.get(entry.getKey()));
207 }
208 }
209 checkEviction(cchm);
210 checkExpiration(cchm);
211 }
212
213
214
215
216
217
218 static void checkExpiration(Cache<?, ?> cache) {
219 if (hasLocalCache(cache)) {
220 checkExpiration(toLocalCache(cache));
221 }
222 }
223
224 static void checkExpiration(LocalCache<?, ?> cchm) {
225 for (Segment<?, ?> segment : cchm.segments) {
226 if (cchm.usesWriteQueue()) {
227 Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet();
228
229 ReferenceEntry<?, ?> prev = null;
230 for (ReferenceEntry<?, ?> current : segment.writeQueue) {
231 assertTrue(entries.add(current));
232 if (prev != null) {
233 assertSame(prev, current.getPreviousInWriteQueue());
234 assertSame(prev.getNextInWriteQueue(), current);
235 assertTrue(prev.getWriteTime() <= current.getWriteTime());
236 }
237 Object key = current.getKey();
238 if (key != null) {
239 assertSame(current, segment.getEntry(key, current.getHash()));
240 }
241 prev = current;
242 }
243 assertEquals(segment.count, entries.size());
244 } else {
245 assertTrue(segment.writeQueue.isEmpty());
246 }
247
248 if (cchm.usesAccessQueue()) {
249 Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet();
250
251 ReferenceEntry<?, ?> prev = null;
252 for (ReferenceEntry<?, ?> current : segment.accessQueue) {
253 assertTrue(entries.add(current));
254 if (prev != null) {
255 assertSame(prev, current.getPreviousInAccessQueue());
256 assertSame(prev.getNextInAccessQueue(), current);
257
258 assertTrue(prev.getAccessTime() <= current.getAccessTime()
259 || prev.getAccessTime() - current.getAccessTime() < 1000);
260 }
261 Object key = current.getKey();
262 if (key != null) {
263 assertSame(current, segment.getEntry(key, current.getHash()));
264 }
265 prev = current;
266 }
267 assertEquals(segment.count, entries.size());
268 } else {
269 assertTrue(segment.accessQueue.isEmpty());
270 }
271 }
272 }
273
274
275
276
277
278
279 static void checkEviction(Cache<?, ?> cache) {
280 if (hasLocalCache(cache)) {
281 checkEviction(toLocalCache(cache));
282 }
283 }
284
285 static void checkEviction(LocalCache<?, ?> map) {
286 if (map.evictsBySize()) {
287 for (Segment<?, ?> segment : map.segments) {
288 drainRecencyQueue(segment);
289 assertEquals(0, segment.recencyQueue.size());
290 assertEquals(0, segment.readCount.get());
291
292 ReferenceEntry<?, ?> prev = null;
293 for (ReferenceEntry<?, ?> current : segment.accessQueue) {
294 if (prev != null) {
295 assertSame(prev, current.getPreviousInAccessQueue());
296 assertSame(prev.getNextInAccessQueue(), current);
297 }
298 Object key = current.getKey();
299 if (key != null) {
300 assertSame(current, segment.getEntry(key, current.getHash()));
301 }
302 prev = current;
303 }
304 }
305 } else {
306 for (Segment<?, ?> segment : map.segments) {
307 assertEquals(0, segment.recencyQueue.size());
308 }
309 }
310 }
311
312 static int segmentSize(Segment<?, ?> segment) {
313 Map<?, ?> map = segmentTable(segment);
314 return map.size();
315 }
316
317 static <K, V> Map<K, V> segmentTable(Segment<K, V> segment) {
318 AtomicReferenceArray<? extends ReferenceEntry<K, V>> table = segment.table;
319 Map<K, V> map = Maps.newLinkedHashMap();
320 for (int i = 0; i < table.length(); i++) {
321 for (ReferenceEntry<K, V> entry = table.get(i); entry != null; entry = entry.getNext()) {
322 K key = entry.getKey();
323 V value = entry.getValueReference().get();
324 if (key != null && value != null) {
325 assertNull(map.put(key, value));
326 }
327 }
328 }
329 return map;
330 }
331
332 static int writeQueueSize(Cache<?, ?> cache) {
333 LocalCache<?, ?> cchm = toLocalCache(cache);
334
335 int size = 0;
336 for (Segment<?, ?> segment : cchm.segments) {
337 size += writeQueueSize(segment);
338 }
339 return size;
340 }
341
342 static int writeQueueSize(Segment<?, ?> segment) {
343 return segment.writeQueue.size();
344 }
345
346 static int accessQueueSize(Cache<?, ?> cache) {
347 LocalCache<?, ?> cchm = toLocalCache(cache);
348 int size = 0;
349 for (Segment<?, ?> segment : cchm.segments) {
350 size += accessQueueSize(segment);
351 }
352 return size;
353 }
354
355 static int accessQueueSize(Segment<?, ?> segment) {
356 return segment.accessQueue.size();
357 }
358
359 static int expirationQueueSize(Cache<?, ?> cache) {
360 return Math.max(accessQueueSize(cache), writeQueueSize(cache));
361 }
362
363 static void processPendingNotifications(Cache<?, ?> cache) {
364 if (hasLocalCache(cache)) {
365 LocalCache<?, ?> cchm = toLocalCache(cache);
366 cchm.processPendingNotifications();
367 }
368 }
369
370 interface Receiver<T> {
371 void accept(@Nullable T object);
372 }
373
374
375
376
377
378
379
380
381 static void checkRecency(LoadingCache<Integer, Integer> cache, int maxSize,
382 Receiver<ReferenceEntry<Integer, Integer>> operation) {
383 checkNotNull(operation);
384 if (hasLocalCache(cache)) {
385 warmUp(cache, 0, 2 * maxSize);
386
387 LocalCache<Integer, Integer> cchm = toLocalCache(cache);
388 Segment<?, ?> segment = cchm.segments[0];
389 drainRecencyQueue(segment);
390 assertEquals(maxSize, accessQueueSize(cache));
391 assertEquals(maxSize, cache.size());
392
393 ReferenceEntry<?, ?> originalHead = segment.accessQueue.peek();
394 @SuppressWarnings("unchecked")
395 ReferenceEntry<Integer, Integer> entry = (ReferenceEntry) originalHead;
396 operation.accept(entry);
397 drainRecencyQueue(segment);
398
399 assertNotSame(originalHead, segment.accessQueue.peek());
400 assertEquals(cache.size(), accessQueueSize(cache));
401 }
402 }
403
404
405
406
407 static void warmUp(LoadingCache<Integer, Integer> map, int start, int end) {
408 checkNotNull(map);
409 for (int i = start; i < end; i++) {
410 map.getUnchecked(i);
411 }
412 }
413
414 static void expireEntries(Cache<?, ?> cache, long expiringTime, FakeTicker ticker) {
415 checkNotNull(ticker);
416 expireEntries(toLocalCache(cache), expiringTime, ticker);
417 }
418
419 static void expireEntries(
420 LocalCache<?, ?> cchm, long expiringTime, FakeTicker ticker) {
421
422 for (Segment<?, ?> segment : cchm.segments) {
423 drainRecencyQueue(segment);
424 }
425
426 ticker.advance(2 * expiringTime, TimeUnit.MILLISECONDS);
427
428 long now = ticker.read();
429 for (Segment<?, ?> segment : cchm.segments) {
430 expireEntries(segment, now);
431 assertEquals("Expiration queue must be empty by now", 0, writeQueueSize(segment));
432 assertEquals("Expiration queue must be empty by now", 0, accessQueueSize(segment));
433 assertEquals("Segments must be empty by now", 0, segmentSize(segment));
434 }
435 cchm.processPendingNotifications();
436 }
437
438 static void expireEntries(Segment<?, ?> segment, long now) {
439 segment.lock();
440 try {
441 segment.expireEntries(now);
442 segment.cleanUp();
443 } finally {
444 segment.unlock();
445 }
446 }
447 static void checkEmpty(Cache<?, ?> cache) {
448 assertEquals(0, cache.size());
449 assertFalse(cache.asMap().containsKey(null));
450 assertFalse(cache.asMap().containsKey(6));
451 assertFalse(cache.asMap().containsValue(null));
452 assertFalse(cache.asMap().containsValue(6));
453 checkEmpty(cache.asMap());
454 }
455
456 static void checkEmpty(ConcurrentMap<?, ?> map) {
457 checkEmpty(map.keySet());
458 checkEmpty(map.values());
459 checkEmpty(map.entrySet());
460 assertEquals(ImmutableMap.of(), map);
461 assertEquals(ImmutableMap.of().hashCode(), map.hashCode());
462 assertEquals(ImmutableMap.of().toString(), map.toString());
463
464 if (map instanceof LocalCache) {
465 LocalCache<?, ?> cchm = (LocalCache<?, ?>) map;
466
467 checkValidState(cchm);
468 assertTrue(cchm.isEmpty());
469 assertEquals(0, cchm.size());
470 for (LocalCache.Segment<?, ?> segment : cchm.segments) {
471 assertEquals(0, segment.count);
472 assertEquals(0, segmentSize(segment));
473 assertTrue(segment.writeQueue.isEmpty());
474 assertTrue(segment.accessQueue.isEmpty());
475 }
476 }
477 }
478
479 static void checkEmpty(Collection<?> collection) {
480 assertTrue(collection.isEmpty());
481 assertEquals(0, collection.size());
482 assertFalse(collection.iterator().hasNext());
483 assertEquals(0, collection.toArray().length);
484 assertEquals(0, collection.toArray(new Object[0]).length);
485 if (collection instanceof Set) {
486 new EqualsTester()
487 .addEqualityGroup(ImmutableSet.of(), collection)
488 .addEqualityGroup(ImmutableSet.of(""))
489 .testEquals();
490 } else if (collection instanceof List) {
491 new EqualsTester()
492 .addEqualityGroup(ImmutableList.of(), collection)
493 .addEqualityGroup(ImmutableList.of(""))
494 .testEquals();
495 }
496 }
497 }