X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/7c878c7f73356568b2cf6c801d90e44a08a1e233..08df1a8222ae79ae145533fff43f069be907efc6:/src/surf/gtnets/gtnets_topology.cc

diff --git a/src/surf/gtnets/gtnets_topology.cc b/src/surf/gtnets/gtnets_topology.cc
index 16f019e837..09e2f263cb 100644
--- a/src/surf/gtnets/gtnets_topology.cc
+++ b/src/surf/gtnets/gtnets_topology.cc
@@ -1,380 +1,453 @@
+/* $ID$ */
 
-//SGNode, SGTopology: tmporary classes for GTNetS topology.
+/* Copyright (c) 2007 Kayo Fujiwara. All rights reserved.                  */
+
+/* This program is free software; you can redistribute it and/or modify it
+ * under the terms of the license (GNU LGPL) which comes with this package. */
+
+//GTNETS_Link, GTNETS_Node, GTNETS_Topology: 
+//Temporary classes for generating GTNetS topology
 
 #include "gtnets_topology.h"
 
 // 
-//  SGNode
+//  GTNETS_Node
 // 
-//  TODO when merging a node, remember to add the existing "hosts".
-SGNode::SGNode(int id, int hostid){
-  ID_ = id;
-  if (hostid >= 0)
-    hosts_.push_back(hostid);
-}
 
