Mailing-List: contact common-commits-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: liuml07@apache.org
To: common-commits@hadoop.apache.org
Message-Id: <25cb816652004658b22411124272476e@git.apache.org>
Subject: hadoop git commit: HDFS-11430. Separate class InnerNode from class
 NetworkTopology and make it extendable. Contributed by Tsz Wo Nicholas Sze
Date: Tue, 21 Feb 2017 23:35:40 +0000 (UTC)
archived-at: Tue, 21 Feb 2017 23:35:42 -0000

Repository: hadoop
Updated Branches:
  refs/heads/trunk 8ef7ebbc7 -> 003ae0069


HDFS-11430. Separate class InnerNode from class NetworkTopology and make it extendable. Contributed by Tsz Wo Nicholas Sze


Project: http://git-wip-us.apache.org/repos/asf/hadoop/repo
Commit: http://git-wip-us.apache.org/repos/asf/hadoop/commit/003ae006
Tree: http://git-wip-us.apache.org/repos/asf/hadoop/tree/003ae006
Diff: http://git-wip-us.apache.org/repos/asf/hadoop/diff/003ae006

Branch: refs/heads/trunk
Commit: 003ae00693d079799c4dcf02705379bcf34b8c79
Parents: 8ef7ebb
Author: Mingliang Liu <liuml07@apache.org>
Authored: Tue Feb 21 15:29:20 2017 -0800
Committer: Mingliang Liu <liuml07@apache.org>
Committed: Tue Feb 21 15:32:46 2017 -0800

