tree.c File Reference

contains tree build functions More...

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "global.h"
#include "inline.h"

Include dependency graph for tree.c:

Go to the source code of this file.

Functions
void	treeBuildInitial (int depth, struct bht_node **iroots, struct bht_node *node)
void	treeBuild ()
void	treeFree ()

Variables
double	tci [8][3]

Detailed Description

contains tree build functions

Definition in file tree.c.

Function Documentation

void treeBuild

(

)

This function builds an octree for local cells.

Definition at line 181 of file tree.c.

References bht_root, boxmax, boxmin, boxsize, cells, bht_node::center, bht_node::child, bht_node::father, bht_node::isempty, bht_node::leaf, leafs, bht_node::len, lnc, MPIrank, ni, nnodes, nnodes_init, nx, OMPthreads, bht_node::partnum, s, sdim, statOutStep, step, stopRun(), tnc, tree, treeBuildInitial(), cellData::x, cellData::y, and cellData::z.

{

  int i, j;
  int pow2, idepth, pparts, k, l;
  int maxTreeSize;
  struct bht_node *node;
  struct bht_node **iroots;
  int nnodes_per_thread = 0;

  if (lnc == 0)
    return;
#ifdef DEBUG
  if (MPIrank == 0 && !(step % statOutStep)) {
    printf(" Tree build...");
    fflush(stdout);
  }
#endif
  if (sdim == 3)
    tnc = 8;
  if (sdim == 2)
    tnc = 4;

  nnodes = 0;
  nnodes_init = 0;

  pow2 = 0;
  k = 1;
  while (1) {
    if (k >= OMPthreads || k >= lnc)
      break;
    k = k * 2;
    pow2 += 1;
  }

  idepth = 0;
  l = 1;
  while (1) {
    if (l >= k)
      break;
    l = l * tnc;
    idepth += 1;
  }

  if (!
      (iroots =
       (struct bht_node **) malloc(l * sizeof(struct bht_node *))))
    stopRun(106, "iroots", __FILE__, __LINE__);

  pparts = l / k;

  /* allocate memory for the leafs table */
  if (!
      (leafs =
       (struct bht_node **) malloc(lnc * sizeof(struct bht_node *))))
    stopRun(106, "leafs", __FILE__, __LINE__);

  maxTreeSize = lnc * 16;

  if (!
      (tree =
       (struct bht_node *) malloc(maxTreeSize * sizeof(struct bht_node))))
    stopRun(106, "tree", __FILE__, __LINE__);

  bht_root = &tree[0];

  nnodes_init = 1;


  boxmin[0] = nx;
  boxmin[1] = nx;
  boxmin[2] = nx;
  boxmax[0] = -nx;
  boxmax[1] = -nx;
  boxmax[2] = -nx;

  for (i = 0; i < lnc; i++) {
    boxmin[0] = (cells[i].x < boxmin[0] ? cells[i].x : boxmin[0]);
    boxmax[0] = (cells[i].x > boxmax[0] ? cells[i].x : boxmax[0]);
    boxmin[1] = (cells[i].y < boxmin[1] ? cells[i].y : boxmin[1]);
    boxmax[1] = (cells[i].y > boxmax[1] ? cells[i].y : boxmax[1]);
    boxmin[2] = (cells[i].z < boxmin[2] ? cells[i].z : boxmin[2]);
    boxmax[2] = (cells[i].z > boxmax[2] ? cells[i].z : boxmax[2]);
  }

  boxsize = boxmax[0] - boxmin[0];
  boxsize =
      (boxmax[1] - boxmin[1] > boxsize ? boxmax[1] - boxmin[1] : boxsize);
  boxsize =
      (boxmax[2] - boxmin[2] > boxsize ? boxmax[2] - boxmin[2] : boxsize);
  boxsize += 0.1;

  /* set up the root node */
  bht_root->len = boxsize;
  bht_root->center[0] = boxmin[0] + (boxmax[0] - boxmin[0]) / 2.0;
  bht_root->center[1] = boxmin[1] + (boxmax[1] - boxmin[1]) / 2.0;
  if (sdim == 3)
    bht_root->center[2] = boxmin[2] + (boxmax[2] - boxmin[2]) / 2.0;
  if (sdim == 2)
    bht_root->center[2] = 0.0;

  bht_root->leaf = 1;
  bht_root->isempty = 1;
  bht_root->father = NULL;

  for (i = 0; i < tnc; i++)
    bht_root->child[i] = NULL;

  ni = 0;

  treeBuildInitial(idepth, iroots, bht_root);

  ni = nnodes_init;

  /* stop if there are no particles in this process */
  if (lnc == 0)
    return;

#pragma omp parallel num_threads(k) private(node,i,j) firstprivate(pparts) shared(ni)
  {
    int OMPid;

    OMPid = omp_get_thread_num();

    node = bht_root;

    /* loop over cells - each cell is inserted into its own octree location */
    for (i = 0; i < lnc; i++) {
      int mycell = 0;
      int c;
      int s;
      struct bht_node *no;

      no = node;

      for (j = 0; j < pparts; j++) {
    mycell = cellInNode(i, iroots[OMPid * pparts + j]);
    if (mycell == 1) {
      no = iroots[OMPid * pparts + j];
      break;
    }
      }

      if (mycell == 0)
    continue;

      /* this loop iterates until given cell p is inserted into its location */
      while (1) {
    /* if this node is not a leaf we continue searching */
    if (no->leaf == 0) {
      c = whichChildNode(i, no);
      no = no->child[c];
      /* if this node is a leaf and it is not empty we need to move cells */
    } else if (no->leaf == 1 && no->isempty == 0) {
      for (s = 0; s < tnc; s++)
        no->child[s] = NULL;
      no->leaf = 0;
      c = whichChildNode(no->partnum, no);
      no->child[c]->partnum = no->partnum;
      no->child[c]->isempty = 0;
      leafs[no->partnum] = no->child[c];
      c = whichChildNode(i, no);
      no = no->child[c];
      /* if this node is a leaf and it is empty we insert cell into the node */
    } else {
      no->partnum = i;
      no->isempty = 0;
      leafs[i] = no;
      break;
    }
      }

    }

  }             /* end of OpenMP parallel region */

  free(iroots);
#ifdef DEBUG
  if (MPIrank == 0 && !(step % statOutStep)) {
    printf("done\n");
    fflush(stdout);
  }
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

void treeBuildInitial	(	int	depth,
		struct bht_node **	iroots,
		struct bht_node *	node
	)

This function builds an initial tree which is needed for OpenMP parallelization

Definition at line 145 of file tree.c.

References bht_node::center, bht_node::child, bht_node::father, bht_node::isempty, bht_node::leaf, bht_node::len, ni, nnodes_init, bht_node::partnum, sdim, tci, tnc, and tree.

{
  int i, j, k;
  if (depth != 0) {
    double shift;
    shift = node->len * 0.25;
    for (j = 0; j < tnc; j++) {
      node->child[j] = &tree[nnodes_init];
      node->child[j]->len = node->len * 0.5;
      node->child[j]->center[0] = node->center[0] + tci[j][0] * shift;
      node->child[j]->center[1] = node->center[1] + tci[j][1] * shift;
      if (sdim == 3)
    node->child[j]->center[2] = node->center[2] + tci[j][2] * shift;
      if (sdim == 2)
    node->child[j]->center[2] = 0.0;
      node->child[j]->father = node;
      node->child[j]->isempty = 1;
      node->child[j]->leaf = 1;
      node->leaf = 0;
      for (k = 0; k < tnc; k++)
    node->child[j]->child[k] = NULL;
      nnodes_init++;
      treeBuildInitial(depth - 1, iroots, node->child[j]);
    }
  } else {
    node->leaf = 1;
    node->partnum = -1;     /* indicates an empty node */
    iroots[ni] = node;
    ni++;
  }
}

Here is the caller graph for this function:

void treeFree

(

)

This function dealocates arrays used in tree building

Definition at line 369 of file tree.c.

References leafs, and tree.

{
  free(tree);
  free(leafs);
}

Here is the caller graph for this function:

Variable Documentation

double tci[8][3]

Initial value:

= { {-1, -1, -1}, {-1, 1, -1}, {1, -1, -1}, {1, 1, -1},
{-1, -1, 1}, {-1, 1, 1}, {1, -1, 1}, {1, 1, 1},
}

Definition at line 35 of file tree.c.