1 /*******************************************************************************
2 * Copyright (c) 2013, 2014 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
.tracecompass
.internal
.tmf
.core
.trace
.indexer
;
16 import java
.io
.IOException
;
17 import java
.io
.RandomAccessFile
;
18 import java
.nio
.ByteBuffer
;
19 import java
.text
.MessageFormat
;
21 import org
.eclipse
.tracecompass
.internal
.tmf
.core
.Activator
;
22 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.indexer
.ITmfPersistentlyIndexable
;
23 import org
.eclipse
.tracecompass
.tmf
.core
.trace
.indexer
.checkpoint
.ITmfCheckpoint
;
26 * A BTree made of BTreeNodes representing a series of ITmfCheckpoints ordered
27 * by time stamps. {@link BTreeNodeCache } is used to improve performance by
28 * caching some nodes in memory and the other nodes are kept on disk.
30 * @author Marc-Andre Laperle
32 public class BTree
extends AbstractFileCheckpointCollection
{
35 * Typical BTree file name
37 public static final String INDEX_FILE_NAME
= "checkpoint_btree.idx"; //$NON-NLS-1$
38 private static final int SUB_VERSION
= 4;
39 private static final boolean ALWAYS_CACHE_ROOT
= true;
41 private final int fMaxNumEntries
;
42 private final int fMaxNumChildren
;
43 private final int fMedianEntry
;
45 private BTreeHeader fBTreeHeader
;
48 private int nodeSize
= -1;
49 private final ByteBuffer fNodeByteBuffer
;
50 private final BTreeNodeCache fNodeCache
;
52 private class BTreeHeader
extends CheckpointCollectionFileHeader
{
53 private static final int SIZE
= LONG_SIZE
+ INT_SIZE
;
55 private final int fSubVersion
;
57 private BTreeHeader(int version
, int subVersion
) {
59 fSubVersion
= subVersion
;
62 private BTreeHeader(RandomAccessFile randomAccessFile
) throws IOException
{
63 super(randomAccessFile
);
65 fRoot
= randomAccessFile
.readLong();
66 fSubVersion
= randomAccessFile
.readInt();
70 public int getSubVersion() {
75 public int getSize() {
76 return SIZE
+ super.getSize();
80 public void serialize(RandomAccessFile randomAccessFile
) throws IOException
{
81 super.serialize(randomAccessFile
);
83 randomAccessFile
.writeLong(fRoot
);
84 randomAccessFile
.writeInt(fSubVersion
);
89 protected CheckpointCollectionFileHeader
createHeader() {
90 fBTreeHeader
= new BTreeHeader(getVersion(), SUB_VERSION
);
95 protected CheckpointCollectionFileHeader
createHeader(RandomAccessFile randomAccessFile
) throws IOException
{
96 fBTreeHeader
= new BTreeHeader(randomAccessFile
);
101 protected int getSubVersion() {
106 * Constructs a BTree for a given trace from scratch or from an existing
107 * file. The degree is used to calibrate the number of entries in each node
108 * which can affect performance. When the BTree is created from scratch, it
109 * is populated by subsequent calls to {@link #insert}.
112 * the degree to use in the tree
114 * the file to use as the persistent storage
118 public BTree(int degree
, File file
, ITmfPersistentlyIndexable trace
) {
121 fMaxNumEntries
= 2 * degree
- 1;
122 fMaxNumChildren
= 2 * degree
;
123 fMedianEntry
= degree
- 1;
125 fNodeByteBuffer
= ByteBuffer
.allocate(getNodeSize());
126 fNodeByteBuffer
.clear();
127 fNodeCache
= new BTreeNodeCache(this);
128 BTreeNode rootNode
= isCreatedFromScratch() ?
allocateNode() : fNodeCache
.getNode(fBTreeHeader
.fRoot
);
129 setRootNode(rootNode
);
133 * Insert a checkpoint into the file-backed BTree
136 * the checkpoint to insert
139 public void insert(ITmfCheckpoint checkpoint
) {
140 insert(checkpoint
, fBTreeHeader
.fRoot
, null, 0);
143 private void setRootNode(BTreeNode newRootNode
) {
144 fBTreeHeader
.fRoot
= newRootNode
.getOffset();
145 if (ALWAYS_CACHE_ROOT
) {
146 fNodeCache
.setRootNode(newRootNode
);
148 fNodeCache
.addNode(newRootNode
);
152 private void insert(ITmfCheckpoint checkpoint
, long nodeOffset
, BTreeNode pParent
, int iParent
) {
153 BTreeNode parent
= pParent
;
154 BTreeNode node
= fNodeCache
.getNode(nodeOffset
);
156 // If this node is full (last entry isn't null), split it
157 if (node
.getEntry(fMaxNumEntries
- 1) != null) {
159 ITmfCheckpoint median
= node
.getEntry(fMedianEntry
);
160 if (median
.compareTo(checkpoint
) == 0) {
166 // Create the new node and move the larger entries over.
167 BTreeNode newnode
= allocateNode();
168 fNodeCache
.addNode(newnode
);
169 long newNodeOffset
= newnode
.getOffset();
170 for (int i
= 0; i
< fMedianEntry
; ++i
) {
171 newnode
.setEntry(i
, node
.getEntry(fMedianEntry
+ 1 + i
));
172 node
.setEntry(fMedianEntry
+ 1 + i
, null);
173 newnode
.setChild(i
, node
.getChild(fMedianEntry
+ 1 + i
));
174 node
.setChild(fMedianEntry
+ 1 + i
, BTreeNode
.NULL_CHILD
);
176 newnode
.setChild(fMedianEntry
, node
.getChild(fMaxNumEntries
));
177 node
.setChild(fMaxNumEntries
, BTreeNode
.NULL_CHILD
);
179 if (parent
== null) {
180 parent
= allocateNode();
182 parent
.setChild(0, nodeOffset
);
184 // Insert the median into the parent.
185 for (int i
= fMaxNumEntries
- 2; i
>= iParent
; --i
) {
186 ITmfCheckpoint r
= parent
.getEntry(i
);
188 parent
.setEntry(i
+ 1, r
);
189 parent
.setChild(i
+ 2, parent
.getChild(i
+ 1));
194 fNodeCache
.getNode(parent
.getOffset());
196 parent
.setEntry(iParent
, median
);
197 parent
.setChild(iParent
+ 1, newNodeOffset
);
199 node
.setEntry(fMedianEntry
, null);
201 // Set the node to the correct one to follow.
202 if (checkpoint
.compareTo(median
) > 0) {
207 // Binary search to find the insert point.
209 int upper
= fMaxNumEntries
- 1;
210 while (lower
< upper
&& node
.getEntry(upper
- 1) == null) {
214 while (lower
< upper
) {
215 int middle
= (lower
+ upper
) / 2;
216 ITmfCheckpoint check
= node
.getEntry(middle
);
220 int compare
= check
.compareTo(checkpoint
);
223 } else if (compare
< 0) {
226 // Found it, no insert
232 long child
= node
.getChild(i
);
233 if (child
!= BTreeNode
.NULL_CHILD
) {
234 // Visit the children.
235 insert(checkpoint
, child
, node
, i
);
237 // We are at the leaf, add us in.
238 // First copy everything after over one.
239 for (int j
= fMaxNumEntries
- 2; j
>= i
; --j
) {
240 ITmfCheckpoint r
= node
.getEntry(j
);
242 node
.setEntry(j
+ 1, r
);
245 node
.setEntry(i
, checkpoint
);
246 CheckpointCollectionFileHeader header
= getHeader();
253 if (nodeSize
== -1) {
254 nodeSize
= INT_SIZE
; // num entries
255 nodeSize
+= getTrace().getCheckpointSize() * fMaxNumEntries
;
256 nodeSize
+= LONG_SIZE
* fMaxNumChildren
;
262 private BTreeNode
allocateNode() {
264 long offset
= getRandomAccessFile().length();
265 getRandomAccessFile().setLength(offset
+ getNodeSize());
266 BTreeNode node
= new BTreeNode(this, offset
);
268 } catch (IOException e
) {
269 Activator
.logError(MessageFormat
.format(Messages
.BTree_IOErrorAllocatingNode
, getFile()), e
);
275 public long binarySearch(ITmfCheckpoint checkpoint
) {
276 BTreeCheckpointVisitor v
= new BTreeCheckpointVisitor(checkpoint
);
278 return v
.getCheckpointRank();
282 * Accept a visitor. This visitor is used to search through the whole tree.
285 * the visitor to accept
287 public void accept(IBTreeVisitor treeVisitor
) {
288 accept(fBTreeHeader
.fRoot
, treeVisitor
);
291 private void accept(long nodeOffset
, IBTreeVisitor visitor
) {
293 if (nodeOffset
== BTreeNode
.NULL_CHILD
) {
297 BTreeNode node
= fNodeCache
.getNode(nodeOffset
);
299 // Binary search to find first entry greater or equal.
301 int upper
= fMaxNumEntries
- 1;
302 while (lower
< upper
&& node
.getEntry(upper
- 1) == null) {
305 while (lower
< upper
) {
306 int middle
= (lower
+ upper
) / 2;
307 ITmfCheckpoint middleCheckpoint
= node
.getEntry(middle
);
308 if (middleCheckpoint
== null) {
311 int compare
= visitor
.compare(middleCheckpoint
);
314 } else if (compare
> 0) {
322 // Start with first record greater or equal, reuse comparison
325 for (; i
< fMaxNumEntries
; ++i
) {
326 ITmfCheckpoint record
= node
.getEntry(i
);
327 if (record
== null) {
331 int compare
= visitor
.compare(record
);
333 // Start point is to the left.
334 accept(node
.getChild(i
), visitor
);
336 } else if (compare
== 0) {
340 accept(node
.getChild(i
), visitor
);
345 * Get the maximum number of entries in a node
347 * @return the maximum number of entries in a node
349 int getMaxNumEntries() {
350 return fMaxNumEntries
;
354 * Get the maximum number of children in a node
356 * @return the maximum number of children in a node
358 int getMaxNumChildren() {
359 return fMaxNumChildren
;
362 ByteBuffer
getNodeByteBuffer() {
363 return fNodeByteBuffer
;
367 public void dispose() {
368 if (fNodeCache
!= null && getRandomAccessFile() != null) {
369 fNodeCache
.serialize();