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), 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, range.lowerBits);
  51             } else {
  52                 addRange(ranges, range);
  53             }
  54         }
  55     }
  56
  57     private static void addOne(final NavigableSet<Entry> ranges, final Entry range, final long longBits) {
  58         // We need Iterator.remove() to perform efficient merge below
  59         final var headIt = ranges.headSet(range, true).descendingIterator();
  60         if (headIt.hasNext()) {
  61             final var head = headIt.next();
  62             if (Long.compareUnsigned(head.upperBits, longBits) >= 0) {
  63                 // Already contained, this is a no-op
  64                 return;
  65             }
  66
  67             // Merge into head entry if possible
  68             if (head.upperBits + 1 == longBits) {
  69                 head.upperBits = longBits;
  70
  71                 // Potentially merge head entry and tail entry
  72                 final var tail = ranges.higher(range);
  73                 if (tail != null) {
  74                     if (tail.lowerBits - 1 == longBits) {
  75                         // Expand tail, remove head
  76                         tail.lowerBits = head.lowerBits;
  77                         headIt.remove();
  78                     }
  79                 }
  80                 return;
  81             }
  82         }
  83
  84         final var tail = ranges.higher(range);
  85         if (tail != null) {
  86             // Merge into tail entry if possible
  87             if (tail.lowerBits - 1 == longBits) {
  88                 tail.lowerBits = longBits;
  89                 return;
  90             }
  91         }
  92
  93         // No luck, store a new entry
  94         ranges.add(range);
  95     }
  96
  97     private static void addRange(final NavigableSet<Entry> ranges, final Entry range) {
  98         // If the start of the range is already covered by an existing range, we can expand that
  99         final var lower = ranges.floor(range);
 100         if (lower != null && Long.compareUnsigned(lower.upperBits + 1, range.lowerBits) >= 0) {
 101             expandLower(ranges, lower, range.upperBits);
 102             return;
 103         }
 104
 105         // If the end of the range is already covered by an existing range, we can expand that
 106         final var upper = ranges.floor(Entry.of(range.upperBits));
 107         if (upper != null && Long.compareUnsigned(upper.lowerBits - 1, range.upperBits) <= 0) {
 108             // Quick check: if we did not find a lower range at all, we might be expanding the entire span, in which
 109             // case upper needs to become the first entry
 110             if (lower == null) {
 111                 ranges.headSet(upper, false).clear();
 112             }
 113
 114             expandUpper(ranges, upper, range.lowerBits, range.upperBits);
 115             return;
 116         }
 117
 118         // No luck, insert
 119         ranges.add(range);
 120     }
 121
 122     private static void expandLower(final NavigableSet<Entry> ranges, final Entry entry, final long upperBits) {
 123         if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
 124             // Already contained, this is a no-op
 125             return;
 126         }
 127
 128         // Acquire any ranges after floor and clean them up
 129         final var tailIt = ranges.tailSet(entry, false).iterator();
 130         final long nextLower = upperBits + 1;
 131         while (tailIt.hasNext()) {
 132             final var tail = tailIt.next();
 133             if (Long.compareUnsigned(tail.lowerBits, nextLower) > 0) {
 134                 // There is gap, nothing more to cleanup
 135                 break;
 136             }
 137
 138             // We can merge this entry into floor...
 139             tailIt.remove();
 140
 141             if (Long.compareUnsigned(tail.upperBits, nextLower) >= 0) {
 142                 // ... but we need to expand floor accordingly and after that we are done
 143                 entry.upperBits = tail.upperBits;
 144                 return;
 145             }
 146         }
 147
 148         // Expand floor to include this range and we are done
 149         entry.upperBits = upperBits;
 150     }
 151
 152     private static void expandUpper(final NavigableSet<Entry> ranges, final Entry entry, final long lowerBits,
 153             final long upperBits) {
 154         if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
 155             // Upper end is already covered
 156             entry.lowerBits = lowerBits;
 157             return;
 158         }
 159
 160         // We are expanding the entry's upper boundary, we need to check if we need to coalesce following entries
 161         long newUpper = upperBits;
 162         final var tailIt = ranges.tailSet(entry, false).iterator();
 163         if (tailIt.hasNext()) {
 164             final var tail = tailIt.next();
 165             if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
 166                 tailIt.remove();
 167                 newUpper = tail.upperBits;
 168             }
 169         }
 170
 171         entry.lowerBits = lowerBits;
 172         entry.upperBits = newUpper;
 173     }
 174
 175     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
 176         return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
 177     }
 178 }