View Javadoc

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  
17  package net.sf.ehcache.store;
18  
19  import net.sf.ehcache.Element;
20  
21  import java.util.Random;
22  
23  /***
24   * A base policy class
25   *
26   * @author Greg Luck
27   */
28  public abstract class AbstractPolicy implements Policy {
29  
30      /***
31       * The sample size to use
32       */
33      static final int DEFAULT_SAMPLE_SIZE = 30;
34  
35      /***
36       * Used to select random numbers
37       */
38      static final Random RANDOM = new Random();
39  
40      /***
41       * sampleSize how many samples to take
42       *
43       * @param populationSize the size of the store
44       * @return the smaller of the map size and the default sample size of 30
45       */
46      public static int calculateSampleSize(int populationSize) {
47          if (populationSize < DEFAULT_SAMPLE_SIZE) {
48              return populationSize;
49          } else {
50              return DEFAULT_SAMPLE_SIZE;
51          }
52      }
53  
54      /***
55       * Finds the best eviction candidate based on the sampled elements. What distuingishes this approach
56       * from the classic data structures approach, is that an Element contains metadata which can be used
57       * for making policy decisions, while generic data structures do not.
58       *
59       * @param sampledElements this should be a random subset of the population
60       * @param justAdded       we never want to select the element just added. May be null.
61       * @return the least hit
62       */
63      public Element selectedBasedOnPolicy(Element[] sampledElements, Element justAdded) {
64          //edge condition when Memory Store configured to size 0
65          if (sampledElements.length == 1 && justAdded != null && (justAdded.isExpired() || !justAdded.isPinned())) {
66              return justAdded;
67          }
68          Element lowestElement = null;
69          for (Element element : sampledElements) {
70              if (element == null) {
71                  continue;
72              }
73              if (lowestElement == null) {
74                  if (!element.equals(justAdded)) {
75                      lowestElement = element;
76                  }
77              } else if (compare(lowestElement, element) && !element.equals(justAdded)) {
78                  lowestElement = element;
79              }
80  
81          }
82          return lowestElement;
83      }
84  
85      /***
86       * Generates a random sample from a population
87       *
88       * @param populationSize the size to draw from
89       * @return a list of random offsets
90       */
91      public static int[] generateRandomSample(int populationSize) {
92          int sampleSize = calculateSampleSize(populationSize);
93          int[] offsets = new int[sampleSize];
94  
95          //Guard against the possibility (which can happen) that the store has emptied, via another thread(s) and thus sampleSize is 0.
96          //Otherwise return an empty array.
97          if (sampleSize != 0) {
98              int maxOffset = 0;
99              maxOffset = populationSize / sampleSize;
100             for (int i = 0; i < sampleSize; i++) {
101                 offsets[i] = RANDOM.nextInt(maxOffset);
102             }
103         }
104         return offsets;
105     }
106 }