statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/classic/CoreNode.java

   1 /*******************************************************************************
   2  * Copyright (c) 2010, 2016 Ericsson, École Polytechnique de Montréal, and others
   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  *   Alexandre Montplaisir - Initial API and implementation
  11  *   Florian Wininger - Add Extension and Leaf Node
  12  *******************************************************************************/
  13
  14 package org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.classic;
  15
  16 import java.nio.ByteBuffer;
  17 import java.util.Arrays;
  18 import java.util.Collection;
  19 import java.util.Collections;
  20 import java.util.concurrent.locks.ReentrantReadWriteLock;
  21
  22 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTConfig;
  23 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.HTNode;
  24 import org.eclipse.tracecompass.internal.statesystem.core.backend.historytree.ParentNode;
  25 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  26
  27 /**
  28  * A Core node is a first-level node of a History Tree which is not a leaf node.
  29  *
  30  * It extends HTNode by adding support for child nodes, and also extensions.
  31  *
  32  * @author Alexandre Montplaisir
  33  */
  34 public final class CoreNode extends ParentNode {
  35
  36     /** Nb. of children this node has */
  37     private int nbChildren;
  38
  39     /** Seq. numbers of the children nodes (size = MAX_NB_CHILDREN) */
  40     private int[] children;
  41
  42     /** Start times of each of the children (size = MAX_NB_CHILDREN) */
  43     private long[] childStart;
  44
  45     /** Seq number of this node's extension. -1 if none */
  46     private volatile int extension = -1;
  47
  48     /**
  49      * Lock used to gate the accesses to the children arrays. Meant to be a
  50      * different lock from the one in {@link HTNode}.
  51      */
  52     private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(false);
  53
  54     /**
  55      * Initial constructor. Use this to initialize a new EMPTY node.
  56      *
  57      * @param config
  58      *            Configuration of the History Tree
  59      * @param seqNumber
  60      *            The (unique) sequence number assigned to this particular node
  61      * @param parentSeqNumber
  62      *            The sequence number of this node's parent node
  63      * @param start
  64      *            The earliest timestamp stored in this node
  65      */
  66     public CoreNode(HTConfig config, int seqNumber, int parentSeqNumber,
  67             long start) {
  68         super(config, seqNumber, parentSeqNumber, start);
  69         this.nbChildren = 0;
  70         int size = config.getMaxChildren();
  71
  72         /*
  73          * We instantiate the two following arrays at full size right away,
  74          * since we want to reserve that space in the node's header.
  75          * "this.nbChildren" will tell us how many relevant entries there are in
  76          * those tables.
  77          */
  78         this.children = new int[size];
  79         this.childStart = new long[size];
  80     }
  81
  82     @Override
  83     protected void readSpecificHeader(ByteBuffer buffer) {
  84         int size = getConfig().getMaxChildren();
  85
  86         extension = buffer.getInt();
  87         nbChildren = buffer.getInt();
  88
  89         children = new int[size];
  90         for (int i = 0; i < nbChildren; i++) {
  91             children[i] = buffer.getInt();
  92         }
  93         for (int i = nbChildren; i < size; i++) {
  94             buffer.getInt();
  95         }
  96
  97         this.childStart = new long[size];
  98         for (int i = 0; i < nbChildren; i++) {
  99             childStart[i] = buffer.getLong();
 100         }
 101         for (int i = nbChildren; i < size; i++) {
 102             buffer.getLong();
 103         }
 104     }
 105
 106     @Override
 107     protected void writeSpecificHeader(ByteBuffer buffer) {
 108         int size = getConfig().getMaxChildren();
 109
 110         buffer.putInt(extension);
 111         buffer.putInt(nbChildren);
 112
 113         /* Write the "children's seq number" array */
 114         for (int i = 0; i < nbChildren; i++) {
 115             buffer.putInt(children[i]);
 116         }
 117         for (int i = nbChildren; i < size; i++) {
 118             buffer.putInt(0);
 119         }
 120
 121         /* Write the "children's start times" array */
 122         for (int i = 0; i < nbChildren; i++) {
 123             buffer.putLong(childStart[i]);
 124         }
 125         for (int i = nbChildren; i < size; i++) {
 126             buffer.putLong(0);
 127         }
 128     }
 129
 130     @Override
 131     public int getNbChildren() {
 132         rwl.readLock().lock();
 133         try {
 134             return nbChildren;
 135         } finally {
 136             rwl.readLock().unlock();
 137         }
 138     }
 139
 140     @Override
 141     public int getChild(int index) {
 142         rwl.readLock().lock();
 143         try {
 144             return children[index];
 145         } finally {
 146             rwl.readLock().unlock();
 147         }
 148     }
 149
 150     @Override
 151     public int getLatestChild() {
 152         rwl.readLock().lock();
 153         try {
 154             return children[nbChildren - 1];
 155         } finally {
 156             rwl.readLock().unlock();
 157         }
 158     }
 159
 160     @Override
 161     public long getChildStart(int index) {
 162         rwl.readLock().lock();
 163         try {
 164             return childStart[index];
 165         } finally {
 166             rwl.readLock().unlock();
 167         }
 168     }
 169
 170     /**
 171      * Get the sequence number of the extension to this node (if there is one).
 172      *
 173      * @return The sequence number of the extended node. '-1' is returned if
 174      *         there is no extension node.
 175      */
 176     public int getExtensionSequenceNumber() {
 177         rwl.readLock().lock();
 178         try {
 179             return extension;
 180         } finally {
 181             rwl.readLock().unlock();
 182         }
 183     }
 184
 185     @Override
 186     public void linkNewChild(HTNode childNode) {
 187         rwl.writeLock().lock();
 188         try {
 189             if (nbChildren >= getConfig().getMaxChildren()) {
 190                 throw new IllegalStateException("Asked to link another child but parent already has maximum number of children"); //$NON-NLS-1$
 191             }
 192
 193             children[nbChildren] = childNode.getSequenceNumber();
 194             childStart[nbChildren] = childNode.getNodeStart();
 195             nbChildren++;
 196
 197         } finally {
 198             rwl.writeLock().unlock();
 199         }
 200     }
 201
 202     @Override
 203     public Collection<Integer> selectNextChildren(long t) throws TimeRangeException {
 204         if (t < getNodeStart() || (isOnDisk() && t > getNodeEnd())) {
 205             throw new TimeRangeException("Requesting children outside the node's range: " + t); //$NON-NLS-1$
 206         }
 207         rwl.readLock().lock();
 208         try {
 209             int potentialNextSeqNb = -1;
 210             for (int i = 0; i < nbChildren; i++) {
 211                 if (t >= childStart[i]) {
 212                     potentialNextSeqNb = children[i];
 213                 } else {
 214                     break;
 215                 }
 216             }
 217
 218             if (potentialNextSeqNb == -1) {
 219                 throw new IllegalStateException("No next child node found"); //$NON-NLS-1$
 220             }
 221             return Collections.singleton(potentialNextSeqNb);
 222         } finally {
 223             rwl.readLock().unlock();
 224         }
 225     }
 226
 227     @Override
 228     public NodeType getNodeType() {
 229         return NodeType.CORE;
 230     }
 231
 232     @Override
 233     protected int getSpecificHeaderSize() {
 234         int maxChildren = getConfig().getMaxChildren();
 235         int specificSize =
 236                   Integer.BYTES /* 1x int (extension node) */
 237                 + Integer.BYTES /* 1x int (nbChildren) */
 238
 239                 /* MAX_NB * int ('children' table) */
 240                 + Integer.BYTES * maxChildren
 241
 242                 /* MAX_NB * Timevalue ('childStart' table) */
 243                 + Long.BYTES * maxChildren;
 244
 245         return specificSize;
 246     }
 247
 248     @Override
 249     public String toStringSpecific() {
 250         /* Only used for debugging, shouldn't be externalized */
 251         return String.format("Core Node, %d children %s", //$NON-NLS-1$
 252                 nbChildren, Arrays.toString(Arrays.copyOf(children, nbChildren)));
 253     }
 254
 255 }