http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java index b359416..8067ccc 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractPatriciaTrie.java @@ -44,10 +44,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> private static final long serialVersionUID = -2303909182832019043L; /** - * The root node of the {@link Trie}. + * The root node of the {@link Trie}. */ final TrieEntry<K, V> root = new TrieEntry<>(null, null, -1); - + /** * Each of these fields are initialized to contain an instance of the * appropriate view the first time this view is requested. The views are @@ -56,52 +56,52 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> private transient volatile Set<K> keySet; private transient volatile Collection<V> values; private transient volatile Set<Map.Entry<K,V>> entrySet; - + /** * The current size of the {@link Trie} */ private int size = 0; - + /** * The number of times this {@link Trie} has been modified. * It's used to detect concurrent modifications and fail-fast * the {@link Iterator}s. */ transient int modCount = 0; - + public AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) { super(keyAnalyzer); } - + public AbstractPatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m) { super(keyAnalyzer); putAll(m); } - + @Override public void clear() { root.key = null; root.bitIndex = -1; root.value = null; - + root.parent = null; root.left = root; root.right = null; root.predecessor = root; - + size = 0; incrementModCount(); } - + @Override public int size() { return size; } - + /** * A helper method to increment the {@link Trie} size * and the modification counter. @@ -111,7 +111,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> size++; incrementModCount(); } - + /** * A helper method to decrement the {@link Trie} size * and increment the modification counter. @@ -121,7 +121,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> size--; incrementModCount(); } - + /** * A helper method to increment the modification counter. */ @@ -129,15 +129,15 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { ++modCount; } - + @Override public V put(K key, V value) { if (key == null) throw new NullPointerException("Key cannot be null"); - + int lengthInBits = lengthInBits(key); - + // The only place to store a key with a length // of zero bits is the root node if (lengthInBits == 0) @@ -149,7 +149,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> return root.setKeyValue(key, value); } - + TrieEntry<K, V> found = getNearestEntryForKey(key); if (compareKeys(key, found.key)) { @@ -160,7 +160,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> return found.setKeyValue(key, value); } - + int bitIndex = bitIndex(key, found.key); if (!Tries.isOutOfBoundsIndex(bitIndex)) { @@ -176,7 +176,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { // A bits of the Key are zero. The only place to // store such a Key is the root Node! - + /* NULL BIT KEY */ if (root.isEmpty()) incrementSize(); @@ -184,24 +184,25 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> incrementModCount(); return root.setKeyValue(key, value); - + } else if (Tries.isEqualBitKey(bitIndex)) { // This is a very special and rare case. - + /* REPLACE OLD KEY+VALUE */ - if (found != root) { + if (found != root) + { incrementModCount(); return found.setKeyValue(key, value); } } } - - throw new IndexOutOfBoundsException("Failed to put: " + + throw new IndexOutOfBoundsException("Failed to put: " + key + " -> " + value + ", " + bitIndex); } - + /** * Adds the given {@link TrieEntry} to the {@link Trie} */ @@ -215,7 +216,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> if (current.bitIndex >= entry.bitIndex || current.bitIndex <= path.bitIndex) { entry.predecessor = entry; - + if (!isBitSet(entry.key, entry.bitIndex)) { entry.left = entry; @@ -226,30 +227,30 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> entry.left = current; entry.right = entry; } - + entry.parent = path; if (current.bitIndex >= entry.bitIndex) current.parent = entry; - + // if we inserted an uplink, set the predecessor on it if (current.bitIndex <= path.bitIndex) current.predecessor = entry; - + if (path == root || !isBitSet(entry.key, path.bitIndex)) path.left = entry; else path.right = entry; - + return entry; } - + path = current; - + current = !isBitSet(entry.key, current.bitIndex) ? current.left : current.right; } } - + @Override public V get(Object k) { @@ -261,7 +262,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> * Returns the entry associated with the specified key in the * AbstractPatriciaTrie. Returns null if the map contains no mapping * for this key. - * + * * This may throw ClassCastException if the object is not of type K. */ TrieEntry<K,V> getEntry(Object k) @@ -269,18 +270,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> K key = Tries.cast(k); if (key == null) return null; - + TrieEntry<K,V> entry = getNearestEntryForKey(key); return !entry.isEmpty() && compareKeys(key, entry.key) ? entry : null; } - + @Override public Map.Entry<K, V> select(K key) { Reference<Map.Entry<K, V>> reference = new Reference<>(); return !selectR(root.left, -1, key, reference) ? reference.get() : null; } - + @Override public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor) { @@ -327,11 +328,11 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> return false; } - + /** - * + * */ - private boolean selectR(TrieEntry<K,V> h, int bitIndex, + private boolean selectR(TrieEntry<K,V> h, int bitIndex, final K key, final Cursor<? super K, ? super V> cursor, final Reference<Map.Entry<K, V>> reference) { @@ -377,10 +378,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> return selectR(h.left, h.bitIndex, key, cursor, reference); } } - + return false; } - + @Override public Map.Entry<K, V> traverse(Cursor<? super K, ? super V> cursor) { @@ -388,10 +389,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> while (entry != null) { TrieEntry<K, V> current = entry; - + Decision decision = cursor.select(current); entry = nextEntry(current); - + switch(decision) { case EXIT: @@ -409,21 +410,21 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> case CONTINUE: // do nothing. } } - + return null; } - + @Override public boolean containsKey(Object k) { if (k == null) return false; - + K key = Tries.cast(k); TrieEntry<K, V> entry = getNearestEntryForKey(key); return !entry.isEmpty() && compareKeys(key, entry.key); } - + @Override public Set<Map.Entry<K,V>> entrySet() { @@ -432,7 +433,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> return entrySet; } - + @Override public Set<K> keySet() { @@ -440,7 +441,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> keySet = new KeySet(); return keySet; } - + @Override public Collection<V> values() { @@ -448,18 +449,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> values = new Values(); return values; } - + /** * {@inheritDoc} - * - * @throws ClassCastException if provided key is of an incompatible type + * + * @throws ClassCastException if provided key is of an incompatible type */ @Override public V remove(Object k) { if (k == null) return null; - + K key = Tries.cast(k); TrieEntry<K, V> current = root.left; TrieEntry<K, V> path = root; @@ -476,17 +477,17 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> return null; } } - + path = current; current = !isBitSet(key, current.bitIndex) ? current.left : current.right; } } - + /** * Returns the nearest entry for a given key. This is useful * for finding knowing if a given key exists (and finding the value * for it), or for inserting the key. - * + * * The actual get implementation. This is very similar to * selectR but with the exception that it might return the * root Entry even if it's empty. @@ -500,17 +501,17 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { if (current.bitIndex <= path.bitIndex) return current; - + path = current; current = !isBitSet(key, current.bitIndex) ? current.left : current.right; } } - + /** * Removes a single entry from the {@link Trie}. - * + * * If we found a Key (Entry h) then figure out if it's - * an internal (hard to remove) or external Entry (easy + * an internal (hard to remove) or external Entry (easy * to remove) */ V removeEntry(TrieEntry<K, V> h) @@ -526,14 +527,14 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> removeExternalEntry(h); } } - + decrementSize(); return h.setKeyValue(null, null); } - + /** * Removes an external entry from the {@link Trie}. - * + * * If it's an external Entry then just remove it. * This is very easy and straight forward. */ @@ -546,11 +547,11 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> else if (!h.isExternalNode()) { throw new IllegalArgumentException(h + " is not an external Entry!"); - } - + } + TrieEntry<K, V> parent = h.parent; TrieEntry<K, V> child = (h.left == h) ? h.right : h.left; - + if (parent.left == h) { parent.left = child; @@ -559,7 +560,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { parent.right = child; } - + // either the parent is changing, or the predecessor is changing. if (child.bitIndex > parent.bitIndex) { @@ -569,12 +570,12 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { child.predecessor = parent; } - + } - + /** * Removes an internal entry from the {@link Trie}. - * + * * If it's an internal Entry then "good luck" with understanding * this code. The Idea is essentially that Entry p takes Entry h's * place in the trie which requires some re-wiring. @@ -588,18 +589,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> else if (!h.isInternalNode()) { throw new IllegalArgumentException(h + " is not an internal Entry!"); - } - + } + TrieEntry<K, V> p = h.predecessor; - + // Set P's bitIndex p.bitIndex = h.bitIndex; - + // Fix P's parent, predecessor and child Nodes { TrieEntry<K, V> parent = p.parent; TrieEntry<K, V> child = (p.left == h) ? p.right : p.left; - + // if it was looping to itself previously, // it will now be pointed from it's parent // (if we aren't removing it's parent -- @@ -608,7 +609,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> // predecessor. if (p.predecessor == p && p.parent != h) p.predecessor = p.parent; - + if (parent.left == p) { parent.left = child; @@ -617,23 +618,23 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { parent.right = child; } - + if (child.bitIndex > parent.bitIndex) { child.parent = parent; } } - + // Fix H's parent and child Nodes - { - // If H is a parent of its left and right child + { + // If H is a parent of its left and right child // then change them to P if (h.left.parent == h) h.left.parent = p; if (h.right.parent == h) h.right.parent = p; - + // Change H's parent if (h.parent.left == h) { @@ -644,22 +645,22 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> h.parent.right = p; } } - + // Copy the remaining fields from H to P //p.bitIndex = h.bitIndex; p.parent = h.parent; p.left = h.left; p.right = h.right; - + // Make sure that if h was pointing to any uplinks, // p now points to them. if (isValidUplink(p.left, p)) p.left.predecessor = p; - + if (isValidUplink(p.right, p)) p.right.predecessor = p; } - + /** * Returns the entry lexicographically after the given entry. * If the given entry is null, returns the first node. @@ -668,38 +669,38 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, null); } - + /** * Scans for the next node, starting at the specified point, and using 'previous' * as a hint that the last node we returned was 'previous' (so we know not to return * it again). If 'tree' is non-null, this will limit the search to the given tree. - * + * * The basic premise is that each iteration can follow the following steps: - * + * * 1) Scan all the way to the left. * a) If we already started from this node last time, proceed to Step 2. * b) If a valid uplink is found, use it. * c) If the result is an empty node (root not set), break the scan. * d) If we already returned the left node, break the scan. - * + * * 2) Check the right. * a) If we already returned the right node, proceed to Step 3. * b) If it is a valid uplink, use it. * c) Do Step 1 from the right node. - * + * * 3) Back up through the parents until we encounter find a parent * that we're not the right child of. - * + * * 4) If there's no right child of that parent, the iteration is finished. * Otherwise continue to Step 5. - * + * * 5) Check to see if the right child is a valid uplink. * a) If we already returned that child, proceed to Step 6. * Otherwise, use it. - * + * * 6) If the right child of the parent is the parent itself, we've * already found & returned the end of the Trie, so exit. - * + * * 7) Do Step 1 on the parent's right child. */ TrieEntry<K, V> nextEntryImpl(TrieEntry<K, V> start, TrieEntry<K, V> previous, TrieEntry<K, V> tree) @@ -717,18 +718,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> // returned the left of this node. if (previous == current.left) break; - + if (isValidUplink(current.left, current)) return current.left; - + current = current.left; } } - + // If there's no data at all, exit. if (current.isEmpty()) return null; - + // If we've already returned the left, // and the immediate right is null, // there's only one entry in the Trie @@ -740,18 +741,18 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> // if (current.right == null) return null; - + // If nothing valid on the left, try the right. if (previous != current.right) { // See if it immediately is valid. if (isValidUplink(current.right, current)) return current.right; - + // Must search on the right's side if it wasn't initially valid. return nextEntryImpl(current.right, previous, tree); } - + // Neither left nor right are valid, find the first parent // whose child did not come from the right & traverse it. while (current == current.parent.right) @@ -759,33 +760,33 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> // If we're going to traverse to above the subtree, stop. if (current == tree) return null; - + current = current.parent; } // If we're on the top of the subtree, we can't go any higher. if (current == tree) return null; - + // If there's no right, the parent must be root, so we're done. if (current.parent.right == null) return null; - + // If the parent's right points to itself, we've found one. if (previous != current.parent.right && isValidUplink(current.parent.right, current.parent)) return current.parent.right; - + // If the parent's right is itself, there can't be any more nodes. if (current.parent.right == current.parent) return null; - + // We need to traverse down the parent's right's path. return nextEntryImpl(current.parent.right, previous, tree); } - + /** * Returns the first entry the {@link Trie} is storing. - * + * * This is implemented by going always to the left until * we encounter a valid uplink. That uplink is the first key. */ @@ -794,9 +795,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> // if Trie is empty, no first node. return isEmpty() ? null : followLeft(root); } - - /** - * Goes left through the tree until it finds a valid node. + + /** + * Goes left through the tree until it finds a valid node. */ TrieEntry<K, V> followLeft(TrieEntry<K, V> node) { @@ -806,80 +807,80 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> // if we hit root and it didn't have a node, go right instead. if (child.isEmpty()) child = node.right; - + if (child.bitIndex <= node.bitIndex) return child; - + node = child; } } - - /** - * Returns true if 'next' is a valid uplink coming from 'from'. + + /** + * Returns true if 'next' is a valid uplink coming from 'from'. */ static boolean isValidUplink(TrieEntry<?, ?> next, TrieEntry<?, ?> from) { return next != null && next.bitIndex <= from.bitIndex && !next.isEmpty(); } - + /** - * A {@link Reference} allows us to return something through a Method's - * argument list. An alternative would be to an Array with a length of + * A {@link Reference} allows us to return something through a Method's + * argument list. An alternative would be to an Array with a length of * one (1) but that leads to compiler warnings. Computationally and memory - * wise there's no difference (except for the need to load the + * wise there's no difference (except for the need to load the * {@link Reference} Class but that happens only once). */ private static class Reference<E> { - + private E item; - + public void set(E item) { this.item = item; } - + public E get() { return item; } } - + /** * A {@link Trie} is a set of {@link TrieEntry} nodes */ static class TrieEntry<K,V> extends BasicEntry<K, V> { - + private static final long serialVersionUID = 4596023148184140013L; - + /** The index this entry is comparing. */ protected int bitIndex; - + /** The parent of this entry. */ protected TrieEntry<K,V> parent; - + /** The left child of this entry. */ protected TrieEntry<K,V> left; - + /** The right child of this entry. */ protected TrieEntry<K,V> right; - - /** The entry who uplinks to this entry. */ + + /** The entry who uplinks to this entry. */ protected TrieEntry<K,V> predecessor; - + public TrieEntry(K key, V value, int bitIndex) { super(key, value); - + this.bitIndex = bitIndex; - + this.parent = null; this.left = this; this.right = null; this.predecessor = this; } - + /** * Whether or not the entry is storing a key. * Only the root can potentially be empty, all other @@ -889,27 +890,27 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { return key == null; } - - /** - * Neither the left nor right child is a loopback + + /** + * Neither the left nor right child is a loopback */ public boolean isInternalNode() { return left != this && right != this; } - - /** - * Either the left or right child is a loopback + + /** + * Either the left or right child is a loopback */ public boolean isExternalNode() { return !isInternalNode(); } } - + /** - * This is a entry set view of the {@link Trie} as returned + * This is a entry set view of the {@link Trie} as returned * by {@link Map#entrySet()} */ private class EntrySet extends AbstractSet<Map.Entry<K,V>> @@ -919,17 +920,17 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { return new EntryIterator(); } - + @Override public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; - + TrieEntry<K,V> candidate = getEntry(((Map.Entry<?, ?>)o).getKey()); return candidate != null && candidate.equals(o); } - + @Override public boolean remove(Object o) { @@ -937,19 +938,19 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> AbstractPatriciaTrie.this.remove(o); return size != size(); } - + @Override public int size() { return AbstractPatriciaTrie.this.size(); } - + @Override public void clear() { AbstractPatriciaTrie.this.clear(); } - + /** * An {@link Iterator} that returns {@link Entry} Objects */ @@ -962,9 +963,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> } } } - + /** - * This is a key set view of the {@link Trie} as returned + * This is a key set view of the {@link Trie} as returned * by {@link Map#keySet()} */ private class KeySet extends AbstractSet<K> @@ -974,19 +975,19 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { return new KeyIterator(); } - + @Override public int size() { return AbstractPatriciaTrie.this.size(); } - + @Override public boolean contains(Object o) { return containsKey(o); } - + @Override public boolean remove(Object o) { @@ -994,13 +995,13 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> AbstractPatriciaTrie.this.remove(o); return size != size(); } - + @Override public void clear() { AbstractPatriciaTrie.this.clear(); } - + /** * An {@link Iterator} that returns Key Objects */ @@ -1013,9 +1014,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> } } } - + /** - * This is a value view of the {@link Trie} as returned + * This is a value view of the {@link Trie} as returned * by {@link Map#values()} */ private class Values extends AbstractCollection<V> @@ -1025,25 +1026,25 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { return new ValueIterator(); } - + @Override public int size() { return AbstractPatriciaTrie.this.size(); } - + @Override public boolean contains(Object o) { return containsValue(o); } - + @Override public void clear() { AbstractPatriciaTrie.this.clear(); } - + @Override public boolean remove(Object o) { @@ -1058,7 +1059,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> } return false; } - + /** * An {@link Iterator} that returns Value Objects */ @@ -1071,9 +1072,9 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> } } } - - /** - * An iterator for the entries. + + /** + * An iterator for the entries. */ abstract class TrieIterator<E> implements Iterator<E> { @@ -1081,10 +1082,10 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> * For fast-fail */ protected int expectedModCount = AbstractPatriciaTrie.this.modCount; - + protected TrieEntry<K, V> next; // the next node to return protected TrieEntry<K, V> current; // the current entry we're on - + /** * Starts iteration from the root */ @@ -1092,7 +1093,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { next = AbstractPatriciaTrie.this.nextEntry(null); } - + /** * Starts iteration at the given entry */ @@ -1100,7 +1101,7 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { next = firstEntry; } - + /** * Returns the next {@link TrieEntry} */ @@ -1108,16 +1109,16 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { if (expectedModCount != AbstractPatriciaTrie.this.modCount) throw new ConcurrentModificationException(); - + TrieEntry<K,V> e = next; if (e == null) throw new NoSuchElementException(); - + next = findNext(e); current = e; return e; } - + /** * @see PatriciaTrie#nextEntry(TrieEntry) */ @@ -1125,26 +1126,26 @@ abstract class AbstractPatriciaTrie<K, V> extends AbstractTrie<K, V> { return AbstractPatriciaTrie.this.nextEntry(prior); } - + @Override public boolean hasNext() { return next != null; } - + @Override public void remove() { if (current == null) throw new IllegalStateException(); - + if (expectedModCount != AbstractPatriciaTrie.this.modCount) throw new ConcurrentModificationException(); - + TrieEntry<K, V> node = current; current = null; AbstractPatriciaTrie.this.removeEntry(node); - + expectedModCount = AbstractPatriciaTrie.this.modCount; } }
http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java index 0bf9c20..f24ec14 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/AbstractTrie.java @@ -29,74 +29,75 @@ import java.util.Map; */ /** - * This class provides some basic {@link Trie} functionality and + * This class provides some basic {@link Trie} functionality and * utility methods for actual {@link Trie} implementations. */ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializable, Trie<K, V> { private static final long serialVersionUID = -6358111100045408883L; - + /** - * The {@link KeyAnalyzer} that's being used to build the + * The {@link KeyAnalyzer} that's being used to build the * PATRICIA {@link Trie} */ protected final KeyAnalyzer<? super K> keyAnalyzer; - - /** - * Constructs a new {@link Trie} using the given {@link KeyAnalyzer} + + /** + * Constructs a new {@link Trie} using the given {@link KeyAnalyzer} */ public AbstractTrie(KeyAnalyzer<? super K> keyAnalyzer) { this.keyAnalyzer = Tries.notNull(keyAnalyzer, "keyAnalyzer"); } - + @Override public K selectKey(K key) { Map.Entry<K, V> entry = select(key); return entry != null ? entry.getKey() : null; } - + @Override public V selectValue(K key) { Map.Entry<K, V> entry = select(key); return entry != null ? entry.getValue() : null; } - + @Override public String toString() { StringBuilder buffer = new StringBuilder(); buffer.append("Trie[").append(size()).append("]={\n"); - for (Map.Entry<K, V> entry : entrySet()) { + for (Map.Entry<K, V> entry : entrySet()) + { buffer.append(" ").append(entry).append("\n"); } buffer.append("}\n"); return buffer.toString(); } - + /** * Returns the length of the given key in bits - * + * * @see KeyAnalyzer#lengthInBits(Object) */ final int lengthInBits(K key) { return key == null ? 0 : keyAnalyzer.lengthInBits(key); } - + /** - * Returns whether or not the given bit on the + * Returns whether or not the given bit on the * key is set or false if the key is null. - * + * * @see KeyAnalyzer#isBitSet(Object, int) */ final boolean isBitSet(K key, int bitIndex) { return key != null && keyAnalyzer.isBitSet(key, bitIndex); } - + /** * Utility method for calling {@link KeyAnalyzer#bitIndex(Object, Object)} */ @@ -104,7 +105,7 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa { if (key != null && otherKey != null) { - return keyAnalyzer.bitIndex(key, otherKey); + return keyAnalyzer.bitIndex(key, otherKey); } else if (key != null) { @@ -114,10 +115,10 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa { return bitIndex(otherKey); } - + return KeyAnalyzer.NULL_BIT_KEY; } - + private int bitIndex(K key) { int lengthInBits = lengthInBits(key); @@ -126,10 +127,10 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa if (isBitSet(key, i)) return i; } - + return KeyAnalyzer.NULL_BIT_KEY; } - + /** * An utility method for calling {@link KeyAnalyzer#compare(Object, Object)} */ @@ -143,10 +144,10 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa { return false; } - + return keyAnalyzer.compare(key, other) == 0; } - + /** * A basic implementation of {@link Entry} */ @@ -155,17 +156,17 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa private static final long serialVersionUID = -944364551314110330L; protected K key; - + protected V value; - + private transient int hashCode = 0; - + public BasicEntry(K key, V value) { this.key = key; this.value = value; } - + /** * Replaces the current key and value with the provided * key & value @@ -176,19 +177,19 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa this.hashCode = 0; return setValue(value); } - + @Override public K getKey() { return key; } - + @Override public V getValue() { return value; } - + @Override public V setValue(V value) { @@ -196,7 +197,7 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa this.value = value; return previous; } - + @Override public int hashCode() { @@ -204,7 +205,7 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa hashCode = (key != null ? key.hashCode() : 0); return hashCode; } - + @Override public boolean equals(Object o) { @@ -216,11 +217,11 @@ abstract class AbstractTrie<K, V> extends AbstractMap<K, V> implements Serializa { return false; } - + Map.Entry<?, ?> other = (Map.Entry<?, ?>)o; return Tries.areEqual(key, other.getKey()) && Tries.areEqual(value, other.getValue()); } - + @Override public String toString() { http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java index 513fae0..dde3c8a 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/Cursor.java @@ -28,39 +28,39 @@ import java.util.Map.Entry; */ /** - * A {@link Cursor} can be used to traverse a {@link Trie}, visit each node - * step by step and make {@link Decision}s on each step how to continue with + * A {@link Cursor} can be used to traverse a {@link Trie}, visit each node + * step by step and make {@link Decision}s on each step how to continue with * traversing the {@link Trie}. */ public interface Cursor<K, V> { - + /** - * The {@link Decision} tells the {@link Cursor} what to do on each step + * The {@link Decision} tells the {@link Cursor} what to do on each step * while traversing the {@link Trie}. - * - * NOTE: Not all operations that work with a {@link Cursor} support all + * + * NOTE: Not all operations that work with a {@link Cursor} support all * {@link Decision} types */ enum Decision { - + /** * Exit the traverse operation */ - EXIT, - + EXIT, + /** * Continue with the traverse operation */ - CONTINUE, - + CONTINUE, + /** * Remove the previously returned element * from the {@link Trie} and continue */ - REMOVE, - + REMOVE, + /** * Remove the previously returned element * from the {@link Trie} and exit from the @@ -68,15 +68,15 @@ public interface Cursor<K, V> */ REMOVE_AND_EXIT } - + /** - * Called for each {@link Entry} in the {@link Trie}. Return + * Called for each {@link Entry} in the {@link Trie}. Return * {@link Decision#EXIT} to finish the {@link Trie} operation, * {@link Decision#CONTINUE} to go to the next {@link Entry}, * {@link Decision#REMOVE} to remove the {@link Entry} and * continue iterating or {@link Decision#REMOVE_AND_EXIT} to * remove the {@link Entry} and stop iterating. - * + * * Note: Not all operations support {@link Decision#REMOVE}. */ Decision select(Map.Entry<? extends K, ? extends V> entry); http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java index 9cab4ae..c6ef665 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/KeyAnalyzer.java @@ -37,36 +37,36 @@ public interface KeyAnalyzer<K> extends Comparator<K> * bits were all zero (0). */ int NULL_BIT_KEY = -1; - - /** + + /** * Returned by {@link #bitIndex(Object, Object)} if a the * bits of two keys were all equal. */ int EQUAL_BIT_KEY = -2; - + /** - * Returned by {@link #bitIndex(Object, Object)} if a keys + * Returned by {@link #bitIndex(Object, Object)} if a keys * indices are out of bounds. */ int OUT_OF_BOUNDS_BIT_KEY = -3; - + /** * Returns the key's length in bits. */ int lengthInBits(K key); - + /** * Returns {@code true} if a key's bit it set at the given index. */ boolean isBitSet(K key, int bitIndex); - + /** * Returns the index of the first bit that is different in the two keys. */ int bitIndex(K key, K otherKey); - + /** - * Returns {@code true} if the second argument is a + * Returns {@code true} if the second argument is a * prefix of the first argument. */ boolean isPrefix(K key, K prefix); http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java index 3c672ec..9187894 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/PatriciaTrie.java @@ -29,98 +29,98 @@ import java.util.*; /** * <h3>PATRICIA {@link Trie}</h3> - * + * * <i>Practical Algorithm to Retrieve Information Coded in Alphanumeric</i> - * - * <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing - * all data at the edges of the {@link Trie} (and having empty internal nodes), - * PATRICIA stores data in every node. This allows for very efficient traversal, - * insert, delete, predecessor, successor, prefix, range, and {@link #select(Object)} - * operations. All operations are performed at worst in O(K) time, where K - * is the number of bits in the largest item in the tree. In practice, - * operations actually take O(A(K)) time, where A(K) is the average number of + * + * <p>A PATRICIA {@link Trie} is a compressed {@link Trie}. Instead of storing + * all data at the edges of the {@link Trie} (and having empty internal nodes), + * PATRICIA stores data in every node. This allows for very efficient traversal, + * insert, delete, predecessor, successor, prefix, range, and {@link #select(Object)} + * operations. All operations are performed at worst in O(K) time, where K + * is the number of bits in the largest item in the tree. In practice, + * operations actually take O(A(K)) time, where A(K) is the average number of * bits of all items in the tree. - * + * * <p>Most importantly, PATRICIA requires very few comparisons to keys while - * doing any operation. While performing a lookup, each comparison (at most - * K of them, described above) will perform a single bit comparison against + * doing any operation. While performing a lookup, each comparison (at most + * K of them, described above) will perform a single bit comparison against * the given key, instead of comparing the entire key to another key. - * - * <p>The {@link Trie} can return operations in lexicographical order using the - * {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The - * {@link Trie} can also scan for items that are 'bitwise' (using an XOR - * metric) by the 'select' method. Bitwise closeness is determined by the - * {@link KeyAnalyzer} returning true or false for a bit being set or not in + * + * <p>The {@link Trie} can return operations in lexicographical order using the + * {@link #traverse(Cursor)}, 'prefix', 'submap', or 'iterator' methods. The + * {@link Trie} can also scan for items that are 'bitwise' (using an XOR + * metric) by the 'select' method. Bitwise closeness is determined by the + * {@link KeyAnalyzer} returning true or false for a bit being set or not in * a given key. - * - * <p>Any methods here that take an {@link Object} argument may throw a - * {@link ClassCastException} if the method is expecting an instance of K + * + * <p>Any methods here that take an {@link Object} argument may throw a + * {@link ClassCastException} if the method is expecting an instance of K * and it isn't K. - * + * * @see <a href="http://en.wikipedia.org/wiki/Radix_tree";>Radix Tree</a> * @see <a href="http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA";>PATRICIA</a> * @see <a href="http://www.imperialviolet.org/binary/critbit.pdf";>Crit-Bit Tree</a> - * + * * @author Roger Kapsi * @author Sam Berlin */ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Serializable { private static final long serialVersionUID = -2246014692353432660L; - + public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer) { super(keyAnalyzer); } - + public PatriciaTrie(KeyAnalyzer<? super K> keyAnalyzer, Map<? extends K, ? extends V> m) { super(keyAnalyzer, m); } - + @Override public Comparator<? super K> comparator() { return keyAnalyzer; } - + @Override public SortedMap<K, V> prefixMap(K prefix) { return lengthInBits(prefix) == 0 ? this : new PrefixRangeMap(prefix); } - + @Override public K firstKey() { return firstEntry().getKey(); } - + @Override public K lastKey() { TrieEntry<K, V> entry = lastEntry(); return entry != null ? entry.getKey() : null; } - + @Override public SortedMap<K, V> headMap(K toKey) { return new RangeEntryMap(null, toKey); } - + @Override public SortedMap<K, V> subMap(K fromKey, K toKey) { return new RangeEntryMap(fromKey, toKey); } - + @Override public SortedMap<K, V> tailMap(K fromKey) { return new RangeEntryMap(fromKey, null); - } - + } + /** * Returns an entry strictly higher than the given key, * or null if no such entry exists. @@ -128,10 +128,10 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se private TrieEntry<K,V> higherEntry(K key) { // TODO: Cleanup so that we don't actually have to add/remove from the - // tree. (We do it here because there are other well-defined + // tree. (We do it here because there are other well-defined // functions to perform the search.) int lengthInBits = lengthInBits(key); - + if (lengthInBits == 0) { if (!root.isEmpty()) @@ -145,11 +145,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return firstEntry(); } } - + TrieEntry<K, V> found = getNearestEntryForKey(key); if (compareKeys(key, found.key)) return nextEntry(found); - + int bitIndex = bitIndex(key, found.key); if (Tries.isValidBitIndex(bitIndex)) { @@ -178,7 +178,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se // we should have exited above. throw new IllegalStateException("invalid lookup: " + key); } - + /** * Returns a key-value mapping associated with the least key greater * than or equal to the given key, or null if there is no such key. @@ -199,12 +199,12 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se // These steps ensure that the returned value is either the // entry for the key itself, or the first entry directly after // the key. - + // TODO: Cleanup so that we don't actually have to add/remove from the - // tree. (We do it here because there are other well-defined + // tree. (We do it here because there are other well-defined // functions to perform the search.) int lengthInBits = lengthInBits(key); - + if (lengthInBits == 0) { if (!root.isEmpty()) @@ -216,11 +216,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return firstEntry(); } } - + TrieEntry<K, V> found = getNearestEntryForKey(key); if (compareKeys(key, found.key)) return found; - + int bitIndex = bitIndex(key, found.key); if (Tries.isValidBitIndex(bitIndex)) { @@ -267,7 +267,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se modCount -= 2; // we didn't really modify it. return prior; } - + /** * Returns a key-value mapping associated with the greatest key * strictly less than the given key, or null if there is no such key. @@ -287,19 +287,19 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se // // These steps ensure that the returned value is always just before // the key or null (if there was nothing before it). - + // TODO: Cleanup so that we don't actually have to add/remove from the - // tree. (We do it here because there are other well-defined + // tree. (We do it here because there are other well-defined // functions to perform the search.) int lengthInBits = lengthInBits(key); - + if (lengthInBits == 0) return null; // there can never be anything before root. - + TrieEntry<K, V> found = getNearestEntryForKey(key); if (compareKeys(key, found.key)) return previousEntry(found); - + int bitIndex = bitIndex(key, found.key); if (Tries.isValidBitIndex(bitIndex)) { @@ -317,26 +317,26 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se // we should have exited above. throw new IllegalStateException("invalid lookup: " + key); } - + /** * Returns a key-value mapping associated with the greatest key * less than or equal to the given key, or null if there is no such key. */ - TrieEntry<K,V> floorEntry(K key) { + TrieEntry<K,V> floorEntry(K key) { // TODO: Cleanup so that we don't actually have to add/remove from the - // tree. (We do it here because there are other well-defined + // tree. (We do it here because there are other well-defined // functions to perform the search.) int lengthInBits = lengthInBits(key); - + if (lengthInBits == 0) { return !root.isEmpty() ? root : null; } - + TrieEntry<K, V> found = getNearestEntryForKey(key); if (compareKeys(key, found.key)) return found; - + int bitIndex = bitIndex(key, found.key); if (Tries.isValidBitIndex(bitIndex)) { @@ -361,56 +361,56 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se // we should have exited above. throw new IllegalStateException("invalid lookup: " + key); } - + /** * Finds the subtree that contains the prefix. - * + * * This is very similar to getR but with the difference that * we stop the lookup if h.bitIndex > lengthInBits. */ private TrieEntry<K, V> subtree(K prefix) { int lengthInBits = lengthInBits(prefix); - + TrieEntry<K, V> current = root.left; TrieEntry<K, V> path = root; while(true) { if (current.bitIndex <= path.bitIndex || lengthInBits < current.bitIndex) break; - + path = current; current = !isBitSet(prefix, current.bitIndex) ? current.left : current.right; - } + } // Make sure the entry is valid for a subtree. TrieEntry<K, V> entry = current.isEmpty() ? path : current; - + // If entry is root, it can't be empty. if (entry.isEmpty()) return null; - + // if root && length of root is less than length of lookup, // there's nothing. // (this prevents returning the whole subtree if root has an empty // string and we want to lookup things with "\0") if (entry == root && lengthInBits(entry.getKey()) < lengthInBits) return null; - + // Found key's length-th bit differs from our key // which means it cannot be the prefix... if (isBitSet(prefix, lengthInBits) != isBitSet(entry.key, lengthInBits)) return null; - + // ... or there are less than 'length' equal bits int bitIndex = bitIndex(prefix, entry.key); return (bitIndex >= 0 && bitIndex < lengthInBits) ? null : entry; } - + /** * Returns the last entry the {@link Trie} is storing. - * + * * <p>This is implemented by going always to the right until * we encounter a valid uplink. That uplink is the last key. */ @@ -418,7 +418,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { return followRight(root.left); } - + /** * Traverses down the right path until it finds an uplink. */ @@ -427,40 +427,40 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se // if Trie is empty, no last entry. if (node.right == null) return null; - + // Go as far right as possible, until we encounter an uplink. while (node.right.bitIndex > node.bitIndex) { node = node.right; } - + return node.right; } - + /** * Returns the node lexicographically before the given node (or null if none). - * + * * This follows four simple branches: * - If the uplink that returned us was a right uplink: * - If predecessor's left is a valid uplink from predecessor, return it. * - Else, follow the right path from the predecessor's left. * - If the uplink that returned us was a left uplink: - * - Loop back through parents until we encounter a node where + * - Loop back through parents until we encounter a node where * node != node.parent.left. * - If node.parent.left is uplink from node.parent: * - If node.parent.left is not root, return it. * - If it is root & root isEmpty, return null. * - If it is root & root !isEmpty, return root. * - If node.parent.left is not uplink from node.parent: - * - Follow right path for first right child from node.parent.left - * + * - Follow right path for first right child from node.parent.left + * * @param start the start entry */ private TrieEntry<K, V> previousEntry(TrieEntry<K, V> start) { if (start.predecessor == null) throw new IllegalArgumentException("must have come from somewhere!"); - + if (start.predecessor.right == start) { return isValidUplink(start.predecessor.left, start.predecessor) @@ -493,11 +493,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return followRight(node.parent.left); } } - + /** * Returns the entry lexicographically after the given entry. * If the given entry is null, returns the first node. - * + * * This will traverse only within the subtree. If the given node * is not within the subtree, this will have undefined results. */ @@ -505,12 +505,12 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { return (node == null) ? firstEntry() : nextEntryImpl(node.predecessor, node, parentOfSubtree); } - + private boolean isPrefix(K key, K prefix) { return keyAnalyzer.isPrefix(key, prefix); } - + /** * A range view of the {@link Trie} */ @@ -522,7 +522,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se private transient volatile Set<Map.Entry<K, V>> entrySet; /** - * Creates and returns an {@link #entrySet()} + * Creates and returns an {@link #entrySet()} * view of the {@link RangeMap} */ protected abstract Set<Map.Entry<K, V>> createEntrySet(); @@ -531,47 +531,47 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se * Returns the FROM Key */ protected abstract K getFromKey(); - + /** * Whether or not the {@link #getFromKey()} is in the range */ protected abstract boolean isFromInclusive(); - + /** * Returns the TO Key */ protected abstract K getToKey(); - + /** * Whether or not the {@link #getToKey()} is in the range */ protected abstract boolean isToInclusive(); - - + + @Override public Comparator<? super K> comparator() { return PatriciaTrie.this.comparator(); } - + @Override public boolean containsKey(Object key) { return inRange(Tries.<K>cast(key)) && PatriciaTrie.this.containsKey(key); } - + @Override public V remove(Object key) { return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.remove(key); } - + @Override public V get(Object key) { return (!inRange(Tries.<K>cast(key))) ? null : PatriciaTrie.this.get(key); } - + @Override public V put(K key, V value) { @@ -580,7 +580,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return PatriciaTrie.this.put(key, value); } - + @Override public Set<Map.Entry<K, V>> entrySet() { @@ -588,7 +588,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se entrySet = createEntrySet(); return entrySet; } - + @Override public SortedMap<K, V> subMap(K fromKey, K toKey) { @@ -600,7 +600,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return createRangeMap(fromKey, isFromInclusive(), toKey, isToInclusive()); } - + @Override public SortedMap<K, V> headMap(K toKey) { @@ -609,7 +609,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return createRangeMap(getFromKey(), isFromInclusive(), toKey, isToInclusive()); } - + @Override public SortedMap<K, V> tailMap(K fromKey) { @@ -645,7 +645,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se } /** - * Returns true if the provided key is in the FROM range + * Returns true if the provided key is in the FROM range * of the {@link RangeMap} */ protected boolean inFromRange(K key, boolean forceInclusive) @@ -658,7 +658,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se } /** - * Returns true if the provided key is in the TO range + * Returns true if the provided key is in the TO range * of the {@link RangeMap} */ protected boolean inToRange(K key, boolean forceInclusive) @@ -675,32 +675,32 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se */ protected abstract SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); } - + /** * A {@link RangeMap} that deals with {@link Entry}s */ private class RangeEntryMap extends RangeMap { - /** - * The key to start from, null if the beginning. + /** + * The key to start from, null if the beginning. */ protected final K fromKey; - - /** - * The key to end at, null if till the end. + + /** + * The key to end at, null if till the end. */ protected final K toKey; - - /** - * Whether or not the 'from' is inclusive. + + /** + * Whether or not the 'from' is inclusive. */ protected final boolean fromInclusive; - - /** - * Whether or not the 'to' is inclusive. + + /** + * Whether or not the 'to' is inclusive. */ protected final boolean toInclusive; - + /** * Creates a {@link RangeEntryMap} with the fromKey included and * the toKey excluded from the range @@ -709,7 +709,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { this(fromKey, true, toKey, false); } - + /** * Creates a {@link RangeEntryMap} */ @@ -717,24 +717,24 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { if (fromKey == null && toKey == null) throw new IllegalArgumentException("must have a from or to!"); - + if (fromKey != null && toKey != null && keyAnalyzer.compare(fromKey, toKey) > 0) throw new IllegalArgumentException("fromKey > toKey"); - + this.fromKey = fromKey; this.fromInclusive = fromInclusive; this.toKey = toKey; this.toInclusive = toInclusive; } - - + + @Override public K firstKey() { Map.Entry<K,V> e = fromKey == null ? firstEntry() : fromInclusive ? ceilingEntry(fromKey) : higherEntry(fromKey); - + K first = e != null ? e.getKey() : null; if (e == null || toKey != null && !inToRange(first, false)) throw new NoSuchElementException(); @@ -742,58 +742,58 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return first; } - + @Override public K lastKey() { Map.Entry<K,V> e = toKey == null ? lastEntry() : toInclusive ? floorEntry(toKey) : lowerEntry(toKey); - + K last = e != null ? e.getKey() : null; if (e == null || fromKey != null && !inFromRange(last, false)) throw new NoSuchElementException(); return last; } - + @Override protected Set<Entry<K, V>> createEntrySet() { return new RangeEntrySet(this); } - + @Override public K getFromKey() { return fromKey; } - + @Override public K getToKey() { return toKey; } - + @Override public boolean isFromInclusive() { return fromInclusive; } - + @Override public boolean isToInclusive() { return toInclusive; } - + @Override protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive); } } - + /** * A {@link Set} view of a {@link RangeMap} */ @@ -816,7 +816,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se this.delegate = delegate; } - + @Override public Iterator<Map.Entry<K, V>> iterator() { @@ -830,7 +830,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return new EntryIterator(first, last); } - + @Override public int size() { @@ -848,13 +848,13 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return size; } - + @Override public boolean isEmpty() { return !iterator().hasNext(); } - + @Override public boolean contains(Object o) { @@ -870,7 +870,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se TrieEntry<K, V> node = getEntry(key); return node != null && Tries.areEqual(node.getValue(), entry.getValue()); } - + @Override public boolean remove(Object o) { @@ -892,9 +892,9 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return false; } - - /** - * An {@link Iterator} for {@link RangeEntrySet}s. + + /** + * An {@link Iterator} for {@link RangeEntrySet}s. */ private final class EntryIterator extends TrieIterator<Map.Entry<K,V>> { @@ -908,40 +908,40 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se super(first); this.excludedKey = (last != null ? last.getKey() : null); } - + @Override public boolean hasNext() { return next != null && !Tries.areEqual(next.key, excludedKey); } - + @Override public Map.Entry<K,V> next() { if (next == null || Tries.areEqual(next.key, excludedKey)) throw new NoSuchElementException(); - + return nextEntry(); } } - } - - /** - * A submap used for prefix views over the {@link Trie}. + } + + /** + * A submap used for prefix views over the {@link Trie}. */ private class PrefixRangeMap extends RangeMap { - + private final K prefix; - + private K fromKey = null; - + private K toKey = null; - + private int expectedModCount = -1; - + private int size = -1; - + /** * Creates a {@link PrefixRangeMap} */ @@ -949,11 +949,11 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { this.prefix = prefix; } - + /** * This method does two things. It determinates the FROM * and TO range of the {@link PrefixRangeMap} and the number - * of elements in the range. This method must be called every + * of elements in the range. This method must be called every * time the {@link Trie} has changed. */ private int fixup() @@ -964,69 +964,69 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { Iterator<Map.Entry<K, V>> it = entrySet().iterator(); size = 0; - + Map.Entry<K, V> entry = null; if (it.hasNext()) { entry = it.next(); size = 1; } - + fromKey = entry == null ? null : entry.getKey(); if (fromKey != null) { TrieEntry<K, V> prior = previousEntry((TrieEntry<K, V>)entry); fromKey = prior == null ? null : prior.getKey(); } - + toKey = fromKey; - + while (it.hasNext()) { ++size; entry = it.next(); } - + toKey = entry == null ? null : entry.getKey(); - + if (toKey != null) { entry = nextEntry((TrieEntry<K, V>)entry); toKey = entry == null ? null : entry.getKey(); } - + expectedModCount = PatriciaTrie.this.modCount; } - + return size; } - + @Override public K firstKey() { fixup(); - + Map.Entry<K,V> e = fromKey == null ? firstEntry() : higherEntry(fromKey); K first = e != null ? e.getKey() : null; if (e == null || !isPrefix(first, prefix)) throw new NoSuchElementException(); - + return first; } - + @Override public K lastKey() { fixup(); - + Map.Entry<K,V> e = toKey == null ? lastEntry() : lowerEntry(toKey); K last = e != null ? e.getKey() : null; if (e == null || !isPrefix(last, prefix)) throw new NoSuchElementException(); - + return last; } - + /** * Returns true if this {@link PrefixRangeMap}'s key is a prefix * of the provided key. @@ -1045,7 +1045,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { return inRange(key); } - + /** * Returns true if the provided Key is in the FROM range * of the {@link PrefixRangeMap} @@ -1055,7 +1055,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { return isPrefix(key, prefix); } - + /** * Returns true if the provided Key is in the TO range * of the {@link PrefixRangeMap} @@ -1065,37 +1065,37 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se { return isPrefix(key, prefix); } - + @Override protected Set<Map.Entry<K, V>> createEntrySet() { return new PrefixRangeEntrySet(this); } - + @Override public K getFromKey() { return fromKey; } - + @Override public K getToKey() { return toKey; } - + @Override public boolean isFromInclusive() { return false; } - + @Override public boolean isToInclusive() { return false; } - + @Override protected SortedMap<K, V> createRangeMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) @@ -1103,18 +1103,18 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return new RangeEntryMap(fromKey, fromInclusive, toKey, toInclusive); } } - + /** * A prefix {@link RangeEntrySet} view of the {@link Trie} */ private final class PrefixRangeEntrySet extends RangeEntrySet { private final PrefixRangeMap delegate; - + private TrieEntry<K, V> prefixStart; - + private int expectedModCount = -1; - + /** * Creates a {@link PrefixRangeEntrySet} */ @@ -1123,13 +1123,13 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se super(delegate); this.delegate = delegate; } - + @Override public int size() { return delegate.fixup(); } - + @Override public Iterator<Map.Entry<K,V>> iterator() { @@ -1138,7 +1138,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se prefixStart = subtree(delegate.prefix); expectedModCount = PatriciaTrie.this.modCount; } - + if (prefixStart == null) { Set<Map.Entry<K,V>> empty = Collections.emptySet(); @@ -1153,62 +1153,62 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se return new EntryIterator(prefixStart, delegate.prefix); } } - - /** - * An {@link Iterator} that holds a single {@link TrieEntry}. + + /** + * An {@link Iterator} that holds a single {@link TrieEntry}. */ private final class SingletonIterator implements Iterator<Map.Entry<K, V>> { private final TrieEntry<K, V> entry; - + private int hit = 0; - + public SingletonIterator(TrieEntry<K, V> entry) { this.entry = entry; } - + @Override public boolean hasNext() { return hit == 0; } - + @Override public Map.Entry<K, V> next() { if (hit != 0) throw new NoSuchElementException(); - + ++hit; return entry; } - + @Override public void remove() { if (hit != 1) throw new IllegalStateException(); - + ++hit; PatriciaTrie.this.removeEntry(entry); } } - - /** - * An {@link Iterator} for iterating over a prefix search. + + /** + * An {@link Iterator} for iterating over a prefix search. */ private final class EntryIterator extends TrieIterator<Map.Entry<K, V>> { // values to reset the subtree if we remove it. protected final K prefix; protected boolean lastOne; - + protected TrieEntry<K, V> subtree; // the subtree to search within - + /** - * Starts iteration at the given entry & search only + * Starts iteration at the given entry & search only * within the given subtree. */ EntryIterator(TrieEntry<K, V> startScan, K prefix) @@ -1217,7 +1217,7 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se next = PatriciaTrie.this.followLeft(startScan); this.prefix = prefix; } - + @Override public Map.Entry<K,V> next() { @@ -1226,13 +1226,13 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se next = null; return entry; } - + @Override protected TrieEntry<K, V> findNext(TrieEntry<K, V> prior) { return PatriciaTrie.this.nextEntryInSubtree(prior, subtree); } - + @Override public void remove() { @@ -1242,9 +1242,9 @@ public class PatriciaTrie<K, V> extends AbstractPatriciaTrie<K, V> implements Se int bitIdx = subtree.bitIndex; if (current == subtree) needsFixing = true; - + super.remove(); - + // If the subtree changed its bitIndex or we // removed the old subtree, get a new one. if (bitIdx != subtree.bitIndex || needsFixing) http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java index 44809f3..1866fec 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/Trie.java @@ -30,16 +30,16 @@ import org.apache.cassandra.index.sasi.utils.trie.Cursor.Decision; */ /** - * Defines the interface for a prefix tree, an ordered tree data structure. For + * Defines the interface for a prefix tree, an ordered tree data structure. For * more information, see <a href="http://en.wikipedia.org/wiki/Trie";>Tries</a>. - * + * * @author Roger Kapsi * @author Sam Berlin */ public interface Trie<K, V> extends SortedMap<K, V> { /** - * Returns the {@link Map.Entry} whose key is closest in a bitwise XOR + * Returns the {@link Map.Entry} whose key is closest in a bitwise XOR * metric to the given key. This is NOT lexicographic closeness. * For example, given the keys: * @@ -48,103 +48,103 @@ public interface Trie<K, V> extends SortedMap<K, V> * <li>H = 1001000 * <li>L = 1001100 * </ol> - * - * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would - * return 'L', because the XOR distance between D & L is smaller - * than the XOR distance between D & H. - * + * + * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would + * return 'L', because the XOR distance between D & L is smaller + * than the XOR distance between D & H. + * * @return The {@link Map.Entry} whose key is closest in a bitwise XOR metric * to the provided key. */ Map.Entry<K, V> select(K key); - + /** - * Returns the key that is closest in a bitwise XOR metric to the + * Returns the key that is closest in a bitwise XOR metric to the * provided key. This is NOT lexicographic closeness! - * + * * For example, given the keys: - * + * * <ol> * <li>D = 1000100 * <li>H = 1001000 * <li>L = 1001100 * </ol> - * - * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would - * return 'L', because the XOR distance between D & L is smaller - * than the XOR distance between D & H. - * + * + * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would + * return 'L', because the XOR distance between D & L is smaller + * than the XOR distance between D & H. + * * @return The key that is closest in a bitwise XOR metric to the provided key. */ @SuppressWarnings("unused") K selectKey(K key); - + /** - * Returns the value whose key is closest in a bitwise XOR metric to + * Returns the value whose key is closest in a bitwise XOR metric to * the provided key. This is NOT lexicographic closeness! - * + * * For example, given the keys: - * + * * <ol> * <li>D = 1000100 * <li>H = 1001000 * <li>L = 1001100 * </ol> - * - * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would - * return 'L', because the XOR distance between D & L is smaller - * than the XOR distance between D & H. - * + * + * If the {@link Trie} contained 'H' and 'L', a lookup of 'D' would + * return 'L', because the XOR distance between D & L is smaller + * than the XOR distance between D & H. + * * @return The value whose key is closest in a bitwise XOR metric * to the provided key. */ @SuppressWarnings("unused") V selectValue(K key); - + /** * Iterates through the {@link Trie}, starting with the entry whose bitwise * value is closest in an XOR metric to the given key. After the closest * entry is found, the {@link Trie} will call select on that entry and continue * calling select for each entry (traversing in order of XOR closeness, * NOT lexicographically) until the cursor returns {@link Decision#EXIT}. - * + * * <p>The cursor can return {@link Decision#CONTINUE} to continue traversing. - * + * * <p>{@link Decision#REMOVE_AND_EXIT} is used to remove the current element * and stop traversing. - * + * * <p>Note: The {@link Decision#REMOVE} operation is not supported. - * - * @return The entry the cursor returned {@link Decision#EXIT} on, or null + * + * @return The entry the cursor returned {@link Decision#EXIT} on, or null * if it continued till the end. */ Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor); - + /** - * Traverses the {@link Trie} in lexicographical order. + * Traverses the {@link Trie} in lexicographical order. * {@link Cursor#select(java.util.Map.Entry)} will be called on each entry. - * - * <p>The traversal will stop when the cursor returns {@link Decision#EXIT}, - * {@link Decision#CONTINUE} is used to continue traversing and - * {@link Decision#REMOVE} is used to remove the element that was selected + * + * <p>The traversal will stop when the cursor returns {@link Decision#EXIT}, + * {@link Decision#CONTINUE} is used to continue traversing and + * {@link Decision#REMOVE} is used to remove the element that was selected * and continue traversing. - * + * * <p>{@link Decision#REMOVE_AND_EXIT} is used to remove the current element * and stop traversing. - * - * @return The entry the cursor returned {@link Decision#EXIT} on, or null + * + * @return The entry the cursor returned {@link Decision#EXIT} on, or null * if it continued till the end. */ Map.Entry<K,V> traverse(Cursor<? super K, ? super V> cursor); - + /** - * Returns a view of this {@link Trie} of all elements that are prefixed + * Returns a view of this {@link Trie} of all elements that are prefixed * by the given key. - * - * <p>In a {@link Trie} with fixed size keys, this is essentially a + * + * <p>In a {@link Trie} with fixed size keys, this is essentially a * {@link #get(Object)} operation. - * - * <p>For example, if the {@link Trie} contains 'Anna', 'Anael', + * + * <p>For example, if the {@link Trie} contains 'Anna', 'Anael', * 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then * a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'. */ http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java b/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java index c258dd2..84080c2 100644 --- a/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java +++ b/src/java/org/apache/cassandra/index/sasi/utils/trie/Tries.java @@ -29,7 +29,7 @@ package org.apache.cassandra.index.sasi.utils.trie; */ public class Tries { - /** + /** * Returns true if bitIndex is a {@link KeyAnalyzer#OUT_OF_BOUNDS_BIT_KEY} */ static boolean isOutOfBoundsIndex(int bitIndex) @@ -37,7 +37,7 @@ public class Tries return bitIndex == KeyAnalyzer.OUT_OF_BOUNDS_BIT_KEY; } - /** + /** * Returns true if bitIndex is a {@link KeyAnalyzer#EQUAL_BIT_KEY} */ static boolean isEqualBitKey(int bitIndex) @@ -45,17 +45,17 @@ public class Tries return bitIndex == KeyAnalyzer.EQUAL_BIT_KEY; } - /** - * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY} + /** + * Returns true if bitIndex is a {@link KeyAnalyzer#NULL_BIT_KEY} */ static boolean isNullBitKey(int bitIndex) { return bitIndex == KeyAnalyzer.NULL_BIT_KEY; } - /** - * Returns true if the given bitIndex is valid. Indices - * are considered valid if they're between 0 and + /** + * Returns true if the given bitIndex is valid. Indices + * are considered valid if they're between 0 and * {@link Integer#MAX_VALUE} */ static boolean isValidBitIndex(int bitIndex) @@ -72,7 +72,7 @@ public class Tries } /** - * Throws a {@link NullPointerException} with the given message if + * Throws a {@link NullPointerException} with the given message if * the argument is null. */ static <T> T notNull(T o, String message) http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java b/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java index b02e29f..e668b75 100644 --- a/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java +++ b/src/java/org/apache/cassandra/io/sstable/CQLSSTableWriter.java @@ -290,7 +290,8 @@ public class CQLSSTableWriter implements Closeable { int size = Math.min(values.size(), boundNames.size()); List<ByteBuffer> rawValues = new ArrayList<>(size); - for (int i = 0; i < size; i++) { + for (int i = 0; i < size; i++) + { ColumnSpecification spec = boundNames.get(i); rawValues.add(values.get(spec.name.toString())); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/68d25266/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java b/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java index d2c83bf..87d2a6e 100644 --- a/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java +++ b/src/java/org/apache/cassandra/io/sstable/format/SSTableReader.java @@ -1500,7 +1500,8 @@ public abstract class SSTableReader extends SSTable implements SelfRefCounted<SS protected RowIndexEntry getCachedPosition(KeyCacheKey unifiedKey, boolean updateStats) { - if (keyCache != null && keyCache.getCapacity() > 0 && metadata.params.caching.cacheKeys()) { + if (keyCache != null && keyCache.getCapacity() > 0 && metadata.params.caching.cacheKeys()) + { if (updateStats) { RowIndexEntry cachedEntry = keyCache.get(unifiedKey);
