Commit | Line | Data |
---|---|---|
032ecd45 | 1 | /******************************************************************************* |
7b3400bd | 2 | * Copyright (c) 2013, 2016 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); | |
0861e8e8 MAL |
246 | CheckpointCollectionFileHeader header = getHeader(); |
247 | ++header.fSize; | |
032ecd45 MAL |
248 | return; |
249 | } | |
250 | } | |
251 | ||
252 | int getNodeSize() { | |
253 | if (nodeSize == -1) { | |
254 | nodeSize = INT_SIZE; // num entries | |
255 | nodeSize += getTrace().getCheckpointSize() * fMaxNumEntries; | |
256 | nodeSize += LONG_SIZE * fMaxNumChildren; | |
257 | } | |
258 | ||
259 | return nodeSize; | |
260 | } | |
261 | ||
262 | private BTreeNode allocateNode() { | |
263 | try { | |
264 | long offset = getRandomAccessFile().length(); | |
265 | getRandomAccessFile().setLength(offset + getNodeSize()); | |
266 | BTreeNode node = new BTreeNode(this, offset); | |
267 | return node; | |
268 | } catch (IOException e) { | |
269 | Activator.logError(MessageFormat.format(Messages.BTree_IOErrorAllocatingNode, getFile()), e); | |
270 | } | |
271 | return null; | |
272 | } | |
273 | ||
274 | @Override | |
275 | public long binarySearch(ITmfCheckpoint checkpoint) { | |
276 | BTreeCheckpointVisitor v = new BTreeCheckpointVisitor(checkpoint); | |
277 | accept(v); | |
278 | return v.getCheckpointRank(); | |
279 | } | |
280 | ||
281 | /** | |
282 | * Accept a visitor. This visitor is used to search through the whole tree. | |
283 | * | |
284 | * @param treeVisitor | |
285 | * the visitor to accept | |
286 | */ | |
287 | public void accept(IBTreeVisitor treeVisitor) { | |
288 | accept(fBTreeHeader.fRoot, treeVisitor); | |
289 | } | |
290 | ||
291 | private void accept(long nodeOffset, IBTreeVisitor visitor) { | |
292 | ||
7b3400bd | 293 | if (nodeOffset == BTreeNode.NULL_CHILD || getRandomAccessFile() == null) { |
032ecd45 MAL |
294 | return; |
295 | } | |
296 | ||
297 | BTreeNode node = fNodeCache.getNode(nodeOffset); | |
298 | ||
299 | // Binary search to find first entry greater or equal. | |
300 | int lower = 0; | |
301 | int upper = fMaxNumEntries - 1; | |
302 | while (lower < upper && node.getEntry(upper - 1) == null) { | |
303 | upper--; | |
304 | } | |
305 | while (lower < upper) { | |
306 | int middle = (lower + upper) / 2; | |
307 | ITmfCheckpoint middleCheckpoint = node.getEntry(middle); | |
308 | if (middleCheckpoint == null) { | |
309 | upper = middle; | |
310 | } else { | |
311 | int compare = visitor.compare(middleCheckpoint); | |
312 | if (compare == 0) { | |
313 | return; | |
314 | } else if (compare > 0) { | |
315 | upper = middle; | |
316 | } else { | |
317 | lower = middle + 1; | |
318 | } | |
319 | } | |
320 | } | |
321 | ||
322 | // Start with first record greater or equal, reuse comparison | |
323 | // results. | |
324 | int i = lower; | |
325 | for (; i < fMaxNumEntries; ++i) { | |
326 | ITmfCheckpoint record = node.getEntry(i); | |
327 | if (record == null) { | |
328 | break; | |
329 | } | |
330 | ||
331 | int compare = visitor.compare(record); | |
332 | if (compare > 0) { | |
333 | // Start point is to the left. | |
334 | accept(node.getChild(i), visitor); | |
335 | return; | |
336 | } else if (compare == 0) { | |
337 | return; | |
338 | } | |
339 | } | |
340 | accept(node.getChild(i), visitor); | |
341 | return; | |
342 | } | |
343 | ||
032ecd45 MAL |
344 | /** |
345 | * Get the maximum number of entries in a node | |
346 | * | |
347 | * @return the maximum number of entries in a node | |
348 | */ | |
349 | int getMaxNumEntries() { | |
350 | return fMaxNumEntries; | |
351 | } | |
352 | ||
032ecd45 MAL |
353 | /** |
354 | * Get the maximum number of children in a node | |
355 | * | |
356 | * @return the maximum number of children in a node | |
357 | */ | |
358 | int getMaxNumChildren() { | |
359 | return fMaxNumChildren; | |
360 | } | |
361 | ||
362 | ByteBuffer getNodeByteBuffer() { | |
363 | return fNodeByteBuffer; | |
364 | } | |
0861e8e8 MAL |
365 | |
366 | @Override | |
367 | public void dispose() { | |
4f1ec6cc | 368 | if (fNodeCache != null && getRandomAccessFile() != null) { |
0861e8e8 MAL |
369 | fNodeCache.serialize(); |
370 | } | |
371 | ||
372 | super.dispose(); | |
373 | } | |
032ecd45 | 374 | } |