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 #endif
00107 #ifdef EH_SANITIZE
00108   if (h) h->sanitize();
00109 #endif
00110   if (!this) return h;
00111   else if (!h) return this;
00112   else if (((pose_config.deterministic) && (e->timestamp < h->e->timestamp) ||
00113             ((e->timestamp == h->e->timestamp) && (e->evID <= h->e->evID))) ||
00114            (e->timestamp < h->e->timestamp || (e->timestamp == h->e->timestamp && e->evID <= h->e->evID)))
00115     { 
00116       // conjoin this's kids into this's left and make this's right h
00117       if (!left) left = right;
00118       else left = left->conjoin(right);
00119       right = h;
00120       subheapsize += h->subheapsize;
00121 #ifdef EH_SANITIZE
00122       sanitize();
00123 #endif
00124       return this;
00125     }
00126   else { // make h the root
00127     // conjoin h's kids into h's right and make h's left this
00128     if (h->left) h->right = h->left->conjoin(h->right);
00129     h->left = this;
00130     h->subheapsize += subheapsize;
00131 #ifdef EH_SANITIZE
00132     h->sanitize();
00133 #endif
00134     return h;
00135   }
00136 }
00137 
00139 int HeapNode::remove(eventID evID, POSE_TimeType timestamp)
00140 {
00141 #ifdef EH_SANITIZE
00142     sanitize();
00143 #endif
00144   CmiAssert(this != NULL);
00145   CmiAssert(!(this->e->evID == evID));
00146   int found = 0; // return status
00147   HeapNode *tmp;
00148   if (left) { // search left subheap first
00149     if (timestamp < left->e->timestamp) found = 0; // subheap elements too high
00150     else if ((timestamp == left->e->timestamp) && (evID == left->e->evID)) {
00151       // found element on top
00152       tmp = left; // save a pointer to it
00153       if (left->left)
00154         left = left->left->conjoin(left->right); // remove it from heap
00155       else left = left->right;
00156       subheapsize--;
00157       tmp->left = tmp->right = NULL; // foil recursive destructor
00158       delete tmp; // delete it
00159       found = 1;
00160     }
00161     else if (timestamp >= left->e->timestamp) { // need to look deeper
00162       found = left->remove(evID, timestamp);
00163       if (found) subheapsize--; // must decrement heap size
00164     }
00165   }
00166   if (found) return 1; // found in left subheap; exit with status 1
00167   else if (right) { // search in right subheap
00168     if (timestamp < right->e->timestamp) found = 0; //subheap elements too high
00169     else if ((timestamp == right->e->timestamp) && (evID == right->e->evID)) {
00170       // found element on top
00171       tmp = right; // save a pointer to it
00172       if (right->left)
00173         right = right->left->conjoin(right->right); // remove it from heap
00174       else right = right->right;
00175       subheapsize--;                 
00176       tmp->left = tmp->right = NULL; // foil recursive destructor
00177       delete tmp; // delete it
00178       found = 1; 
00179     }
00180     else if (timestamp >= right->e->timestamp) { // need to look deeper
00181       found = right->remove(evID, timestamp); // set return status
00182       if (found) subheapsize--; // must decrement heap size
00183     }
00184   }
00185 #ifdef EH_SANITIZE
00186     sanitize();
00187 #endif
00188   return found; // exit with found status
00189 }
00190 
00192 void HeapNode::dump()
00193 {
00194   CkPrintf("[HpNd: sz=%d event=(", subheapsize);
00195   e->evID.dump();
00196   CkPrintf(") ");
00197   if (left) left->dump();
00198   else CkPrintf("[NULL] ");
00199   if (right) right->dump();
00200   else CkPrintf("[NULL]");
00201   CkPrintf(" end HpNd]\n");
00202 }
00203 
00205 char *HeapNode::dumpString() {
00206   char str[PVT_DEBUG_BUFFER_LINE_LENGTH];
00207 #if USE_LONG_TIMESTAMPS
00208   sprintf(str, "[HpNd: sz=%d event=%lld(%u.%d) ", subheapsize, e->timestamp, e->evID.id, e->evID.getPE());
00209 #else
00210   sprintf(str, "[HpNd: sz=%d event=%d(%u.%d) ", subheapsize, e->timestamp, e->evID.id, e->evID.getPE());
00211 #endif
00212   if (left) {
00213     strcat(str, left->dumpString());
00214   } else {
00215     strcat(str, "[NULL] ");
00216   }
00217   if (right) {
00218     strcat(str, right->dumpString());
00219   } else {
00220     strcat(str, "[NULL]");
00221   }
00222   strcat(str, "] ");
00223   return str;
00224 }
00225 
00227 
00228 void HeapNode::pup(PUP::er &p)
00229 {
00230   CmiAssert(this != NULL);
00231   CmiAssert(!p.isUnpacking());
00232   e->pup(p);
00233   if (left) left->pup(p);
00234   if (right) right->pup(p);
00235 }
00236 
00237 void HeapNode::sanitize()
00238 {
00239   if (e == NULL) CkPrintf("WARNING: uninitialized HeapNode!\n");
00240   CmiAssert(((e==NULL) && (subheapsize==0) && (left==NULL) && (right==NULL)) ||
00241             ((e!=NULL) && (subheapsize==1) && (left==NULL) && (right==NULL)) ||
00242             ((e!=NULL) && (subheapsize>1)));
00243   if (e!=NULL) {
00244     e->sanitize();
00245     if (left) left->sanitize();
00246     if (right) right->sanitize();
00247   }
00248 }
00249 
00251 void EqHeap::InsertEvent(Event *e)
00252 {
00253   HeapNode *eh;
00254 
00255   if(pose_config.deterministic){
00256     InsertDeterministic(e);
00257   }
00258   else
00259     {
00260 #ifdef EH_SANITIZE
00261       sanitize();
00262 #endif
00263       CmiAssert((top == NULL) || (top->subheapsize > 0));
00264       if (top == NULL) // make the top of the heap
00265         top = new HeapNode(e, 1, NULL, NULL);
00266       else if (e->timestamp < top->e->timestamp || (e->timestamp == top->e->timestamp && e->evID < top->e->evID)) { // insert at top of heap
00267         if (top->subheapsize == 1) // only one node in heap
00268           top = new HeapNode(e, 2, top, NULL); // make old top into left subheap
00269         else if (top->left && top->right) { // full(ish) heap
00270           // try to improve the balance by one
00271           if (top->left->subheapsize < top->right->subheapsize) {
00272             eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00273             top->subheapsize -= top->right->subheapsize;
00274             top->right = NULL;
00275             top = eh;
00276           }
00277           else {
00278             eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00279             top->subheapsize -= top->left->subheapsize;
00280             top->left = NULL;
00281             top = eh;
00282           }
00283         }
00284         else if (top->left) { // at least keep the balance about the same
00285           eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00286           top->subheapsize = 1;
00287           top->left = NULL;
00288           top = eh;
00289         }
00290         else if (top->right) { // at least keep the balance about the same
00291           eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00292           top->subheapsize = 1;
00293           top->right = NULL;
00294           top = eh;
00295         }
00296       }
00297       else // insert somewhere below the top node
00298         top->insert(e);
00299       heapSize++;
00300 #ifdef EH_SANITIZE
00301       sanitize();
00302 #endif
00303     }
00304 }
00305 
00307 void EqHeap::InsertDeterministic(Event *e)
00308 {
00309 #ifdef EH_SANITIZE
00310     sanitize();
00311 #endif
00312   HeapNode *eh;
00313 
00314   CmiAssert((top == NULL) || (top->subheapsize > 0));
00315   if (top == NULL) // make the top of the heap
00316     top = new HeapNode(e, 1, NULL, NULL);
00317   else if ((e->timestamp < top->e->timestamp) || 
00318            ((e->timestamp == top->e->timestamp) && 
00319             (e->evID <= top->e->evID))) { // insert at top of heap
00320     if (top->subheapsize == 1) // only one node in heap
00321       top = new HeapNode(e, 2, top, NULL); // make old top into left subheap
00322     else if (top->left && top->right) { // full(ish) heap
00323       // try to improve the balance by one
00324       if (top->left->subheapsize < top->right->subheapsize) {
00325         eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00326         top->subheapsize -= top->right->subheapsize;
00327         top->right = NULL;
00328         top = eh;
00329       }
00330       else {
00331         eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00332         top->subheapsize -= top->left->subheapsize;
00333         top->left = NULL;
00334         top = eh;
00335       }
00336     }
00337     else if (top->left) { // at least keep the balance about the same
00338       eh = new HeapNode(e, top->subheapsize+1, top->left, top);
00339       top->subheapsize = 1;
00340       top->left = NULL;
00341       top = eh;
00342     }
00343     else if (top->right) { // at least keep the balance about the same
00344       eh = new HeapNode(e, top->subheapsize+1, top, top->right);
00345       top->subheapsize = 1;
00346       top->right = NULL;
00347       top = eh;
00348     }
00349   }
00350   else // insert somewhere below the top node
00351     top->insert(e);
00352   heapSize++;
00353 #ifdef EH_SANITIZE
00354     sanitize();
00355 #endif
00356 }
00357 
00359 Event *EqHeap::GetAndRemoveTopEvent()
00360 {
00361 #ifdef EH_SANITIZE
00362     sanitize();
00363 #endif
00364   CmiAssert(top != NULL);
00365   CmiAssert(top->subheapsize > 0);
00366   HeapNode *tmp = top;
00367   Event *result;
00368 
00369   if (top->left) top = top->left->conjoin(top->right);
00370   else top = top->right;
00371   result = tmp->e;
00372   tmp->e = NULL;
00373   tmp->left = tmp->right = NULL;
00374   delete(tmp);
00375   heapSize--;
00376 #ifdef EH_SANITIZE
00377     sanitize();
00378 #endif
00379   return result;
00380 }
00381 
00383 int EqHeap::DeleteEvent(eventID evID, POSE_TimeType timestamp)
00384 {
00385 #ifdef EH_SANITIZE
00386     sanitize();
00387 #endif
00388   int result;
00389   if (!top || (timestamp < top->e->timestamp))  // NOTE: Skipping evID comparison... if control not set in parameter evID then
00390     return 0;                                   //   search will fail... not having the check shouldn't cause too much un-needed work
00391   else if ((top->e->timestamp == timestamp) && (top->e->evID == evID)) {
00392     HeapNode *tmp = top; // top is the match
00393     if (top->left)
00394       top = top->left->conjoin(top->right); // remove node from heap
00395     else top = top->right;
00396     tmp->left = tmp->right = NULL; // foil recursive destructor
00397     delete tmp;
00398     heapSize--;
00399 #ifdef EH_SANITIZE
00400     sanitize();
00401 #endif
00402     return 1;
00403   }
00404   else { // search deeper in heap
00405     result = top->remove(evID, timestamp);
00406     if (result) heapSize--;
00407 #ifdef EH_SANITIZE
00408     sanitize();
00409 #endif
00410     return result;
00411   }
00412 }
00413 
00415 void EqHeap::pup(PUP::er &p) { 
00416   int i=0, hs;
00417   Event *e;
00418 
00419   if (p.isUnpacking()) {  // UNPACK entire heap right here
00420     p(hs);
00421     top = NULL;
00422     while (i < hs) {
00423       e = new Event();
00424       e->pup(p);
00425       InsertEvent(e);
00426       i++;
00427     }
00428   }
00429   else {  // PACK / SIZE
00430     p(heapSize);
00431     if (top) top->pup(p); // HeapNode::pup recursively packs/sizes events
00432   }
00433 }
00434 
00436 void EqHeap::dump()
00437 {
00438   CkPrintf("[EQHEAP: ");
00439   if (top) top->dump();
00440   else CkPrintf("NULL");
00441   CkPrintf(" end EQHEAP]\n");
00442 }
00443 
00445 char *EqHeap::dumpString() {
00446   char str[8192];
00447   sprintf(str, "[EQHEAP: ");
00448   //if (top) {
00449   //  strcat(str, top->dumpString());
00450   //} else {
00451   //  strcat(str, "NULL");
00452   //}
00453   strcat(str, "<not printed right now>");
00454   strcat(str, " end EQHEAP] ");
00455   return str;
00456 }
00457 
00459 void EqHeap::sanitize()
00460 {
00461   CkAssert(((top==NULL) && (heapSize==0)) ||
00462            ((top!=NULL) && (heapSize>0)));
00463   if (top!=NULL) top->sanitize();
00464 }
libs/ck-libs/pose/eqheap.C
