fix the HACK when dealing with WhenTrigger data structure.
[charm.git] / src / ck-core / sdag.h
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 #ifndef _sdag_H_
9 #define _sdag_H_
10
11 #include "charm++.h"
12
13 class CMsgBuffer {
14   public:
15     int entry;
16     void *msg;
17     void *bgLog1; 
18     void *bgLog2; 
19     int refnum;
20     CMsgBuffer *next;
21
22     CMsgBuffer(int e, void *m, void* l1, int r) : entry(e), msg(m), bgLog1(l1), bgLog2(NULL),refnum(r), next(NULL) {}
23     CMsgBuffer(int e, void *m, int r) : entry(e), msg(m), bgLog1(NULL), bgLog2(NULL),refnum(r), next(NULL) {}
24     CMsgBuffer(): bgLog1(NULL), bgLog2(NULL), next(NULL) {}
25     void pup(PUP::er& p) {
26       p|entry;
27       CkPupMessage(p, &msg);
28       p|refnum;
29       if (p.isUnpacking()) {
30         bgLog1 = bgLog2 = NULL;
31       }
32     }
33 };
34
35 #define MAXARG 8
36 #define MAXANY 8
37 #define MAXREF 8
38
39 class CWhenTrigger {
40   public:
41     int whenID, nArgs;
42     size_t args[MAXARG];
43     int nAnyEntries;
44     int anyEntries[MAXANY];
45     int nEntries;
46     int entries[MAXREF];
47     int refnums[MAXREF];
48
49     CWhenTrigger *next;
50     CWhenTrigger(int id, int na, int ne, int nae) :
51        whenID(id), nArgs(na), nAnyEntries(nae), nEntries(ne), next(NULL) {}
52     CWhenTrigger(): next(NULL) {}
53     void pup(PUP::er& p) {
54       p|whenID;
55       p|nArgs;
56       p(args, MAXARG);
57       p|nAnyEntries;
58       p(anyEntries, MAXANY);
59       p|nEntries;
60       p(entries, MAXREF);
61       p(refnums, MAXREF);
62       // since CCounter is not pup'ed
63       // don't expect Overlap works with load balancer 
64       // as well as checkpointing
65       p(args, MAXARG);
66       //if (p.isUnpacking()) args[0]=0;            // HACK for load balancer
67     }
68 };
69
70 // Quick and dirty List for small numbers of items.
71 // It should ideally be a template, but in order to have portability,
72 // we would make it two lists
73
74 class TListCWhenTrigger
75 {
76   private:
77
78     CWhenTrigger *first, *last;
79     CWhenTrigger *current;
80
81   public:
82
83     TListCWhenTrigger(void) : first(0), last(0) {;}
84
85     void pup(PUP::er& p) {
86       int nEntries=0;
87       int cur=-1;
88       if (!p.isUnpacking()) { 
89         for (CWhenTrigger *tmp = first; tmp; tmp=tmp->next, nEntries++)
90           if (current == tmp) cur = nEntries;
91       }
92       p|nEntries;
93       p|cur;
94       if (p.isUnpacking()) { 
95         first = last = current = NULL;
96         if (nEntries) {
97           CWhenTrigger** unpackArray = new CWhenTrigger*[nEntries]; 
98           for (int i=0; i<nEntries; i++)  {
99             unpackArray[i] = new CWhenTrigger;
100             if (i!=0) unpackArray[i-1]->next=unpackArray[i];
101           }
102           first = unpackArray[0];
103           last = unpackArray[nEntries-1];
104           last->next = NULL;
105           current = cur==-1?NULL:unpackArray[cur];
106           delete [] unpackArray;
107         }
108       }
109       for (CWhenTrigger *tmp = first; tmp; tmp=tmp->next) tmp->pup(p);
110     }
111
112     int empty(void) { return ! first; }
113     
114     CWhenTrigger *begin(void) {
115       return (current = first);
116     }
117
118     int end(void) {
119       return (current == 0);
120     }
121
122     CWhenTrigger *next (void) {
123       return (current = current->next);
124     }
125
126     CWhenTrigger *front(void)
127     {
128       return first;
129     }
130
131     void remove(CWhenTrigger *data)
132     {
133       // case 1: empty list
134       if (first == 0)
135         return;
136       // case 2: first element to be removed
137       if(first == data) {
138         first = first->next;
139         if(first==0) last=0;
140         return;
141       }
142       // case 3: middle or last element to be removed
143       CWhenTrigger *nn;
144       CWhenTrigger *prev = first;
145       for(nn=first->next; nn; nn = nn->next) {
146         if (nn == data) {
147           prev->next = nn->next;
148           if(nn==last)
149             last=prev;
150           return;
151         }
152         prev = nn;
153       }
154     }
155
156     void append(CWhenTrigger *data)
157     {
158       data->next = 0;
159       if(first == 0) {
160         last = first = data;
161       } else {
162         last->next = data;
163         last = last->next;
164       }
165     }
166 };
167
168 class TListCMsgBuffer
169 {
170   private:
171
172     CMsgBuffer *first, *last;
173     CMsgBuffer *current;
174
175   public:
176
177     TListCMsgBuffer(void) : first(0), last(0) {}
178
179     void pup(PUP::er& p) {
180       int nEntries=0;
181       int cur=0;
182       if (!p.isUnpacking()) { 
183         for (CMsgBuffer *tmp = first; tmp; tmp=tmp->next, nEntries++) {
184           if (current == tmp) cur = nEntries;
185         }
186       }
187       p|nEntries;
188       p|cur;
189       if (p.isUnpacking()) { 
190         first = last = current = NULL;
191         if (nEntries) {
192           CMsgBuffer** unpackArray = new CMsgBuffer*[nEntries]; 
193           for (int i=0; i<nEntries; i++)  {
194             unpackArray[i] = new CMsgBuffer;
195             if (i!=0) unpackArray[i-1]->next=unpackArray[i];
196           }
197           first = unpackArray[0];
198           last = unpackArray[nEntries-1];
199           current = unpackArray[cur];
200           delete [] unpackArray;
201         }
202       }
203       for (CMsgBuffer *tmp = first; tmp; tmp=tmp->next) tmp->pup(p);
204     }
205
206     int empty(void) { return ! first; }
207     
208     CMsgBuffer *begin(void) {
209       return (current = first);
210     }
211
212     int end(void) {
213       return (current == 0);
214     }
215
216     CMsgBuffer *next (void) {
217       return (current = current->next);
218     }
219
220     CMsgBuffer *front(void)
221     {
222       return first;
223     }
224
225     void remove(CMsgBuffer *data)
226     {
227       // case 1: empty list
228       if (first == 0)
229         return;
230       // case 2: first element to be removed
231       if(first == data) {
232         first = first->next;
233         if(first==0) last=0;
234         return;
235       }
236       // case 3: middle or last element to be removed
237       CMsgBuffer *nn;
238       CMsgBuffer *prev = first;
239       for(nn=first->next; nn; nn = nn->next) {
240         if (nn == data) {
241           prev->next = nn->next;
242           if(nn==last)
243             last=prev;
244           return;
245         }
246         prev = nn;
247       }
248     }
249
250     void append(CMsgBuffer *data)
251     {
252       data->next = 0;
253       if(first == 0) {
254         last = first = data;
255       } else {
256         last->next = data;
257         last = last->next;
258       }
259     }
260 };
261
262
263 /**
264  This class hides all the details of dependencies between
265  when blocks and entries. It also contains the entry buffers
266  and when triggers.
267 */
268
269 class CDep {
270    int numEntries, numWhens;
271    TListCWhenTrigger **whens;
272    TListCMsgBuffer **buffers;
273    int *numWhenDepends;
274    int *numEntryDepends;
275    TListCMsgBuffer ***whenDepends;
276    TListCWhenTrigger ***entryDepends;
277
278  public:
279    void pup(PUP::er& p) {
280      /* 
281         no need for initMem() because __sdag_pup() will take care of 
282         allocating of CDep and call addDepends(), so we don't pup whenDepends
283         and entryDepends here.
284      */ 
285      int i;
286
287      for (i=0; i<numWhens; i++)    whens[i]->pup(p);
288      for (i=0; i<numEntries; i++)  buffers[i]->pup(p);
289
290      p(numWhenDepends, numWhens);
291      p(numEntryDepends, numEntries);
292
293 /*
294      // don't actually pack this info because it gets created once 
295      // the addDepends() in the initialization scheme are called for this class
296      for (i=0; i<numWhens; i++)
297        for (j=0; j<numWhenDepends[i]; j++) {
298          int which;
299          if (p.isPacking())  which = whenDepends[i][j] - buffers[0];
300          p|which;
301          if (p.isUnpacking()) whenDepends[i][j] = buffers[which];
302        }
303
304      for (i=0; i<numEntries; i++)
305        for (j=0; j<numEntryDepends[i]; j++) {
306          int which;
307          if (p.isPacking())  which = entryDepends[i][j] - whens[0];
308          p|which;
309          if (p.isUnpacking()) entryDepends[i][j] = whens[which];
310      }
311 */
312    }
313
314    CDep(int ne, int nw) : numEntries(ne), numWhens(nw) { initMem(); }
315
316    ~CDep() {
317      int i;
318      delete [] numWhenDepends;
319      delete [] numEntryDepends;
320      for(i=0;i<numWhens;i++) {
321        delete whens[i];
322        delete [] whenDepends[i];
323      }
324      for(i=0;i<numEntries;i++) {
325        delete buffers[i];
326        delete [] entryDepends[i];
327      }
328      delete [] whens;
329      delete [] buffers;
330      delete [] whenDepends;
331      delete [] entryDepends;
332    }
333
334  private:
335    void initMem() {
336      // initialize the internal data structures here
337      whens = new TListCWhenTrigger *[numWhens];
338      buffers = new TListCMsgBuffer *[numEntries];
339      numWhenDepends = new int[numWhens];
340      numEntryDepends = new int[numEntries];
341      whenDepends = new TListCMsgBuffer **[numWhens];
342      entryDepends = new TListCWhenTrigger **[numEntries];
343      int i;
344      for(i=0;i<numWhens;i++) {
345        whens[i] = new TListCWhenTrigger();
346        whenDepends[i] = new TListCMsgBuffer *[numEntries];
347        numWhenDepends[i] = 0;
348      }
349      for(i=0;i<numEntries;i++) {
350        buffers[i] = new TListCMsgBuffer();
351        entryDepends[i] = new TListCWhenTrigger *[numWhens];
352        numEntryDepends[i] = 0;
353      }
354    }
355
356  public:
357    // adds a dependency of whenID upon Entry
358    // done only at initialization.
359    void addDepends(int whenID, int entry) {
360      whenDepends[whenID][numWhenDepends[whenID]++] = buffers[entry];
361      entryDepends[entry][numEntryDepends[entry]++] = whens[whenID];
362    }
363
364    // register a trigger to be called with
365    // with <nEntries> specified
366    // in <entries> with corresponding <refnums>
367    void Register(CWhenTrigger *trigger)
368    {
369      whens[trigger->whenID]->append(trigger);
370    }
371
372    // deregister trigger from all
373    // the entries it is registered for
374    void deRegister(CWhenTrigger *trigger)
375    {
376      whens[trigger->whenID]->remove(trigger);
377    }
378
379    // buffer a message for a specific entry point with a specified
380    // reference number
381    CMsgBuffer* bufferMessage(int entry, void *msg, void* log , int refnum)
382    {
383      CMsgBuffer *buf = new CMsgBuffer(entry, msg, log,refnum);
384      buffers[entry]->append(buf);
385      return buf;
386    }
387
388    // For a specified entry number and reference number,
389    // get the registered trigger which satisfies dependency. 
390    // If no trigger exists
391    // for the given reference number, get the trigger registered for
392    // ANY ref num. If that also doesnt exist, Return NULL
393    CWhenTrigger *getTrigger(int entry, int refnum)
394    {
395      for(int i=0;i<numEntryDepends[entry];i++) {
396        TListCWhenTrigger *wlist = entryDepends[entry][i];
397        for(CWhenTrigger *elem=wlist->begin(); 
398            !wlist->end(); 
399            elem=wlist->next()) {
400          if(elem==0)
401            break;
402          if(depSatisfied(elem)){
403             deRegister(elem);
404             return elem;
405          }
406        }
407      }
408      return 0;
409    }
410
411
412    // given the entry number and reference number,
413    // get the buffered message, without removing it from
414    // the list, NULL if no such message exists
415    CMsgBuffer *getMessage(int entry, int refnum)
416    {
417      TListCMsgBuffer *list = buffers[entry];
418      for(CMsgBuffer *elem=list->begin(); !list->end(); elem=list->next()) {
419        if(elem==0)
420          return 0;
421        if(elem->refnum == refnum)
422          return elem;
423      }
424      return 0;
425    }
426
427    // given the entry number,
428    // get the buffered message, without removing it from
429    // the list, NULL if no such message exists
430    // note that this is the ANY case
431    CMsgBuffer *getMessage(int entry)
432    {
433      return buffers[entry]->front();
434    }
435
436    // remove the given message from buffer
437    void removeMessage(CMsgBuffer *msg)
438    {
439      TListCMsgBuffer *list = buffers[msg->entry];
440      list->remove(msg);
441    }
442
443    // return 1 if all the dependeces for trigger are satisfied
444    // return 0 otherwise
445    int depSatisfied(CWhenTrigger *trigger)
446    {
447      int i;
448      for(i=0;i<trigger->nEntries;i++) {
449        if(!getMessage(trigger->entries[i], trigger->refnums[i]))
450          return 0;
451      }
452      for(i=0;i<trigger->nAnyEntries;i++) {
453        if(!getMessage(trigger->anyEntries[i]))
454          return 0;
455      }
456      return 1;
457    }
458 };
459
460
461 /** 
462  This class hides all of the details of dependencies between
463  overlap blocks and when blocks. 
464  */
465
466 class COverDep {
467
468    int numOverlaps, numWhens;
469    TListCWhenTrigger **whens;
470    int *numOverlapDepends;
471    TListCWhenTrigger ***overlapDepends;
472    
473   public:
474      void pup(PUP::er& p) {
475         /*
476           no need for initMem() because __sdag_pup() will take care of
477           allocating of COverDep and call addOverlapDepends(), so we don't pup overlapsDepends here
478         */
479         int i; // , j;
480         for (i=0; i<numWhens; i++)    whens[i]->pup(p);
481
482         p(numOverlapDepends, numOverlaps);
483      }
484
485      COverDep(int no, int nw) : numOverlaps(no), numWhens(nw) { initMem(); }
486
487      ~COverDep() {
488         int i;
489         delete [] numOverlapDepends;
490         for(i=0;i<numWhens;i++) {
491             delete whens[i];
492         }
493         for(i=0;i<numOverlaps;i++) {
494             delete [] overlapDepends[i];
495
496         }
497         delete [] whens;
498         delete [] overlapDepends;
499      }
500      
501    private:
502      void initMem() {
503        // initialize the internal data structures here
504        whens = new TListCWhenTrigger *[numWhens];
505        numOverlapDepends = new int[numOverlaps];
506        overlapDepends = new TListCWhenTrigger **[numOverlaps];
507        int i;
508        for(i=0;i<numWhens;i++) {
509          whens[i] = new TListCWhenTrigger();
510        }
511        for(i=0;i<numOverlaps;i++) {
512          overlapDepends[i] = new TListCWhenTrigger *[numWhens];
513          numOverlapDepends[i] = 0;
514        }
515      }
516
517    public:
518      //adds a dependency of the whenID for each Overlap
519      // done only at initialization
520      void addOverlapDepends(int whenID, int overlap) {
521        overlapDepends[overlap][whenID] = whens[whenID];
522        //overlapDepends[overlap][numOverlapDepends[overlap]++] = whens[whenID];
523      }
524      
525      // register a trigger to be called with
526      // with <nEntries> specified
527      // in <entries> with corresponding <refnums>
528      void Register(CWhenTrigger *trigger)
529      {
530        whens[trigger->whenID]->append(trigger);
531      }
532      
533      // deregister trigger from all
534      // the entries it is registered for
535      void deRegister(CWhenTrigger *trigger)
536      {
537         whens[trigger->whenID]->remove(trigger);
538      }
539      
540      
541      // For a specified entry number and reference number,
542      // get the registered trigger which satisfies dependency.
543      // If no trigger exists
544      // for the given reference number, get the trigger registered for
545      // ANY ref num. If that also doesnt exist, Return NULL
546      CWhenTrigger *getTrigger(int overlapID, int whenID)
547      {
548         TListCWhenTrigger *wlist = overlapDepends[overlapID][whenID];
549         CWhenTrigger *elem=wlist->begin(); 
550         if (elem == 0)
551           return 0;       
552         else {
553           deRegister(elem);
554           return elem;
555         }
556      }
557 };
558
559 class CCounter {
560   private:
561     unsigned int count;
562   public:
563     CCounter(int c) : count(c) {}
564     CCounter(int first, int last, int stride) {
565       count = ((last-first)/stride)+1;
566     }
567     void decrement(void) {count--;}
568     int isDone(void) {return (count==0);}
569 };
570
571 #endif