2 * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved.
4 * This program and the accompanying materials are made available under the
5 * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6 * and is available at http://www.eclipse.org/legal/epl-v10.html
8 package org.opendaylight.controller.cluster.datastore.utils;
10 import static java.util.Objects.requireNonNull;
12 import com.google.common.annotations.Beta;
13 import com.google.common.annotations.VisibleForTesting;
14 import com.google.common.base.MoreObjects;
15 import com.google.common.collect.RangeSet;
16 import java.io.DataInput;
17 import java.io.DataOutput;
18 import java.io.IOException;
19 import java.util.Collections;
20 import java.util.NavigableSet;
21 import java.util.TreeSet;
22 import org.eclipse.jdt.annotation.NonNull;
23 import org.opendaylight.yangtools.concepts.Immutable;
24 import org.opendaylight.yangtools.concepts.WritableObjects;
27 * A class holding an equivalent of {@code Set<UnsignedLong>}. It is geared towards efficiently tracking ranges of
28 * objects, similar to what a {@link RangeSet} would do.
31 * Unlike a {@code RangeSet}, though, this class takes advantage of knowing that an unsigned long is a discrete unit
32 * and can be stored in a simple {@code long}.
34 * @author Robert Varga
36 abstract class UnsignedLongSet {
39 public static final class Entry implements Comparable<Entry>, Immutable {
40 public final long lowerBits;
41 public final long upperBits;
43 private Entry(final long lowerBits, final long upperBits) {
44 this.lowerBits = lowerBits;
45 this.upperBits = upperBits;
48 static @NonNull Entry of(final long longBits) {
49 return of(longBits, longBits);
52 static @NonNull Entry of(final long lowerBits, final long upperBits) {
53 return new Entry(lowerBits, upperBits);
56 @NonNull Entry withLower(final long newLowerBits) {
57 return of(newLowerBits, upperBits);
60 @NonNull Entry withUpper(final long newUpperBits) {
61 return of(lowerBits, newUpperBits);
64 // These two methods provide the same serialization format as the one we've used to serialize
65 // Range<UnsignedLong>
66 static @NonNull Entry readUnsigned(final DataInput in) throws IOException {
67 final byte hdr = WritableObjects.readLongHeader(in);
68 final long first = WritableObjects.readFirstLong(in, hdr);
69 final long second = WritableObjects.readSecondLong(in, hdr) - 1;
70 if (Long.compareUnsigned(first, second) > 0) {
71 throw new IOException("Lower endpoint " + Long.toUnsignedString(first) + " is greater than upper "
72 + "endpoint " + Long.toUnsignedString(second));
75 return new Entry(first, second);
78 void writeUnsigned(final @NonNull DataOutput out) throws IOException {
79 WritableObjects.writeLongs(out, lowerBits, upperBits + 1);
83 @SuppressWarnings("checkstyle:parameterName")
84 public int compareTo(final Entry o) {
85 return Long.compareUnsigned(lowerBits, o.lowerBits);
89 public int hashCode() {
90 return Long.hashCode(lowerBits) * 31 + Long.hashCode(upperBits);
94 public boolean equals(final Object obj) {
98 if (!(obj instanceof Entry)) {
101 final var other = (Entry) obj;
102 return lowerBits == other.lowerBits && upperBits == other.upperBits;
106 public String toString() {
107 return "[" + Long.toUnsignedString(lowerBits) + ".." + Long.toUnsignedString(upperBits) + "]";
111 // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means
112 // that for a contains() operation we just need the first headSet() entry. For insert operations we just update
113 // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and
114 // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
115 private final @NonNull NavigableSet<Entry> ranges;
117 UnsignedLongSet(final NavigableSet<Entry> ranges) {
118 this.ranges = requireNonNull(ranges);
121 public final boolean contains(final long longBits) {
122 final var head = ranges.floor(Entry.of(longBits));
124 && Long.compareUnsigned(head.lowerBits, longBits) <= 0
125 && Long.compareUnsigned(head.upperBits, longBits) >= 0;
128 public final boolean isEmpty() {
129 return ranges.isEmpty();
132 public final int rangeSize() {
133 return ranges.size();
136 public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
138 public final @NonNull MutableUnsignedLongSet mutableCopy() {
139 return new MutableUnsignedLongSet(new TreeSet<>(ranges));
142 public final @NonNull NavigableSet<Entry> ranges() {
143 return Collections.unmodifiableNavigableSet(ranges);
146 final @NonNull NavigableSet<Entry> trustedRanges() {
151 public final int hashCode() {
152 return ranges.hashCode();
156 public final boolean equals(final Object obj) {
157 return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges);
161 public final String toString() {
162 final var helper = MoreObjects.toStringHelper(this);
164 final int size = ranges.size();
169 helper.add("span", ranges.first());
172 helper.add("span", Entry.of(ranges.first().lowerBits, ranges.last().upperBits));
175 return helper.add("size", size).toString();