tmf/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 = true;
  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         if (offset < 0) {
  74             throw new IllegalStateException("Invalid node offset: " + offset); //$NON-NLS-1$
  75         }
  76         fTree = tree;
  77         fFileOffset = offset;
  78         fEntries = new ITmfCheckpoint[fTree.getMaxNumEntries()];
  79         fChildrenFileOffsets = new long[fTree.getMaxNumChildren()];
  80         Arrays.fill(fChildrenFileOffsets, NULL_CHILD);
  81     }
  82
  83     /**
  84      * Get the file offset for this node
  85      *
  86      * @return the file offset
  87      */
  88     long getOffset() {
  89         return fFileOffset;
  90     }
  91
  92     /**
  93      * Read the node data from disk
  94      */
  95     void serializeIn() {
  96         try {
  97             fTree.getRandomAccessFile().seek(fFileOffset);
  98
  99             ByteBuffer bb;
 100             bb = fTree.getNodeByteBuffer();
 101             bb.clear();
 102             fTree.getRandomAccessFile().read(bb.array());
 103
 104             for (int i = 0; i < fTree.getMaxNumChildren(); ++i) {
 105                 long offset = bb.getLong();
 106                 if (offset < 0 && offset != NULL_CHILD) {
 107                     throw new IllegalStateException("Invalid node offset: " + offset); //$NON-NLS-1$
 108                 }
 109                 fChildrenFileOffsets[i] = offset;
 110             }
 111             fNumEntries = bb.getInt();
 112
 113             for (int i = 0; i < fNumEntries; ++i) {
 114
 115                 ITmfLocation location = fTree.getTrace().restoreLocation(bb);
 116                 ITmfTimestamp timeStamp = new TmfTimestamp(bb);
 117                 TmfCheckpoint c = new TmfCheckpoint(timeStamp, location, bb);
 118                 fEntries[i] = c;
 119             }
 120             fIsDirty = false;
 121
 122         } catch (IOException e) {
 123             Activator.logError(MessageFormat.format(Messages.BTreeNode_IOErrorLoading, fFileOffset, fTree.getRandomAccessFile()), e);
 124         }
 125     }
 126
 127     /**
 128      * Write the node data to disk
 129      */
 130     void serializeOut() {
 131         try {
 132             fTree.getRandomAccessFile().seek(fFileOffset);
 133
 134             ByteBuffer bb = fTree.getNodeByteBuffer();
 135             bb.clear();
 136
 137             for (int i = 0; i < fTree.getMaxNumChildren(); ++i) {
 138                 bb.putLong(fChildrenFileOffsets[i]);
 139             }
 140             bb.putInt(fNumEntries);
 141
 142             for (int i = 0; i < fNumEntries; ++i) {
 143                 ITmfCheckpoint key = fEntries[i];
 144                 key.serialize(bb);
 145             }
 146
 147             fTree.getRandomAccessFile().write(bb.array());
 148
 149             fIsDirty = false;
 150         } catch (IOException e) {
 151             Activator.logError(MessageFormat.format(Messages.BTreeNode_IOErrorWriting, fFileOffset, fTree.getRandomAccessFile()), e);
 152         }
 153     }
 154
 155     /**
 156      * Get the entry at the given index
 157      *
 158      * @param index
 159      *            the index where to get the entry
 160      * @return the entry at the index
 161      */
 162     ITmfCheckpoint getEntry(int index) {
 163         return fEntries[index];
 164     }
 165
 166     long getChild(int index) {
 167         long childOffset = fChildrenFileOffsets[index];
 168         if (childOffset < 0 && childOffset != NULL_CHILD) {
 169             throw new IllegalStateException("Invalid node offset: " + childOffset); //$NON-NLS-1$
 170         }
 171         return childOffset;
 172     }
 173
 174     /**
 175      * Set the checkpoint entry at the given index
 176      *
 177      * @param index
 178      *            the index where to set the entry
 179      * @param checkpoint
 180      *            the checkpoint to set at the index
 181      */
 182     void setEntry(int index, ITmfCheckpoint checkpoint) {
 183         fIsDirty = true;
 184         // Update number of entries
 185         if (fEntries[index] == null && checkpoint != null) {
 186             ++fNumEntries;
 187         } else if (fEntries[index] != null && checkpoint == null) {
 188             fNumEntries = Math.max(0, fNumEntries - 1);
 189         }
 190
 191         fEntries[index] = checkpoint;
 192     }
 193
 194     /**
 195      * Set the child file offset at the given index
 196      *
 197      * @param index
 198      *            the index where to set the child offset
 199      * @param offset
 200      *            the child offset
 201      */
 202     void setChild(int index, long offset) {
 203         fIsDirty = true;
 204         fChildrenFileOffsets[index] = offset;
 205     }
 206
 207     /**
 208      * Returns whether or not the node is dirty, that is, if the node has been
 209      * modified since it first has been loaded into memory
 210      *
 211      * @return true if the node is dirty, false otherwise
 212      */
 213     boolean isDirty() {
 214         return fIsDirty;
 215     }
 216 }