Commit | Line | Data |
---|---|---|
5e7913a4 GB |
1 | /******************************************************************************* |
2 | * Copyright (c) 2017 École Polytechnique de Montréal | |
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 | ||
10 | package org.eclipse.tracecompass.internal.provisional.datastore.core.historytree; | |
11 | ||
12 | import java.io.File; | |
13 | import java.io.FileInputStream; | |
14 | import java.io.FileOutputStream; | |
15 | import java.io.IOException; | |
16 | import java.nio.ByteBuffer; | |
17 | import java.nio.ByteOrder; | |
18 | import java.nio.channels.ClosedChannelException; | |
19 | import java.nio.channels.FileChannel; | |
20 | import java.util.ArrayList; | |
8b03451b | 21 | import java.util.Collection; |
5e7913a4 GB |
22 | import java.util.Collections; |
23 | import java.util.Deque; | |
24 | import java.util.LinkedList; | |
25 | import java.util.List; | |
26 | import java.util.concurrent.locks.ReentrantReadWriteLock; | |
27 | import java.util.function.Predicate; | |
28 | ||
29 | import org.eclipse.jdt.annotation.NonNull; | |
30 | import org.eclipse.tracecompass.common.core.NonNullUtils; | |
31 | import org.eclipse.tracecompass.internal.datastore.core.historytree.HtIo; | |
32 | import org.eclipse.tracecompass.internal.provisional.datastore.core.condition.RangeCondition; | |
33 | import org.eclipse.tracecompass.internal.provisional.datastore.core.exceptions.RangeException; | |
34 | import org.eclipse.tracecompass.internal.provisional.datastore.core.historytree.IHTNode.NodeType; | |
35 | import org.eclipse.tracecompass.internal.provisional.datastore.core.interval.IHTInterval; | |
36 | import org.eclipse.tracecompass.internal.provisional.datastore.core.interval.IHTIntervalReader; | |
37 | ||
38 | import com.google.common.annotations.VisibleForTesting; | |
39 | import com.google.common.collect.ImmutableList; | |
40 | import com.google.common.collect.Iterables; | |
41 | ||
42 | /** | |
43 | * Base class for history trees that encapsulates the logic to read from/write | |
44 | * to a file. | |
45 | * | |
46 | * @author Alexandre Montplaisir | |
47 | * @author Geneviève Bastien | |
48 | * @param <E> | |
49 | * The type of intervals that will be saved in the tree | |
50 | * @param <N> | |
51 | * The base type of the nodes of this tree | |
52 | */ | |
53 | public abstract class AbstractHistoryTree<E extends IHTInterval, N extends HTNode<E>> | |
54 | implements IHistoryTree<E> { | |
55 | ||
56 | /** | |
57 | * Interface for history to create the various HTNodes | |
58 | * | |
59 | * @param <E> | |
60 | * The type of intervals that will be saved in the node | |
61 | * @param <N> | |
62 | * The base type of the nodes of this tree | |
63 | */ | |
64 | @FunctionalInterface | |
65 | public interface IHTNodeFactory<E extends IHTInterval, N extends HTNode<E>> { | |
66 | ||
67 | /** | |
68 | * Creates a new node for the specific history tree | |
69 | * | |
70 | * @param type | |
71 | * The type of node to create. See {@link IHTNode.NodeType}. | |
72 | * @param blockSize | |
73 | * The size (in bytes) of each node once serialized to disk | |
74 | * @param maxChildren | |
75 | * The maximum number of amount a single core node can have | |
76 | * @param seqNumber | |
77 | * The (unique) sequence number assigned to this particular | |
78 | * node | |
79 | * @param parentSeqNumber | |
80 | * The sequence number of this node's parent node | |
81 | * @param start | |
82 | * The earliest timestamp stored in this node | |
83 | * @return The new core node | |
84 | */ | |
85 | N createNode(NodeType type, int blockSize, int maxChildren, | |
86 | int seqNumber, int parentSeqNumber, long start); | |
87 | } | |
88 | ||
89 | // ------------------------------------------------------------------------ | |
90 | // Tree-specific configuration | |
91 | // ------------------------------------------------------------------------ | |
92 | ||
93 | /* Tree configuration constants */ | |
94 | private final File fHistoryFile; | |
95 | private final int fBlockSize; | |
96 | private final int fMaxChildren; | |
97 | private final int fProviderVersion; | |
98 | private final long fTreeStart; | |
99 | private final IHTIntervalReader<E> fIntervalReader; | |
100 | ||
101 | /** Reader/writer object */ | |
102 | private HtIo<E, N> fTreeIO; | |
103 | ||
104 | // ------------------------------------------------------------------------ | |
105 | // Variable Fields (will change throughout the existence of the SHT) | |
106 | // ------------------------------------------------------------------------ | |
107 | ||
108 | /** Latest timestamp found in the tree (at any given moment) */ | |
109 | private long fTreeEnd; | |
110 | ||
111 | /** The total number of nodes that exists in this tree */ | |
112 | private int fNodeCount; | |
113 | ||
114 | /** "Cache" to keep the active nodes in memory */ | |
115 | private final List<N> fLatestBranch; | |
116 | ||
117 | /* Lock used to protect the accesses to the HT_IO object */ | |
118 | private final ReentrantReadWriteLock fRwl = new ReentrantReadWriteLock(false); | |
119 | ||
120 | /** | |
121 | * Create a new State History from scratch, specifying all configuration | |
122 | * parameters. | |
123 | * | |
124 | * @param stateHistoryFile | |
125 | * The name of the history file | |
126 | * @param blockSize | |
127 | * The size of each "block" on disk in bytes. One node will | |
128 | * always fit in one block. It should be at least 4096. | |
129 | * @param maxChildren | |
130 | * The maximum number of children allowed per core (non-leaf) | |
131 | * node. | |
132 | * @param providerVersion | |
133 | * The version of the state provider. If a file already exists, | |
134 | * and their versions match, the history file will not be rebuilt | |
135 | * uselessly. | |
136 | * @param treeStart | |
137 | * The start time of the history | |
138 | * @param intervalReader | |
139 | * The factory to create new tree intervals when reading from | |
140 | * the disk | |
141 | * @throws IOException | |
142 | * If an error happens trying to open/write to the file | |
143 | * specified in the config | |
144 | */ | |
145 | public AbstractHistoryTree(File stateHistoryFile, | |
146 | int blockSize, | |
147 | int maxChildren, | |
148 | int providerVersion, | |
149 | long treeStart, | |
150 | IHTIntervalReader<E> intervalReader) throws IOException { | |
151 | /* | |
152 | * Simple check to make sure we have enough place in the 0th block for | |
153 | * the tree configuration | |
154 | */ | |
155 | if (blockSize < TREE_HEADER_SIZE) { | |
156 | throw new IllegalArgumentException(); | |
157 | } | |
158 | ||
159 | fHistoryFile = stateHistoryFile; | |
160 | fBlockSize = blockSize; | |
161 | fMaxChildren = maxChildren; | |
162 | fProviderVersion = providerVersion; | |
163 | fTreeStart = treeStart; | |
164 | fIntervalReader = intervalReader; | |
165 | ||
166 | fTreeEnd = treeStart; | |
167 | fNodeCount = 0; | |
168 | fLatestBranch = NonNullUtils.checkNotNull(Collections.synchronizedList(new ArrayList<>())); | |
169 | ||
170 | /* Prepare the IO object */ | |
171 | fTreeIO = new HtIo<>(stateHistoryFile, | |
172 | blockSize, | |
173 | maxChildren, | |
174 | true, | |
175 | intervalReader, | |
176 | getNodeFactory()); | |
177 | ||
178 | /* Add the first node to the tree */ | |
179 | N firstNode = initNewLeafNode(-1, treeStart); | |
180 | fLatestBranch.add(firstNode); | |
181 | } | |
182 | ||
183 | /** | |
184 | * "Reader" constructor : instantiate a SHTree from an existing tree file on | |
185 | * disk | |
186 | * | |
187 | * @param existingStateFile | |
188 | * Path/filename of the history-file we are to open | |
189 | * @param expectedProviderVersion | |
190 | * The expected version of the state provider | |
191 | * @param intervalReader | |
192 | * The factory used to read segments from the history tree | |
193 | * @throws IOException | |
194 | * If an error happens reading the file | |
195 | */ | |
196 | public AbstractHistoryTree(File existingStateFile, | |
197 | int expectedProviderVersion, | |
198 | IHTIntervalReader<E> intervalReader) throws IOException { | |
199 | /* | |
200 | * Open the file ourselves, get the tree header information we need, | |
201 | * then pass on the descriptor to the TreeIO object. | |
202 | */ | |
203 | int rootNodeSeqNb, res; | |
204 | int bs, maxc; | |
205 | long startTime; | |
206 | ||
207 | /* Java I/O mumbo jumbo... */ | |
208 | if (!existingStateFile.exists()) { | |
209 | throw new IOException("Selected state file does not exist"); //$NON-NLS-1$ | |
210 | } | |
211 | if (existingStateFile.length() <= 0) { | |
212 | throw new IOException("Empty target file"); //$NON-NLS-1$ | |
213 | } | |
214 | ||
215 | try (FileInputStream fis = new FileInputStream(existingStateFile); | |
216 | FileChannel fc = fis.getChannel();) { | |
217 | ||
218 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); | |
219 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
220 | buffer.clear(); | |
221 | ||
222 | res = fc.read(buffer); | |
223 | if (res != TREE_HEADER_SIZE) { | |
224 | throw new IOException("Invalid header size"); //$NON-NLS-1$ | |
225 | } | |
226 | ||
227 | buffer.flip(); | |
228 | ||
229 | /* | |
230 | * Check the magic number to make sure we're opening the right type | |
231 | * of file | |
232 | */ | |
233 | res = buffer.getInt(); | |
234 | if (res != getMagicNumber()) { | |
235 | throw new IOException("Wrong magic number"); //$NON-NLS-1$ | |
236 | } | |
237 | ||
238 | res = buffer.getInt(); /* File format version number */ | |
239 | if (res != getFileVersion()) { | |
240 | throw new IOException("Mismatching History Tree file format versions"); //$NON-NLS-1$ | |
241 | } | |
242 | ||
243 | res = buffer.getInt(); /* Event handler's version number */ | |
244 | if (res != expectedProviderVersion) { | |
245 | /* | |
246 | * The existing history was built using an event handler that | |
247 | * doesn't match the current one in the framework. | |
248 | * | |
249 | * Information could be all wrong. Instead of keeping an | |
250 | * incorrect history file, a rebuild is done. | |
251 | */ | |
252 | throw new IOException("Mismatching event handler versions"); //$NON-NLS-1$ | |
253 | } | |
254 | ||
255 | bs = buffer.getInt(); /* Block Size */ | |
256 | maxc = buffer.getInt(); /* Max nb of children per node */ | |
257 | ||
258 | fNodeCount = buffer.getInt(); | |
259 | rootNodeSeqNb = buffer.getInt(); | |
260 | startTime = buffer.getLong(); | |
261 | ||
262 | /* Set all other permanent configuration options */ | |
263 | fHistoryFile = existingStateFile; | |
264 | fBlockSize = bs; | |
265 | fMaxChildren = maxc; | |
266 | fProviderVersion = expectedProviderVersion; | |
267 | fIntervalReader = intervalReader; | |
268 | fTreeStart = startTime; | |
269 | } | |
270 | ||
271 | /* | |
272 | * FIXME We close fis here and the TreeIO will then reopen the same | |
273 | * file, not extremely elegant. But how to pass the information here to | |
274 | * the SHT otherwise? | |
275 | */ | |
276 | fTreeIO = new HtIo<>(fHistoryFile, | |
277 | fBlockSize, | |
278 | fMaxChildren, | |
279 | false, | |
280 | fIntervalReader, | |
281 | getNodeFactory()); | |
282 | ||
283 | fLatestBranch = buildLatestBranch(rootNodeSeqNb); | |
284 | fTreeEnd = getRootNode().getNodeEnd(); | |
285 | ||
286 | /* | |
287 | * Make sure the history start time we read previously is consistent | |
288 | * with was is actually in the root node. | |
289 | */ | |
290 | if (startTime != getRootNode().getNodeStart()) { | |
291 | throw new IOException("Inconsistent start times in the " + //$NON-NLS-1$ | |
292 | "history file, it might be corrupted."); //$NON-NLS-1$ | |
293 | } | |
294 | } | |
295 | ||
296 | /** | |
297 | * Rebuild the latestBranch "cache" object by reading the nodes from disk | |
298 | * (When we are opening an existing file on disk and want to append to it, | |
299 | * for example). | |
300 | * | |
301 | * @param rootNodeSeqNb | |
302 | * The sequence number of the root node, so we know where to | |
303 | * start | |
304 | * @throws ClosedChannelException | |
305 | */ | |
306 | private List<N> buildLatestBranch(int rootNodeSeqNb) throws ClosedChannelException { | |
307 | List<N> list = new ArrayList<>(); | |
308 | ||
309 | N nextChildNode = fTreeIO.readNode(rootNodeSeqNb); | |
310 | list.add(nextChildNode); | |
311 | ||
312 | // TODO: Do we need the full latest branch? The latest leaf may not be | |
313 | // the one we'll query first... Won't it build itself later? | |
314 | ||
315 | /* Follow the last branch up to the leaf */ | |
316 | while (nextChildNode.getNodeType() == HTNode.NodeType.CORE) { | |
317 | nextChildNode = fTreeIO.readNode(nextChildNode.getLatestChild()); | |
318 | list.add(nextChildNode); | |
319 | } | |
320 | return Collections.synchronizedList(list); | |
321 | } | |
322 | ||
323 | // ------------------------------------------------------------------------ | |
324 | // Accessors | |
325 | // ------------------------------------------------------------------------ | |
326 | ||
327 | @Override | |
328 | public long getTreeStart() { | |
329 | return fTreeStart; | |
330 | } | |
331 | ||
332 | @Override | |
333 | public long getTreeEnd() { | |
334 | return fTreeEnd; | |
335 | } | |
336 | ||
337 | /** | |
338 | * Get the number of nodes in this tree. | |
339 | * | |
340 | * @return The number of nodes | |
341 | */ | |
342 | public int getNodeCount() { | |
343 | return fNodeCount; | |
344 | } | |
345 | ||
346 | /** | |
347 | * Get the current root node of this tree | |
348 | * | |
349 | * @return The root node | |
350 | */ | |
351 | public N getRootNode() { | |
352 | return fLatestBranch.get(0); | |
353 | } | |
354 | ||
355 | @Override | |
356 | public long getFileSize() { | |
357 | return fHistoryFile.length(); | |
358 | } | |
359 | ||
360 | /** | |
361 | * Return the latest branch of the tree. That branch is immutable. | |
362 | * | |
363 | * @return The immutable latest branch | |
364 | */ | |
365 | @VisibleForTesting | |
8b03451b | 366 | List<N> getLatestBranch() { |
5e7913a4 GB |
367 | return ImmutableList.copyOf(fLatestBranch); |
368 | } | |
369 | ||
370 | /** | |
371 | * Get the node in the latest branch at a depth. If the depth is too large, | |
372 | * it will throw an IndexOutOfBoundsException | |
373 | * | |
374 | * @param depth | |
375 | * The depth at which to get the node | |
376 | * @return The node at depth | |
377 | */ | |
fb7125d6 | 378 | protected N getLatestNode(int depth) { |
5e7913a4 GB |
379 | if (depth > fLatestBranch.size()) { |
380 | throw new IndexOutOfBoundsException("Trying to get latest node too deep"); //$NON-NLS-1$ | |
381 | } | |
382 | return fLatestBranch.get(depth); | |
383 | } | |
384 | ||
385 | /** | |
386 | * Get the magic number for the history file. This number should be specific | |
387 | * for each implementation of the history tree. | |
388 | * | |
389 | * @return The magic number for the history file | |
390 | */ | |
391 | protected abstract int getMagicNumber(); | |
392 | ||
393 | /** | |
394 | * Get the file version for the history file. This file version should be | |
395 | * modified for a history tree class whenever changing the format of the | |
396 | * file. Different versions of the file may not be compatible. | |
397 | * | |
398 | * @return The file version for the history file. | |
399 | */ | |
400 | protected abstract int getFileVersion(); | |
401 | ||
402 | /** | |
403 | * Get the factory to use to create new nodes for this history tree. | |
404 | * | |
405 | * This method is called in the constructor of the abstract class, so | |
406 | * assigning the factory to a final field may cause NullPointerException | |
407 | * since that final field may not be initialized the first time this is | |
408 | * called. | |
409 | * | |
410 | * @return The NodeFactory for the History Tree | |
411 | */ | |
412 | protected abstract IHTNodeFactory<E, N> getNodeFactory(); | |
413 | ||
414 | /** | |
415 | * Read a node with a given sequence number | |
416 | * | |
417 | * @param seqNum | |
418 | * The sequence number of the node to read | |
419 | * @return The HTNode object | |
420 | * @throws ClosedChannelException | |
421 | * Exception thrown when reading the node, if the file was | |
422 | * closed | |
423 | */ | |
424 | @VisibleForTesting | |
8b03451b | 425 | @NonNull N getNode(int seqNum) throws ClosedChannelException { |
5e7913a4 GB |
426 | // First, check in the latest branch if the node is there |
427 | for (N node : fLatestBranch) { | |
428 | if (node.getSequenceNumber() == seqNum) { | |
429 | return node; | |
430 | } | |
431 | } | |
432 | return fTreeIO.readNode(seqNum); | |
433 | } | |
434 | ||
435 | /** | |
436 | * Retrieve the TreeIO object. Should only be used for testing. | |
437 | * | |
438 | * @return The TreeIO | |
439 | */ | |
440 | @VisibleForTesting | |
8b03451b | 441 | HtIo<E, N> getTreeIO() { |
5e7913a4 GB |
442 | return fTreeIO; |
443 | } | |
444 | ||
445 | // ------------------------------------------------------------------------ | |
446 | // HT_IO interface | |
447 | // ------------------------------------------------------------------------ | |
448 | ||
449 | // TODO Remove from here | |
450 | @Override | |
451 | public FileInputStream supplyATReader() { | |
452 | fRwl.readLock().lock(); | |
453 | try { | |
454 | return fTreeIO.supplyATReader(getNodeCount()); | |
455 | } finally { | |
456 | fRwl.readLock().unlock(); | |
457 | } | |
458 | } | |
459 | ||
460 | // TODO Remove from here | |
461 | @Override | |
462 | public File supplyATWriterFile() { | |
463 | return fHistoryFile; | |
464 | } | |
465 | ||
466 | // TODO Remove from here | |
467 | @Override | |
468 | public long supplyATWriterFilePos() { | |
469 | return IHistoryTree.TREE_HEADER_SIZE | |
470 | + ((long) getNodeCount() * fBlockSize); | |
471 | } | |
472 | ||
473 | /** | |
474 | * Read a node from the tree. | |
475 | * | |
476 | * @param seqNumber | |
477 | * The sequence number of the node to read | |
478 | * @return The node | |
479 | * @throws ClosedChannelException | |
480 | * If the tree IO is unavailable | |
481 | */ | |
482 | public N readNode(int seqNumber) throws ClosedChannelException { | |
483 | /* Try to read the node from memory */ | |
484 | synchronized (fLatestBranch) { | |
485 | for (N node : fLatestBranch) { | |
486 | if (node.getSequenceNumber() == seqNumber) { | |
487 | return node; | |
488 | } | |
489 | } | |
490 | } | |
491 | ||
492 | fRwl.readLock().lock(); | |
493 | try { | |
494 | /* Read the node from disk */ | |
495 | return fTreeIO.readNode(seqNumber); | |
496 | } finally { | |
497 | fRwl.readLock().unlock(); | |
498 | } | |
499 | } | |
500 | ||
501 | /** | |
502 | * Write a node object to the history file. | |
503 | * | |
504 | * @param node | |
505 | * The node to write to disk | |
506 | */ | |
507 | public void writeNode(N node) { | |
508 | fRwl.readLock().lock(); | |
509 | try { | |
510 | fTreeIO.writeNode(node); | |
511 | } finally { | |
512 | fRwl.readLock().unlock(); | |
513 | } | |
514 | } | |
515 | ||
516 | /** | |
517 | * Close the history file. | |
518 | */ | |
519 | @Override | |
520 | public void closeFile() { | |
521 | fRwl.writeLock().lock(); | |
522 | try { | |
523 | fTreeIO.closeFile(); | |
524 | clearContent(); | |
525 | } finally { | |
526 | fRwl.writeLock().unlock(); | |
527 | } | |
528 | } | |
529 | ||
530 | /** | |
531 | * Delete the history file. | |
532 | */ | |
533 | @Override | |
534 | public void deleteFile() { | |
535 | fRwl.writeLock().lock(); | |
536 | try { | |
537 | fTreeIO.deleteFile(); | |
538 | clearContent(); | |
539 | } finally { | |
540 | fRwl.writeLock().unlock(); | |
541 | } | |
542 | } | |
543 | ||
544 | @Override | |
545 | public void cleanFile() throws IOException { | |
546 | fRwl.writeLock().lock(); | |
547 | try { | |
548 | closeTree(fTreeEnd); | |
549 | fTreeIO.deleteFile(); | |
550 | ||
551 | fTreeIO = new HtIo<>(fHistoryFile, | |
552 | fBlockSize, | |
553 | fMaxChildren, | |
554 | true, | |
555 | fIntervalReader, | |
556 | getNodeFactory()); | |
557 | ||
558 | clearContent(); | |
559 | /* Add the first node to the tree */ | |
560 | N firstNode = initNewLeafNode(-1, fTreeStart); | |
561 | fLatestBranch.add(firstNode); | |
562 | } finally { | |
563 | fRwl.writeLock().unlock(); | |
564 | } | |
565 | } | |
566 | ||
567 | private void clearContent() { | |
568 | // Re-initialize the content of the tree after the file is deleted or | |
569 | // closed | |
570 | fNodeCount = 0; | |
571 | fLatestBranch.clear(); | |
572 | } | |
573 | ||
574 | // ------------------------------------------------------------------------ | |
575 | // Operations | |
576 | // ------------------------------------------------------------------------ | |
577 | ||
578 | /** | |
579 | * Insert an interval in the tree. | |
580 | * | |
581 | * @param interval | |
582 | * The interval to be inserted | |
583 | * @throws RangeException | |
584 | * If the start of end time of the interval are invalid | |
585 | */ | |
586 | @Override | |
587 | public synchronized void insert(E interval) throws RangeException { | |
588 | if (interval.getStart() < fTreeStart) { | |
589 | throw new RangeException("Interval Start:" + interval.getStart() + ", Config Start:" + fTreeStart); //$NON-NLS-1$ //$NON-NLS-2$ | |
590 | } | |
591 | tryInsertAtNode(interval, fLatestBranch.size() - 1); | |
592 | } | |
593 | ||
594 | /** | |
595 | * Add a new empty core node to the tree. | |
596 | * | |
597 | * @param parentSeqNumber | |
598 | * Sequence number of this node's parent | |
599 | * @param startTime | |
600 | * Start time of the new node | |
601 | * @return The newly created node | |
602 | */ | |
603 | protected final N initNewCoreNode(int parentSeqNumber, long startTime) { | |
604 | N newNode = getNodeFactory().createNode(NodeType.CORE, fBlockSize, fMaxChildren, | |
605 | fNodeCount, parentSeqNumber, startTime); | |
606 | fNodeCount++; | |
607 | return newNode; | |
608 | } | |
609 | ||
610 | /** | |
611 | * Add a new empty leaf node to the tree. | |
612 | * | |
613 | * @param parentSeqNumber | |
614 | * Sequence number of this node's parent | |
615 | * @param startTime | |
616 | * Start time of the new node | |
617 | * @return The newly created node | |
618 | */ | |
619 | protected final N initNewLeafNode(int parentSeqNumber, long startTime) { | |
620 | N newNode = getNodeFactory().createNode(NodeType.LEAF, fBlockSize, fMaxChildren, | |
621 | fNodeCount, parentSeqNumber, startTime); | |
622 | fNodeCount++; | |
623 | return newNode; | |
624 | } | |
625 | ||
626 | /** | |
627 | * Inner method to find in which node we should add the interval. | |
628 | * | |
629 | * @param interval | |
630 | * The interval to add to the tree | |
631 | * @param depth | |
632 | * The index *in the latestBranch* where we are trying the | |
633 | * insertion | |
634 | */ | |
635 | protected final void tryInsertAtNode(E interval, int depth) { | |
636 | N targetNode = getLatestBranch().get(depth); | |
fb7125d6 | 637 | informInsertingAtDepth(depth); |
5e7913a4 GB |
638 | |
639 | /* Verify if there is enough room in this node to store this interval */ | |
640 | if (interval.getSizeOnDisk() > targetNode.getNodeFreeSpace()) { | |
641 | /* Nope, not enough room. Insert in a new sibling instead. */ | |
642 | addSiblingNode(depth, getNewBranchStart(depth, interval)); | |
643 | tryInsertAtNode(interval, getLatestBranch().size() - 1); | |
644 | return; | |
645 | } | |
646 | ||
647 | /* Make sure the interval time range fits this node */ | |
648 | if (interval.getStart() < targetNode.getNodeStart()) { | |
649 | /* | |
650 | * No, this interval starts before the startTime of this node. We | |
651 | * need to check recursively in parents if it can fit. | |
652 | */ | |
653 | tryInsertAtNode(interval, depth - 1); | |
654 | return; | |
655 | } | |
656 | ||
657 | /* | |
658 | * Ok, there is room, and the interval fits in this time slot. Let's add | |
659 | * it. | |
660 | */ | |
661 | targetNode.add(interval); | |
662 | ||
663 | updateEndTime(interval); | |
664 | } | |
665 | ||
fb7125d6 LPD |
666 | /** |
667 | * Informs the tree that the insertion is requested at a given depth. When | |
668 | * this is called, the element is not yet inserted, but the last call to | |
669 | * this for an element will represent the depth at which is was really | |
670 | * inserted. By default, this method does nothing and should not be | |
671 | * necessary for concrete implementations, but it can be used by unit tests | |
672 | * to check to position of insertion of elements. | |
673 | * | |
674 | * @param depth | |
675 | * The depth at which the last insertion was done | |
676 | */ | |
677 | @VisibleForTesting | |
678 | protected void informInsertingAtDepth(int depth) { | |
679 | ||
680 | } | |
681 | ||
5e7913a4 GB |
682 | /** |
683 | * Get the start time of the new node of the branch that will be added | |
684 | * starting at depth. | |
685 | * | |
686 | * Note that the depth is the depth of the last node that was filled and to | |
687 | * which a sibling should be added. But depending on the returned start | |
688 | * time, the actual new branch may start at a lower depth if the start time | |
689 | * happens to be lesser than the parent's start time. | |
690 | * | |
691 | * @param depth | |
692 | * The depth of the last node that was filled and at which the | |
693 | * new branch should start. | |
694 | * @param interval | |
695 | * The interval that is about to be inserted | |
696 | * @return The value that should be the start time of the sibling node | |
697 | */ | |
698 | protected abstract long getNewBranchStart(int depth, E interval); | |
699 | ||
700 | /** | |
701 | * Method to add a sibling to any node in the latest branch. This will add | |
702 | * children back down to the leaf level, if needed. | |
703 | * | |
704 | * @param depth | |
705 | * The depth in latestBranch where we start adding | |
706 | * @param newNodeStartTime | |
707 | * The start time of the new node | |
708 | */ | |
709 | private final void addSiblingNode(int depth, long newNodeStartTime) { | |
710 | synchronized (fLatestBranch) { | |
711 | final long splitTime = fTreeEnd; | |
712 | ||
713 | if (depth >= fLatestBranch.size()) { | |
714 | /* | |
715 | * We need to make sure (indexOfNode - 1) doesn't get the last | |
716 | * node in the branch, because that one is a Leaf Node. | |
717 | */ | |
718 | throw new IllegalStateException(); | |
719 | } | |
720 | ||
721 | /* Check if we need to add a new root node */ | |
722 | if (depth == 0) { | |
723 | addNewRootNode(newNodeStartTime); | |
724 | return; | |
725 | } | |
726 | ||
727 | /* | |
728 | * Check if we can indeed add a child to the target parent and if | |
729 | * the new start time is not before the target parent. | |
730 | */ | |
731 | if (fLatestBranch.get(depth - 1).getNbChildren() == fMaxChildren || | |
732 | newNodeStartTime < fLatestBranch.get(depth - 1).getNodeStart()) { | |
733 | /* If not, add a branch starting one level higher instead */ | |
734 | addSiblingNode(depth - 1, newNodeStartTime); | |
735 | return; | |
736 | } | |
737 | ||
738 | /* | |
739 | * Close nodes from the leaf up because some parent nodes may need | |
740 | * to get updated when their children are closed | |
741 | */ | |
742 | for (int i = fLatestBranch.size() - 1; i >= depth; i--) { | |
743 | fLatestBranch.get(i).closeThisNode(splitTime); | |
744 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
745 | } | |
746 | ||
747 | /* Split off the new branch from the old one */ | |
748 | for (int i = depth; i < fLatestBranch.size(); i++) { | |
749 | N prevNode = fLatestBranch.get(i - 1); | |
750 | N newNode; | |
751 | ||
752 | switch (fLatestBranch.get(i).getNodeType()) { | |
753 | case CORE: | |
754 | newNode = initNewCoreNode(prevNode.getSequenceNumber(), newNodeStartTime); | |
755 | break; | |
756 | case LEAF: | |
757 | newNode = initNewLeafNode(prevNode.getSequenceNumber(), newNodeStartTime); | |
758 | break; | |
759 | default: | |
760 | throw new IllegalStateException(); | |
761 | } | |
762 | ||
763 | prevNode.linkNewChild(newNode); | |
764 | fLatestBranch.set(i, newNode); | |
765 | } | |
766 | } | |
767 | } | |
768 | ||
769 | /** | |
770 | * Similar to the previous method, except here we rebuild a completely new | |
771 | * latestBranch | |
772 | */ | |
773 | private void addNewRootNode(long newNodeStartTime) { | |
774 | final long nodeEnd = fTreeEnd; | |
775 | ||
776 | N oldRootNode = fLatestBranch.get(0); | |
777 | N newRootNode = initNewCoreNode(-1, fTreeStart); | |
778 | ||
779 | /* Tell the old root node that it isn't root anymore */ | |
780 | oldRootNode.setParentSequenceNumber(newRootNode.getSequenceNumber()); | |
781 | ||
782 | /* Close off the whole current latestBranch */ | |
783 | for (int i = fLatestBranch.size() - 1; i >= 0; i--) { | |
784 | fLatestBranch.get(i).closeThisNode(nodeEnd); | |
785 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
786 | } | |
787 | ||
788 | /* Link the new root to its first child (the previous root node) */ | |
789 | newRootNode.linkNewChild(oldRootNode); | |
790 | ||
791 | /* Rebuild a new latestBranch */ | |
792 | int depth = fLatestBranch.size(); | |
793 | fLatestBranch.clear(); | |
794 | fLatestBranch.add(newRootNode); | |
795 | ||
796 | // Create new coreNode | |
797 | for (int i = 1; i < depth; i++) { | |
798 | N prevNode = fLatestBranch.get(i - 1); | |
799 | N newNode = initNewCoreNode(prevNode.getSequenceNumber(), newNodeStartTime); | |
800 | prevNode.linkNewChild(newNode); | |
801 | fLatestBranch.add(newNode); | |
802 | } | |
803 | ||
804 | // Create the new leafNode | |
805 | N prevNode = fLatestBranch.get(depth - 1); | |
806 | N newNode = initNewLeafNode(prevNode.getSequenceNumber(), newNodeStartTime); | |
807 | prevNode.linkNewChild(newNode); | |
808 | fLatestBranch.add(newNode); | |
809 | } | |
810 | ||
811 | /** | |
812 | * Update the tree's end time with this interval data | |
813 | * | |
814 | * @param interval | |
815 | * The interval that was just added to the tree | |
816 | */ | |
817 | protected void updateEndTime(E interval) { | |
818 | fTreeEnd = Math.max(fTreeEnd, interval.getEnd()); | |
819 | } | |
820 | ||
821 | @Override | |
822 | public void closeTree(long requestedEndTime) { | |
823 | /* This is an important operation, queries can wait */ | |
824 | synchronized (fLatestBranch) { | |
825 | /* | |
826 | * Work-around the "empty branches" that get created when the root | |
827 | * node becomes full. Overwrite the tree's end time with the | |
828 | * original wanted end-time, to ensure no queries are sent into | |
829 | * those empty nodes. | |
830 | */ | |
831 | fTreeEnd = requestedEndTime; | |
832 | ||
833 | /* Close off the latest branch of the tree */ | |
834 | for (int i = fLatestBranch.size() - 1; i >= 0; i--) { | |
835 | fLatestBranch.get(i).closeThisNode(fTreeEnd); | |
836 | fTreeIO.writeNode(fLatestBranch.get(i)); | |
837 | } | |
838 | ||
839 | try (FileOutputStream fc = fTreeIO.getFileWriter(-1);) { | |
840 | ByteBuffer buffer = ByteBuffer.allocate(TREE_HEADER_SIZE); | |
841 | buffer.order(ByteOrder.LITTLE_ENDIAN); | |
842 | buffer.clear(); | |
843 | ||
844 | buffer.putInt(getMagicNumber()); | |
845 | ||
846 | buffer.putInt(getFileVersion()); | |
847 | buffer.putInt(fProviderVersion); | |
848 | ||
849 | buffer.putInt(fBlockSize); | |
850 | buffer.putInt(fMaxChildren); | |
851 | ||
852 | buffer.putInt(fNodeCount); | |
853 | ||
854 | /* root node seq. nb */ | |
855 | buffer.putInt(fLatestBranch.get(0).getSequenceNumber()); | |
856 | ||
857 | /* start time of this history */ | |
858 | buffer.putLong(fLatestBranch.get(0).getNodeStart()); | |
859 | ||
860 | buffer.flip(); | |
861 | fc.write(buffer.array()); | |
862 | /* done writing the file header */ | |
863 | ||
864 | } catch (IOException e) { | |
865 | /* | |
866 | * If we were able to write so far, there should not be any | |
867 | * problem at this point... | |
868 | */ | |
869 | throw new RuntimeException("State system write error"); //$NON-NLS-1$ | |
870 | } | |
871 | } | |
872 | } | |
873 | ||
874 | @Override | |
875 | public Iterable<E> getMatchingIntervals(RangeCondition<Long> timeCondition, | |
876 | Predicate<E> extraPredicate) { | |
877 | ||
878 | // TODO Change this to evaluate the nodes lazily | |
879 | ||
880 | List<Iterable<E>> intervalsOfNodes = new LinkedList<>(); | |
881 | ||
882 | /* Queue is a stack of nodes containing nodes intersecting t */ | |
883 | Deque<Integer> queue = new LinkedList<>(); | |
884 | /* We start by reading the information in the root node */ | |
885 | queue.add(getRootNode().getSequenceNumber()); | |
886 | ||
887 | /* Then we follow the down in the relevant children */ | |
888 | try { | |
889 | while (!queue.isEmpty()) { | |
890 | int sequenceNumber = queue.pop(); | |
891 | HTNode<E> currentNode = readNode(sequenceNumber); | |
892 | RangeCondition<Long> nodeCondition = timeCondition.subCondition( | |
893 | currentNode.getNodeStart(), currentNode.getNodeEnd()); | |
894 | ||
895 | if (nodeCondition == null) { | |
896 | continue; | |
897 | } | |
898 | ||
899 | if (currentNode.getNodeType() == HTNode.NodeType.CORE) { | |
900 | /* Here we add the relevant children nodes for BFS */ | |
901 | queue.addAll(currentNode.selectNextChildren(nodeCondition)); | |
902 | } | |
903 | Iterable<E> nodeIntervals = currentNode.getMatchingIntervals(nodeCondition, extraPredicate); | |
904 | intervalsOfNodes.add(nodeIntervals); | |
905 | } | |
906 | } catch (ClosedChannelException e) { | |
907 | } | |
908 | return Iterables.concat(intervalsOfNodes); | |
909 | } | |
910 | ||
911 | @Override | |
912 | public String toString() { | |
913 | return "Information on the current tree:\n\n" + "Blocksize: " //$NON-NLS-1$ //$NON-NLS-2$ | |
914 | + fBlockSize + "\n" + "Max nb. of children per node: " //$NON-NLS-1$//$NON-NLS-2$ | |
915 | + fMaxChildren + "\n" + "Number of nodes: " + fNodeCount //$NON-NLS-1$//$NON-NLS-2$ | |
916 | + "\n" + "Depth of the tree: " + fLatestBranch.size() + "\n" //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ | |
917 | + "Size of the treefile: " + getFileSize() + "\n" //$NON-NLS-1$//$NON-NLS-2$ | |
918 | + "Root node has sequence number: " //$NON-NLS-1$ | |
919 | + fLatestBranch.get(0).getSequenceNumber() + "\n" //$NON-NLS-1$ | |
920 | + "'Latest leaf' has sequence number: " //$NON-NLS-1$ | |
921 | + fLatestBranch.get(fLatestBranch.size() - 1).getSequenceNumber(); | |
922 | } | |
923 | ||
8b03451b GB |
924 | |
925 | // ------------------------------------------------------------------------ | |
926 | // Test-specific methods | |
927 | // ------------------------------------------------------------------------ | |
928 | ||
929 | /** | |
930 | * Get the current depth of the tree. | |
931 | * | |
932 | * @return The current depth | |
933 | */ | |
934 | @VisibleForTesting | |
935 | protected int getDepth() { | |
936 | return getLatestBranch().size(); | |
937 | } | |
938 | ||
939 | /** | |
940 | * Get the leaf (bottom-most) node of the latest branch. | |
941 | * | |
942 | * @return The latest leaf | |
943 | */ | |
944 | @VisibleForTesting | |
945 | protected N getLatestLeaf() { | |
946 | List<N> latestBranch = getLatestBranch(); | |
947 | return latestBranch.get(latestBranch.size() - 1); | |
948 | } | |
949 | ||
950 | /** | |
951 | * Verify a node's specific information about a child. | |
952 | * | |
953 | * @param parent | |
954 | * The parent node | |
955 | * @param index | |
956 | * The index of the child in the parent's extra data | |
957 | * @param child | |
958 | * The child node to verify | |
959 | * @return False if a problem was found, true otherwise | |
960 | */ | |
961 | @VisibleForTesting | |
962 | protected boolean verifyChildrenSpecific(N parent, | |
963 | int index, | |
964 | N child) { | |
965 | // Nothing to do for the default implementation | |
966 | return true; | |
967 | } | |
968 | ||
969 | /** | |
970 | * This method should verify in the whole time range of the parent node that | |
971 | * the child node appears or not as a next children for a given timestamp. | |
972 | * | |
973 | * @param parent | |
974 | * The parent node | |
975 | * @param child | |
976 | * The child node | |
977 | * @return False if a problem was found, true otherwise | |
978 | */ | |
979 | @VisibleForTesting | |
980 | protected boolean verifyIntersectingChildren(N parent, N child) { | |
981 | int childSequence = child.getSequenceNumber(); | |
982 | boolean shouldBeInCollection; | |
983 | Collection<Integer> nextChildren; | |
984 | for (long t = parent.getNodeStart(); t < parent.getNodeEnd(); t++) { | |
985 | shouldBeInCollection = true; | |
986 | nextChildren = parent.selectNextChildren(RangeCondition.singleton(t)); | |
987 | if (shouldBeInCollection != nextChildren.contains(childSequence)) { | |
988 | return false; | |
989 | } | |
990 | } | |
991 | return true; | |
992 | } | |
5e7913a4 | 993 | } |