basilisk-docs/html/foreach__cell_8h_source.html

/** @file foreach_cell.h

 */

/* ===============================================================

 *                    Tree traversal

 * recursive() below is for reference only. The macro

 * for (int _i = 0; _i < _N; _i++) /* foreach_cell */ is a stack-based implementation of


 * recursive(). It is about 12% slower than the recursive

 * version and 60% slower than simple array traversal.

 *

 * This article was useful:

 * http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

 *

 * =============================================================== */


#define _BOTTOM (2*point.j - GHOSTS)

#define _TOP    (_BOTTOM + 1)

#define _LEFT   (2*point.i - GHOSTS)

#define _RIGHT  (_LEFT + 1)

#define _BACK   (2*point.k - GHOSTS)

#define _FRONT  (_BACK + 1)


#if 0

void recursive (Point point)

{

  if (point.level == grid->depth) {

    /* do something */

  }

  else {

    Point p1 = point; p1.level = point.level + 1;

    p1.i = _LEFT;  p1.j = _TOP;    recursive (p1);

    p1.i = _RIGHT; p1.j = _TOP;    recursive (p1);

    p1.i = _LEFT;  p1.j = _BOTTOM; recursive (p1);

    p1.i = _RIGHT; p1.j = _BOTTOM; recursive (p1);

  }

}

#endif


#define STACKSIZE 20

#if dimension == 1

#define _push(b,c,d,e,f)        \

  { _s++; stack[_s].l = b;        \

    stack[_s].i = c;          \

    stack[_s].stage = f; }

#define _pop()            \

  { point.level = stack[_s].l;        \

    point.i = stack[_s].i;        \

    stage = stack[_s].stage; _s--; }

#elif dimension == 2

#define _push(b,c,d,e,f)        \

  { _s++; stack[_s].l = b;        \

    stack[_s].i = c; stack[_s].j = d;     \

    stack[_s].stage = f; }

#define _pop()            \

  { point.level = stack[_s].l;        \

    point.i = stack[_s].i; point.j = stack[_s].j; \

    stage = stack[_s].stage; _s--; }

#else // dimension == 3

#define _push(b,c,d,e,f)            \

  { _s++; stack[_s].l = b;            \

    stack[_s].i = c; stack[_s].j = d; stack[_s].k = e;      \

    stack[_s].stage = f; }

#define _pop()                \

  { point.level = stack[_s].l;            \

    point.i = stack[_s].i; point.j = stack[_s].j; point.k = stack[_s].k; \

    stage = stack[_s].stage; _s--; }

#endif


macro2 foreach_cell_root (Point root)

{

  {

    int ig = 0, jg = 0; NOT_UNUSED(ig); NOT_UNUSED(jg);

    Point point = {0};

#if dimension == 1

    struct { int l, i, stage; } stack[STACKSIZE];

#elif dimension == 2

    struct { int l, i, j, stage; } stack[STACKSIZE];

#else // dimension == 3

    int kg = 0; NOT_UNUSED(kg);

    struct { int l, i, j, k, stage; } stack[STACKSIZE];

#endif

    int _s = -1;

    _push (root.level, root.i, root.j, root.k, 0);

    while (_s >= 0) {

      int stage;

      _pop();

      if (!allocated (0,0,0))

  continue;

      switch (stage) {

      case 0: {


  {...}


  if (point.level < grid->depth) {

    _push (point.level, point.i, point.j, point.k, 1);

    _push (point.level + 1, _LEFT, _BOTTOM, _BACK, 0);

  }

  break;

      }

#if dimension == 1

      case 1: _push (point.level + 1, _RIGHT, _BOTTOM, _BACK, 0); break;

#elif dimension == 2

      case 1: _push (point.level, point.i, point.j, point.k, 2);

  _push (point.level + 1, _LEFT,  _TOP, _BACK, 0); break;

      case 2: _push (point.level, point.i, point.j, point.k, 3);

  _push (point.level + 1, _RIGHT, _BOTTOM, _BACK, 0); break;

      case 3: _push (point.level + 1, _RIGHT, _TOP, _BACK, 0); break;

#elif dimension == 3

      case 1: _push (point.level, point.i, point.j, point.k, 2);

  _push (point.level + 1, _LEFT, _BOTTOM, _FRONT, 0); break;

      case 2: _push (point.level, point.i, point.j, point.k, 3);

  _push (point.level + 1, _LEFT, _TOP, _BACK, 0); break;

      case 3: _push (point.level, point.i, point.j, point.k, 4);

  _push (point.level + 1, _LEFT, _TOP, _FRONT, 0); break;

      case 4: _push (point.level, point.i, point.j, point.k, 5);

  _push (point.level + 1, _RIGHT, _BOTTOM, _BACK, 0); break;

      case 5: _push (point.level, point.i, point.j, point.k, 6);

  _push (point.level + 1, _RIGHT, _BOTTOM, _FRONT, 0); break;

      case 6: _push (point.level, point.i, point.j, point.k, 7);

  _push (point.level + 1, _RIGHT, _TOP, _BACK, 0); break;

      case 7: _push (point.level + 1, _RIGHT, _TOP, _FRONT, 0); break;

#endif

      }

    }

  }

}


