This is an automated email from the ASF dual-hosted git repository.
andor pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/zookeeper.git
The following commit(s) were added to refs/heads/master by this push:
new 04cc5ca ZOOKEEPER-3347: Improve PathTrie Consistency
04cc5ca is described below
commit 04cc5cae1e7d4b007490e68109a676b88ce790a3
Author: Beluga Behr <[email protected]>
AuthorDate: Fri Aug 9 16:15:20 2019 +0200
ZOOKEEPER-3347: Improve PathTrie Consistency
Author: Beluga Behr <[email protected]>
Author: apache <[email protected]>
Reviewers: [email protected], [email protected]
Closes #888 from belugabehr/ZOOKEEPER-3347 and squashes the following
commits:
bb9efee81 [apache] Added unit tests
4f8dc4b04 [apache] Fixed double-locking
34b61838d [Beluga Behr] Simplified further
6c6ec6c18 [Beluga Behr] ZOOKEEPER-3347: Improve PathTrie Consistency
---
.../java/org/apache/zookeeper/common/PathTrie.java | 387 ++++++++++++---------
.../java/org/apache/zookeeper/server/DataTree.java | 5 +-
.../org/apache/zookeeper/common/PathTrieTest.java | 152 ++++++++
.../org/apache/zookeeper/server/DataTreeTest.java | 2 +-
4 files changed, 375 insertions(+), 171 deletions(-)
diff --git
a/zookeeper-server/src/main/java/org/apache/zookeeper/common/PathTrie.java
b/zookeeper-server/src/main/java/org/apache/zookeeper/common/PathTrie.java
index 7c755f6..0a96b27 100644
--- a/zookeeper-server/src/main/java/org/apache/zookeeper/common/PathTrie.java
+++ b/zookeeper-server/src/main/java/org/apache/zookeeper/common/PathTrie.java
@@ -18,11 +18,17 @@
package org.apache.zookeeper.common;
-import java.util.ArrayList;
+import java.util.ArrayDeque;
+import java.util.Collection;
+import java.util.Deque;
import java.util.HashMap;
-import java.util.List;
import java.util.Map;
+import java.util.Objects;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import org.apache.commons.lang.StringUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -40,254 +46,301 @@ import org.slf4j.LoggerFactory;
* (bc)
* cf/
* (cf)
- */
+ */
public class PathTrie {
- /**
- * the logger for this class
- */
+
+ /** Logger for this class */
private static final Logger LOG = LoggerFactory.getLogger(PathTrie.class);
-
- /**
- * the root node of PathTrie
- */
- private final TrieNode rootNode ;
-
+
+ /** Root node of PathTrie */
+ private final TrieNode rootNode;
+
+ private final ReadWriteLock lock = new ReentrantReadWriteLock(true);
+
+ private final Lock readLock = lock.readLock();
+
+ private final Lock writeLock = lock.writeLock();
+
static class TrieNode {
- boolean property = false;
+ final String value;
final Map<String, TrieNode> children;
- TrieNode parent = null;
+ boolean property;
+ TrieNode parent;
+
/**
- * create a trienode with parent
- * as parameter
- * @param parent the parent of this trienode
+ * Create a trie node with parent as parameter.
+ *
+ * @param parent the parent of this node
+ * @param value the value stored in this node
*/
- private TrieNode(TrieNode parent) {
- children = new HashMap<String, TrieNode>();
+ private TrieNode(TrieNode parent, String value) {
+ this.value = value;
this.parent = parent;
+ this.property = false;
+ this.children = new HashMap<>(4);
}
-
+
/**
- * get the parent of this node
+ * Get the parent of this node.
+ *
* @return the parent node
*/
TrieNode getParent() {
return this.parent;
}
-
+
/**
- * set the parent of this node
+ * set the parent of this node.
+ *
* @param parent the parent to set to
*/
void setParent(TrieNode parent) {
this.parent = parent;
}
-
+
/**
- * a property that is set
- * for a node - making it
- * special.
+ * A property that is set for a node - making it special.
*/
void setProperty(boolean prop) {
this.property = prop;
}
-
- /** the property of this
- * node
- * @return the property for this
- * node
+
+ /**
+ * The property of this node.
+ *
+ * @return the property for this node
*/
- boolean getProperty() {
+ boolean hasProperty() {
return this.property;
}
+
+ /**
+ * The value stored in this node.
+ *
+ * @return the value stored in this node
+ */
+ public String getValue() {
+ return this.value;
+ }
+
/**
- * add a child to the existing node
+ * Add a child to the existing node.
+ *
* @param childName the string name of the child
* @param node the node that is the child
*/
void addChild(String childName, TrieNode node) {
- synchronized(children) {
- if (children.containsKey(childName)) {
- return;
- }
- children.put(childName, node);
- }
+ this.children.putIfAbsent(childName, node);
}
-
+
/**
- * delete child from this node
- * @param childName the string name of the child to
- * be deleted
+ * Delete child from this node.
+ *
+ * @param childName the name of the child to be deleted
*/
void deleteChild(String childName) {
- synchronized(children) {
- if (!children.containsKey(childName)) {
- return;
- }
- TrieNode childNode = children.get(childName);
- // this is the only child node.
- if (childNode.getChildren().length == 1) {
+ this.children.computeIfPresent(childName, (key, childNode) -> {
+ // Node no longer has an external property associated
+ childNode.setProperty(false);
+
+ // Delete it if it has no children (is a leaf node)
+ if (childNode.isLeafNode()) {
childNode.setParent(null);
- children.remove(childName);
- }
- else {
- // their are more child nodes
- // so just reset property.
- childNode.setProperty(false);
+ return null;
}
- }
+
+ return childNode;
+ });
}
-
+
/**
- * return the child of a node mapping
- * to the input childname
+ * Return the child of a node mapping to the input child name.
+ *
* @param childName the name of the child
* @return the child of a node
*/
TrieNode getChild(String childName) {
- synchronized(children) {
- if (!children.containsKey(childName)) {
- return null;
- }
- else {
- return children.get(childName);
- }
- }
+ return this.children.get(childName);
}
/**
- * get the list of children of this
- * trienode.
- * @return the string list of its children
+ * Get the list of children of this trienode.
+ *
+ * @return A collection containing the node's children
*/
- String[] getChildren() {
- synchronized(children) {
- return children.keySet().toArray(new String[0]);
- }
+ Collection<String> getChildren() {
+ return children.keySet();
}
-
+
/**
- * get the string representation
- * for this node
+ * Determine if this node is a leaf (has no children).
+ *
+ * @return true if this node is a lead node; otherwise false
*/
+ boolean isLeafNode() {
+ return children.isEmpty();
+ }
+
+ @Override
public String toString() {
- StringBuilder sb = new StringBuilder();
- sb.append("Children of trienode: ");
- synchronized(children) {
- for (String str: children.keySet()) {
- sb.append(" " + str);
- }
- }
- return sb.toString();
+ return "TrieNode [name=" + value + ", property=" + property
+ + ", children=" + children.keySet() + "]";
}
}
-
+
/**
- * construct a new PathTrie with
- * a root node of /
+ * Construct a new PathTrie with a root node.
*/
public PathTrie() {
- this.rootNode = new TrieNode(null);
+ this.rootNode = new TrieNode(null, "/");
}
-
+
/**
- * add a path to the path trie
- * @param path
+ * Add a path to the path trie. All paths are relative to the root node.
+ *
+ * @param path the path to add to the trie
*/
- public void addPath(String path) {
- if (path == null) {
- return;
- }
- String[] pathComponents = path.split("/");
- TrieNode parent = rootNode;
- String part = null;
- if (pathComponents.length <= 1) {
- throw new IllegalArgumentException("Invalid path " + path);
+ public void addPath(final String path) {
+ Objects.requireNonNull(path, "Path cannot be null");
+
+ final String[] pathComponents = StringUtils.split(path, '/');
+ if (pathComponents.length == 0) {
+ throw new IllegalArgumentException("Invalid path: " + path);
}
- for (int i=1; i<pathComponents.length; i++) {
- part = pathComponents[i];
- if (parent.getChild(part) == null) {
- parent.addChild(part, new TrieNode(parent));
+
+ writeLock.lock();
+ try {
+ TrieNode parent = rootNode;
+ for (final String part : pathComponents) {
+ TrieNode child = parent.getChild(part);
+ if (child == null) {
+ child = new TrieNode(parent, part);
+ parent.addChild(part, child);
+ }
+ parent = child;
}
- parent = parent.getChild(part);
+ parent.setProperty(true);
+ } finally {
+ writeLock.unlock();
}
- parent.setProperty(true);
}
-
+
/**
- * delete a path from the trie
+ * Delete a path from the trie. All paths are relative to the root node.
+ *
* @param path the path to be deleted
*/
- public void deletePath(String path) {
- if (path == null) {
- return;
- }
- String[] pathComponents = path.split("/");
- TrieNode parent = rootNode;
- String part = null;
- if (pathComponents.length <= 1) {
- throw new IllegalArgumentException("Invalid path " + path);
+ public void deletePath(final String path) {
+ Objects.requireNonNull(path, "Path cannot be null");
+
+ final String[] pathComponents = StringUtils.split(path, '/');
+ if (pathComponents.length == 0) {
+ throw new IllegalArgumentException("Invalid path: " + path);
}
- for (int i=1; i<pathComponents.length; i++) {
- part = pathComponents[i];
- if (parent.getChild(part) == null) {
- //the path does not exist
- return;
+
+ writeLock.lock();
+ try {
+ TrieNode parent = rootNode;
+ for (final String part : pathComponents) {
+ if (parent.getChild(part) == null) {
+ // the path does not exist
+ return;
+ }
+ parent = parent.getChild(part);
+ LOG.debug("{}", parent);
}
- parent = parent.getChild(part);
- LOG.info("{}",parent);
+
+ final TrieNode realParent = parent.getParent();
+ realParent.deleteChild(parent.getValue());
+ } finally {
+ writeLock.unlock();
}
- TrieNode realParent = parent.getParent();
- realParent.deleteChild(part);
}
-
+
/**
- * return the largest prefix for the input path.
+ * Return true if the given path exists in the trie, otherwise return
false;
+ * All paths are relative to the root node.
+ *
* @param path the input path
- * @return the largest prefix for the input path.
+ * @return the largest prefix for the
+ */
+ public boolean existsNode(final String path) {
+ Objects.requireNonNull(path, "Path cannot be null");
+
+ final String[] pathComponents = StringUtils.split(path, '/');
+ if (pathComponents.length == 0) {
+ throw new IllegalArgumentException("Invalid path: " + path);
+ }
+
+ readLock.lock();
+ try {
+ TrieNode parent = rootNode;
+ for (final String part : pathComponents) {
+ if (parent.getChild(part) == null) {
+ // the path does not exist
+ return false;
+ }
+ parent = parent.getChild(part);
+ LOG.debug("{}", parent);
+ }
+ } finally {
+ readLock.unlock();
+ }
+ return true;
+ }
+
+ /**
+ * Return the largest prefix for the input path. All paths are relative to
the
+ * root node.
+ *
+ * @param path the input path
+ * @return the largest prefix for the input path
*/
- public String findMaxPrefix(String path) {
- if (path == null) {
- return null;
- }
- if ("/".equals(path)) {
- return path;
- }
- String[] pathComponents = path.split("/");
- TrieNode parent = rootNode;
- List<String> components = new ArrayList<String>();
- if (pathComponents.length <= 1) {
- throw new IllegalArgumentException("Invalid path " + path);
- }
- int i = 1;
- String part = null;
- StringBuilder sb = new StringBuilder();
- int lastindex = -1;
- while((i < pathComponents.length)) {
- if (parent.getChild(pathComponents[i]) != null) {
- part = pathComponents[i];
- parent = parent.getChild(part);
- components.add(part);
- if (parent.getProperty()) {
- lastindex = i-1;
+ public String findMaxPrefix(final String path) {
+ Objects.requireNonNull(path, "Path cannot be null");
+
+ final String[] pathComponents = StringUtils.split(path, '/');
+
+ readLock.lock();
+ try {
+ TrieNode parent = rootNode;
+ TrieNode deepestPropertyNode = null;
+ for (final String element : pathComponents) {
+ parent = parent.getChild(element);
+ if (parent == null) {
+ LOG.debug("{}", element);
+ break;
}
+ if (parent.hasProperty()) {
+ deepestPropertyNode = parent;
+ }
+ }
+
+ if (deepestPropertyNode == null) {
+ return "/";
}
- else {
- break;
+
+ final Deque<String> treePath = new ArrayDeque<>();
+ TrieNode node = deepestPropertyNode;
+ while (node != this.rootNode) {
+ treePath.offerFirst(node.getValue());
+ node = node.parent;
}
- i++;
+ return "/" + String.join("/", treePath);
+ } finally {
+ readLock.unlock();
}
- for (int j=0; j< (lastindex+1); j++) {
- sb.append("/" + components.get(j));
- }
- return sb.toString();
}
/**
- * clear all nodes
+ * Clear all nodes in the trie.
*/
public void clear() {
- for(String child : rootNode.getChildren()) {
- rootNode.deleteChild(child);
- }
+ writeLock.lock();
+ try {
+ rootNode.getChildren().clear();
+ } finally {
+ writeLock.unlock();
+ }
}
}
diff --git
a/zookeeper-server/src/main/java/org/apache/zookeeper/server/DataTree.java
b/zookeeper-server/src/main/java/org/apache/zookeeper/server/DataTree.java
index d2371ff..2d9fb93 100644
--- a/zookeeper-server/src/main/java/org/apache/zookeeper/server/DataTree.java
+++ b/zookeeper-server/src/main/java/org/apache/zookeeper/server/DataTree.java
@@ -697,10 +697,9 @@ public class DataTree {
// root node for now.
String lastPrefix = pTrie.findMaxPrefix(path);
- if (rootZookeeper.equals(lastPrefix) || "".equals(lastPrefix)) {
+ if (rootZookeeper.equals(lastPrefix) || lastPrefix.isEmpty()) {
return null;
- }
- else {
+ } else {
return lastPrefix;
}
}
diff --git
a/zookeeper-server/src/test/java/org/apache/zookeeper/common/PathTrieTest.java
b/zookeeper-server/src/test/java/org/apache/zookeeper/common/PathTrieTest.java
new file mode 100644
index 0000000..eeaaeb7
--- /dev/null
+++
b/zookeeper-server/src/test/java/org/apache/zookeeper/common/PathTrieTest.java
@@ -0,0 +1,152 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.zookeeper.common;
+
+import org.junit.Assert;
+import org.junit.Before;
+import org.junit.Test;
+
+public class PathTrieTest {
+
+ private PathTrie pathTrie;
+
+ @Before
+ public void before() {
+ this.pathTrie = new PathTrie();
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void addNullPath() {
+ this.pathTrie.addPath(null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void addIllegalPath() {
+ this.pathTrie.addPath("");
+ }
+
+ @Test
+ public void addPathToRoot() {
+ this.pathTrie.addPath("node1");
+ Assert.assertTrue(this.pathTrie.existsNode("/node1"));
+ }
+
+ @Test
+ public void addPathToRootLeaves() {
+ this.pathTrie.addPath("node1");
+ this.pathTrie.addPath("node1/node2");
+ this.pathTrie.addPath("node1/node3");
+ Assert.assertTrue(this.pathTrie.existsNode("/node1"));
+ Assert.assertTrue(this.pathTrie.existsNode("/node1/node2"));
+ Assert.assertTrue(this.pathTrie.existsNode("/node1/node3"));
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void deleteNullPath() {
+ this.pathTrie.deletePath(null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void deleteIllegalPath() {
+ this.pathTrie.deletePath("");
+ }
+
+ @Test
+ public void deletePathFromRoot() {
+ this.pathTrie.addPath("node1");
+ this.pathTrie.deletePath("node1");
+ Assert.assertFalse(this.pathTrie.existsNode("/node1"));
+ }
+
+ @Test
+ public void deletePathFromRootLeaves() {
+ this.pathTrie.addPath("node1");
+ this.pathTrie.addPath("node1/node2");
+ this.pathTrie.addPath("node1/node3");
+
+ this.pathTrie.deletePath("node1/node3");
+
+ Assert.assertTrue(this.pathTrie.existsNode("/node1"));
+ Assert.assertTrue(this.pathTrie.existsNode("/node1/node2"));
+ Assert.assertFalse(this.pathTrie.existsNode("/node1/node3"));
+
+ this.pathTrie.deletePath("node1/node2");
+
+ Assert.assertTrue(this.pathTrie.existsNode("/node1"));
+ Assert.assertFalse(this.pathTrie.existsNode("/node1/node2"));
+
+ this.pathTrie.deletePath("node1");
+ Assert.assertFalse(this.pathTrie.existsNode("/node1"));
+ }
+
+ @Test
+ public void deletePathDoesNotExist() {
+ this.pathTrie.addPath("node1");
+ this.pathTrie.addPath("node1/node2");
+
+ this.pathTrie.deletePath("node1/node3");
+
+ Assert.assertTrue(this.pathTrie.existsNode("/node1"));
+ Assert.assertTrue(this.pathTrie.existsNode("/node1/node2"));
+ }
+
+ @Test
+ public void deleteRootPath() {
+ this.pathTrie.addPath("node1");
+ this.pathTrie.addPath("node1/node2");
+ this.pathTrie.addPath("node1/node3");
+
+ // Nodes are only removed from the trie if they are a leaf node
+ this.pathTrie.deletePath("node1");
+
+ Assert.assertTrue(this.pathTrie.existsNode("/node1"));
+ Assert.assertTrue(this.pathTrie.existsNode("/node1/node2"));
+ Assert.assertTrue(this.pathTrie.existsNode("/node1/node3"));
+ }
+
+ @Test(expected = NullPointerException.class)
+ public void findMaxPrefixNullPath() {
+ this.pathTrie.findMaxPrefix(null);
+ }
+
+ @Test
+ public void findMaxPrefixRootPath() {
+ Assert.assertEquals("/", this.pathTrie.findMaxPrefix("/"));
+ }
+
+ @Test
+ public void findMaxPrefixChildren() {
+ this.pathTrie.addPath("node1");
+ this.pathTrie.addPath("node1/node2");
+ this.pathTrie.addPath("node1/node3");
+
+ Assert.assertEquals("/node1", this.pathTrie.findMaxPrefix("/node1"));
+ Assert.assertEquals("/node1/node2",
this.pathTrie.findMaxPrefix("/node1/node2"));
+ Assert.assertEquals("/node1/node3",
this.pathTrie.findMaxPrefix("/node1/node3"));
+ }
+
+ @Test
+ public void findMaxPrefixChildrenPrefix() {
+ this.pathTrie.addPath("node1");
+
+ Assert.assertEquals("/node1",
this.pathTrie.findMaxPrefix("/node1/node2"));
+ Assert.assertEquals("/node1",
this.pathTrie.findMaxPrefix("/node1/node3"));
+ }
+
+}
diff --git
a/zookeeper-server/src/test/java/org/apache/zookeeper/server/DataTreeTest.java
b/zookeeper-server/src/test/java/org/apache/zookeeper/server/DataTreeTest.java
index d26db23..5c8fb41 100644
---
a/zookeeper-server/src/test/java/org/apache/zookeeper/server/DataTreeTest.java
+++
b/zookeeper-server/src/test/java/org/apache/zookeeper/server/DataTreeTest.java
@@ -256,7 +256,7 @@ public class DataTreeTest extends ZKTestCase {
PathTrie pTrie = (PathTrie)pfield.get(dserTree);
//Check that the node path is removed from pTrie
- Assert.assertEquals("/bug is still in pTrie", "",
pTrie.findMaxPrefix("/bug"));
+ Assert.assertEquals("/bug is still in pTrie", "/",
pTrie.findMaxPrefix("/bug"));
}
/*
