opendaylight/md-sal/sal-distributed-datastore/src/main/java/org/opendaylight/controller/cluster/datastore/utils/MutableUnsignedLongSet.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 com.google.common.annotations.Beta;
  11 import com.google.common.collect.Collections2;
  12 import com.google.common.collect.ImmutableRangeSet;
  13 import com.google.common.collect.Range;
  14 import com.google.common.primitives.UnsignedLong;
  15 import java.util.NavigableSet;
  16 import java.util.TreeSet;
  17 import org.eclipse.jdt.annotation.NonNull;
  18 import org.opendaylight.yangtools.concepts.Mutable;
  19
  20 @Beta
  21 public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mutable {
  22     MutableUnsignedLongSet(final TreeSet<Entry> ranges) {
  23         super(ranges);
  24     }
  25
  26     public static @NonNull MutableUnsignedLongSet of() {
  27         return new MutableUnsignedLongSet(new TreeSet<>());
  28     }
  29
  30     public static @NonNull MutableUnsignedLongSet of(final long... ulongs) {
  31         final var ret = MutableUnsignedLongSet.of();
  32         for (long longBits : ulongs) {
  33             ret.add(longBits);
  34         }
  35         return ret;
  36     }
  37
  38     @Override
  39     public ImmutableUnsignedLongSet immutableCopy() {
  40         return ImmutableUnsignedLongSet.copyOf(this);
  41     }
  42
  43     public void add(final long longBits) {
  44         addOne(trustedRanges(), Entry.of(longBits));
  45     }
  46
  47     public void addAll(final UnsignedLongSet other) {
  48         final var ranges = trustedRanges();
  49         for (var range : other.trustedRanges()) {
  50             if (range.lowerBits == range.upperBits) {
  51                 addOne(ranges, range);
  52             } else {
  53                 addRange(ranges, range);
  54             }
  55         }
  56     }
  57
  58     private static void addOne(final NavigableSet<Entry> ranges, final Entry range) {
  59         final long longBits = range.lowerBits;
  60
  61         // We need Iterator.remove() to perform efficient merge below
  62         final var headIt = ranges.headSet(range, true).descendingIterator();
  63         if (headIt.hasNext()) {
  64             final var head = headIt.next();
  65             if (Long.compareUnsigned(head.upperBits, longBits) >= 0) {
  66                 // Already contained, this is a no-op
  67                 return;
  68             }
  69
  70             // Merge into head entry if possible
  71             if (head.upperBits + 1 == longBits) {
  72                 // We will be replacing head
  73                 headIt.remove();
  74
  75                 // Potentially merge head entry and tail entry
  76                 final var tailIt = ranges.tailSet(range, false).iterator();
  77                 if (tailIt.hasNext()) {
  78                     final var tail = tailIt.next();
  79                     if (tail.lowerBits - 1 == longBits) {
  80                         // Update tail.lowerBits to include contents of head
  81                         tailIt.remove();
  82                         ranges.add(tail.withLower(head.lowerBits));
  83                         return;
  84                     }
  85                 }
  86
  87                 // Update head.upperBits
  88                 ranges.add(head.withUpper(longBits));
  89                 return;
  90             }
  91         }
  92
  93         final var tailIt = ranges.tailSet(range, false).iterator();
  94         if (tailIt.hasNext()) {
  95             final var tail = tailIt.next();
  96             // Merge into tail entry if possible
  97             if (tail.lowerBits - 1 == longBits) {
  98                 // Update tail.lowerBits
  99                 tailIt.remove();
 100                 ranges.add(tail.withLower(longBits));
 101                 return;
 102             }
 103         }
 104
 105         // No luck, store a new entry
 106         ranges.add(range);
 107     }
 108
 109     private static void addRange(final NavigableSet<Entry> ranges, final Entry range) {
 110         // If the start of the range is already covered by an existing range, we can expand that
 111         final var headIt = ranges.headSet(range, true).descendingIterator();
 112         final boolean hasFloor = headIt.hasNext();
 113         if (hasFloor) {
 114             final var floor = headIt.next();
 115             if (Long.compareUnsigned(floor.upperBits, range.upperBits) < 0
 116                 && Long.compareUnsigned(floor.upperBits + 1, range.lowerBits) >= 0) {
 117                 headIt.remove();
 118                 ranges.add(expandFloor(ranges, floor, range.upperBits));
 119                 return;
 120             }
 121         }
 122
 123         // If the end of the range is already covered by an existing range, we can expand that
 124         final var tailIt = ranges.headSet(Entry.of(range.upperBits), true).descendingIterator();
 125         if (tailIt.hasNext()) {
 126             final var upper = tailIt.next();
 127             tailIt.remove();
 128
 129             // Quick check: if we did not find a lower range at all, we might be expanding the entire span, in which
 130             // case upper needs to become the first entry
 131             if (!hasFloor) {
 132                 ranges.headSet(upper, false).clear();
 133             }
 134
 135             ranges.add(expandCeiling(ranges, upper, range.lowerBits, range.upperBits));
 136             return;
 137         }
 138
 139         // No luck, insert
 140         ranges.add(range);
 141     }
 142
 143     private static @NonNull Entry expandFloor(final NavigableSet<Entry> ranges, final Entry floor,
 144             final long upperBits) {
 145         // Acquire any ranges after floor and clean them up
 146         final var tailIt = ranges.tailSet(floor, false).iterator();
 147         final long nextLower = upperBits + 1;
 148         while (tailIt.hasNext()) {
 149             final var tail = tailIt.next();
 150             if (Long.compareUnsigned(tail.lowerBits, nextLower) > 0) {
 151                 // There is gap, nothing more to cleanup
 152                 break;
 153             }
 154
 155             // We can merge this entry into floor...
 156             tailIt.remove();
 157
 158             if (Long.compareUnsigned(tail.upperBits, nextLower) >= 0) {
 159                 // ... but we need to expand floor accordingly and after that we are done
 160                 return floor.withUpper(tail.upperBits);
 161             }
 162         }
 163
 164         // Expand floor to include this range and we are done
 165         return floor.withUpper(upperBits);
 166     }
 167
 168     private static @NonNull Entry expandCeiling(final NavigableSet<Entry> ranges, final Entry ceiling,
 169             final long lowerBits, final long upperBits) {
 170         if (Long.compareUnsigned(ceiling.upperBits, upperBits) >= 0) {
 171             // Upper end is already covered
 172             return ceiling.withLower(lowerBits);
 173         }
 174
 175         // We are expanding the entry's upper boundary, we need to check if we need to coalesce following entries
 176         long newUpper = upperBits;
 177         final var tailIt = ranges.tailSet(ceiling, false).iterator();
 178         if (tailIt.hasNext()) {
 179             final var tail = tailIt.next();
 180             if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
 181                 tailIt.remove();
 182                 newUpper = tail.upperBits;
 183             }
 184         }
 185
 186         return Entry.of(lowerBits, newUpper);
 187     }
 188
 189     // Provides compatibility with RangeSet<UnsignedLong> using [lower, upper + 1)
 190     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
 191         return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), entry -> Range.closedOpen(
 192             UnsignedLong.fromLongBits(entry.lowerBits), UnsignedLong.fromLongBits(entry.upperBits + 1))));
 193     }
 194 }