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