statesystem/org.eclipse.tracecompass.segmentstore.core.tests/src/org/eclipse/tracecompass/segmentstore/core/tests/AbstractTestSegmentStore.java

   1 /*******************************************************************************
   2  * Copyright (c) 2016 Ericsson
   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.segmentstore.core.tests;
  11
  12 import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
  13 import static org.junit.Assert.assertEquals;
  14 import static org.junit.Assert.assertFalse;
  15 import static org.junit.Assert.assertTrue;
  16
  17 import java.util.ArrayList;
  18 import java.util.Arrays;
  19 import java.util.Collection;
  20 import java.util.Collections;
  21 import java.util.Comparator;
  22 import java.util.Iterator;
  23 import java.util.LinkedList;
  24 import java.util.List;
  25
  26 import org.eclipse.jdt.annotation.NonNull;
  27 import org.eclipse.tracecompass.common.core.NonNullUtils;
  28 import org.eclipse.tracecompass.datastore.core.interval.IHTIntervalReader;
  29 import org.eclipse.tracecompass.datastore.core.serialization.ISafeByteBufferWriter;
  30 import org.eclipse.tracecompass.datastore.core.serialization.SafeByteBufferFactory;
  31 import org.eclipse.tracecompass.internal.provisional.segmentstore.core.ISegment2;
  32 import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
  33 import org.eclipse.tracecompass.segmentstore.core.ISegment;
  34 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
  35 import org.eclipse.tracecompass.segmentstore.core.SegmentComparators;
  36 import org.junit.After;
  37 import org.junit.Before;
  38 import org.junit.Test;
  39
  40 import com.google.common.collect.ImmutableList;
  41 import com.google.common.collect.Iterables;
  42 import com.google.common.collect.Lists;
  43
  44 /**
  45  * Unit tests for intersecting elements in an SegmentStore
  46  *
  47  * Originally the TreeMapStoreTest, copied for this internal implementation. The
  48  * test was barely changed as it tests the interface and not the internals.
  49  *
  50  * @author Matthew Khouzam
  51  */
  52 public abstract class AbstractTestSegmentStore {
  53
  54     /**
  55      * The segment store
  56      */
  57     protected final ISegmentStore<@NonNull TestSegment> fSegmentStore;
  58
  59     /**
  60      * Get the segment store to test
  61      *
  62      * @return the segment store
  63      */
  64     protected abstract ISegmentStore<@NonNull TestSegment> getSegmentStore();
  65
  66     /**
  67      * Get the segment store to test with initial data
  68      *
  69      * @param data
  70      *            the data
  71      *
  72      * @return the segment store
  73      */
  74     protected abstract ISegmentStore<@NonNull TestSegment> getSegmentStore(@NonNull TestSegment @NonNull [] data);
  75
  76     private static final @NonNull TestSegment SEGMENT_2_6 = new TestSegment(2, 6, "test");
  77     private static final @NonNull TestSegment SEGMENT_4_6 = new TestSegment(4, 6, "test2");
  78     private static final @NonNull TestSegment SEGMENT_4_8 = new TestSegment(4, 8, "test3");
  79     private static final @NonNull TestSegment SEGMENT_6_8 = new TestSegment(6, 8, "test");
  80     private static final @NonNull TestSegment SEGMENT_10_14 = new TestSegment(10, 14, "test");
  81     /**
  82      * A sample segment list
  83      */
  84     protected static final List<@NonNull TestSegment> SEGMENTS = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_6, SEGMENT_4_8, SEGMENT_6_8, SEGMENT_10_14);
  85     private static final List<@NonNull TestSegment> REVERSE_SEGMENTS = Lists.reverse(SEGMENTS);
  86
  87     /**
  88      * A test type of segment that can be serialized with the safe buffers. It
  89      * has an extra payload
  90      *
  91      * @author Geneviève Bastien
  92      */
  93     protected static final class TestSegment implements ISegment2 {
  94
  95         /**
  96          * The reader for this class
  97          */
  98         public static final @NonNull IHTIntervalReader<@NonNull TestSegment> DESERIALISER = buffer -> new TestSegment(buffer.getLong(), buffer.getLong(), buffer.getString());
  99
 100         /**
 101         *
 102         */
 103         private static final long serialVersionUID = -2242452053089575887L;
 104
 105         private final long fStart;
 106         private final long fEnd;
 107         private final @NonNull String fPayload;
 108
 109         /**
 110          * Constructor
 111          *
 112          * @param start
 113          *            Start of this segment
 114          * @param end
 115          *            End of this segment
 116          * @param payload
 117          *            Payload
 118          */
 119         public TestSegment(long start, long end, @NonNull String payload) {
 120             fStart = start;
 121             fEnd = end;
 122             fPayload = payload;
 123         }
 124
 125         @Override
 126         public long getStart() {
 127             return fStart;
 128         }
 129
 130         @Override
 131         public long getEnd() {
 132             return fEnd;
 133         }
 134
 135         /**
 136          * Get the payload of this segment
 137          *
 138          * @return The payload
 139          */
 140         public String getPayload() {
 141             return fPayload;
 142         }
 143
 144         @Override
 145         public int getSizeOnDisk() {
 146             return 2 * Long.BYTES + SafeByteBufferFactory.getStringSizeInBuffer(fPayload);
 147         }
 148
 149         @Override
 150         public void writeSegment(@NonNull ISafeByteBufferWriter buffer) {
 151             buffer.putLong(fStart);
 152             buffer.putLong(fEnd);
 153             buffer.putString(fPayload);
 154         }
 155
 156     }
 157
 158     /**
 159      * Constructor
 160      */
 161     public AbstractTestSegmentStore() {
 162         super();
 163         fSegmentStore = getSegmentStore();
 164     }
 165
 166     /**
 167      * Asserts that 2 segments are equal. Some backend may not return exactly
 168      * the same type of segment so the main assert will be false, but the
 169      * segments are in fact identical
 170      *
 171      * @param expected
 172      *            The expected segment
 173      * @param actual
 174      *            The actual segment
 175      */
 176     protected void assertSegmentsEqual(ISegment expected, ISegment actual) {
 177         assertEquals(expected, actual);
 178     }
 179
 180     /**
 181      * Initialize data (test vector) that will be tested
 182      */
 183     @Before
 184     public void setup() {
 185         for (TestSegment segment : SEGMENTS) {
 186             fSegmentStore.add(segment);
 187         }
 188     }
 189
 190     /**
 191      * Dispose of the segment store
 192      */
 193     @After
 194     public void teardown() {
 195         fSegmentStore.dispose();
 196     }
 197
 198     /**
 199      * Testing method size()
 200      */
 201     @Test
 202     public void testSize() {
 203         assertEquals(SEGMENTS.size(), fSegmentStore.size());
 204     }
 205
 206     /**
 207      * Testing isEmpty() method
 208      */
 209     @Test
 210     public void testIsEmpty() {
 211         assertFalse(fSegmentStore.isEmpty());
 212         fSegmentStore.clear();
 213         assertTrue(fSegmentStore.isEmpty());
 214     }
 215
 216     /**
 217      * Testing adding a collection with the addAll method
 218      */
 219     @Test
 220     public void testAddAll() {
 221         assertFalse(fSegmentStore.isEmpty());
 222         fSegmentStore.clear();
 223         assertTrue(fSegmentStore.isEmpty());
 224         fSegmentStore.addAll(SEGMENTS);
 225         assertTrue(fSegmentStore.containsAll(SEGMENTS));
 226     }
 227
 228     /**
 229      * Testing "copy" constructor
 230      */
 231     @Test
 232     public void testAddAllConstructor() {
 233         ISegmentStore<@NonNull TestSegment> other = getSegmentStore(fSegmentStore.toArray(new TestSegment[fSegmentStore.size()]));
 234         assertTrue(fSegmentStore.containsAll(other));
 235         assertTrue(other.containsAll(fSegmentStore));
 236     }
 237
 238     /**
 239      * Testing "copy" constructor out of order
 240      */
 241     @Test
 242     public void testAddAllConstructorOutOfOrder() {
 243         ISegmentStore<@NonNull TestSegment> other = getSegmentStore(REVERSE_SEGMENTS.toArray(new TestSegment[fSegmentStore.size()]));
 244         assertTrue(fSegmentStore.containsAll(other));
 245         assertTrue(other.containsAll(fSegmentStore));
 246     }
 247
 248     /**
 249      * Testing adding an out of order collection with the addAll method
 250      */
 251     @Test
 252     public void testAddAllOutOfOrder() {
 253         assertFalse(fSegmentStore.isEmpty());
 254         fSegmentStore.clear();
 255         assertTrue(fSegmentStore.isEmpty());
 256         fSegmentStore.addAll(REVERSE_SEGMENTS);
 257         assertTrue(fSegmentStore.containsAll(SEGMENTS));
 258     }
 259
 260     /**
 261      * Test the contains() method.
 262      */
 263     @Test
 264     public void testContains() {
 265         ISegment otherSegment = new BasicSegment(0, 20);
 266
 267         assertTrue(fSegmentStore.contains(SEGMENT_2_6));
 268         assertTrue(fSegmentStore.contains(SEGMENT_4_8));
 269         assertFalse(fSegmentStore.contains(otherSegment));
 270     }
 271
 272     /**
 273      * Test containsAll() method
 274      */
 275     public void testContainsAll() {
 276         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 277
 278         store.add(SEGMENT_2_6);
 279         assertTrue(store.containsAll(Collections.emptyList()));
 280         assertTrue(store.containsAll(Collections.singleton(SEGMENT_2_6)));
 281         assertFalse(store.containsAll(Collections.singleton(SEGMENT_4_6)));
 282     }
 283
 284     /**
 285      * Test the toArray() method.
 286      */
 287     @Test
 288     public void testToObjectArray() {
 289         Object[] array = fSegmentStore.toArray();
 290
 291         assertEquals(SEGMENTS.size(), array.length);
 292         assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
 293     }
 294
 295     /**
 296      * Test the toArray(T[]) method.
 297      */
 298     @Test
 299     public void testToSpecificArray() {
 300         ISegment[] array = fSegmentStore.toArray(new ISegment[0]);
 301
 302         assertEquals(SEGMENTS.size(), array.length);
 303         assertTrue(Arrays.asList(array).containsAll(SEGMENTS));
 304     }
 305
 306     /**
 307      * Test the toArray(T[]) method with a subtype of ISegment.
 308      */
 309     @Test
 310     public void testToSpecifyArraySubtype() {
 311         ISegmentStore<@NonNull TestSegment> tms2 = getSegmentStore();
 312         TestSegment otherSegment = new TestSegment(2, 6, "test");
 313         tms2.add(otherSegment);
 314         TestSegment[] array = tms2.toArray(new TestSegment[0]);
 315
 316         assertEquals(1, array.length);
 317         assertTrue(Arrays.asList(array).contains(otherSegment));
 318
 319         tms2.dispose();
 320     }
 321
 322     /**
 323      * Test the iteration order of the complete segment store.
 324      */
 325     @Test
 326     public void testIterationOrder() {
 327         int i = 0;
 328         for (ISegment segment : fSegmentStore) {
 329             assertSegmentsEqual(SEGMENTS.get(i++), segment);
 330         }
 331     }
 332
 333     /**
 334      * Test the iteration order when the elements are not inserted in sorted
 335      * order.
 336      */
 337     @Test
 338     public void testIterationOrderNonSortedInsertion() {
 339         /* Prepare the segment store, we don't use the 'fixture' in this test */
 340         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 341         for (TestSegment segment : REVERSE_SEGMENTS) {
 342             store.add(checkNotNull(segment));
 343         }
 344
 345         /*
 346          * Test each element one by one, the iteration order should follow the
 347          * start times, not the insertion order.
 348          */
 349         int i = 0;
 350         for (TestSegment segment : store) {
 351             assertSegmentsEqual(SEGMENTS.get(i++), segment);
 352         }
 353
 354         /* Manually dispose our own store */
 355         store.dispose();
 356     }
 357
 358     /**
 359      * Testing method
 360      * {@link ISegmentStore#getIntersectingElements(long start, long end)}
 361      */
 362     @Test
 363     public void testGetIntersectingElementsRange() {
 364
 365         Iterable<TestSegment> intersectingElements;
 366
 367         /*
 368          * Range that does not include any segment
 369          */
 370         intersectingElements = fSegmentStore.getIntersectingElements(16, 20);
 371         assertEquals(0, Iterables.size(intersectingElements));
 372
 373         /*
 374          * Range start time : Before first segment start time Range end time :
 375          * After last segment end time
 376          */
 377         intersectingElements = fSegmentStore.getIntersectingElements(1, 15);
 378         assertEquals(5, Iterables.size(intersectingElements));
 379
 380         /*
 381          * Range start time : On first segment start time Range end time : On
 382          * last segment end time
 383          */
 384         intersectingElements = fSegmentStore.getIntersectingElements(2, 14);
 385         assertEquals(5, Iterables.size(intersectingElements));
 386
 387         /*
 388          * Range start time : After one segment start time Range end time :
 389          * Before one segment end time
 390          */
 391         intersectingElements = fSegmentStore.getIntersectingElements(11, 13);
 392         assertEquals(1, Iterables.size(intersectingElements));
 393         assertSegmentsEqual(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 394
 395         /*
 396          * Range start time : On one segment start time Range end time : On one
 397          * segment end time
 398          */
 399         intersectingElements = fSegmentStore.getIntersectingElements(10, 14);
 400         assertEquals(1, Iterables.size(intersectingElements));
 401         assertSegmentsEqual(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 402
 403         /*
 404          * Range start time : On last segment end time Range end time : After
 405          * last segment end time
 406          */
 407         intersectingElements = fSegmentStore.getIntersectingElements(14, 18);
 408         assertEquals(1, Iterables.size(intersectingElements));
 409         assertSegmentsEqual(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 410
 411         /*
 412          * Range start time : Before first segment start time Range end time :
 413          * On first segment start time
 414          */
 415         intersectingElements = fSegmentStore.getIntersectingElements(1, 2);
 416         assertEquals(1, Iterables.size(intersectingElements));
 417         assertSegmentsEqual(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
 418     }
 419
 420     /**
 421      * Testing method {@link ISegmentStore#getIntersectingElements(long time)}
 422      */
 423     @Test
 424     public void testGetIntersectingElementsTime() {
 425
 426         Iterable<TestSegment> intersectingElements;
 427
 428         /*
 429          * Time between segment start time and end time
 430          */
 431         intersectingElements = fSegmentStore.getIntersectingElements(3);
 432         assertEquals(1, Iterables.size(intersectingElements));
 433         assertSegmentsEqual(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
 434
 435         /*
 436          * Time on segment start time
 437          */
 438         intersectingElements = fSegmentStore.getIntersectingElements(2);
 439         assertEquals(1, Iterables.size(intersectingElements));
 440         assertSegmentsEqual(SEGMENT_2_6, Iterables.getOnlyElement(intersectingElements));
 441
 442         /*
 443          * Time on segment end time
 444          */
 445         intersectingElements = fSegmentStore.getIntersectingElements(14);
 446         assertEquals(1, Iterables.size(intersectingElements));
 447         assertSegmentsEqual(SEGMENT_10_14, Iterables.getOnlyElement(intersectingElements));
 448
 449         /*
 450          * Time overlapping many segments
 451          */
 452         intersectingElements = fSegmentStore.getIntersectingElements(6);
 453         assertEquals(4, Iterables.size(intersectingElements));
 454
 455         /*
 456          * Time between segments
 457          */
 458         intersectingElements = fSegmentStore.getIntersectingElements(9);
 459         assertEquals(0, Iterables.size(intersectingElements));
 460
 461         /*
 462          * Time before all segment start time
 463          */
 464         intersectingElements = fSegmentStore.getIntersectingElements(1);
 465         assertEquals(0, Iterables.size(intersectingElements));
 466
 467         /*
 468          * Time after all segment end time
 469          */
 470         intersectingElements = fSegmentStore.getIntersectingElements(15);
 471         assertEquals(0, Iterables.size(intersectingElements));
 472     }
 473
 474     /**
 475      * Testing method {@link ISegmentStore#dispose()}
 476      */
 477     @Test
 478     public void testDispose() {
 479         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 480         store.add(SEGMENT_2_6);
 481         store.dispose();
 482         assertEquals(0, store.size());
 483     }
 484
 485     /**
 486      * Test iterating over a store being built.
 487      *
 488      * bug 500607
 489      */
 490     @Test
 491     public void testIterator() {
 492         Collection<@NonNull TestSegment> beforeExpected = ImmutableList.of(SEGMENT_2_6);
 493         Collection<@NonNull TestSegment> afterExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8);
 494         Collection<@NonNull TestSegment> lastExpected = ImmutableList.of(SEGMENT_2_6, SEGMENT_4_8, SEGMENT_6_8);
 495         Collection<@NonNull TestSegment> fixture = new ArrayList<>();
 496         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 497
 498         // Add one segment to the segment store and iterate
 499         store.add(SEGMENT_2_6);
 500         for (TestSegment item : store) {
 501             fixture.add(item);
 502         }
 503         assertEquals(beforeExpected, fixture);
 504
 505         // Add a second segment to the store and iterate
 506         fixture.clear();
 507         store.add(SEGMENT_4_8);
 508         for (TestSegment item : store) {
 509             fixture.add(item);
 510         }
 511         assertEquals(afterExpected, fixture);
 512
 513         fixture.clear();
 514         // Take an iterator
 515         Iterator<@NonNull TestSegment> iter = store.iterator();
 516
 517         // Add a third segment to the store and iterate
 518         store.add(SEGMENT_6_8);
 519         Iterator<@NonNull TestSegment> iter2 = store.iterator();
 520         fixture.clear();
 521
 522         // Make sure the first iterator take has at least 2 elements (depends on
 523         // implementation) and the second has 3 elements
 524         while (iter.hasNext()) {
 525             fixture.add(iter.next());
 526         }
 527         assertTrue(fixture.size() >= 2);
 528         fixture.clear();
 529         while (iter2.hasNext()) {
 530             fixture.add(iter2.next());
 531         }
 532         assertEquals(lastExpected, fixture);
 533     }
 534
 535     /**
 536      * Test to check ordered iterators
 537      */
 538     @Test
 539     public void testSortedIterator() {
 540         List<@NonNull Comparator<ISegment>> comparators = new LinkedList<>();
 541         comparators.add(SegmentComparators.INTERVAL_END_COMPARATOR);
 542         comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_END_COMPARATOR.reversed()));
 543         comparators.add(SegmentComparators.INTERVAL_START_COMPARATOR);
 544         comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_START_COMPARATOR.reversed()));
 545         comparators.add(SegmentComparators.INTERVAL_LENGTH_COMPARATOR);
 546         comparators.add(NonNullUtils.checkNotNull(SegmentComparators.INTERVAL_LENGTH_COMPARATOR.reversed()));
 547
 548         Iterable<TestSegment> iterable;
 549         for (Comparator<ISegment> comparator : comparators) {
 550             iterable = fSegmentStore.iterator(comparator);
 551             verifySortedIterable(iterable, 5, comparator);
 552             iterable = fSegmentStore.getIntersectingElements(5, comparator);
 553             verifySortedIterable(iterable, 3, comparator);
 554             iterable = fSegmentStore.getIntersectingElements(7, 14, comparator);
 555             verifySortedIterable(iterable, 3, comparator);
 556         }
 557     }
 558
 559     private static void verifySortedIterable(Iterable<TestSegment> iterable, int expectedSize, Comparator<ISegment> comparator) {
 560         // check its size
 561         assertEquals(expectedSize, Iterables.size(iterable));
 562         Iterator<TestSegment> iterator = iterable.iterator();
 563         // check the order
 564         ISegment prev, current = iterator.next();
 565         while (iterator.hasNext()) {
 566             prev = current;
 567             current = iterator.next();
 568             assertTrue(comparator.compare(prev, current) <= 0);
 569         }
 570     }
 571
 572     /**
 573      * Test retainAll() contract
 574      */
 575     @Test(expected = UnsupportedOperationException.class)
 576     public void testRetainAll() {
 577         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 578
 579         store.add(SEGMENT_2_6);
 580         store.retainAll(Collections.emptyList());
 581     }
 582
 583     /**
 584      * Test remove() contract
 585      */
 586     @Test(expected = UnsupportedOperationException.class)
 587     public void testRemove() {
 588         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 589
 590         store.add(SEGMENT_2_6);
 591         store.remove(SEGMENT_2_6);
 592     }
 593
 594     /**
 595      * Test removeAll() contract
 596      */
 597     @Test(expected = UnsupportedOperationException.class)
 598     public void testRemoveAll() {
 599         ISegmentStore<@NonNull TestSegment> store = getSegmentStore();
 600
 601         store.add(SEGMENT_2_6);
 602         store.removeAll(Collections.emptyList());
 603     }
 604 }