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 com.google.common.base.Verify.verify;
  11 import static java.util.Objects.requireNonNull;
  12
  13 import com.google.common.annotations.Beta;
  14 import com.google.common.annotations.VisibleForTesting;
  15 import com.google.common.base.MoreObjects;
  16 import com.google.common.collect.BoundType;
  17 import com.google.common.collect.Collections2;
  18 import com.google.common.collect.Range;
  19 import com.google.common.collect.RangeSet;
  20 import com.google.common.primitives.UnsignedLong;
  21 import java.io.DataInput;
  22 import java.io.DataOutput;
  23 import java.io.IOException;
  24 import java.util.Collections;
  25 import java.util.Iterator;
  26 import java.util.NavigableSet;
  27 import java.util.TreeSet;
  28 import org.eclipse.jdt.annotation.NonNull;
  29 import org.opendaylight.yangtools.concepts.Mutable;
  30 import org.opendaylight.yangtools.concepts.WritableObjects;
  31
  32 /**
  33  * A class holding an equivalent of {@code Set<UnsignedLong>}. It is geared towards efficiently tracking ranges of
  34  * objects, similar to what a {@link RangeSet} would do.
  35  *
  36  * <p>
  37  * Unlike a {@code RangeSet}, though, this class takes advantage of knowing that an unsigned long is a discrete unit
  38  * and can be stored in a simple {@code long}.
  39  *
  40  * @author Robert Varga
  41  */
  42 abstract class UnsignedLongSet {
  43     @Beta
  44     @VisibleForTesting
  45     public static final class Entry implements Comparable<Entry>, Mutable {
  46         // Note: mutable to allow efficient merges.
  47         long lowerBits;
  48         long upperBits;
  49
  50         private Entry(final long lowerBits, final long upperBits) {
  51             this.lowerBits = lowerBits;
  52             this.upperBits = upperBits;
  53         }
  54
  55         static Entry of(final long longBits) {
  56             return of(longBits, longBits);
  57         }
  58
  59         static Entry of(final long lowerBits, final long upperBits) {
  60             return new Entry(lowerBits, upperBits);
  61         }
  62
  63         static Entry of(final Range<UnsignedLong> range) {
  64             verify(range.lowerBoundType() == BoundType.CLOSED && range.upperBoundType() == BoundType.OPEN,
  65                 "Unexpected range %s", range);
  66             return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1);
  67         }
  68
  69         @VisibleForTesting
  70         public UnsignedLong lower() {
  71             return UnsignedLong.fromLongBits(lowerBits);
  72         }
  73
  74         @VisibleForTesting
  75         public UnsignedLong upper() {
  76             return UnsignedLong.fromLongBits(upperBits);
  77         }
  78
  79         boolean contains(final long longBits) {
  80             return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0;
  81         }
  82
  83         Entry copy() {
  84             return new Entry(lowerBits, upperBits);
  85         }
  86
  87         // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
  88         Range<UnsignedLong> toUnsigned() {
  89             return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
  90         }
  91
  92         // These two methods provide the same serialization format as the one we've used to serialize
  93         // Range<UnsignedLong>
  94         static @NonNull Entry readUnsigned(final DataInput in) throws IOException {
  95             final byte hdr = WritableObjects.readLongHeader(in);
  96             final long first = WritableObjects.readFirstLong(in, hdr);
  97             final long second = WritableObjects.readSecondLong(in, hdr) - 1;
  98             if (Long.compareUnsigned(first, second) > 0) {
  99                 throw new IOException("Lower endpoint " + Long.toUnsignedString(first) + " is greater than upper "
 100                     + "endpoint " + Long.toUnsignedString(second));
 101             }
 102
 103             return new Entry(first, second);
 104         }
 105
 106         void writeUnsigned(final @NonNull DataOutput out) throws IOException {
 107             WritableObjects.writeLongs(out, lowerBits, upperBits + 1);
 108         }
 109
 110         @Override
 111         @SuppressWarnings("checkstyle:parameterName")
 112         public int compareTo(final Entry o) {
 113             return Long.compareUnsigned(lowerBits, o.lowerBits);
 114         }
 115
 116         @Override
 117         public int hashCode() {
 118             return Long.hashCode(lowerBits) * 31 + Long.hashCode(upperBits);
 119         }
 120
 121         @Override
 122         public boolean equals(final Object obj) {
 123             if (obj == this) {
 124                 return true;
 125             }
 126             if (!(obj instanceof Entry)) {
 127                 return false;
 128             }
 129             final var other = (Entry) obj;
 130             return lowerBits == other.lowerBits && upperBits == other.upperBits;
 131         }
 132
 133         @Override
 134         public String toString() {
 135             return "[" + Long.toUnsignedString(lowerBits) + ".." + Long.toUnsignedString(upperBits) + "]";
 136         }
 137     }
 138
 139     // The idea is rather simple, we track a TreeSet of range entries, ordered by their lower bound. This means that
 140     // for a contains() operation we just need the first headSet() entry. For insert operations we just update either
 141     // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they
 142     // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
 143     private final @NonNull TreeSet<Entry> ranges;
 144
 145     UnsignedLongSet(final TreeSet<Entry> ranges) {
 146         this.ranges = requireNonNull(ranges);
 147     }
 148
 149     final void addImpl(final long longBits) {
 150         final var range = Entry.of(longBits);
 151
 152         final var headIt = headIter(range);
 153         if (headIt.hasNext()) {
 154             final var head = headIt.next();
 155             if (head.contains(longBits)) {
 156                 return;
 157             }
 158             if (head.upperBits + 1 == longBits) {
 159                 head.upperBits = longBits;
 160                 final var tailSet = ranges.tailSet(range);
 161                 if (!tailSet.isEmpty()) {
 162                     final var tail = tailSet.first();
 163                     if (tail.lowerBits - 1 == longBits) {
 164                         tail.lowerBits = head.lowerBits;
 165                         headIt.remove();
 166                     }
 167                 }
 168                 return;
 169             }
 170         }
 171
 172         final var tailSet = ranges.tailSet(range);
 173         if (!tailSet.isEmpty()) {
 174             final var tail = tailSet.first();
 175             if (tail.lowerBits - 1 == longBits) {
 176                 tail.lowerBits = longBits;
 177                 return;
 178             }
 179         }
 180
 181         ranges.add(range);
 182     }
 183
 184     public final boolean contains(final long longBits) {
 185         final var headIt = headIter(Entry.of(longBits));
 186         return headIt.hasNext() && headIt.next().contains(longBits);
 187     }
 188
 189     public final boolean isEmpty() {
 190         return ranges.isEmpty();
 191     }
 192
 193     public final int size() {
 194         return ranges.size();
 195     }
 196
 197     public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
 198
 199     public final @NonNull MutableUnsignedLongSet mutableCopy() {
 200         return new MutableUnsignedLongSet(copyRanges());
 201     }
 202
 203     final @NonNull TreeSet<Entry> copyRanges() {
 204         return new TreeSet<>(Collections2.transform(ranges, Entry::copy));
 205     }
 206
 207     public final @NonNull NavigableSet<Entry> ranges() {
 208         return Collections.unmodifiableNavigableSet(ranges);
 209     }
 210
 211     final @NonNull NavigableSet<Entry> trustedRanges() {
 212         return ranges;
 213     }
 214
 215     @Override
 216     public final int hashCode() {
 217         return ranges.hashCode();
 218     }
 219
 220     @Override
 221     public final boolean equals(final Object obj) {
 222         return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges);
 223     }
 224
 225     @Override
 226     public final String toString() {
 227         final var helper = MoreObjects.toStringHelper(this);
 228
 229         final int size = ranges.size();
 230         switch (size) {
 231             case 0:
 232                 break;
 233             case 1:
 234                 helper.add("span", ranges.first());
 235                 break;
 236             default:
 237                 helper.add("span", Entry.of(ranges.first().lowerBits, ranges.last().upperBits));
 238         }
 239
 240         return helper.add("size", size).toString();
 241     }
 242
 243     private Iterator<Entry> headIter(final Entry range) {
 244         return ranges.headSet(range, true).descendingIterator();
 245     }
 246 }