----------------------------------------------------------------------
 .../java/org/apache/hadoop/net/InnerNode.java   |  67 ++++
 .../org/apache/hadoop/net/InnerNodeImpl.java    | 304 +++++++++++++++++
 .../org/apache/hadoop/net/NetworkTopology.java  | 326 +------------------
 .../net/NetworkTopologyWithNodeGroup.java       |  43 +--
 .../apache/hadoop/net/TestNetworkTopology.java  |   2 +-
 5 files changed, 388 insertions(+), 354 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/hadoop/blob/003ae006/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNode.java
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNode.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNode.java
new file mode 100644
index 0000000..d07929b
--- /dev/null
+++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNode.java
@@ -0,0 +1,67 @@
+/**
+ * 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.hadoop.net;
+
+import org.apache.hadoop.classification.InterfaceAudience;
+import org.apache.hadoop.classification.InterfaceStability;
+
+import java.util.List;
+
+
+@InterfaceAudience.LimitedPrivate({"HDFS", "MapReduce"})
+@InterfaceStability.Unstable
+public interface InnerNode extends Node {
+  interface Factory<N extends InnerNode> {
+    /** Construct an InnerNode from a path-like string */
+    N newInnerNode(String path);
+  }
+
+  /** Add node <i>n</i> to the subtree of this node
+   * @param n node to be added
+   * @return true if the node is added; false otherwise
+   */
+  boolean add(Node n);
+
+  /** Given a node's string representation, return a reference to the node
+   * @param loc string location of the form /rack/node
+   * @return null if the node is not found or the childnode is there but
+   * not an instance of {@link InnerNodeImpl}
+   */
+  Node getLoc(String loc);
+
+  /** @return its children */
+  List<Node> getChildren();
+
+  /** @return the number of leave nodes. */
+  int getNumOfLeaves();
+
+  /** Remove node <i>n</i> from the subtree of this node
+   * @param n node to be deleted
+   * @return true if the node is deleted; false otherwise
+   */
+  boolean remove(Node n);
+
+  /** get <i>leafIndex</i> leaf of this subtree
+   * if it is not in the <i>excludedNode</i>
+   *
+   * @param leafIndex an indexed leaf of the node
+   * @param excludedNode an excluded node (can be null)
+   * @return
+   */
+  Node getLeaf(int leafIndex, Node excludedNode);
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/003ae006/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNodeImpl.java
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNodeImpl.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNodeImpl.java
new file mode 100644
index 0000000..e6aa0f7
--- /dev/null
+++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/InnerNodeImpl.java
@@ -0,0 +1,304 @@
+/**
+ * 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.hadoop.net;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/** InnerNode represents a switch/router of a data center or rack.
+ * Different from a leaf node, it has non-null children.
+ */
+class InnerNodeImpl extends NodeBase implements InnerNode {
+  static class Factory implements InnerNode.Factory<InnerNodeImpl> {
+    private Factory() {}
+
+    @Override
+    public InnerNodeImpl newInnerNode(String path) {
+      return new InnerNodeImpl(path);
+    }
+  }
+
+  static final Factory FACTORY = new Factory();
+
+  private final List<Node> children = new ArrayList<>();
+  private final Map<String, Node> childrenMap = new HashMap<>();
+  private int numOfLeaves;
+
+  /** Construct an InnerNode from a path-like string */
+  InnerNodeImpl(String path) {
+    super(path);
+  }
+
+  /** Construct an InnerNode
+   * from its name, its network location, its parent, and its level */
+  InnerNodeImpl(String name, String location, InnerNode parent, int level) {
+    super(name, location, parent, level);
+  }
+
+  @Override
+  public List<Node> getChildren() {return children;}
+
+  /** @return the number of children this node has */
+  int getNumOfChildren() {
+    return children.size();
+  }
+
+  /** Judge if this node represents a rack
+   * @return true if it has no child or its children are not InnerNodes
+   */
+  boolean isRack() {
+    if (children.isEmpty()) {
+      return true;
+    }
+
+    Node firstChild = children.get(0);
+    if (firstChild instanceof InnerNode) {
+      return false;
+    }
+
+    return true;
+  }
+
+  /** Judge if this node is an ancestor of node <i>n</i>
+   *
+   * @param n a node
+   * @return true if this node is an ancestor of <i>n</i>
+   */
+  boolean isAncestor(Node n) {
+    return getPath(this).equals(NodeBase.PATH_SEPARATOR_STR) ||
+      (n.getNetworkLocation()+NodeBase.PATH_SEPARATOR_STR).
+      startsWith(getPath(this)+NodeBase.PATH_SEPARATOR_STR);
+  }
+
+  /** Judge if this node is the parent of node <i>n</i>
+   *
+   * @param n a node
+   * @return true if this node is the parent of <i>n</i>
+   */
+  boolean isParent(Node n) {
+    return n.getNetworkLocation().equals(getPath(this));
+  }
+
+  /* Return a child name of this node who is an ancestor of node <i>n</i> */
+  private String getNextAncestorName(Node n) {
+    if (!isAncestor(n)) {
+      throw new IllegalArgumentException(
+                                         this + "is not an ancestor of " + n);
+    }
+    String name = n.getNetworkLocation().substring(getPath(this).length());
+    if (name.charAt(0) == PATH_SEPARATOR) {
+      name = name.substring(1);
+    }
+    int index=name.indexOf(PATH_SEPARATOR);
+    if (index !=-1)
+      name = name.substring(0, index);
+    return name;
+  }
+
+  @Override
+  public boolean add(Node n) {
+    if (!isAncestor(n)) {
+      throw new IllegalArgumentException(n.getName()
+          + ", which is located at " + n.getNetworkLocation()
+          + ", is not a descendant of " + getPath(this));
+    }
+    if (isParent(n)) {
+      // this node is the parent of n; add n directly
+      n.setParent(this);
+      n.setLevel(this.level+1);
+      Node prev = childrenMap.put(n.getName(), n);
+      if (prev != null) {
+        for(int i=0; i<children.size(); i++) {
+          if (children.get(i).getName().equals(n.getName())) {
+            children.set(i, n);
+            return false;
+          }
+        }
+      }
+      children.add(n);
+      numOfLeaves++;
+      return true;
+    } else {
+      // find the next ancestor node
+      String parentName = getNextAncestorName(n);
+      InnerNode parentNode = (InnerNode)childrenMap.get(parentName);
+      if (parentNode == null) {
+        // create a new InnerNode
+        parentNode = createParentNode(parentName);
+        children.add(parentNode);
+        childrenMap.put(parentNode.getName(), parentNode);
+      }
+      // add n to the subtree of the next ancestor node
+      if (parentNode.add(n)) {
+        numOfLeaves++;
+        return true;
+      } else {
+        return false;
+      }
+    }
+  }
+
+  /**
+   * Creates a parent node to be added to the list of children.
+   * Creates a node using the InnerNode four argument constructor specifying
+   * the name, location, parent, and level of this node.
+   *
+   * <p>To be overridden in subclasses for specific InnerNode implementations,
+   * as alternative to overriding the full {@link #add(Node)} method.
+   *
+   * @param parentName The name of the parent node
+   * @return A new inner node
+   * @see InnerNodeImpl(String, String, InnerNode, int)
+   */
+  private InnerNodeImpl createParentNode(String parentName) {
+    return new InnerNodeImpl(parentName, getPath(this), this, this.getLevel()+1);
+  }
+
+  @Override
+  public boolean remove(Node n) {
+    if (!isAncestor(n)) {
+      throw new IllegalArgumentException(n.getName()
+          + ", which is located at " + n.getNetworkLocation()
+          + ", is not a descendant of " + getPath(this));
+    }
+    if (isParent(n)) {
+      // this node is the parent of n; remove n directly
+      if (childrenMap.containsKey(n.getName())) {
+        for (int i=0; i<children.size(); i++) {
+          if (children.get(i).getName().equals(n.getName())) {
+            children.remove(i);
+            childrenMap.remove(n.getName());
+            numOfLeaves--;
+            n.setParent(null);
+            return true;
+          }
+        }
+      }
+      return false;
+    } else {
+      // find the next ancestor node: the parent node
+      String parentName = getNextAncestorName(n);
+      InnerNodeImpl parentNode = (InnerNodeImpl)childrenMap.get(parentName);
+      if (parentNode == null) {
+        return false;
+      }
+      // remove n from the parent node
+      boolean isRemoved = parentNode.remove(n);
+      // if the parent node has no children, remove the parent node too
+      if (isRemoved) {
+        if (parentNode.getNumOfChildren() == 0) {
+          for(int i=0; i < children.size(); i++) {
+            if (children.get(i).getName().equals(parentName)) {
+              children.remove(i);
+              childrenMap.remove(parentName);
+              break;
+            }
+          }
+        }
+        numOfLeaves--;
+      }
+      return isRemoved;
+    }
+  } // end of remove
+
+  @Override
+  public Node getLoc(String loc) {
+    if (loc == null || loc.length() == 0) return this;
+
+    String[] path = loc.split(PATH_SEPARATOR_STR, 2);
+    Node childnode = childrenMap.get(path[0]);
+    if (childnode == null) return null; // non-existing node
+    if (path.length == 1) return childnode;
+    if (childnode instanceof InnerNode) {
+      return ((InnerNode)childnode).getLoc(path[1]);
+    } else {
+      return null;
+    }
+  }
+
+  @Override
+  public Node getLeaf(int leafIndex, Node excludedNode) {
+    int count=0;
+    // check if the excluded node a leaf
+    boolean isLeaf =
+      excludedNode == null || !(excludedNode instanceof InnerNode);
+    // calculate the total number of excluded leaf nodes
+    int numOfExcludedLeaves =
+      isLeaf ? 1 : ((InnerNode)excludedNode).getNumOfLeaves();
+    if (isLeafParent()) { // children are leaves
+      if (isLeaf) { // excluded node is a leaf node
+        if (excludedNode != null &&
+            childrenMap.containsKey(excludedNode.getName())) {
+          int excludedIndex = children.indexOf(excludedNode);
+          if (excludedIndex != -1 && leafIndex >= 0) {
+            // excluded node is one of the children so adjust the leaf index
+            leafIndex = leafIndex>=excludedIndex ? leafIndex+1 : leafIndex;
+          }
+        }
+      }
+      // range check
+      if (leafIndex<0 || leafIndex>=this.getNumOfChildren()) {
+        return null;
+      }
+      return children.get(leafIndex);
+    } else {
+      for(int i=0; i<children.size(); i++) {
+        InnerNodeImpl child = (InnerNodeImpl)children.get(i);
+        if (excludedNode == null || excludedNode != child) {
+          // not the excludedNode
+          int numOfLeaves = child.getNumOfLeaves();
+          if (excludedNode != null && child.isAncestor(excludedNode)) {
+            numOfLeaves -= numOfExcludedLeaves;
+          }
+          if (count+numOfLeaves > leafIndex) {
+            // the leaf is in the child subtree
+            return child.getLeaf(leafIndex-count, excludedNode);
+          } else {
+            // go to the next child
+            count = count+numOfLeaves;
+          }
+        } else { // it is the excluededNode
+          // skip it and set the excludedNode to be null
+          excludedNode = null;
+        }
+      }
+      return null;
+    }
+  }
+
+  private boolean isLeafParent() {
+    return isRack();
+  }
+
+  @Override
+  public int getNumOfLeaves() {
+    return numOfLeaves;
+  }
+
+  @Override
+  public int hashCode() {
+    return super.hashCode();
+  }
+
+  @Override
+  public boolean equals(Object to) {
+    return super.equals(to);
+  }
+}

