course/semester2/pprog/assignment1/nbody-bh/tree.h

   1 /**
   2  * @file tree.h
   3  * @purpose Declaration of tree structures for Barnes Hut clustering algorithm for N-Body simulator
   4  * @author Sam Moore (20503628) - 2012
   5  */
   6
   7 #ifndef _TREE_H
   8 #define _TREE_H
   9
  10 #include "nbody.h"
  11
  12 #define SUB_DIVISIONS 8
  13
  14 // Define to break everything and nest the threading
  15 // (Program becomes impossibly slow, but feel free to try)
  16 // #define USE_THREADS
  17
  18 /**
  19  * Structure to represent each node of the tree (a cube (actually a prism) in space)
  20  *      I call them.... "Data Prisms"
  21  *      But that takes too long to type, so they are Node instead
  22  */
  23 typedef struct n
  24 {
  25         float x[DIMENSIONS]; // The corner of the cube with smallest valued co-ordinates
  26         float size[DIMENSIONS]; // The lengths of the cube faces.
  27
  28         Body * * body; // Array of pointers to bodies in the node; dynamically created
  29         unsigned N; // Number of bodies in the node; valid length of array
  30         unsigned allocated; //space allocated for bodies; used to dynamically resize array (doubles every time array is filled).
  31
  32         float mass;
  33         float com[DIMENSIONS]; // Centre of Mass
  34
  35         struct n * children[SUB_DIVISIONS]; // children nodes (smaller data prisms)
  36         struct n * parent; // parent node; the bodies in this node are also in the parent node (bigger data prism)
  37
  38
  39 } Node;
  40
  41 void Node_SetSpace(Node * node, float x[DIMENSIONS], float size[DIMENSIONS]); //set the position and volume of a Node
  42 void Node_Destroy(Node * node); // Cleanup a Node
  43 unsigned Node_FindBodies(Node * n, System * s); // Find all bodies in System s contained in Node n
  44 unsigned Node_Subdivide(Node * node, System * s); // Divide Node n into smaller nodes until each node has 1 Body in it
  45
  46 float Node_CalculateMass(Node * node); // Calculate the total mass of a Node
  47
  48 unsigned Node_AddBody(Node * n, Body * b); // Add a body to a Node
  49
  50 unsigned Generate_Tree(System * s, Node * n); // Generate the tree of Nodes for the *first* time
  51
  52 unsigned Update_Tree(System * s, Node * n); // Subsequently update the tree
  53
  54 unsigned Node_Forces(Body * b, Node * node, float theta); // Calculate forces on body due to node. Theta is the approximation factor.
  55
  56 void Node_FitSystem(Node * n, System * s); // Take a node and increase the size until it contains the entire system.
  57
  58
  59 Node * Node_Create(Node * parent); // Construct a node for the first time
  60
  61 bool Node_ContainsBody(Node * n, Body * b); // Check if a Body is in a Node
  62 Body * Node_Body(Node * n, unsigned index); // Identify the n'th body in a Node. Required because the Body* array is slightly special.
  63 void Draw_Node(Node * n); // Draw a cube corresponding to Node n
  64
  65
  66 // Used if nested threading is desired; not recommended. Breaks things
  67 #ifdef USE_THREADS
  68 void Prepare_Threads(unsigned max); // Attempt to create "max" threads on the next #pragma omp parallel
  69 extern unsigned nested_used; // Number of nested threads created
  70 extern omp_lock_t nested_lock; // Lock around nested_used
  71 #endif //USE_THREADS
  72
  73
  74 #endif //_TREE_H
  75
  76 //EOF