Commit | Line | Data |
---|---|---|
26a6a7eb | 1 | /******************************************************************************* |
e5083481 | 2 | * Copyright (c) 2015 EfficiOS Inc., Alexandre Montplaisir and others. |
26a6a7eb AM |
3 | * |
4 | * All rights reserved. This program and the accompanying materials | |
5 | * are made available under the terms of the Eclipse Public License v1.0 | |
6 | * which 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 | *******************************************************************************/ | |
12 | ||
13 | package org.eclipse.tracecompass.segmentstore.core.treemap; | |
14 | ||
15 | import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; | |
16 | ||
26a6a7eb | 17 | import java.util.Iterator; |
26a6a7eb AM |
18 | import java.util.TreeMap; |
19 | ||
26a6a7eb AM |
20 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
21 | import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; | |
e5083481 | 22 | import org.eclipse.tracecompass.segmentstore.core.SegmentComparators; |
26a6a7eb AM |
23 | |
24 | import com.google.common.collect.Iterables; | |
e5083481 | 25 | import com.google.common.collect.Ordering; |
26a6a7eb AM |
26 | import com.google.common.collect.Sets; |
27 | import com.google.common.collect.TreeMultimap; | |
28 | ||
29 | /** | |
30 | * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s. | |
31 | * This relatively simple implementation holds everything in memory, and as such | |
32 | * cannot contain too much data. | |
33 | * | |
e5083481 PT |
34 | * The TreeMapStore itself is Iterable, and its iteration order will be by |
35 | * ascending order of start times. For segments with identical start times, the | |
36 | * secondary comparator will be the end time. If even those are equal, it will | |
37 | * defer to the segments' natural ordering ({@link ISegment#compareTo}). | |
38 | * | |
39 | * The store's tree maps will not accept duplicate key-value pairs, which means | |
40 | * that if you want several segments with the same start and end times, make | |
41 | * sure their compareTo() differentiates them. | |
42 | * | |
26a6a7eb | 43 | * @param <T> |
e5083481 | 44 | * The type of segment held in this store |
26a6a7eb AM |
45 | * |
46 | * @author Alexandre Montplaisir | |
47 | */ | |
48 | public class TreeMapStore<T extends ISegment> implements ISegmentStore<T> { | |
49 | ||
50 | private final TreeMultimap<Long, T> fStartTimesIndex; | |
51 | private final TreeMultimap<Long, T> fEndTimesIndex; | |
52 | ||
52d9d1f6 | 53 | private volatile long fSize; |
26a6a7eb AM |
54 | |
55 | /** | |
e5083481 | 56 | * Constructor |
26a6a7eb AM |
57 | */ |
58 | public TreeMapStore() { | |
e5083481 PT |
59 | /* |
60 | * For the start times index, the "key comparator" will compare the | |
61 | * start times as longs directly. This is the primary comparator for its | |
62 | * tree map. | |
63 | * | |
64 | * The secondary "value" comparator will check the end times first, and | |
65 | * in the event of a tie, defer to the ISegment's Comparable | |
66 | * implementation, a.k.a. its natural ordering. | |
67 | * | |
68 | * The same is done for the end times index, but swapping the first two | |
69 | * comparators instead. | |
70 | */ | |
71 | fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create( | |
72 | SegmentComparators.LONG_COMPARATOR, | |
73 | Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural()))); | |
74 | ||
75 | fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create( | |
76 | SegmentComparators.LONG_COMPARATOR, | |
77 | Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural()))); | |
78 | ||
26a6a7eb AM |
79 | fSize = 0; |
80 | } | |
81 | ||
82 | @Override | |
83 | public Iterator<T> iterator() { | |
84 | return checkNotNull(fStartTimesIndex.values().iterator()); | |
85 | } | |
86 | ||
87 | @Override | |
88 | public synchronized void addElement(T val) { | |
e5083481 PT |
89 | if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) { |
90 | fEndTimesIndex.put(Long.valueOf(val.getEnd()), val); | |
91 | fSize++; | |
92 | } | |
26a6a7eb AM |
93 | } |
94 | ||
95 | @Override | |
96 | public long getNbElements() { | |
97 | return fSize; | |
98 | } | |
99 | ||
26a6a7eb AM |
100 | @Override |
101 | public Iterable<T> getIntersectingElements(long position) { | |
102 | /* | |
103 | * The intervals intersecting 't' are those whose 1) start time is | |
104 | * *lower* than 't' AND 2) end time is *higher* than 't'. | |
105 | */ | |
106 | Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values()); | |
107 | Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values()); | |
108 | ||
109 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); | |
110 | } | |
111 | ||
112 | @Override | |
113 | public Iterable<T> getIntersectingElements(long start, long end) { | |
114 | Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values()); | |
115 | Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values()); | |
116 | ||
117 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); | |
118 | } | |
119 | ||
120 | @Override | |
52d9d1f6 | 121 | public synchronized void dispose() { |
26a6a7eb AM |
122 | fStartTimesIndex.clear(); |
123 | fEndTimesIndex.clear(); | |
52d9d1f6 | 124 | fSize = 0; |
26a6a7eb | 125 | } |
26a6a7eb | 126 | } |