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.TreeSet;
  15 import org.eclipse.jdt.annotation.NonNull;
  16 import org.opendaylight.yangtools.concepts.Mutable;
  17
  18 @Beta
  19 public final class MutableUnsignedLongSet extends UnsignedLongSet implements Mutable {
  20     MutableUnsignedLongSet(final TreeSet<Entry> ranges) {
  21         super(ranges);
  22     }
  23
  24     public static @NonNull MutableUnsignedLongSet of() {
  25         return new MutableUnsignedLongSet(new TreeSet<>());
  26     }
  27
  28     @Override
  29     public ImmutableUnsignedLongSet immutableCopy() {
  30         return ImmutableUnsignedLongSet.copyOf(this);
  31     }
  32
  33     public void add(final long longBits) {
  34         final var ranges = trustedRanges();
  35         final var range = Entry.of(longBits);
  36
  37         // We need Iterator.remove() to perform efficient merge below
  38         final var headIt = ranges.headSet(range, true).descendingIterator();
  39         if (headIt.hasNext()) {
  40             final var head = headIt.next();
  41             if (Long.compareUnsigned(head.upperBits, longBits) >= 0) {
  42                 // Already contained, this is a no-op
  43                 return;
  44             }
  45
  46             // Merge into head entry if possible
  47             if (head.upperBits + 1 == longBits) {
  48                 head.upperBits = longBits;
  49
  50                 // Potentially merge head entry and tail entry
  51                 final var tail = ranges.higher(range);
  52                 if (tail != null) {
  53                     if (tail.lowerBits - 1 == longBits) {
  54                         // Expand tail, remove head
  55                         tail.lowerBits = head.lowerBits;
  56                         headIt.remove();
  57                     }
  58                 }
  59                 return;
  60             }
  61         }
  62
  63         final var tail = ranges.higher(range);
  64         if (tail != null) {
  65             // Merge into tail entry if possible
  66             if (tail.lowerBits - 1 == longBits) {
  67                 tail.lowerBits = longBits;
  68                 return;
  69             }
  70         }
  71
  72         // No luck, store a new entry
  73         ranges.add(range);
  74     }
  75
  76     public ImmutableRangeSet<UnsignedLong> toRangeSet() {
  77         return ImmutableRangeSet.copyOf(Collections2.transform(trustedRanges(), Entry::toUnsigned));
  78     }
  79 }