01: /*
02: Copyright 2004 Philip Jacob <phil@whirlycott.com>
03: Seth Fitzsimmons <seth@note.amherst.edu>
04:
05: Licensed under the Apache License, Version 2.0 (the "License");
06: you may not use this file except in compliance with the License.
07: You may obtain a copy of the License at
08:
09: http://www.apache.org/licenses/LICENSE-2.0
10:
11: Unless required by applicable law or agreed to in writing, software
12: distributed under the License is distributed on an "AS IS" BASIS,
13: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14: See the License for the specific language governing permissions and
15: limitations under the License.
16: */
17:
18: package com.whirlycott.cache.policy;
19:
20: import java.util.ArrayList;
21: import java.util.Collections;
22: import java.util.List;
23: import java.util.Map;
24: import java.util.Map.Entry;
25: import java.util.concurrent.ConcurrentHashMap;
26:
27: import org.apache.commons.logging.Log;
28: import org.apache.commons.logging.LogFactory;
29:
30: import com.whirlycott.cache.CacheMaintenancePolicy;
31: import com.whirlycott.cache.ManagedCache;
32: import com.whirlycott.cache.Messages;
33:
34: /**
35: * This policy removes cached items, biased towards least frequently used (LFU) Items.
36: *
37: * @author Seth Fitzsimmons
38: */
39: public class LFUMaintenancePolicy<K, V> implements
40: CacheMaintenancePolicy<K, V> {
41:
42: private static final Log log = LogFactory
43: .getLog(LFUMaintenancePolicy.class);
44:
45: public void performMaintenance(ManagedCache<K, V> managedCache,
46: int maxSize) {
47: if (log.isDebugEnabled()) {
48: log
49: .debug(Messages
50: .getString("LFUMaintenancePolicy.performing_lfu_maintenance"));
51:
52: log.debug(Messages.getCompoundString(
53: "CacheMaintenancePolicy.report_items", maxSize,
54: managedCache.size()));
55: }
56:
57: // Sort the entries in the cache.
58: int currentSize = managedCache.size();
59: if (maxSize < currentSize) {
60: if (log.isDebugEnabled()) {
61: log
62: .debug(Messages
63: .getCompoundString(
64: "CacheMaintenancePolicy.clearing_approximately",
65: currentSize - maxSize));
66: }
67: final List<Map.Entry<K, V>> entries = new ArrayList<Map.Entry<K, V>>(
68: new ConcurrentHashMap<K, V>(managedCache)
69: .entrySet());
70: Collections.sort(entries, new CountComparator());
71: final List<Map.Entry<K, V>> removeThese = entries.subList(
72: 0, currentSize - maxSize);
73: for (Entry<K, V> entry : removeThese) {
74: if (entry != null) {
75: // final Item evictee = (Item) entry.getValue();
76: // log.trace("Removing: " + entry.getKey() + " (" +
77: // evictee.added + ", " + evictee.used + ", " + evictee.count +
78: // ")");
79: managedCache.remove(entry.getKey());
80: }
81: }
82: if (log.isDebugEnabled()) {
83: log.debug(Messages
84: .getString("LFUMaintenancePolicy.new_size")
85: + managedCache.size());
86: }
87: }
88: }
89: }
|