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:
PolicyIterator()35 PolicyIterator()
36 : Base() {}
37
PolicyIterator(const iterator & X)38 PolicyIterator(const iterator &X)
39 : Base(X.m_pNode) {}
40
PolicyIterator(NodeBase * X)41 explicit PolicyIterator(NodeBase* X)
42 : Base(X) {}
43
~PolicyIterator()44 virtual ~PolicyIterator() {}
45
isGroup()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 ----- //
BinaryTree()93 BinaryTree()
94 : BinaryTreeBase<Input>()
95 { }
96
~BinaryTree()97 ~BinaryTree() {
98 }
99
100 // ----- iterators ----- //
bfs_begin()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
bfs_end()109 bfs_iterator bfs_end()
110 { return bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
111
bfs_begin()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
bfs_end()121 const_bfs_iterator bfs_end() const
122 { return const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
123
dfs_begin()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
dfs_end()132 dfs_iterator dfs_end()
133 { return dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
134
dfs_begin()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
dfs_end()144 const_dfs_iterator dfs_end() const
145 { return const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
146
root()147 iterator root()
148 { return iterator(&(BinaryTreeBase<Input>::m_Root.node)); }
149
root()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
begin()158 iterator begin()
159 {
160 iterator it = iterator(BinaryTreeBase<Input>::m_Root.node.left);
161 return it;
162 }
163
end()164 iterator end()
165 { return iterator(BinaryTreeBase<Input>::m_Root.node.right); }
166
begin()167 const_iterator begin() const
168 {
169 const_iterator it = const_iterator(BinaryTreeBase<Input>::m_Root.node.left);
170 return it;
171 }
172
end()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>
join(TreeIteratorBase & pPosition,const Input & value)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>
merge(TreeIteratorBase & pPosition,BinaryTree & pTree)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;
~MoverMover249 virtual ~Mover() { }
250 };
251
252 /** \class Succeeder
253 * \brief class Succeeder moves the iterator afterward.
254 */
255 struct Succeeder : public Mover {
connectSucceeder256 void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const {
257 pFrom.hook<Positional>(pTo);
258 }
259
moveSucceeder260 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 {
connectIncluder269 void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const {
270 pFrom.hook<Inclusive>(pTo);
271 }
272
moveIncluder273 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&
enterGroup(mcld::TreeIteratorBase pRoot)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>
insert(mcld::TreeIteratorBase pRoot,mcld::Input & pInput)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