important changes:
[charm.git] / src / ck-ldb / LBComm.C
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 /**
9  * \addtogroup CkLdb
10 */
11 /*@{*/
12
13 #include <converse.h>
14
15 #if CMK_LBDB_ON
16
17 #include <stdio.h>
18 #include <math.h>
19 #include "LBComm.h"
20
21 // Hash table mostly based on open hash table from Introduction to
22 // Algorithms by Cormen, Leiserson, and Rivest
23
24 // Moved comparison function to LDObjIDEqual
25
26 // static inline CmiBool ObjIDEqual(const LDObjid i1, const LDObjid i2)
27 // {
28 //   return (CmiBool)(i1.id[0] == i2.id[0] 
29 //       && i1.id[1] == i2.id[1] && i1.id[2] == i2.id[2] 
30 //       && i1.id[3] == i2.id[3]);
31 // };
32
33 LBCommData* LBCommTable::HashInsert(const LBCommData &data)
34 {
35   if (in_use > cur_sz/2)
36     Resize();
37   int i = 0;
38   int j;
39   do {
40     j = data.hash(i,cur_sz);
41     //    CmiPrintf("Hashing to %d, %d %d\n",j,i,cur_sz);
42     if (state[j] == nil) {
43       state[j] = InUse;
44       set[j] = data;
45       in_use++;
46       return &set[j];
47     } else i++;
48   } while (i != cur_sz);
49
50   // No room for item, but I should never get here, because I would have
51   // resized the list
52   CmiPrintf("HashInsert Couldn't insert!\n");
53   return 0;
54 }
55
56 LBCommData* LBCommTable::HashSearch(const LBCommData &data)
57 {
58   int i=0;
59   int j;
60   do {
61     j = data.hash(i,cur_sz);
62     if (state[j] != nil && set[j].equal(data)) {
63       return &set[j];
64     }
65     i++;
66   } while (state[j] != nil && i != cur_sz);
67   return 0;
68 }
69
70 LBCommData* LBCommTable::HashInsertUnique(const LBCommData &data)
71 {
72   LBCommData* item = HashSearch(data);
73   if (!item) {
74     item = HashInsert(data);
75   }
76   return item;
77 }
78
79 void LBCommTable::Resize()
80 {
81   LBCommData* old_set = set;
82   TableState* old_state = state;
83   int old_sz = cur_sz;
84
85   NewTable(old_sz*2);
86   for(int i=0; i < old_sz; i++) {
87     if (old_state[i] == InUse)
88       HashInsert(old_set[i]);
89   }
90   delete [] old_set;
91   delete [] old_state;
92 }       
93
94 CmiBool LBCommData::equal(const LBCommData d2) const
95 {
96   if (from_proc()) {
97     if (src_proc != d2.src_proc)
98       return CmiFalse;
99   } else {
100     if (!LDOMidEqual(srcObj.omID(), d2.srcObj.omID())
101         || !LDObjIDEqual(srcObj.objID(),d2.srcObj.objID()) )
102       return CmiFalse;
103   }
104   return (CmiBool)(destObj == d2.destObj);
105 }
106
107 int LBCommData::compute_key()
108 {
109   int kstring[80];
110   char* kptr = (char*)((void*)(&(kstring[0])));
111   int pcount;
112
113   if (from_proc()) {
114     pcount = sprintf(kptr,"%d",src_proc);
115     kptr += pcount;
116   } else {
117     pcount = sprintf(kptr,"%d%d%d%d%d",srcObj.omID().id.idx,
118                      srcObj.id.id[0],srcObj.id.id[1],
119                      srcObj.id.id[2],srcObj.id.id[3]);
120     kptr += pcount;
121   }
122
123   CmiAssert(destObj.get_type() == LD_OBJ_MSG);
124   switch (destObj.get_type()) {
125   case LD_PROC_MSG:
126        pcount += sprintf(kptr,"%d", destObj.proc());
127        break;
128   case LD_OBJ_MSG: {
129        LDObjKey &destKey = destObj.get_destObj();
130        pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destKey.omID().id.idx,
131                     destKey.objID().id[0],destKey.objID().id[1],
132                     destKey.objID().id[2],destKey.objID().id[3]);
133        pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
134        break;
135        }
136   case LD_OBJLIST_MSG: {
137        int len;
138        LDObjKey *destKeys = destObj.get_destObjs(len);
139        CmiAssert(len>0);
140        pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destKeys[0].omID().id.idx,
141                     destKeys[0].objID().id[0],destKeys[0].objID().id[1],
142                     destKeys[0].objID().id[2],destKeys[0].objID().id[3]);
143        pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
144        break;
145        }
146   }
147
148   int k=-1;
149   for(int i=0; i < (pcount+3)/4; i++)
150     k ^= kstring[i];
151
152   // CmiPrintf("New key %d, %s\n",k,kstring);
153
154   return k;
155 }
156
157 int LBCommData::hash(const int i, const int m) const
158 {
159   const double a = 0.6803398875;
160   const int k = key();
161   const double ka = k * a;
162
163   int h1 = (int) floor(m*(ka-floor(ka)));
164   int h2 = 1;  // Should be odd, to guarantee that h2 and size of table
165                // are relatively prime.
166
167   //  CmiPrintf("k=%d h1=%d h2=%d m=%d\n",k,h1,h2,m);
168   return (h1 + i * h2) % m;
169 }
170
171 void LBCommTable::GetCommData(LDCommData* data)
172 {
173   LDCommData* out=data;
174   LBCommData* curtable=set;
175   TableState* curstate=state;
176   int i;
177
178   for(i=0; i < cur_sz; i++, curtable++, curstate++) {
179     if (*curstate == InUse) {
180       if (curtable->from_proc()) {
181         out->src_proc = curtable->src_proc;
182       } else {
183         out->src_proc = -1;
184         out->sender.omID() = curtable->srcObj.omID();
185         out->sender.objID() = curtable->srcObj.objID();
186       }
187       CmiAssert(curtable->destObj.get_type() == LD_OBJ_MSG);
188       out->receiver = curtable->destObj;
189       out->messages = curtable->n_messages;
190       out->bytes = curtable->n_bytes;
191       out++;
192     }
193   }
194 }
195
196 #endif // CMK_LBDB_ON
197
198 /*@}*/