[GitHub] [helix] xyuanlu commented on a diff in pull request #2439: Add a Trie class to represent RecursivePersistWatcherListener in ZkClient

["xyuanlu (via GitHub)" <gi...@apache.org>]

xyuanlu commented on code in PR #2439:
URL: https://github.com/apache/helix/pull/2439#discussion_r1166075911


##########
zookeeper-api/src/main/java/org/apache/helix/zookeeper/zkclient/util/ZkPathRecursiveWatcherTrie.java:
##########
@@ -0,0 +1,271 @@
+package org.apache.helix.zookeeper.zkclient.util;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
+import java.util.stream.Stream;
+
+import com.google.common.annotations.VisibleForTesting;
+import org.apache.helix.zookeeper.zkclient.RecursivePersistListener;
+
+
+/**
+ * ZkPathRecursiveWatcherTrie will be used for a registry for ZK persist recursive watcher.
+ * When persist recursive watcher is registered on path /X, ZK will send out data change for any
+ * data/child changing under the tree structure of /X. The event only include the path of changed
+ * ZNode.
+ * In ZkClient, when ever we get a dataChange event for path /X/Y/Z, we need to track back the path
+ * and notify all registered recursive persist listener and notify them about the node change.
+ * ref: https://zookeeper.apache.org/doc/r3.7.1/zookeeperProgrammers.html#sc_WatchPersistentRecursive
+ */
+public class ZkPathRecursiveWatcherTrie {
+
+  /** 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 {
+
+    final String value;   // Segmented ZNode path at current level
+    final Map<String, TrieNode> children; // A map of segmented ZNode path of next level to TrieNode
+    TrieNode parent;  // A reference to upper level TrieNode
+    Set<RecursivePersistListener> recursiveListeners;
+    // A list of recursive persist watcher on the current path
+
+    /**
+     * 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, String value) {
+      this.value = value;
+      this.parent = parent;
+      this.children =
+          new HashMap<>(4);  // We keep the same number of init children side as Zk sevrer
+      this.recursiveListeners = new HashSet<>(4);
+    }
+
+    /**
+     * Get the parent of this node.
+     *
+     * @return the parent node
+     */
+    TrieNode getParent() {
+      return this.parent;
+    }
+
+    /**
+     * set the parent of this node.
+     *
+     * @param parent the parent to set to
+     */
+    void setParent(TrieNode parent) {
+      this.parent = parent;
+    }
+
+    /**
+     * 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.
+     *
+     * @param childName the string name of the child
+     * @param node the node that is the child
+     */
+    void addChild(String childName, TrieNode node) {
+      this.children.putIfAbsent(childName, node);
+    }
+
+    /**
+     * Delete child from this node.
+     *
+     * @param childName the name of the child to be deleted
+     */
+    void deleteChild(String childName) {
+      this.children.computeIfPresent(childName, (key, childNode) -> {
+
+        // Delete it if it has no children (is a leaf node)
+        if (childNode.isLeafNode()) {
+          childNode.setParent(null);
+          return null;
+        }
+
+        return childNode;
+      });
+    }
+
+    /**
+     * 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
+     */
+    @VisibleForTesting
+    TrieNode getChild(String childName) {
+      return this.children.get(childName);
+    }
+
+    /**
+     * Get the list of children of this trienode.
+     *
+     * @return A collection containing the node's children
+     */
+    @VisibleForTesting
+    Collection<String> getChildren() {
+      return children.keySet();
+    }
+
+    /**
+     * 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();
+    }
+
+    /**
+     * Get the set of RecursivePersistWatcherListener
+     * Returns an empty set if no listener is registered on the path
+     * @return
+     */
+    @VisibleForTesting
+    Set<RecursivePersistListener> getRecursiveListeners() {
+      return recursiveListeners;
+    }
+
+    @Override
+    public String toString() {
+      return "TrieNode [name=" + value + ", children=" + children.keySet() + "]";
+    }
+  }
+
+  /**
+   * Construct a new PathTrie with a root node.
+   */
+  public ZkPathRecursiveWatcherTrie() {
+    this.rootNode = new TrieNode(null, "/");
+  }
+
+  /**
+   * Add a path to the path trie. All paths are relative to the root node.
+   *
+   * @param path the path to add RecursivePersistListener
+   * @param listener the RecursivePersistListener to be added
+   */
+  public void addRecursiveListener(final String path, RecursivePersistListener listener) {
+    Objects.requireNonNull(path, "Path cannot be null");
+
+    if (path.length() == 0) {
+      throw new IllegalArgumentException("Invalid path: " + path);
+    }
+    final String[] pathComponents = split(path);
+
+    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.recursiveListeners.add(listener);
+    } finally {
+      writeLock.unlock();
+    }
+  }
+
+  /**
+   * Removing a RecursivePersistWatcherListener on a path.
+   *
+   * Delete a path from the nearest trie node to current node if this is the only listener and there
+   * is no child on the trie node.
+   *
+   * @param path the of the lister registered
+   * @param listener the RecursivePersistListener to be removed
+   */
+  public void removeRecursiveListener(final String path, RecursivePersistListener listener) {
+    Objects.requireNonNull(path, "Path cannot be null");
+
+    if (path.length() == 0) {
+      throw new IllegalArgumentException("Invalid path: " + path);
+    }
+    final String[] pathComponents = split(path);
+
+    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);
+      }
+
+      TrieNode cur = parent;
+      cur.getRecursiveListeners().remove(listener);
+      // if cur is leaf node, remove the node and the path up to root until and parent node
+      // 1. has other child, or has watcher on that path
+      // remove the path if needed
+      while (cur != rootNode && (cur.children.size() == 0

Review Comment:
   This delete is from leaf to root. I am not sure if there is anything to be parallel processed..?



-- 
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.

To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org