macro2 for (int _i = 0; _i < _N; _i++) /* foreach_cell */

{

  {

#if dimension == 1

    Point root = {GHOSTS,0};

#elif dimension == 2

    Point root = {GHOSTS,GHOSTS,0};

#else // dimension == 3

    Point root = {GHOSTS,GHOSTS,GHOSTS,0};

#endif

    foreach_cell_root (root)

      {...}

  }

}


macro2 foreach_cell_all() {

  {

    Point root = {0};

    for (root.i = GHOSTS*Period.x; root.i <= GHOSTS*(2 - Period.x); root.i++)

#if dimension >= 2

      for (root.j = GHOSTS*Period.y; root.j <= GHOSTS*(2 - Period.y); root.j++)

#endif

#if dimension >= 3

  for (root.k = GHOSTS*Period.z; root.k <= GHOSTS*(2 - Period.z); root.k++)

#endif

    foreach_cell_root (root)

      {...}

  }

}


macro2 foreach_cell_post_root (bool condition, Point root)

{

  {

    int ig = 0, jg = 0; NOT_UNUSED(ig); NOT_UNUSED(jg);

    Point point = {0};

#if dimension == 1

    struct { int l, i, stage; } stack[STACKSIZE];

#elif dimension == 2

    struct { int l, i, j, stage; } stack[STACKSIZE];

#else // dimension == 3

    int kg = 0; NOT_UNUSED(kg);

    struct { int l, i, j, k, stage; } stack[STACKSIZE];

#endif

    int _s = -1;

    _push (0, root.i, root.j, root.k, 0); /* the root cell */

    while (_s >= 0) {

      int stage;

      _pop();

      if (!allocated (0,0,0))

  continue;

      switch (stage) {

      case 0: {

  if (point.level == grid->depth) {

    _push (point.level, point.i, point.j, point.k, 8);

  }

  else {

    _push (point.level, point.i, point.j, point.k, 1);

    if (condition)

      _push (point.level + 1, _LEFT, _BOTTOM, _BACK, 0);

  }

  break;

      }

#if dimension == 1

      case 1:

  _push (point.level, point.i, point.j, point.k, 2);

  if (condition)

    _push (point.level + 1, _RIGHT, _BOTTOM, _BACK, 0);

  break;

#elif dimension == 2

      case 1:

  _push (point.level, point.i, point.j, point.k, 2);

  if (condition)

    _push (point.level + 1, _LEFT, _TOP, _BACK, 0);

  break;

      case 2:

  _push (point.level, point.i, point.j, point.k, 3);

  if (condition)

    _push (point.level + 1, _RIGHT, _BOTTOM, _BACK, 0);

  break;

      case 3:

  _push (point.level, point.i, point.j, point.k, 4);

  if (condition)

    _push (point.level + 1, _RIGHT, _TOP, _BACK, 0);

  break;

#elif dimension == 3

      case 1:

  _push (point.level, point.i, point.j, point.k, 2);

  if (condition)

    _push (point.level + 1, _LEFT, _BOTTOM, _FRONT, 0);

  break;

      case 2:

  _push (point.level, point.i, point.j, point.k, 3);

  if (condition)

    _push (point.level + 1, _LEFT, _TOP, _BACK, 0);

  break;

      case 3:

  _push (point.level, point.i, point.j, point.k, 4);

  if (condition)

    _push (point.level + 1, _LEFT, _TOP, _FRONT, 0);

  break;

      case 4:

  _push (point.level, point.i, point.j, point.k, 5);

  if (condition)

    _push (point.level + 1, _RIGHT, _BOTTOM, _BACK, 0);

  break;

      case 5:

  _push (point.level, point.i, point.j, point.k, 6);

  if (condition)

    _push (point.level + 1, _RIGHT, _BOTTOM, _FRONT, 0);

  break;

      case 6:

  _push (point.level, point.i, point.j, point.k, 7);

  if (condition)

    _push (point.level + 1, _RIGHT, _TOP, _BACK, 0);

  break;

      case 7:

  _push (point.level, point.i, point.j, point.k, 8);

  if (condition)

    _push (point.level + 1, _RIGHT, _TOP, _FRONT, 0);

  break;

#endif

      default:

  {...}


      }

    }

  }

}


macro2 foreach_cell_post (bool condition)

{

  {

#if dimension == 1

    Point root = {GHOSTS,0};

#elif dimension == 2

    Point root = {GHOSTS,GHOSTS,0};

#else // dimension == 3

    Point root = {GHOSTS,GHOSTS,GHOSTS,0};

#endif

    foreach_cell_post_root (condition, root)

      {...}

  }

}


macro2 foreach_cell_post_all (bool condition)

{

  {

    Point root = {0};

    for (root.i = 0; root.i <= 2*GHOSTS; root.i++)

#if dimension >= 2

      for (root.j = 0; root.j <= 2*GHOSTS; root.j++)

#endif

#if dimension >= 3

  for (root.k = 0; root.k <= 2*GHOSTS; root.k++)

#endif

    foreach_cell_post_root (condition, root)

      {...}

  }

}


