diff options
6 files changed, 934 insertions, 0 deletions
diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF index 23ce1dafa2..df4a39c883 100644 --- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF +++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF @@ -41,6 +41,7 @@ Import-Package: com.googlecode.javaewah;version="[1.1.6,2.0.0)", org.eclipse.jgit.internal.storage.dfs;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.file;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.io;version="[6.5.0,6.6.0)", + org.eclipse.jgit.internal.storage.memory;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.pack;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.storage.reftable;version="[6.5.0,6.6.0)", org.eclipse.jgit.internal.transport.connectivity;version="[6.5.0,6.6.0)", diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/memory/TernarySearchTreeTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/memory/TernarySearchTreeTest.java new file mode 100644 index 0000000000..623c92fc90 --- /dev/null +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/memory/TernarySearchTreeTest.java @@ -0,0 +1,330 @@ +/* + * Copyright (C) 2021, Matthias Sohn <matthias.sohn@sap.com> and others + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.storage.memory; + +import static java.util.Map.entry; +import static org.junit.Assert.assertArrayEquals; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertNull; +import static org.junit.Assert.assertThrows; +import static org.junit.Assert.assertTrue; + +import java.util.Arrays; +import java.util.List; +import java.util.Map; +import java.util.function.Consumer; +import java.util.stream.Collectors; +import java.util.stream.StreamSupport; + +import org.junit.Before; +import org.junit.Test; + +public class TernarySearchTreeTest { + + private TernarySearchTree<String> tree; + + @Before + public void setup() { + tree = new TernarySearchTree<>(); + tree.insert("foo", "1"); + tree.insert("bar", "2"); + tree.insert("foobar", "3"); + tree.insert("foobaz", "4"); + tree.insert("johndoe", "5"); + } + + @Test + public void testInsert() { + int initialSize = tree.size(); + tree.insert("foobarbaz", "6"); + assertEquals(initialSize + 1, tree.size()); + assertEquals("6", tree.get("foobarbaz")); + } + + @Test + public void testBatchInsert() { + Map<String, String> m = Map.ofEntries( + entry("refs/heads/master", "master"), + entry("refs/heads/stable-1.0", "stable-1.0"), + entry("refs/heads/stable-2.1", "stable-2.1"), + entry("refs/heads/stable-2.0", "stable-2.0"), + entry("refs/heads/stable-1.1", "stable-1.1"), + entry("refs/heads/stable-2.2", "stable-2.2"), + entry("aaa", "aaa"), entry("refs/tags/xyz", "xyz"), + entry("refs/tags/v1.1", "v1.1"), + entry("refs/tags/v2.2", "v2.2"), + entry("refs/tags/v1.0", "v1.0"), + entry("refs/tags/v2.1", "v2.1"), + entry("refs/tags/v2.0", "v2.0")); + tree.insert(m); + assertArrayEquals( + new String[] { "refs/heads/master", "refs/heads/stable-1.0", + "refs/heads/stable-1.1", "refs/heads/stable-2.0", + "refs/heads/stable-2.1", "refs/heads/stable-2.2" }, + toArray(tree.getKeysWithPrefix("refs/heads/"))); + assertArrayEquals( + new String[] { "refs/tags/v1.0", "refs/tags/v1.1", + "refs/tags/v2.0", "refs/tags/v2.1", "refs/tags/v2.2", + "refs/tags/xyz" }, + toArray(tree.getKeysWithPrefix("refs/tags/"))); + assertEquals("aaa", tree.get("aaa")); + } + + @Test + public void testInsertWithNullKey() { + Exception exception = assertThrows(IllegalArgumentException.class, + () -> { + tree.insert(null, "42"); + }); + assertTrue(exception.getMessage() + .contains("TernarySearchTree key must not be null or empty")); + } + + @Test + public void testOverwriteValue() { + int initialSize = tree.size(); + tree.insert("foo", "overwritten"); + assertEquals(initialSize, tree.size()); + assertEquals("overwritten", tree.get("foo")); + } + + @Test + public void testInsertNullValue() { + Exception exception = assertThrows(IllegalArgumentException.class, + () -> { + tree.insert("xxx", null); + }); + assertTrue(exception.getMessage() + .contains("cannot insert null value into TernarySearchTree")); + } + + @Test + public void testReloadAll() { + Map<String, String> map = Map.of("foo", "foo-value", "bar", + "bar-value"); + tree.replace(map.entrySet()); + assertArrayEquals(new String[] { "bar", "foo" }, + toArray(tree.getKeys())); + } + + @Test + public void testReload() { + int initialSize = tree.size(); + Map<String, String> map = Map.of("foo", "foo-value", "bar", + "bar-value"); + tree.reload(map.entrySet()); + assertEquals("foo-value", tree.get("foo")); + assertEquals("bar-value", tree.get("bar")); + assertEquals("3", tree.get("foobar")); + assertEquals("4", tree.get("foobaz")); + assertEquals("5", tree.get("johndoe")); + assertEquals(initialSize, tree.size()); + } + + @Test + public void testContains() { + assertTrue(tree.contains("foo")); + assertTrue(tree.contains("foobaz")); + assertFalse(tree.contains("ship")); + } + + @Test + public void testContainsWithNullKey() { + Exception exception = assertThrows(IllegalArgumentException.class, + () -> { + tree.contains(null); + }); + assertTrue(exception.getMessage() + .contains("TernarySearchTree key must not be null or empty")); + } + + @Test + public void testGet() { + assertEquals("1", tree.get("foo")); + assertEquals("5", tree.get("johndoe")); + assertNull(tree.get("ship")); + } + + @Test + public void testGetWithNullKey() { + Exception exception = assertThrows(IllegalArgumentException.class, + () -> { + tree.get(null); + }); + assertTrue(exception.getMessage() + .contains("TernarySearchTree key must not be null or empty")); + } + + @Test + public void testDeleteExisting() { + int initialSize = tree.size(); + tree.delete("foo"); + assertNull(tree.get("foo")); + assertEquals(initialSize - 1, tree.size()); + tree.delete("cake"); + assertEquals(4, tree.size()); + } + + @Test + public void testDeleteNonExisting() { + int initialSize = tree.size(); + tree.delete("non-existent-key"); + assertEquals(initialSize, tree.size()); + } + + @Test + public void testDeleteWithNullKey() { + Exception exception = assertThrows(IllegalArgumentException.class, + () -> { + tree.delete((String) null); + }); + assertTrue(exception.getMessage() + .contains("TernarySearchTree key must not be null or empty")); + } + + @Test + public void testDeleteMultiple() { + int initialSize = tree.size(); + List<String> keys = toList(tree.getKeys()); + keys.remove("foobar"); + keys.remove("johndoe"); + tree.delete(Arrays.asList(new String[] { "foobar", "johndoe" })); + assertEquals(initialSize - 2, tree.size()); + assertArrayEquals(keys.toArray(), toArray(tree.getKeys())); + } + + @Test + public void testClear() { + assertEquals(5, tree.size()); + tree.clear(); + assertEquals(0, tree.size()); + tree.getKeys().forEach(new Consumer<String>() { + + @Override + public void accept(String t) { + throw new IllegalStateException("should find no key"); + } + }); + } + + @Test + public void testKeyLongestPrefix() { + assertEquals("foobar", tree.keyLongestPrefixOf("foobari")); + assertEquals("foo", tree.keyLongestPrefixOf("foocake")); + assertEquals("", tree.keyLongestPrefixOf("faabar")); + assertEquals("johndoe", tree.keyLongestPrefixOf("johndoea")); + assertEquals("", tree.keyLongestPrefixOf("wxy")); + assertNull(tree.keyLongestPrefixOf("")); + assertNull(tree.keyLongestPrefixOf(null)); + } + + @Test + public void testGetKeys() { + assertArrayEquals( + new String[] { "bar", "foo", "foobar", "foobaz", "johndoe" }, + toArray(tree.getKeys())); + } + + @Test + public void testGetKeysWithPrefix() { + assertArrayEquals(new String[] { "foo", "foobar", "foobaz" }, + toArray(tree.getKeysWithPrefix("foo"))); + assertArrayEquals(new String[] { "johndoe" }, + toArray(tree.getKeysWithPrefix("john"))); + assertArrayEquals(new String[0], + toArray(tree.getKeysWithPrefix("cake"))); + assertArrayEquals( + new String[] { "bar", "foo", "foobar", "foobaz", "johndoe" }, + toArray(tree.getKeysWithPrefix(""))); + assertArrayEquals(new String[0], toArray(tree.getKeysWithPrefix(null))); + } + + @Test + public void testGetWithPrefixFoo() { + Map<String, String> result = tree.getWithPrefix("foo"); + assertEquals(3, result.size()); + assertEquals("1", result.get("foo")); + assertEquals("3", result.get("foobar")); + assertEquals("4", result.get("foobaz")); + } + + @Test + public void testGetWithPrefixNotFound() { + Map<String, String> result = tree.getWithPrefix("cheese"); + assertEquals(0, result.size()); + } + + @Test + public void testGetWithPrefixNull() { + Map<String, String> result = tree.getWithPrefix(null); + assertEquals(0, result.size()); + } + + @Test + public void testGetWithPrefixEmptyPrefix() { + Map<String, String> result = tree.getWithPrefix(""); + assertEquals(5, result.size()); + assertEquals("1", result.get("foo")); + assertEquals("2", result.get("bar")); + assertEquals("3", result.get("foobar")); + assertEquals("4", result.get("foobaz")); + assertEquals("5", result.get("johndoe")); + } + + @Test + public void testGetValuesWithPrefixFoo() { + List<String> result = tree.getValuesWithPrefix("foo"); + assertEquals(3, result.size()); + assertArrayEquals(new String[] { "1", "3", "4" }, + result.toArray()); + } + + @Test + public void testGetValuesWithPrefixNotFound() { + List<String> result = tree.getValuesWithPrefix("cheese"); + assertEquals(0, result.size()); + } + + @Test + public void testGetValuesWithPrefixNull() { + List<String> result = tree.getValuesWithPrefix(null); + assertEquals(0, result.size()); + } + + @Test + public void testGetValuesWithPrefixEmptyPrefix() { + List<String> result = tree.getValuesWithPrefix(""); + assertEquals(5, result.size()); + assertArrayEquals(new String[] { "2", "1", "3", "4", "5" }, + result.toArray()); + } + + @Test + public void testGetKeysMatching() { + assertArrayEquals(new String[] { "foobar" }, + toArray(tree.getKeysMatching("fo?bar"))); + assertArrayEquals(new String[] { "foobar", "foobaz" }, + toArray(tree.getKeysMatching("fooba?"))); + assertArrayEquals(new String[] { "foobar", "foobaz" }, + toArray(tree.getKeysMatching("?o?ba?"))); + assertArrayEquals(new String[0], toArray(tree.getKeysMatching(""))); + assertArrayEquals(new String[0], toArray(tree.getKeysMatching(null))); + } + + private static List<String> toList(Iterable<String> iter) { + return StreamSupport.stream(iter.spliterator(), false) + .collect(Collectors.toList()); + } + + private static String[] toArray(Iterable<String> iter) { + return toList(iter).toArray(new String[0]); + } +} diff --git a/org.eclipse.jgit/META-INF/MANIFEST.MF b/org.eclipse.jgit/META-INF/MANIFEST.MF index 453a716d8f..1fad623a7b 100644 --- a/org.eclipse.jgit/META-INF/MANIFEST.MF +++ b/org.eclipse.jgit/META-INF/MANIFEST.MF @@ -101,6 +101,8 @@ Export-Package: org.eclipse.jgit.annotations;version="6.5.0", x-friends:="org.eclipse.jgit.junit, org.eclipse.jgit.test, org.eclipse.jgit.pgm", + org.eclipse.jgit.internal.storage.memory;version="6.5.0"; + x-friends:="org.eclipse.jgit.test", org.eclipse.jgit.internal.storage.pack;version="6.5.0"; x-friends:="org.eclipse.jgit.junit, org.eclipse.jgit.test, diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties index 836213286d..bdf35d8d73 100644 --- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties +++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties @@ -360,6 +360,8 @@ illegalArgumentNotA=Not {0} illegalCombinationOfArguments=The combination of arguments {0} and {1} is not allowed illegalHookName=Illegal hook name {0} illegalPackingPhase=Illegal packing phase {0} +illegalTernarySearchTreeKey=TernarySearchTree key must not be null or empty +illegalTernarySearchTreeValue=cannot insert null value into TernarySearchTree incorrectHashFor=Incorrect hash for {0}; computed {1} as a {2} from {3} bytes. incorrectOBJECT_ID_LENGTH=Incorrect OBJECT_ID_LENGTH. indexFileCorruptedNegativeBucketCount=Invalid negative bucket count read from pack v2 index file: {0} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java index f4f91f8aab..b502a1a98b 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java @@ -388,6 +388,8 @@ public class JGitText extends TranslationBundle { /***/ public String illegalCombinationOfArguments; /***/ public String illegalHookName; /***/ public String illegalPackingPhase; + /***/ public String illegalTernarySearchTreeKey; + /***/ public String illegalTernarySearchTreeValue; /***/ public String incorrectHashFor; /***/ public String incorrectOBJECT_ID_LENGTH; /***/ public String indexFileCorruptedNegativeBucketCount; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/memory/TernarySearchTree.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/memory/TernarySearchTree.java new file mode 100644 index 0000000000..1ac6627360 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/memory/TernarySearchTree.java @@ -0,0 +1,597 @@ +/* + * Copyright (C) 2021, Matthias Sohn <matthias.sohn@sap.com> and others + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://www.eclipse.org/org/documents/edl-v10.php. + * + * SPDX-License-Identifier: BSD-3-Clause + */ +package org.eclipse.jgit.internal.storage.memory; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Queue; +import java.util.concurrent.atomic.AtomicInteger; +import java.util.concurrent.locks.ReadWriteLock; +import java.util.concurrent.locks.ReentrantReadWriteLock; + +import org.eclipse.jgit.annotations.Nullable; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.util.StringUtils; + +/** + * A ternary search tree with String keys and generic values. + * + * TernarySearchTree is a type of trie (sometimes called a prefix tree) where + * nodes are arranged in a manner similar to a binary search tree, but with up + * to three children rather than the binary tree's limit of two. Like other + * prefix trees, a ternary search tree can be used as an associative map + * structure with the ability for incremental string search. However, ternary + * search trees are more space efficient compared to standard prefix trees, at + * the cost of speed. + * + * Keys must not be null or empty. Values cannot be null. + * + * This class is thread safe. + * + * @param <Value> + * type of values in this tree + * @since 6.5 + */ +public final class TernarySearchTree<Value> { + + private static final char WILDCARD = '?'; + + private static class Node<Value> { + final char c; + + Node<Value> lo, eq, hi; + + Value val; + + Node(char c) { + this.c = c; + } + + boolean hasValue() { + return val != null; + } + } + + /** + * Loader to load key-value pairs to be cached in the tree + * + * @param <Value> + * type of values + */ + public static interface Loader<Value> { + /** + * Load map of all key value pairs + * + * @return map of all key value pairs to cache in the tree + */ + Map<String, Value> loadAll(); + } + + private static void validateKey(String key) { + if (StringUtils.isEmptyOrNull(key)) { + throw new IllegalArgumentException( + JGitText.get().illegalTernarySearchTreeKey); + } + } + + private static <V> void validateValue(V value) { + if (value == null) { + throw new IllegalArgumentException( + JGitText.get().illegalTernarySearchTreeValue); + } + } + + private final ReadWriteLock lock; + + private final AtomicInteger size = new AtomicInteger(0); + + private Node<Value> root; + + /** + * Construct a new ternary search tree + */ + public TernarySearchTree() { + lock = new ReentrantReadWriteLock(); + } + + /** + * Get the lock guarding read and write access to the cache. + * + * @return lock guarding read and write access to the cache + */ + public ReadWriteLock getLock() { + return lock; + } + + /** + * Replace the tree with a new tree containing all entries provided by an + * iterable + * + * @param loader + * iterable providing key-value pairs to load + * @return number of key-value pairs after replacing finished + */ + public int replace(Iterable<Entry<String, Value>> loader) { + lock.writeLock().lock(); + try { + clear(); + for (Entry<String, Value> e : loader) { + insertImpl(e.getKey(), e.getValue()); + } + } finally { + lock.writeLock().unlock(); + } + return size.get(); + } + + /** + * Reload the tree entries provided by loader + * + * @param loader + * iterable providing key-value pairs to load + * @return number of key-value pairs + */ + public int reload(Iterable<Entry<String, Value>> loader) { + lock.writeLock().lock(); + try { + for (Entry<String, Value> e : loader) { + insertImpl(e.getKey(), e.getValue()); + } + } finally { + lock.writeLock().unlock(); + } + return size.get(); + } + + /** + * Delete entries + * + * @param delete + * iterable providing keys of entries to be deleted + * @return number of key-value pairs + */ + public int delete(Iterable<String> delete) { + lock.writeLock().lock(); + try { + for (String s : delete) { + delete(s); + } + } finally { + lock.writeLock().unlock(); + } + return size.get(); + } + + /** + * Get the number of key value pairs in this trie + * + * @return number of key value pairs in this trie + */ + public int size() { + return size.get(); + } + + /** + * Get the value associated to a key or {@code null}. + * + * @param key + * the key + * @return the value associated to this key + */ + @Nullable + public Value get(String key) { + validateKey(key); + lock.readLock().lock(); + try { + Node<Value> node = get(root, key, 0); + if (node == null) { + return null; + } + return node.val; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Check whether this tree contains the given key. + * + * @param key + * a key + * @return whether this tree contains this key + */ + public boolean contains(String key) { + return get(key) != null; + } + + /** + * Insert a key-value pair. If the key already exists the old value is + * overwritten. + * + * @param key + * the key + * @param value + * the value + * @return number of key-value pairs after adding the entry + */ + public int insert(String key, Value value) { + lock.writeLock().lock(); + try { + insertImpl(key, value); + return size.get(); + } finally { + lock.writeLock().unlock(); + } + } + + /** + * Insert map of key-value pairs. Values of existing keys are overwritten. + * Use this method to insert multiple key-value pairs. + * + * @param map + * map of key-value pairs to insert + * @return number of key-value pairs after adding entries + */ + public int insert(Map<String, Value> map) { + lock.writeLock().lock(); + try { + for (Entry<String, Value> e : map.entrySet()) { + insertImpl(e.getKey(), e.getValue()); + } + return size.get(); + } finally { + lock.writeLock().unlock(); + } + } + + private void insertImpl(String key, Value value) { + validateValue(value); + if (!contains(key)) { + size.addAndGet(1); + } + root = insert(root, key, value, 0); + } + + /** + * Delete a key-value pair. Does nothing if the key doesn't exist. + * + * @param key + * the key + * @return number of key-value pairs after the deletion + */ + public int delete(String key) { + lock.writeLock().lock(); + try { + if (contains(key)) { + size.addAndGet(-1); + root = insert(root, key, null, 0); + } + return size.get(); + } finally { + lock.writeLock().unlock(); + } + } + + /** + * Remove all key value pairs from this tree + */ + public void clear() { + lock.writeLock().lock(); + try { + size.set(0); + root = null; + } finally { + lock.writeLock().unlock(); + } + } + + /** + * Find the key which is the longest prefix of the given query string. + * + * @param query + * @return the key which is the longest prefix of the given query string or + * {@code null} if none exists. + */ + @Nullable + public String keyLongestPrefixOf(String query) { + if (StringUtils.isEmptyOrNull(query)) { + return null; + } + lock.readLock().lock(); + try { + int length = 0; + Node<Value> node = root; + int i = 0; + while (node != null && i < query.length()) { + char c = query.charAt(i); + if (node.c > c) { + node = node.lo; + } else if (node.c < c) { + node = node.hi; + } else { + i++; + if (node.hasValue()) { + length = i; + } + node = node.eq; + } + } + return query.substring(0, length); + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all keys. + * + * @return all keys + */ + public Iterable<String> getKeys() { + Queue<String> queue = new LinkedList<>(); + lock.readLock().lock(); + try { + findKeysWithPrefix(root, new StringBuilder(), queue); + return queue; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get keys starting with given prefix + * + * @param prefix + * key prefix + * @return keys starting with given prefix + */ + public Iterable<String> getKeysWithPrefix(String prefix) { + Queue<String> keys = new LinkedList<>(); + if (prefix == null) { + return keys; + } + if (prefix.isEmpty()) { + return getKeys(); + } + lock.readLock().lock(); + try { + validateKey(prefix); + Node<Value> node = get(root, prefix, 0); + if (node == null) { + return keys; + } + if (node.hasValue()) { + keys.add(prefix); + } + findKeysWithPrefix(node.eq, new StringBuilder(prefix), keys); + return keys; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all entries. + * + * @return all entries + */ + public Map<String, Value> getAll() { + Map<String, Value> entries = new HashMap<>(); + lock.readLock().lock(); + try { + findWithPrefix(root, new StringBuilder(), entries); + return entries; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all values. + * + * @return all values + */ + public List<Value> getAllValues() { + List<Value> values = new ArrayList<>(); + lock.readLock().lock(); + try { + findValuesWithPrefix(root, new StringBuilder(), values); + return values; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all entries with given prefix + * + * @param prefix + * key prefix + * @return entries with given prefix + */ + public Map<String, Value> getWithPrefix(String prefix) { + Map<String, Value> entries = new HashMap<>(); + if (prefix == null) { + return entries; + } + if (prefix.isEmpty()) { + return getAll(); + } + lock.readLock().lock(); + try { + validateKey(prefix); + Node<Value> node = get(root, prefix, 0); + if (node == null) { + return entries; + } + if (node.hasValue()) { + entries.put(prefix, node.val); + } + findWithPrefix(node.eq, new StringBuilder(prefix), entries); + return entries; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get all values with given key prefix + * + * @param prefix + * key prefix + * @return entries with given prefix + */ + public List<Value> getValuesWithPrefix(String prefix) { + List<Value> values = new ArrayList<>(); + if (prefix == null) { + return values; + } + if (prefix.isEmpty()) { + return getAllValues(); + } + lock.readLock().lock(); + try { + validateKey(prefix); + Node<Value> node = get(root, prefix, 0); + if (node == null) { + return values; + } + if (node.hasValue()) { + values.add(node.val); + } + findValuesWithPrefix(node.eq, new StringBuilder(prefix), values); + return values; + } finally { + lock.readLock().unlock(); + } + } + + /** + * Get keys matching given pattern using '?' as wildcard character. + * + * @param pattern + * search pattern + * @return keys matching given pattern. + */ + public Iterable<String> getKeysMatching(String pattern) { + Queue<String> keys = new LinkedList<>(); + lock.readLock().lock(); + try { + findKeysWithPrefix(root, new StringBuilder(), 0, pattern, keys); + return keys; + } finally { + lock.readLock().unlock(); + } + } + + private Node<Value> get(Node<Value> node, String key, int depth) { + if (node == null) { + return null; + } + char c = key.charAt(depth); + if (node.c > c) { + return get(node.lo, key, depth); + } else if (node.c < c) { + return get(node.hi, key, depth); + } else if (depth < key.length() - 1) { + return get(node.eq, key, depth + 1); + } else { + return node; + } + } + + private Node<Value> insert(Node<Value> node, String key, Value val, + int depth) { + char c = key.charAt(depth); + if (node == null) { + node = new Node<>(c); + } + if (node.c > c) { + node.lo = insert(node.lo, key, val, depth); + } else if (node.c < c) { + node.hi = insert(node.hi, key, val, depth); + } else if (depth < key.length() - 1) { + node.eq = insert(node.eq, key, val, depth + 1); + } else { + node.val = val; + } + return node; + } + + private void findKeysWithPrefix(Node<Value> node, StringBuilder prefix, + Queue<String> keys) { + if (node == null) { + return; + } + findKeysWithPrefix(node.lo, prefix, keys); + if (node.hasValue()) { + keys.add(prefix.toString() + node.c); + } + findKeysWithPrefix(node.eq, prefix.append(node.c), keys); + prefix.deleteCharAt(prefix.length() - 1); + findKeysWithPrefix(node.hi, prefix, keys); + } + + private void findWithPrefix(Node<Value> node, StringBuilder prefix, + Map<String, Value> entries) { + if (node == null) { + return; + } + findWithPrefix(node.lo, prefix, entries); + if (node.hasValue()) { + entries.put(prefix.toString() + node.c, node.val); + } + findWithPrefix(node.eq, prefix.append(node.c), entries); + prefix.deleteCharAt(prefix.length() - 1); + findWithPrefix(node.hi, prefix, entries); + } + + private void findValuesWithPrefix(Node<Value> node, StringBuilder prefix, + List<Value> values) { + if (node == null) { + return; + } + findValuesWithPrefix(node.lo, prefix, values); + if (node.hasValue()) { + values.add(node.val); + } + findValuesWithPrefix(node.eq, prefix.append(node.c), values); + prefix.deleteCharAt(prefix.length() - 1); + findValuesWithPrefix(node.hi, prefix, values); + } + + private void findKeysWithPrefix(Node<Value> node, StringBuilder prefix, + int i, String pattern, Queue<String> keys) { + if (node == null || StringUtils.isEmptyOrNull(pattern)) { + return; + } + char c = pattern.charAt(i); + if (c == WILDCARD || node.c > c) { + findKeysWithPrefix(node.lo, prefix, i, pattern, keys); + } + if (c == WILDCARD || node.c == c) { + if (i == pattern.length() - 1 && node.hasValue()) { + keys.add(prefix.toString() + node.c); + } + if (i < pattern.length() - 1) { + findKeysWithPrefix(node.eq, prefix.append(node.c), i + 1, + pattern, keys); + prefix.deleteCharAt(prefix.length() - 1); + } + } + if (c == WILDCARD || node.c < c) { + findKeysWithPrefix(node.hi, prefix, i, pattern, keys); + } + } +} |