[llvm-dev] [ADT] Generalize GraphTraits NodeType* to NodePtr

[Tim Shen via llvm-dev]

Hi llvm-dev,

Recently I try to specialize GraphTraits on my own graph. I found it hard
to use, since it requires a hardcoded "NodeType *" in required function
signatures. For example, for a graph like:

  struct Graph {
    struct Node {
      MachineInstr *data;
      unsigned EdgeBeginIndex, EdgeEndIndex;
    };
    struct Edge {
      unsigned LeftNodeIndex, RightNodeIndex;
    };
    std::vector<Node> Nodes;
    std::vector<Edge> SortedEdges;
  };

It can't be easily represented via a GraphTraits specialization, Since it's
hard to let "NodeType *" carry necessary information - Nodes and
SortedEdges - about its children. I can certainly add a SortedEdges vector
pointer for each Node, but that seems unnecessary.

I propose to change the requirement from "NodeType*" to a typedef
"NodePtr", so that users can customize their own "smarter" pointers. In the
case above a NodePtr could be:

  struct NodePtr {
    Graph* G;
    unsigned Index;
    MachineInstr *&operator*() {
      return G->Nodes[Index];
    }
    // ...
  };

child_begin and child_end in GraphTraits will take NodePtr by value, and
return ChildIteratorType. Dereferencing a ChildIteratorType returns a
NodePtr by value. Dereferencing a nodes_iterator also returns a NodePtr by
value.

Do you think this is a feasible change? If so, what is the preferred way to
make this change/migration?

Thanks!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160318/d70725ce/attachment-0001.html>