opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/UnsignedLongSet.java

   1 /*
   2  * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others.  All rights reserved.
   3  *
   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
   7  */
   8 package org.opendaylight.controller.cluster.datastore.utils;
   9
  10 import static java.util.Objects.requireNonNull;
  11
  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.Range;
  16 import com.google.common.collect.RangeSet;
  17 import com.google.common.primitives.UnsignedLong;
  18 import java.io.DataInput;
  19 import java.io.DataOutput;
  20 import java.io.IOException;
  21 import java.util.Collections;
  22 import java.util.NavigableSet;
  23 import java.util.TreeSet;
  24 import org.eclipse.jdt.annotation.NonNull;
  25 import org.opendaylight.yangtools.concepts.Immutable;
  26 import org.opendaylight.yangtools.concepts.WritableObjects;
  27
  28 /**
  29  * A class holding an equivalent of {@code Set<UnsignedLong>}. It is geared towards efficiently tracking ranges of
  30  * objects, similar to what a {@link RangeSet} would do.
  31  *
  32  * <p>
  33  * Unlike a {@code RangeSet}, though, this class takes advantage of knowing that an unsigned long is a discrete unit
  34  * and can be stored in a simple {@code long}.
  35  *
  36  * @author Robert Varga
  37  */
  38 abstract class UnsignedLongSet {
  39     @Beta
  40     @VisibleForTesting
  41     public static final class Entry implements Comparable<Entry>, Immutable {
  42         final long lowerBits;
  43         final long upperBits;
  44
  45         private Entry(final long lowerBits, final long upperBits) {
  46             this.lowerBits = lowerBits;
  47             this.upperBits = upperBits;
  48         }
  49
  50         static @NonNull Entry of(final long longBits) {
  51             return of(longBits, longBits);
  52         }
  53
  54         static @NonNull Entry of(final long lowerBits, final long upperBits) {
  55             return new Entry(lowerBits, upperBits);
  56         }
  57
  58         @VisibleForTesting
  59         public @NonNull UnsignedLong lower() {
  60             return UnsignedLong.fromLongBits(lowerBits);
  61         }
  62
  63         @VisibleForTesting
  64         public @NonNull UnsignedLong upper() {
  65             return UnsignedLong.fromLongBits(upperBits);
  66         }
  67
  68         @NonNull Entry withLower(final long newLowerBits) {
  69             return of(newLowerBits, upperBits);
  70         }
  71
  72         @NonNull Entry withUpper(final long newUpperBits) {
  73             return of(lowerBits, newUpperBits);
  74         }
  75
  76         // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
  77         @NonNull Range<UnsignedLong> toUnsigned() {
  78             return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
  79         }
  80
  81         // These two methods provide the same serialization format as the one we've used to serialize
  82         // Range<UnsignedLong>
  83         static @NonNull Entry readUnsigned(final DataInput in) throws IOException {
  84             final byte hdr = WritableObjects.readLongHeader(in);
  85             final long first = WritableObjects.readFirstLong(in, hdr);
  86             final long second = WritableObjects.readSecondLong(in, hdr) - 1;
  87             if (Long.compareUnsigned(first, second) > 0) {
  88                 throw new IOException("Lower endpoint " + Long.toUnsignedString(first) + " is greater than upper "
  89                     + "endpoint " + Long.toUnsignedString(second));
  90             }
  91
  92             return new Entry(first, second);
  93         }
  94
  95         void writeUnsigned(final @NonNull DataOutput out) throws IOException {
  96             WritableObjects.writeLongs(out, lowerBits, upperBits + 1);
  97         }
  98
  99         @Override
 100         @SuppressWarnings("checkstyle:parameterName")
 101         public int compareTo(final Entry o) {
 102             return Long.compareUnsigned(lowerBits, o.lowerBits);
 103         }
 104
 105         @Override
 106         public int hashCode() {
 107             return Long.hashCode(lowerBits) * 31 + Long.hashCode(upperBits);
 108         }
 109
 110         @Override
 111         public boolean equals(final Object obj) {
 112             if (obj == this) {
 113                 return true;
 114             }
 115             if (!(obj instanceof Entry)) {
 116                 return false;
 117             }
 118             final var other = (Entry) obj;
 119             return lowerBits == other.lowerBits && upperBits == other.upperBits;
 120         }
 121
 122         @Override
 123         public String toString() {
 124             return "[" + Long.toUnsignedString(lowerBits) + ".." + Long.toUnsignedString(upperBits) + "]";
 125         }
 126     }
 127
 128     // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means
 129     // that for a contains() operation we just need the first headSet() entry. For insert operations we just update
 130     // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and
 131     // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
 132     private final @NonNull NavigableSet<Entry> ranges;
 133
 134     UnsignedLongSet(final NavigableSet<Entry> ranges) {
 135         this.ranges = requireNonNull(ranges);
 136     }
 137
 138     public final boolean contains(final long longBits) {
 139         final var head = ranges.floor(Entry.of(longBits));
 140         return head != null
 141             && Long.compareUnsigned(head.lowerBits, longBits) <= 0
 142             && Long.compareUnsigned(head.upperBits, longBits) >= 0;
 143     }
 144
 145     public final boolean isEmpty() {
 146         return ranges.isEmpty();
 147     }
 148
 149     public final int size() {
 150         return ranges.size();
 151     }
 152
 153     public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
 154
 155     public final @NonNull MutableUnsignedLongSet mutableCopy() {
 156         return new MutableUnsignedLongSet(new TreeSet<>(ranges));
 157     }
 158
 159     public final @NonNull NavigableSet<Entry> ranges() {
 160         return Collections.unmodifiableNavigableSet(ranges);
 161     }
 162
 163     final @NonNull NavigableSet<Entry> trustedRanges() {
 164         return ranges;
 165     }
 166
 167     @Override
 168     public final int hashCode() {
 169         return ranges.hashCode();
 170     }
 171
 172     @Override
 173     public final boolean equals(final Object obj) {
 174         return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges);
 175     }
 176
 177     @Override
 178     public final String toString() {
 179         final var helper = MoreObjects.toStringHelper(this);
 180
 181         final int size = ranges.size();
 182         switch (size) {
 183             case 0:
 184                 break;
 185             case 1:
 186                 helper.add("span", ranges.first());
 187                 break;
 188             default:
 189                 helper.add("span", Entry.of(ranges.first().lowerBits, ranges.last().upperBits));
 190         }
 191
 192         return helper.add("size", size).toString();
 193     }
 194 }