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