macro2 for (int _i = 0; _i < _N; _i++) /* foreach_leaf */

{

  for (int _i = 0; _i < _N; _i++) /* foreach_cell */

    if (is_leaf (cell)) {

      if (is_active(cell) && is_local(cell))

  {...}

      continue;

    }

}


#if dimension == 1

macro2 foreach_cell_restore (ivec d = Dimensions, int rootlevel = 0)

{

  if (!d.x) d.x = 1;

  for (int ox = 0; ox < d.x; ox++) {

    Point root = {GHOSTS + ox, rootlevel};

    foreach_cell_root (root)

      {...}

  }

}

#elif dimension == 2


macro2 foreach_cell_restore (ivec d = Dimensions, int rootlevel = 0)

{

  if (!d.x) d.x = 1;

  if (!d.y) d.y = 1;

  for (int ox = 0; ox < d.x; ox++)

    for (int oy = 0; oy < d.y; oy++) {

      Point root = {GHOSTS + ox, GHOSTS + oy, rootlevel};

      foreach_cell_root (root)

  {...}

    }

}


#elif dimension == 3

macro2 foreach_cell_restore (ivec d = Dimensions, int rootlevel = 0)

{

  if (!d.x) d.x = 1;

  if (!d.y) d.y = 1;

  if (!d.z) d.z = 1;

  for (int ox = 0; ox < d.x; ox++)

    for (int oy = 0; oy < d.y; oy++)

      for (int oz = 0; oz < d.z; oz++) {

  Point root = {GHOSTS + ox, GHOSTS + oy, GHOSTS + oz, rootlevel};

  foreach_cell_root (root)

    {...}

      }

}

#endif // dimension == 3

a
const vector a
Definition all-mach.h:59

dimension
#define dimension
Definition bitree.h:3

k
define k
Definition cartesian-common.h:8

l
define l
Definition cartesian-common.h:8

GHOSTS
#define GHOSTS
Definition cartesian.h:13

x
int x
Definition common.h:76

Dimensions
ivec Dimensions
Definition common.h:173

Period
struct @0 Period

grid
Grid * grid
Definition common.h:32

point
Point point
Definition conserving.h:86

j
*cs[i, 0, 0] a *[i -1, 0, 0] j
Definition embed.h:88

d
double d[2]
Definition embed.h:383

i
scalar int i
Definition embed.h:74

_pop
#define _pop()

_BACK
#define _BACK

_push
#define _push(b, c, d, e, f)

_TOP
#define _TOP

STACKSIZE
#define STACKSIZE

_BOTTOM
#define _BOTTOM

foreach_cell_all
macro2 foreach_cell_all()
Definition foreach_cell.h:142

foreach_cell_post_root
macro2 foreach_cell_post_root(bool condition, Point root)
Definition foreach_cell.h:157

_RIGHT
#define _RIGHT

foreach_cell_restore
macro2 foreach_cell_restore(ivec d=Dimensions, int rootlevel=0)
Definition foreach_cell.h:308

foreach_cell_post_all
macro2 foreach_cell_post_all(bool condition)
Definition foreach_cell.h:271

foreach_cell_post
macro2 foreach_cell_post(bool condition)
Definition foreach_cell.h:256

_FRONT
#define _FRONT

_LEFT
#define _LEFT

recursive
is a stack based implementation of * recursive(). It is about 12% slower than the recursive *version and 60% slower than simple array traversal. **This article was useful
Definition foreach_cell.h:7

stack
int stack
Definition include.c:991

cell
define is_active() cell(true) @define is_leaf(cell)(point.level

_i
def _i
Definition stencils.h:405

Grid::depth
int depth
Definition common.h:29

Point
Definition linear.h:21

Point::level
int level
Definition linear.h:23

Point::i
int i
Definition linear.h:23

ivec
Definition common.h:139

allocated
def allocated(k, l, n)(mem_allocated(((Tree *) grid) -> L[point.level]->m, point.i+k, point.j+l)) @ @def NEIGHBOR(k, l, n)(((((Tree *) grid) ->L[point.level]->m) ->b[point.i+k][point.j+l])) @ @def PARENT(k, l, n)(((((Tree *) grid) ->L[point.level-1]->m) ->b[(point.i+2)/2+k][(point.j+2)/2+l])) @ @def allocated_child(k, l, n)(level< depth() &&mem_allocated(((Tree *) grid) ->L[point.level+1]->m, 2 *point.i- 2+k, 2 *point.j- 2+l)) @ @def CHILD(k, l, n)(((((Tree *) grid) ->L[point.level+1]->m) ->b[2 *point.i- 2+k][2 *point.j- 2+l])) @ @define CELL(m)(*((Cell *)(m))) @define depth()(grid->depth) @define aparent(k, l, n) CELL(PARENT(k, l, n)) @define child(k, l, n) CELL(CHILD(k, l, n)) @define cell CELL(NEIGHBOR(0, 0, 0)) @define neighbor(k, l, n) CELL(NEIGHBOR(k, l, n)) @def neighborp(l, m, n)(Point)
Definition tree.h:253