Traverse.h 8.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// ============================================================================
// ==                                                                        ==
// == AMDiS - Adaptive multidimensional simulations                          ==
// ==                                                                        ==
// ============================================================================
// ==                                                                        ==
// ==  crystal growth group                                                  ==
// ==                                                                        ==
// ==  Stiftung caesar                                                       ==
// ==  Ludwig-Erhard-Allee 2                                                 ==
// ==  53175 Bonn                                                            ==
// ==  germany                                                               ==
// ==                                                                        ==
// ============================================================================
// ==                                                                        ==
// ==  http://www.caesar.de/cg/AMDiS                                         ==
// ==                                                                        ==
// ============================================================================

/** \file Traverse.h */

/** \defgroup Traverse Traverse module
 * @{ <img src="traverse.png"> @}
 *
 * \brief
 * Contains classes used for mesh traversal.
 */

#ifndef AMDIS_TRAVERSE_H
#define AMDIS_TRAVERSE_H

#include "Flag.h"
#include "Global.h"
#include "ElInfo.h"
Thomas Witkowski's avatar
Thomas Witkowski committed
35
#include "ElInfoStack.h"
36
#include "MemoryManager.h"
37
#include "OpenMP.h"
38
39
#include <vector>
#include <deque>
40
#include <stack>
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

namespace AMDiS {

  class MacroElement;
  class Mesh;

  // ===========================================================================
  // ===== class TraverseStack =================================================
  // ===========================================================================

  /** \ingroup Traverse
   * \brief
   * Mesh refinement and coarsening routines are examples of functions which 
   * need a non-recursive access to the mesh elements.
   * The implementation of the non-recursive mesh traversal routines uses a 
   * stack to save the tree path from a macro element to the current element. 
   * TraverseStack holds such information. Before calling the non-recursive mesh
   * traversal routines, such a stack must be allocated. The stack is 
   * initialized by each call to \ref traverseFirst().
   */
  class TraverseStack 
  {
  public:
    MEMORY_MANAGED(TraverseStack);

    /** \brief
     * Creates an empty TraverseStack
     */
69
70
71
72
73
74
75
    TraverseStack() 
      : traverse_mel(NULL),
        stack_size(0),
        stack_used(0),
        save_stack_used(0),
        myThreadId_(0),
        maxThreads_(1)
Thomas Witkowski's avatar
Thomas Witkowski committed
76
    {}
77
78
79
80
81
82

    /** \brief
     * Destructor
     */
    ~TraverseStack() 
    {
83
      for (int i = 0; i < static_cast<int>(elinfo_stack.size()); i++) {
84
85
	DELETE elinfo_stack[i];
      }
86
      for (int i = 0; i < static_cast<int>(save_elinfo_stack.size()); i++) {
87
88
	DELETE save_elinfo_stack[i];
      }
89
    }
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

  public:
    /** \brief
     * Returns the first ElInfo of a non recursive traversal which fullfills the
     * selection criterion specified by level and fill_flag and initializes the
     * stack. After a call of traverseFirst the next Elements are traversed via 
     * \ref traverseNext(). 
     */
    ElInfo* traverseFirst(Mesh *mesh, int level, Flag fill_flag);

    /** \brief
     * Returns the next ElInfo in a traversal initiated by \ref traverseFirst()
     * If NULL is returned, the traversal is finished.
     */
    ElInfo* traverseNext(ElInfo* elinfo_old);

106
    /// Returns the neighbour-th neighbour of elInfoOld
107
108
    ElInfo* traverseNeighbour(ElInfo* elInfoOld, int neighbour);

109
    /// Returns the neighbour-th neighbour of elInfoOld
110
111
    ElInfo* traverseNeighbour3d(ElInfo* elInfoOld, int neighbour);

112
    /// Returns the neighbour-th neighbour of elInfoOld
113
114
    ElInfo* traverseNeighbour2d(ElInfo* elInfoOld, int neighbour);

115
    /// Not yet implemented
116
117
    ElInfo* traverseMultiGridLevel();

118
    /// Preorder traversal of all elements
119
120
    ElInfo* traverseEveryElementPreorder();

121
    /// Inorder traversal of all elements
122
123
    ElInfo* traverseEveryElementInorder();

124
    /// Postorder traversal of all elements
125
126
    ElInfo* traverseEveryElementPostorder();

127
    /// Only for 3d: Calls update of all ElInfo3d onjects in \ref elinfo_stack
128
129
    void update();

130
131
    ///
    void getCoordsInElem(const ElInfo *upperElInfo, DimMat<double> *coords);
132

133
    /// Is used for parallel mesh traverse.
134
135
136
137
    inline void setMyThreadId(int myThreadId) {
      myThreadId_ = myThreadId;
    }

138
    /// Is used for parallel mesh traverse.
139
140
141
    inline void setMaxThreads(int maxThreads) {
      maxThreads_ = maxThreads;
    }
Thomas Witkowski's avatar
Thomas Witkowski committed
142

143
    ///
Thomas Witkowski's avatar
Thomas Witkowski committed
144
145
146
147
148
149
150
    int getStackData(std::vector<ElInfo*> &elInfos, std::vector<int> &infos) {
      elInfos = elinfo_stack;
      infos = info_stack;

      return stack_used;
    }

151
  private:
152
    /// Enlargement of the stack
153
154
    void enlargeTraverseStack();

155
    /// Used by \ref traverseFirst() \ref traverseNext()
156
157
    ElInfo* traverseLeafElement();

158
    /// Used by \ref traverseFirst() \ref traverseNext()
159
160
    ElInfo* traverseLeafElementLevel();

161
    /// Used by \ref traverseFirst() \ref traverseNext()
162
163
164
165
166
167
168
    ElInfo* traverseElementLevel();

