org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/trace/indexer/BTreeNodeCache.java

   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<>(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 }