View Javadoc

1   /*
2    * Copyright (C) 2004-2006 Christian Siefkes <christian@siefkes.net>.
3    * Development of this software is supported by the German Research Society,
4    * Berlin-Brandenburg Graduate School in Distributed Information Systems
5    * (DFG grant no. GRK 316).
6    *
7    * This program is free software; you can redistribute it and/or modify
8    * it under the terms of the GNU General Public License as published by
9    * the Free Software Foundation; either version 2 of the License, or
10   * (at your option) any later version.
11   *
12   * This program is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   * GNU General Public License for more details.
16   *
17   * You should have received a copy of the GNU General Public License
18   * along with this program; if not, visit
19   * http://www.gnu.org/licenses/gpl.html or write to the Free Software
20   * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
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         // recalculate threshold to work around issue in superclass
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         // delegate to superclass
169         final Object removedValue = super.remove(key);
170 
171         // invoke callback, if given
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             // collect candidates for the pruner
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                 //Util.LOG.debug("Calling entryIter.next");
198                 candidates[i] = (Map.Entry) entryIter.next();
199                 //Util.LOG.debug("Called entryIter.next");
200             }
201 
202             // let the pruner decide + delete the chosen entry
203             final Map.Entry[] resortedEntries =
204                 pruner.sortForPruning(candidates);
205 
206             // remove specified number of entries
207             final int entriesToPrune =
208                 Math.min(pruneNumber, resortedEntries.length);
209 
210             for (int i = 0; i < entriesToPrune; i++) {
211                 // delegate to remove method -- will also invoke removeCallback
212                 remove(resortedEntries[i].getKey());
213             }
214 
215             // deleted chosen entries, no need for further action
216             return false;
217         } else {
218             // standard LRU behavior: let superclass remove entry
219             // + invoke callback, if given
220             if (removeCallback != null) {
221                 removeCallback.removed(entry.getKey());
222             }
223             return true;
224         }
225     }
226 
227 }