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