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-unsubscribe@cassandra.apache.org
For additional commands, e-mail: pr-help@cassandra.apache.org
|