File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\util\CacheLRU.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.util;
8
9 import java.util.ArrayList;
10 import java.util.Collections;
11 import java.util.Map;
12 import org.h2.constant.SysProperties;
13 import org.h2.engine.Constants;
14 import org.h2.message.DbException;
15
16 /**
17 * A cache implementation based on the last recently used (LRU) algorithm.
18 */
19 public class CacheLRU implements Cache {
20
21 static final String TYPE_NAME = "LRU";
22
23 private final CacheWriter writer;
24
25 /**
26 * Use First-In-First-Out (don't move recently used items to the front of
27 * the queue).
28 */
29 private final boolean fifo;
30
31 private final CacheObject head = new CacheHead();
32 private final int mask;
33 private CacheObject[] values;
34 private int recordCount;
35
36 /**
37 * The number of cache buckets.
38 */
39 private final int len;
40
41 /**
42 * The maximum memory, in words (4 bytes each).
43 */
44 private int maxMemory;
45
46 /**
47 * The current memory used in this cache, in words (4 bytes each).
48 */
49 private int memory;
50
51 CacheLRU(CacheWriter writer, int maxMemoryKb, boolean fifo) {
52 this.writer = writer;
53 this.fifo = fifo;
54 this.setMaxMemory(maxMemoryKb);
55 this.len = MathUtils.nextPowerOf2(maxMemory / 64);
56 this.mask = len - 1;
57 clear();
58 }
59
60 /**
61 * Create a cache of the given type and size.
62 *
63 * @param writer the cache writer
64 * @param cacheType the cache type
65 * @param cacheSize the size
66 * @return the cache object
67 */
68 public static Cache getCache(CacheWriter writer, String cacheType, int cacheSize) {
69 Map<Integer, CacheObject> secondLevel = null;
70 if (cacheType.startsWith("SOFT_")) {
71 secondLevel = new SoftHashMap<Integer, CacheObject>();
72 cacheType = cacheType.substring("SOFT_".length());
73 }
74 Cache cache;
75 if (CacheLRU.TYPE_NAME.equals(cacheType)) {
76 cache = new CacheLRU(writer, cacheSize, false);
77 } else if (CacheTQ.TYPE_NAME.equals(cacheType)) {
78 cache = new CacheTQ(writer, cacheSize);
79 } else {
80 throw DbException.getInvalidValueException("CACHE_TYPE", cacheType);
81 }
82 if (secondLevel != null) {
83 cache = new CacheSecondLevel(cache, secondLevel);
84 }
85 return cache;
86 }
87
88 public void clear() {
89 head.cacheNext = head.cachePrevious = head;
90 // first set to null - avoiding out of memory
91 values = null;
92 values = new CacheObject[len];
93 recordCount = 0;
94 memory = len * Constants.MEMORY_POINTER;
95 }
96
97 public void put(CacheObject rec) {
98 if (SysProperties.CHECK) {
99 int pos = rec.getPos();
100 CacheObject old = find(pos);
101 if (old != null) {
102 DbException.throwInternalError("try to add a record twice at pos " + pos);
103 }
104 }
105 int index = rec.getPos() & mask;
106 rec.cacheChained = values[index];
107 values[index] = rec;
108 recordCount++;
109 memory += rec.getMemory();
110 addToFront(rec);
111 removeOldIfRequired();
112 }
113
114 public CacheObject update(int pos, CacheObject rec) {
115 CacheObject old = find(pos);
116 if (old == null) {
117 put(rec);
118 } else {
119 if (SysProperties.CHECK) {
120 if (old != rec) {
121 DbException.throwInternalError("old!=record pos:" + pos + " old:" + old + " new:" + rec);
122 }
123 }
124 if (!fifo) {
125 removeFromLinkedList(rec);
126 addToFront(rec);
127 }
128 }
129 return old;
130 }
131
132 private void removeOldIfRequired() {
133 // a small method, to allow inlining
134 if (memory >= maxMemory) {
135 removeOld();
136 }
137 }
138
139 private void removeOld() {
140 int i = 0;
141 ArrayList<CacheObject> changed = New.arrayList();
142 int mem = memory;
143 int rc = recordCount;
144 boolean flushed = false;
145 CacheObject next = head.cacheNext;
146 while (true) {
147 if (rc <= Constants.CACHE_MIN_RECORDS) {
148 break;
149 }
150 if (changed.size() == 0) {
151 if (mem <= maxMemory) {
152 break;
153 }
154 } else {
155 if (mem * 4 <= maxMemory * 3) {
156 break;
157 }
158 }
159 CacheObject check = next;
160 next = check.cacheNext;
161 i++;
162 if (i >= recordCount) {
163 if (!flushed) {
164 writer.flushLog();
165 flushed = true;
166 i = 0;
167 } else {
168 // can't remove any record, because the records can not be removed
169 // hopefully this does not happen frequently, but it can happen
170 writer.getTrace().info("cannot remove records, cache size too small? records:" + recordCount + " memory:" + memory);
171 break;
172 }
173 }
174 if (SysProperties.CHECK && check == head) {
175 DbException.throwInternalError("try to remove head");
176 }
177 // we are not allowed to remove it if the log is not yet written
178 // (because we need to log before writing the data)
179 // also, can't write it if the record is pinned
180 if (!check.canRemove()) {
181 removeFromLinkedList(check);
182 addToFront(check);
183 continue;
184 }
185 rc--;
186 mem -= check.getMemory();
187 if (check.isChanged()) {
188 changed.add(check);
189 } else {
190 remove(check.getPos());
191 }
192 }
193 if (changed.size() > 0) {
194 if (!flushed) {
195 writer.flushLog();
196 }
197 Collections.sort(changed);
198 int max = maxMemory;
199 int size = changed.size();
200 try {
201 // temporary disable size checking,
202 // to avoid stack overflow
203 maxMemory = Integer.MAX_VALUE;
204 for (i = 0; i < size; i++) {
205 CacheObject rec = changed.get(i);
206 writer.writeBack(rec);
207 }
208 } finally {
209 maxMemory = max;
210 }
211 for (i = 0; i < size; i++) {
212 CacheObject rec = changed.get(i);
213 remove(rec.getPos());
214 if (SysProperties.CHECK) {
215 if (rec.cacheNext != null) {
216 throw DbException.throwInternalError();
217 }
218 }
219 }
220 }
221 }
222
223 private void addToFront(CacheObject rec) {
224 if (SysProperties.CHECK && rec == head) {
225 DbException.throwInternalError("try to move head");
226 }
227 rec.cacheNext = head;
228 rec.cachePrevious = head.cachePrevious;
229 rec.cachePrevious.cacheNext = rec;
230 head.cachePrevious = rec;
231 }
232
233 private void removeFromLinkedList(CacheObject rec) {
234 if (SysProperties.CHECK && rec == head) {
235 DbException.throwInternalError("try to remove head");
236 }
237 rec.cachePrevious.cacheNext = rec.cacheNext;
238 rec.cacheNext.cachePrevious = rec.cachePrevious;
239 // TODO cache: mystery: why is this required? needs more memory if we
240 // don't do this
241 rec.cacheNext = null;
242 rec.cachePrevious = null;
243 }
244
245 public boolean remove(int pos) {
246 int index = pos & mask;
247 CacheObject rec = values[index];
248 if (rec == null) {
249 return false;
250 }
251 if (rec.getPos() == pos) {
252 values[index] = rec.cacheChained;
253 } else {
254 CacheObject last;
255 do {
256 last = rec;
257 rec = rec.cacheChained;
258 if (rec == null) {
259 return false;
260 }
261 } while (rec.getPos() != pos);
262 last.cacheChained = rec.cacheChained;
263 }
264 recordCount--;
265 memory -= rec.getMemory();
266 removeFromLinkedList(rec);
267 if (SysProperties.CHECK) {
268 rec.cacheChained = null;
269 CacheObject o = find(pos);
270 if (o != null) {
271 DbException.throwInternalError("not removed: " + o);
272 }
273 }
274 return true;
275 }
276
277 public CacheObject find(int pos) {
278 CacheObject rec = values[pos & mask];
279 while (rec != null && rec.getPos() != pos) {
280 rec = rec.cacheChained;
281 }
282 return rec;
283 }
284
285 public CacheObject get(int pos) {
286 CacheObject rec = find(pos);
287 if (rec != null) {
288 if (!fifo) {
289 removeFromLinkedList(rec);
290 addToFront(rec);
291 }
292 }
293 return rec;
294 }
295
296 // private void testConsistency() {
297 // int s = size;
298 // HashSet set = new HashSet();
299 // for(int i=0; i<values.length; i++) {
300 // Record rec = values[i];
301 // if(rec == null) {
302 // continue;
303 // }
304 // set.add(rec);
305 // while(rec.chained != null) {
306 // rec = rec.chained;
307 // set.add(rec);
308 // }
309 // }
310 // Record rec = head.next;
311 // while(rec != head) {
312 // set.add(rec);
313 // rec = rec.next;
314 // }
315 // rec = head.previous;
316 // while(rec != head) {
317 // set.add(rec);
318 // rec = rec.previous;
319 // }
320 // if(set.size() != size) {
321 // System.out.println("size="+size+" but el.size="+set.size());
322 // }
323 // }
324
325 public ArrayList<CacheObject> getAllChanged() {
326 // if(Database.CHECK) {
327 // testConsistency();
328 // }
329 ArrayList<CacheObject> list = New.arrayList();
330 CacheObject rec = head.cacheNext;
331 while (rec != head) {
332 if (rec.isChanged()) {
333 list.add(rec);
334 }
335 rec = rec.cacheNext;
336 }
337 return list;
338 }
339
340 public void setMaxMemory(int maxKb) {
341 int newSize = MathUtils.convertLongToInt(maxKb * 1024L / 4);
342 maxMemory = newSize < 0 ? 0 : newSize;
343 // can not resize, otherwise existing records are lost
344 // resize(maxSize);
345 removeOldIfRequired();
346 }
347
348 public int getMaxMemory() {
349 return (int) (maxMemory * 4L / 1024);
350 }
351
352 public int getMemory() {
353 // CacheObject rec = head.cacheNext;
354 // while (rec != head) {
355 // System.out.println(rec.getMemory() + " " +
356 // MemoryFootprint.getObjectSize(rec) + " " + rec);
357 // rec = rec.cacheNext;
358 // }
359 return (int) (memory * 4L / 1024);
360 }
361
362 }
363