1 //===- InputTree.h --------------------------------------------------------===// 2 // 3 // The MCLinker Project 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 #ifndef MCLD_INPUTTREE_H_ 10 #define MCLD_INPUTTREE_H_ 11 12 #include "mcld/ADT/BinTree.h" 13 #include "mcld/ADT/TypeTraits.h" 14 #include "mcld/MC/Input.h" 15 #include "mcld/Support/Path.h" 16 17 #include <string> 18 19 namespace mcld { 20 21 /** \class template<typename Traits, typename Iterator> 22 * PolicyIterator<mcld::Input> 23 * \brief PolicyIterator<mcld::Input> is a partially specific PolicyIterator 24 */ 25 template <typename Traits, typename IteratorType> 26 class PolicyIterator<mcld::Input, Traits, IteratorType> 27 : public PolicyIteratorBase<Input, Traits, IteratorType> { 28 public: 29 typedef PolicyIterator<Input, Traits, IteratorType> Self; 30 typedef PolicyIteratorBase<Input, Traits, IteratorType> Base; 31 typedef PolicyIterator<Input, typename Traits::nonconst_traits, IteratorType> 32 iterator; 33 typedef PolicyIterator<Input, typename Traits::const_traits, IteratorType> 34 const_iterator; 35 36 public: 37 PolicyIterator() : Base() {} 38 39 PolicyIterator(const iterator& X) : Base(X.m_pNode) {} 40 41 explicit PolicyIterator(NodeBase* X) : Base(X) {} 42 43 virtual ~PolicyIterator() {} 44 45 bool isGroup() const { return !Base::hasData() && !Base::isRoot(); } 46 47 Self& operator++() { 48 IteratorType::advance(); 49 // skip the Group node 50 while (isGroup()) 51 IteratorType::advance(); 52 return *this; 53 } 54 55 Self operator++(int) { 56 Self tmp(*this); 57 IteratorType::advance(); 58 // skip the Group node 59 while (isGroup()) 60 IteratorType::advance(); 61 return tmp; 62 } 63 }; 64 65 template <> 66 class BinaryTree<Input> : public BinaryTreeBase<Input> { 67 public: 68 typedef size_t size_type; 69 typedef ptrdiff_t difference_type; 70 typedef Input value_type; 71 typedef value_type* pointer; 72 typedef value_type& reference; 73 typedef const value_type* const_pointer; 74 typedef const value_type& const_reference; 75 76 typedef BinaryTree<Input> Self; 77 typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator; 78 typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator; 79 80 typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> 81 dfs_iterator; 82 typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator> 83 const_dfs_iterator; 84 typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> 85 bfs_iterator; 86 typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator> 87 const_bfs_iterator; 88 89 protected: 90 typedef Node<value_type> node_type; 91 92 public: 93 // ----- constructors and destructor ----- // 94 BinaryTree() : BinaryTreeBase<Input>() {} 95 96 ~BinaryTree() {} 97 98 // ----- iterators ----- // 99 bfs_iterator bfs_begin() { 100 bfs_iterator it = bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 101 if (it.isGroup()) 102 ++it; 103 return it; 104 } 105 106 bfs_iterator bfs_end() { 107 return bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 108 } 109 110 const_bfs_iterator bfs_begin() const { 111 const_bfs_iterator it = 112 const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 113 if (it.isGroup()) 114 ++it; 115 return it; 116 } 117 118 const_bfs_iterator bfs_end() const { 119 return const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 120 } 121 122 dfs_iterator dfs_begin() { 123 dfs_iterator it = dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 124 if (it.isGroup()) 125 ++it; 126 return it; 127 } 128 129 dfs_iterator dfs_end() { 130 return dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 131 } 132 133 const_dfs_iterator dfs_begin() const { 134 const_dfs_iterator it = 135 const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left); 136 if (it.isGroup()) 137 ++it; 138 return it; 139 } 140 141 const_dfs_iterator dfs_end() const { 142 return const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); 143 } 144 145 iterator root() { return iterator(&(BinaryTreeBase<Input>::m_Root.node)); } 146 147 const_iterator root() const { 148 // FIXME: provide the iterater constructors for constant NodeBase instead of 149 // using const_cast 150 return const_iterator( 151 const_cast<NodeBase*>(&BinaryTreeBase<Input>::m_Root.node)); 152 } 153 154 iterator begin() { 155 iterator it = iterator(BinaryTreeBase<Input>::m_Root.node.left); 156 return it; 157 } 158 159 iterator end() { return iterator(BinaryTreeBase<Input>::m_Root.node.right); } 160 161 const_iterator begin() const { 162 return const_iterator(BinaryTreeBase<Input>::m_Root.node.left); 163 } 164 165 const_iterator end() const { 166 return const_iterator(BinaryTreeBase<Input>::m_Root.node.right); 167 } 168 169 // ----- modifiers ----- // 170 /// join - create a leaf node and merge it in the tree. 171 // This version of join determines the direction on compilation time. 172 // @param DIRECT the direction of the connecting edge of the parent node. 173 // @param position the parent node 174 // @param value the value being pushed. 175 template <size_t DIRECT> 176 BinaryTree& join(TreeIteratorBase& pPosition, const Input& value) { 177 node_type* node = BinaryTreeBase<Input>::createNode(); 178 node->data = const_cast<Input*>(&value); 179 180 if (pPosition.isRoot()) 181 pPosition.hook<TreeIteratorBase::Leftward>(node); 182 else 183 pPosition.hook<DIRECT>(node); 184 185 return *this; 186 } 187 188 /// merge - merge the tree 189 // @param DIRECT the direction of the connecting edge of the parent node. 190 // @param position the parent node 191 // @param the tree being joined. 192 // @return the joined tree 193 template <size_t DIRECT> 194 BinaryTree& merge(TreeIteratorBase& pPosition, BinaryTree& pTree) { 195 if (this == &pTree) 196 return *this; 197 198 if (!pTree.empty()) { 199 pPosition.hook<DIRECT>(pTree.m_Root.node.left); 200 BinaryTreeBase<Input>::m_Root.summon(pTree.BinaryTreeBase<Input>::m_Root); 201 BinaryTreeBase<Input>::m_Root.delegate(pTree.m_Root); 202 pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node; 203 } 204 return *this; 205 } 206 }; 207 208 /** \class InputTree 209 * \brief InputTree is the input tree to contains all inputs from the 210 * command line. 211 * 212 * InputTree, of course, is uncopyable. 213 * 214 * @see Input 215 */ 216 class InputTree : public BinaryTree<Input> { 217 private: 218 typedef BinaryTree<Input> BinTreeTy; 219 220 public: 221 enum Direction { 222 Inclusive = TreeIteratorBase::Leftward, 223 Positional = TreeIteratorBase::Rightward 224 }; 225 226 typedef BinaryTree<Input>::iterator iterator; 227 typedef BinaryTree<Input>::const_iterator const_iterator; 228 229 public: 230 /** \class Mover 231 * \brief Mover provides the interface for moving iterator forward. 232 * 233 * Mover is a function object (functor). @ref Mover::move moves 234 * iterator forward in certain direction. @ref Mover::connect 235 * connects two nodes of the given iterators togather. 236 */ 237 struct Mover { 238 virtual void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const = 0; 239 virtual void move(TreeIteratorBase& pNode) const = 0; 240 virtual ~Mover() {} 241 }; 242 243 /** \class Succeeder 244 * \brief class Succeeder moves the iterator afterward. 245 */ 246 struct Succeeder : public Mover { 247 void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const { 248 pFrom.hook<Positional>(pTo); 249 } 250 251 void move(TreeIteratorBase& pNode) const { pNode.move<Positional>(); } 252 }; 253 254 /** \class Includer 255 * \brief class Includer moves the iterator downward. 256 */ 257 struct Includer : public Mover { 258 void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const { 259 pFrom.hook<Inclusive>(pTo); 260 } 261 262 void move(TreeIteratorBase& pNode) const { pNode.move<Inclusive>(); } 263 }; 264 265 public: 266 static Succeeder Afterward; 267 static Includer Downward; 268 269 public: 270 using BinTreeTy::merge; 271 272 // ----- modify ----- // 273 template <size_t DIRECT> 274 InputTree& enterGroup(TreeIteratorBase pRoot); 275 276 template <size_t DIRECT> 277 InputTree& insert(TreeIteratorBase pRoot, Input& pInput); 278 279 InputTree& merge(TreeIteratorBase pRoot, 280 const Mover& pMover, 281 InputTree& pTree); 282 283 InputTree& insert(TreeIteratorBase pRoot, const Mover& pMover, Input& pInput); 284 285 InputTree& enterGroup(TreeIteratorBase pRoot, const Mover& pMover); 286 }; 287 288 bool isGroup(const InputTree::iterator& pos); 289 bool isGroup(const InputTree::const_iterator& pos); 290 bool isGroup(const InputTree::dfs_iterator& pos); 291 bool isGroup(const InputTree::const_dfs_iterator& pos); 292 bool isGroup(const InputTree::bfs_iterator& pos); 293 bool isGroup(const InputTree::const_bfs_iterator& pos); 294 295 } // namespace mcld 296 297 //===----------------------------------------------------------------------===// 298 // template member functions 299 //===----------------------------------------------------------------------===// 300 template <size_t DIRECT> 301 mcld::InputTree& mcld::InputTree::enterGroup(mcld::TreeIteratorBase pRoot) { 302 BinTreeTy::node_type* node = createNode(); 303 304 if (pRoot.isRoot()) 305 pRoot.hook<TreeIteratorBase::Leftward>(node); 306 else 307 pRoot.hook<DIRECT>(node); 308 309 return *this; 310 } 311 312 template <size_t DIRECT> 313 mcld::InputTree& mcld::InputTree::insert(mcld::TreeIteratorBase pRoot, 314 mcld::Input& pInput) { 315 BinTreeTy::node_type* node = createNode(); 316 node->data = &pInput; 317 318 if (pRoot.isRoot()) 319 pRoot.hook<TreeIteratorBase::Leftward>(node); 320 else 321 pRoot.hook<DIRECT>(node); 322 323 return *this; 324 } 325 326 #endif // MCLD_INPUTTREE_H_ 327
