1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package de.fu_berlin.ties.util;
23
24 import java.util.Iterator;
25 import java.util.Map;
26
27 import org.apache.commons.collections.map.AbstractLinkedMap;
28 import org.apache.commons.collections.map.LRUMap;
29
30 /***
31 * A fixed-size map that uses an flexible adaptable strategy for pruning
32 * entries based on LRU (pruning one the least recently used entries).
33 * Instances of this class are not thread-safe and must be synchronized
34 * externally, if required.
35 *
36 * @author Christian Siefkes
37 * @version $Revision: 1.14 $, $Date: 2006/10/21 16:04:27 $, $Author: siefkes $
38 */
39 public class AdaptableLRUMap extends LRUMap {
40
41 /***
42 * Used to decide which entries to prune.
43 */
44 private final Pruner pruner;
45
46 /***
47 * Used to decide which entries to prune.
48 */
49 private final RemoveCallback removeCallback;
50
51 /***
52 * The number of candidates to consider for each pruning operation.
53 */
54 private final int candidateNumber;
55
56 /***
57 * The number of elements to remove by each pruning operation.
58 */
59 private final int pruneNumber;
60
61 /***
62 * Constructs a new, empty map with the specified initial capacity and
63 * a load factor of 0.8. If the number of candidates is one, this
64 * class behaves like a normal {@link LRUMap}; otherwise the
65 * {@link Pruner} is consulted to decide which entry to prune.
66 *
67 * @param maxSize the maximum size of the map
68 * @param prun Used to decide which entries to prune
69 * @param rmCallback will be called back whenever a key is removed from this
70 * map; might be <code>null</code>
71 * @param candidates The number of candidates to consider for each pruning
72 * operation
73 * @param pruneNum The number of elements to remove by each pruning
74 * operation, must not be larger than <code>candidates</code>
75 * @throws IllegalArgumentException if one of the input parameters is
76 * invalid
77 */
78 public AdaptableLRUMap(final int maxSize, final Pruner prun,
79 final RemoveCallback rmCallback,
80 final int candidates, final int pruneNum)
81 throws IllegalArgumentException {
82 this(maxSize, 0.8f, prun, rmCallback, candidates, pruneNum);
83 }
84
85 /***
86 * Constructs a new, empty map with the specified initial capacity and
87 * load factor. If the number of candidates is one, this
88 * class behaves like a normal {@link LRUMap}; otherwise the
89 * {@link Pruner} is consulted to decide which entry to prune. A callback
90 * object can be specified that will be informed whenever a key is removed
91 * from this map.
92 *
93 * @param maxSize the maximum size of the map
94 * @param loadFactor the load factor
95 * @param prun used to decide which entries to prune
96 * @param rmCallback will be called back whenever a key is removed from this
97 * map; might be <code>null</code>
98 * @param candidates the number of candidates to consider for each pruning
99 * operation
100 * @param pruneNum the number of elements to remove by each pruning
101 * operation, must not be larger than <code>candidates</code>
102 * @throws IllegalArgumentException if one of the input parameters is
103 * invalid
104 */
105 public AdaptableLRUMap(final int maxSize, final float loadFactor,
106 final Pruner prun, final RemoveCallback rmCallback,
107 final int candidates, final int pruneNum)
108 throws IllegalArgumentException {
109 super(maxSize, loadFactor);
110 checkArguments(maxSize, candidates, pruneNum);
111
112 pruner = prun;
113 removeCallback = rmCallback;
114 candidateNumber = candidates;
115 pruneNumber = pruneNum;
116
117
118 threshold = calculateThreshold(data.length, this.loadFactor);
119 }
120
121 /***
122 * Helper method that checks whether constructor arguments are valid and
123 * throws an exception if this is not the case.
124 *
125 * @param maxSize the maximum size of the map
126 * @param candidates The number of candidates to consider for each pruning
127 * operation
128 * @param pruneNum The number of elements to remove by each pruning
129 * operation, must not be larger than <code>candidates</code>
130 * @throws IllegalArgumentException if one of the input parameters is
131 * invalid
132 */
133 private void checkArguments(final int maxSize, final int candidates,
134 final int pruneNum) throws IllegalArgumentException {
135 if ((candidates < 1) || (candidates > maxSize)) {
136 throw new IllegalArgumentException("Number of pruning candidates "
137 + "must be in range from 1 to maxSize (" + maxSize + "): "
138 + candidates);
139 }
140
141 if ((pruneNum < 1) || (pruneNum > candidates)) {
142 throw new IllegalArgumentException("Number of elements to prun "
143 + "must be in range from 1 to number of candidates ("
144 + candidates + "): " + pruneNum);
145 }
146 }
147
148 /***
149 * Returns the number of candidates considered for each pruning operation.
150 * @return the value of the attribute
151 */
152 public int getCandidateNumber() {
153 return candidateNumber;
154 }
155
156 /***
157 * Returns the number of elements removed by each pruning operation.
158 * @return the value of the attribute
159 */
160 public int getPruneNumber() {
161 return pruneNumber;
162 }
163
164 /***
165 * {@inheritDoc}
166 */
167 public Object remove(final Object key) {
168
169 final Object removedValue = super.remove(key);
170
171
172 if (removeCallback != null) {
173 removeCallback.removed(key);
174 }
175
176 return removedValue;
177 }
178
179 /***
180 * Controls removal of one of the least recently used entries from the map.
181 * Lets the pruner decide if there are multiple candidates to consider.
182 *
183 * @param entry the least recently used entry
184 * @return <code>true</code> if the superclass should delete the
185 * specified entry; <code>false</code> if this class took the necessary
186 * action by deleting the first {@link #getPruneNumber()} entries selected
187 * by the pruner
188 */
189 protected boolean removeLRU(final AbstractLinkedMap.LinkEntry entry) {
190 if (candidateNumber > 1) {
191
192 final int consideredCandidates = Math.min(candidateNumber, size());
193 final Map.Entry[] candidates = new Map.Entry[consideredCandidates];
194 final Iterator entryIter = entrySet().iterator();
195
196 for (int i = 0; i < candidates.length; i++) {
197
198 candidates[i] = (Map.Entry) entryIter.next();
199
200 }
201
202
203 final Map.Entry[] resortedEntries =
204 pruner.sortForPruning(candidates);
205
206
207 final int entriesToPrune =
208 Math.min(pruneNumber, resortedEntries.length);
209
210 for (int i = 0; i < entriesToPrune; i++) {
211
212 remove(resortedEntries[i].getKey());
213 }
214
215
216 return false;
217 } else {
218
219
220 if (removeCallback != null) {
221 removeCallback.removed(entry.getKey());
222 }
223 return true;
224 }
225 }
226
227 }