+ private static void addRange(final NavigableSet<Entry> ranges, final Entry range) {
+ // If the start of the range is already covered by an existing range, we can expand that
+ final var lower = ranges.floor(range);
+ if (lower != null && Long.compareUnsigned(lower.upperBits + 1, range.lowerBits) >= 0) {
+ expandLower(ranges, lower, range.upperBits);
+ return;
+ }
+
+ // If the end of the range is already covered by an existing range, we can expand that
+ final var upper = ranges.floor(Entry.of(range.upperBits));
+ if (upper != null && Long.compareUnsigned(upper.lowerBits - 1, range.upperBits) <= 0) {
+ // Quick check: if we did not find a lower range at all, we might be expanding the entire span, in which
+ // case upper needs to become the first entry
+ if (lower == null) {
+ ranges.headSet(upper, false).clear();
+ }
+
+ expandUpper(ranges, upper, range.lowerBits, range.upperBits);
+ return;
+ }
+
+ // No luck, insert
+ ranges.add(range);
+ }
+
+ private static void expandLower(final NavigableSet<Entry> ranges, final Entry entry, final long upperBits) {
+ if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+ // Already contained, this is a no-op
+ return;
+ }
+
+ // Acquire any ranges after floor and clean them up
+ final var tailIt = ranges.tailSet(entry, false).iterator();
+ final long nextLower = upperBits + 1;
+ while (tailIt.hasNext()) {
+ final var tail = tailIt.next();
+ if (Long.compareUnsigned(tail.lowerBits, nextLower) > 0) {
+ // There is gap, nothing more to cleanup
+ break;
+ }
+
+ // We can merge this entry into floor...
+ tailIt.remove();
+
+ if (Long.compareUnsigned(tail.upperBits, nextLower) >= 0) {
+ // ... but we need to expand floor accordingly and after that we are done
+ entry.upperBits = tail.upperBits;
+ return;
+ }
+ }
+
+ // Expand floor to include this range and we are done
+ entry.upperBits = upperBits;
+ }
+
+ private static void expandUpper(final NavigableSet<Entry> ranges, final Entry entry, final long lowerBits,
+ final long upperBits) {
+ if (Long.compareUnsigned(entry.upperBits, upperBits) >= 0) {
+ // Upper end is already covered
+ entry.lowerBits = lowerBits;
+ return;
+ }
+
+ // We are expanding the entry's upper boundary, we need to check if we need to coalesce following entries
+ long newUpper = upperBits;
+ final var tailIt = ranges.tailSet(entry, false).iterator();
+ if (tailIt.hasNext()) {
+ final var tail = tailIt.next();
+ if (Long.compareUnsigned(tail.lowerBits, newUpper + 1) <= 0) {
+ tailIt.remove();
+ newUpper = tail.upperBits;
+ }
+ }
+
+ entry.lowerBits = lowerBits;
+ entry.upperBits = newUpper;
+ }
+