src/surf/gtnets/gtnets_topology.cc

   1
   2 //SGNode, SGTopology: tmporary classes for GTNetS topology.
   3
   4 #include "gtnets_topology.h"
   5
   6 //
   7 //  SGNode
   8 //
   9 //  TODO when merging a node, remember to add the existing "hosts".
  10 SGNode::SGNode(int id, int hostid){
  11   ID_ = id;
  12   if (hostid >= 0)
  13     hosts_.push_back(hostid);
  14 }
  15
  16 SGNode::~SGNode(){
  17   //TODO
  18 }
  19
  20 void SGNode::add_link(SGLink* newlink){
  21   links_.push_back(newlink);
  22 }
  23
  24
  25 SGLink* SGNode::other_link(int linkid){
  26   for (int i = 0; i < links_.size(); i++){
  27     if (links_[i]->id() != linkid)
  28       return links_[i];
  29   }
  30   return NULL;
  31 }
  32
  33 bool SGNode::has_link(SGLink* link){
  34   for (int i = 0; i < links_.size(); i++){
  35     //TODO can compare by object itself?
  36     if ((links_[i]->id()) == (link->id()))
  37       return true;
  38   }
  39   return false;
  40 }
  41
  42 void SGNode::print_hosts(){
  43   cout << "hosts[";
  44   for (int i = 0; i < hosts_.size(); i++){
  45     cout << hosts_[i] << ",";
  46   }
  47   cout << "] ";
  48 }
  49
  50 void SGNode::print_links(){
  51   cout << "links[";
  52   for (int i = 0; i < links_.size(); i++){
  53     cout << links_[i]->id() << ",";
  54   }
  55   cout << "]" << endl;
  56 }
  57
  58 vector<SGLink*>& SGNode::links(){
  59   return links_;
  60 }
  61 vector<int>& SGNode::hosts(){
  62   return hosts_;
  63 }
  64
  65 //
  66 //  SGLink
  67 //
  68 SGLink::SGLink(int id, SGNode* left, SGNode* right)
  69   :ID_(id),
  70    left_node_(left),
  71    right_node_(right){}
  72
  73
  74 SGLink::~SGLink(){
  75
  76 }
  77
  78 // add_left_linK: tow things.
  79 // add the link to the corresponding node.
  80 // add the corresponding node to the new link.
  81 //  (change from the tmp node to the correct node)
  82 void SGLink::add_left_link(SGLink* newlink, int side){
  83   if (!left_node_){
  84     //if alllinks don't have a node, then copy it from
  85     //tmporary link.
  86     if (side == LEFTSIDE){
  87       left_node_ = newlink->left_node_;
  88     } else if (side == RIGHTSIDE){
  89       left_node_ = newlink->right_node_;
  90     } else {
  91       cout << "should not come here. side: " << side << endl;
  92     }
  93   } else {
  94     // if already exists, then add the new link to the existing node.
  95     left_node_->add_link(newlink);
  96   }
  97
  98   if (side == LEFTSIDE){
  99     newlink->left_node_ = left_node_;
 100     //printf("link[%d] new left node: %d\n", link.ID, @left_node.ID)
 101   }else if (side == RIGHTSIDE){
 102     newlink->right_node_ = left_node_;
 103     //printf("link[%d] new left node: %d\n", link.ID, @left_node.ID)
 104   }else{
 105     cout << "should not come here. side: " << side << endl;
 106   }
 107
 108 }
 109
 110 void SGLink::add_right_link(SGLink* newlink, int side){
 111   if (!right_node_) {
 112     //if alllinks doesn't have a node, then copy it from
 113     //tmporary link.
 114     if (side == LEFTSIDE){
 115       right_node_ = newlink->left_node_;
 116     }else if (side == RIGHTSIDE){
 117       right_node_ = newlink->right_node_;
 118     }else{
 119       cout << "should not come here. side: " << side << endl;
 120     }
 121   }else{
 122     right_node_->add_link(newlink);
 123   }
 124
 125   if (side == LEFTSIDE){
 126     newlink->left_node_ = right_node_;
 127     //printf("link[%d] new left node: %d\n", link.ID, @right_node.ID)
 128   }else if (side == RIGHTSIDE){
 129     newlink->right_node_ = right_node_;
 130     //printf("link[%d] new right node: %d\n", link.ID, @right_node.ID)
 131   }else{
 132     cout << "should not come here. side: " << side << endl;
 133   }
 134 }
 135
 136 bool SGLink::is_inleft(SGLink* link){
 137   if (!left_node_)
 138     return false;
 139   else
 140     return left_node_->has_link(link);
 141 }
 142
 143 bool SGLink::is_inright(SGLink* link){
 144   if (!right_node_)
 145     return false;
 146   else
 147     return right_node_->has_link(link);
 148 }
 149
 150
 151 //return the pointer for the left link.
 152 SGLink* SGLink::left_link(){
 153   if (!left_node_){
 154     return NULL;
 155   }else{
 156     return left_node_->other_link(ID_);
 157   }
 158 }
 159
 160 SGLink* SGLink::right_link(){
 161   if (!right_node_){
 162     return NULL;
 163   }else{
 164     return right_node_->other_link(ID_);
 165   }
 166
 167 }
 168
 169 SGNode* SGLink::left_node(){
 170   return left_node_;
 171 }
 172
 173
 174 SGNode* SGLink::right_node(){
 175   return right_node_;
 176 }
 177
 178
 179 void SGLink::print(){
 180   printf("link[%d]:\n", ID_);
 181   if (left_node_){
 182     printf("   left  node: %d ", left_node_->id());
 183     left_node_->print_hosts();
 184     left_node_->print_links();
 185   }
 186
 187   if (right_node_){
 188     printf("   right node: %d ", right_node_->id());
 189     right_node_->print_hosts();
 190     right_node_->print_links();
 191   }
 192 }
 193
 194
 195 SGTopology::SGTopology(){
 196   nodeID_ = 0;
 197 }
 198
 199 SGTopology::~SGTopology(){
 200
 201 }
 202
 203
 204 // TODO: assume that all router-route 1-hop routes are set.
 205 void SGTopology::add_link(int src, int dst, int* links, int nsize){
 206   if (nsize == 1){
 207     map<int, SGNode*>::iterator it;
 208     it = nodes_.find(src);
 209     //if not exists, add one.
 210     if (it == nodes_.end()){
 211       nodes_[src] = new SGNode(src, src);
 212     }
 213     it = nodes_.find(dst);
 214     //if not exists, add one.
 215     if (it == nodes_.end()){
 216       nodes_[dst] = new SGNode(dst, dst);
 217     }
 218
 219     map<int, SGLink*>::iterator itl;
 220     itl = links_.find(links[0]);
 221     //if not exists, add one.
 222     if (itl == links_.end()){
 223       links_[links[0]] = new SGLink(links[0], nodes_[src], nodes_[dst]);
 224     }
 225   }
 226 }
 227
 228
 229 //create a temporary link set. (one route)
 230 // not used now. should clean up...
 231 void SGTopology::create_tmplink(int src, int dst, int* links, int nsize){
 232   map<int, SGLink*> tmplinks;
 233
 234   SGNode* n1;
 235   SGNode* n2;
 236
 237   int cur = -1;
 238   int nex;
 239
 240   for (int i = 0; i < nsize; i++){
 241     if (i == 0) {
 242       nodeID_++;  //new node
 243       n1   = new SGNode(nodeID_, src);
 244     }else
 245       n1   = n2; //current
 246
 247     cur = links[i];
 248
 249     if (i == (nsize-1)){
 250       nodeID_++;
 251       n2  = new SGNode(nodeID_, dst);
 252     }else{
 253       nex = links[i+1];
 254       nodeID_++;  //new node
 255       n2  = new SGNode(nodeID_, -1);
 256     }
 257
 258     tmplinks[cur] = new SGLink(cur, n1, n2);
 259     if (n1) n1->add_link(tmplinks[cur]);
 260     if (n2) n2->add_link(tmplinks[cur]);
 261   }
 262
 263   for (int i = 0; i < nsize; i++){
 264     //tmplinks[links[i]]->print();
 265     merge_link(tmplinks[links[i]]);
 266   }
 267   add_tmplink_to_links(tmplinks);
 268 }
 269
 270 void SGTopology::merge_link(SGLink* link){
 271   map<int, SGLink*>::iterator iter;
 272   iter = links_.find(link->id());
 273   if (iter == links_.end()){
 274     //if the link has not been added to the topology.links_, then
 275     //printf("link %d doesn't exist in alllinks. No action.\n", link->id());
 276     return;
 277   }else{
 278     int ncommon = 0;
 279     int comleft = -1;  //if tmplink.left == @alllinks.link.left, 0, otherwise, 1.
 280     int comright = -1; //if tmplink.right == @alllinks.link.left, 0, otherwise, 1.
 281     //since link is from tmplinks, each link has at most two neibours.
 282
 283     if (link->left_link()){
 284       //printf("common neibor: left_first: %d\n", link->left_link()->id());
 285       if (links_[link->id()]->is_inleft(link->left_link())){
 286         comleft = 0;
 287         ncommon += 1;
 288       }
 289       if (links_[link->id()]->is_inright(link->left_link())){
 290         comleft = 1;
 291         ncommon += 1;
 292       }
 293     }
 294
 295     if (link->right_link()){
 296       //printf("common neibor: right_first: %d\n", link->right_link()->id());
 297       if (links_[link->id()]->is_inleft(link->right_link())){
 298         comright = 0;
 299         ncommon += 1;
 300       }
 301       if (links_[link->id()]->is_inright(link->right_link())){
 302         comright = 1;
 303         ncommon += 1;
 304       }
 305     }
 306
 307     //printf("common: %d, comright: %d, comleft: %d\n",ncommon, comright, comleft);
 308
 309     if (ncommon == 0){
 310       //merge link.n1 with @alllink.n1, link.n2 with @alllink.n2
 311       if (link->left_link())
 312         links_[link->id()]->add_left_link(link->left_link(), RIGHTSIDE);
 313
 314       if (link->right_link())
 315         links_[link->id()]->add_right_link(link->right_link(), LEFTSIDE);
 316
 317     }else if (ncommon == 1){
 318       printf("ncommon %d\n", links_[link->id()]->id());
 319       //left --> right
 320       if ((comleft == -1) && (comright == 0)){
 321         if (link->left_link())
 322           links_[link->id()]->add_right_link(link->left_link(), RIGHTSIDE);
 323       }else if ((comleft == -1) && (comright == 1)){
 324         //left --> left
 325         if (link->left_link())
 326           links_[link->id()]->add_left_link(link->left_link(), RIGHTSIDE);
 327       }else if ((comright == -1) && (comleft == 0)){
 328         //right --> right
 329         if (link->right_link())
 330           links_[link->id()]->add_right_link(link->right_link(), LEFTSIDE);
 331       }else if ((comright == -1) && (comleft == 1)){
 332         //right --> left
 333         if (link->right_link())
 334           links_[link->id()]->add_left_link(link->right_link(), LEFTSIDE);
 335       }else{
 336         fprintf(stderr, "should not come here\n");
 337       }
 338
 339     }else if (ncommon == 2){
 340       //no change
 341
 342     }else{
 343       fprintf(stderr, "error, common links are more than 2. %d\n", ncommon);
 344     }
 345   }
 346 }
 347
 348 void SGTopology::add_tmplink_to_links(map<int, SGLink*> tmplink){
 349   map<int, SGLink*>::iterator iter;
 350
 351   for (iter = tmplink.begin(); iter != tmplink.end(); iter++){
 352     map<int, SGLink*>::iterator alliter = links_.find(iter->first);
 353     if (alliter == links_.end()){
 354       // cout << "tmplink " << iter->first << " not found in links_, adding."
 355       // << endl;
 356       links_[iter->first] = iter->second;
 357     }
 358     //    cout << "tmplink: " << iter->second->id() << endl;
 359   }
 360
 361 }
 362
 363 void SGTopology::print_topology(){
 364   map<int, SGLink*>::iterator iter;
 365   for (iter = links_.begin(); iter != links_.end(); iter++){
 366     iter->second->print();
 367   }
 368 }
 369
 370 void SGTopology::create_gtnets_topology(){
 371   map<int, SGLink*>::iterator it;
 372   for (it = links_.begin(); it != links_.end(); it++){
 373
 374   }
 375 }
 376
 377 map<int, SGLink*>& SGTopology::get_links(){
 378   return links_;
 379 }
 380