14 #include "TopoManager.h"
16 // Hash table mostly based on open hash table from Introduction to
17 // Algorithms by Cormen, Leiserson, and Rivest
19 // Moved comparison function to LDObjIDEqual
21 // static inline bool ObjIDEqual(const LDObjid i1, const LDObjid i2)
23 // return (bool)(i1.id[0] == i2.id[0]
24 // && i1.id[1] == i2.id[1] && i1.id[2] == i2.id[2]
25 // && i1.id[3] == i2.id[3]);
28 LBCommData* LBCommTable::HashInsert(const LBCommData &data)
30 if (in_use > cur_sz/2)
35 j = data.hash(i,cur_sz);
36 // CmiPrintf("Hashing to %d, %d %d\n",j,i,cur_sz);
37 if (state[j] == nil) {
43 } while (i != cur_sz);
45 // No room for item, but I should never get here, because I would have
47 CmiPrintf("HashInsert Couldn't insert!\n");
51 LBCommData* LBCommTable::HashSearch(const LBCommData &data)
56 j = data.hash(i,cur_sz);
57 if (state[j] != nil && set[j].equal(data)) {
61 } while (state[j] != nil && i != cur_sz);
65 LBCommData* LBCommTable::HashInsertUnique(const LBCommData &data)
67 LBCommData* item = HashSearch(data);
69 item = HashInsert(data);
74 void LBCommTable::Resize()
76 LBCommData* old_set = set;
77 TableState* old_state = state;
81 for(int i=0; i < old_sz; i++) {
82 if (old_state[i] == InUse)
83 HashInsert(old_set[i]);
89 bool LBCommData::equal(const LBCommData &d2) const
92 if (src_proc != d2.src_proc)
95 if (!LDOMidEqual(srcObj.omID(), d2.srcObj.omID())
96 || !LDObjIDEqual(srcObj.objID(),d2.srcObj.objID()) )
99 return (bool)(destObj == d2.destObj);
102 int LBCommData::compute_key()
105 char* kptr = (char*)((void*)(&(kstring[0])));
109 pcount = sprintf(kptr,"%d",src_proc);
112 pcount = sprintf(kptr,"%d%d%d%d%d",srcObj.omID().id.idx,
113 srcObj.id.id[0],srcObj.id.id[1],
114 srcObj.id.id[2],srcObj.id.id[3]);
118 //CmiAssert(destObj.get_type() == LD_OBJ_MSG);
119 switch (destObj.get_type()) {
121 pcount += sprintf(kptr,"%d", destObj.proc());
124 LDObjKey &destKey = destObj.get_destObj();
125 pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destKey.omID().id.idx,
126 destKey.objID().id[0],destKey.objID().id[1],
127 destKey.objID().id[2],destKey.objID().id[3]);
128 pcount -= 8; /* The 'X's insure that the next few bytes are fixed */
131 case LD_OBJLIST_MSG: {
133 LDObjKey *destKeys = destObj.get_destObjs(len);
135 pcount += sprintf(kptr,"%d%d%d%d%dXXXXXXXX",destKeys[0].omID().id.idx,
136 destKeys[0].objID().id[0],destKeys[0].objID().id[1],
137 destKeys[0].objID().id[2],destKeys[0].objID().id[3]);
138 pcount -= 8; /* The 'X's insure that the next few bytes are fixed */
144 for(int i=0; i < (pcount+3)/4; i++)
147 // CmiPrintf("New key %d, %s\n",k,kstring);
152 int LBCommData::hash(const int i, const int m) const
154 const double a = 0.6803398875;
156 const double ka = k * a;
158 int h1 = (int) floor(m*(ka-floor(ka)));
159 int h2 = 1; // Should be odd, to guarantee that h2 and size of table
160 // are relatively prime.
162 // CmiPrintf("k=%d h1=%d h2=%d m=%d\n",k,h1,h2,m);
163 return (h1 + i * h2) % m;
166 void LBCommTable::GetCommData(LDCommData* data)
168 LDCommData* out=data;
169 LBCommData* curtable=set;
170 TableState* curstate=state;
173 for(i=0; i < cur_sz; i++, curtable++, curstate++) {
174 if (*curstate == InUse) {
176 if (curtable->from_proc()) {
177 out->src_proc = curtable->src_proc;
180 out->sender.omID() = curtable->srcObj.omID();
181 out->sender.objID() = curtable->srcObj.objID();
183 out->receiver = curtable->destObj;
184 out->messages = curtable->n_messages;
185 out->bytes = curtable->n_bytes;
191 struct LDCommDescComp {
192 bool operator() (const LDCommDesc& lhs, const LDCommDesc &rhs) const {
193 return (lhs.get_destObj() < rhs.get_destObj());
197 void LBCommTable::GetCommInfo(int& bytes, int& msgs, int& outsidepemsgs, int&
198 outsidepebytes, int& num_nghbor, int& hops, int& hopbytes) {
200 LBCommData* curtable=set;
201 TableState* curstate=state;
209 std::set<LDCommDesc, LDCommDescComp> num_neighbors;
213 for(i=0; i < cur_sz; i++, curtable++, curstate++) {
214 if (*curstate == InUse) {
215 msgs += curtable->n_messages;
216 bytes += curtable->n_bytes;
217 if (curtable->destObj.get_type() == LD_OBJ_MSG) {
218 num_neighbors.insert(curtable->destObj);
221 if (curtable->destObj.lastKnown() != CkMyPe()) {
222 outsidepebytes += curtable->n_bytes;
223 outsidepemsgs += curtable->n_messages;
224 if(curtable->destObj.lastKnown()>=0 && curtable->destObj.lastKnown()<CkNumPes()){
225 TopoManager_getHopsBetweenPeRanks(CkMyPe(), curtable->destObj.lastKnown(), &h);
226 hops += curtable->n_messages * h;
227 hopbytes += curtable->n_bytes * h;
232 num_nghbor = num_neighbors.size();
235 #endif // CMK_LBDB_ON