From 551ccae044b0ff658fe629dd67edd5ffe75d10e8 Mon Sep 17 00:00:00 2001 From: Reid Spencer Date: Wed, 1 Sep 2004 22:55:40 +0000 Subject: Changes For Bug 352 Move include/Config and include/Support into include/llvm/Config, include/llvm/ADT and include/llvm/Support. From here on out, all LLVM public header files must be under include/llvm/. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@16137 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/Support/DepthFirstIterator.h | 230 ----------------------------------- 1 file changed, 230 deletions(-) delete mode 100644 include/Support/DepthFirstIterator.h (limited to 'include/Support/DepthFirstIterator.h') diff --git a/include/Support/DepthFirstIterator.h b/include/Support/DepthFirstIterator.h deleted file mode 100644 index c465f4e549..0000000000 --- a/include/Support/DepthFirstIterator.h +++ /dev/null @@ -1,230 +0,0 @@ -//===- Support/DepthFirstIterator.h - Depth First iterator ------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file builds on the Support/GraphTraits.h file to build generic depth -// first graph iterator. This file exposes the following functions/types: -// -// df_begin/df_end/df_iterator -// * Normal depth-first iteration - visit a node and then all of its children. -// -// idf_begin/idf_end/idf_iterator -// * Depth-first iteration on the 'inverse' graph. -// -// df_ext_begin/df_ext_end/df_ext_iterator -// * Normal depth-first iteration - visit a node and then all of its children. -// This iterator stores the 'visited' set in an external set, which allows -// it to be more efficient, and allows external clients to use the set for -// other purposes. -// -// idf_ext_begin/idf_ext_end/idf_ext_iterator -// * Depth-first iteration on the 'inverse' graph. -// This iterator stores the 'visited' set in an external set, which allows -// it to be more efficient, and allows external clients to use the set for -// other purposes. -// -//===----------------------------------------------------------------------===// - -#ifndef SUPPORT_DEPTHFIRSTITERATOR_H -#define SUPPORT_DEPTHFIRSTITERATOR_H - -#include "Support/GraphTraits.h" -#include "Support/iterator" -#include -#include - -namespace llvm { - -// df_iterator_storage - A private class which is used to figure out where to -// store the visited set. -template // Non-external set -class df_iterator_storage { -public: - SetType Visited; -}; - -template -class df_iterator_storage { -public: - df_iterator_storage(SetType &VSet) : Visited(VSet) {} - df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} - SetType &Visited; -}; - - -// Generic Depth First Iterator -template::NodeType*>, - bool ExtStorage = false, class GT = GraphTraits > -class df_iterator : public forward_iterator, - public df_iterator_storage { - typedef forward_iterator super; - - typedef typename GT::NodeType NodeType; - typedef typename GT::ChildIteratorType ChildItTy; - - // VisitStack - Used to maintain the ordering. Top = current block - // First element is node pointer, second is the 'next child' to visit - std::vector > VisitStack; -private: - inline df_iterator(NodeType *Node) { - this->Visited.insert(Node); - VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node))); - } - inline df_iterator() { /* End is when stack is empty */ } - - inline df_iterator(NodeType *Node, SetType &S) - : df_iterator_storage(S) { - if (!S.count(Node)) { - this->Visited.insert(Node); - VisitStack.push_back(std::make_pair(Node, GT::child_begin(Node))); - } - } - inline df_iterator(SetType &S) - : df_iterator_storage(S) { - // End is when stack is empty - } - -public: - typedef typename super::pointer pointer; - typedef df_iterator _Self; - - // Provide static begin and end methods as our public "constructors" - static inline _Self begin(GraphT G) { - return _Self(GT::getEntryNode(G)); - } - static inline _Self end(GraphT G) { return _Self(); } - - // Static begin and end methods as our public ctors for external iterators - static inline _Self begin(GraphT G, SetType &S) { - return _Self(GT::getEntryNode(G), S); - } - static inline _Self end(GraphT G, SetType &S) { return _Self(S); } - - inline bool operator==(const _Self& x) const { - return VisitStack.size() == x.VisitStack.size() && - VisitStack == x.VisitStack; - } - inline bool operator!=(const _Self& x) const { return !operator==(x); } - - inline pointer operator*() const { - return VisitStack.back().first; - } - - // This is a nonstandard operator-> that dereferences the pointer an extra - // time... so that you can actually call methods ON the Node, because - // the contained type is a pointer. This allows BBIt->getTerminator() f.e. - // - inline NodeType *operator->() const { return operator*(); } - - inline _Self& operator++() { // Preincrement - do { - std::pair &Top = VisitStack.back(); - NodeType *Node = Top.first; - ChildItTy &It = Top.second; - - while (It != GT::child_end(Node)) { - NodeType *Next = *It++; - if (!this->Visited.count(Next)) { // Has our next sibling been visited? - // No, do it now. - this->Visited.insert(Next); - VisitStack.push_back(std::make_pair(Next, GT::child_begin(Next))); - return *this; - } - } - - // Oops, ran out of successors... go up a level on the stack. - VisitStack.pop_back(); - } while (!VisitStack.empty()); - return *this; - } - - inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; - } - - // nodeVisited - return true if this iterator has already visited the - // specified node. This is public, and will probably be used to iterate over - // nodes that a depth first iteration did not find: ie unreachable nodes. - // - inline bool nodeVisited(NodeType *Node) const { - return this->Visited.count(Node) != 0; - } -}; - - -// Provide global constructors that automatically figure out correct types... -// -template -df_iterator df_begin(T G) { - return df_iterator::begin(G); -} - -template -df_iterator df_end(T G) { - return df_iterator::end(G); -} - -// Provide global definitions of external depth first iterators... -template ::NodeType*> > -struct df_ext_iterator : public df_iterator { - df_ext_iterator(const df_iterator &V) - : df_iterator(V) {} -}; - -template -df_ext_iterator df_ext_begin(T G, SetTy &S) { - return df_ext_iterator::begin(G, S); -} - -template -df_ext_iterator df_ext_end(T G, SetTy &S) { - return df_ext_iterator::end(G, S); -} - - -// Provide global definitions of inverse depth first iterators... -template ::NodeType*>, - bool External = false> -struct idf_iterator : public df_iterator, SetTy, External> { - idf_iterator(const df_iterator, SetTy, External> &V) - : df_iterator, SetTy, External>(V) {} -}; - -template -idf_iterator idf_begin(T G) { - return idf_iterator::begin(G); -} - -template -idf_iterator idf_end(T G){ - return idf_iterator::end(G); -} - -// Provide global definitions of external inverse depth first iterators... -template ::NodeType*> > -struct idf_ext_iterator : public idf_iterator { - idf_ext_iterator(const idf_iterator &V) - : idf_iterator(V) {} - idf_ext_iterator(const df_iterator, SetTy, true> &V) - : idf_iterator(V) {} -}; - -template -idf_ext_iterator idf_ext_begin(T G, SetTy &S) { - return idf_ext_iterator::begin(G, S); -} - -template -idf_ext_iterator idf_ext_end(T G, SetTy &S) { - return idf_ext_iterator::end(G, S); -} - -} // End llvm namespace - -#endif -- cgit v1.2.3