//
// 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.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/ADT/GraphTraits.h"
#include "llvm/Support/DOTGraphTraits.h"
+#include <cassert>
#include <vector>
namespace llvm {
public:
class Node {
friend class Trie;
- friend class GraphTraits<Trie<Payload> >;
- typedef enum {
+ public:
+ typedef std::vector<Node*> 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<Node*> NodeVector;
- typedef typename std::vector<Node*>::iterator NodeVectorIter;
+ };
struct NodeCmp {
bool operator() (Node* N1, Node* N2) {
std::string Label;
Payload Data;
- NodeVector Children;
+ NodeVectorType Children;
// Do not implement
Node(const Node&);
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 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;
}
#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:
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<class Payload>
+bool Trie<Payload>::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<class Payload>
+const Payload& Trie<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:
+ 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<class Payload>
struct GraphTraits<Trie<Payload> > {
- typedef typename Trie<Payload>::Node NodeType;
- typedef typename std::vector<NodeType*>::iterator ChildIteratorType;
+ typedef Trie<Payload> TrieType;
+ typedef typename TrieType::Node NodeType;
+ typedef typename NodeType::iterator ChildIteratorType;
- static inline NodeType *getEntryNode(const Trie<Payload>& 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<NodeType*>::const_iterator nodes_iterator;
- static inline nodes_iterator nodes_begin(const Trie<Payload>& G) {
+ static inline nodes_iterator nodes_begin(const TrieType& G) {
return G.Nodes.begin();
}
- static inline nodes_iterator nodes_end(const Trie<Payload>& G) {
+ static inline nodes_iterator nodes_end(const TrieType& G) {
return G.Nodes.end();
}
projects / oota-llvm.git / blobdiff