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