    /** \brief
     * Avoids copy of a traverse stack. If copy should be possible
     * the operator must be implemented (deep copy not flat copy!)
     */
    void operator=(const TraverseStack& /*rhs*/) {
169
      FUNCNAME("TraverseStack::operator=()");
170
      ERROR_EXIT("not implemented");
171
    }
172
173
174
175
176
177

    /** \brief
     * Avoids copy of a traverse stack. If copy should be possible
     * the operator must be implemented (deep copy not flat copy!)
     */
    TraverseStack(const TraverseStack&) {
178
      FUNCNAME("TraverseStack::TraverseStack()");
179
      ERROR_EXIT("not implemented");
180
    }
181
182

  private:
183
    /// Iterator to the current MacroElement
184
    std::deque<MacroElement*>::const_iterator currentMacro;
185

186
    /// Mesh which is currently traversed
187
    Mesh* traverse_mesh;
188
189
190
191
192

    /** \brief
     * Traverse level. Used if CALL_EL_LEVEL or CALL_LEAF_EL_LEVEL are set in
     * \ref traverse_fill_flag
     */
193
    int traverse_level;
194
195
196
197
198

    /** \brief
     * Flags for traversal. Specifies which elements are visited and which
     * information are filled to the ElInfo objects.
     */
199
    Flag traverse_fill_flag;
200
  
201
    /// current macro element
202
203
    const MacroElement *traverse_mel;

204
    /// Current size of the stack
205
    int stack_size;
206

207
    /// Used size of the stack
208
    int stack_used;
209

210
    ///
211
    std::vector<ElInfo*> elinfo_stack;
212
213

    /** \brief
214
215
216
217
218
     * Stores for all level, which children of this element was already 
     * visited. If 0, no children were visited (this status occurs only
     * in intermediate computations). If 1, only the first was vistied.
     * If 2, both children of the element on this level were already 
     * visited.
219
     */
220
    std::vector<int> info_stack;
221
222

    ///
223
224
    const MacroElement *save_traverse_mel;

225
    ///
226
    std::vector<ElInfo*> save_elinfo_stack;
227

228
    ///
229
    std::vector<unsigned char> save_info_stack;
230

231
    ///
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
    int save_stack_used;

    /** \brief
     * Is used for parallel mesh traverse. The thread with the id
     * myThreadId is only allowed to access coarse elements, which id
     * satisfies: elId % maxThreads = myThreadId.
     */
    int myThreadId_;

    /** \brief
     * Is used for parallel mesh traverse. The thread with the id
     * myThreadId is only allowed to access coarse elements, which id
     * satisfies: elId % maxThreads = myThreadId.
     */
    int maxThreads_;
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
  };

  // ============================================================================
  // ===== class Traverse =======================================================
  // ============================================================================

  /** \ingroup Traverse
   * \brief
   * Class for recursive mesh traversal. Used in \ref Mesh::traverse()
   */
  class Traverse 
  {
  public:
    MEMORY_MANAGED(Traverse);

    /** \brief
     * Creates a Traverse object for Mesh m with fill flags f and level l.
     * el_fct is a pointer to a the function that will be called for every 
     * visited element.
     */
    Traverse(Mesh* m,
	     const Flag f,
	     const unsigned char l,
	     int (*ef)(ElInfo*))
Thomas Witkowski's avatar
Thomas Witkowski committed
271
272
273
274
      : mesh(m),
        flag(f),
        level(l),
        el_fct(ef) 
275
276
    {
      TEST_EXIT(m)("No traverse without mesh!\n");
277
    }
278

279
    /// Performs the recursive traversal
Thomas Witkowski's avatar
Thomas Witkowski committed
280
    int recursive(ElInfoStack*);
281
282
283
  
  private:
    Mesh *mesh;
284

285
    Flag flag; 
286

287
    int level;
288

289
290
291
292
    int (*el_fct)(ElInfo*);

    Traverse();

293
    Traverse(const Traverse&);
294
295
296
297
298
299
  };

}

#endif  // AMDIS_TRAVERSE_H