Pedantry: The last extraneous ';'s
[charm.git] / examples / bigsim / emulator / octo.C
1 #include <stdlib.h>
2 #include "blue.h"
3
4 int BCastID;
5 int ReduceID;
6 const int MAX_MESSAGES = 10;
7 const int NumBroadcasts = 10;   
8
9 extern "C" void BCastOcto(char*);
10 extern "C" void ReduceOcto(char*);
11
12 class OctoMsg;
13
14 void Octo(int, int, int, OctoMsg*, char*);
15 void SplitXYZ(int, int, int, OctoMsg*, char*);
16 bool HandleSpecial(int, int, int, OctoMsg*, char*);
17 // special cases
18 void Handle112(int, int, int, OctoMsg*, char*);
19 void Handle11X(int, int, int, OctoMsg*, char*);
20 void Handle122(int, int, int, OctoMsg*, char*);
21 void Handle12X(int, int, int, OctoMsg*, char*);
22 void Handle1XX(int, int, int, OctoMsg*, char*);
23 void Handle222(int, int, int, OctoMsg*, char*);
24 void Handle22X(int, int, int, OctoMsg*, char*);
25 void Handle2XX(int, int, int, OctoMsg*, char*);
26
27 class OctoMsg { 
28   public:
29     char core[CmiBlueGeneMsgHeaderSizeBytes];
30     int x_min, y_min, z_min;
31     int x_max, y_max, z_max;
32     bool v;  // true if min_coord already visited
33     int sender_x, sender_y, sender_z;
34
35     OctoMsg() { }
36     OctoMsg(int x1, int x2, int y1, int y2, int z1, int z2, bool visit) :
37       x_min   (x1), 
38       x_max   (x2),
39       y_min   (y1),
40       y_max   (y2),
41       z_min   (z1),
42       z_max   (z2),
43       v       (visit)
44     { 
45     }
46
47     /*
48     friend CkOutStream& operator<<(CkOutStream& os, const OctoMsg& msg)
49     {
50       os <<"OctoMsg from " <<msg.sender_x <<" " <<msg.sender_y <<" " 
51          <<msg.sender_z <<"->x(" <<msg.x_min <<"," <<msg.x_max <<")->y(" 
52          <<msg.y_min <<"," <<msg.y_max <<")->z(" <<msg.z_min <<"," 
53          <<msg.z_max <<")";
54       return os;
55     }
56     */
57     void *operator new(size_t s) { return CmiAlloc(s); }
58     void operator delete(void* ptr) { CmiFree(ptr); }
59 };
60
61 class TimeMsg {
62   public :
63     char core[CmiBlueGeneMsgHeaderSizeBytes];
64     double time;
65     TimeMsg(double t) : time(t) { }
66     void *operator new(size_t s) { return CmiAlloc(s); }
67     void operator delete(void* ptr) { CmiFree(ptr); }
68 };
69
70 // for storing results of different tests
71 struct TimeRecord 
72 {
73   int    test_num;
74   double* max_time;
75   double* start_time;
76
77   TimeRecord() : test_num(0) {
78     max_time = new double[NumBroadcasts];
79     start_time = new double[NumBroadcasts];
80     for (int i=0; i<NumBroadcasts; i++) {
81       max_time[i] = start_time[i] = 0.0;
82     }
83   }
84
85   ~TimeRecord() {
86     delete [] max_time;
87     delete [] start_time;
88   }
89      
90   void Print(char* info) {
91     //print result
92     double average = 0.0;
93     int sizeX, sizeY, sizeZ;
94     BgGetSize(&sizeX, &sizeY, &sizeZ);
95     int numComm = BgGetNumCommThread();
96     int numWork = BgGetNumWorkThread();
97
98     CmiPrintf("\nResults for %d by %d by %d with %d comm %d work\n\n",
99               sizeX, sizeY, sizeZ, numComm, numWork);
100     CmiPrintf("-------------------------------------------------------------\n"
101               "Iter No:    StartTime           EndTime          TotalTime   \n"
102               "-------------------------------------------------------------\n");
103     for (int i=0; i<NumBroadcasts; i++) {
104       CmiPrintf("    %d         %f               %f           %f\n",
105                 i, start_time[i], max_time[i], max_time[i] - start_time[i]);
106       average += max_time[i] - start_time[i];
107     }
108     CmiPrintf("-------------------------------------------------------------\n"
109               "Average BroadCast Time:                      %f\n"
110               "-------------------------------------------------------------\n",
111               average/NumBroadcasts);
112     BgShutdown();
113   }
114 };
115
116 struct OctoData 
117 {
118   OctoMsg     messages[MAX_MESSAGES];
119   int         dest_x[MAX_MESSAGES];
120   int         dest_y[MAX_MESSAGES];
121   int         dest_z[MAX_MESSAGES];
122   int         root_x, root_y, root_z;
123   int         parent_x, parent_y, parent_z;
124   TimeRecord* record;
125   
126   OctoData(int x, int y, int z): 
127     root_x       (x),
128     root_y       (y),
129     root_z       (z),
130     record       (NULL)
131  { }
132 };
133
134 BnvStaticDeclare(int, num_messages)
135 BnvStaticDeclare(double, max_time)
136 BnvStaticDeclare(int, reduce_count)
137
138 void BgEmulatorInit(int argc, char** argv)
139 {
140   if (argc < 6) { 
141     CmiPrintf("Usage: octo <x> <y> <z> <numComm> <numWork> \n"); 
142     BgShutdown();
143   }
144     
145   BgSetSize(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]));
146   BgSetNumCommThread(atoi(argv[4]));
147   BgSetNumWorkThread(atoi(argv[5]));
148
149 }
150
151 void BgWorkThreadInit(int argc, char** argv)
152 {
153 }
154
155 void BgNodeStart(int argc, char** argv)
156 {
157   BCastID = BgRegisterHandler(BCastOcto);
158   ReduceID  = BgRegisterHandler(ReduceOcto);
159
160   int x, y, z;
161   BgGetMyXYZ(&x, &y, &z);
162   int numBgX, numBgY, numBgZ;
163   BgGetSize(&numBgX, &numBgY, &numBgZ);
164
165   BnvInitialize(int, num_messages);
166   BnvAccess(num_messages) = -1;
167   BnvInitialize(double, max_time);
168   BnvAccess(max_time) = 0.0;
169   BnvInitialize(int, reduce_count);
170   BnvAccess(reduce_count) = 0;
171  
172   
173   int center_x = (numBgX == 2) ? 0 : numBgX/2;
174   int center_y = (numBgY == 2) ? 0 : numBgY/2;
175   int center_z = (numBgZ == 2) ? 0 : numBgZ/2;
176   OctoData* data = new OctoData(center_x, center_y, center_z);
177   BgSetNodeData((char*)data);
178
179   // check to see if center node
180   if (x == center_x && y == center_y && z == center_z) 
181   {
182     data->record = new TimeRecord();
183     OctoMsg* msg = new OctoMsg(0, numBgX-1, 0, numBgY-1, 0, numBgZ-1, false);
184     BgSendLocalPacket(ANYTHREAD, BCastID, LARGE_WORK, sizeof(OctoMsg), 
185                       (char*)msg);
186   }
187 }
188
189 void BCastOcto(char* info) {
190   int x, y, z;
191   BgGetMyXYZ(&x, &y, &z);
192
193   OctoMsg* m = (OctoMsg*)info;
194   OctoData* d = (OctoData*)BgGetNodeData();
195   
196   // CmiPrintf("BCastOcto at %d %d %d range x=(%d,%d) y=(%d,%d) z=(%d,%d)\n", 
197   //           x, y, z, m->x_min, m->x_max, m->y_min, m->y_max, m->z_min, 
198   //           m->z_max);
199
200   if (x == d->root_x && y == d->root_y && z == d->root_z) {
201     if (d->record == NULL) {
202       CmiPrintf("Error, root node should have timing info\n");
203       BgShutdown();
204       return;
205     }
206     TimeRecord* r = d->record;
207     r->start_time[r->test_num] = BgGetTime();
208     // CmiPrintf("Starting new broadcast at %f\n", r->start_time[r->test_num]);
209   }
210
211   // if first time through, calculate correct nodes to send
212   if (BnvAccess(num_messages) == -1) { 
213     d->parent_x = m->sender_x;
214     d->parent_y = m->sender_y;
215     d->parent_z = m->sender_z;
216   
217     SplitXYZ(x, y, z, m, info); 
218   }
219
220   // once calculated, send to nodes
221   if (BnvAccess(num_messages) <= 0) {
222     // this is a terminal node, so start reduction
223     TimeMsg* parent = new TimeMsg(BgGetTime());
224     // CmiPrintf("  Terminal node, time %f to %d %d %d\n", 
225     //           parent->time, d->parent_x, d->parent_y, d->parent_z);
226     BgSendPacket(d->parent_x, d->parent_y, d->parent_z, 
227                  ANYTHREAD, ReduceID, SMALL_WORK, sizeof(TimeMsg), 
228                  (char*)parent);
229   }
230   else {
231     // CmiPrintf("  There are %d messages\n", d->num_messages);
232     for (int i=0; i<BnvAccess(num_messages); i++) {
233       OctoMsg* msg = new OctoMsg(d->messages[i]);
234       // CmiPrintf("    Sending message %d/%d to %d %d %d\n", i+1, 
235       //           d->num_messages, d->dest_x[i], d->dest_y[i], d->dest_z[i]);
236       BgSendPacket(d->dest_x[i], d->dest_y[i], d->dest_z[i], 
237                    ANYTHREAD, BCastID, SMALL_WORK, sizeof(OctoMsg), (char*)msg);
238     }
239   }
240 }
241
242 void ReduceOcto(char* info) 
243 {
244   int x, y, z;
245   BgGetMyXYZ(&x, &y, &z);
246
247   OctoData* d = (OctoData*)BgGetNodeData();
248   TimeMsg* msg = (TimeMsg*)info;
249
250   BnvAccess(reduce_count)++;
251
252   //CmiPrintf("ReduceOcto at node %d %d %d message %d/%d with time %f "
253   //          "max time is %f\n", x, y, z, BnvAccess(reduce_count), 
254   //          BnvAccess(num_messages), msg->time, BnvAccess(max_time));
255
256   if (msg->time > BnvAccess(max_time)) { BnvAccess(max_time) = msg->time; }
257
258   // check to see if all children have been heard from
259   if (BnvAccess(reduce_count) >= BnvAccess(num_messages)) {
260     BnvAccess(reduce_count) = 0;
261
262     if (x == d->root_x && y == d->root_y && z == d->root_z) {
263       // this is the root node
264       TimeRecord* r = d->record;
265       r->max_time[r->test_num] = BnvAccess(max_time);
266       r->test_num++;
267       if (r->test_num < NumBroadcasts) {
268         // start bcast all over again
269         int numBgX, numBgY, numBgZ;
270         BgGetSize(&numBgX, &numBgY, &numBgZ);
271         OctoMsg* start = 
272           new OctoMsg(0, numBgX-1, 0, numBgY-1, 0, numBgZ-1, false);
273         BgSendLocalPacket(ANYTHREAD, BCastID, SMALL_WORK, sizeof(OctoMsg), 
274                           (char*)start);
275       }
276       else {
277         // print results and quit
278         r->Print(info);
279         BgShutdown();
280         return;
281       }
282     }
283     else {
284       // this is not the root node
285       TimeMsg* parent = new TimeMsg(BnvAccess(max_time));
286       BgSendPacket(d->parent_x, d->parent_y, d->parent_z, ANYTHREAD, ReduceID,
287                    SMALL_WORK, sizeof(TimeMsg), (char*)parent);
288       BnvAccess(max_time) = 0;
289     }
290   }
291 }
292
293 void SplitXYZ
294 (
295   int         x,     // x pos of node
296   int         y,     // y pos of node
297   int         z,     // z pos of node
298   OctoMsg*    m,     // message with limit data
299   char* info
300 )
301 {
302   // check terminal case
303   if (x == m->x_min && x == m->x_max &&
304       y == m->y_min && y == m->y_max &&
305       z == m->z_min && z == m->z_max)
306   {
307     return;
308   }
309   
310   if (HandleSpecial(x, y, z, m, info)) { return; }
311
312   int del_x = m->x_max - m->x_min;
313   int del_y = m->y_max - m->y_min;
314   int del_z = m->z_max - m->z_min;
315
316   // calculate new midpoints
317   int x_lo = (m->x_min + x - 1)/2;  int x_hi = (m->x_max + x)/2;
318   int y_lo = (m->y_min + y - 1)/2;  int y_hi = (m->y_max + y)/2;
319   int z_lo = (m->z_min + z - 1)/2;  int z_hi = (m->z_max + z)/2;
320   
321   OctoMsg* new_msg = NULL;
322
323   // x_lo, y_lo, z_lo
324   new_msg = new OctoMsg(m->x_min, x-1, m->y_min, y-1, m->z_min, z-1, m->v);
325   if (x_lo == m->x_min && y_lo == m->y_min && z_lo == m->z_min && m->v) {
326     SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
327     delete new_msg;
328   }
329   else { Octo(x_lo, y_lo, z_lo, new_msg, info); }
330   // x_lo, y_lo, z_hi
331   new_msg = new OctoMsg(m->x_min, x-1, m->y_min, y-1, z, m->z_max, false);
332   Octo(x_lo, y_lo, z_hi, new_msg, info);
333   // x_lo, y_hi, z_lo
334   new_msg = new OctoMsg(m->x_min, x-1, y, m->y_max, m->z_min, z-1, false);
335   Octo(x_lo, y_hi, z_lo, new_msg, info);
336   // x_lo, y_hi, z_hi
337   new_msg = new OctoMsg(m->x_min, x-1, y, m->y_max, z, m->z_max, false);
338   Octo(x_lo, y_hi, z_hi, new_msg, info);
339   // x_hi, y_lo, z_lo
340   new_msg = new OctoMsg(x, m->x_max, m->y_min, y-1, m->z_min, z-1, false);
341   Octo(x_hi, y_lo, z_lo, new_msg, info);
342   // x_hi, y_lo, z_hi
343   new_msg = new OctoMsg(x, m->x_max, m->y_min, y-1, z, m->z_max, false);
344   Octo(x_hi, y_lo, z_hi, new_msg, info);
345   // x_hi, y_hi, z_lo
346   new_msg = new OctoMsg(x, m->x_max, y, m->y_max, m->z_min, z-1, false);
347   Octo(x_hi, y_hi, z_lo, new_msg, info);
348   // x_hi, y_hi, z_hi (x, y, z) 
349   new_msg = new OctoMsg(x, m->x_max, y, m->y_max, z, m->z_max, true);
350   if (x_hi == x && y_hi == y && z_hi == z) {
351     // just call local function instead of passing message
352     SplitXYZ(x_hi, y_hi, z_hi, new_msg, info);
353     delete new_msg;
354   }
355   else { Octo(x_hi, y_hi, z_hi, new_msg, info); }
356 }
357
358 void Octo
359 (
360   int         x,     // x pos of node
361   int         y,     // y pos of node
362   int         z,     // z pos of node
363   OctoMsg*    m,     // message with limit data
364   char* info
365 )
366 {
367   OctoData* d = (OctoData*)BgGetNodeData();
368   BgGetMyXYZ(&m->sender_x, &m->sender_y, &m->sender_z);
369
370   // save the message if desired
371   if (BnvAccess(num_messages) == -1) { BnvAccess(num_messages)++; }
372   if (BnvAccess(num_messages) < MAX_MESSAGES) {
373     int i = BnvAccess(num_messages);
374     d->dest_x[i] = x;
375     d->dest_y[i] = y;
376     d->dest_z[i] = z;
377     d->messages[i] = *m;
378     BnvAccess(num_messages)++;
379   }
380   else { 
381     CmiPrintf("ERR: No room to write message on node %d %d %d\n",
382               m->sender_x, m->sender_y, m->sender_z);
383     BgShutdown();
384     return;
385   }
386 }
387
388 bool HandleSpecial
389 (
390   int         x,     // x pos of node
391   int         y,     // y pos of node
392   int         z,     // z pos of node
393   OctoMsg*    m,     // message with limit data
394   char* info
395 )
396 {
397   int del_x = m->x_max - m->x_min;
398   int del_y = m->y_max - m->y_min;
399   int del_z = m->z_max - m->z_min;
400
401   if (del_x >= 2 && del_y >= 2 && del_z >= 2) {
402     return false;
403   }
404
405   if ((del_x == 1 && del_y == 0 && del_z == 0) ||
406       (del_x == 0 && del_y == 1 && del_z == 0) ||
407       (del_x == 0 && del_y == 0 && del_z == 1))
408   {
409     Handle112(x, y, z, m, info);
410   }
411   else if ((del_x >  1 && del_y == 0 && del_z == 0) ||
412            (del_x == 0 && del_y  > 1 && del_z == 0) ||
413            (del_x == 0 && del_y == 0 && del_z  > 1))
414   {
415     Handle11X(x, y, z, m, info);
416   }
417   else if ((del_x == 1 && del_y == 1 && del_z == 0) ||
418            (del_x == 1 && del_y == 0 && del_z == 1) ||
419            (del_x == 0 && del_y == 1 && del_z == 1))
420   {
421     Handle122(x, y, z, m, info);
422   }
423   else if ((del_x == 0 && del_y == 1 && del_z  > 1) ||
424            (del_x == 0 && del_y  > 1 && del_z == 1) ||
425            (del_x == 1 && del_y == 0 && del_z  > 1) ||
426            (del_x == 1 && del_y  > 1 && del_z == 0) ||
427            (del_x  > 1 && del_y == 0 && del_z == 1) ||
428            (del_x  > 1 && del_y == 1 && del_z == 0)) 
429   {
430     Handle12X(x, y, z, m, info);
431   }
432   else if ((del_x == 0 && del_y  > 1 && del_z  > 1) ||
433            (del_x  > 1 && del_y == 0 && del_z  > 1) ||
434            (del_x  > 1 && del_y  > 1 && del_z == 0))
435   {
436     Handle1XX(x, y, z, m, info);
437   }
438   else if (del_x == 1 && del_y == 1 && del_z == 1) {
439     Handle222(x, y, z, m, info);
440   }
441   else if ((del_x == 1 && del_y == 1 && del_z  > 1) ||
442            (del_x == 1 && del_y  > 1 && del_z == 1) ||
443            (del_x  > 1 && del_y == 1 && del_z == 1)) 
444   {
445     Handle22X(x, y, z, m, info);
446   }
447   else if ((del_x == 1 && del_y  > 1 && del_z  > 1) ||
448            (del_x  > 1 && del_y == 1 && del_z  > 1) ||
449            (del_x  > 1 && del_y  > 1 && del_z == 1)) 
450   {
451     Handle2XX(x, y, z, m, info);
452   }
453   else {
454     CmiPrintf("ERR: COULDN'T HANDLE %d x %d x %d\n", del_x+1, del_y+1, del_z+1);
455     BgShutdown();
456     return false;
457   }
458   
459   return true;
460 }
461
462 void Handle112(int x, int y, int z, OctoMsg* m, char* info)
463 {
464   // 2x1x1 -> only 2nd x hasn't been touched
465   // 1x2x1 -> only 2nd y hasn't been touched
466   // 1x1x2 -> only 2nd z hasn't been touched
467
468   int del_x = m->x_max - m->x_min;
469   int del_y = m->y_max - m->y_min;
470   int del_z = m->z_max - m->z_min;
471
472   OctoMsg* new_msg = 
473     new OctoMsg(x+del_x, x+del_x, y+del_y, y+del_y, z+del_z, z+del_z, false);
474   Octo(x+del_x, y+del_y, z+del_z, new_msg, info);
475 }
476
477 void Handle11X(int x, int y, int z, OctoMsg* m, char* info)
478 {
479   int x_mod = ((m->x_max - m->x_min) > 1) ? 1 : 0;
480   int y_mod = ((m->y_max - m->y_min) > 1) ? 1 : 0;
481   int z_mod = ((m->z_max - m->z_min) > 1) ? 1 : 0; 
482     
483   // calculate new midpoints
484   int x_lo = (m->x_min + x - x_mod)/2;  int x_hi = (m->x_max + x)/2;
485   int y_lo = (m->y_min + y - y_mod)/2;  int y_hi = (m->y_max + y)/2;
486   int z_lo = (m->z_min + z - z_mod)/2;  int z_hi = (m->z_max + z)/2;
487
488   // hit high node
489   OctoMsg* new_msg = new OctoMsg(x, m->x_max, y, m->y_max, z, m->z_max, true);
490   if (x == x_hi && y == y_hi && z == z_hi) {
491     SplitXYZ(x_hi, y_hi, z_hi, new_msg, info);
492     delete new_msg;
493   }
494   else { Octo(x_hi, y_hi, z_hi, new_msg, info); }
495
496   // hit low node if it hasn't been hit yet
497   int new_x_width = (x - x_mod - m->x_min + 1);
498   int new_y_width = (y - y_mod - m->y_min + 1);
499   int new_z_width = (z - z_mod - m->z_min + 1);
500   
501   new_msg = new OctoMsg(m->x_min, x-x_mod, m->y_min, y-y_mod, 
502                         m->z_min, z-z_mod, m->v);
503
504   // error handle all different cases
505   if (new_x_width * new_y_width * new_z_width == 1) {
506     if (!m->v) { Octo(x_lo, y_lo, z_lo, new_msg, info); }
507     else { delete new_msg; }
508   }
509   else if (x == x_lo && y == y_lo && z == z_lo) {
510     SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
511     delete new_msg;
512   }
513   else if (new_x_width * new_y_width * new_z_width != 0) { 
514     if (x_lo == m->x_min && y_lo == m->y_min && z_lo == m->z_min && m->v) {
515       SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
516       delete new_msg;
517     }
518     else { Octo(x_lo, y_lo, z_lo, new_msg, info); }
519   }
520 }
521
522 void Handle122(int x, int y, int z, OctoMsg* m, char* info)
523 {
524   int del_x = m->x_max - m->x_min;
525   int del_y = m->y_max - m->y_min;
526   int del_z = m->z_max - m->z_min;
527
528   OctoMsg* new_msg = NULL;
529   
530   // 2x2x1 -> split along x axiz and handle it
531   // 2x1x2 -> split along x axis and handle it
532   if (del_z == 0 || del_y == 0)
533   {
534     new_msg = new OctoMsg(x, x, m->y_min, m->y_max, m->z_min, m->z_max, true);
535     SplitXYZ(x, y, z, new_msg, info); 
536     delete new_msg;
537
538     new_msg = 
539       new OctoMsg(x+1, x+1, m->y_min, m->y_max, m->z_min, m->z_max, false);
540     Octo(x+1, y, z, new_msg, info);
541   }
542   // 1x2x2 -> split along y axis and handle it
543   else if (del_x == 0) {
544     new_msg = new OctoMsg(x, x, y, y, m->z_min, m->z_max, true);
545     SplitXYZ(x, y, z, new_msg, info);
546     delete new_msg;
547
548     new_msg = new OctoMsg(x, x, y+1, y+1, m->z_min, m->z_max, false);
549     Octo(x, y+1, z, new_msg, info);
550   }
551 }
552
553 void Handle12X(int x, int y, int z, OctoMsg* m, char* info)
554 {
555   int x_mod = ((m->x_max - m->x_min) > 1) ? 1 : 0;
556   int y_mod = ((m->y_max - m->y_min) > 1) ? 1 : 0;
557   int z_mod = ((m->z_max - m->z_min) > 1) ? 1 : 0; 
558     
559   // calculate new midpoints
560   int x_lo = (m->x_min + x - x_mod)/2;  int x_hi = (m->x_max + x)/2;
561   int y_lo = (m->y_min + y - y_mod)/2;  int y_hi = (m->y_max + y)/2;
562   int z_lo = (m->z_min + z - z_mod)/2;  int z_hi = (m->z_max + z)/2;
563
564   // first split high side
565   OctoMsg* new_msg = new OctoMsg(x, m->x_max, y, m->y_max, z, m->z_max, true);
566   if (x == x_hi && y == y_hi && z == z_hi) {
567     SplitXYZ(x_hi, y_hi, z_hi, new_msg, info);
568     delete new_msg;
569   }
570   else { Octo(x_hi, y_hi, z_hi, new_msg, info); }
571
572   int del_x = m->x_max - m->x_min;
573   int del_y = m->y_max - m->y_min;
574   int del_z = m->z_max - m->z_min;
575
576   // hit low node if it hasn't been hit yet
577   int new_x_width = del_x > 1 ? (x - x_mod - m->x_min + 1) : del_x + 1;
578   int new_y_width = del_y > 1 ? (y - y_mod - m->y_min + 1) : del_y + 1;
579   int new_z_width = del_z > 1 ? (z - z_mod - m->z_min + 1) : del_z + 1;
580   
581   // adjust mods
582   x_mod = ((m->x_max - m->x_min) == 1) ? -1 : x_mod;
583   y_mod = ((m->y_max - m->y_min) == 1) ? -1 : y_mod;
584   z_mod = ((m->z_max - m->z_min) == 1) ? -1 : z_mod; 
585   new_msg = new OctoMsg(m->x_min, x-x_mod, m->y_min, y-y_mod, 
586                         m->z_min, z-z_mod, m->v);
587
588   // error handle all different cases
589   if (new_x_width * new_y_width * new_z_width == 2) {
590     if (!m->v) { Octo(x_lo, y_lo, z_lo, new_msg, info); }
591     else { 
592       SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
593       delete new_msg; 
594     }
595   }
596   else if (x == x_lo && y == y_lo && z == z_lo) {
597     SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
598     delete new_msg;
599   }
600   else if (new_x_width * new_y_width * new_z_width != 0) { 
601     if (x_lo == m->x_min && y_lo == m->y_min && z_lo == m->z_min && m->v) {
602       SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
603       delete new_msg;
604     }
605     else { Octo(x_lo, y_lo, z_lo, new_msg, info); }
606   }
607 }
608
609 void Handle1XX(int x, int y, int z, OctoMsg* m, char* info)
610 {
611   int del_x = m->x_max - m->x_min;
612   int del_y = m->y_max - m->y_min;
613   int del_z = m->z_max - m->z_min;
614
615   int x_mod = ((m->x_max - m->x_min) > 1) ? 1 : 0;
616   int y_mod = ((m->y_max - m->y_min) > 1) ? 1 : 0;
617   int z_mod = ((m->z_max - m->z_min) > 1) ? 1 : 0; 
618
619   // calculate new midpoints
620   int x_lo = (m->x_min + x - x_mod)/2;  int x_hi = (m->x_max + x)/2;
621   int y_lo = (m->y_min + y - y_mod)/2;  int y_hi = (m->y_max + y)/2;
622   int z_lo = (m->z_min + z - z_mod)/2;  int z_hi = (m->z_max + z)/2;
623
624   OctoMsg* new_msg = 
625     new OctoMsg(x, m->x_max, y, m->y_max, z, m->z_max, true);
626   if (x == x_hi && y == y_hi && z == z_hi) {
627     SplitXYZ(x_hi, y_hi, z_hi, new_msg, info);
628     delete new_msg;
629   }
630   else { Octo(x_hi, y_hi, z_hi, new_msg, info); }
631     
632   // hit low node if it hasn't been hit yet
633   int new_x_width = (x-x_mod - m->x_min + 1);
634   int new_y_width = (y-y_mod - m->y_min + 1);
635   int new_z_width = (z-z_mod - m->z_min + 1);
636   
637   new_msg = new OctoMsg(m->x_min, x-x_mod, m->y_min, y-y_mod, 
638                         m->z_min, z-z_mod, m->v);
639
640   // error handle all different cases
641   if (new_x_width * new_y_width * new_z_width == 1) {
642     if (!m->v) { Octo(x_lo, y_lo, z_lo, new_msg, info); }
643     else { delete new_msg; }
644   }
645   else if (x == x_lo && y == y_lo && z == z_lo) {
646     SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
647     delete new_msg;
648   }
649   else { 
650     if (x_lo == m->x_min && y_lo == m->y_min && z_lo == m->z_min && m->v) {
651       SplitXYZ(x_lo, y_lo, z_lo, new_msg, info);
652       delete new_msg;
653     }
654     else { Octo(x_lo, y_lo, z_lo, new_msg, info); }
655   }
656
657   // calculate new mods
658   x_mod = (x - m->x_min - 1);  x_mod = x_mod > 0 ? x_mod : 0;
659   y_mod = (y - m->y_min - 1);  y_mod = y_mod > 0 ? y_mod : 0;
660   z_mod = (z - m->z_min - 1);  z_mod = z_mod > 0 ? z_mod : 0;
661
662   // 1xXxX
663   if (del_x == 0) {
664     new_msg = 
665       new OctoMsg(x, x, y, m->y_max, m->z_min, m->z_min + z_mod, false);
666     Octo(x, y_hi, z_lo, new_msg, info);
667     
668     new_msg = 
669       new OctoMsg(x, x, m->y_min, m->y_min + y_mod, z, m->z_max, false);
670     Octo(x, y_lo, z_hi, new_msg, info);
671   }
672   // Xx1xX
673   else if (del_y == 0) {
674     new_msg = 
675       new OctoMsg(x, m->x_max, y, y, m->z_min, m->z_min + z_mod, false);
676     Octo(x_hi, y, z_lo, new_msg, info);
677     
678     new_msg = 
679       new OctoMsg(m->x_min, m->x_min + x_mod, y, y, z, m->z_max, false);
680     Octo(x_lo, y, z_hi, new_msg, info);
681   }
682   // XxXx1
683   else { // (del_z == 0)
684     new_msg = 
685       new OctoMsg(x, m->x_max, m->y_min, m->y_min + y_mod, z, z, false);
686     Octo(x_hi, y_lo, z, new_msg, info);
687     
688     new_msg = 
689       new OctoMsg(m->x_min, m->x_min + x_mod, y, m->y_max, z, z, false);
690     Octo(x_lo, y_hi, z, new_msg, info);
691   }
692 }
693
694 void Handle222(int x, int y, int z, OctoMsg* m, char* info)
695 {
696   int del_x = m->x_max - m->x_min;
697   int del_y = m->y_max - m->y_min;
698   int del_z = m->z_max - m->z_min;
699
700   // 2x2x2 -> split along z axis and handle it
701   OctoMsg* new_msg = 
702     new OctoMsg(m->x_min, m->x_max, m->y_min, m->y_max, z, z, true);
703   SplitXYZ(x, y, z, new_msg, info);
704   delete new_msg;
705
706   new_msg = 
707     new OctoMsg(m->x_min, m->x_max, m->y_min, m->y_max, z+1, z+1, m->v);
708   Octo(x, y, z+1, new_msg, info);
709 }
710
711 void Handle22X(int x, int y, int z, OctoMsg* m, char* info)
712 {
713   int del_x = m->x_max - m->x_min;
714   int del_y = m->y_max - m->y_min;
715   int del_z = m->z_max - m->z_min;
716
717   // calculate new midpoints
718   int x_lo = (m->x_min + x - 1)/2;  int x_hi = (m->x_max + x)/2;
719   int y_lo = (m->y_min + y - 1)/2;  int y_hi = (m->y_max + y)/2;
720   int z_lo = (m->z_min + z - 1)/2;  int z_hi = (m->z_max + z)/2;
721
722   OctoMsg* new_msg = NULL;
723
724   // 2x2xX
725   if (del_z != 1) {
726     new_msg = 
727       new OctoMsg(m->x_min, m->x_max, m->y_min, m->y_max, z, m->z_max, true);
728     if (z == z_hi) {
729       SplitXYZ(x, y, z_hi, new_msg, info);
730       delete new_msg;
731     }
732     else { Octo(x, y, z_hi, new_msg, info); }
733
734     new_msg = 
735       new OctoMsg(m->x_min, m->x_max, m->y_min, m->y_max, m->z_min, z-1, m->v);
736     if (z_lo == m->z_min && m->v) {
737       SplitXYZ(x, y, z_lo, new_msg, info);
738       delete new_msg;
739     }
740     else { Octo(x, y, z_lo, new_msg, info); }
741   }
742   // 2xXx2
743   else if (del_y != 1) {
744     new_msg = 
745       new OctoMsg(m->x_min, m->x_max, y, m->y_max, m->z_min, m->z_max, true);
746     if (y == y_hi) {
747       SplitXYZ(x, y_hi, z, new_msg, info); 
748       delete new_msg;
749     }
750     else { Octo(x, y_hi, z, new_msg, info); }
751
752     new_msg = 
753       new OctoMsg(m->x_min, m->x_max, m->y_min, y-1, m->z_min, m->z_max, m->v);
754     if (y_lo == m->y_min && m->v) {
755       SplitXYZ(x, y_lo, z, new_msg, info);
756       delete new_msg;
757     }
758     else { Octo(x, y_lo, z, new_msg, info); }
759   }
760   // Xx2x2
761   else { // (del_x != 1)
762     new_msg = 
763       new OctoMsg(x, m->x_max, m->y_min, m->y_max, m->z_min, m->z_max, true);
764     if (x == x_hi) {
765       SplitXYZ(x_hi, y, z, new_msg, info); 
766       delete new_msg;
767     }
768     else { Octo(x_hi, y, z, new_msg, info); }
769
770     new_msg = 
771       new OctoMsg(m->x_min, x-1, m->y_min, m->y_max, m->z_min, m->z_max, m->v);
772     if (x_lo == m->x_min && m->v) {
773       SplitXYZ(x_lo, y, z, new_msg, info);
774       delete new_msg;
775     }
776     else { Octo(x_lo, y, z, new_msg, info); }
777   }
778 }
779
780 void Handle2XX(int x, int y, int z, OctoMsg* m, char* info)
781 {
782   int del_x = m->x_max - m->x_min;
783   int del_y = m->y_max - m->y_min;
784   int del_z = m->z_max - m->z_min;
785
786   // calculate new midpoints
787   int x_lo = (m->x_min + x - 1)/2;  int x_hi = (m->x_max + x)/2;
788   int y_lo = (m->y_min + y - 1)/2;  int y_hi = (m->y_max + y)/2;
789   int z_lo = (m->z_min + z - 1)/2;  int z_hi = (m->z_max + z)/2;
790
791   OctoMsg* new_msg = NULL;
792
793   // get upper corner
794   new_msg = new OctoMsg(x, m->x_max, y, m->y_max, z, m->z_max, true);
795   if (x == x_hi && y == y_hi && z == z_hi) {
796     SplitXYZ(x_hi, y_hi, z_hi, new_msg, info);
797     delete new_msg;
798   }
799   else { Octo(x_hi, y_hi, z_hi, new_msg, info); }
800
801   // 2xXxX 
802   if (del_x == 1) {
803     // lower corner
804     new_msg = new OctoMsg(x, x+1, m->y_min, y-1, m->z_min, z-1, m->v);
805     if (x == m->x_min && y_lo == m->y_min && z_lo == m->z_min && m->v) {
806       SplitXYZ(x, y_lo, z_lo, new_msg, info); 
807       delete new_msg;
808     }
809     else { Octo(x, y_lo, z_lo, new_msg, info); }
810
811     // y_hi, z_lo
812     new_msg = new OctoMsg(x, x+1, y, m->y_max, m->z_min, z-1, false);
813     Octo(x, y_hi, z_lo, new_msg, info);
814
815     // y_lo, z_hi
816     new_msg = new OctoMsg(x, x+1, m->y_min, y-1, z, m->z_max, false);
817     Octo(x, y_lo, z_hi, new_msg, info);
818   }
819   // Xx2xX
820   else if (del_y == 1) {
821     // lower corner
822     new_msg = new OctoMsg(m->x_min, x-1, y, y+1, m->z_min, z-1, m->v);
823     if (x_lo == m->x_min && y == m->y_min && z_lo == m->z_min && m->v) {
824       SplitXYZ(x_lo, y, z_lo, new_msg, info);
825       delete new_msg;
826     }
827     else { Octo(x_lo, y, z_lo, new_msg, info); }
828
829     // x_hi, z_lo
830     new_msg = new OctoMsg(x, m->x_max, y, y+1, m->z_min, z-1, false);
831     Octo(x_hi, y, z_lo, new_msg, info);
832
833     // x_lo, z_hi
834     new_msg = new OctoMsg(m->x_min, x-1, y, y+1, z, m->z_max, false);
835     Octo(x_lo, y, z_hi, new_msg, info);
836   }
837   // XxXx2
838   else if (del_z == 1) {
839     // lower corner
840     new_msg = new OctoMsg(m->x_min, x-1, m->y_min, y-1, z, z+1, m->v);
841     if (x_lo == m->x_min && y_lo == m->y_min && z == m->z_min && m->v) {
842       SplitXYZ(x_lo, y_lo, z, new_msg, info);
843       delete new_msg;
844     }
845     else { Octo(x_lo, y_lo, z, new_msg, info); }
846
847     // x_hi, y_lo
848     new_msg = new OctoMsg(x, m->x_max, m->y_min, y-1, z, z+1, false);
849     Octo(x_hi, y_lo, z, new_msg, info); 
850
851     // x_lo, y_hi
852     new_msg = new OctoMsg(m->x_min, x-1, y, m->y_max, z, z+1, false);
853     Octo(x_lo, y_hi, z, new_msg, info);
854   }
855 }
856