ss: Speed up TreeMapStore#add()
[deliverable/tracecompass.git] / statesystem / org.eclipse.tracecompass.segmentstore.core / src / org / eclipse / tracecompass / segmentstore / core / treemap / TreeMapStore.java
CommitLineData
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
13package org.eclipse.tracecompass.segmentstore.core.treemap;
14
15import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
16
1a9cb076 17import java.util.Collection;
26a6a7eb 18import java.util.Iterator;
26a6a7eb 19import java.util.TreeMap;
71e78f69
MK
20import java.util.concurrent.locks.ReadWriteLock;
21import java.util.concurrent.locks.ReentrantReadWriteLock;
26a6a7eb 22
4dafe201 23import org.eclipse.jdt.annotation.Nullable;
26a6a7eb
AM
24import org.eclipse.tracecompass.segmentstore.core.ISegment;
25import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
e5083481 26import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
26a6a7eb 27
4dafe201 28import com.google.common.collect.ImmutableList;
26a6a7eb 29import com.google.common.collect.Iterables;
e5083481 30import com.google.common.collect.Ordering;
26a6a7eb
AM
31import com.google.common.collect.Sets;
32import com.google.common.collect.TreeMultimap;
33
34/**
35 * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s.
36 * This relatively simple implementation holds everything in memory, and as such
37 * cannot contain too much data.
38 *
e5083481
PT
39 * The TreeMapStore itself is Iterable, and its iteration order will be by
40 * ascending order of start times. For segments with identical start times, the
41 * secondary comparator will be the end time. If even those are equal, it will
42 * defer to the segments' natural ordering ({@link ISegment#compareTo}).
43 *
44 * The store's tree maps will not accept duplicate key-value pairs, which means
45 * that if you want several segments with the same start and end times, make
46 * sure their compareTo() differentiates them.
47 *
1a9cb076
AM
48 * Removal operations are not supported.
49 *
50 * @param <E>
e5083481 51 * The type of segment held in this store
26a6a7eb
AM
52 *
53 * @author Alexandre Montplaisir
54 */
1a9cb076 55public class TreeMapStore<E extends ISegment> implements ISegmentStore<E> {
26a6a7eb 56
71e78f69
MK
57 private final ReadWriteLock fLock = new ReentrantReadWriteLock(false);
58
1a9cb076
AM
59 private final TreeMultimap<Long, E> fStartTimesIndex;
60 private final TreeMultimap<Long, E> fEndTimesIndex;
26a6a7eb 61
1a9cb076 62 private volatile long fSize;
26a6a7eb 63
1a9cb076 64 private @Nullable transient Iterable<E> fLastSnapshot = null;
4dafe201 65
26a6a7eb 66 /**
e5083481 67 * Constructor
26a6a7eb
AM
68 */
69 public TreeMapStore() {
e5083481
PT
70 /*
71 * For the start times index, the "key comparator" will compare the
72 * start times as longs directly. This is the primary comparator for its
73 * tree map.
74 *
75 * The secondary "value" comparator will check the end times first, and
76 * in the event of a tie, defer to the ISegment's Comparable
77 * implementation, a.k.a. its natural ordering.
78 *
79 * The same is done for the end times index, but swapping the first two
80 * comparators instead.
81 */
1a9cb076 82 fStartTimesIndex = checkNotNull(TreeMultimap.<Long, E> create(
e5083481
PT
83 SegmentComparators.LONG_COMPARATOR,
84 Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())));
85
1a9cb076 86 fEndTimesIndex = checkNotNull(TreeMultimap.<Long, E> create(
e5083481
PT
87 SegmentComparators.LONG_COMPARATOR,
88 Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())));
89
26a6a7eb
AM
90 fSize = 0;
91 }
92
1a9cb076
AM
93 // ------------------------------------------------------------------------
94 // Methods from Collection
95 // ------------------------------------------------------------------------
96
26a6a7eb 97 @Override
1a9cb076 98 public Iterator<E> iterator() {
4dafe201
MK
99 fLock.readLock().lock();
100 try {
1a9cb076 101 Iterable<E> lastSnapshot = fLastSnapshot;
4dafe201
MK
102 if (lastSnapshot == null) {
103 lastSnapshot = checkNotNull(ImmutableList.copyOf(fStartTimesIndex.values()));
104 fLastSnapshot = lastSnapshot;
105 }
106 return checkNotNull(lastSnapshot.iterator());
107 } finally {
108 fLock.readLock().unlock();
109 }
26a6a7eb
AM
110 }
111
112 @Override
1a9cb076
AM
113 public boolean add(@Nullable E val) {
114 if (val == null) {
115 throw new IllegalArgumentException();
116 }
117
71e78f69
MK
118 fLock.writeLock().lock();
119 try {
120 if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) {
121 fEndTimesIndex.put(Long.valueOf(val.getEnd()), val);
122 fSize++;
4dafe201 123 fLastSnapshot = null;
8b246d45 124 return true;
71e78f69 125 }
8b246d45 126 return false;
71e78f69
MK
127 } finally {
128 fLock.writeLock().unlock();
e5083481 129 }
1a9cb076
AM
130 }
131
132 @Override
133 public int size() {
134 return Long.valueOf(fSize).intValue();
135 }
136
137 @Override
138 public boolean isEmpty() {
139 return (fSize == 0);
26a6a7eb
AM
140 }
141
142 @Override
1a9cb076 143 public boolean contains(@Nullable Object o) {
71e78f69
MK
144 fLock.readLock().lock();
145 try {
1a9cb076 146 return fStartTimesIndex.containsValue(o);
71e78f69
MK
147 } finally {
148 fLock.readLock().unlock();
149 }
26a6a7eb
AM
150 }
151
1a9cb076
AM
152
153 @Override
154 public boolean containsAll(@Nullable Collection<?> c) {
155 fLock.readLock().lock();
156 try {
157 return fStartTimesIndex.values().containsAll(c);
158 } finally {
159 fLock.readLock().unlock();
160 }
161 }
162
163 @Override
164 public Object[] toArray() {
165 fLock.readLock().lock();
166 try {
167 return checkNotNull(fStartTimesIndex.values().toArray());
168 } finally {
169 fLock.readLock().unlock();
170 }
171 }
172
173 @Override
174 public <T> T[] toArray(@Nullable T[] a) {
175 fLock.readLock().lock();
176 try {
177 return checkNotNull(fStartTimesIndex.values().toArray(a));
178 } finally {
179 fLock.readLock().unlock();
180 }
181 }
182
183 @Override
184 public boolean remove(@Nullable Object o) {
185 throw new UnsupportedOperationException();
186 }
187
188 @Override
189 public boolean addAll(@Nullable Collection<? extends E> c) {
190 if (c == null) {
191 throw new IllegalArgumentException();
192 }
193
194 fLock.writeLock().lock();
195 try {
196 boolean changed = false;
197 for (E elem : c) {
198 if (this.add(elem)) {
199 changed = true;
200 }
201 }
202 return changed;
203 } finally {
204 fLock.writeLock().unlock();
205 }
206 }
207
208 @Override
209 public boolean removeAll(@Nullable Collection<?> c) {
210 throw new UnsupportedOperationException();
211 }
212
213 @Override
214 public boolean retainAll(@Nullable Collection<?> c) {
215 throw new UnsupportedOperationException();
216 }
217
218 @Override
219 public void clear() {
220 throw new UnsupportedOperationException();
221 }
222
223 // ------------------------------------------------------------------------
224 // Methods added by ISegmentStore
225 // ------------------------------------------------------------------------
226
26a6a7eb 227 @Override
1a9cb076 228 public Iterable<E> getIntersectingElements(long position) {
26a6a7eb
AM
229 /*
230 * The intervals intersecting 't' are those whose 1) start time is
231 * *lower* than 't' AND 2) end time is *higher* than 't'.
232 */
71e78f69
MK
233 fLock.readLock().lock();
234 try {
1a9cb076
AM
235 Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(position, true).values());
236 Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(position, true).values());
71e78f69
MK
237 return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
238 } finally {
239 fLock.readLock().unlock();
240 }
26a6a7eb
AM
241 }
242
243 @Override
1a9cb076 244 public Iterable<E> getIntersectingElements(long start, long end) {
71e78f69
MK
245 fLock.readLock().lock();
246 try {
1a9cb076
AM
247 Iterable<E> matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values());
248 Iterable<E> matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values());
71e78f69
MK
249 return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds)));
250 } finally {
251 fLock.readLock().unlock();
252 }
26a6a7eb
AM
253 }
254
255 @Override
71e78f69
MK
256 public void dispose() {
257 fLock.writeLock().lock();
258 try {
259 fStartTimesIndex.clear();
260 fEndTimesIndex.clear();
261 fSize = 0;
262 } finally {
263 fLock.writeLock().unlock();
264 }
26a6a7eb 265 }
26a6a7eb 266}
This page took 0.039596 seconds and 5 git commands to generate.