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 2Q algorithm.
016: * For about the algorithm, see
017: * http://www.vldb.org/conf/1994/P439.PDF .
018: * In this implementation, items are moved from 'in'
019: * queue and move to the 'main' queue if the are referenced again.
020: */
021: public class Cache2Q implements Cache {
022:
023: public static final String TYPE_NAME = "TQ";
024: private static final int MAIN = 1, IN = 2, OUT = 3;
025: private static final int PERCENT_IN = 20, PERCENT_OUT = 50;
026:
027: private final CacheWriter writer;
028: private int maxSize;
029: private int maxMain, maxIn, maxOut;
030: private CacheObject headMain = new CacheHead();
031: private CacheObject headIn = new CacheHead();
032: private CacheObject headOut = new CacheHead();
033: private int sizeMain, sizeIn, sizeOut;
034: private int recordCount;
035: private int len;
036: private CacheObject[] values;
037: private int mask;
038:
039: public Cache2Q(CacheWriter writer, int maxKb) {
040: int maxSize = maxKb * 1024 / 4;
041: this .writer = writer;
042: this .maxSize = maxSize;
043: this .len = MathUtils.nextPowerOf2(maxSize / 64);
044: this .mask = len - 1;
045: MathUtils.checkPowerOf2(len);
046: recalculateMax();
047: clear();
048: }
049:
050: public void clear() {
051: headMain.next = headMain.previous = headMain;
052: headIn.next = headIn.previous = headIn;
053: headOut.next = headOut.previous = headOut;
054: values = new CacheObject[len];
055: sizeIn = sizeOut = sizeMain = 0;
056: recordCount = 0;
057: }
058:
059: private void recalculateMax() {
060: maxMain = maxSize;
061: maxIn = maxSize * PERCENT_IN / 100;
062: maxOut = maxSize * PERCENT_OUT / 100;
063: }
064:
065: private void addToFront(CacheObject head, CacheObject rec) {
066: if (SysProperties.CHECK) {
067: if (rec == head) {
068: throw Message.getInternalError("try to move head");
069: }
070: if (rec.next != null || rec.previous != null) {
071: throw Message.getInternalError("already linked");
072: }
073: }
074: rec.next = head;
075: rec.previous = head.previous;
076: rec.previous.next = rec;
077: head.previous = rec;
078: }
079:
080: private void removeFromList(CacheObject rec) {
081: if (SysProperties.CHECK
082: && (rec instanceof CacheHead && rec.cacheQueue != OUT)) {
083: throw Message.getInternalError();
084: }
085: rec.previous.next = rec.next;
086: rec.next.previous = rec.previous;
087: // TODO cache: mystery: why is this required? needs more memory if we
088: // don't do this
089: rec.next = null;
090: rec.previous = null;
091: }
092:
093: public CacheObject get(int pos) {
094: CacheObject r = findCacheObject(pos);
095: if (r == null) {
096: return null;
097: }
098: if (r.cacheQueue == MAIN) {
099: removeFromList(r);
100: addToFront(headMain, r);
101: } else if (r.cacheQueue == OUT) {
102: return null;
103: } else if (r.cacheQueue == IN) {
104: removeFromList(r);
105: sizeIn -= r.getMemorySize();
106: sizeMain += r.getMemorySize();
107: r.cacheQueue = MAIN;
108: addToFront(headMain, r);
109: }
110: return r;
111: }
112:
113: private CacheObject findCacheObject(int pos) {
114: CacheObject rec = values[pos & mask];
115: while (rec != null && rec.getPos() != pos) {
116: rec = rec.chained;
117: }
118: return rec;
119: }
120:
121: private CacheObject removeCacheObject(int pos) {
122: int index = pos & mask;
123: CacheObject rec = values[index];
124: if (rec == null) {
125: return null;
126: }
127: if (rec.getPos() == pos) {
128: values[index] = rec.chained;
129: } else {
130: CacheObject last;
131: do {
132: last = rec;
133: rec = rec.chained;
134: if (rec == null) {
135: return null;
136: }
137: } while (rec.getPos() != pos);
138: last.chained = rec.chained;
139: }
140: recordCount--;
141: if (SysProperties.CHECK) {
142: rec.chained = null;
143: }
144: return rec;
145: }
146:
147: public void remove(int pos) {
148: CacheObject r = removeCacheObject(pos);
149: if (r != null) {
150: removeFromList(r);
151: if (r.cacheQueue == MAIN) {
152: sizeMain -= r.getMemorySize();
153: } else if (r.cacheQueue == IN) {
154: sizeIn -= r.getMemorySize();
155: }
156: }
157: }
158:
159: private void removeOldIfRequired() throws SQLException {
160: // a small method, to allow inlining
161: if ((sizeIn >= maxIn) || (sizeOut >= maxOut)
162: || (sizeMain >= maxMain)) {
163: removeOld();
164: }
165: }
166:
167: private void removeOld() throws SQLException {
168: int i = 0;
169: ObjectArray changed = new ObjectArray();
170: while (((sizeIn * 4 > maxIn * 3) || (sizeOut * 4 > maxOut * 3) || (sizeMain * 4 > maxMain * 3))
171: && recordCount > Constants.CACHE_MIN_RECORDS) {
172: i++;
173: if (i == recordCount) {
174: writer.flushLog();
175: }
176: if (i >= recordCount * 2) {
177: // can't remove any record, because the log is not written yet
178: // hopefully this does not happen too much, but it could happen
179: // theoretically
180: // TODO log this
181: break;
182: }
183: if (sizeIn > maxIn) {
184: CacheObject r = headIn.next;
185: if (!r.canRemove()) {
186: removeFromList(r);
187: addToFront(headIn, r);
188: continue;
189: }
190: sizeIn -= r.getMemorySize();
191: int pos = r.getPos();
192: removeCacheObject(pos);
193: removeFromList(r);
194: if (r.isChanged()) {
195: changed.add(r);
196: }
197: r = new CacheHead();
198: r.setPos(pos);
199: r.cacheQueue = OUT;
200: putCacheObject(r);
201: addToFront(headOut, r);
202: sizeOut++;
203: if (sizeOut >= maxOut) {
204: r = headOut.next;
205: sizeOut--;
206: removeCacheObject(r.getPos());
207: removeFromList(r);
208: }
209: } else if (sizeMain > 0) {
210: CacheObject r = headMain.next;
211: if (!r.canRemove() && !(r instanceof CacheHead)) {
212: removeFromList(r);
213: addToFront(headMain, r);
214: continue;
215: }
216: sizeMain -= r.getMemorySize();
217: removeCacheObject(r.getPos());
218: removeFromList(r);
219: if (r.isChanged()) {
220: changed.add(r);
221: }
222: }
223: }
224: if (changed.size() > 0) {
225: CacheObject.sort(changed);
226: for (i = 0; i < changed.size(); i++) {
227: CacheObject rec = (CacheObject) changed.get(i);
228: writer.writeBack(rec);
229: }
230: }
231: }
232:
233: public ObjectArray getAllChanged() {
234: ObjectArray list = new ObjectArray();
235: for (CacheObject o = headMain.next; o != headMain; o = o.next) {
236: if (o.isChanged()) {
237: list.add(o);
238: }
239: }
240: for (CacheObject o = headIn.next; o != headIn; o = o.next) {
241: if (o.isChanged()) {
242: list.add(o);
243: }
244: }
245: CacheObject.sort(list);
246: return list;
247: }
248:
249: public CacheObject find(int pos) {
250: CacheObject o = findCacheObject(pos);
251: if (o != null && o.cacheQueue != OUT) {
252: return o;
253: }
254: return null;
255: }
256:
257: private void putCacheObject(CacheObject rec) {
258: if (SysProperties.CHECK) {
259: for (int i = 0; i < rec.getBlockCount(); i++) {
260: CacheObject old = find(rec.getPos() + i);
261: if (old != null) {
262: throw Message
263: .getInternalError("try to add a record twice i="
264: + i);
265: }
266: }
267: }
268: int index = rec.getPos() & mask;
269: rec.chained = values[index];
270: values[index] = rec;
271: recordCount++;
272: }
273:
274: public void put(CacheObject rec) throws SQLException {
275: int pos = rec.getPos();
276: CacheObject r = findCacheObject(pos);
277: if (r != null) {
278: if (r.cacheQueue == OUT) {
279: removeCacheObject(pos);
280: removeFromList(r);
281: removeOldIfRequired();
282: rec.cacheQueue = MAIN;
283: putCacheObject(rec);
284: addToFront(headMain, rec);
285: sizeMain += rec.getMemorySize();
286: }
287: } else if (sizeMain < maxMain) {
288: removeOldIfRequired();
289: rec.cacheQueue = MAIN;
290: putCacheObject(rec);
291: addToFront(headMain, rec);
292: sizeMain += rec.getMemorySize();
293: } else {
294: removeOldIfRequired();
295: rec.cacheQueue = IN;
296: putCacheObject(rec);
297: addToFront(headIn, rec);
298: sizeIn += rec.getMemorySize();
299: }
300: }
301:
302: public CacheObject update(int pos, CacheObject rec)
303: throws SQLException {
304: CacheObject old = find(pos);
305: if (old == null || old.cacheQueue == OUT) {
306: put(rec);
307: } else {
308: if (old == rec) {
309: if (rec.cacheQueue == MAIN) {
310: removeFromList(rec);
311: addToFront(headMain, rec);
312: }
313: }
314: }
315: return old;
316: }
317:
318: public void setMaxSize(int maxKb) throws SQLException {
319: int newSize = maxKb * 1024 / 4;
320: maxSize = newSize < 0 ? 0 : newSize;
321: recalculateMax();
322: // can not resize, otherwise existing records are lost
323: // resize(maxSize);
324: removeOldIfRequired();
325: }
326:
327: public String getTypeName() {
328: return TYPE_NAME;
329: }
330:
331: }
|