X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FTrie.h;h=845af015b052d7a4919cb30463ffa1c3eba41bc9;hb=e82fafe9e22c7f0bb35ec4cb7d5428bf9e930807;hp=21cc5fe17f41603663011c4097460a625eb6c466;hpb=41ff20bff472c942d07cf5d85b3d7cd41a140a67;p=oota-llvm.git diff --git a/include/llvm/ADT/Trie.h b/include/llvm/ADT/Trie.h index 21cc5fe17f4..845af015b05 100644 --- a/include/llvm/ADT/Trie.h +++ b/include/llvm/ADT/Trie.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Anton Korobeynikov and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -15,7 +15,10 @@ #ifndef LLVM_ADT_TRIE_H #define LLVM_ADT_TRIE_H -#include +#include "llvm/ADT/GraphTraits.h" +#include "llvm/Support/DOTGraphTraits.h" + +#include #include namespace llvm { @@ -24,22 +27,28 @@ namespace llvm { // - Labels are usually small, maybe it's better to use SmallString // - Should we use char* during construction? // - Should we templatize Empty with traits-like interface? -// - GraphTraits interface template class Trie { + friend class GraphTraits >; + friend class DOTGraphTraits >; +public: class Node { friend class Trie; - typedef enum { + public: + typedef std::vector NodeVectorType; + typedef typename NodeVectorType::iterator iterator; + typedef typename NodeVectorType::const_iterator const_iterator; + + private: + enum QueryResult { Same = -3, StringIsPrefix = -2, LabelIsPrefix = -1, DontMatch = 0, HaveCommonPart - } QueryResult; - typedef std::vector NodeVector; - typedef typename std::vector::iterator NodeVectorIter; + }; struct NodeCmp { bool operator() (Node* N1, Node* N2) { @@ -52,70 +61,27 @@ class Trie { std::string Label; Payload Data; - NodeVector Children; - public: - inline explicit Node(const Payload& data, const std::string& label = ""): - Label(label), Data(data) { } - - inline Node(const Node& n) { - Data = n.Data; - Children = n.Children; - Label = n.Label; - } - inline Node& operator=(const Node& n) { - if (&n != this) { - Data = n.Data; - Children = n.Children; - Label = n.Label; - } - - return *this; - } + NodeVectorType Children; - inline bool isLeaf() const { return Children.empty(); } - - inline const Payload& getData() const { return Data; } - inline void setData(const Payload& data) { Data = data; } - - inline void setLabel(const std::string& label) { Label = label; } - inline const std::string& getLabel() const { return Label; } - -#if 0 - inline void dump() { - std::cerr << "Node: " << this << "\n" - << "Label: " << Label << "\n" - << "Children:\n"; - - for (NodeVectorIter I = Children.begin(), E = Children.end(); I != E; ++I) - std::cerr << (*I)->Label << "\n"; - } -#endif + // Do not implement + Node(const Node&); + Node& operator=(const Node&); inline void addEdge(Node* N) { if (Children.empty()) Children.push_back(N); else { - NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), - N, NodeCmp()); + iterator I = std::lower_bound(Children.begin(), Children.end(), + N, NodeCmp()); // FIXME: no dups are allowed Children.insert(I, N); } } - inline Node* getEdge(char Id) { - Node* fNode = NULL; - NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), - Id, NodeCmp()); - if (I != Children.end() && (*I)->Label[0] == Id) - fNode = *I; - - return fNode; - } - inline void setEdge(Node* N) { char Id = N->Label[0]; - NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), - Id, NodeCmp()); + iterator I = std::lower_bound(Children.begin(), Children.end(), + Id, NodeCmp()); assert(I != Children.end() && "Node does not exists!"); *I = N; } @@ -141,13 +107,55 @@ class Trie { } else // s and Label have common (possible empty) part, return its length return (QueryResult)i; } + + public: + inline explicit Node(const Payload& data, const std::string& label = ""): + Label(label), Data(data) { } + + inline const Payload& data() const { return Data; } + inline void setData(const Payload& data) { Data = data; } + + inline const std::string& label() const { return Label; } + +#if 0 + inline void dump() { + llvm::cerr << "Node: " << this << "\n" + << "Label: " << Label << "\n" + << "Children:\n"; + + for (iterator I = Children.begin(), E = Children.end(); I != E; ++I) + llvm::cerr << (*I)->Label << "\n"; + } +#endif + + inline Node* getEdge(char Id) { + Node* fNode = NULL; + iterator I = std::lower_bound(Children.begin(), Children.end(), + Id, NodeCmp()); + if (I != Children.end() && (*I)->Label[0] == Id) + fNode = *I; + + return fNode; + } + + inline iterator begin() { return Children.begin(); } + inline const_iterator begin() const { return Children.begin(); } + inline iterator end () { return Children.end(); } + inline const_iterator end () const { return Children.end(); } + + inline size_t size () const { return Children.size(); } + inline bool empty() const { return Children.empty(); } + inline const Node* &front() const { return Children.front(); } + inline Node* &front() { return Children.front(); } + inline const Node* &back() const { return Children.back(); } + inline Node* &back() { return Children.back(); } + }; +private: std::vector Nodes; Payload Empty; - inline Node* getRoot() const { return Nodes[0]; } - inline Node* addNode(const Payload& data, const std::string label = "") { Node* N = new Node(data, label); Nodes.push_back(N); @@ -172,6 +180,10 @@ class Trie { return nNode; } + // Do not implement + Trie(const Trie&); + Trie& operator=(const Trie&); + public: inline explicit Trie(const Payload& empty):Empty(empty) { addNode(Empty); @@ -181,79 +193,142 @@ public: delete Nodes[i]; } - bool addString(const std::string& s, const Payload& data) { - Node* cNode = getRoot(); - Node* tNode = NULL; - std::string s1(s); - - while (tNode == NULL) { - char Id = s1[0]; - if (Node* nNode = cNode->getEdge(Id)) { - typename Node::QueryResult r = nNode->query(s1); - - switch (r) { - case Node::Same: - case Node::StringIsPrefix: - // Currently we don't allow to have two strings in the trie one - // being a prefix of another. This should be fixed. - assert(0 && "FIXME!"); - return false; - case Node::DontMatch: - assert(0 && "Impossible!"); - return false; - case Node::LabelIsPrefix: - s1 = s1.substr(nNode->getLabel().length()); - cNode = nNode; - break; - default: - nNode = splitEdge(cNode, Id, r); - tNode = addNode(data, s1.substr(r)); - nNode->addEdge(tNode); - } - } else { - tNode = addNode(data, s1); - cNode->addEdge(tNode); + inline Node* getRoot() const { return Nodes[0]; } + + bool addString(const std::string& s, const Payload& data); + const Payload& lookup(const std::string& s) const; + +}; + +// Define this out-of-line to dissuade the C++ compiler from inlining it. +template +bool Trie::addString(const std::string& s, const Payload& data) { + Node* cNode = getRoot(); + Node* tNode = NULL; + std::string s1(s); + + while (tNode == NULL) { + char Id = s1[0]; + if (Node* nNode = cNode->getEdge(Id)) { + typename Node::QueryResult r = nNode->query(s1); + + switch (r) { + case Node::Same: + case Node::StringIsPrefix: + // Currently we don't allow to have two strings in the trie one + // being a prefix of another. This should be fixed. + assert(0 && "FIXME!"); + return false; + case Node::DontMatch: + llvm_unreachable("Impossible!"); + case Node::LabelIsPrefix: + s1 = s1.substr(nNode->label().length()); + cNode = nNode; + break; + default: + nNode = splitEdge(cNode, Id, r); + tNode = addNode(data, s1.substr(r)); + nNode->addEdge(tNode); } + } else { + tNode = addNode(data, s1); + cNode->addEdge(tNode); } - - return true; } - const Payload& lookup(const std::string& s) const { - Node* cNode = getRoot(); - Node* tNode = NULL; - std::string s1(s); - - while (tNode == NULL) { - char Id = s1[0]; - if (Node* nNode = cNode->getEdge(Id)) { - typename Node::QueryResult r = nNode->query(s1); - - switch (r) { - case Node::Same: - tNode = nNode; - break; - case Node::StringIsPrefix: - return Empty; - case Node::DontMatch: - assert(0 && "Impossible!"); - return Empty; - case Node::LabelIsPrefix: - s1 = s1.substr(nNode->getLabel().length()); - cNode = nNode; - break; - default: - return Empty; - } - } else + return true; +} + +template +const Payload& Trie::lookup(const std::string& s) const { + Node* cNode = getRoot(); + Node* tNode = NULL; + std::string s1(s); + + while (tNode == NULL) { + char Id = s1[0]; + if (Node* nNode = cNode->getEdge(Id)) { + typename Node::QueryResult r = nNode->query(s1); + + switch (r) { + case Node::Same: + tNode = nNode; + break; + case Node::StringIsPrefix: return Empty; - } + case Node::DontMatch: + llvm_unreachable("Impossible!"); + case Node::LabelIsPrefix: + s1 = s1.substr(nNode->label().length()); + cNode = nNode; + break; + default: + return Empty; + } + } else + return Empty; + } + + return tNode->data(); +} + +template +struct GraphTraits > { + typedef Trie TrieType; + typedef typename TrieType::Node NodeType; + typedef typename NodeType::iterator ChildIteratorType; + + static inline NodeType *getEntryNode(const TrieType& T) { + return T.getRoot(); + } - return tNode->getData(); + static inline ChildIteratorType child_begin(NodeType *N) { + return N->begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } + + typedef typename std::vector::const_iterator nodes_iterator; + + static inline nodes_iterator nodes_begin(const TrieType& G) { + return G.Nodes.begin(); + } + static inline nodes_iterator nodes_end(const TrieType& G) { + return G.Nodes.end(); } }; -} +template +struct DOTGraphTraits > : public DefaultDOTGraphTraits { + typedef typename Trie::Node NodeType; + typedef typename GraphTraits >::ChildIteratorType EdgeIter; + + static std::string getGraphName(const Trie& T) { + return "Trie"; + } + + static std::string getNodeLabel(NodeType* Node, const Trie& T) { + if (T.getRoot() == Node) + return ""; + else + return Node->label(); + } + + static std::string getEdgeSourceLabel(NodeType* Node, EdgeIter I) { + NodeType* N = *I; + return N->label().substr(0, 1); + } + + static std::string getNodeAttributes(const NodeType* Node, + const Trie& T) { + if (Node->data() != T.Empty) + return "color=blue"; + + return ""; + } + +}; + +} // end of llvm namespace #endif // LLVM_ADT_TRIE_H