EMMA Coverage Report (generated Sun Mar 01 22:06:14 CET 2015)
[all classes][org.h2.util]

COVERAGE SUMMARY FOR SOURCE FILE [CacheLRU.java]

nameclass, %method, %block, %line, %
CacheLRU.java100% (1/1)88%  (14/16)72%  (458/635)78%  (129.3/165)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class CacheLRU100% (1/1)88%  (14/16)72%  (458/635)78%  (129.3/165)
getMaxMemory (): int 0%   (0/1)0%   (0/9)0%   (0/1)
getMemory (): int 0%   (0/1)0%   (0/9)0%   (0/1)
getCache (CacheWriter, String, int): Cache 100% (1/1)42%  (22/52)50%  (6/12)
update (int, CacheObject): CacheObject 100% (1/1)59%  (26/44)90%  (9/10)
removeOld (): void 100% (1/1)66%  (123/185)71%  (38.4/54)
remove (int): boolean 100% (1/1)67%  (54/81)67%  (14/21)
find (int): CacheObject 100% (1/1)80%  (16/20)75%  (3/4)
put (CacheObject): void 100% (1/1)82%  (47/57)92%  (12/13)
removeFromLinkedList (CacheObject): void 100% (1/1)88%  (23/26)86%  (6/7)
addToFront (CacheObject): void 100% (1/1)89%  (24/27)86%  (6/7)
setMaxMemory (int): void 100% (1/1)89%  (16/18)97%  (3.9/4)
CacheLRU (CacheWriter, int, boolean): void 100% (1/1)100% (32/32)100% (9/9)
clear (): void 100% (1/1)100% (27/27)100% (6/6)
get (int): CacheObject 100% (1/1)100% (17/17)100% (6/6)
getAllChanged (): ArrayList 100% (1/1)100% (23/23)100% (7/7)
removeOldIfRequired (): void 100% (1/1)100% (8/8)100% (3/3)

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

[all classes][org.h2.util]
EMMA 2.0.5312 (C) Vladimir Roubtsov