Commit | Line | Data |
---|---|---|
032ecd45 MAL |
1 | /******************************************************************************* |
2 | * Copyright (c) 2013 Ericsson | |
3 | * | |
4 | * All rights reserved. This program and the accompanying materials are | |
5 | * made available under the terms of the Eclipse Public License v1.0 which | |
6 | * accompanies this distribution, and is available at | |
7 | * http://www.eclipse.org/legal/epl-v10.html | |
8 | * | |
9 | * Contributors: | |
10 | * Marc-Andre Laperle - Initial API and implementation | |
11 | *******************************************************************************/ | |
12 | ||
13 | package org.eclipse.linuxtools.internal.tmf.core.trace.indexer; | |
14 | ||
15 | import java.util.ArrayDeque; | |
16 | import java.util.Deque; | |
17 | ||
18 | /** | |
19 | * A simple LRU node cache. The BTree request a node from the cache and the | |
20 | * cache load it from disk if it's not already in memory. | |
21 | * | |
22 | * This cache could be improved considerably by allowing bigger caches. | |
23 | * | |
24 | * @author Marc-Andre Laperle | |
25 | */ | |
26 | public class BTreeNodeCache { | |
27 | ||
28 | /** | |
29 | * Cache size obtained by experimentation. An improved cache could set this | |
30 | * dynamically or using a user preference. | |
31 | */ | |
32 | private static final int CACHE_SIZE = 15; | |
33 | ||
34 | private final BTree fTree; | |
35 | /** | |
36 | * The root node is always kept in memory when {@link | |
37 | * BTree#ALWAYS_CACHE_ROOT} is set to true | |
38 | */ | |
39 | private BTreeNode fRootNode = null; | |
40 | /** | |
41 | * The collection keeping the nodes in memory. The most recently used is | |
42 | * kept at the front of the double-ended queue and the least recently used | |
43 | * node is kept at the back. | |
44 | */ | |
45 | private final Deque<BTreeNode> fCachedNodes = new ArrayDeque<BTreeNode>(CACHE_SIZE); | |
46 | ||
47 | private int fCcheMisses = 0; | |
48 | ||
49 | /** | |
50 | * Construct a new node cache for the given BTree | |
51 | * | |
52 | * @param tree | |
53 | * the BTree that will use the cache | |
54 | */ | |
55 | BTreeNodeCache(BTree tree) { | |
56 | fTree = tree; | |
57 | } | |
58 | ||
59 | /** | |
60 | * Get the node at the offset from the cache. If the node is not found in | |
61 | * memory, it is loaded from disk. | |
62 | * | |
63 | * @param offset | |
64 | * @return | |
65 | */ | |
66 | BTreeNode getNode(long offset) { | |
67 | if (fRootNode != null && fRootNode.getOffset() == offset) { | |
68 | return fRootNode; | |
69 | } | |
70 | ||
71 | for (BTreeNode nodeSearch : fCachedNodes) { | |
72 | if (nodeSearch.getOffset() == offset) { | |
73 | // This node is now the most recently used | |
74 | fCachedNodes.remove(nodeSearch); | |
75 | fCachedNodes.push(nodeSearch); | |
76 | ||
77 | return nodeSearch; | |
78 | } | |
79 | } | |
80 | ||
81 | ++fCcheMisses; | |
82 | ||
83 | BTreeNode node = new BTreeNode(fTree, offset); | |
84 | node.serializeIn(); | |
85 | addNode(node); | |
86 | ||
87 | return node; | |
88 | } | |
89 | ||
90 | /** | |
91 | * Write all in-memory nodes to disk if they are dirty | |
92 | */ | |
93 | void serialize() { | |
94 | if (fRootNode != null && fRootNode.isDirty()) { | |
95 | fRootNode.serializeOut(); | |
96 | } | |
97 | for (BTreeNode nodeSearch : fCachedNodes) { | |
98 | if (nodeSearch.isDirty()) { | |
99 | nodeSearch.serializeOut(); | |
100 | } | |
101 | } | |
102 | } | |
103 | ||
104 | /** | |
105 | * Add a node to the cache. If the cache has reached the size specified with | |
106 | * {@link #CACHE_SIZE}, the least recently used node is removed from memory. | |
107 | * | |
108 | * @param node | |
109 | * the node to add to the cache | |
110 | */ | |
111 | void addNode(BTreeNode node) { | |
112 | if (fCachedNodes.size() >= CACHE_SIZE) { | |
113 | BTreeNode removed = fCachedNodes.removeLast(); | |
114 | if (removed.isDirty()) { | |
115 | removed.serializeOut(); | |
116 | } | |
117 | } | |
118 | fCachedNodes.push(node); | |
119 | } | |
120 | ||
121 | /** | |
122 | * Set the root node. See {@link #fRootNode} | |
123 | * | |
124 | * @param newRootNode | |
125 | * the new root node | |
126 | */ | |
127 | void setRootNode(BTreeNode newRootNode) { | |
128 | BTreeNode oldRootNode = fRootNode; | |
129 | fRootNode = newRootNode; | |
130 | if (oldRootNode != null) { | |
131 | addNode(oldRootNode); | |
132 | } | |
133 | return; | |
134 | } | |
135 | ||
136 | /** | |
137 | * Useful for benchmarks. Get the number of cache misses for the whole BTree | |
138 | * instance lifetime. Cache misses occur when a node is requested and it's | |
139 | * not in memory therefore it has to be read from disk. | |
140 | * | |
141 | * @return the number of cache misses. | |
142 | */ | |
143 | int getCacheMisses() { | |
144 | return fCcheMisses; | |
145 | } | |
146 | } |