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