org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/trace/indexer/BTreeNode.java

   1 /*******************************************************************************
   2  * Copyright (c) 2013, 2014 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.tracecompass.internal.tmf.core.trace.indexer;
  14
  15 import java.io.IOException;
  16 import java.nio.ByteBuffer;
  17 import java.text.MessageFormat;
  18 import java.util.Arrays;
  19
  20 import org.eclipse.tracecompass.internal.tmf.core.Activator;
  21 import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp;
  22 import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimestamp;
  23 import org.eclipse.tracecompass.tmf.core.trace.indexer.checkpoint.ITmfCheckpoint;
  24 import org.eclipse.tracecompass.tmf.core.trace.indexer.checkpoint.TmfCheckpoint;
  25 import org.eclipse.tracecompass.tmf.core.trace.location.ITmfLocation;
  26
  27 /**
  28  * A node in the BTree. A node contains entries and pointers to other nodes.
  29  * The layout can be illustrated like this:
  30  *
  31  *               |
  32  *   ___________Node__________
  33  *   |  e  |  e  |  e  |  e  |
  34  *   p     p     p     p     p
  35  *   |
  36  *   |
  37  *  Node  ...
  38  *
  39  *  Where e is an entry, p is a pointer to another node.
  40  *
  41  *  A pointer on the left side of an entry points to a node containing entries
  42  *  that are of lesser value than the entry and a pointer on the right side of
  43  *  an entry points to a node containing entries that are of greater value
  44  *  than the entry. In this implementation, entries are ITmfCheckpoints and
  45  *  pointers are file offsets (long).
  46  *
  47  * @author Marc-Andre Laperle
  48  */
  49 class BTreeNode {
  50
  51     /**
  52      * Integer to represent a null child
  53      */
  54     static final int NULL_CHILD = -1;
  55
  56     private final ITmfCheckpoint fEntries[];
  57     private final long fChildrenFileOffsets[];
  58     private final long fFileOffset;
  59     private final BTree fTree;
  60
  61     private int fNumEntries = 0;
  62     private boolean fIsDirty = false;
  63
  64     /**
  65      * Construct a node for the specified tree for the specified file offset
  66      *
  67      * @param tree
  68      *            the BTree
  69      * @param offset
  70      *            the file offset
  71      */
  72     BTreeNode(BTree tree, long offset) {
  73         fTree = tree;
  74         fFileOffset = offset;
  75         fEntries = new ITmfCheckpoint[fTree.getMaxNumEntries()];
  76         fChildrenFileOffsets = new long[fTree.getMaxNumChildren()];
  77         Arrays.fill(fChildrenFileOffsets, NULL_CHILD);
  78     }
  79
  80     /**
  81      * Get the file offset for this node
  82      *
  83      * @return the file offset
  84      */
  85     long getOffset() {
  86         return fFileOffset;
  87     }
  88
  89     /**
  90      * Read the node data from disk
  91      */
  92     void serializeIn() {
  93         try {
  94             fTree.getRandomAccessFile().seek(fFileOffset);
  95
  96             ByteBuffer bb;
  97             bb = fTree.getNodeByteBuffer();
  98             bb.clear();
  99             fTree.getRandomAccessFile().read(bb.array());
 100
 101             for (int i = 0; i < fTree.getMaxNumChildren(); ++i) {
 102                 fChildrenFileOffsets[i] = bb.getLong();
 103             }
 104             fNumEntries = bb.getInt();
 105
 106             for (int i = 0; i < fNumEntries; ++i) {
 107
 108                 ITmfLocation location = fTree.getTrace().restoreLocation(bb);
 109                 ITmfTimestamp timeStamp = new TmfTimestamp(bb);
 110                 TmfCheckpoint c = new TmfCheckpoint(timeStamp, location, bb);
 111                 fEntries[i] = c;
 112             }
 113
 114         } catch (IOException e) {
 115             Activator.logError(MessageFormat.format(Messages.BTreeNode_IOErrorLoading, fFileOffset, fTree.getRandomAccessFile()), e);
 116         }
 117     }
 118
 119     /**
 120      * Write the node data to disk
 121      */
 122     void serializeOut() {
 123         try {
 124             fTree.getRandomAccessFile().seek(fFileOffset);
 125
 126             ByteBuffer bb = fTree.getNodeByteBuffer();
 127             bb.clear();
 128
 129             for (int i = 0; i < fTree.getMaxNumChildren(); ++i) {
 130                 bb.putLong(fChildrenFileOffsets[i]);
 131             }
 132             bb.putInt(fNumEntries);
 133
 134             for (int i = 0; i < fNumEntries; ++i) {
 135                 ITmfCheckpoint key = fEntries[i];
 136                 key.serialize(bb);
 137             }
 138
 139             fTree.getRandomAccessFile().write(bb.array());
 140
 141             fIsDirty = false;
 142         } catch (IOException e) {
 143             Activator.logError(MessageFormat.format(Messages.BTreeNode_IOErrorWriting, fFileOffset, fTree.getRandomAccessFile()), e);
 144         }
 145     }
 146
 147     /**
 148      * Get the entry at the given index
 149      *
 150      * @param index
 151      *            the index where to get the entry
 152      * @return the entry at the index
 153      */
 154     ITmfCheckpoint getEntry(int index) {
 155         return fEntries[index];
 156     }
 157
 158     long getChild(int index) {
 159         return fChildrenFileOffsets[index];
 160     }
 161
 162     /**
 163      * Set the checkpoint entry at the given index
 164      *
 165      * @param index
 166      *            the index where to set the entry
 167      * @param checkpoint
 168      *            the checkpoint to set at the index
 169      */
 170     void setEntry(int index, ITmfCheckpoint checkpoint) {
 171         fIsDirty = true;
 172         // Update number of entries
 173         if (fEntries[index] == null && checkpoint != null) {
 174             ++fNumEntries;
 175         } else if (fEntries[index] != null && checkpoint == null) {
 176             fNumEntries = Math.max(0, fNumEntries - 1);
 177         }
 178
 179         fEntries[index] = checkpoint;
 180     }
 181
 182     /**
 183      * Set the child file offset at the given index
 184      *
 185      * @param index
 186      *            the index where to set the child offset
 187      * @param offset
 188      *            the child offset
 189      */
 190     void setChild(int index, long offset) {
 191         fIsDirty = true;
 192         fChildrenFileOffsets[index] = offset;
 193     }
 194
 195     /**
 196      * Returns whether or not the node is dirty, that is, if the node has been
 197      * modified since it first has been loaded into memory
 198      *
 199      * @return true if the node is dirty, false otherwise
 200      */
 201     boolean isDirty() {
 202         return fIsDirty;
 203     }
 204 }