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 com.google.common.base.Verify.verify;
  11 import static java.util.Objects.requireNonNull;
  12
  13 import com.google.common.annotations.Beta;
  14 import com.google.common.base.MoreObjects;
  15 import com.google.common.collect.BoundType;
  16 import com.google.common.collect.Collections2;
  17 import com.google.common.collect.ImmutableRangeSet;
  18 import com.google.common.collect.Range;
  19 import com.google.common.collect.RangeSet;
  20 import com.google.common.primitives.UnsignedLong;
  21 import java.util.Iterator;
  22 import java.util.TreeSet;
  23 import org.eclipse.jdt.annotation.NonNull;
  24 import org.opendaylight.yangtools.concepts.Mutable;
  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 @Beta
  37 public final class UnsignedLongSet implements Mutable {
  38     private static final class Entry implements Comparable<Entry>, Mutable {
  39         // Note: mutable to allow efficient merges.
  40         long lowerBits;
  41         long upperBits;
  42
  43         private Entry(final long lowerBits, final long upperBits) {
  44             this.lowerBits = lowerBits;
  45             this.upperBits = upperBits;
  46         }
  47
  48         static Entry of(final long longBits) {
  49             return of(longBits, longBits);
  50         }
  51
  52         static Entry of(final long lowerBits, final long upperBits) {
  53             return new Entry(lowerBits, upperBits);
  54         }
  55
  56         static Entry of(final Range<UnsignedLong> range) {
  57             verify(range.lowerBoundType() == BoundType.CLOSED && range.upperBoundType() == BoundType.OPEN,
  58                 "Unexpected range %s", range);
  59             return of(range.lowerEndpoint().longValue(), range.upperEndpoint().longValue() - 1);
  60         }
  61
  62         boolean contains(final long longBits) {
  63             return Long.compareUnsigned(lowerBits, longBits) <= 0 && Long.compareUnsigned(upperBits, longBits) >= 0;
  64         }
  65
  66         Entry copy() {
  67             return new Entry(lowerBits, upperBits);
  68         }
  69
  70         // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
  71         Range<UnsignedLong> toUnsigned() {
  72             return Range.closedOpen(UnsignedLong.fromLongBits(lowerBits), UnsignedLong.fromLongBits(upperBits + 1));
  73         }
  74
  75         @Override
  76         @SuppressWarnings("checkstyle:parameterName")
  77         public int compareTo(final Entry o) {
  78             return Long.compareUnsigned(lowerBits, o.lowerBits);
  79         }
  80
  81         @Override
  82         public int hashCode() {
  83             return Long.hashCode(lowerBits) * 31 + Long.hashCode(upperBits);
  84         }
  85
  86         @Override
  87         public boolean equals(final Object obj) {
  88             if (obj == this) {
  89                 return true;
  90             }
  91             if (!(obj instanceof Entry)) {
  92                 return false;
  93             }
  94             final var other = (Entry) obj;
  95             return lowerBits == other.lowerBits && upperBits == other.upperBits;
  96         }
  97
  98         @Override
  99         public String toString() {
 100             return "[" + Long.toUnsignedString(lowerBits) + ".." + Long.toUnsignedString(upperBits) + "]";
 101         }
 102     }
 103
 104     // The idea is rather simple, we track a TreeSet of range entries, ordered by their lower bound. This means that
 105     // for a contains() operation we just need the first headSet() entry. For insert operations we just update either
 106     // the lower bound or the upper bound of an existing entry. When we do, we also look at prev/next entry and if they
 107     // are contiguous with the updated entry, we adjust the entry once more and remove the prev/next entry.
 108     private final TreeSet<Entry> ranges;
 109
 110     private UnsignedLongSet(final TreeSet<Entry> ranges) {
 111         this.ranges = requireNonNull(ranges);
 112     }
 113
 114     private UnsignedLongSet(final RangeSet<UnsignedLong> rangeSet) {
 115         ranges = new TreeSet<>();
 116         for (var range : rangeSet.asRanges()) {
 117             ranges.add(Entry.of(range));
 118         }
 119     }
 120
 121     public static @NonNull UnsignedLongSet of() {
 122         return new UnsignedLongSet(new TreeSet<>());
 123     }
 124
 125     public static @NonNull UnsignedLongSet of(final RangeSet<UnsignedLong> rangeSet) {
 126         return new UnsignedLongSet(rangeSet);
 127     }
 128
 129     public void add(final long longBits) {
 130         final var range = Entry.of(longBits);
 131
 132         final var headIt = headIter(range);
 133         if (headIt.hasNext()) {
 134             final var head = headIt.next();
 135             if (head.contains(longBits)) {
 136                 return;
 137             }
 138             if (head.upperBits + 1 == longBits) {
 139                 head.upperBits = longBits;
 140                 final var tailSet = ranges.tailSet(range);
 141                 if (!tailSet.isEmpty()) {
 142                     final var tail = tailSet.first();
 143                     if (tail.lowerBits - 1 == longBits) {
 144                         tail.lowerBits = head.lowerBits;
 145                         headIt.remove();
 146                     }
 147                 }
 148                 return;
 149             }
 150         }
 151
 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 = longBits;
 157                 return;
 158             }
 159         }
 160
 161         ranges.add(range);
 162     }
 163
 164     public boolean contains(final long longBits) {
 165         final var headIt = headIter(Entry.of(longBits));
 166         return headIt.hasNext() && headIt.next().contains(longBits);
 167     }
 168
 169     public UnsignedLongSet copy() {
 170         return new UnsignedLongSet(new TreeSet<>(Collections2.transform(ranges, Entry::copy)));
 171     }
 172
 173     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
 174         return ImmutableRangeSet.copyOf(Collections2.transform(ranges, Entry::toUnsigned));
 175     }
 176
 177     @Override
 178     public int hashCode() {
 179         return ranges.hashCode();
 180     }
 181
 182     @Override
 183     public boolean equals(final Object obj) {
 184         return obj == this || obj instanceof UnsignedLongSet && ranges.equals(((UnsignedLongSet) obj).ranges);
 185     }
 186
 187     @Override
 188     public String toString() {
 189         final var helper = MoreObjects.toStringHelper(this);
 190
 191         final int size = ranges.size();
 192         switch (size) {
 193             case 0:
 194                 break;
 195             case 1:
 196                 helper.add("span", ranges.first());
 197                 break;
 198             default:
 199                 helper.add("span", Entry.of(ranges.first().lowerBits, ranges.last().upperBits));
 200         }
 201
 202         return helper.add("size", size).toString();
 203     }
 204
 205     private Iterator<Entry> headIter(final Entry range) {
 206         return ranges.headSet(range, true).descendingIterator();
 207     }
 208 }