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