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 | 18 | import java.util.TreeMap; |
71e78f69 MK |
19 | import java.util.concurrent.locks.ReadWriteLock; |
20 | import java.util.concurrent.locks.ReentrantReadWriteLock; | |
26a6a7eb | 21 | |
26a6a7eb AM |
22 | import org.eclipse.tracecompass.segmentstore.core.ISegment; |
23 | import org.eclipse.tracecompass.segmentstore.core.ISegmentStore; | |
e5083481 | 24 | import org.eclipse.tracecompass.segmentstore.core.SegmentComparators; |
26a6a7eb AM |
25 | |
26 | import com.google.common.collect.Iterables; | |
e5083481 | 27 | import com.google.common.collect.Ordering; |
26a6a7eb AM |
28 | import com.google.common.collect.Sets; |
29 | import com.google.common.collect.TreeMultimap; | |
30 | ||
31 | /** | |
32 | * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s. | |
33 | * This relatively simple implementation holds everything in memory, and as such | |
34 | * cannot contain too much data. | |
35 | * | |
e5083481 PT |
36 | * The TreeMapStore itself is Iterable, and its iteration order will be by |
37 | * ascending order of start times. For segments with identical start times, the | |
38 | * secondary comparator will be the end time. If even those are equal, it will | |
39 | * defer to the segments' natural ordering ({@link ISegment#compareTo}). | |
40 | * | |
41 | * The store's tree maps will not accept duplicate key-value pairs, which means | |
42 | * that if you want several segments with the same start and end times, make | |
43 | * sure their compareTo() differentiates them. | |
44 | * | |
26a6a7eb | 45 | * @param <T> |
e5083481 | 46 | * The type of segment held in this store |
26a6a7eb AM |
47 | * |
48 | * @author Alexandre Montplaisir | |
49 | */ | |
50 | public class TreeMapStore<T extends ISegment> implements ISegmentStore<T> { | |
51 | ||
71e78f69 MK |
52 | private final ReadWriteLock fLock = new ReentrantReadWriteLock(false); |
53 | ||
26a6a7eb AM |
54 | private final TreeMultimap<Long, T> fStartTimesIndex; |
55 | private final TreeMultimap<Long, T> fEndTimesIndex; | |
56 | ||
71e78f69 | 57 | private long fSize; |
26a6a7eb AM |
58 | |
59 | /** | |
e5083481 | 60 | * Constructor |
26a6a7eb AM |
61 | */ |
62 | public TreeMapStore() { | |
e5083481 PT |
63 | /* |
64 | * For the start times index, the "key comparator" will compare the | |
65 | * start times as longs directly. This is the primary comparator for its | |
66 | * tree map. | |
67 | * | |
68 | * The secondary "value" comparator will check the end times first, and | |
69 | * in the event of a tie, defer to the ISegment's Comparable | |
70 | * implementation, a.k.a. its natural ordering. | |
71 | * | |
72 | * The same is done for the end times index, but swapping the first two | |
73 | * comparators instead. | |
74 | */ | |
75 | fStartTimesIndex = checkNotNull(TreeMultimap.<Long, T> create( | |
76 | SegmentComparators.LONG_COMPARATOR, | |
77 | Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural()))); | |
78 | ||
79 | fEndTimesIndex = checkNotNull(TreeMultimap.<Long, T> create( | |
80 | SegmentComparators.LONG_COMPARATOR, | |
81 | Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural()))); | |
82 | ||
26a6a7eb AM |
83 | fSize = 0; |
84 | } | |
85 | ||
71e78f69 MK |
86 | /** |
87 | * Warning, this is not thread safe, and can cause concurrent modification | |
88 | * exceptions | |
89 | */ | |
26a6a7eb AM |
90 | @Override |
91 | public Iterator<T> iterator() { | |
92 | return checkNotNull(fStartTimesIndex.values().iterator()); | |
93 | } | |
94 | ||
95 | @Override | |
71e78f69 MK |
96 | public void addElement(T val) { |
97 | fLock.writeLock().lock(); | |
98 | try { | |
99 | if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) { | |
100 | fEndTimesIndex.put(Long.valueOf(val.getEnd()), val); | |
101 | fSize++; | |
102 | } | |
103 | } finally { | |
104 | fLock.writeLock().unlock(); | |
e5083481 | 105 | } |
26a6a7eb AM |
106 | } |
107 | ||
108 | @Override | |
109 | public long getNbElements() { | |
71e78f69 MK |
110 | fLock.readLock().lock(); |
111 | try { | |
112 | return fSize; | |
113 | } finally { | |
114 | fLock.readLock().unlock(); | |
115 | } | |
26a6a7eb AM |
116 | } |
117 | ||
26a6a7eb AM |
118 | @Override |
119 | public Iterable<T> getIntersectingElements(long position) { | |
120 | /* | |
121 | * The intervals intersecting 't' are those whose 1) start time is | |
122 | * *lower* than 't' AND 2) end time is *higher* than 't'. | |
123 | */ | |
71e78f69 MK |
124 | fLock.readLock().lock(); |
125 | try { | |
126 | Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values()); | |
127 | Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values()); | |
128 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); | |
129 | } finally { | |
130 | fLock.readLock().unlock(); | |
131 | } | |
26a6a7eb AM |
132 | } |
133 | ||
134 | @Override | |
135 | public Iterable<T> getIntersectingElements(long start, long end) { | |
71e78f69 MK |
136 | fLock.readLock().lock(); |
137 | try { | |
138 | Iterable<T> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values()); | |
139 | Iterable<T> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values()); | |
140 | return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); | |
141 | } finally { | |
142 | fLock.readLock().unlock(); | |
143 | } | |
26a6a7eb AM |
144 | } |
145 | ||
146 | @Override | |
71e78f69 MK |
147 | public void dispose() { |
148 | fLock.writeLock().lock(); | |
149 | try { | |
150 | fStartTimesIndex.clear(); | |
151 | fEndTimesIndex.clear(); | |
152 | fSize = 0; | |
153 | } finally { | |
154 | fLock.writeLock().unlock(); | |
155 | } | |
26a6a7eb | 156 | } |
26a6a7eb | 157 | } |