2 * Copyright (c) 2021 PANTHEON.tech, s.r.o. and others. All rights reserved.
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
8 package org.opendaylight.controller.cluster.datastore.utils;
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;
20 public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mutable {
21 MutableUnsignedLongSet(final TreeSet<Entry> ranges) {
25 public static @NonNull MutableUnsignedLongSet of() {
26 return new MutableUnsignedLongSet(new TreeSet<>());
29 public static @NonNull MutableUnsignedLongSet of(final long... ulongs) {
30 final var ret = MutableUnsignedLongSet.of();
31 for (long longBits : ulongs) {
38 public ImmutableUnsignedLongSet immutableCopy() {
39 return ImmutableUnsignedLongSet.copyOf(this);
42 public void add(final long longBits) {
43 addOne(trustedRanges(), Entry.of(longBits));
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);
52 addRange(ranges, range);
57 private static void addOne(final NavigableSet<Entry> ranges, final Entry range) {
58 final long longBits = range.lowerBits;
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
69 // Merge into head entry if possible
70 if (head.upperBits + 1 == longBits) {
71 // We will be replacing head
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
81 ranges.add(tail.withLower(head.lowerBits));
86 // Update head.upperBits
87 ranges.add(head.withUpper(longBits));
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
99 ranges.add(tail.withLower(longBits));
104 // No luck, store a new entry
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();
113 final var floor = headIt.next();
114 if (Long.compareUnsigned(floor.upperBits, range.upperBits) < 0
115 && Long.compareUnsigned(floor.upperBits + 1, range.lowerBits) >= 0) {
117 ranges.add(expandFloor(ranges, floor, range.upperBits));
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();
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
131 ranges.headSet(upper, false).clear();
134 ranges.add(expandCeiling(ranges, upper, range.lowerBits, range.upperBits));
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
154 // We can merge this entry into floor...
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);
163 // Expand floor to include this range and we are done
164 return floor.withUpper(upperBits);
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);
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) {
181 newUpper = tail.upperBits;
185 return Entry.of(lowerBits, newUpper);
188 public ImmutableRangeSet<UnsignedLong> toRangeSet() {
189 return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));