| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.cassandra.dht; |
| |
| import java.io.Serializable; |
| import java.util.*; |
| |
| import org.apache.commons.lang3.ObjectUtils; |
| |
| import org.apache.cassandra.db.PartitionPosition; |
| import org.apache.cassandra.utils.Pair; |
| |
| /** |
| * A representation of the range that a node is responsible for on the DHT ring. |
| * |
| * A Range is responsible for the tokens between (left, right]. |
| * |
| * Used by the partitioner and by map/reduce by-token range scans. |
| * |
| * Note: this class has a natural ordering that is inconsistent with equals |
| */ |
| public class Range<T extends RingPosition<T>> extends AbstractBounds<T> implements Comparable<Range<T>>, Serializable |
| { |
| public static final long serialVersionUID = 1L; |
| |
| public Range(T left, T right) |
| { |
| super(left, right); |
| } |
| |
| public static <T extends RingPosition<T>> boolean contains(T left, T right, T point) |
| { |
| if (isWrapAround(left, right)) |
| { |
| /* |
| * We are wrapping around, so the interval is (a,b] where a >= b, |
| * then we have 3 cases which hold for any given token k: |
| * (1) a < k -- return true |
| * (2) k <= b -- return true |
| * (3) b < k <= a -- return false |
| */ |
| if (point.compareTo(left) > 0) |
| return true; |
| else |
| return right.compareTo(point) >= 0; |
| } |
| else |
| { |
| /* |
| * This is the range (a, b] where a < b. |
| */ |
| return point.compareTo(left) > 0 && right.compareTo(point) >= 0; |
| } |
| } |
| |
| public boolean contains(Range<T> that) |
| { |
| if (this.left.equals(this.right)) |
| { |
| // full ring always contains all other ranges |
| return true; |
| } |
| |
| boolean thiswraps = isWrapAround(left, right); |
| boolean thatwraps = isWrapAround(that.left, that.right); |
| if (thiswraps == thatwraps) |
| { |
| return left.compareTo(that.left) <= 0 && that.right.compareTo(right) <= 0; |
| } |
| else if (thiswraps) |
| { |
| // wrapping might contain non-wrapping |
| // that is contained if both its tokens are in one of our wrap segments |
| return left.compareTo(that.left) <= 0 || that.right.compareTo(right) <= 0; |
| } |
| else |
| { |
| // (thatwraps) |
| // non-wrapping cannot contain wrapping |
| return false; |
| } |
| } |
| |
| /** |
| * Helps determine if a given point on the DHT ring is contained |
| * in the range in question. |
| * @param point point in question |
| * @return true if the point contains within the range else false. |
| */ |
| public boolean contains(T point) |
| { |
| return contains(left, right, point); |
| } |
| |
| /** |
| * @param that range to check for intersection |
| * @return true if the given range intersects with this range. |
| */ |
| public boolean intersects(Range<T> that) |
| { |
| return intersectionWith(that).size() > 0; |
| } |
| |
| public boolean intersects(AbstractBounds<T> that) |
| { |
| // implemented for cleanup compaction membership test, so only Range + Bounds are supported for now |
| if (that instanceof Range) |
| return intersects((Range<T>) that); |
| if (that instanceof Bounds) |
| return intersects((Bounds<T>) that); |
| throw new UnsupportedOperationException("Intersection is only supported for Bounds and Range objects; found " + that.getClass()); |
| } |
| |
| /** |
| * @param that range to check for intersection |
| * @return true if the given range intersects with this range. |
| */ |
| public boolean intersects(Bounds<T> that) |
| { |
| // Same punishment than in Bounds.contains(), we must be carefull if that.left == that.right as |
| // as new Range<T>(that.left, that.right) will then cover the full ring which is not what we |
| // want. |
| return contains(that.left) || (!that.left.equals(that.right) && intersects(new Range<T>(that.left, that.right))); |
| } |
| |
| @SafeVarargs |
| public static <T extends RingPosition<T>> Set<Range<T>> rangeSet(Range<T> ... ranges) |
| { |
| return Collections.unmodifiableSet(new HashSet<Range<T>>(Arrays.asList(ranges))); |
| } |
| |
| public static <T extends RingPosition<T>> Set<Range<T>> rangeSet(Range<T> range) |
| { |
| return Collections.singleton(range); |
| } |
| |
| /** |
| * @param that |
| * @return the intersection of the two Ranges. this can be two disjoint Ranges if one is wrapping and one is not. |
| * say you have nodes G and M, with query range (D,T]; the intersection is (M-T] and (D-G]. |
| * If there is no intersection, an empty list is returned. |
| */ |
| public Set<Range<T>> intersectionWith(Range<T> that) |
| { |
| if (that.contains(this)) |
| return rangeSet(this); |
| if (this.contains(that)) |
| return rangeSet(that); |
| |
| boolean thiswraps = isWrapAround(left, right); |
| boolean thatwraps = isWrapAround(that.left, that.right); |
| if (!thiswraps && !thatwraps) |
| { |
| // neither wraps: the straightforward case. |
| if (!(left.compareTo(that.right) < 0 && that.left.compareTo(right) < 0)) |
| return Collections.emptySet(); |
| return rangeSet(new Range<T>(ObjectUtils.max(this.left, that.left), |
| ObjectUtils.min(this.right, that.right))); |
| } |
| if (thiswraps && thatwraps) |
| { |
| //both wrap: if the starts are the same, one contains the other, which we have already ruled out. |
| assert !this.left.equals(that.left); |
| // two wrapping ranges always intersect. |
| // since we have already determined that neither this nor that contains the other, we have 2 cases, |
| // and mirror images of those case. |
| // (1) both of that's (1, 2] endpoints lie in this's (A, B] right segment: |
| // ---------B--------A--1----2------> |
| // (2) only that's start endpoint lies in this's right segment: |
| // ---------B----1---A-------2------> |
| // or, we have the same cases on the left segement, which we can handle by swapping this and that. |
| return this.left.compareTo(that.left) < 0 |
| ? intersectionBothWrapping(this, that) |
| : intersectionBothWrapping(that, this); |
| } |
| if (thiswraps) // this wraps, that does not wrap |
| return intersectionOneWrapping(this, that); |
| // the last case: this does not wrap, that wraps |
| return intersectionOneWrapping(that, this); |
| } |
| |
| private static <T extends RingPosition<T>> Set<Range<T>> intersectionBothWrapping(Range<T> first, Range<T> that) |
| { |
| Set<Range<T>> intersection = new HashSet<Range<T>>(2); |
| if (that.right.compareTo(first.left) > 0) |
| intersection.add(new Range<T>(first.left, that.right)); |
| intersection.add(new Range<T>(that.left, first.right)); |
| return Collections.unmodifiableSet(intersection); |
| } |
| |
| private static <T extends RingPosition<T>> Set<Range<T>> intersectionOneWrapping(Range<T> wrapping, Range<T> other) |
| { |
| Set<Range<T>> intersection = new HashSet<Range<T>>(2); |
| if (other.contains(wrapping.right)) |
| intersection.add(new Range<T>(other.left, wrapping.right)); |
| // need the extra compareto here because ranges are asymmetrical; wrapping.left _is not_ contained by the wrapping range |
| if (other.contains(wrapping.left) && wrapping.left.compareTo(other.right) < 0) |
| intersection.add(new Range<T>(wrapping.left, other.right)); |
| return Collections.unmodifiableSet(intersection); |
| } |
| |
| public Pair<AbstractBounds<T>, AbstractBounds<T>> split(T position) |
| { |
| assert contains(position) || left.equals(position); |
| // Check if the split would have no effect on the range |
| if (position.equals(left) || position.equals(right)) |
| return null; |
| |
| AbstractBounds<T> lb = new Range<T>(left, position); |
| AbstractBounds<T> rb = new Range<T>(position, right); |
| return Pair.create(lb, rb); |
| } |
| |
| public boolean inclusiveLeft() |
| { |
| return false; |
| } |
| |
| public boolean inclusiveRight() |
| { |
| return true; |
| } |
| |
| public List<Range<T>> unwrap() |
| { |
| T minValue = right.minValue(); |
| if (!isWrapAround() || right.equals(minValue)) |
| return Arrays.asList(this); |
| List<Range<T>> unwrapped = new ArrayList<Range<T>>(2); |
| unwrapped.add(new Range<T>(left, minValue)); |
| unwrapped.add(new Range<T>(minValue, right)); |
| return unwrapped; |
| } |
| |
| /** |
| * Tells if the given range is a wrap around. |
| */ |
| public static <T extends RingPosition<T>> boolean isWrapAround(T left, T right) |
| { |
| return left.compareTo(right) >= 0; |
| } |
| |
| /** |
| * Tells if the given range covers the entire ring |
| */ |
| private static <T extends RingPosition<T>> boolean isFull(T left, T right) |
| { |
| return left.equals(right); |
| } |
| |
| /** |
| * Note: this class has a natural ordering that is inconsistent with equals |
| */ |
| public int compareTo(Range<T> rhs) |
| { |
| boolean lhsWrap = isWrapAround(left, right); |
| boolean rhsWrap = isWrapAround(rhs.left, rhs.right); |
| |
| // if one of the two wraps, that's the smaller one. |
| if (lhsWrap != rhsWrap) |
| return Boolean.compare(!lhsWrap, !rhsWrap); |
| // otherwise compare by right. |
| return right.compareTo(rhs.right); |
| } |
| |
| /** |
| * Subtracts a portion of this range. |
| * @param contained The range to subtract from this. It must be totally |
| * contained by this range. |
| * @return A List of the Ranges left after subtracting contained |
| * from this. |
| */ |
| private List<Range<T>> subtractContained(Range<T> contained) |
| { |
| // both ranges cover the entire ring, their difference is an empty set |
| if(isFull(left, right) && isFull(contained.left, contained.right)) |
| { |
| return Collections.emptyList(); |
| } |
| |
| // a range is subtracted from another range that covers the entire ring |
| if(isFull(left, right)) |
| { |
| return Collections.singletonList(new Range<>(contained.right, contained.left)); |
| } |
| |
| List<Range<T>> difference = new ArrayList<>(2); |
| if (!left.equals(contained.left)) |
| difference.add(new Range<T>(left, contained.left)); |
| if (!right.equals(contained.right)) |
| difference.add(new Range<T>(contained.right, right)); |
| return difference; |
| } |
| |
| public Set<Range<T>> subtract(Range<T> rhs) |
| { |
| return rhs.differenceToFetch(this); |
| } |
| |
| public Set<Range<T>> subtractAll(Collection<Range<T>> ranges) |
| { |
| Set<Range<T>> result = new HashSet<>(); |
| result.add(this); |
| for(Range<T> range : ranges) |
| { |
| result = substractAllFromToken(result, range); |
| } |
| |
| return result; |
| } |
| |
| private static <T extends RingPosition<T>> Set<Range<T>> substractAllFromToken(Set<Range<T>> ranges, Range<T> subtract) |
| { |
| Set<Range<T>> result = new HashSet<>(); |
| for(Range<T> range : ranges) |
| { |
| result.addAll(range.subtract(subtract)); |
| } |
| |
| return result; |
| } |
| /** |
| * Calculate set of the difference ranges of given two ranges |
| * (as current (A, B] and rhs is (C, D]) |
| * which node will need to fetch when moving to a given new token |
| * |
| * @param rhs range to calculate difference |
| * @return set of difference ranges |
| */ |
| public Set<Range<T>> differenceToFetch(Range<T> rhs) |
| { |
| Set<Range<T>> result; |
| Set<Range<T>> intersectionSet = this.intersectionWith(rhs); |
| if (intersectionSet.isEmpty()) |
| { |
| result = new HashSet<Range<T>>(); |
| result.add(rhs); |
| } |
| else |
| { |
| @SuppressWarnings("unchecked") |
| Range<T>[] intersections = new Range[intersectionSet.size()]; |
| intersectionSet.toArray(intersections); |
| if (intersections.length == 1) |
| { |
| result = new HashSet<Range<T>>(rhs.subtractContained(intersections[0])); |
| } |
| else |
| { |
| // intersections.length must be 2 |
| Range<T> first = intersections[0]; |
| Range<T> second = intersections[1]; |
| List<Range<T>> temp = rhs.subtractContained(first); |
| |
| // Because there are two intersections, subtracting only one of them |
| // will yield a single Range. |
| Range<T> single = temp.get(0); |
| result = new HashSet<Range<T>>(single.subtractContained(second)); |
| } |
| } |
| return result; |
| } |
| |
| public static <T extends RingPosition<T>> boolean isInRanges(T token, Iterable<Range<T>> ranges) |
| { |
| assert ranges != null; |
| |
| for (Range<T> range : ranges) |
| { |
| if (range.contains(token)) |
| { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| @Override |
| public boolean equals(Object o) |
| { |
| if (!(o instanceof Range)) |
| return false; |
| Range<?> rhs = (Range<?>)o; |
| return left.equals(rhs.left) && right.equals(rhs.right); |
| } |
| |
| @Override |
| public String toString() |
| { |
| return "(" + left + "," + right + "]"; |
| } |
| |
| protected String getOpeningString() |
| { |
| return "("; |
| } |
| |
| protected String getClosingString() |
| { |
| return "]"; |
| } |
| |
| public boolean isStartInclusive() |
| { |
| return false; |
| } |
| |
| public boolean isEndInclusive() |
| { |
| return true; |
| } |
| |
| public List<String> asList() |
| { |
| ArrayList<String> ret = new ArrayList<String>(2); |
| ret.add(left.toString()); |
| ret.add(right.toString()); |
| return ret; |
| } |
| |
| public boolean isWrapAround() |
| { |
| return isWrapAround(left, right); |
| } |
| |
| /** |
| * @return A copy of the given list of with all ranges unwrapped, sorted by left bound and with overlapping bounds merged. |
| */ |
| public static <T extends RingPosition<T>> List<Range<T>> normalize(Collection<Range<T>> ranges) |
| { |
| // unwrap all |
| List<Range<T>> output = new ArrayList<Range<T>>(ranges.size()); |
| for (Range<T> range : ranges) |
| output.addAll(range.unwrap()); |
| |
| // sort by left |
| Collections.sort(output, new Comparator<Range<T>>() |
| { |
| public int compare(Range<T> b1, Range<T> b2) |
| { |
| return b1.left.compareTo(b2.left); |
| } |
| }); |
| |
| // deoverlap |
| return deoverlap(output); |
| } |
| |
| /** |
| * Given a list of unwrapped ranges sorted by left position, return an |
| * equivalent list of ranges but with no overlapping ranges. |
| */ |
| private static <T extends RingPosition<T>> List<Range<T>> deoverlap(List<Range<T>> ranges) |
| { |
| if (ranges.isEmpty()) |
| return ranges; |
| |
| List<Range<T>> output = new ArrayList<Range<T>>(); |
| |
| Iterator<Range<T>> iter = ranges.iterator(); |
| Range<T> current = iter.next(); |
| |
| T min = current.left.minValue(); |
| while (iter.hasNext()) |
| { |
| // If current goes to the end of the ring, we're done |
| if (current.right.equals(min)) |
| { |
| // If one range is the full range, we return only that |
| if (current.left.equals(min)) |
| return Collections.<Range<T>>singletonList(current); |
| |
| output.add(new Range<T>(current.left, min)); |
| return output; |
| } |
| |
| Range<T> next = iter.next(); |
| |
| // if next left is equal to current right, we do not intersect per se, but replacing (A, B] and (B, C] by (A, C] is |
| // legit, and since this avoid special casing and will result in more "optimal" ranges, we do the transformation |
| if (next.left.compareTo(current.right) <= 0) |
| { |
| // We do overlap |
| // (we've handled current.right.equals(min) already) |
| if (next.right.equals(min) || current.right.compareTo(next.right) < 0) |
| current = new Range<T>(current.left, next.right); |
| } |
| else |
| { |
| output.add(current); |
| current = next; |
| } |
| } |
| output.add(current); |
| return output; |
| } |
| |
| public AbstractBounds<T> withNewRight(T newRight) |
| { |
| return new Range<T>(left, newRight); |
| } |
| |
| public static <T extends RingPosition<T>> List<Range<T>> sort(Collection<Range<T>> ranges) |
| { |
| List<Range<T>> output = new ArrayList<>(ranges.size()); |
| for (Range<T> r : ranges) |
| output.addAll(r.unwrap()); |
| // sort by left |
| Collections.sort(output, new Comparator<Range<T>>() |
| { |
| public int compare(Range<T> b1, Range<T> b2) |
| { |
| return b1.left.compareTo(b2.left); |
| } |
| }); |
| return output; |
| } |
| |
| |
| /** |
| * Compute a range of keys corresponding to a given range of token. |
| */ |
| public static Range<PartitionPosition> makeRowRange(Token left, Token right) |
| { |
| return new Range<PartitionPosition>(left.maxKeyBound(), right.maxKeyBound()); |
| } |
| |
| public static Range<PartitionPosition> makeRowRange(Range<Token> tokenBounds) |
| { |
| return makeRowRange(tokenBounds.left, tokenBounds.right); |
| } |
| |
| /** |
| * Helper class to check if a token is contained within a given collection of ranges |
| */ |
| public static class OrderedRangeContainmentChecker |
| { |
| private final Iterator<Range<Token>> normalizedRangesIterator; |
| private Token lastToken = null; |
| private Range<Token> currentRange; |
| |
| public OrderedRangeContainmentChecker(Collection<Range<Token>> ranges) |
| { |
| normalizedRangesIterator = normalize(ranges).iterator(); |
| assert normalizedRangesIterator.hasNext(); |
| currentRange = normalizedRangesIterator.next(); |
| } |
| |
| /** |
| * Returns true if the ranges given in the constructor contains the token, false otherwise. |
| * |
| * The tokens passed to this method must be in increasing order |
| * |
| * @param t token to check, must be larger than or equal to the last token passed |
| * @return true if the token is contained within the ranges given to the constructor. |
| */ |
| public boolean contains(Token t) |
| { |
| assert lastToken == null || lastToken.compareTo(t) <= 0; |
| lastToken = t; |
| while (true) |
| { |
| if (t.compareTo(currentRange.left) <= 0) |
| return false; |
| else if (t.compareTo(currentRange.right) <= 0 || currentRange.right.compareTo(currentRange.left) <= 0) |
| return true; |
| |
| if (!normalizedRangesIterator.hasNext()) |
| return false; |
| currentRange = normalizedRangesIterator.next(); |
| } |
| } |
| } |
| } |