source: XIOS/dev/branch_openmp/extern/remap/src/node.hpp @ 1328

Last change on this file since 1328 was 1328, checked in by yushan, 6 years ago

dev_omp
File size: 6.4 KB
Line 
1#ifndef __NODE_H__
2#define __NODE_H__
3
4#include <cassert>
5#include <list>
6#include <vector>
7#include <set>
8#include <map>
9#include <iostream>
10
11#include "triple.hpp"
12
13namespace sphereRemap {
14
15struct Circle
16{
17        Coord centre;
18        double radius;
19};
20
21const int MIN_NODE_SZ = 5;
22const int MAX_NODE_SZ = MIN_NODE_SZ*2; /* maximum number of elements per tree-node */
23const int TYPICAL_NODE_SZ = (2*MAX_NODE_SZ + MIN_NODE_SZ)/3;
24const double frac = 0.3;
25
26const int CLOSEST = 1;
27const int FARTHEST = -1;
28
29class CBasicTree;
30struct Node;
31
32
33//#ifdef DEBUG
34//enum alloc_stat { ALLOCATED, DELETED, BORROWED /* mostly means allocated as part of new[] or C++ container */ };
35//struct mem_info { int ref_cnt; enum alloc_stat stat; };
36////extern std::map<void*, struct mem_info> _mem_deb; // reference counter
37//std::map<void*, struct mem_info> _mem_deb; // reference counter
38//
39//// throughout the whole class, ignore NULL pointers
40//class NodePtr
41//{
42//private:
43//      Node* ptr;
44//
45//      void unlink();
46//
47//public:
48//      NodePtr() : ptr(NULL) {}
49//      NodePtr(Node* ptr) : ptr(ptr)
50//      {
51//              if (ptr)
52//              {
53//                      // if ptr does not exist yet just add it, this is not the problem we want so solve here
54//                      // if we do not do this, we run in troubles with pointers on targets allocated as part of array
55//                      // start with 1 since we assume this target is always reachable through the array
56//                      // (we do not want to fix array leaks here)
57//                      if (_mem_deb.count(ptr) == 0)
58//                      {
59//                              _mem_deb[ptr].ref_cnt = 1;
60//                              _mem_deb[ptr].stat = BORROWED;
61//                      }
62////std::cerr << "cnstr ptr " << ptr << " cnt " << _mem_deb[ptr].ref_cnt << std::endl;
63//                      _mem_deb[ptr].ref_cnt += 1;
64//              }
65//      }
66//      NodePtr(const NodePtr& other) : ptr(other.ptr)
67//      {
68////std::cerr << "copy " << ptr << " cnt " << _mem_deb[ptr].ref_cnt << std::endl;
69//              if (ptr) _mem_deb[ptr].ref_cnt += 1;
70//      }
71//      ~NodePtr()
72//      {
73//              if (ptr and _mem_deb.count(ptr)) // if our target has been deleted, that's fine
74//              {
75//                      // Target of ptr is not deleted. We want same behaviour as regular pointer here.
76////std::cerr << "destr ptr " << ptr << " cnt " << _mem_deb[ptr].ref_cnt << std::endl;
77//                      unlink();
78//              }
79//      }
80//      NodePtr& operator=(const NodePtr& other)
81//      {
82//              if (ptr == other.ptr) return *this;
83//              if (ptr and _mem_deb.count(ptr)) // if our target has been deleted, that's fine
84//              {
85////std::cerr << "overr ptr " << ptr << " cnt " << _mem_deb[ptr].ref_cnt << std::endl;
86//                      unlink();
87//              }
88//              ptr = other.ptr;
89//              if (ptr) _mem_deb[ptr].ref_cnt += 1;
90//              return *this;
91//      }
92//      Node& operator*() const
93//      {
94//              assert(ptr);
95//              return *ptr;
96//      }
97//      Node* operator->() const
98//      {
99//              assert(ptr);
100//              return ptr;
101//      }
102//      operator Node*() const
103//      {
104//              return ptr;
105//      }
106//};
107//
108//void memory_report();
109//
110//#else
111//typedef Node* NodePtr;
112//#endif
113
114typedef Node* NodePtr;
115
116struct Node
117{
118        int level; /* FIXME leafs are 0 and root is max level? */
119        int leafCount; /* number of leafs that are descendants of this node (the elements in it's cycle) */
120        Coord centre;
121        double radius;
122        NodePtr parent, ref;
123        std::vector<NodePtr> child;
124        std::list<NodePtr> intersectors;
125        bool reinserted;
126        int updateCount;  // double var;
127        CBasicTree* tree;
128        void *data;
129        int route;
130  bool toDelete ;
131
132        Node() : level(0), leafCount(1), centre(ORIGIN), radius(0), reinserted(false), updateCount(0), toDelete(false) {}
133        Node(const Coord& centre, double radius, void *data)
134                : level(0), leafCount(1), centre(centre), radius(radius), reinserted(false), updateCount(0), data(data), toDelete(false) {}
135
136//#ifdef DEBUG
137////    void *operator new[](size_t size)
138////    {
139////            void *new_array = ::new char[size];
140////std::cerr << "new vector " << new_array << " cnt " << std::endl;
141////            return new_array;
142////    }
143//      void *operator new(size_t size)
144//      {
145//              assert(size == sizeof(Node)); // also sanity? I found this on the internet, better save than sorry
146//              void *new_node = ::new char[size];
147//              assert(_mem_deb.count(new_node) == 0); // sanity that new is returned new pointer (should not happen even if code is broke)
148//              _mem_deb[new_node].ref_cnt = 0;
149//              _mem_deb[new_node].stat = ALLOCATED;
150////std::cerr << "new " << new_node << " cnt " << 0 << std::endl;
151//              return new_node;
152//      }
153//
154////    void operator delete[](void *ptr)
155////    {
156////            if (ptr)
157////            {
158////std::cerr << "delete vector " << ptr << " cnt " << _mem_deb_counter[ptr] << std::endl;
159////                    _mem_deb.erase(ptr);
160////                    ::delete [] ptr;
161////            }
162////    }
163//
164//      void operator delete(void *ptr)
165//      {
166//              if (ptr)
167//              {
168//                      assert(_mem_deb[ptr].ref_cnt); // if this fails it means Matthias is wrong (because he thinks it cannot fail)
169//                      // IF THIS FAILS we handed an invalid pointer to delete (DOUBLE FREE, POINTER ON STL CONTAINER, etc)
170//                      assert(_mem_deb[ptr].stat == ALLOCATED);
171////std::cerr << "delete " << ptr << " cnt " << _mem_deb[ptr].ref_cnt << std::endl;
172//                      // if/since there are still references to this Node, we cannot delete the memory,
173//                      // because otherwise it might get allocate it to a new Node and the reference will point to this node
174//                      // so we mark that delete has been called and free the memory when the last reference disappears
175//                      _mem_deb[ptr].stat = DELETED;
176//              }
177//      }
178//#endif
179
180        void move(const NodePtr node);
181        void remove(const NodePtr node);
182        void inflate(const NodePtr node);
183        void update();
184  void output(std::ostream& flux, int level, int color) ;
185        NodePtr closest(std::vector<NodePtr>& list, int n = CLOSEST);
186        NodePtr farthest(std::vector<NodePtr>& list);
187        void findClosest(int level, NodePtr src, double& minDist, NodePtr &closest);
188
189        void search(NodePtr node);
190        bool centreInside(Node &node);
191        bool intersects(NodePtr node);
192        bool isInside(Node &node);
193        int incluCheck();
194  void checkParent(void) ;
195        void printChildren();
196        void assignRoute(std::vector<int>::iterator& rank, int level);
197        void assignCircleAndPropagateUp(Coord *centres, double *radia, int level);
198        void printLevel(int level);
199        void routeNode(NodePtr node, int level);
200        void routingIntersecting(std::vector<Node>* routingList, NodePtr node);
201        void routeIntersection(std::vector<int>& routes, NodePtr node);
202  void getNodeLevel(int level,std::list<NodePtr>& NodeList) ;
203  bool removeDeletedNodes(int assignLevel) ;
204  void free_descendants();
205};
206
207bool transferNode(NodePtr thIs, NodePtr parent, NodePtr node);
208void findNeighbour(NodePtr thIs, NodePtr node, std::set<NodePtr>& neighbourList);
209NodePtr split(NodePtr);
210NodePtr reinsert(NodePtr);
211NodePtr insert(NodePtr, NodePtr);
212void slim2(NodePtr thIs, int level, int minNodeSize=MIN_NODE_SZ);
213
214}
215#endif
Note: See TracBrowser for help on using the repository browser.