-SGNode::~SGNode(){
-  //TODO
+// Constructor
+GTNETS_Node::GTNETS_Node(int id):ID_(id),is_router_(false){}
+// Copy constructor
+GTNETS_Node::GTNETS_Node(const GTNETS_Node& node){
+  ID_ = node.ID_;
+  is_router_ = node.is_router_;
+  hosts_ = node.hosts_;
 }
 
-void SGNode::add_link(SGLink* newlink){
-  links_.push_back(newlink);
-}
+GTNETS_Node::~GTNETS_Node(){
 
-
-SGLink* SGNode::other_link(int linkid){
-  for (int i = 0; i < links_.size(); i++){
-    if (links_[i]->id() != linkid)
-      return links_[i];
-  }
-  return NULL;
 }
 
-bool SGNode::has_link(SGLink* link){
-  for (int i = 0; i < links_.size(); i++){
-    //TODO can compare by object itself?
-    if ((links_[i]->id()) == (link->id()))
-      return true;
+// hostid = network_card_id
+int GTNETS_Node::add_host(int hostid){
+  if (is_router_){
+    fprintf(stderr, "Cannot add a host to a router node.\n");
+    return -1;
   }
-  return false;
+  hosts_.insert(hostid);
+  return 0;
 }
 
-void SGNode::print_hosts(){
-  cout << "hosts[";
-  for (int i = 0; i < hosts_.size(); i++){
-    cout << hosts_[i] << ",";
+// Add a router. If this node already has a router/host,
+// return -1.
+int GTNETS_Node::add_router(int routerid){
+  if (hosts_.size() > 1){
+    fprintf(stderr, "Router node should have only one router.\n");
+    return -1;
+  }else if (hosts_.size() == 1){
+    if (hosts_.find(routerid) != hosts_.end()){
+      //printf("the router already exists\n");
+      return 0;
+    }else{
+      fprintf(stderr, "Node %d is a different router.\n");
+      return -1;
+    }
   }
-  cout << "] ";
+  is_router_ = true;
+  hosts_.insert(routerid);
+  return 0;
 }
 
-void SGNode::print_links(){
-  cout << "links[";
-  for (int i = 0; i < links_.size(); i++){
-    cout << links_[i]->id() << ",";
-  }
-  cout << "]" << endl;
+bool GTNETS_Node::is_router(){
+  return is_router_;
 }
 
-vector<SGLink*>& SGNode::links(){
-  return links_;
+bool GTNETS_Node::include(int hostid){
+  if (hosts_.find(hostid) == hosts_.end()) return false;
+  else return true;
 }
-vector<int>& SGNode::hosts(){
-  return hosts_;
+
+void GTNETS_Node::print_hosts(){
+  set<int>::iterator it;
+  printf("[");
+  for (it = hosts_.begin(); it != hosts_.end(); it++){
+    printf(" %d", *it);
+  }
+  printf("]");
 }
 
 //
-//  SGLink
+//  GTNETS_Link
 //
-SGLink::SGLink(int id, SGNode* left, SGNode* right)
-  :ID_(id),
-   left_node_(left),
-   right_node_(right){}
 
+// Constructor
+GTNETS_Link::GTNETS_Link(){
+  ID_=-1;
+  src_node_ = 0;
+  dst_node_ = 0;
+}
+GTNETS_Link::GTNETS_Link(int id):ID_(id), src_node_(0), dst_node_(0){}
 
-SGLink::~SGLink(){
+// Copy constructor
+GTNETS_Link::GTNETS_Link(const GTNETS_Link& link){
+  ID_ = link.ID_;
+  src_node_ = link.src_node_;
+  dst_node_ = link.dst_node_;
+}
 
+GTNETS_Link::~GTNETS_Link(){
+  
 }
 
-// add_left_linK: tow things.
-// add the link to the corresponding node.
-// add the corresponding node to the new link. 
-//  (change from the tmp node to the correct node)
-void SGLink::add_left_link(SGLink* newlink, int side){
-  if (!left_node_){
-    //if alllinks don't have a node, then copy it from
-    //tmporary link.
-    if (side == LEFTSIDE){
-      left_node_ = newlink->left_node_;
-    } else if (side == RIGHTSIDE){
-      left_node_ = newlink->right_node_;
-    } else {
-      cout << "should not come here. side: " << side << endl;
-    }
-  } else {
-    // if already exists, then add the new link to the existing node.
-    left_node_->add_link(newlink);
+void GTNETS_Link::print_link_status(){
+  printf("== LINKID: %d\n", ID_);
+  if (src_node_){
+    printf("  [SRC] ID: %d, router?: %d, hosts[]: ",
+	   src_node_->id(), src_node_->is_router());
+    src_node_->print_hosts();
+    printf("\n");
   }
 
-  if (side == LEFTSIDE){
-    newlink->left_node_ = left_node_;
-    //printf("link[%d] new left node: %d\n", link.ID, @left_node.ID)
-  }else if (side == RIGHTSIDE){
-    newlink->right_node_ = left_node_;
-    //printf("link[%d] new left node: %d\n", link.ID, @left_node.ID)
-  }else{
-    cout << "should not come here. side: " << side << endl;
+  if (dst_node_){
+    printf("  [DST] ID: %d, router?: %d, hosts[]: ", 
+	   dst_node_->id(), dst_node_->is_router());
+    dst_node_->print_hosts();
+    printf("\n");
   }
+}
 
+GTNETS_Node* GTNETS_Link::src_node(){
+  return src_node_;
 }
 
-void SGLink::add_right_link(SGLink* newlink, int side){
-  if (!right_node_) {
-    //if alllinks doesn't have a node, then copy it from
-    //tmporary link.
-    if (side == LEFTSIDE){
-      right_node_ = newlink->left_node_;
-    }else if (side == RIGHTSIDE){
-      right_node_ = newlink->right_node_;
-    }else{
-      cout << "should not come here. side: " << side << endl;
-    }
-  }else{
-    right_node_->add_link(newlink);
-  }
+GTNETS_Node* GTNETS_Link::dst_node(){
+  return dst_node_;
+}
 
-  if (side == LEFTSIDE){
-    newlink->left_node_ = right_node_;
-    //printf("link[%d] new left node: %d\n", link.ID, @right_node.ID)
-  }else if (side == RIGHTSIDE){
-    newlink->right_node_ = right_node_;
-    //printf("link[%d] new right node: %d\n", link.ID, @right_node.ID)
-  }else{
-    cout << "should not come here. side: " << side << endl;
+bool GTNETS_Link::route_exists(){
+  if (src_node_ && dst_node_) return true;
+  else return false;
+}
+
+// return the peer node id
+int GTNETS_Link::peer_node(int cur_id){
+  if (cur_id ==  src_node_->id()) return dst_node_->id();
+  else if (cur_id == dst_node_->id()) return src_node_->id();
+  else {
+    fprintf(stderr, "node not found\n");
+    return -1;
   }
 }
 
-bool SGLink::is_inleft(SGLink* link){
-  if (!left_node_)
-    return false;
-  else
-    return left_node_->has_link(link);
+int GTNETS_Link::add_src(GTNETS_Node* src){
+  src_node_ = src;
 }
 
-bool SGLink::is_inright(SGLink* link){
-  if (!right_node_)
-    return false;
-  else
-    return right_node_->has_link(link);
+int GTNETS_Link::add_dst(GTNETS_Node* dst){
+  dst_node_ = dst;
 }
 
 
-//return the pointer for the left link.
-SGLink* SGLink::left_link(){
-  if (!left_node_){
-    return NULL;
-  }else{
-    return left_node_->other_link(ID_);
-  }
+//
+//  GTNETS_Topology
+//
+
+// Constructor
+GTNETS_Topology::GTNETS_Topology(){
+  nodeID_ = 0;
 }
 
-SGLink* SGLink::right_link(){
-  if (!right_node_){
-    return NULL;
-  }else{
-    return right_node_->other_link(ID_);
+// Destructor
+GTNETS_Topology::~GTNETS_Topology(){
+  map<int, GTNETS_Link*>::iterator it1;
+  for (it1 = links_.begin(); it1 != links_.end(); it1++){
+    delete it1->second;
+  }
+  vector<GTNETS_Node*>::iterator it2;
+  for (it2 = nodes_.begin(); it2 != nodes_.end(); it2++){
+    delete *it2;
   }
-
 }
 
-SGNode* SGLink::left_node(){
-  return left_node_;
-}
 
+int GTNETS_Topology::link_size(){
+  return links_.size();
+}
 
-SGNode* SGLink::right_node(){
-  return right_node_;
+int GTNETS_Topology::node_size(){
+  return nodes_.size();
 }
 
+int GTNETS_Topology::add_link(int id){
+  map<int,GTNETS_Link*>::iterator iter = links_.find(id);
 
-void SGLink::print(){
-  printf("link[%d]:\n", ID_);
-  if (left_node_){
-    printf("   left  node: %d ", left_node_->id());
-    left_node_->print_hosts();
-    left_node_->print_links();
-  }
-  
-  if (right_node_){
-    printf("   right node: %d ", right_node_->id());
-    right_node_->print_hosts();
-    right_node_->print_links();
+  if(iter == links_.end()) {
+    GTNETS_Link* link= new GTNETS_Link(id);
+    //printf("link %d is added: %d\n", id, link->id());
+    //links_.insert(make_pair(id, link));
+    links_[id] = link;
+    return 0;
+  }else{
+    fprintf(stderr, "Link %d already exists.\n", id);
+    return -1;
   }
 }
 
+int GTNETS_Topology::add_router(int id){
+  set<int>::iterator iter = routers_.find(id);
 
-SGTopology::SGTopology(){
-  nodeID_ = 0;
+  if(iter == routers_.end()) {
+    //printf("router %d is inserted\n", id);
+    routers_.insert(id);
+    return 0;
+  }else{
+    fprintf(stderr, "Router %d already exists.\n", id);
+    return -1;
+  }
 }
 
-SGTopology::~SGTopology(){
+bool GTNETS_Topology::is_router(int id){
+  set<int>::iterator iter = routers_.find(id);
+  if(iter == routers_.end()) return false;
+  else return true;
+}
 
+//return the node id of the peer of cur_id by linkid.
+int GTNETS_Topology::peer_node_id(int linkid, int cur_id){
+  //printf("linkid: %d, cur_id: %d\n", linkid, cur_id);
+  GTNETS_Link* link = links_[linkid];
+  if (!link) {
+    fprintf(stderr, "link %d not found\n", linkid);
+    return -1;
+  }
+  if ((cur_id < 0) || (cur_id > nodes_.size()-1)){
+    fprintf(stderr, "node %d not found\n", cur_id);
+    return -1;
+  }
+  int peer  = link->peer_node(nodes_[cur_id]->id());
+  if (peer < 0){
+    fprintf(stderr, "peer not found\n");
+    return -1;
+  }
+  return peer;
 }
 
+int GTNETS_Topology::add_onehop_route(int src, int dst, int linkid){
+  GTNETS_Link* link;
 
-// TODO: assume that all router-route 1-hop routes are set.
-void SGTopology::add_link(int src, int dst, int* links, int nsize){
-  if (nsize == 1){
-    map<int, SGNode*>::iterator it;
-    it = nodes_.find(src);
-    //if not exists, add one.
-    if (it == nodes_.end()){    
-      nodes_[src] = new SGNode(src, src);
-    }
-    it = nodes_.find(dst);
-    //if not exists, add one.
-    if (it == nodes_.end()){    
-      nodes_[dst] = new SGNode(dst, dst);
-    }
+  map<int, GTNETS_Link*>::iterator iter = links_.find(linkid);
 
-    map<int, SGLink*>::iterator itl;
-    itl = links_.find(links[0]);
-    //if not exists, add one.
-    if (itl == links_.end()){
-      links_[links[0]] = new SGLink(links[0], nodes_[src], nodes_[dst]);
-    }
+  if(iter == links_.end()) {
+    fprintf(stderr, "Link %d not found.\n", linkid);
+    return -1;
+  }else{
+    link = iter->second;
   }
-}
 
+  //  printf("add_onehop_route: src: %d, dst: %d, linkid: %d, %d\n",
+  //	 src, dst, linkid, link->id());
 
-//create a temporary link set. (one route)
-// not used now. should clean up...
-void SGTopology::create_tmplink(int src, int dst, int* links, int nsize){
-  map<int, SGLink*> tmplinks;
+  GTNETS_Node *src_node, *dst_node;
+  src_node = link->src_node();
+  dst_node = link->dst_node();
 
-  SGNode* n1;
-  SGNode* n2;
 
-  int cur = -1;
-  int nex;
+  // If not exists a route, add one.
+  if (!link->route_exists()){
+    //check whether there exists a node for the src host/router.
+    int s_node_id = nodeid_from_hostid(src);
+    int node_id;
+
+    if (s_node_id < 0){//not exist, create one.
+      s_node_id = nodeID_;
+      GTNETS_Node* node1 = new GTNETS_Node(s_node_id);
+      nodes_.push_back(node1);
+      hosts_[src] = nodes_[s_node_id]->id();
 
-  for (int i = 0; i < nsize; i++){
-    if (i == 0) {
-      nodeID_++;  //new node
-      n1   = new SGNode(nodeID_, src);
-    }else 
-      n1   = n2; //current
-    
-    cur = links[i];
-    
-    if (i == (nsize-1)){
       nodeID_++;
-      n2  = new SGNode(nodeID_, dst);
-    }else{
-      nex = links[i+1];
-      nodeID_++;  //new node
-      n2  = new SGNode(nodeID_, -1);
     }
 
-    tmplinks[cur] = new SGLink(cur, n1, n2);
-    if (n1) n1->add_link(tmplinks[cur]);
-    if (n2) n2->add_link(tmplinks[cur]);
+    if (is_router(src))
+      nodes_[s_node_id]->add_router(src);
+    else
+      nodes_[s_node_id]->add_host(src);
+
+    link->add_src(nodes_[s_node_id]);
+
+    //check whether there exists a node for the dst host/router.
+    int d_node_id = nodeid_from_hostid(dst);
+    if (d_node_id < 0){//not exist, create one.
+      d_node_id = nodeID_;
+      GTNETS_Node* node2 = new GTNETS_Node(d_node_id);
+      nodes_.push_back(node2);
+      hosts_[dst] = nodes_[d_node_id]->id();
+      nodeID_++;
+    }
+
+    if (is_router(dst))
+      nodes_[d_node_id]->add_router(dst);
+    else
+      nodes_[d_node_id]->add_host(dst);
+
+    link->add_dst(nodes_[d_node_id]);
+
+  // other: has either src or dst (error)
+  }else if (!src_node || !dst_node){
+    fprintf(stderr, "Either src or dst is null\n");
+    return -1;
   }
 
-  for (int i = 0; i < nsize; i++){
-    //tmplinks[links[i]]->print();
-    merge_link(tmplinks[links[i]]);
+  // case 1: link has two routers
+  else if (src_node->is_router() && dst_node->is_router()){
+    int tmpsrc1 = src_node->id();
+    int tmpsrc2 = nodeid_from_hostid(src);
+    int tmpdst1 = dst_node->id();
+    int tmpdst2 = nodeid_from_hostid(dst);
+    if (((tmpsrc1 == tmpsrc2) && (tmpdst1 == tmpdst2)) ||
+	((tmpsrc1 == tmpdst2) && (tmpdst1 == tmpsrc2))){
+      fprintf(stderr, "Route already exists\n");
+    }else{
+      fprintf(stderr, "Different one hop route defined\n");
+      return -1;
+    }
   }
-  add_tmplink_to_links(tmplinks);
-}
+  // case 2: link has one router and one host
+  else if (src_node->is_router() && !dst_node->is_router()){
+    int newsrc, newdst;
+    if (is_router(src)){
+      newsrc = src;
+      newdst = dst;
+    }else if (is_router(dst)){
+      newsrc = dst;
+      newdst = src;
+    }else{
+      fprintf(stderr, "one of nodes should be a router\n");
+      return -1;
+    }
 
-void SGTopology::merge_link(SGLink* link){
-  map<int, SGLink*>::iterator iter;
-  iter = links_.find(link->id());
-  if (iter == links_.end()){
-    //if the link has not been added to the topology.links_, then
-    //printf("link %d doesn't exist in alllinks. No action.\n", link->id());
-    return;
-  }else{
-    int ncommon = 0;
-    int comleft = -1;  //if tmplink.left == @alllinks.link.left, 0, otherwise, 1.
-    int comright = -1; //if tmplink.right == @alllinks.link.left, 0, otherwise, 1.
-    //since link is from tmplinks, each link has at most two neibours.
-
-    if (link->left_link()){
-      //printf("common neibor: left_first: %d\n", link->left_link()->id());
-      if (links_[link->id()]->is_inleft(link->left_link())){
-	comleft = 0;
-	ncommon += 1;
-      }
-      if (links_[link->id()]->is_inright(link->left_link())){
-	comleft = 1;
-	ncommon += 1;
-      }
+    if (src_node->id() != nodeid_from_hostid(newsrc)){
+      fprintf(stderr, "The router should be identical\n");
+      return -1;
     }
 
-    if (link->right_link()){
-      //printf("common neibor: right_first: %d\n", link->right_link()->id());
-      if (links_[link->id()]->is_inleft(link->right_link())){
-	comright = 0;
-	ncommon += 1;
-      }
-      if (links_[link->id()]->is_inright(link->right_link())){
-	comright = 1;
-	ncommon += 1;
-      }
+    //now, to add dst to dst_node, dst should be a host.
+
+    if (is_router(newdst)){
+      fprintf(stderr, "dst %d is not an endpoint. cannot add it to dst_node\n");
+      return -1;
     }
 
-    //printf("common: %d, comright: %d, comleft: %d\n",ncommon, comright, comleft);
+    if (!dst_node->include(newdst)){
+      dst_node->add_host(newdst);
+      hosts_[newdst] = dst_node->id();
+    }
+  }
+  else if (!src_node->is_router() && dst_node->is_router()){
+    int newsrc, newdst;
+    if (is_router(src)){
+      newsrc = dst;
+      newdst = src;
+    }else if (is_router(dst)){
+      newsrc = src;
+      newdst = dst;
+    }else{
+      fprintf(stderr, "one of nodes should be a router\n");
+      return -1;
+    }
 
-    if (ncommon == 0){
-      //merge link.n1 with @alllink.n1, link.n2 with @alllink.n2
-      if (link->left_link())
-	links_[link->id()]->add_left_link(link->left_link(), RIGHTSIDE);
 
-      if (link->right_link())
-	links_[link->id()]->add_right_link(link->right_link(), LEFTSIDE);
-      
-    }else if (ncommon == 1){
-      printf("ncommon %d\n", links_[link->id()]->id());
-      //left --> right
-      if ((comleft == -1) && (comright == 0)){
-	if (link->left_link())
-	  links_[link->id()]->add_right_link(link->left_link(), RIGHTSIDE);
-      }else if ((comleft == -1) && (comright == 1)){
-	//left --> left
-	if (link->left_link())
-	  links_[link->id()]->add_left_link(link->left_link(), RIGHTSIDE);
-      }else if ((comright == -1) && (comleft == 0)){
-	//right --> right
-	if (link->right_link())
-	  links_[link->id()]->add_right_link(link->right_link(), LEFTSIDE);
-      }else if ((comright == -1) && (comleft == 1)){
-	//right --> left
-	if (link->right_link())
-	  links_[link->id()]->add_left_link(link->right_link(), LEFTSIDE);
-      }else{
-	fprintf(stderr, "should not come here\n");
-      }
+    if (dst_node->id() != hosts_[newdst]){
+      fprintf(stderr, "The router should be identical\n");
+      return -1;
+    }
 
-    }else if (ncommon == 2){
-      //no change
+    //now, to add dst to src_node, dst should be a host.
 
-    }else{
-      fprintf(stderr, "error, common links are more than 2. %d\n", ncommon);
+    if (is_router(newsrc)){
+      fprintf(stderr, "dst %d is not an endpoint. cannot add it to src_node\n");
+      return -1;
+    }
+
+    if (!src_node->include(newsrc)){
+      src_node->add_host(newsrc);
+      hosts_[newsrc] = src_node->id();
     }
   }
-}
 
-void SGTopology::add_tmplink_to_links(map<int, SGLink*> tmplink){
-  map<int, SGLink*>::iterator iter;
+  // case 3: link has two hosts
+  else if (!src_node->is_router() && !dst_node->is_router()){
 
-  for (iter = tmplink.begin(); iter != tmplink.end(); iter++){
-    map<int, SGLink*>::iterator alliter = links_.find(iter->first);
-    if (alliter == links_.end()){
-      // cout << "tmplink " << iter->first << " not found in links_, adding."
-      // << endl;
-      links_[iter->first] = iter->second;
+    if (is_router(src) || is_router(dst)){
+      fprintf(stderr, "Cannot add a router to host-host link\n");
+      return -1;
     }
-    //    cout << "tmplink: " << iter->second->id() << endl;
+
+    //if both are hosts, the order doesn't matter.
+    if (src_node->include(src)){
+      if (dst_node->include(dst)){
+	//nothing
+      }else{
+	dst_node->add_host(dst);
+	hosts_[dst] = dst_node->id();
+      }
+    }else if (src_node->include(dst)){
+      if (dst_node->include(src)){
+	//nothing
+      }else{
+	dst_node->add_host(src);
+	hosts_[src] = dst_node->id();
+      }
+    }else if (dst_node->include(src)){
+      if (src_node->include(dst)){
+	//nothing
+      }else{
+	src_node->add_host(dst);
+	hosts_[dst] = src_node->id();
+      }
+    }else if (dst_node->include(dst)){
+      if (src_node->include(src)){
+	//nothing
+      }else{
+	src_node->add_host(src);
+	hosts_[src] = src_node->id();
+      }
+    }else{
+      src_node->add_host(src);
+      dst_node->add_host(dst);
+      hosts_[src] = src_node->id();
+      hosts_[dst] = dst_node->id();
+    }   
+      
+  }
+  else{
+    fprintf(stderr, "Shouldn't be here\n");
+    return -1;
   }
-							       
+  return 0;
 }
 
-void SGTopology::print_topology(){
-  map<int, SGLink*>::iterator iter;
-  for (iter = links_.begin(); iter != links_.end(); iter++){
-    iter->second->print();
-  }
+int GTNETS_Topology::nodeid_from_hostid(int hostid){
+  map<int,int>::iterator it = hosts_.find(hostid);
+  if (it == hosts_.end())
+    return -1;
+  else return it->second;
 }
 
-void SGTopology::create_gtnets_topology(){
-  map<int, SGLink*>::iterator it;
+void GTNETS_Topology::print_topology(){
+  printf("<<<<<================================>>>>>\n");
+  printf("Dumping GTNETS topollogy information\n");
+  map<int, GTNETS_Link*>::iterator it;
   for (it = links_.begin(); it != links_.end(); it++){
-    
+    it->second->print_link_status();
   }
+  printf(">>>>>================================<<<<<\n");
+  fflush(NULL);
+}
+
+const vector<GTNETS_Node*>& GTNETS_Topology::nodes(){
+  return nodes_;
 }
 
-map<int, SGLink*>& SGTopology::get_links(){
+const map<int, GTNETS_Link*>& GTNETS_Topology::links(){
   return links_;
 }