X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FTrie.h;h=845af015b052d7a4919cb30463ffa1c3eba41bc9;hb=40dab1059e72d3af59f2523fa8a7d05f40dafca5;hp=71a0c8ea94bca8b55d0ec60a9f4731aba796f44c;hpb=11ffccf2a5aa5fb652945ffc8dda9b8dfdf58ae8;p=oota-llvm.git diff --git a/include/llvm/ADT/Trie.h b/include/llvm/ADT/Trie.h index 71a0c8ea94b..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. // //===----------------------------------------------------------------------===// // @@ -18,6 +18,7 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/Support/DOTGraphTraits.h" +#include #include namespace llvm { @@ -34,17 +35,20 @@ class Trie { public: class Node { friend class Trie; - friend class GraphTraits >; - 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) { @@ -57,7 +61,7 @@ public: std::string Label; Payload Data; - NodeVector Children; + NodeVectorType Children; // Do not implement Node(const Node&); @@ -67,8 +71,8 @@ public: 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); } @@ -76,8 +80,8 @@ public: 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; } @@ -115,24 +119,37 @@ public: #if 0 inline void dump() { - std::cerr << "Node: " << this << "\n" + llvm::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"; + 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; - NodeVectorIter I = std::lower_bound(Children.begin(), Children.end(), + 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: @@ -178,101 +195,104 @@ public: inline Node* getRoot() const { return Nodes[0]; } - 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->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); + 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->label().length()); - cNode = nNode; - break; - default: - return Empty; - } - } else - return Empty; - } + return true; +} - return tNode->data(); +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 typename Trie::Node NodeType; - typedef typename std::vector::iterator ChildIteratorType; + typedef Trie TrieType; + typedef typename TrieType::Node NodeType; + typedef typename NodeType::iterator ChildIteratorType; - static inline NodeType *getEntryNode(const Trie& T) { + static inline NodeType *getEntryNode(const TrieType& T) { return T.getRoot(); } static inline ChildIteratorType child_begin(NodeType *N) { - return N->Children.begin(); - } - static inline ChildIteratorType child_end(NodeType *N) { - return N->Children.end(); + 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 Trie& G) { + static inline nodes_iterator nodes_begin(const TrieType& G) { return G.Nodes.begin(); } - static inline nodes_iterator nodes_end(const Trie& G) { + static inline nodes_iterator nodes_end(const TrieType& G) { return G.Nodes.end(); }