Commit | Line | Data |
---|---|---|
032ecd45 | 1 | /******************************************************************************* |
ed902a2b | 2 | * Copyright (c) 2013, 2014 Ericsson |
032ecd45 MAL |
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 | ||
2bdf0193 | 13 | package org.eclipse.tracecompass.internal.tmf.core.trace.indexer; |
032ecd45 MAL |
14 | |
15 | import java.io.File; | |
16 | import java.io.IOException; | |
17 | import java.io.RandomAccessFile; | |
18 | import java.nio.ByteBuffer; | |
19 | import java.text.MessageFormat; | |
20 | ||
2bdf0193 AM |
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; | |
032ecd45 MAL |
24 | |
25 | /** | |
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. | |
29 | * | |
30 | * @author Marc-Andre Laperle | |
31 | */ | |
32 | public class BTree extends AbstractFileCheckpointCollection { | |
33 | ||
34 | /** | |
35 | * Typical BTree file name | |
36 | */ | |
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; | |
40 | ||
41 | private final int fMaxNumEntries; | |
42 | private final int fMaxNumChildren; | |
43 | private final int fMedianEntry; | |
44 | ||
45 | private BTreeHeader fBTreeHeader; | |
46 | ||
47 | // Cached values | |
48 | private int nodeSize = -1; | |
49 | private final ByteBuffer fNodeByteBuffer; | |
50 | private final BTreeNodeCache fNodeCache; | |
51 | ||
52 | private class BTreeHeader extends CheckpointCollectionFileHeader { | |
53 | private static final int SIZE = LONG_SIZE + INT_SIZE; | |
54 | private long fRoot; | |
55 | private final int fSubVersion; | |
56 | ||
57 | private BTreeHeader(int version, int subVersion) { | |
58 | super(version); | |
59 | fSubVersion = subVersion; | |
60 | } | |
61 | ||
62 | private BTreeHeader(RandomAccessFile randomAccessFile) throws IOException { | |
63 | super(randomAccessFile); | |
64 | ||
65 | fRoot = randomAccessFile.readLong(); | |
66 | fSubVersion = randomAccessFile.readInt(); | |
67 | } | |
68 | ||
69 | @Override | |
70 | public int getSubVersion() { | |
71 | return fSubVersion; | |
72 | } | |
73 | ||
74 | @Override | |
75 | public int getSize() { | |
76 | return SIZE + super.getSize(); | |
77 | } | |
78 | ||
79 | @Override | |
80 | public void serialize(RandomAccessFile randomAccessFile) throws IOException { | |
81 | super.serialize(randomAccessFile); | |
82 | ||
83 | randomAccessFile.writeLong(fRoot); | |
84 | randomAccessFile.writeInt(fSubVersion); | |
85 | } | |
86 | } | |
87 | ||
88 | @Override | |
89 | protected CheckpointCollectionFileHeader createHeader() { | |
90 | fBTreeHeader = new BTreeHeader(getVersion(), SUB_VERSION); | |
91 | return fBTreeHeader; | |
92 | } | |
93 | ||
94 | @Override | |
95 | protected CheckpointCollectionFileHeader createHeader(RandomAccessFile randomAccessFile) throws IOException { | |
96 | fBTreeHeader = new BTreeHeader(randomAccessFile); | |
97 | return fBTreeHeader; | |
98 | } | |
99 | ||
100 | @Override | |
101 | protected int getSubVersion() { | |
102 | return SUB_VERSION; | |
103 | } | |
104 | ||
105 | /** | |
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}. | |
110 | * | |
111 | * @param degree | |
112 | * the degree to use in the tree | |
113 | * @param file | |
114 | * the file to use as the persistent storage | |
115 | * @param trace | |
116 | * the trace | |
117 | */ | |
118 | public BTree(int degree, File file, ITmfPersistentlyIndexable trace) { | |
119 | super(file, trace); | |
120 | ||
121 | fMaxNumEntries = 2 * degree - 1; | |
122 | fMaxNumChildren = 2 * degree; | |
123 | fMedianEntry = degree - 1; | |
124 | ||
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); | |
130 | } | |
131 | ||
132 | /** | |
133 | * Insert a checkpoint into the file-backed BTree | |
134 | * | |
135 | * @param checkpoint | |
136 | * the checkpoint to insert | |
137 | */ | |
138 | @Override | |
139 | public void insert(ITmfCheckpoint checkpoint) { | |
140 | insert(checkpoint, fBTreeHeader.fRoot, null, 0); | |
141 | } | |
142 | ||
143 | private void setRootNode(BTreeNode newRootNode) { | |
144 | fBTreeHeader.fRoot = newRootNode.getOffset(); | |
145 | if (ALWAYS_CACHE_ROOT) { | |
146 | fNodeCache.setRootNode(newRootNode); | |
147 | } else { | |
148 | fNodeCache.addNode(newRootNode); | |
149 | } | |
150 | } | |
151 | ||
152 | private void insert(ITmfCheckpoint checkpoint, long nodeOffset, BTreeNode pParent, int iParent) { | |
153 | BTreeNode parent = pParent; | |
154 | BTreeNode node = fNodeCache.getNode(nodeOffset); | |
155 | ||
156 | // If this node is full (last entry isn't null), split it | |
157 | if (node.getEntry(fMaxNumEntries - 1) != null) { | |
158 | ||
159 | ITmfCheckpoint median = node.getEntry(fMedianEntry); | |
160 | if (median.compareTo(checkpoint) == 0) { | |
161 | // Found it | |
162 | return; | |
163 | } | |
164 | ||
165 | // Split it. | |
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); | |
175 | } | |
176 | newnode.setChild(fMedianEntry, node.getChild(fMaxNumEntries)); | |
177 | node.setChild(fMaxNumEntries, BTreeNode.NULL_CHILD); | |
178 | ||
179 | if (parent == null) { | |
180 | parent = allocateNode(); | |
181 | setRootNode(parent); | |
182 | parent.setChild(0, nodeOffset); | |
183 | } else { | |
184 | // Insert the median into the parent. | |
185 | for (int i = fMaxNumEntries - 2; i >= iParent; --i) { | |
186 | ITmfCheckpoint r = parent.getEntry(i); | |
187 | if (r != null) { | |
188 | parent.setEntry(i + 1, r); | |
189 | parent.setChild(i + 2, parent.getChild(i + 1)); | |
190 | } | |
191 | } | |
192 | } | |
193 | ||
194 | fNodeCache.getNode(parent.getOffset()); | |
195 | ||
196 | parent.setEntry(iParent, median); | |
197 | parent.setChild(iParent + 1, newNodeOffset); | |
198 | ||
199 | node.setEntry(fMedianEntry, null); | |
200 | ||
201 | // Set the node to the correct one to follow. | |
202 | if (checkpoint.compareTo(median) > 0) { | |
203 | node = newnode; | |
204 | } | |
205 | } | |
206 | ||
207 | // Binary search to find the insert point. | |
208 | int lower = 0; | |
209 | int upper = fMaxNumEntries - 1; | |
210 | while (lower < upper && node.getEntry(upper - 1) == null) { | |
211 | upper--; | |
212 | } | |
213 | ||
214 | while (lower < upper) { | |
215 | int middle = (lower + upper) / 2; | |
216 | ITmfCheckpoint check = node.getEntry(middle); | |
217 | if (check == null) { | |
218 | upper = middle; | |
219 | } else { | |
220 | int compare = check.compareTo(checkpoint); | |
221 | if (compare > 0) { | |
222 | upper = middle; | |
223 | } else if (compare < 0) { | |
224 | lower = middle + 1; | |
225 | } else { | |
226 | // Found it, no insert | |
227 | return; | |
228 | } | |
229 | } | |
230 | } | |
231 | final int i = lower; | |
232 | long child = node.getChild(i); | |
233 | if (child != BTreeNode.NULL_CHILD) { | |
234 | // Visit the children. | |
235 | insert(checkpoint, child, node, i); | |
236 | } else { | |
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); | |
241 | if (r != null) { | |
242 | node.setEntry(j + 1, r); | |
243 | } | |
244 | } | |
245 | node.setEntry(i, checkpoint); | |
246 | return; | |
247 | } | |
248 | } | |
249 | ||
250 | int getNodeSize() { | |
251 | if (nodeSize == -1) { | |
252 | nodeSize = INT_SIZE; // num entries | |
253 | nodeSize += getTrace().getCheckpointSize() * fMaxNumEntries; | |
254 | nodeSize += LONG_SIZE * fMaxNumChildren; | |
255 | } | |
256 | ||
257 | return nodeSize; | |
258 | } | |
259 | ||
260 | private BTreeNode allocateNode() { | |
261 | try { | |
262 | long offset = getRandomAccessFile().length(); | |
263 | getRandomAccessFile().setLength(offset + getNodeSize()); | |
264 | BTreeNode node = new BTreeNode(this, offset); | |
265 | return node; | |
266 | } catch (IOException e) { | |
267 | Activator.logError(MessageFormat.format(Messages.BTree_IOErrorAllocatingNode, getFile()), e); | |
268 | } | |
269 | return null; | |
270 | } | |
271 | ||
272 | @Override | |
273 | public long binarySearch(ITmfCheckpoint checkpoint) { | |
274 | BTreeCheckpointVisitor v = new BTreeCheckpointVisitor(checkpoint); | |
275 | accept(v); | |
276 | return v.getCheckpointRank(); | |
277 | } | |
278 | ||
279 | /** | |
280 | * Accept a visitor. This visitor is used to search through the whole tree. | |
281 | * | |
282 | * @param treeVisitor | |
283 | * the visitor to accept | |
284 | */ | |
285 | public void accept(IBTreeVisitor treeVisitor) { | |
286 | accept(fBTreeHeader.fRoot, treeVisitor); | |
287 | } | |
288 | ||
289 | private void accept(long nodeOffset, IBTreeVisitor visitor) { | |
290 | ||
291 | if (nodeOffset == BTreeNode.NULL_CHILD) { | |
292 | return; | |
293 | } | |
294 | ||
295 | BTreeNode node = fNodeCache.getNode(nodeOffset); | |
296 | ||
297 | // Binary search to find first entry greater or equal. | |
298 | int lower = 0; | |
299 | int upper = fMaxNumEntries - 1; | |
300 | while (lower < upper && node.getEntry(upper - 1) == null) { | |
301 | upper--; | |
302 | } | |
303 | while (lower < upper) { | |
304 | int middle = (lower + upper) / 2; | |
305 | ITmfCheckpoint middleCheckpoint = node.getEntry(middle); | |
306 | if (middleCheckpoint == null) { | |
307 | upper = middle; | |
308 | } else { | |
309 | int compare = visitor.compare(middleCheckpoint); | |
310 | if (compare == 0) { | |
311 | return; | |
312 | } else if (compare > 0) { | |
313 | upper = middle; | |
314 | } else { | |
315 | lower = middle + 1; | |
316 | } | |
317 | } | |
318 | } | |
319 | ||
320 | // Start with first record greater or equal, reuse comparison | |
321 | // results. | |
322 | int i = lower; | |
323 | for (; i < fMaxNumEntries; ++i) { | |
324 | ITmfCheckpoint record = node.getEntry(i); | |
325 | if (record == null) { | |
326 | break; | |
327 | } | |
328 | ||
329 | int compare = visitor.compare(record); | |
330 | if (compare > 0) { | |
331 | // Start point is to the left. | |
332 | accept(node.getChild(i), visitor); | |
333 | return; | |
334 | } else if (compare == 0) { | |
335 | return; | |
336 | } | |
337 | } | |
338 | accept(node.getChild(i), visitor); | |
339 | return; | |
340 | } | |
341 | ||
342 | /** | |
343 | * Set the index as complete. No more checkpoints will be inserted. | |
344 | */ | |
345 | @Override | |
346 | public void setIndexComplete() { | |
347 | super.setIndexComplete(); | |
348 | ||
349 | fNodeCache.serialize(); | |
350 | } | |
351 | ||
352 | /** | |
353 | * Get the maximum number of entries in a node | |
354 | * | |
355 | * @return the maximum number of entries in a node | |
356 | */ | |
357 | int getMaxNumEntries() { | |
358 | return fMaxNumEntries; | |
359 | } | |
360 | ||
361 | /** | |
362 | * Set the size of the BTree, expressed as a number of checkpoints | |
363 | * | |
364 | * @param size | |
365 | * the size of the BTree | |
366 | */ | |
367 | public void setSize(int size) { | |
368 | fBTreeHeader.fSize = size; | |
369 | } | |
370 | ||
371 | /** | |
372 | * Get the maximum number of children in a node | |
373 | * | |
374 | * @return the maximum number of children in a node | |
375 | */ | |
376 | int getMaxNumChildren() { | |
377 | return fMaxNumChildren; | |
378 | } | |
379 | ||
380 | ByteBuffer getNodeByteBuffer() { | |
381 | return fNodeByteBuffer; | |
382 | } | |
383 | } |