http://git-wip-us.apache.org/repos/asf/hadoop/blob/003ae006/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopology.java
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopology.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopology.java
index 5751d2b..38c02f8 100644
--- a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopology.java
+++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopology.java
@@ -17,18 +17,9 @@
  */
 package org.apache.hadoop.net;
 
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.List;
-import java.util.Map;
-import java.util.Random;
-import java.util.TreeMap;
-import java.util.concurrent.locks.ReadWriteLock;
-import java.util.concurrent.locks.ReentrantReadWriteLock;
-
 import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
 import org.apache.hadoop.classification.InterfaceAudience;
 import org.apache.hadoop.classification.InterfaceStability;
 import org.apache.hadoop.conf.Configuration;
@@ -37,8 +28,9 @@ import org.apache.hadoop.util.ReflectionUtils;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
+import java.util.*;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.ReentrantReadWriteLock;
 
 /** The class represents a cluster of computer with a tree hierarchical
  * network topology.
@@ -81,314 +73,11 @@ public class NetworkTopology {
         NetworkTopology.class, NetworkTopology.class), conf);
   }
 
-  /** InnerNode represents a switch/router of a data center or rack.
-   * Different from a leaf node, it has non-null children.
-   */
-  static class InnerNode extends NodeBase {
-    protected List<Node> children=new ArrayList<Node>();
-    private Map<String, Node> childrenMap = new HashMap<String, Node>();
-    private int numOfLeaves;
-        
-    /** Construct an InnerNode from a path-like string */
-    InnerNode(String path) {
-      super(path);
-    }
-        
-    /** Construct an InnerNode from its name and its network location */
-    InnerNode(String name, String location) {
-      super(name, location);
-    }
-        
-    /** Construct an InnerNode
-     * from its name, its network location, its parent, and its level */
-    InnerNode(String name, String location, InnerNode parent, int level) {
-      super(name, location, parent, level);
-    }
-        
-    /** @return its children */
-    List<Node> getChildren() {return children;}
-        
-    /** @return the number of children this node has */
-    int getNumOfChildren() {
-      return children.size();
-    }
-        
-    /** Judge if this node represents a rack 
-     * @return true if it has no child or its children are not InnerNodes
-     */ 
-    boolean isRack() {
-      if (children.isEmpty()) {
-        return true;
-      }
-            
-      Node firstChild = children.get(0);
-      if (firstChild instanceof InnerNode) {
-        return false;
-      }
-            
-      return true;
-    }
-        
-    /** Judge if this node is an ancestor of node <i>n</i>
-     * 
-     * @param n a node
-     * @return true if this node is an ancestor of <i>n</i>
-     */
-    boolean isAncestor(Node n) {
-      return getPath(this).equals(NodeBase.PATH_SEPARATOR_STR) ||
-        (n.getNetworkLocation()+NodeBase.PATH_SEPARATOR_STR).
-        startsWith(getPath(this)+NodeBase.PATH_SEPARATOR_STR);
-    }
-        
-    /** Judge if this node is the parent of node <i>n</i>
-     * 
-     * @param n a node
-     * @return true if this node is the parent of <i>n</i>
-     */
-    boolean isParent(Node n) {
-      return n.getNetworkLocation().equals(getPath(this));
-    }
-        
-    /* Return a child name of this node who is an ancestor of node <i>n</i> */
-    private String getNextAncestorName(Node n) {
-      if (!isAncestor(n)) {
-        throw new IllegalArgumentException(
-                                           this + "is not an ancestor of " + n);
-      }
-      String name = n.getNetworkLocation().substring(getPath(this).length());
-      if (name.charAt(0) == PATH_SEPARATOR) {
-        name = name.substring(1);
-      }
-      int index=name.indexOf(PATH_SEPARATOR);
-      if (index !=-1)
-        name = name.substring(0, index);
-      return name;
-    }
-        
-    /** Add node <i>n</i> to the subtree of this node 
-     * @param n node to be added
-     * @return true if the node is added; false otherwise
-     */
-    boolean add(Node n) {
-      if (!isAncestor(n)) {
-        throw new IllegalArgumentException(n.getName()
-            + ", which is located at " + n.getNetworkLocation()
-            + ", is not a descendant of " + getPath(this));
-      }
-      if (isParent(n)) {
-        // this node is the parent of n; add n directly
-        n.setParent(this);
-        n.setLevel(this.level+1);
-        Node prev = childrenMap.put(n.getName(), n);
-        if (prev != null) {
-          for(int i=0; i<children.size(); i++) {
-            if (children.get(i).getName().equals(n.getName())) {
-              children.set(i, n);
-              return false;
-            }
-          }
-        }
-        children.add(n);
-        numOfLeaves++;
-        return true;
-      } else {
-        // find the next ancestor node
-        String parentName = getNextAncestorName(n);
-        InnerNode parentNode = (InnerNode)childrenMap.get(parentName);
-        if (parentNode == null) {
-          // create a new InnerNode
-          parentNode = createParentNode(parentName);
-          children.add(parentNode);
-          childrenMap.put(parentNode.getName(), parentNode);
-        }
-        // add n to the subtree of the next ancestor node
-        if (parentNode.add(n)) {
-          numOfLeaves++;
-          return true;
-        } else {
-          return false;
-        }
-      }
-    }
-
-    /**
-     * Creates a parent node to be added to the list of children.  
-     * Creates a node using the InnerNode four argument constructor specifying 
-     * the name, location, parent, and level of this node.
-     * 
-     * <p>To be overridden in subclasses for specific InnerNode implementations,
-     * as alternative to overriding the full {@link #add(Node)} method.
-     * 
-     * @param parentName The name of the parent node
-     * @return A new inner node
-     * @see InnerNode#InnerNode(String, String, InnerNode, int)
-     */
-    protected InnerNode createParentNode(String parentName) {
-      return new InnerNode(parentName, getPath(this), this, this.getLevel()+1);
-    }
-
-    /** Remove node <i>n</i> from the subtree of this node
-     * @param n node to be deleted 
-     * @return true if the node is deleted; false otherwise
-     */
-    boolean remove(Node n) {
-      if (!isAncestor(n)) {
-        throw new IllegalArgumentException(n.getName()
-            + ", which is located at " + n.getNetworkLocation()
-            + ", is not a descendant of " + getPath(this));
-      }
-      if (isParent(n)) {
-        // this node is the parent of n; remove n directly
-        if (childrenMap.containsKey(n.getName())) {
-          for (int i=0; i<children.size(); i++) {
-            if (children.get(i).getName().equals(n.getName())) {
-              children.remove(i);
-              childrenMap.remove(n.getName());
-              numOfLeaves--;
-              n.setParent(null);
-              return true;
-            }
-          }
-        }
-        return false;
-      } else {
-        // find the next ancestor node: the parent node
-        String parentName = getNextAncestorName(n);
-        InnerNode parentNode = (InnerNode)childrenMap.get(parentName);
-        if (parentNode == null) {
-          return false;
-        }
-        // remove n from the parent node
-        boolean isRemoved = parentNode.remove(n);
-        // if the parent node has no children, remove the parent node too
-        if (isRemoved) {
-          if (parentNode.getNumOfChildren() == 0) {
-            for(int i=0; i < children.size(); i++) {
-              if (children.get(i).getName().equals(parentName)) {
-                children.remove(i);
-                childrenMap.remove(parentName);
-                break;
-              }
-            }
-          }
-          numOfLeaves--;
-        }
-        return isRemoved;
-      }
-    } // end of remove
-        
-    /** Given a node's string representation, return a reference to the node
-     * @param loc string location of the form /rack/node
-     * @return null if the node is not found or the childnode is there but
-     * not an instance of {@link InnerNode}
-     */
-    private Node getLoc(String loc) {
-      if (loc == null || loc.length() == 0) return this;
-            
-      String[] path = loc.split(PATH_SEPARATOR_STR, 2);
-      Node childnode = childrenMap.get(path[0]);
-      if (childnode == null) return null; // non-existing node
-      if (path.length == 1) return childnode;
-      if (childnode instanceof InnerNode) {
-        return ((InnerNode)childnode).getLoc(path[1]);
-      } else {
-        return null;
-      }
-    }
-        
-    /** get <i>leafIndex</i> leaf of this subtree 
-     * if it is not in the <i>excludedNode</i>
-     *
-     * @param leafIndex an indexed leaf of the node
-     * @param excludedNode an excluded node (can be null)
-     * @return
-     */
-    Node getLeaf(int leafIndex, Node excludedNode) {
-      int count=0;
-      // check if the excluded node a leaf
-      boolean isLeaf =
-        excludedNode == null || !(excludedNode instanceof InnerNode);
-      // calculate the total number of excluded leaf nodes
-      int numOfExcludedLeaves =
-        isLeaf ? 1 : ((InnerNode)excludedNode).getNumOfLeaves();
-      if (isLeafParent()) { // children are leaves
-        if (isLeaf) { // excluded node is a leaf node
-          if (excludedNode != null &&
-              childrenMap.containsKey(excludedNode.getName())) {
-            int excludedIndex = children.indexOf(excludedNode);
-            if (excludedIndex != -1 && leafIndex >= 0) {
-              // excluded node is one of the children so adjust the leaf index
-              leafIndex = leafIndex>=excludedIndex ? leafIndex+1 : leafIndex;
-            }
-          }
-        }
-        // range check
-        if (leafIndex<0 || leafIndex>=this.getNumOfChildren()) {
-          return null;
-        }
-        return children.get(leafIndex);
-      } else {
-        for(int i=0; i<children.size(); i++) {
-          InnerNode child = (InnerNode)children.get(i);
-          if (excludedNode == null || excludedNode != child) {
-            // not the excludedNode
-            int numOfLeaves = child.getNumOfLeaves();
-            if (excludedNode != null && child.isAncestor(excludedNode)) {
-              numOfLeaves -= numOfExcludedLeaves;
-            }
-            if (count+numOfLeaves > leafIndex) {
-              // the leaf is in the child subtree
-              return child.getLeaf(leafIndex-count, excludedNode);
-            } else {
-              // go to the next child
-              count = count+numOfLeaves;
-            }
-          } else { // it is the excluededNode
-            // skip it and set the excludedNode to be null
-            excludedNode = null;
-          }
-        }
-        return null;
-      }
-    }
-    
-    protected boolean isLeafParent() {
-      return isRack();
-    }
-
-    /**
-      * Determine if children a leaves, default implementation calls {@link #isRack()}
-      * <p>To be overridden in subclasses for specific InnerNode implementations,
-      * as alternative to overriding the full {@link #getLeaf(int, Node)} method.
-      * 
-      * @return true if children are leaves, false otherwise
-      */
-    protected boolean areChildrenLeaves() {
-      return isRack();
-    }
-
-    /**
-     * Get number of leaves.
-     */
-    int getNumOfLeaves() {
-      return numOfLeaves;
-    }
-
-    @Override
-    public int hashCode() {
-      return super.hashCode();
-    }
-
-    @Override
-    public boolean equals(Object to) {
-      return super.equals(to);
-    }
-  } // end of InnerNode
-
+  InnerNode.Factory factory = InnerNodeImpl.FACTORY;
   /**
    * the root cluster map
    */
