1 /*******************************************************************************
2 * Copyright (c) 2013 Ericsson
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
10 * Marc-Andre Laperle - Initial API and implementation
11 *******************************************************************************/
13 package org
.eclipse
.linuxtools
.internal
.tmf
.core
.trace
.indexer
;
15 import java
.util
.ArrayDeque
;
16 import java
.util
.Deque
;
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.
22 * This cache could be improved considerably by allowing bigger caches.
24 * @author Marc-Andre Laperle
26 public class BTreeNodeCache
{
29 * Cache size obtained by experimentation. An improved cache could set this
30 * dynamically or using a user preference.
32 private static final int CACHE_SIZE
= 15;
34 private final BTree fTree
;
36 * The root node is always kept in memory when {@link
37 * BTree#ALWAYS_CACHE_ROOT} is set to true
39 private BTreeNode fRootNode
= null;
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.
45 private final Deque
<BTreeNode
> fCachedNodes
= new ArrayDeque
<>(CACHE_SIZE
);
47 private int fCcheMisses
= 0;
50 * Construct a new node cache for the given BTree
53 * the BTree that will use the cache
55 BTreeNodeCache(BTree tree
) {
60 * Get the node at the offset from the cache. If the node is not found in
61 * memory, it is loaded from disk.
66 BTreeNode
getNode(long offset
) {
67 if (fRootNode
!= null && fRootNode
.getOffset() == offset
) {
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
);
83 BTreeNode node
= new BTreeNode(fTree
, offset
);
91 * Write all in-memory nodes to disk if they are dirty
94 if (fRootNode
!= null && fRootNode
.isDirty()) {
95 fRootNode
.serializeOut();
97 for (BTreeNode nodeSearch
: fCachedNodes
) {
98 if (nodeSearch
.isDirty()) {
99 nodeSearch
.serializeOut();
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.
109 * the node to add to the cache
111 void addNode(BTreeNode node
) {
112 if (fCachedNodes
.size() >= CACHE_SIZE
) {
113 BTreeNode removed
= fCachedNodes
.removeLast();
114 if (removed
.isDirty()) {
115 removed
.serializeOut();
118 fCachedNodes
.push(node
);
122 * Set the root node. See {@link #fRootNode}
127 void setRootNode(BTreeNode newRootNode
) {
128 BTreeNode oldRootNode
= fRootNode
;
129 fRootNode
= newRootNode
;
130 if (oldRootNode
!= null) {
131 addNode(oldRootNode
);
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.
141 * @return the number of cache misses.
143 int getCacheMisses() {
This page took 0.034344 seconds and 5 git commands to generate.