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