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