-  InnerNode clusterMap;
+  InnerNode clusterMap = factory.newInnerNode(NodeBase.ROOT);
   /** Depth of all leaf nodes */
   private int depthOfAllLeaves = -1;
   /** rack counter */
@@ -404,7 +93,6 @@ public class NetworkTopology {
   protected ReadWriteLock netlock = new ReentrantReadWriteLock();
 
   public NetworkTopology() {
-    clusterMap = new InnerNode(InnerNode.ROOT);
   }
 
   /** Add a leaf node

http://git-wip-us.apache.org/repos/asf/hadoop/blob/003ae006/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopologyWithNodeGroup.java
----------------------------------------------------------------------
diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopologyWithNodeGroup.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopologyWithNodeGroup.java
index 8ebe846..a20d5fc 100644
--- a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopologyWithNodeGroup.java
+++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/net/NetworkTopologyWithNodeGroup.java
@@ -36,7 +36,7 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
   public final static String DEFAULT_NODEGROUP = "/default-nodegroup";
 
   public NetworkTopologyWithNodeGroup() {
-    clusterMap = new InnerNodeWithNodeGroup(InnerNode.ROOT);
+    clusterMap = new InnerNodeWithNodeGroup(NodeBase.ROOT);
   }
 
   @Override
@@ -58,7 +58,7 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
   public String getRack(String loc) {
     netlock.readLock().lock();
     try {
-      loc = InnerNode.normalize(loc);
+      loc = NodeBase.normalize(loc);
       Node locNode = getNode(loc);
       if (locNode instanceof InnerNodeWithNodeGroup) {
         InnerNodeWithNodeGroup node = (InnerNodeWithNodeGroup) locNode;
@@ -90,7 +90,7 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
   public String getNodeGroup(String loc) {
     netlock.readLock().lock();
     try {
-      loc = InnerNode.normalize(loc);
+      loc = NodeBase.normalize(loc);
       Node locNode = getNode(loc);
       if (locNode instanceof InnerNodeWithNodeGroup) {
         InnerNodeWithNodeGroup node = (InnerNodeWithNodeGroup) locNode;
@@ -238,7 +238,7 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
       if (clusterMap.remove(node)) {
         Node nodeGroup = getNode(node.getNetworkLocation());
         if (nodeGroup == null) {
-          nodeGroup = new InnerNode(node.getNetworkLocation());
+          nodeGroup = factory.newInnerNode(node.getNetworkLocation());
         }
         InnerNode rack = (InnerNode)getNode(nodeGroup.getNetworkLocation());
         if (rack == null) {
@@ -302,16 +302,7 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
   /** InnerNodeWithNodeGroup represents a switch/router of a data center, rack
    * or physical host. Different from a leaf node, it has non-null children.
    */
-  static class InnerNodeWithNodeGroup extends InnerNode {
-    public InnerNodeWithNodeGroup(String name, String location, 
-        InnerNode parent, int level) {
-      super(name, location, parent, level);
-    }
-
-    public InnerNodeWithNodeGroup(String name, String location) {
-      super(name, location);
-    }
-
+  static class InnerNodeWithNodeGroup extends InnerNodeImpl {
     public InnerNodeWithNodeGroup(String path) {
       super(path);
     }
@@ -323,10 +314,10 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
         return false;
       }
 
-      Node firstChild = children.get(0);
+      Node firstChild = getChildren().get(0);
 
       if (firstChild instanceof InnerNode) {
-        Node firstGrandChild = (((InnerNode) firstChild).children).get(0);
+        Node firstGrandChild = (((InnerNode) firstChild).getChildren()).get(0);
         if (firstGrandChild instanceof InnerNode) {
           // it is datacenter
           return false;
@@ -343,31 +334,15 @@ public class NetworkTopologyWithNodeGroup extends NetworkTopology {
      * @return true if it has no child or its children are not InnerNodes
      */
     boolean isNodeGroup() {
-      if (children.isEmpty()) {
+      if (getChildren().isEmpty()) {
         return true;
       }
-      Node firstChild = children.get(0);
+      Node firstChild = getChildren().get(0);
       if (firstChild instanceof InnerNode) {
         // it is rack or datacenter
         return false;
       }
       return true;
     }
-    
-    @Override
-    protected boolean isLeafParent() {
-      return isNodeGroup();
-    }
-
-    @Override
-    protected InnerNode createParentNode(String parentName) {
-      return new InnerNodeWithNodeGroup(parentName, getPath(this), this,
-          this.getLevel() + 1);
-    }
-
-    @Override
-    protected boolean areChildrenLeaves() {
-      return isNodeGroup();
-    }
   }
 }

http://git-wip-us.apache.org/repos/asf/hadoop/blob/003ae006/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/net/TestNetworkTopology.java
----------------------------------------------------------------------
diff --git a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/net/TestNetworkTopology.java b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/net/TestNetworkTopology.java
index 3a281fc..62bd262 100644
--- a/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/net/TestNetworkTopology.java
+++ b/hadoop-hdfs-project/hadoop-hdfs/src/test/java/org/apache/hadoop/net/TestNetworkTopology.java
@@ -296,7 +296,7 @@ public class TestNetworkTopology {
       assertFalse(cluster.contains(dataNodes[i]));
     }
     assertEquals(0, cluster.getNumOfLeaves());
-    assertEquals(0, cluster.clusterMap.children.size());
+    assertEquals(0, cluster.clusterMap.getChildren().size());
     for(int i=0; i<dataNodes.length; i++) {
       cluster.add(dataNodes[i]);
     }


---------------------------------------------------------------------
To unsubscribe, e-mail: common-commits-unsubscribe@hadoop.apache.org
For additional commands, e-mail: common-commits-help@hadoop.apache.org