Github user belliottsmith commented on a diff in the pull request: https://github.com/apache/cassandra/pull/271#discussion_r221306464 --- Diff: src/java/org/apache/cassandra/locator/AbstractReplicaCollection.java --- @@ -58,45 +63,332 @@ }; } - protected final List<Replica> list; - protected final boolean isSnapshot; - protected AbstractReplicaCollection(List<Replica> list, boolean isSnapshot) + /** + * A simple list with no comodification checks and immutability by default (only append permitted, and only one initial copy) + * this permits us to reduce the amount of garbage generated, by not wrapping iterators or unnecessarily copying + * and reduces the amount of indirection necessary, as well as ensuring monomorphic callsites + */ + protected static class ReplicaList implements Iterable<Replica> { - this.list = list; - this.isSnapshot = isSnapshot; + private static final Replica[] EMPTY = new Replica[0]; + Replica[] contents; + int begin, size; + + public ReplicaList() { this(0); } + public ReplicaList(int capacity) { contents = capacity == 0 ? EMPTY : new Replica[capacity]; } + public ReplicaList(Replica[] contents, int begin, int size) { this.contents = contents; this.begin = begin; this.size = size; } + + public boolean isSubList(ReplicaList subList) + { + return subList.contents == contents; + } + + public Replica get(int index) + { + if (index > size) + throw new IndexOutOfBoundsException(); + return contents[begin + index]; + } + + public void add(Replica replica) + { + // can only add to full array - if we have sliced it, we must be a snapshot + assert begin == 0; + if (size == contents.length) + { + int newSize; + if (size < 3) newSize = 3; + else if (size < 9) newSize = 9; + else newSize = size * 2; + contents = Arrays.copyOf(contents, newSize); + } + contents[size++] = replica; + } + + public int size() + { + return size; + } + + public boolean isEmpty() + { + return size == 0; + } + + public ReplicaList subList(int begin, int end) + { + if (end > size || begin > end) throw new IndexOutOfBoundsException(); + return new ReplicaList(contents, this.begin + begin, end - begin); + } + + public ReplicaList sorted(Comparator<Replica> comparator) + { + Replica[] copy = Arrays.copyOfRange(contents, begin, begin + size); + Arrays.sort(copy, comparator); + return new ReplicaList(copy, 0, copy.length); + } + + public Stream<Replica> stream() + { + return Arrays.stream(contents, begin, begin + size); + } + + @Override + public Iterator<Replica> iterator() + { + return new Iterator<Replica>() + { + final int end = begin + size; + int i = begin; + @Override + public boolean hasNext() + { + return i < end; + } + + @Override + public Replica next() + { + return contents[i++]; + } + }; + } + + public <K> Iterator<K> transformIterator(Function<Replica, K> function) + { + return new Iterator<K>() + { + final int end = begin + size; + int i = begin; + @Override + public boolean hasNext() + { + return i < end; + } + + @Override + public K next() + { + return function.apply(contents[i++]); + } + }; + } + + private Iterator<Replica> filterIterator(Predicate<Replica> predicate, int limit) + { + return new Iterator<Replica>() + { + final int end = begin + size; + int next = begin; + int count = 0; + { updateNext(); } + void updateNext() + { + if (count == limit) next = end; + while (next < end && !predicate.test(contents[next])) + ++next; + ++count; + } + @Override + public boolean hasNext() + { + return next < end; + } + + @Override + public Replica next() + { + if (!hasNext()) throw new IllegalStateException(); + Replica result = contents[next++]; + updateNext(); + return result; + } + }; + } + + @VisibleForTesting + public boolean equals(Object to) + { + if (to == null || to.getClass() != ReplicaList.class) + return false; + ReplicaList that = (ReplicaList) to; + if (this.size != that.size) return false; + for (int i = 0 ; i < size ; ++i) + if (!this.get(i).equals(that.get(i))) + return false; + return true; + } } - // if subList == null, should return self (or a clone thereof) - protected abstract C snapshot(List<Replica> subList); - protected abstract C self(); /** - * construct a new Mutable of our own type, so that we can concatenate - * TODO: this isn't terribly pretty, but we need sometimes to select / merge two Endpoints of unknown type; + * A simple map that ensures the underlying list's iteration order is maintained, and can be shared with + * subLists (either produced via subList, or via filter that naturally produced a subList). + * This permits us to reduce the amount of garbage generated, by not unnecessarily copying, + * reduces the amount of indirection necessary, as well as ensuring monomorphic callsites. + * The underlying map is also more efficient, particularly for such small collections as we typically produce. */ - public abstract Mutable<C> newMutable(int initialCapacity); + protected static class ReplicaMap<K> extends AbstractMap<K, Replica> + { + private final Function<Replica, K> toKey; + private final ReplicaList list; + // we maintain a map of key -> index in our list; this lets us share with subLists (or between Builder and snapshots) + // since we only need to corroborate that the list index we find is within the bounds of our list + // (if not, it's a shared map, and the key only occurs in one of our ancestors) + private final ObjectIntOpenHashMap<K> map; + private Set<K> keySet; + private Set<Entry<K, Replica>> entrySet; + + abstract class AbstractImmutableSet<K> extends AbstractSet<K> --- End diff -- We supply a different type parameter for EntrySet and KeySet, but shadowing the outer K is confusing. I've renamed K to T here.
--- --------------------------------------------------------------------- To unsubscribe, e-mail: pr-unsubscr...@cassandra.apache.org For additional commands, e-mail: pr-h...@cassandra.apache.org