• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
PolicyIterator()38   PolicyIterator()
39     : Base() {}
40 
PolicyIterator(const iterator & X)41   PolicyIterator(const iterator &X)
42     : Base(X.m_pNode) {}
43 
PolicyIterator(NodeBase * X)44   explicit PolicyIterator(NodeBase* X)
45     : Base(X) {}
46 
~PolicyIterator()47   virtual ~PolicyIterator() {}
48 
isGroup()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  ----- //
BinaryTree()96   BinaryTree()
97   : BinaryTreeBase<Input>()
98   { }
99 
~BinaryTree()100   ~BinaryTree() {
101   }
102 
103   // -----  iterators  ----- //
bfs_begin()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 
bfs_end()112   bfs_iterator bfs_end()
113   { return bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
114 
bfs_begin()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 
bfs_end()124   const_bfs_iterator bfs_end() const
125   { return const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
126 
dfs_begin()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 
dfs_end()135   dfs_iterator dfs_end()
136   { return dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
137 
dfs_begin()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 
dfs_end()147   const_dfs_iterator dfs_end() const
148   { return const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
149 
root()150   iterator root()
151   { return iterator(&(BinaryTreeBase<Input>::m_Root.node)); }
152 
root()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 
begin()161   iterator begin()
162   {
163     iterator it = iterator(BinaryTreeBase<Input>::m_Root.node.left);
164     return it;
165   }
166 
end()167   iterator end()
168   { return iterator(BinaryTreeBase<Input>::m_Root.node.right); }
169 
begin()170   const_iterator begin() const
171   {
172     const_iterator it = const_iterator(BinaryTreeBase<Input>::m_Root.node.left);
173     return it;
174   }
175 
end()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>
join(Pos position,const Input & value)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>
merge(Pos position,BinaryTree & pTree)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 {
~MoverMover251     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 {
connectSucceeder260     virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const {
261       proxy::hook<Positional>(pFrom.m_pNode, pTo.m_pNode);
262     }
263 
moveSucceeder264     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 {
connectIncluder273     virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const {
274       proxy::hook<Inclusive>(pFrom.m_pNode, pTo.m_pNode);
275     }
276 
moveIncluder277     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&
enterGroup(mcld::TreeIteratorBase pRoot)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>
insert(mcld::TreeIteratorBase pRoot,mcld::Input & pInput)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