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