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