d26bf04498872d7fc2270b49a8c4b86542783f27
[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   if (!LDOMidEqual(destOM,d2.destOM)
105       || !LDObjIDEqual(destObj,d2.destObj))
106     return CmiFalse;
107   else return CmiTrue;
108 }
109
110 int LBCommData::compute_key()
111 {
112   int kstring[80];
113   char* kptr = (char*)((void*)(&(kstring[0])));
114   int pcount;
115
116   if (from_proc()) {
117     pcount = sprintf(kptr,"%d",src_proc);
118     kptr += pcount;
119   } else {
120     pcount = sprintf(kptr,"%d%d%d%d%d",srcObj.omID().id.idx,
121                      srcObj.id.id[0],srcObj.id.id[1],
122                      srcObj.id.id[2],srcObj.id.id[3]);
123     kptr += pcount;
124   }
125   pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destOM.id.idx,
126                     destObj.id[0],destObj.id[1],
127                     destObj.id[2],destObj.id[3]);
128   pcount -= 8;  /* The 'X's insure that the next few bytes are fixed */
129
130   int k=-1;
131   for(int i=0; i < (pcount+3)/4; i++)
132     k ^= kstring[i];
133
134   // CmiPrintf("New key %d, %s\n",k,kstring);
135
136   return k;
137 }
138
139 int LBCommData::hash(const int i, const int m) const
140 {
141   const double a = 0.6803398875;
142   const int k = key();
143   const double ka = k * a;
144
145   int h1 = (int) floor(m*(ka-floor(ka)));
146   int h2 = 1;  // Should be odd, to guarantee that h2 and size of table
147                // are relatively prime.
148
149   //  CmiPrintf("k=%d h1=%d h2=%d m=%d\n",k,h1,h2,m);
150   return (h1 + i * h2) % m;
151 }
152
153 void LBCommTable::GetCommData(LDCommData* data)
154 {
155   LDCommData* out=data;
156   LBCommData* curtable=set;
157   TableState* curstate=state;
158   int i;
159
160   for(i=0; i < cur_sz; i++, curtable++, curstate++) {
161     if (*curstate == InUse) {
162       if (curtable->from_proc()) {
163         out->src_proc = curtable->src_proc;
164       } else {
165         out->src_proc = -1;
166         out->senderOM = curtable->srcObj.omID();
167         out->sender = curtable->srcObj.objID();
168       }
169       out->dest_proc = -1;
170       out->receiverOM = curtable->destOM;
171       out->receiver = curtable->destObj;
172       out->messages = curtable->n_messages;
173       out->bytes = curtable->n_bytes;
174       out++;
175     }
176   }
177 }
178
179 #endif // CMK_LBDB_ON
180
181 /*@}*/