[HADOOP-16671] Optimize InnerNodeImpl#getLeaf

• Type: Improvement
• Status: Patch Available
• Priority: Major
• Resolution: Unresolved
• Assignee: Lisheng Sun
• Reporter: Lisheng Sun
• Created: 25/Oct/19 07:17
• Updated: 22/Apr/20 06:13

Description

@Override
public Node getLeaf(int leafIndex, Node excludedNode) {
  int count=0;
  // check if the excluded node a leaf
  boolean isLeaf = !(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 {

the code InnerNodeImpl#getLeaf() as above

i think it has two problems:

1.if childrenMap.containsKey(excludedNode.getName()) return true, children.indexOf(excludedNode) must return > -1, so if (excludedIndex != -1) is it necessary?

2. if excludedindex = children.size() -1

as current code:

leafIndex = leafIndex>=excludedIndex ? leafIndex+1 : leafIndex;

leafIndex will be out of index and return null. Actually there are nodes that can be returned.

i think it should add the judgement excludedIndex == children.size() -1

Issue Links

• relates to: HDFS-11430 Separate class InnerNode from class NetworkTopology and make it extendable