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