KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > h2 > util > Cache2Q


1 /*
2  * Copyright 2004-2006 H2 Group. Licensed under the H2 License, Version 1.0 (http://h2database.com/html/license.html).
3  * Initial Developer: H2 Group
4  */

5 package org.h2.util;
6
7 import java.sql.SQLException JavaDoc;
8
9 import org.h2.engine.Constants;
10 import org.h2.message.Message;
11
12 /**
13  * For details about the 2Q algorithm, see http://www.vldb.org/conf/1994/P439.PDF.
14  * However, items are moved from 'in' queue and move to the 'main' queue if the are referenced again.
15  */

16 public class Cache2Q implements Cache {
17     
18     public static final String JavaDoc TYPE_NAME = "TQ";
19     
20     private static final int MAIN = 1, IN = 2, OUT = 3;
21     private int maxSize;
22     private CacheWriter writer;
23     private int percentIn = 20, percentOut = 50;
24     private int maxMain, maxIn, maxOut;
25     private CacheObject headMain = new CacheHead();
26     private CacheObject headIn = new CacheHead();
27     private CacheObject headOut = new CacheHead();
28     private int sizeMain, sizeIn, sizeOut, sizeRecords;
29     private int len;
30     private CacheObject[] values;
31     private int mask;
32     
33     public Cache2Q(CacheWriter writer, int maxSize) {
34         this.writer = writer;
35         this.maxSize = maxSize;
36         this.len = maxSize / 2;
37         MathUtils.checkPowerOf2(len);
38         this.mask = len - 1;
39         clear();
40     }
41     
42     public void clear() {
43         headMain.next = headMain.previous = headMain;
44         headIn.next = headIn.previous = headIn;
45         headOut.next = headOut.previous = headOut;
46         values = new CacheObject[len];
47         sizeIn = sizeOut = sizeMain = 0;
48         sizeRecords = 0;
49         recalcMax();
50     }
51     
52     void setPercentIn(int percent) {
53         percentIn = percent;
54         recalcMax();
55     }
56
57     void setPercentOut(int percent) {
58         percentOut = percent;
59         recalcMax();
60     }
61
62     private void recalcMax() {
63         maxMain = maxSize;
64         maxIn = maxSize * percentIn / 100;
65         maxOut = maxSize * percentOut / 100;
66     }
67     
68     private void addToFront(CacheObject head, CacheObject rec) {
69         if(Constants.CHECK) {
70             if(rec == head) {
71                 throw Message.getInternalError("try to move head");
72             }
73             if(rec.next != null || rec.previous != null) {
74                 throw Message.getInternalError("already linked");
75             }
76         }
77         rec.next = head;
78         rec.previous = head.previous;
79         rec.previous.next = rec;
80         head.previous = rec;
81     }
82     
83     private void removeFromList(CacheObject rec) {
84         if(Constants.CHECK && (rec instanceof CacheHead && rec.cacheQueue != OUT)) {
85             throw Message.getInternalError();
86         }
87         rec.previous.next = rec.next;
88         rec.next.previous = rec.previous;
89         // TODO cache: mystery: why is this required? needs more memory if we don't do this
90
rec.next = null;
91         rec.previous = null;
92     }
93
94     public CacheObject get(int pos) {
95         CacheObject r = findCacheObject(pos);
96         if(r==null) {
97             return null;
98         }
99         if(r.cacheQueue == MAIN) {
100             removeFromList(r);
101             addToFront(headMain, r);
102         } else if(r.cacheQueue == OUT) {
103             return null;
104         } else if(r.cacheQueue == IN) {
105             removeFromList(r);
106             sizeIn -= r.getBlockCount();
107             sizeMain += r.getBlockCount();
108             r.cacheQueue = MAIN;
109             addToFront(headMain, r);
110         }
111         return r;
112     }
113
114     private CacheObject findCacheObject(int pos) {
115         CacheObject rec = values[pos & mask];
116         while(rec != null && rec.getPos() != pos) {
117             rec = rec.chained;
118         }
119         return rec;
120     }
121     
122     private CacheObject removeCacheObject(int pos) {
123         int index = pos & mask;
124         CacheObject rec = values[index];
125         if(rec == null) {
126             return null;
127         }
128         if(rec.getPos() == pos) {
129             values[index] = rec.chained;
130         } else {
131             CacheObject last;
132             do {
133                 last = rec;
134                 rec = rec.chained;
135                 if(rec == null) {
136                     return null;
137                 }
138             } while(rec.getPos() != pos);
139             last.chained = rec.chained;
140         }
141         sizeRecords--;
142         if(Constants.CHECK) {
143             rec.chained = null;
144         }
145         return rec;
146     }
147
148     public void remove(int pos) {
149         CacheObject r = removeCacheObject(pos);
150         if(r != null) {
151             removeFromList(r);
152             if(r.cacheQueue == MAIN) {
153                 sizeMain -= r.getBlockCount();
154             } else if(r.cacheQueue == IN) {
155                 sizeIn -= r.getBlockCount();
156             }
157         }
158     }
159
160     private void removeOld() throws SQLException JavaDoc {
161         if((sizeIn < maxIn) && (sizeOut < maxOut) && (sizeMain < maxMain)) {
162             return;
163         }
164         int i=0;
165         ObjectArray changed = new ObjectArray();
166         while (((sizeIn*4 > maxIn*3) || (sizeOut*4 > maxOut*3) || (sizeMain*4 > maxMain*3)) && sizeRecords > Constants.CACHE_MIN_RECORDS) {
167             if(i++ >= sizeRecords) {
168                 // can't remove any record, because the log is not written yet
169
// hopefully this does not happen too much, but it could happen theoretically
170
// TODO log this
171
break;
172             }
173             if (sizeIn > maxIn) {
174                 CacheObject r = headIn.next;
175                 if(!r.canRemove()) {
176                     removeFromList(r);
177                     addToFront(headIn, r);
178                     continue;
179                 }
180                 sizeIn -= r.getBlockCount();
181                 int pos = r.getPos();
182                 removeCacheObject(pos);
183                 removeFromList(r);
184                 if(r.isChanged()) {
185                     changed.add(r);
186                 }
187                 r = new CacheHead();
188                 r.setPos(pos);
189                 r.cacheQueue = OUT;
190                 putCacheObject(r);
191                 addToFront(headOut, r);
192                 sizeOut++;
193                 if (sizeOut >= maxOut) {
194                     r = headOut.next;
195                     sizeOut--;
196                     removeCacheObject(r.getPos());
197                     removeFromList(r);
198                 }
199             } else {
200                 CacheObject r = headMain.next;
201                 if(!r.canRemove()) {
202                     removeFromList(r);
203                     addToFront(headMain, r);
204                     continue;
205                 }
206                 sizeMain -= r.getBlockCount();
207                 removeCacheObject(r.getPos());
208                 removeFromList(r);
209                 if(r.isChanged()) {
210                     changed.add(r);
211                 }
212             }
213         }
214         if(changed.size() > 0) {
215             CacheObject.sort(changed);
216             for(i=0; i<changed.size(); i++) {
217                 CacheObject rec = (CacheObject) changed.get(i);
218                 writer.writeBack(rec);
219             }
220         }
221     }
222
223     public ObjectArray getAllChanged() {
224         ObjectArray list = new ObjectArray();
225         for(CacheObject o = headMain.next; o != headMain; o = o.next) {
226             if(o.isChanged()) {
227                 list.add(o);
228             }
229         }
230         for(CacheObject o = headIn.next; o != headIn; o = o.next) {
231             if(o.isChanged()) {
232                 list.add(o);
233             }
234         }
235         CacheObject.sort(list);
236         return list;
237     }
238
239     public CacheObject find(int pos) {
240         CacheObject o = findCacheObject(pos);
241         if(o != null && o.cacheQueue != OUT) {
242             return o;
243         }
244         return null;
245     }
246     
247     private void putCacheObject(CacheObject rec) {
248         if(Constants.CHECK) {
249             for(int i=0; i<rec.getBlockCount(); i++) {
250                 CacheObject old = find(rec.getPos() + i);
251                 if(old != null) {
252                     throw Message.getInternalError("try to add a record twice i="+i);
253                 }
254             }
255         }
256         int index = rec.getPos() & mask;
257         rec.chained = values[index];
258         values[index] = rec;
259         sizeRecords++;
260     }
261     
262
263     public void put(CacheObject rec) throws SQLException JavaDoc {
264         int pos = rec.getPos();
265         CacheObject r = findCacheObject(pos);
266         if(r != null) {
267             if(r.cacheQueue == OUT) {
268                 removeCacheObject(pos);
269                 removeFromList(r);
270                 removeOld();
271                 rec.cacheQueue = MAIN;
272                 putCacheObject(rec);
273                 addToFront(headMain, rec);
274                 sizeMain += rec.getBlockCount();
275             }
276         } else if(sizeMain < maxMain) {
277             removeOld();
278             rec.cacheQueue = MAIN;
279             putCacheObject(rec);
280             addToFront(headMain, rec);
281             sizeMain += rec.getBlockCount();
282         } else {
283             removeOld();
284             rec.cacheQueue = IN;
285             putCacheObject(rec);
286             addToFront(headIn, rec);
287             sizeIn += rec.getBlockCount();
288         }
289     }
290
291     public CacheObject update(int pos, CacheObject rec) throws SQLException JavaDoc {
292         CacheObject old = find(pos);
293         if(old == null || old.cacheQueue == OUT) {
294             put(rec);
295         } else {
296             if(old == rec) {
297                 if(rec.cacheQueue == MAIN) {
298                     removeFromList(rec);
299                     addToFront(headMain, rec);
300                 }
301             }
302         }
303         return old;
304     }
305     
306     public void setMaxSize(int newSize) throws SQLException JavaDoc {
307         maxSize = newSize < 0 ? 0 : newSize;
308         recalcMax();
309         removeOld();
310     }
311     
312     public String JavaDoc getTypeName() {
313         return TYPE_NAME;
314     }
315
316 }
317
Popular Tags