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