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