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.Collection;
  23 import java.util.Collections;
  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         Entry copy() {
  72             return new Entry(lowerBits, upperBits);
  73         }
  74
  75         // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
  76         Range<UnsignedLong> toUnsigned() {
  77             return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
  78         }
  79
  80         // These two methods provide the same serialization format as the one we've used to serialize
  81         // Range<UnsignedLong>
  82         static @NonNull Entry readUnsigned(final DataInput in) throws IOException {
  83             final byte hdr = WritableObjects.readLongHeader(in);
  84             final long first = WritableObjects.readFirstLong(in, hdr);
  85             final long second = WritableObjects.readSecondLong(in, hdr) - 1;
  86             if (Long.compareUnsigned(first, second) > 0) {
  87                 throw new IOException("Lower endpoint " + Long.toUnsignedString(first) + " is greater than upper "
  88                     + "endpoint " + Long.toUnsignedString(second));
  89             }
  90
  91             return new Entry(first, second);
  92         }
  93
  94         void writeUnsigned(final @NonNull DataOutput out) throws IOException {
  95             WritableObjects.writeLongs(out, lowerBits, upperBits + 1);
  96         }
  97
  98         @Override
  99         @SuppressWarnings("checkstyle:parameterName")
 100         public int compareTo(final Entry o) {
 101             return Long.compareUnsigned(lowerBits, o.lowerBits);
 102         }
 103
 104         @Override
 105         public int hashCode() {
 106             return Long.hashCode(lowerBits) * 31 + Long.hashCode(upperBits);
 107         }
 108
 109         @Override
 110         public boolean equals(final Object obj) {
 111             if (obj == this) {
 112                 return true;
 113             }
 114             if (!(obj instanceof Entry)) {
 115                 return false;
 116             }
 117             final var other = (Entry) obj;
 118             return lowerBits == other.lowerBits && upperBits == other.upperBits;
 119         }
 120
 121         @Override
 122         public String toString() {
 123             return "[" + Long.toUnsignedString(lowerBits) + ".." + Long.toUnsignedString(upperBits) + "]";
 124         }
 125     }
 126
 127     // The idea is rather simple, we track a NavigableSet of range entries, ordered by their lower bound. This means
 128     // that for a contains() operation we just need the first headSet() entry. For insert operations we just update
 129     // either the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and
 130     // if they are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
 131     private final @NonNull NavigableSet<Entry> ranges;
 132
 133     UnsignedLongSet(final NavigableSet<Entry> ranges) {
 134         this.ranges = requireNonNull(ranges);
 135     }
 136
 137     public final boolean contains(final long longBits) {
 138         final var head = ranges.floor(Entry.of(longBits));
 139         return head != null
 140             && Long.compareUnsigned(head.lowerBits, longBits) <= 0
 141             && Long.compareUnsigned(head.upperBits, longBits) >= 0;
 142     }
 143
 144     public final boolean isEmpty() {
 145         return ranges.isEmpty();
 146     }
 147
 148     public final int size() {
 149         return ranges.size();
 150     }
 151
 152     public abstract @NonNull ImmutableUnsignedLongSet immutableCopy();
 153
 154     public final @NonNull MutableUnsignedLongSet mutableCopy() {
 155         return new MutableUnsignedLongSet(new TreeSet<>(copiedRanges()));
 156     }
 157
 158     public final @NonNull NavigableSet<Entry> ranges() {
 159         return Collections.unmodifiableNavigableSet(ranges);
 160     }
 161
 162     final @NonNull NavigableSet<Entry> trustedRanges() {
 163         return ranges;
 164     }
 165
 166     final @NonNull Collection<Entry> copiedRanges() {
 167         return Collections2.transform(ranges, Entry::copy);
 168     }
 169
 170     @Override
 171     public final int hashCode() {
 172         return ranges.hashCode();
 173     }
 174
 175     @Override
 176     public final boolean equals(final Object obj) {
 177         return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges);
 178     }
 179
 180     @Override
 181     public final String toString() {
 182         final var helper = MoreObjects.toStringHelper(this);
 183
 184         final int size = ranges.size();
 185         switch (size) {
 186             case 0:
 187                 break;
 188             case 1:
 189                 helper.add("span", ranges.first());
 190                 break;
 191             default:
 192                 helper.add("span", Entry.of(ranges.first().lowerBits, ranges.last().upperBits));
 193         }
 194
 195         return helper.add("size", size).toString();
 196     }
 197 }