1*1c78a5d6SAndrew Rist /**************************************************************
2cdf0e10cSrcweir *
3*1c78a5d6SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
4*1c78a5d6SAndrew Rist * or more contributor license agreements. See the NOTICE file
5*1c78a5d6SAndrew Rist * distributed with this work for additional information
6*1c78a5d6SAndrew Rist * regarding copyright ownership. The ASF licenses this file
7*1c78a5d6SAndrew Rist * to you under the Apache License, Version 2.0 (the
8*1c78a5d6SAndrew Rist * "License"); you may not use this file except in compliance
9*1c78a5d6SAndrew Rist * with the License. You may obtain a copy of the License at
10*1c78a5d6SAndrew Rist *
11*1c78a5d6SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
12*1c78a5d6SAndrew Rist *
13*1c78a5d6SAndrew Rist * Unless required by applicable law or agreed to in writing,
14*1c78a5d6SAndrew Rist * software distributed under the License is distributed on an
15*1c78a5d6SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16*1c78a5d6SAndrew Rist * KIND, either express or implied. See the License for the
17*1c78a5d6SAndrew Rist * specific language governing permissions and limitations
18*1c78a5d6SAndrew Rist * under the License.
19*1c78a5d6SAndrew Rist *
20*1c78a5d6SAndrew Rist *************************************************************/
21*1c78a5d6SAndrew Rist
22*1c78a5d6SAndrew Rist
23cdf0e10cSrcweir
24cdf0e10cSrcweir #ifndef ARY_SYMTREE_NODE_HXX
25cdf0e10cSrcweir #define ARY_SYMTREE_NODE_HXX
26cdf0e10cSrcweir
27cdf0e10cSrcweir
28cdf0e10cSrcweir // USED SERVICES
29cdf0e10cSrcweir // BASE CLASSES
30cdf0e10cSrcweir // OTHER
31cdf0e10cSrcweir
32cdf0e10cSrcweir
33cdf0e10cSrcweir
34cdf0e10cSrcweir namespace ary
35cdf0e10cSrcweir {
36cdf0e10cSrcweir namespace symtree
37cdf0e10cSrcweir {
38cdf0e10cSrcweir
39cdf0e10cSrcweir
40cdf0e10cSrcweir
41cdf0e10cSrcweir /** Represents a node in a tree of symbols like a namespace tree or a
42cdf0e10cSrcweir directory tree.
43cdf0e10cSrcweir
44cdf0e10cSrcweir @tpl NODE_TRAITS
45cdf0e10cSrcweir Needs to define the types:
46cdf0e10cSrcweir entity_base_type: The type of the entities in that storage,
47cdf0e10cSrcweir e.g. ->ary::cpp::CodeEntity.
48cdf0e10cSrcweir id_type: The type of the ids of those entities,
49cdf0e10cSrcweir e.g. ->ary::cpp::Ce_id.
50cdf0e10cSrcweir
51cdf0e10cSrcweir Needs to define the functions:
52cdf0e10cSrcweir 1. static entity_base_type &
53cdf0e10cSrcweir EntityOf_(
54cdf0e10cSrcweir id_type i_id );
55cdf0e10cSrcweir 2. static symtree::Node<LeNode_Traits> *
56cdf0e10cSrcweir NodeOf_(
57cdf0e10cSrcweir const entity_base_type &
58cdf0e10cSrcweir i_entity );
59cdf0e10cSrcweir 3. static const String &
60cdf0e10cSrcweir LocalNameOf_(
61cdf0e10cSrcweir const entity_base_type &
62cdf0e10cSrcweir i_entity );
63cdf0e10cSrcweir 4. static entity_base_type *
64cdf0e10cSrcweir ParentOf_(
65cdf0e10cSrcweir const entity_base_type &
66cdf0e10cSrcweir i_entity );
67cdf0e10cSrcweir 5. template <class KEY>
68cdf0e10cSrcweir static id_t Search_(
69cdf0e10cSrcweir const entity_base_type &
70cdf0e10cSrcweir i_entity,
71cdf0e10cSrcweir const KEY & i_localKey );
72cdf0e10cSrcweir */
73cdf0e10cSrcweir template <class NODE_TRAITS>
74cdf0e10cSrcweir class Node
75cdf0e10cSrcweir {
76cdf0e10cSrcweir public:
77cdf0e10cSrcweir typedef Node<NODE_TRAITS> node_self;
78cdf0e10cSrcweir typedef typename NODE_TRAITS::entity_base_type entity_t;
79cdf0e10cSrcweir typedef typename NODE_TRAITS::id_type id_t;
80cdf0e10cSrcweir
81cdf0e10cSrcweir
82cdf0e10cSrcweir // LIFECYCLE
83cdf0e10cSrcweir /// @attention Always needs to be followed by ->Assign_Entity()!
84cdf0e10cSrcweir Node();
85cdf0e10cSrcweir explicit Node(
86cdf0e10cSrcweir entity_t & i_entity );
87cdf0e10cSrcweir void Assign_Entity(
88cdf0e10cSrcweir entity_t & i_entity );
89cdf0e10cSrcweir ~Node();
90cdf0e10cSrcweir // INQUIRY
91cdf0e10cSrcweir id_t Id();
92cdf0e10cSrcweir const String Name() const;
93cdf0e10cSrcweir int Depth() const;
94cdf0e10cSrcweir const entity_t & Entity() const;
95cdf0e10cSrcweir const node_self * Parent() const;
96cdf0e10cSrcweir
97cdf0e10cSrcweir /** Gets a child with a specific name and of a specific type.
98cdf0e10cSrcweir
99cdf0e10cSrcweir There may be more childs with the same name.
100cdf0e10cSrcweir
101cdf0e10cSrcweir @return id_t(0), if no matching child is found.
102cdf0e10cSrcweir */
103cdf0e10cSrcweir template <class KEY>
104cdf0e10cSrcweir typename NODE_TRAITS::id_type
Search(const KEY & i_localKey) const105cdf0e10cSrcweir Search(
106cdf0e10cSrcweir const KEY & i_localKey ) const
107cdf0e10cSrcweir {
108cdf0e10cSrcweir // Inline here to workaround SUNW8 compiler bug, works in SUNW12.
109cdf0e10cSrcweir return NODE_TRAITS::Search_(Entity(), i_localKey);
110cdf0e10cSrcweir }
111cdf0e10cSrcweir
112cdf0e10cSrcweir
113cdf0e10cSrcweir /** Gets a child with a specific qualified name below this node.
114cdf0e10cSrcweir
115cdf0e10cSrcweir The child may not exists.
116cdf0e10cSrcweir */
117cdf0e10cSrcweir template <class KEY>
118cdf0e10cSrcweir void SearchBelow(
119cdf0e10cSrcweir id_t & o_return, // Workaround SUNW8 compiler bug
120cdf0e10cSrcweir StringVector::const_iterator
121cdf0e10cSrcweir i_qualifiedSearchedName_begin,
122cdf0e10cSrcweir StringVector::const_iterator
123cdf0e10cSrcweir i_qualifiedSearchedName_end,
124cdf0e10cSrcweir const KEY & i_localKey ) const;
125cdf0e10cSrcweir
126cdf0e10cSrcweir /** Gets a child with a specific qualified name, either below this node
127cdf0e10cSrcweir or below any of the parent nodes.
128cdf0e10cSrcweir
129cdf0e10cSrcweir The child may not exists.
130cdf0e10cSrcweir */
131cdf0e10cSrcweir template <class KEY>
132cdf0e10cSrcweir void SearchUp(
133cdf0e10cSrcweir id_t & o_return, // Workaround SUNW8 compiler bug
134cdf0e10cSrcweir StringVector::const_iterator
135cdf0e10cSrcweir i_qualifiedSearchedName_begin,
136cdf0e10cSrcweir StringVector::const_iterator
137cdf0e10cSrcweir i_qualifiedSearchedName_end,
138cdf0e10cSrcweir const KEY & i_localKey ) const;
139cdf0e10cSrcweir // ACCESS
140cdf0e10cSrcweir entity_t & Entity();
141cdf0e10cSrcweir node_self * Parent();
142cdf0e10cSrcweir
143cdf0e10cSrcweir private:
144cdf0e10cSrcweir // Forbid copying:
145cdf0e10cSrcweir Node(const node_self&);
146cdf0e10cSrcweir node_self& operator=(const node_self&);
147cdf0e10cSrcweir
148cdf0e10cSrcweir // Locals
149cdf0e10cSrcweir void InitDepth();
150cdf0e10cSrcweir node_self * Get_Parent() const;
151cdf0e10cSrcweir node_self * NodeOf(
152cdf0e10cSrcweir id_t i_id ) const;
153cdf0e10cSrcweir
154cdf0e10cSrcweir // DATA
155cdf0e10cSrcweir entity_t * pEntity;
156cdf0e10cSrcweir int nDepth;
157cdf0e10cSrcweir };
158cdf0e10cSrcweir
159cdf0e10cSrcweir
160cdf0e10cSrcweir
161cdf0e10cSrcweir
162cdf0e10cSrcweir // IMPLEMENTATION
163cdf0e10cSrcweir
164cdf0e10cSrcweir template <class NODE_TRAITS>
165cdf0e10cSrcweir inline const typename Node<NODE_TRAITS>::entity_t &
Entity() const166cdf0e10cSrcweir Node<NODE_TRAITS>::Entity() const
167cdf0e10cSrcweir {
168cdf0e10cSrcweir csv_assert(pEntity != 0);
169cdf0e10cSrcweir return *pEntity;
170cdf0e10cSrcweir }
171cdf0e10cSrcweir
172cdf0e10cSrcweir template <class NODE_TRAITS>
173cdf0e10cSrcweir inline Node<NODE_TRAITS> *
NodeOf(id_t i_id) const174cdf0e10cSrcweir Node<NODE_TRAITS>::NodeOf(id_t i_id) const
175cdf0e10cSrcweir {
176cdf0e10cSrcweir if (i_id.IsValid())
177cdf0e10cSrcweir return NODE_TRAITS::NodeOf_(NODE_TRAITS::EntityOf_(i_id));
178cdf0e10cSrcweir return 0;
179cdf0e10cSrcweir }
180cdf0e10cSrcweir
181cdf0e10cSrcweir template <class NODE_TRAITS>
182cdf0e10cSrcweir inline Node<NODE_TRAITS> *
Get_Parent() const183cdf0e10cSrcweir Node<NODE_TRAITS>::Get_Parent() const
184cdf0e10cSrcweir {
185cdf0e10cSrcweir entity_t *
186cdf0e10cSrcweir parent = NODE_TRAITS::ParentOf_(Entity());
187cdf0e10cSrcweir if (parent != 0)
188cdf0e10cSrcweir return NODE_TRAITS::NodeOf_(*parent);
189cdf0e10cSrcweir return 0;
190cdf0e10cSrcweir }
191cdf0e10cSrcweir
192cdf0e10cSrcweir template <class NODE_TRAITS>
Node()193cdf0e10cSrcweir Node<NODE_TRAITS>::Node()
194cdf0e10cSrcweir : pEntity(0),
195cdf0e10cSrcweir nDepth(0)
196cdf0e10cSrcweir {
197cdf0e10cSrcweir }
198cdf0e10cSrcweir
199cdf0e10cSrcweir template <class NODE_TRAITS>
Node(entity_t & i_entity)200cdf0e10cSrcweir Node<NODE_TRAITS>::Node(entity_t & i_entity)
201cdf0e10cSrcweir : pEntity(&i_entity),
202cdf0e10cSrcweir nDepth(0)
203cdf0e10cSrcweir {
204cdf0e10cSrcweir InitDepth();
205cdf0e10cSrcweir }
206cdf0e10cSrcweir
207cdf0e10cSrcweir template <class NODE_TRAITS>
208cdf0e10cSrcweir void
Assign_Entity(entity_t & i_entity)209cdf0e10cSrcweir Node<NODE_TRAITS>::Assign_Entity(entity_t & i_entity)
210cdf0e10cSrcweir {
211cdf0e10cSrcweir pEntity = &i_entity;
212cdf0e10cSrcweir InitDepth();
213cdf0e10cSrcweir }
214cdf0e10cSrcweir
215cdf0e10cSrcweir template <class NODE_TRAITS>
~Node()216cdf0e10cSrcweir Node<NODE_TRAITS>::~Node()
217cdf0e10cSrcweir {
218cdf0e10cSrcweir }
219cdf0e10cSrcweir
220cdf0e10cSrcweir template <class NODE_TRAITS>
221cdf0e10cSrcweir inline typename Node<NODE_TRAITS>::id_t
Id()222cdf0e10cSrcweir Node<NODE_TRAITS>::Id()
223cdf0e10cSrcweir {
224cdf0e10cSrcweir return NODE_TRAITS::IdOf(Entity());
225cdf0e10cSrcweir }
226cdf0e10cSrcweir
227cdf0e10cSrcweir template <class NODE_TRAITS>
228cdf0e10cSrcweir inline const String
Name() const229cdf0e10cSrcweir Node<NODE_TRAITS>::Name() const
230cdf0e10cSrcweir {
231cdf0e10cSrcweir return NODE_TRAITS::LocalNameOf_(Entity());
232cdf0e10cSrcweir }
233cdf0e10cSrcweir
234cdf0e10cSrcweir template <class NODE_TRAITS>
235cdf0e10cSrcweir inline int
Depth() const236cdf0e10cSrcweir Node<NODE_TRAITS>::Depth() const
237cdf0e10cSrcweir {
238cdf0e10cSrcweir return nDepth;
239cdf0e10cSrcweir }
240cdf0e10cSrcweir
241cdf0e10cSrcweir template <class NODE_TRAITS>
242cdf0e10cSrcweir inline const Node<NODE_TRAITS> *
Parent() const243cdf0e10cSrcweir Node<NODE_TRAITS>::Parent() const
244cdf0e10cSrcweir {
245cdf0e10cSrcweir return Get_Parent();
246cdf0e10cSrcweir }
247cdf0e10cSrcweir
248cdf0e10cSrcweir template <class NODE_TRAITS>
249cdf0e10cSrcweir template <class KEY>
250cdf0e10cSrcweir void
SearchBelow(id_t & o_return,StringVector::const_iterator i_qualifiedSearchedName_begin,StringVector::const_iterator i_qualifiedSearchedName_end,const KEY & i_localKey) const251cdf0e10cSrcweir Node<NODE_TRAITS>::SearchBelow(
252cdf0e10cSrcweir id_t & o_return, // Workaround SUNW8 compiler bug
253cdf0e10cSrcweir StringVector::const_iterator i_qualifiedSearchedName_begin,
254cdf0e10cSrcweir StringVector::const_iterator i_qualifiedSearchedName_end,
255cdf0e10cSrcweir const KEY & i_localKey ) const
256cdf0e10cSrcweir {
257cdf0e10cSrcweir if (i_qualifiedSearchedName_begin != i_qualifiedSearchedName_end)
258cdf0e10cSrcweir {
259cdf0e10cSrcweir id_t
260cdf0e10cSrcweir next = Search(*i_qualifiedSearchedName_begin);
261cdf0e10cSrcweir if (next.IsValid())
262cdf0e10cSrcweir {
263cdf0e10cSrcweir const node_self *
264cdf0e10cSrcweir subnode = NodeOf(next);
265cdf0e10cSrcweir if (subnode != 0)
266cdf0e10cSrcweir {
267cdf0e10cSrcweir subnode->SearchBelow( o_return,
268cdf0e10cSrcweir i_qualifiedSearchedName_begin+1,
269cdf0e10cSrcweir i_qualifiedSearchedName_end ,
270cdf0e10cSrcweir i_localKey );
271cdf0e10cSrcweir return;
272cdf0e10cSrcweir }
273cdf0e10cSrcweir }
274cdf0e10cSrcweir o_return = id_t(0);
275cdf0e10cSrcweir return;
276cdf0e10cSrcweir }
277cdf0e10cSrcweir
278cdf0e10cSrcweir o_return = Search(i_localKey);
279cdf0e10cSrcweir }
280cdf0e10cSrcweir
281cdf0e10cSrcweir template <class NODE_TRAITS>
282cdf0e10cSrcweir template <class KEY>
283cdf0e10cSrcweir void
SearchUp(id_t & o_return,StringVector::const_iterator i_qualifiedSearchedName_begin,StringVector::const_iterator i_qualifiedSearchedName_end,const KEY & i_localKey) const284cdf0e10cSrcweir Node<NODE_TRAITS>::SearchUp(
285cdf0e10cSrcweir id_t & o_return, // Workaround SUNW8 compiler bug
286cdf0e10cSrcweir StringVector::const_iterator i_qualifiedSearchedName_begin,
287cdf0e10cSrcweir StringVector::const_iterator i_qualifiedSearchedName_end,
288cdf0e10cSrcweir const KEY & i_localKey ) const
289cdf0e10cSrcweir {
290cdf0e10cSrcweir SearchBelow( o_return,
291cdf0e10cSrcweir i_qualifiedSearchedName_begin,
292cdf0e10cSrcweir i_qualifiedSearchedName_end,
293cdf0e10cSrcweir i_localKey );
294cdf0e10cSrcweir if (o_return.IsValid())
295cdf0e10cSrcweir return;
296cdf0e10cSrcweir
297cdf0e10cSrcweir node_self *
298cdf0e10cSrcweir parent = Get_Parent();
299cdf0e10cSrcweir if (parent != 0)
300cdf0e10cSrcweir {
301cdf0e10cSrcweir parent->SearchUp( o_return,
302cdf0e10cSrcweir i_qualifiedSearchedName_begin,
303cdf0e10cSrcweir i_qualifiedSearchedName_end,
304cdf0e10cSrcweir i_localKey );
305cdf0e10cSrcweir }
306cdf0e10cSrcweir }
307cdf0e10cSrcweir
308cdf0e10cSrcweir template <class NODE_TRAITS>
309cdf0e10cSrcweir typename Node<NODE_TRAITS>::entity_t &
Entity()310cdf0e10cSrcweir Node<NODE_TRAITS>::Entity()
311cdf0e10cSrcweir {
312cdf0e10cSrcweir csv_assert(pEntity != 0);
313cdf0e10cSrcweir return *pEntity;
314cdf0e10cSrcweir }
315cdf0e10cSrcweir
316cdf0e10cSrcweir template <class NODE_TRAITS>
317cdf0e10cSrcweir inline Node<NODE_TRAITS> *
Parent()318cdf0e10cSrcweir Node<NODE_TRAITS>::Parent()
319cdf0e10cSrcweir {
320cdf0e10cSrcweir return Get_Parent();
321cdf0e10cSrcweir }
322cdf0e10cSrcweir
323cdf0e10cSrcweir template <class NODE_TRAITS>
324cdf0e10cSrcweir void
InitDepth()325cdf0e10cSrcweir Node<NODE_TRAITS>::InitDepth()
326cdf0e10cSrcweir {
327cdf0e10cSrcweir Node<NODE_TRAITS> *
328cdf0e10cSrcweir pp = Get_Parent();
329cdf0e10cSrcweir if (pp != 0)
330cdf0e10cSrcweir nDepth = pp->Depth() + 1;
331cdf0e10cSrcweir else
332cdf0e10cSrcweir nDepth = 0;
333cdf0e10cSrcweir }
334cdf0e10cSrcweir
335cdf0e10cSrcweir
336cdf0e10cSrcweir
337cdf0e10cSrcweir
338cdf0e10cSrcweir } // namespace symtree
339cdf0e10cSrcweir } // namespace ary
340cdf0e10cSrcweir #endif
341