package org.opendaylight.controller.cluster.datastore.utils;
import com.google.common.annotations.Beta;
+import com.google.common.collect.ImmutableSortedSet;
import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
+import java.util.ArrayList;
+import java.util.NavigableSet;
import java.util.TreeSet;
import org.eclipse.jdt.annotation.NonNull;
import org.opendaylight.yangtools.concepts.Immutable;
@Beta
public final class ImmutableUnsignedLongSet extends UnsignedLongSet implements Immutable, WritableObject {
- private static final @NonNull ImmutableUnsignedLongSet EMPTY = new ImmutableUnsignedLongSet(new TreeSet<>());
+ // Do not all
+ private static final int ARRAY_MAX_ELEMENTS = 4096;
- private ImmutableUnsignedLongSet(final TreeSet<Entry> ranges) {
+ private static final @NonNull ImmutableUnsignedLongSet EMPTY =
+ new ImmutableUnsignedLongSet(ImmutableSortedSet.of());
+
+ private ImmutableUnsignedLongSet(final NavigableSet<Entry> ranges) {
super(ranges);
}
- static @NonNull ImmutableUnsignedLongSet of(final TreeSet<Entry> ranges) {
- return ranges.isEmpty() ? EMPTY : new ImmutableUnsignedLongSet(ranges);
+ static @NonNull ImmutableUnsignedLongSet copyOf(final MutableUnsignedLongSet mutable) {
+ if (mutable.isEmpty()) {
+ return of();
+ }
+ if (mutable.size() <= ARRAY_MAX_ELEMENTS) {
+ return new ImmutableUnsignedLongSet(ImmutableSortedSet.copyOfSorted(mutable.trustedRanges()));
+ }
+ return new ImmutableUnsignedLongSet(new TreeSet<>(mutable.trustedRanges()));
}
public static @NonNull ImmutableUnsignedLongSet of() {
return EMPTY;
}
- final var ranges = new TreeSet<Entry>();
- for (int i = 0; i < size; ++i) {
- ranges.add(Entry.readUnsigned(in));
+ final NavigableSet<Entry> ranges;
+ if (size <= ARRAY_MAX_ELEMENTS) {
+ final var entries = new ArrayList<Entry>(size);
+ for (int i = 0; i < size; ++i) {
+ entries.add(Entry.readUnsigned(in));
+ }
+ ranges = ImmutableSortedSet.copyOf(entries);
+ } else {
+ ranges = new TreeSet<>();
+ for (int i = 0; i < size; ++i) {
+ ranges.add(Entry.readUnsigned(in));
+ }
}
return new ImmutableUnsignedLongSet(ranges);
}
@Override
public ImmutableUnsignedLongSet immutableCopy() {
- return ImmutableUnsignedLongSet.of(copyRanges());
+ return ImmutableUnsignedLongSet.copyOf(this);
}
public void add(final long longBits) {
*/
package org.opendaylight.controller.cluster.datastore.utils;
-import static com.google.common.base.Verify.verify;
import static java.util.Objects.requireNonNull;
import com.google.common.annotations.Beta;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;
-import com.google.common.collect.BoundType;
import com.google.common.collect.Collections2;
import com.google.common.collect.Range;
import com.google.common.collect.RangeSet;
return new Entry(lowerBits, upperBits);
}
- static Entry of(final Range<UnsignedLong> range) {
- verify(range.lowerBoundType() == BoundType.CLOSED && range.upperBoundType() == BoundType.OPEN,
- "Unexpected range %s", range);
- return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1);
- }
-
@VisibleForTesting
public UnsignedLong lower() {
return UnsignedLong.fromLongBits(lowerBits);
}
}
- // The idea is rather simple, we track a TreeSet of range entries, ordered by their lower bound. This means that
- // for a contains() operation we just need the first headSet() entry. For insert operations we just update either
- // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they
- // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
- private final @NonNull TreeSet<Entry> ranges;
+ // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means
+ // that for a contains() operation we just need the first headSet() entry. For insert operations we just update
+ // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and
+ // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
+ private final @NonNull NavigableSet<Entry> ranges;
- UnsignedLongSet(final TreeSet<Entry> ranges) {
+ UnsignedLongSet(final NavigableSet<Entry> ranges) {
this.ranges = requireNonNull(ranges);
}
public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
public final @NonNull MutableUnsignedLongSet mutableCopy() {
- return new MutableUnsignedLongSet(copyRanges());
- }
-
- final @NonNull TreeSet<Entry> copyRanges() {
- return new TreeSet<>(Collections2.transform(ranges, Entry::copy));
+ return new MutableUnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy)));
}
public final @NonNull NavigableSet<Entry> ranges() {
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertNotSame;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertThrows;
import static org.junit.Assert.assertTrue;
+import static org.mockito.Mockito.mock;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.DataInputStream;
+import java.io.DataOutput;
import java.io.DataOutputStream;
import java.io.IOException;
import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.junit.MockitoJUnitRunner;
+@RunWith(MockitoJUnitRunner.StrictStubs.class)
public class UnsignedLongSetTest {
@Test
public void testOperations() {
set.add(3);
assertEquals("[[0..2), [3..5)]", set.toRangeSet().toString());
}
+
+ @Test
+ public void testEmptyCopy() {
+ final var orig = MutableUnsignedLongSet.of();
+ assertSame(ImmutableUnsignedLongSet.of(), orig.immutableCopy());
+ final var copy = orig.mutableCopy();
+ assertEquals(orig, copy);
+ assertNotSame(orig, copy);
+ }
+
+ @Test
+ public void testMutableCopy() {
+ final var orig = MutableUnsignedLongSet.of();
+ orig.add(-1);
+ assertEquals("MutableUnsignedLongSet{span=[18446744073709551615..18446744073709551615], size=1}",
+ orig.toString());
+
+ final var copy = orig.mutableCopy();
+ assertEquals(orig, copy);
+ assertNotSame(orig, copy);
+
+ orig.add(-2);
+ assertNotEquals(orig, copy);
+ assertEquals("MutableUnsignedLongSet{span=[18446744073709551614..18446744073709551615], size=1}",
+ orig.toString());
+ }
+
+ @Test
+ public void testWriteRangesTo() throws IOException {
+ ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 0);
+ }
+
+ @Test
+ public void testWriteRangesToViolation() {
+ final var ex = assertThrows(IOException.class,
+ () -> ImmutableUnsignedLongSet.of().writeRangesTo(mock(DataOutput.class), 1));
+ assertEquals("Mismatched size: expected 0, got 1", ex.getMessage());
+ }
}
Code Review / controller.git / commitdiff