1 /**
2 * Copyright 2003-2007 Greg Luck
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 java.util.Random;
20
21 /**
22 * Contains common LFU policy code for use between the LfuMemoryStore and the DiskStore, which also
23 * uses an LfuPolicy for evictions.
24 *
25 * @author Greg Luck
26 * @version $Id: LfuPolicy.java 512 2007-07-10 09:18:45Z gregluck $
27 */
28 public final class LfuPolicy {
29
30 private static final int DEFAULT_SAMPLE_SIZE = 30;
31
32 private static final Random RANDOM = new Random();
33
34 /**
35 * Utilitiy class therefore no constructor
36 */
37 private LfuPolicy() {
38 }
39
40 /**
41 * sampleSize how many samples to take
42 * @return the smaller of the map size and the default sample size of 30
43 */
44 private static int calculateSampleSize(int populationSize) {
45 if (populationSize < DEFAULT_SAMPLE_SIZE) {
46 return populationSize;
47 } else {
48 return DEFAULT_SAMPLE_SIZE;
49 }
50
51 }
52
53
54 /**
55 * Finds the least hit of the sampled elements provided
56 * @param sampledElements this should be a random subset of the population
57 * @param justAdded we never want to select the element just added. May be null.
58 * @return the least hit
59 */
60 public static LfuPolicy.Metadata leastHit(LfuPolicy.Metadata[] sampledElements, LfuPolicy.Metadata justAdded) {
61 //edge condition when Memory Store configured to size 0
62 if (sampledElements.length == 1) {
63 return justAdded;
64 }
65 LfuPolicy.Metadata lowestElement = null;
66 for (int i = 0; i < sampledElements.length; i++) {
67 LfuPolicy.Metadata element = sampledElements[i];
68 if (lowestElement == null) {
69 if (!element.equals(justAdded)) {
70 lowestElement = element;
71 }
72 } else {
73 if (element.getHitCount() < lowestElement.getHitCount() && !element.equals(justAdded)) {
74 lowestElement = element;
75 }
76 }
77 }
78 return lowestElement;
79 }
80
81 /**
82 * Generates a random sample from a population
83 * @param populationSize the size to draw from
84 */
85 public static int[] generateRandomSample(int populationSize) {
86 int sampleSize = LfuPolicy.calculateSampleSize(populationSize);
87 int[] offsets = new int[sampleSize];
88 int maxOffset = populationSize / sampleSize;
89 for (int i = 0; i < sampleSize; i++) {
90 offsets[i] = RANDOM.nextInt(maxOffset);
91 }
92 return offsets;
93 }
94
95
96 /**
97 * A type representing relevant metadata from an element, used by LfuPolicy for its operations.
98 */
99 public static interface Metadata {
100
101 /**
102 * @return the key of this object
103 */
104 Object getKey();
105
106 /**
107 *
108 * @return the hit count for the element
109 */
110 long getHitCount();
111
112 }
113 }