Charm++: Charm Source Code Documentation

00001 
00002 #include "pose.h"
00003 
00004 //#define EH_SANITIZE 1
00005 
00007 void HeapNode::insert(Event *e)
00008 {
00009   if(pose_config.deterministic)
00010     {
00011       insertDeterministic(e);
00012     }
00013   else
00014     {
00015 #ifdef EH_SANITIZE
00016       sanitize();
00017 #endif
00018       CmiAssert(this != NULL);
00019       CmiAssert(e->timestamp > this->e->timestamp || (e->timestamp == this->e->timestamp && e->evID >= this->e->evID));
00020       HeapNode *eh;
00021       if (left == NULL) {  // make it the left subheap
00022     eh = new HeapNode(e, 1, NULL, NULL);
00023     left = eh;
00024     subheapsize += 1;
00025       }
00026       else if (right == NULL) {  // make it the right subheap
00027     eh = new HeapNode(e, 1, NULL, NULL);
00028     right = eh;
00029     subheapsize += 1;
00030       }
00031       else if (e->timestamp < left->e->timestamp || (e->timestamp == left->e->timestamp && e->evID <= left->e->evID)) { // make root of left subtree
00032     eh = new HeapNode(e, left->subheapsize+1, left, NULL);
00033     left = eh;
00034     subheapsize += 1;
00035       }
00036       else if (e->timestamp < right->e->timestamp || (e->timestamp == right->e->timestamp && e->evID <= right->e->evID)) { // make root of right subtree
00037     eh = new HeapNode(e, right->subheapsize+1, right, NULL);
00038     right = eh;
00039     subheapsize += 1;
00040       }
00041       else if (left->subheapsize < right->subheapsize) { // insert in left subtree
00042     subheapsize += 1;
00043     left->insert(e);
00044       }
00045       else { // insert in right subtree
00046     subheapsize += 1;
00047     right->insert(e);
00048       }
00049 #ifdef EH_SANITIZE
00050       sanitize();
00051 #endif
00052     }
00053 }
00054 
00056 void HeapNode::insertDeterministic(Event *e)
00057 {
00058 #ifdef EH_SANITIZE
00059   sanitize();
00060 #endif
00061   CmiAssert(this != NULL);
00062   CmiAssert(e->timestamp > this->e->timestamp || (e->timestamp == this->e->timestamp && e->evID >= this->e->evID));
00063   HeapNode *eh;
00064   if (left == NULL) {  // make it the left subheap
00065     eh = new HeapNode(e, 1, NULL, NULL);
00066     left = eh;
00067     subheapsize += 1;
00068   }
00069   else if (right == NULL) {  // make it the right subheap
00070     eh = new HeapNode(e, 1, NULL, NULL);
00071     right = eh;
00072     subheapsize += 1;
00073   }
00074   else if ((e->timestamp < left->e->timestamp) ||
00075        ((e->timestamp == left->e->timestamp) &&
00076         (e->evID <= left->e->evID))) { // make root of left subtree
00077     eh = new HeapNode(e, left->subheapsize+1, left, NULL);
00078     left = eh;
00079     subheapsize += 1;
00080   }
00081   else if ((e->timestamp < right->e->timestamp) ||
00082        ((e->timestamp == right->e->timestamp) &&
00083         (e->evID <= right->e->evID))) { // make root of right subtree
00084     eh = new HeapNode(e, right->subheapsize+1, right, NULL);
00085     right = eh;
00086     subheapsize += 1;
00087   }
00088   else if (left->subheapsize < right->subheapsize) { // insert in left subtree
00089     subheapsize += 1;
00090     left->insertDeterministic(e);
00091   }
00092   else { // insert in right subtree
00093     subheapsize += 1;
00094     right->insertDeterministic(e);
00095   }
00096 #ifdef EH_SANITIZE
00097   sanitize();
00098 #endif
00099 }
00100 
00102 HeapNode *HeapNode::conjoin(HeapNode *h)
00103 {
00104 #ifdef EH_SANITIZE
00105   sanitize();
00106   if (h) h->sanitize();
00107 #endif
00108   if (!h) return this;
00109   else if ((pose_config.deterministic && e->timestamp < h->e->timestamp) ||
00110            (e->timestamp == h->e->timestamp && e->evID <= h->e->evID) ||
00111            e->timestamp < h->e->timestamp ||
00112            (e->timestamp == h->e->timestamp && e->evID <= h->e->evID))
00113     { 
00114       // conjoin this's kids into this's left and make this's right h
00115       if (!left) left = right;
00116       else left = left->conjoin(right);
00117       right = h;
00118       subheapsize += h->subheapsize;
00119 #ifdef EH_SANITIZE
00120       sanitize();
00121 #endif
00122       return this;
00123     }
00124   else { // make h the root
00125     // conjoin h's kids into h's right and make h's left this
00126     if (h->left) h->right = h->left->conjoin(h->right);
00127     h->left = this;
00128     h->subheapsize += subheapsize;
00129 #ifdef EH_SANITIZE
00130     h->sanitize();
00131 #endif
00132     return h;
00133   }
00134 }
00135 
00137 int HeapNode::remove(eventID evID, POSE_TimeType timestamp)
00138 {
00139 #ifdef EH_SANITIZE
00140     sanitize();
00141 #endif
00142   CmiAssert(this != NULL);
00143   CmiAssert(!(this->e->evID == evID));
00144   int found = 0; // return status
00145   HeapNode *tmp;
00146   if (left) { // search left subheap first
00147     if (timestamp < left->e->timestamp) found = 0; // subheap elements too high
00148     else if ((timestamp == left->e->timestamp) && (evID == left->e->evID)) {
00149       // found element on top
00150       tmp = left; // save a pointer to it
00151       if (left->left)
00152     left = left->left->conjoin(left->right); // remove it from heap
00153       else left = left->right;
00154       subheapsize--;
00155       tmp->left = tmp->right = NULL; // foil recursive destructor
00156       delete tmp; // delete it
00157       found = 1;
00158     }
00159     else if (timestamp >= left->e->timestamp) { // need to look deeper
00160       found = left->remove(evID, timestamp);
00161       if (found) subheapsize--; // must decrement heap size
00162     }
00163   }
00164   if (found) return 1; // found in left subheap; exit with status 1
00165   else if (right) { // search in right subheap
00166     if (timestamp < right->e->timestamp) found = 0; //subheap elements too high
00167     else if ((timestamp == right->e->timestamp) && (evID == right->e->evID)) {
00168       // found element on top
00169       tmp = right; // save a pointer to it
00170       if (right->left)
00171     right = right->left->conjoin(right->right); // remove it from heap
00172       else right = right->right;
00173       subheapsize--;                 
00174       tmp->left = tmp->right = NULL; // foil recursive destructor
00175       delete tmp; // delete it
00176       found = 1; 
00177     }
00178     else if (timestamp >= right->e->timestamp) { // need to look deeper
00179       found = right->remove(evID, timestamp); // set return status
00180       if (found) subheapsize--; // must decrement heap size
00181     }
00182   }
00183 #ifdef EH_SANITIZE
00184     sanitize();
00185 #endif
00186   return found; // exit with found status
00187 }
00188 
00190 void HeapNode::dump()
00191 {
00192   CkPrintf("[HpNd: sz=%d event=(", subheapsize);
00193   e->evID.dump();
00194   CkPrintf(") ");
00195   if (left) left->dump();
00196   else CkPrintf("[NULL] ");
00197   if (right) right->dump();
00198   else CkPrintf("[NULL]");
00199   CkPrintf(" end HpNd]\n");
00200 }
00201 
00203 char *HeapNode::dumpString() {
00204   char *str=new char[PVT_DEBUG_BUFFER_LINE_LENGTH];
00205 #if USE_LONG_TIMESTAMPS
00206   snprintf(str, PVT_DEBUG_BUFFER_LINE_LENGTH,"[HpNd: sz=%d event=%lld(%u.%d) ", subheapsize, e->timestamp, e->evID.id, e->evID.getPE());
00207 #else
00208   snprintf(str, PVT_DEBUG_BUFFER_LINE_LENGTH, "[HpNd: sz=%d event=%d(%u.%d) ", subheapsize, e->timestamp, e->evID.id, e->evID.getPE());
00209 #endif
00210   if (left) {
00211     char *lstring=left->dumpString();
00212     strncat(str, lstring, 32);
00213     delete [] lstring;
00214   } else {
00215     strncat(str, "[NULL] ",  PVT_DEBUG_BUFFER_LINE_LENGTH);
00216   }
00217   if (right) {
00218     char *rstring=right->dumpString();
00219     strncat(str, rstring, 32);
00220     delete [] rstring;
00221   } else {
00222     strncat(str, "[NULL]", PVT_DEBUG_BUFFER_LINE_LENGTH);
00223   }
00224   strncat(str, "] ", PVT_DEBUG_BUFFER_LINE_LENGTH);
00225   return str;
00226 }
00227 
00229 
00230 void HeapNode::pup(PUP::er &p)
00231 {
00232   CmiAssert(this != NULL);
00233   CmiAssert(!p.isUnpacking());
00234   e->pup(p);
00235   if (left) left->pup(p);
00236   if (right) right->pup(p);
00237 }
00238 
00239 void HeapNode::sanitize()
00240 {
00241   if (e == NULL) CkPrintf("WARNING: uninitialized HeapNode!\n");
00242   CmiAssert(((e==NULL) && (subheapsize==0) && (left==NULL) && (right==NULL)) ||
00243         ((e!=NULL) && (subheapsize==1) && (left==NULL) && (right==NULL)) ||
00244         ((e!=NULL) && (subheapsize>1)));
00245   if (e!=NULL) {
00246     e->sanitize();
00247     if (left) left->sanitize();
00248     if (right) right->sanitize();
00249   }
00250 }
00251 
00253 void EqHeap::InsertEvent(Event *e)
00254 {
00255   HeapNode *eh;
00256 
00257   if(pose_config.deterministic){
00258     InsertDeterministic(e);
00259   }
00260   else
00261     {
00262 #ifdef EH_SANITIZE
00263       sanitize();
00264 #endif
00265       CmiAssert((top == NULL) || (top->subheapsize > 0));
00266       if (top == NULL) // make the top of the heap
00267     top = new HeapNode(e, 1, NULL, NULL);
00268       else if (e->timestamp < top->e->timestamp || (e->timestamp == top->e->timestamp && e->evID < top->e->evID)) { // insert at top of heap
00269     if (top->subheapsize == 1) // only one node in heap
00270       top = new HeapNode(e, 2, top, NULL); // make old top into left subheap
00271     else if (top->left && top->right) { // full(ish) heap
00272       // try to improve the balance by one
00273       if (top->left->subheapsize < top->right->subheapsize) {
00274         eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00275         top->subheapsize -= top->right->subheapsize;
00276         top->right = NULL;
00277         top = eh;
00278       }
00279       else {
00280         eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00281         top->subheapsize -= top->left->subheapsize;
00282         top->left = NULL;
00283         top = eh;
00284       }
00285     }
00286     else if (top->left) { // at least keep the balance about the same
00287       eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00288       top->subheapsize = 1;
00289       top->left = NULL;
00290       top = eh;
00291     }
00292     else if (top->right) { // at least keep the balance about the same
00293       eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00294       top->subheapsize = 1;
00295       top->right = NULL;
00296       top = eh;
00297     }
00298       }
00299       else // insert somewhere below the top node
00300     top->insert(e);
00301       heapSize++;
00302 #ifdef EH_SANITIZE
00303       sanitize();
00304 #endif
00305     }
00306 }
00307 
00309 void EqHeap::InsertDeterministic(Event *e)
00310 {
00311 #ifdef EH_SANITIZE
00312     sanitize();
00313 #endif
00314   HeapNode *eh;
00315 
00316   CmiAssert((top == NULL) || (top->subheapsize > 0));
00317   if (top == NULL) // make the top of the heap
00318     top = new HeapNode(e, 1, NULL, NULL);
00319   else if ((e->timestamp < top->e->timestamp) || 
00320            ((e->timestamp == top->e->timestamp) && 
00321         (e->evID <= top->e->evID))) { // insert at top of heap
00322     if (top->subheapsize == 1) // only one node in heap
00323       top = new HeapNode(e, 2, top, NULL); // make old top into left subheap
00324     else if (top->left && top->right) { // full(ish) heap
00325       // try to improve the balance by one
00326       if (top->left->subheapsize < top->right->subheapsize) {
00327     eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00328     top->subheapsize -= top->right->subheapsize;
00329     top->right = NULL;
00330     top = eh;
00331       }
00332       else {
00333     eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00334     top->subheapsize -= top->left->subheapsize;
00335     top->left = NULL;
00336     top = eh;
00337       }
00338     }
00339     else if (top->left) { // at least keep the balance about the same
00340       eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00341       top->subheapsize = 1;
00342       top->left = NULL;
00343       top = eh;
00344     }
00345     else if (top->right) { // at least keep the balance about the same
00346       eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00347       top->subheapsize = 1;
00348       top->right = NULL;
00349       top = eh;
00350     }
00351   }
00352   else // insert somewhere below the top node
00353     top->insert(e);
00354   heapSize++;
00355 #ifdef EH_SANITIZE
00356     sanitize();
00357 #endif
00358 }
00359 
00361 Event *EqHeap::GetAndRemoveTopEvent()
00362 {
00363 #ifdef EH_SANITIZE
00364     sanitize();
00365 #endif
00366   CmiAssert(top != NULL);
00367   CmiAssert(top->subheapsize > 0);
00368   HeapNode *tmp = top;
00369   Event *result;
00370 
00371   if (top->left) top = top->left->conjoin(top->right);
00372   else top = top->right;
00373   result = tmp->e;
00374   tmp->e = NULL;
00375   tmp->left = tmp->right = NULL;
00376   delete(tmp);
00377   heapSize--;
00378 #ifdef EH_SANITIZE
00379     sanitize();
00380 #endif
00381   return result;
00382 }
00383 
00385 int EqHeap::DeleteEvent(eventID evID, POSE_TimeType timestamp)
00386 {
00387 #ifdef EH_SANITIZE
00388     sanitize();
00389 #endif
00390   int result;
00391   if (!top || (timestamp < top->e->timestamp))  // NOTE: Skipping evID comparison... if control not set in parameter evID then
00392     return 0;                                   //   search will fail... not having the check shouldn't cause too much un-needed work
00393   else if ((top->e->timestamp == timestamp) && (top->e->evID == evID)) {
00394     HeapNode *tmp = top; // top is the match
00395     if (top->left)
00396       top = top->left->conjoin(top->right); // remove node from heap
00397     else top = top->right;
00398     tmp->left = tmp->right = NULL; // foil recursive destructor
00399     delete tmp;
00400     heapSize--;
00401 #ifdef EH_SANITIZE
00402     sanitize();
00403 #endif
00404     return 1;
00405   }
00406   else { // search deeper in heap
00407     result = top->remove(evID, timestamp);
00408     if (result) heapSize--;
00409 #ifdef EH_SANITIZE
00410     sanitize();
00411 #endif
00412     return result;
00413   }
00414 }
00415 
00417 void EqHeap::pup(PUP::er &p) { 
00418   int i=0, hs;
00419   Event *e;
00420 
00421   if (p.isUnpacking()) {  // UNPACK entire heap right here
00422     p(hs);
00423     top = NULL;
00424     while (i < hs) {
00425       e = new Event();
00426       e->pup(p);
00427       InsertEvent(e);
00428       i++;
00429     }
00430   }
00431   else {  // PACK / SIZE
00432     p(heapSize);
00433     if (top) top->pup(p); // HeapNode::pup recursively packs/sizes events
00434   }
00435 }
00436 
00438 void EqHeap::dump()
00439 {
00440   CkPrintf("[EQHEAP: ");
00441   if (top) top->dump();
00442   else CkPrintf("NULL");
00443   CkPrintf(" end EQHEAP]\n");
00444 }
00445 
00447 char *EqHeap::dumpString() {
00448   char *str= new char[8192];
00449   sprintf(str, "[EQHEAP: ");
00450   //if (top) {
00451   //  strcat(str, top->dumpString());
00452   //} else {
00453   //  strcat(str, "NULL");
00454   //}
00455   strcat(str, "<not printed right now>");
00456   strcat(str, " end EQHEAP] ");
00457   return str;
00458 }
00459 
00461 void EqHeap::sanitize()
00462 {
00463   CkAssert(((top==NULL) && (heapSize==0)) ||
00464        ((top!=NULL) && (heapSize>0)));
00465   if (top!=NULL) top->sanitize();
00466 }
libs/ck-libs/pose/eqheap.C
