This is an automated email from the ASF dual-hosted git repository. hulee pushed a commit to branch zooscalability in repository https://gitbox.apache.org/repos/asf/helix.git
commit eae041626a4a9fb5c6fadaa1313a629a4a62e3a8 Author: Neal Sun <[email protected]> AuthorDate: Mon Feb 10 16:41:11 2020 -0800 Add TrieRoutingData constructor (#731) This PR adds a constructor to TrieRoutingData. The constructor takes in a mapping of sharding keys to realm addresses and parses it into a trie. Also, TrieRoutingData now treats sharding keys without leading slashes as invalid. Related changes are made due to the addition of the constructor: TrieNode is made private; missing logic is added for refreshRoutingData in ZkMetadataStoreDirectory. --- .../metadatastore/MetadataStoreRoutingData.java | 7 +- .../helix/rest/metadatastore/TrieRoutingData.java | 201 ++++++++++++--- .../metadatastore/ZkMetadataStoreDirectory.java | 36 ++- .../rest/metadatastore/TestTrieRoutingData.java | 282 ++++++++++++++------- 4 files changed, 380 insertions(+), 146 deletions(-) diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java index 237e9b6..8d8b7e3 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/MetadataStoreRoutingData.java @@ -22,7 +22,6 @@ package org.apache.helix.rest.metadatastore; import java.util.Map; import java.util.NoSuchElementException; - public interface MetadataStoreRoutingData { /** * Given a path, return all the "metadata store sharding key-metadata store realm address" pairs @@ -33,15 +32,17 @@ public interface MetadataStoreRoutingData { * @param path - the path where the search is conducted * @return all "sharding key-realm address" pairs where the sharding keys contain the given * path if the path is valid; empty mapping otherwise + * @throws IllegalArgumentException - when the path is invalid */ - Map<String, String> getAllMappingUnderPath(String path); + Map<String, String> getAllMappingUnderPath(String path) throws IllegalArgumentException; /** * Given a path, return the realm address corresponding to the sharding key contained in the * path. If the path doesn't contain a sharding key, throw NoSuchElementException. * @param path - the path where the search is conducted * @return the realm address corresponding to the sharding key contained in the path + * @throws IllegalArgumentException - when the path is invalid * @throws NoSuchElementException - when the path doesn't contain a sharding key */ - String getMetadataStoreRealm(String path) throws NoSuchElementException; + String getMetadataStoreRealm(String path) throws IllegalArgumentException, NoSuchElementException; } diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java index b89a5f9..28add4c 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java @@ -23,8 +23,10 @@ import java.util.ArrayDeque; import java.util.Collections; import java.util.Deque; import java.util.HashMap; +import java.util.List; import java.util.Map; import java.util.NoSuchElementException; +import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataException; /** * This is a class that uses a data structure similar to trie to represent metadata store routing @@ -37,15 +39,26 @@ public class TrieRoutingData implements MetadataStoreRoutingData { private final TrieNode _rootNode; - // TODO: THIS IS A TEMPORARY PLACEHOLDER. A proper constructor will be created, which will not - // take in a TrieNode; it instead initializes the rootNode and creates a trie based on - // some input data. The constructor is blocked by the implementation of RoutingDataAccessor, and - // will therefore be implemented later. - public TrieRoutingData(TrieNode rootNode) { - _rootNode = rootNode; + public TrieRoutingData(Map<String, List<String>> routingData) throws InvalidRoutingDataException { + if (routingData == null || routingData.isEmpty()) { + throw new InvalidRoutingDataException("routingData cannot be null or empty"); + } + + if (isRootShardingKey(routingData)) { + Map.Entry<String, List<String>> entry = routingData.entrySet().iterator().next(); + _rootNode = new TrieNode(Collections.emptyMap(), "/", true, entry.getKey()); + } else { + _rootNode = new TrieNode(new HashMap<>(), "/", false, ""); + constructTrie(routingData); + } } - public Map<String, String> getAllMappingUnderPath(String path) { + public Map<String, String> getAllMappingUnderPath(String path) throws IllegalArgumentException { + if (path.isEmpty() || !path.substring(0, 1).equals(DELIMITER)) { + throw new IllegalArgumentException("Provided path is empty or does not have a leading \"" + + DELIMITER + "\" character: " + path); + } + TrieNode curNode; try { curNode = findTrieNode(path, false); @@ -58,10 +71,10 @@ public class TrieRoutingData implements MetadataStoreRoutingData { nodeStack.push(curNode); while (!nodeStack.isEmpty()) { curNode = nodeStack.pop(); - if (curNode._isLeaf) { - resultMap.put(curNode._name, curNode._realmAddress); + if (curNode.isShardingKey()) { + resultMap.put(curNode.getPath(), curNode.getRealmAddress()); } else { - for (TrieNode child : curNode._children.values()) { + for (TrieNode child : curNode.getChildren().values()) { nodeStack.push(child); } } @@ -69,9 +82,15 @@ public class TrieRoutingData implements MetadataStoreRoutingData { return resultMap; } - public String getMetadataStoreRealm(String path) throws NoSuchElementException { + public String getMetadataStoreRealm(String path) + throws IllegalArgumentException, NoSuchElementException { + if (path.isEmpty() || !path.substring(0, 1).equals(DELIMITER)) { + throw new IllegalArgumentException("Provided path is empty or does not have a leading \"" + + DELIMITER + "\" character: " + path); + } + TrieNode leafNode = findTrieNode(path, true); - return leafNode._realmAddress; + return leafNode.getRealmAddress(); } /** @@ -88,35 +107,28 @@ public class TrieRoutingData implements MetadataStoreRoutingData { */ private TrieNode findTrieNode(String path, boolean findLeafAlongPath) throws NoSuchElementException { - if (path.equals(DELIMITER) || path.equals("")) { - if (findLeafAlongPath && !_rootNode._isLeaf) { + if (path.equals(DELIMITER)) { + if (findLeafAlongPath && !_rootNode.isShardingKey()) { throw new NoSuchElementException("No leaf node found along the path. Path: " + path); } return _rootNode; } - String[] splitPath; - if (path.substring(0, 1).equals(DELIMITER)) { - splitPath = path.substring(1).split(DELIMITER, 0); - } else { - splitPath = path.split(DELIMITER, 0); - } - TrieNode curNode = _rootNode; - if (findLeafAlongPath && curNode._isLeaf) { + if (findLeafAlongPath && curNode.isShardingKey()) { return curNode; } - Map<String, TrieNode> curChildren = curNode._children; - for (String pathSection : splitPath) { + Map<String, TrieNode> curChildren = curNode.getChildren(); + for (String pathSection : path.substring(1).split(DELIMITER, 0)) { curNode = curChildren.get(pathSection); if (curNode == null) { throw new NoSuchElementException( "The provided path is missing from the trie. Path: " + path); } - if (findLeafAlongPath && curNode._isLeaf) { + if (findLeafAlongPath && curNode.isShardingKey()) { return curNode; } - curChildren = curNode._children; + curChildren = curNode.getChildren(); } if (findLeafAlongPath) { throw new NoSuchElementException("No leaf node found along the path. Path: " + path); @@ -124,36 +136,145 @@ public class TrieRoutingData implements MetadataStoreRoutingData { return curNode; } - // TODO: THE CLASS WILL BE CHANGED TO PRIVATE ONCE THE CONSTRUCTOR IS CREATED. - static class TrieNode { + /** + * Checks for the edge case when the only sharding key in provided routing data is the delimiter + * or an empty string. When this is the case, the trie is valid and contains only one node, which + * is the root node, and the root node is a leaf node with a realm address associated with it. + * @param routingData - a mapping from "sharding keys" to "realm addresses" to be parsed into a + * trie + * @return whether the edge case is true + */ + private boolean isRootShardingKey(Map<String, List<String>> routingData) { + if (routingData.size() == 1) { + for (List<String> shardingKeys : routingData.values()) { + return shardingKeys.size() == 1 && shardingKeys.get(0).equals(DELIMITER); + } + } + + return false; + } + + /** + * Constructs a trie based on the provided routing data. It loops through all sharding keys and + * constructs the trie in a top down manner. + * @param routingData- a mapping from "sharding keys" to "realm addresses" to be parsed into a + * trie + * @throws InvalidRoutingDataException - when there is an empty sharding key (edge case that + * always renders the routing data invalid); when there is a sharding key which already + * contains a sharding key (invalid); when there is a sharding key that is a part of + * another sharding key (invalid) + */ + private void constructTrie(Map<String, List<String>> routingData) + throws InvalidRoutingDataException { + for (Map.Entry<String, List<String>> entry : routingData.entrySet()) { + if (entry.getValue().isEmpty()) { + throw new InvalidRoutingDataException( + "Realm address does not have associating sharding keys: " + entry.getKey()); + } + for (String shardingKey : entry.getValue()) { + // Missing leading delimiter is invalid + if (shardingKey.isEmpty() || !shardingKey.substring(0, 1).equals(DELIMITER)) { + throw new InvalidRoutingDataException("Sharding key does not have a leading \"" + + DELIMITER + "\" character: " + shardingKey); + } + + // Root can only be a sharding key if it's the only sharding key. Since this method is + // running, the special case has already been checked, therefore it's definitely invalid + if (shardingKey.equals(DELIMITER)) { + throw new InvalidRoutingDataException( + "There exist other sharding keys. Root cannot be a sharding key."); + } + + // Locate the next delimiter + int nextDelimiterIndex = shardingKey.indexOf(DELIMITER, 1); + int prevDelimiterIndex = 0; + String keySection = shardingKey.substring(prevDelimiterIndex + 1, + nextDelimiterIndex > 0 ? nextDelimiterIndex : shardingKey.length()); + TrieNode curNode = _rootNode; + TrieNode nextNode = curNode.getChildren().get(keySection); + + // If the key section is not the last section yet, go in the loop; if the key section is the + // last section, exit + while (nextDelimiterIndex > 0) { + // If the node is already a leaf node, the current sharding key is invalid; if the node + // doesn't exist, construct a node and continue + if (nextNode != null && nextNode.isShardingKey()) { + throw new InvalidRoutingDataException(shardingKey + " cannot be a sharding key because " + + shardingKey.substring(0, nextDelimiterIndex) + + " is its parent key and is also a sharding key."); + } else if (nextNode == null) { + nextNode = new TrieNode(new HashMap<>(), shardingKey.substring(0, nextDelimiterIndex), + false, ""); + curNode.addChild(keySection, nextNode); + } + prevDelimiterIndex = nextDelimiterIndex; + nextDelimiterIndex = shardingKey.indexOf(DELIMITER, prevDelimiterIndex + 1); + keySection = shardingKey.substring(prevDelimiterIndex + 1, + nextDelimiterIndex > 0 ? nextDelimiterIndex : shardingKey.length()); + curNode = nextNode; + nextNode = curNode.getChildren().get(keySection); + } + + // If the last node already exists, it's a part of another sharding key, making the current + // sharding key invalid + if (nextNode != null) { + throw new InvalidRoutingDataException(shardingKey + + " cannot be a sharding key because it is a parent key to another sharding key."); + } + nextNode = new TrieNode(new HashMap<>(), shardingKey, true, entry.getKey()); + curNode.addChild(keySection, nextNode); + } + } + } + + private static class TrieNode { /** * This field is a mapping between trie key and children nodes. For example, node "a" has * children "ab" and "ac", therefore the keys are "b" and "c" respectively. */ - Map<String, TrieNode> _children; + private Map<String, TrieNode> _children; /** - * This field means if the node is a terminal node in the tree sense, not the trie sense. Any - * node that has children cannot possibly be a leaf node because only the node without children - * can store information. If a node is leaf, then it shouldn't have any children. + * This field states whether the path represented by the node is a sharding key */ - final boolean _isLeaf; + private final boolean _isShardingKey; /** - * This field aligns the traditional trie design: it entails the complete path/prefix leading to - * the current node. For example, the name of root node is "/", then the name of its child node + * This field contains the complete path/prefix leading to the current node. For example, the + * name of root node is "/", then the name of its child node * is "/a", and the name of the child's child node is "/a/b". */ - final String _name; + private final String _path; /** * This field represents the data contained in a node(which represents a path), and is only * available to the terminal nodes. */ - final String _realmAddress; + private final String _realmAddress; - TrieNode(Map<String, TrieNode> children, String name, boolean isLeaf, String realmAddress) { + TrieNode(Map<String, TrieNode> children, String path, boolean isShardingKey, + String realmAddress) { _children = children; - _isLeaf = isLeaf; - _name = name; + _isShardingKey = isShardingKey; + _path = path; _realmAddress = realmAddress; } + + public Map<String, TrieNode> getChildren() { + return _children; + } + + public boolean isShardingKey() { + return _isShardingKey; + } + + public String getPath() { + return _path; + } + + public String getRealmAddress() { + return _realmAddress; + } + + public void addChild(String key, TrieNode node) { + _children.put(key, node); + } } } diff --git a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java index 85f8f4a..5a88ca9 100644 --- a/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java +++ b/helix-rest/src/main/java/org/apache/helix/rest/metadatastore/ZkMetadataStoreDirectory.java @@ -42,9 +42,9 @@ import org.apache.zookeeper.Watcher; import org.slf4j.Logger; import org.slf4j.LoggerFactory; - /** - * ZK-based MetadataStoreDirectory that listens on the routing data in routing ZKs with a update callback. + * ZK-based MetadataStoreDirectory that listens on the routing data in routing ZKs with a update + * callback. */ public class ZkMetadataStoreDirectory implements MetadataStoreDirectory, RoutingDataListener { private static final Logger LOG = LoggerFactory.getLogger(ZkMetadataStoreDirectory.class); @@ -156,34 +156,42 @@ public class ZkMetadataStoreDirectory implements MetadataStoreDirectory, Routing /** * Callback for updating the cached routing data. - * Note: this method should not synchronize on the class or the map. We do not want namespaces blocking each other. + * Note: this method should not synchronize on the class or the map. We do not want namespaces + * blocking each other. * Threadsafe map is used for _realmToShardingKeysMap. - * The global consistency of the in-memory routing data is not a requirement (eventual consistency is enough). + * The global consistency of the in-memory routing data is not a requirement (eventual consistency + * is enough). * @param namespace */ @Override public void refreshRoutingData(String namespace) { - // Safe to ignore the callback if routingDataMap is null. + // Safe to ignore the callback if any of the mapping is null. // If routingDataMap is null, then it will be populated by the constructor anyway // If routingDataMap is not null, then it's safe for the callback function to update it + if (_routingZkAddressMap == null || _routingDataMap == null + || _realmToShardingKeysMap == null) { + LOG.error("Construction is not completed! "); + return; + } // Check if namespace exists; otherwise, return as a NOP and log it if (!_routingZkAddressMap.containsKey(namespace)) { - LOG.error("Failed to refresh internally-cached routing data! Namespace not found: " + namespace); + LOG.error("Failed to refresh internally-cached routing data! Namespace not found: {}", + namespace); + return; } try { - _realmToShardingKeysMap.put(namespace, _routingDataReaderMap.get(namespace).getRoutingData()); + Map<String, List<String>> rawRoutingData = + _routingDataReaderMap.get(namespace).getRoutingData(); + _realmToShardingKeysMap.put(namespace, rawRoutingData); + + MetadataStoreRoutingData routingData = new TrieRoutingData(rawRoutingData); + _routingDataMap.put(namespace, routingData); } catch (InvalidRoutingDataException e) { - LOG.error("Failed to get routing data for namespace: " + namespace + "!"); + LOG.error("Failed to refresh cached routing data for namespace {}", namespace, e); } - if (_routingDataMap != null) { - MetadataStoreRoutingData newRoutingData = - new TrieRoutingData(new TrieRoutingData.TrieNode(null, null, false, null)); - // TODO call constructRoutingData() here. - _routingDataMap.put(namespace, newRoutingData); - } } @Override diff --git a/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java index 1b1754d..bf71456 100644 --- a/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java +++ b/helix-rest/src/test/java/org/apache/helix/rest/metadatastore/TestTrieRoutingData.java @@ -19,146 +19,250 @@ package org.apache.helix.rest.metadatastore; * under the License. */ +import java.util.Arrays; import java.util.Collections; import java.util.HashMap; +import java.util.List; import java.util.Map; import java.util.NoSuchElementException; +import org.apache.helix.rest.metadatastore.exceptions.InvalidRoutingDataException; import org.testng.Assert; import org.testng.annotations.Test; public class TestTrieRoutingData { - // TODO: add constructor related tests after constructor is finished + private TrieRoutingData _trie; @Test - public void testGetAllMappingUnderPathFromRoot() { - TrieRoutingData trie = constructTestTrie(); - Map<String, String> result = trie.getAllMappingUnderPath("/"); - Assert.assertEquals(result.size(), 4); - Assert.assertEquals(result.get("/b/c/d"), "realmAddressD"); - Assert.assertEquals(result.get("/b/c/e"), "realmAddressE"); - Assert.assertEquals(result.get("/b/f"), "realmAddressF"); - Assert.assertEquals(result.get("/g"), "realmAddressG"); + public void testConstructionMissingRoutingData() { + try { + new TrieRoutingData(null); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue(e.getMessage().contains("routingData cannot be null or empty")); + } + try { + new TrieRoutingData(Collections.emptyMap()); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue(e.getMessage().contains("routingData cannot be null or empty")); + } + } + + /** + * This test case is for the situation when there's only one sharding key and it's root. + */ + @Test + public void testConstructionSpecialCase() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress", Collections.singletonList("/")); + TrieRoutingData trie; + try { + trie = new TrieRoutingData(routingData); + Map<String, String> result = trie.getAllMappingUnderPath("/"); + Assert.assertEquals(result.size(), 1); + Assert.assertEquals(result.get("/"), "realmAddress"); + } catch (InvalidRoutingDataException e) { + Assert.fail("Not expecting InvalidRoutingDataException"); + } + } + + @Test + public void testConstructionEmptyShardingKeys() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress1", Collections.emptyList()); + try { + new TrieRoutingData(routingData); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue(e.getMessage() + .contains("Realm address does not have associating sharding keys: realmAddress1")); + } + } + + @Test + public void testConstructionShardingKeyNoLeadingSlash() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress1", Arrays.asList("/g", "/h/i", "/h/j")); + routingData.put("realmAddress2", Arrays.asList("b/c/d", "/b/f")); + routingData.put("realmAddress3", Collections.singletonList("/b/c/e")); + try { + new TrieRoutingData(routingData); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue( + e.getMessage().contains("Sharding key does not have a leading \"/\" character: b/c/d")); + } + } + + @Test + public void testConstructionRootAsShardingKeyInvalid() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress1", Arrays.asList("/a/b", "/")); + try { + new TrieRoutingData(routingData); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue(e.getMessage() + .contains("There exist other sharding keys. Root cannot be a sharding key.")); + } } @Test - public void testGetAllMappingUnderPathFromRootEmptyPath() { - TrieRoutingData trie = constructTestTrie(); - Map<String, String> result = trie.getAllMappingUnderPath(""); - Assert.assertEquals(result.size(), 4); - Assert.assertEquals(result.get("/b/c/d"), "realmAddressD"); - Assert.assertEquals(result.get("/b/c/e"), "realmAddressE"); - Assert.assertEquals(result.get("/b/f"), "realmAddressF"); - Assert.assertEquals(result.get("/g"), "realmAddressG"); + public void testConstructionShardingKeyContainsAnother() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress1", Arrays.asList("/a/b", "/a/b/c")); + try { + new TrieRoutingData(routingData); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue(e.getMessage().contains( + "/a/b/c cannot be a sharding key because /a/b is its parent key and is also a sharding key.")); + } } @Test + public void testConstructionShardingKeyIsAPartOfAnother() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress1", Arrays.asList("/a/b/c", "/a/b")); + try { + new TrieRoutingData(routingData); + Assert.fail("Expecting InvalidRoutingDataException"); + } catch (InvalidRoutingDataException e) { + Assert.assertTrue(e.getMessage().contains( + "/a/b cannot be a sharding key because it is a parent key to another sharding key.")); + } + } + + /** + * Constructing a trie that will also be reused for other tests + * -----<empty> + * ------/-|--\ + * -----b--g--h + * ----/-\---/-\ + * ---c--f--i--j + * --/-\ + * -d--e + * Note: "g", "i", "j" lead to "realmAddress1"; "d", "f" lead to "realmAddress2"; "e" leads to + * "realmAddress3" + */ + @Test + public void testConstructionNormal() { + Map<String, List<String>> routingData = new HashMap<>(); + routingData.put("realmAddress1", Arrays.asList("/g", "/h/i", "/h/j")); + routingData.put("realmAddress2", Arrays.asList("/b/c/d", "/b/f")); + routingData.put("realmAddress3", Collections.singletonList("/b/c/e")); + try { + _trie = new TrieRoutingData(routingData); + } catch (InvalidRoutingDataException e) { + Assert.fail("Not expecting InvalidRoutingDataException"); + } + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testGetAllMappingUnderPathEmptyPath() { + try { + _trie.getAllMappingUnderPath(""); + Assert.fail("Expecting IllegalArgumentException"); + } catch (IllegalArgumentException e) { + Assert.assertTrue(e.getMessage() + .contains("Provided path is empty or does not have a leading \"/\" character: ")); + } + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testGetAllMappingUnderPathNoLeadingSlash() { + try { + _trie.getAllMappingUnderPath("test"); + Assert.fail("Expecting IllegalArgumentException"); + } catch (IllegalArgumentException e) { + Assert.assertTrue(e.getMessage() + .contains("Provided path is empty or does not have a leading \"/\" character: test")); + } + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testGetAllMappingUnderPathFromRoot() { + Map<String, String> result = _trie.getAllMappingUnderPath("/"); + Assert.assertEquals(result.size(), 6); + Assert.assertEquals(result.get("/b/c/d"), "realmAddress2"); + Assert.assertEquals(result.get("/b/c/e"), "realmAddress3"); + Assert.assertEquals(result.get("/b/f"), "realmAddress2"); + Assert.assertEquals(result.get("/g"), "realmAddress1"); + Assert.assertEquals(result.get("/h/i"), "realmAddress1"); + Assert.assertEquals(result.get("/h/j"), "realmAddress1"); + } + + @Test(dependsOnMethods = "testConstructionNormal") public void testGetAllMappingUnderPathFromSecondLevel() { - TrieRoutingData trie = constructTestTrie(); - Map<String, String> result = trie.getAllMappingUnderPath("/b"); + Map<String, String> result = _trie.getAllMappingUnderPath("/b"); Assert.assertEquals(result.size(), 3); - Assert.assertEquals(result.get("/b/c/d"), "realmAddressD"); - Assert.assertEquals(result.get("/b/c/e"), "realmAddressE"); - Assert.assertEquals(result.get("/b/f"), "realmAddressF"); + Assert.assertEquals(result.get("/b/c/d"), "realmAddress2"); + Assert.assertEquals(result.get("/b/c/e"), "realmAddress3"); + Assert.assertEquals(result.get("/b/f"), "realmAddress2"); } - @Test + @Test(dependsOnMethods = "testConstructionNormal") public void testGetAllMappingUnderPathFromLeaf() { - TrieRoutingData trie = constructTestTrie(); - Map<String, String> result = trie.getAllMappingUnderPath("/b/c/d"); + Map<String, String> result = _trie.getAllMappingUnderPath("/b/c/d"); Assert.assertEquals(result.size(), 1); - Assert.assertEquals(result.get("/b/c/d"), "realmAddressD"); + Assert.assertEquals(result.get("/b/c/d"), "realmAddress2"); } - @Test + @Test(dependsOnMethods = "testConstructionNormal") public void testGetAllMappingUnderPathWrongPath() { - TrieRoutingData trie = constructTestTrie(); - Map<String, String> result = trie.getAllMappingUnderPath("/b/c/d/g"); + Map<String, String> result = _trie.getAllMappingUnderPath("/b/c/d/g"); Assert.assertEquals(result.size(), 0); } - @Test - public void testGetMetadataStoreRealm() { - TrieRoutingData trie = constructTestTrie(); + @Test(dependsOnMethods = "testConstructionNormal") + public void testGetMetadataStoreRealmEmptyPath() { try { - Assert.assertEquals(trie.getMetadataStoreRealm("/b/c/d/x/y/z"), "realmAddressD"); - } catch (NoSuchElementException e) { - Assert.fail("Not expecting NoSuchElementException"); + Assert.assertEquals(_trie.getMetadataStoreRealm(""), "realmAddress2"); + Assert.fail("Expecting IllegalArgumentException"); + } catch (IllegalArgumentException e) { + Assert.assertTrue(e.getMessage() + .contains("Provided path is empty or does not have a leading \"/\" character: ")); } } - @Test + @Test(dependsOnMethods = "testConstructionNormal") public void testGetMetadataStoreRealmNoSlash() { - TrieRoutingData trie = constructTestTrie(); try { - Assert.assertEquals(trie.getMetadataStoreRealm("b/c/d/x/y/z"), "realmAddressD"); + Assert.assertEquals(_trie.getMetadataStoreRealm("b/c/d/x/y/z"), "realmAddress2"); + Assert.fail("Expecting IllegalArgumentException"); + } catch (IllegalArgumentException e) { + Assert.assertTrue(e.getMessage().contains( + "Provided path is empty or does not have a leading \"/\" character: b/c/d/x/y/z")); + } + } + + @Test(dependsOnMethods = "testConstructionNormal") + public void testGetMetadataStoreRealm() { + try { + Assert.assertEquals(_trie.getMetadataStoreRealm("/b/c/d/x/y/z"), "realmAddress2"); } catch (NoSuchElementException e) { Assert.fail("Not expecting NoSuchElementException"); } } - @Test + @Test(dependsOnMethods = "testConstructionNormal") public void testGetMetadataStoreRealmWrongPath() { - TrieRoutingData trie = constructTestTrie(); try { - trie.getMetadataStoreRealm("/x/y/z"); + _trie.getMetadataStoreRealm("/x/y/z"); Assert.fail("Expecting NoSuchElementException"); } catch (NoSuchElementException e) { - Assert.assertTrue(e.getMessage().contains("The provided path is missing from the trie. Path: /x/y/z")); + Assert.assertTrue( + e.getMessage().contains("The provided path is missing from the trie. Path: /x/y/z")); } } - @Test + @Test(dependsOnMethods = "testConstructionNormal") public void testGetMetadataStoreRealmNoLeaf() { - TrieRoutingData trie = constructTestTrie(); try { - trie.getMetadataStoreRealm("/b/c"); + _trie.getMetadataStoreRealm("/b/c"); Assert.fail("Expecting NoSuchElementException"); } catch (NoSuchElementException e) { Assert.assertTrue(e.getMessage().contains("No leaf node found along the path. Path: /b/c")); } } - - /** - * Constructing a trie for testing purposes - * -----<empty> - * ------/--\ - * -----b---g - * ----/-\ - * ---c--f - * --/-\ - * -d--e - */ - private TrieRoutingData constructTestTrie() { - TrieRoutingData.TrieNode nodeD = - new TrieRoutingData.TrieNode(Collections.emptyMap(), "/b/c/d", true, "realmAddressD"); - TrieRoutingData.TrieNode nodeE = - new TrieRoutingData.TrieNode(Collections.emptyMap(), "/b/c/e", true, "realmAddressE"); - TrieRoutingData.TrieNode nodeF = - new TrieRoutingData.TrieNode(Collections.emptyMap(), "/b/f", true, "realmAddressF"); - TrieRoutingData.TrieNode nodeG = - new TrieRoutingData.TrieNode(Collections.emptyMap(), "/g", true, "realmAddressG"); - TrieRoutingData.TrieNode nodeC = - new TrieRoutingData.TrieNode(new HashMap<String, TrieRoutingData.TrieNode>() { - { - put("d", nodeD); - put("e", nodeE); - } - }, "c", false, ""); - TrieRoutingData.TrieNode nodeB = - new TrieRoutingData.TrieNode(new HashMap<String, TrieRoutingData.TrieNode>() { - { - put("c", nodeC); - put("f", nodeF); - } - }, "b", false, ""); - TrieRoutingData.TrieNode root = - new TrieRoutingData.TrieNode(new HashMap<String, TrieRoutingData.TrieNode>() { - { - put("b", nodeB); - put("g", nodeG); - } - }, "", false, ""); - - return new TrieRoutingData(root); - } }
