1 files changed, 294 insertions, 0 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/graph/Node.java b/src/main/java/com/google/devtools/build/lib/graph/Node.java
new file mode 100644
index 0000000000..9db2a4c3e7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/graph/Node.java
@@ -0,0 +1,294 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed 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 com.google.devtools.build.lib.graph;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+
+/**
+ * <p>A generic directed-graph Node class.  Type parameter T is the type
+ * of the node's label.
+ *
+ * <p>Each node is identified by a label, which is unique within the graph
+ * owning the node.
+ *
+ * <p>Nodes are immutable, that is, their labels cannot be changed.  However,
+ * their predecessor/successor lists are mutable.
+ *
+ * <p>Nodes cannot be created directly by clients.
+ *
+ * <p>Clients should not confuse nodes belonging to two different graphs!  (Use
+ * Digraph.checkNode() to catch such errors.)  There is no way to find the
+ * graph to which a node belongs; it is intentionally not represented, to save
+ * space.
+ */
+public final class Node<T> {
+
+  private static final int ARRAYLIST_THRESHOLD = 6;
+  private static final int INITIAL_HASHSET_CAPACITY = 12;
+
+  // The succs and preds set representation changes depending on its size.
+  // It is implemented using the following collections:
+  // - null for size = 0.
+  // - Collections$SingletonList for size = 1.
+  // - ArrayList(6) for size = [2..6].
+  // - HashSet(12) for size > 6.
+  // These numbers were chosen based on profiling.
+
+  private final T label;
+
+  /**
+   * A duplicate-free collection of edges from this node.  May be null,
+   * indicating the empty set.
+   */
+  private Collection<Node<T>> succs = null;
+
+  /**
+   * A duplicate-free collection of edges to this node.  May be null,
+   * indicating the empty set.
+   */
+  private Collection<Node<T>> preds = null;
+
+  private final int hashCode;
+
+  /**
+   * Only Digraph.createNode() can call this!
+   */
+  Node(T label, int hashCode) {
+    if (label == null) { throw new NullPointerException("label"); }
+    this.label = label;
+    this.hashCode = hashCode;
+  }
+
+  /**
+   * Returns the label for this node.
+   */
+  public T getLabel() {
+    return label;
+  }
+
+  /**
+   * Returns a duplicate-free collection of the nodes that this node links to.
+   */
+  public Collection<Node<T>> getSuccessors() {
+    if (succs == null) {
+      return Collections.emptyList();
+    } else {
+      return Collections.unmodifiableCollection(succs);
+    }
+  }
+
+  /**
+   * Equivalent to {@code !getSuccessors().isEmpty()} but possibly more
+   * efficient.
+   */
+  public boolean hasSuccessors() {
+    return succs != null;
+  }
+
+  /**
+   * Equivalent to {@code getSuccessors().size()} but possibly more efficient.
+   */
+  public int numSuccessors() {
+    return succs == null ? 0 : succs.size();
+  }
+
+  /**
+   * Removes all edges to/from this node.
+   * Private: breaks graph invariant!
+   */
+  void removeAllEdges() {
+    this.succs = null;
+    this.preds = null;
+  }
+
+  /**
+   * Returns an (unordered, possibly immutable) set of the nodes that link to
+   * this node.
+   */
+  public Collection<Node<T>> getPredecessors() {
+    if (preds == null) {
+      return Collections.emptyList();
+    } else {
+      return Collections.unmodifiableCollection(preds);
+    }
+  }
+
+  /**
+   * Equivalent to {@code getPredecessors().size()} but possibly more
+   * efficient.
+   */
+  public int numPredecessors() {
+    return preds == null ? 0 : preds.size();
+  }
+
+  /**
+   * Equivalent to {@code !getPredecessors().isEmpty()} but possibly more
+   * efficient.
+   */
+  public boolean hasPredecessors() {
+    return preds != null;
+  }
+
+  /**
+   * Adds 'value' to either the predecessor or successor set, updating the
+   * appropriate field as necessary.
+   * @return {@code true} if the set was modified; {@code false} if the set
+   * was not modified
+   */
+  private boolean add(boolean predecessorSet, Node<T> value) {
+    final Collection<Node<T>> set = predecessorSet ? preds : succs;
+    if (set == null) {
+      // null -> SingletonList
+      return updateField(predecessorSet, Collections.singletonList(value));
+    }
+    if (set.contains(value)) {
+      // already exists in this set
+      return false;
+    }
+    int previousSize = set.size();
+    if (previousSize == 1) {
+      // SingletonList -> ArrayList
+      Collection<Node<T>> newSet =
+        new ArrayList<Node<T>>(ARRAYLIST_THRESHOLD);
+      newSet.addAll(set);
+      newSet.add(value);
+      return updateField(predecessorSet, newSet);
+    } else if (previousSize < ARRAYLIST_THRESHOLD) {
+      // ArrayList
+      set.add(value);
+      return true;
+  } else if (previousSize == ARRAYLIST_THRESHOLD) {
+      // ArrayList -> HashSet
+      Collection<Node<T>> newSet =
+        new HashSet<Node<T>>(INITIAL_HASHSET_CAPACITY);
+      newSet.addAll(set);
+      newSet.add(value);
+      return updateField(predecessorSet, newSet);
+    } else {
+      // HashSet
+      set.add(value);
+      return true;
+    }
+  }
+
+  /**
+   * Removes 'value' from either 'preds' or 'succs', updating the appropriate
+   * field as necessary.
+   * @return {@code true} if the set was modified; {@code false} if the set
+   * was not modified
+   */
+  private boolean remove(boolean predecessorSet, Node<T> value) {
+    final Collection<Node<T>> set = predecessorSet ? preds : succs;
+    if (set == null) {
+      // null
+      return false;
+    }
+
+    int previousSize = set.size();
+    if (previousSize == 1) {
+      if (set.contains(value)) {
+        // -> null
+        return updateField(predecessorSet, null);
+      } else {
+        return false;
+      }
+    }
+    // now remove the value
+    if (set.remove(value)) {
+      // may need to change representation
+      if (previousSize == 2) {
+        // -> SingletonList
+        List<Node<T>> list =
+          Collections.singletonList(set.iterator().next());
+        return updateField(predecessorSet, list);
+
+      } else if (previousSize == 1 + ARRAYLIST_THRESHOLD) {
+        // -> ArrayList
+        Collection<Node<T>> newSet =
+          new ArrayList<Node<T>>(ARRAYLIST_THRESHOLD);
+        newSet.addAll(set);
+        return updateField(predecessorSet, newSet);
+      }
+      return true;
+    }
+    return false;
+  }
+
+  /**
+   * Update either the {@link #preds} or {@link #succs} field to point to the
+   * new set.
+   * @return {@code true}, because the set must have been updated
+   */
+  private boolean updateField(boolean predecessorSet,
+      Collection<Node<T>> newSet) {
+    if (predecessorSet) {
+      preds = newSet;
+    } else {
+      succs = newSet;
+    }
+    return true;
+  }
+
+
+  /**
+   * Add 'to' as a successor of 'this' node.  Returns true iff
+   * the graph changed.  Private: breaks graph invariant!
+   */
+  boolean addSuccessor(Node<T> to) {
+    return add(false, to);
+  }
+
+  /**
+   * Add 'from' as a predecessor of 'this' node.  Returns true iff
+   * the graph changed.  Private: breaks graph invariant!
+   */
+  boolean addPredecessor(Node<T> from) {
+    return add(true, from);
+  }
+
+  /**
+   * Remove edge: fromNode.succs = {n | n in fromNode.succs && n != toNode}
+   * Private: breaks graph invariant!
+   */
+  boolean removeSuccessor(Node<T> to) {
+    return remove(false, to);
+  }
+
+  /**
+   * Remove edge: toNode.preds = {n | n in toNode.preds && n != fromNode}
+   * Private: breaks graph invariant!
+   */
+  boolean removePredecessor(Node<T> from) {
+    return remove(true, from);
+  }
+
+  @Override
+  public String toString() {
+    return "node:" + label;
+  }
+
+  @Override
+  public int hashCode() {
+    return hashCode; // Fast, deterministic.
+  }
+
+  @Override
+  public boolean equals(Object that) {
+    return this == that; // Nodes are unique for a given label
+  }
+}