Bring TinyPtrVector under test. Somehow we never picked up unit tests

[oota-llvm.git] / include / llvm / ADT / Trie.h

diff --git a/include/llvm/ADT/Trie.h b/include/llvm/ADT/Trie.h
index 7d2347138a1c77962fbe434007c91e9010700592..845af015b052d7a4919cb30463ffa1c3eba41bc9 100644 (file)
--- 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 <cassert>
 #include <vector>
 
 namespace llvm {
@@ -34,17 +35,20 @@ class Trie {
 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) {
@@ -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:
@@ -203,8 +220,7 @@ bool Trie<Payload>::addString(const std::string& s, const Payload& data) {
         assert(0 && "FIXME!");
         return false;
       case Node::DontMatch:
-        assert(0 && "Impossible!");
-        return false;
+        llvm_unreachable("Impossible!");
       case Node::LabelIsPrefix:
         s1 = s1.substr(nNode->label().length());
         cNode = nNode;
@@ -241,8 +257,7 @@ const Payload& Trie<Payload>::lookup(const std::string& s) const {
       case Node::StringIsPrefix:
         return Empty;
       case Node::DontMatch:
-        assert(0 && "Impossible!");
-        return Empty;
+        llvm_unreachable("Impossible!");
       case Node::LabelIsPrefix:
         s1 = s1.substr(nNode->label().length());
         cNode = nNode;
@@ -259,26 +274,25 @@ const Payload& Trie<Payload>::lookup(const std::string& s) const {
 
 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();
   }