NealSun96 commented on a change in pull request #731: Add TrieRoutingData constructor URL: https://github.com/apache/helix/pull/731#discussion_r377216613
########## File path: helix-rest/src/main/java/org/apache/helix/rest/metadatastore/TrieRoutingData.java ########## @@ -88,72 +107,174 @@ public String getMetadataStoreRealm(String path) throws NoSuchElementException { */ 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.isLeaf()) { 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.isLeaf()) { 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.isLeaf()) { return curNode; } - curChildren = curNode._children; + curChildren = curNode.getChildren(); } if (findLeafAlongPath) { throw new NoSuchElementException("No leaf node found along the path. Path: " + path); } 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: " + 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.isLeaf()) { + throw new InvalidRoutingDataException(shardingKey.substring(0, nextDelimiterIndex) + + " is already a sharding key. " + shardingKey + " cannot be 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 + + " is a part of another sharding key, therefore it cannot be a sharding key."); Review comment: Ditto above. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: reviews-unsubscr...@helix.apache.org For additional commands, e-mail: reviews-h...@helix.apache.org