Traverse.h 10.1 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
    TraverseStack() 
      : traverse_mel(NULL),
        stack_size(0),
        stack_used(0),
        save_stack_used(0),
74
	calcDisplacement(false),
75
76
        myThreadId_(0),
        maxThreads_(1)
77
    {
78
79
80
#ifdef _OPENMP
#pragma omp critical
#endif
81
      id = ElInfo::traverseIdCounter++;
82
    }
83
84
85
86
87
88

    /** \brief
     * Destructor
     */
    ~TraverseStack() 
    {
89
      for (int i = 0; i < static_cast<int>(elinfo_stack.size()); i++) {
90
91
	DELETE elinfo_stack[i];
      }
92
      for (int i = 0; i < static_cast<int>(save_elinfo_stack.size()); i++) {
93
94
	DELETE save_elinfo_stack[i];
      }
95
    }
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

  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);

    /** \brief
     * Returns the neighbour-th neighbour of elInfoOld
     */
    ElInfo* traverseNeighbour(ElInfo* elInfoOld, int neighbour);

    /** \brief
     * Returns the neighbour-th neighbour of elInfoOld
     */
    ElInfo* traverseNeighbour3d(ElInfo* elInfoOld, int neighbour);

    /** \brief
     * Returns the neighbour-th neighbour of elInfoOld
     */
    ElInfo* traverseNeighbour2d(ElInfo* elInfoOld, int neighbour);

    /** \brief
     * Not yet implemented
     */
    ElInfo* traverseMultiGridLevel();

    /** \brief
     * Preorder traversal of all elements
     */
    ElInfo* traverseEveryElementPreorder();

    /** \brief
     * Inorder traversal of all elements
     */
    ElInfo* traverseEveryElementInorder();

    /** \brief
     * Postorder traversal of all elements
     */
    ElInfo* traverseEveryElementPostorder();

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

152
    void getCoordsInElem(const ElInfo *upperElInfo, 
153
			 DimMat<double> *coords);
154

155
156
157
158
159
160
161
162
163
164
165
166
    /** \brief
     * Starts the calculation of the displacement relative to given level.
     */
    void startDisplacementCalculation(int level);
   
    /** \brief
     * Stops the calculation of displacement information.
     */
    void stopDisplacementCalculation() {
      calcDisplacement = false;
    }

167
    /** \brief
Thomas Witkowski's avatar
Thomas Witkowski committed
168
     * Is used for parallel mesh traverse.
169
170
171
172
173
174
     */
    inline void setMyThreadId(int myThreadId) {
      myThreadId_ = myThreadId;
    }

    /** \brief
Thomas Witkowski's avatar
Thomas Witkowski committed
175
     * Is used for parallel mesh traverse.
176
177
178
179
     */
    inline void setMaxThreads(int maxThreads) {
      maxThreads_ = maxThreads;
    }
Thomas Witkowski's avatar
Thomas Witkowski committed
180

Thomas Witkowski's avatar
Thomas Witkowski committed
181
182
183
184
185
186
187
    int getStackData(std::vector<ElInfo*> &elInfos, std::vector<int> &infos) {
      elInfos = elinfo_stack;
      infos = info_stack;

      return stack_used;
    }

188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
  private:
    /** \brief
     * Enlargement of the stack
     */
    void enlargeTraverseStack();

    /** \brief
     * Used by \ref traverseFirst() \ref traverseNext()
     */
    ElInfo* traverseLeafElement();

    /** \brief
     * Used by \ref traverseFirst() \ref traverseNext()
     */
    ElInfo* traverseLeafElementLevel();

    /** \brief
     * Used by \ref traverseFirst() \ref traverseNext()
     */
    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*/) {
214
      FUNCNAME("TraverseStack::operator=()");
215
      ERROR_EXIT("not implemented");
216
    }
217
218
219
220
221
222

    /** \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&) {
223
      FUNCNAME("TraverseStack::TraverseStack()");
224
      ERROR_EXIT("not implemented");
225
    }
226
227
228
229
230

  private:
    /** \brief
     * Iterator to the current MacroElement
     */
231
    std::deque<MacroElement*>::const_iterator currentMacro;
232
233
234
235

    /** \brief
     * Mesh which is currently traversed
     */
236
    Mesh* traverse_mesh;
237
238
239
240
241

    /** \brief
     * Traverse level. Used if CALL_EL_LEVEL or CALL_LEAF_EL_LEVEL are set in
     * \ref traverse_fill_flag
     */
242
    int traverse_level;
243
244
245
246
247

    /** \brief
     * Flags for traversal. Specifies which elements are visited and which
     * information are filled to the ElInfo objects.
     */
248
    Flag traverse_fill_flag;
249
250
251
252
253
254
255
256
257
  
    /** \brief
     * current macro element
     */
    const MacroElement *traverse_mel;

    /** \brief
     * Current size of the stack
     */
258
    int stack_size;
259
260
261
262

    /** \brief
     * Used size of the stack
     */
263
    int stack_used;
264
265
266
267

    /** \brief
     * 
     */
268
    std::vector<ElInfo*> elinfo_stack;
269
270

    /** \brief
271
272
273
274
275
     * 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.
276
     */
277
    std::vector<int> info_stack;
278
279
280
281
282
283
284
285
286
  
    /** \brief
     * 
     */
    const MacroElement *save_traverse_mel;

    /** \brief
     * 
     */
287
    std::vector<ElInfo*> save_elinfo_stack;
288
289
290
291

    /** \brief
     * 
     */
292
    std::vector<unsigned char> save_info_stack;
293
294
295
296

    /** \brief
     * 
     */
297
    int save_stack_used;
298
299
300
301
302
  
    /** \brief
     * 
     */
    int id;
303

304
305
306
    /** \brief
     * Stack for counting the deplacement information for dual traverse.
     */
307
    std::stack<int> displacementStack;
308
309
310
311
312
313

    /** \brief
     * True, if \ref displacementStack should be calculated.
     */
    bool calcDisplacement;

314
315
316
317
318
319
320
321
322
323
324
325
326
    /** \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_;
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
  };

  // ============================================================================
  // ===== 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
351
352
353
354
      : mesh(m),
        flag(f),
        level(l),
        el_fct(ef) 
355
356
357
    {
      TEST_EXIT(m)("No traverse without mesh!\n");
      id = ElInfo::traverseIdCounter++;
358
    }
359
360
361
362

    /** \brief
     * Performs the recursive traversal
     */  
Thomas Witkowski's avatar
Thomas Witkowski committed
363
    int recursive(ElInfoStack*);
364
365
366
  
  private:
    Mesh *mesh;
367

368
    Flag flag; 
369

370
    int level;
371

372
373
    int (*el_fct)(ElInfo*);

374
    int id;
375
376
377

    Traverse();

378
    Traverse(const Traverse&);
379
380
381
382
383
384
  };

}

#endif  // AMDIS_TRAVERSE_H