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.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;
21 public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mutable {
22 MutableUnsignedLongSet(final TreeSet<Entry> ranges) {
26 public static @NonNull MutableUnsignedLongSet of() {
27 return new MutableUnsignedLongSet(new TreeSet<>());
30 public static @NonNull MutableUnsignedLongSet of(final long... ulongs) {
31 final var ret = MutableUnsignedLongSet.of();
32 for (long longBits : ulongs) {
39 public ImmutableUnsignedLongSet immutableCopy() {
40 return ImmutableUnsignedLongSet.copyOf(this);
43 public void add(final long longBits) {
44 addOne(trustedRanges(), Entry.of(longBits));
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);
53 addRange(ranges, range);
58 private static void addOne(final NavigableSet<Entry> ranges, final Entry range) {
59 final long longBits = range.lowerBits;
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
70 // Merge into head entry if possible
71 if (head.upperBits + 1 == longBits) {
72 // We will be replacing head
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
82 ranges.add(tail.withLower(head.lowerBits));
87 // Update head.upperBits
88 ranges.add(head.withUpper(longBits));
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
100 ranges.add(tail.withLower(longBits));
105 // No luck, store a new entry
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();
114 final var floor = headIt.next();
115 if (Long.compareUnsigned(floor.upperBits, range.upperBits) < 0
116 && Long.compareUnsigned(floor.upperBits + 1, range.lowerBits) >= 0) {
118 ranges.add(expandFloor(ranges, floor, range.upperBits));
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();
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
132 ranges.headSet(upper, false).clear();
135 ranges.add(expandCeiling(ranges, upper, range.lowerBits, range.upperBits));
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
155 // We can merge this entry into floor...
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);
164 // Expand floor to include this range and we are done
165 return floor.withUpper(upperBits);
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);
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) {
182 newUpper = tail.upperBits;
186 return Entry.of(lowerBits, newUpper);
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))));