001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.util;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.constant.SysProperties;
011: import org.h2.engine.Constants;
012: import org.h2.message.Message;
013:
014: /**
015: * A cache implementation based on the last recently used (LRU) algorithm.
016: */
017: public class CacheLRU implements Cache {
018:
019: public static final String TYPE_NAME = "LRU";
020:
021: private final CacheWriter writer;
022: private int len;
023: private int maxSize;
024: private CacheObject[] values;
025: private int mask;
026: private int recordCount;
027: private int sizeMemory;
028: private CacheObject head = new CacheHead();
029:
030: public CacheLRU(CacheWriter writer, int maxKb) {
031: int maxSize = maxKb * 1024 / 4;
032: this .writer = writer;
033: this .maxSize = maxSize;
034: this .len = MathUtils.nextPowerOf2(maxSize / 64);
035: this .mask = len - 1;
036: MathUtils.checkPowerOf2(len);
037: clear();
038: }
039:
040: public void clear() {
041: head.next = head.previous = head;
042: values = new CacheObject[len];
043: recordCount = 0;
044: sizeMemory = 0;
045: }
046:
047: public void put(CacheObject rec) throws SQLException {
048: if (SysProperties.CHECK) {
049: for (int i = 0; i < rec.getBlockCount(); i++) {
050: CacheObject old = find(rec.getPos() + i);
051: if (old != null) {
052: throw Message
053: .getInternalError("try to add a record twice i="
054: + i);
055: }
056: }
057: }
058: int index = rec.getPos() & mask;
059: rec.chained = values[index];
060: values[index] = rec;
061: recordCount++;
062: sizeMemory += rec.getMemorySize();
063: addToFront(rec);
064: removeOldIfRequired();
065: }
066:
067: public CacheObject update(int pos, CacheObject rec)
068: throws SQLException {
069: CacheObject old = find(pos);
070: if (old == null) {
071: put(rec);
072: } else {
073: if (SysProperties.CHECK) {
074: if (old != rec) {
075: throw Message.getInternalError("old != record old="
076: + old + " new=" + rec);
077: }
078: }
079: removeFromLinkedList(rec);
080: addToFront(rec);
081: }
082: return old;
083: }
084:
085: private void removeOldIfRequired() throws SQLException {
086: // a small method, to allow inlining
087: if (sizeMemory >= maxSize) {
088: removeOld();
089: }
090: }
091:
092: private void removeOld() throws SQLException {
093: int i = 0;
094: ObjectArray changed = new ObjectArray();
095: while (sizeMemory * 4 > maxSize * 3
096: && recordCount > Constants.CACHE_MIN_RECORDS) {
097: i++;
098: if (i == recordCount) {
099: writer.flushLog();
100: }
101: if (i >= recordCount * 2) {
102: // can't remove any record, because the log is not written yet
103: // hopefully this does not happen too much, but it could happen
104: // theoretically
105: // TODO log this
106: break;
107: }
108: CacheObject last = head.next;
109: if (SysProperties.CHECK && last == head) {
110: throw Message.getInternalError("try to remove head");
111: }
112: // we are not allowed to remove it if the log is not yet written
113: // (because we need to log before writing the data)
114: // also, can't write it if the record is pinned
115: if (!last.canRemove()) {
116: removeFromLinkedList(last);
117: addToFront(last);
118: continue;
119: }
120: remove(last.getPos());
121: if (last.isChanged()) {
122: changed.add(last);
123: }
124: }
125: if (changed.size() > 0) {
126: CacheObject.sort(changed);
127: for (i = 0; i < changed.size(); i++) {
128: CacheObject rec = (CacheObject) changed.get(i);
129: writer.writeBack(rec);
130: }
131: }
132: }
133:
134: private void addToFront(CacheObject rec) {
135: if (SysProperties.CHECK && rec == head) {
136: throw Message.getInternalError("try to move head");
137: }
138: rec.next = head;
139: rec.previous = head.previous;
140: rec.previous.next = rec;
141: head.previous = rec;
142: }
143:
144: private void removeFromLinkedList(CacheObject rec) {
145: if (SysProperties.CHECK && rec == head) {
146: throw Message.getInternalError("try to remove head");
147: }
148: rec.previous.next = rec.next;
149: rec.next.previous = rec.previous;
150: // TODO cache: mystery: why is this required? needs more memory if we
151: // don't do this
152: rec.next = null;
153: rec.previous = null;
154: }
155:
156: public void remove(int pos) {
157: int index = pos & mask;
158: CacheObject rec = values[index];
159: if (rec == null) {
160: return;
161: }
162: if (rec.getPos() == pos) {
163: values[index] = rec.chained;
164: } else {
165: CacheObject last;
166: do {
167: last = rec;
168: rec = rec.chained;
169: if (rec == null) {
170: return;
171: }
172: } while (rec.getPos() != pos);
173: last.chained = rec.chained;
174: }
175: recordCount--;
176: sizeMemory -= rec.getMemorySize();
177: removeFromLinkedList(rec);
178: if (SysProperties.CHECK) {
179: rec.chained = null;
180: if (find(pos) != null) {
181: throw Message.getInternalError("not removed!");
182: }
183: }
184: }
185:
186: public CacheObject find(int pos) {
187: CacheObject rec = values[pos & mask];
188: while (rec != null && rec.getPos() != pos) {
189: rec = rec.chained;
190: }
191: return rec;
192: }
193:
194: public CacheObject get(int pos) {
195: CacheObject rec = find(pos);
196: if (rec != null) {
197: removeFromLinkedList(rec);
198: addToFront(rec);
199: }
200: return rec;
201: }
202:
203: // private void testConsistency() {
204: // int s = size;
205: // HashSet set = new HashSet();
206: // for(int i=0; i<values.length; i++) {
207: // Record rec = values[i];
208: // if(rec == null) {
209: // continue;
210: // }
211: // set.add(rec);
212: // while(rec.chained != null) {
213: // rec = rec.chained;
214: // set.add(rec);
215: // }
216: // }
217: // Record rec = head.next;
218: // while(rec != head) {
219: // set.add(rec);
220: // rec = rec.next;
221: // }
222: // rec = head.previous;
223: // while(rec != head) {
224: // set.add(rec);
225: // rec = rec.previous;
226: // }
227: // if(set.size() != size) {
228: // System.out.println("size="+size+" but el.size="+set.size());
229: // }
230: // }
231:
232: public ObjectArray getAllChanged() {
233: // if(Database.CHECK) {
234: // testConsistency();
235: // }
236: // TODO cache: should probably use the LRU list
237: ObjectArray list = new ObjectArray();
238: for (int i = 0; i < len; i++) {
239: CacheObject rec = values[i];
240: while (rec != null) {
241: if (rec.isChanged()) {
242: list.add(rec);
243: if (list.size() >= recordCount) {
244: if (SysProperties.CHECK) {
245: if (list.size() > recordCount) {
246: throw Message
247: .getInternalError("cache chain error");
248: }
249: } else {
250: break;
251: }
252: }
253: }
254: rec = rec.chained;
255: }
256: }
257: return list;
258: }
259:
260: public void setMaxSize(int maxKb) throws SQLException {
261: int newSize = maxKb * 1024 / 4;
262: maxSize = newSize < 0 ? 0 : newSize;
263: // can not resize, otherwise existing records are lost
264: // resize(maxSize);
265: removeOldIfRequired();
266: }
267:
268: public String getTypeName() {
269: return TYPE_NAME;
270: }
271:
272: }
273:
274: // Unmaintained reference code (very old)
275: //import java.util.Iterator;
276: //import java.util.LinkedHashMap;
277: //import java.util.Map;
278: //
279: //public class Cache extends LinkedHashMap {
280: //
281: // final static int MAX_SIZE = 1 << 10;
282: // private CacheWriter writer;
283: //
284: // public Cache(CacheWriter writer) {
285: // super(16, (float) 0.75, true);
286: // this.writer = writer;
287: // }
288: //
289: // protected boolean removeEldestEntry(Map.Entry eldest) {
290: // if(size() <= MAX_SIZE) {
291: // return false;
292: // }
293: // Record entry = (Record) eldest.getValue();
294: // if(entry.getDeleted()) {
295: // return true;
296: // }
297: // if(entry.isChanged()) {
298: // try {
299: ////System.out.println("cache write "+entry.getPos());
300: // writer.writeBack(entry);
301: // } catch(SQLException e) {
302: // // TODO cache: printStackTrace not needed
303: // // if we use our own hashtable
304: // e.printStackTrace();
305: // }
306: // }
307: // return true;
308: // }
309: //
310: // public void put(Record rec) {
311: // put(new Integer(rec.getPos()), rec);
312: // }
313: //
314: // public Record get(int pos) {
315: // return (Record)get(new Integer(pos));
316: // }
317: //
318: // public void remove(int pos) {
319: // remove(new Integer(pos));
320: // }
321: //
322: // public ObjectArray getAllChanged() {
323: // Iterator it = values().iterator();
324: // ObjectArray list = new ObjectArray();
325: // while(it.hasNext()) {
326: // Record rec = (Record)it.next();
327: // if(rec.isChanged()) {
328: // list.add(rec);
329: // }
330: // }
331: // return list;
332: // }
333: //}
|