src/surf/surf_routing.c

   1 /* Copyright (c) 2009, 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 #include <float.h>
   8 #include "surf_private.h"
   9 #include "xbt/dynar.h"
  10 #include "xbt/str.h"
  11 #include "xbt/config.h"
  12 #include "xbt/graph.h"
  13 #include "xbt/set.h"
  14
  15 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route,surf,"Routing part of surf");
  16
  17 /* Global vars */
  18 routing_global_t global_routing = NULL;
  19 routing_component_t current_routing = NULL;
  20 model_type_t current_routing_model = NULL;
  21
  22 /* Prototypes of each model */
  23 static void* model_full_create(void); /* create structures for full routing model */
  24 static void  model_full_load(void);   /* load parse functions for full routing model */
  25 static void  model_full_unload(void); /* unload parse functions for full routing model */
  26 static void  model_full_end(void);    /* finalize the creation of full routing model */
  27
  28 static void* model_floyd_create(void); /* create structures for floyd routing model */
  29 static void  model_floyd_load(void);   /* load parse functions for floyd routing model */
  30 static void  model_floyd_unload(void); /* unload parse functions for floyd routing model */
  31 static void  model_floyd_end(void);    /* finalize the creation of floyd routing model */
  32
  33 static void* model_dijkstra_both_create(int cached); /* create by calling dijkstra or dijkstracache */
  34 static void* model_dijkstra_create(void);      /* create structures for dijkstra routing model */
  35 static void* model_dijkstracache_create(void); /* create structures for dijkstracache routing model */
  36 static void  model_dijkstra_both_load(void);   /* load parse functions for dijkstra routing model */
  37 static void  model_dijkstra_both_unload(void); /* unload parse functions for dijkstra routing model */
  38 static void  model_dijkstra_both_end(void);    /* finalize the creation of dijkstra routing model */
  39
  40 static void* model_none_create(void); /* none routing model */
  41 static void  model_none_load(void);   /* none routing model */
  42 static void  model_none_unload(void); /* none routing model */
  43 static void  model_none_end(void);    /* none routing model */
  44
  45 /* this lines are olny for replace use like index in the model table */
  46 #define SURF_MODEL_FULL           0
  47 #define SURF_MODEL_FLOYD          1
  48 #define SURF_MODEL_DIJKSTRA       2
  49 #define SURF_MODEL_DIJKSTRACACHE  3
  50 #define SURF_MODEL_NONE           4
  51
  52 /* must be finish with null and carefull if change de order */
  53 struct s_model_type routing_models[] =
  54 { {"Full", "Full routing data (fast, large memory requirements, fully expressive)",
  55   model_full_create, model_full_load, model_full_unload, model_full_end },
  56   {"Floyd", "Floyd routing data (slow initialization, fast lookup, lesser memory requirements, shortest path routing only)",
  57   model_floyd_create, model_floyd_load, model_floyd_unload, model_floyd_end },
  58   {"Dijkstra", "Dijkstra routing data (fast initialization, slow lookup, small memory requirements, shortest path routing only)",
  59   model_dijkstra_create ,model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
  60   {"DijkstraCache", "Dijkstra routing data (fast initialization, fast lookup, small memory requirements, shortest path routing only)",
  61   model_dijkstracache_create, model_dijkstra_both_load, model_dijkstra_both_unload, model_dijkstra_both_end },
  62   {"none", "No routing (usable with Constant network only)",
  63   model_none_create, model_none_load, model_none_unload, model_none_end },
  64   {NULL,NULL,NULL,NULL,NULL,NULL}};
  65
  66 /* ************************************************************************** */
  67 /* ***************** GENERIC PARSE FUNCTIONS (declarations) ***************** */
  68
  69 static void generic_set_processing_units(routing_component_t rc, const char* name);
  70 static void generic_set_autonomous_system(routing_component_t rc, const char* name);
  71 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route);
  72 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
  73 static void generic_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route);
  74
  75 /* ************************************************************************** */
  76 /* *************** GENERIC BUSINESS METHODS (declarations) ****************** */
  77
  78 static route_extended_t generic_get_bypassroute(routing_component_t rc, const char* src, const char* dst);
  79
  80 /* ************************************************************************** */
  81 /* ****************** GENERIC AUX FUNCTIONS (declarations) ****************** */
  82
  83 static route_extended_t generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy, void* data, int order);
  84 static void generic_free_extended_route(route_extended_t e_route);
  85 static routing_component_t generic_autonomous_system_exist(routing_component_t rc, char* element);
  86 static routing_component_t generic_processing_units_exist(routing_component_t rc, char* element);
  87 static void generic_src_dst_check(routing_component_t rc, const char* src, const char* dst);
  88
  89 /* ************************************************************************** */
  90 /* **************************** GLOBAL FUNCTIONS **************************** */
  91
  92 /* global parse functions */
  93 static char* src = NULL;    /* temporary store the source name of a route */
  94 static char* dst = NULL;    /* temporary store the destination name of a route */
  95 static char* gw_src = NULL; /* temporary store the gateway source name of a route */
  96 static char* gw_dst = NULL; /* temporary store the gateway destination name of a route */
  97 static xbt_dynar_t link_list = NULL; /* temporary store of current list link of a route */
  98
  99 /**
 100  * \brief Add a "host" to the network element list
 101  */
 102 static void  parse_S_host(void) {
 103   if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
 104   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_host_id),
 105       "Reading a host, processing unit \"%s\" already exist",A_surfxml_host_id);
 106   xbt_assert1(current_routing->set_processing_units,
 107       "no defined method \"set_processing_units\" in \"%s\"",current_routing->name);
 108   (*(current_routing->set_processing_units))(current_routing,A_surfxml_host_id);
 109   xbt_dict_set(global_routing->where_network_elements,A_surfxml_host_id,(void*)current_routing,NULL);
 110 }
 111
 112 /**
 113  * \brief Add a "router" to the network element list
 114  */
 115 static void parse_S_router(void) {
 116   if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_BASE;
 117   xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,A_surfxml_router_id),
 118       "Reading a router, processing unit \"%s\" already exist",A_surfxml_router_id);
 119   xbt_assert1(current_routing->set_processing_units,
 120       "no defined method \"set_processing_units\" in \"%s\"",current_routing->name);
 121   (*(current_routing->set_processing_units))(current_routing,A_surfxml_router_id);
 122   xbt_dict_set(global_routing->where_network_elements,A_surfxml_router_id,(void*)current_routing,NULL);
 123 }
 124
 125 /**
 126  * \brief Set the endponints for a route
 127  */
 128 static void parse_S_route_new_and_endpoints(void) {
 129   if( src != NULL && dst != NULL && link_list != NULL )
 130     THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_route_src,A_surfxml_route_dst);
 131   src = A_surfxml_route_src;
 132   dst = A_surfxml_route_dst;
 133   xbt_assert2(strlen(src)>0||strlen(dst)>0,
 134       "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
 135   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 136 }
 137
 138 /**
 139  * \brief Set the endponints and gateways for a ASroute
 140  */
 141 static void parse_S_ASroute_new_and_endpoints(void) {
 142   if( src != NULL && dst != NULL && link_list != NULL )
 143     THROW2(arg_error,0,"Route between %s to %s can not be defined",A_surfxml_ASroute_src,A_surfxml_ASroute_dst);
 144   src = A_surfxml_ASroute_src;
 145   dst = A_surfxml_ASroute_dst;
 146   gw_src = A_surfxml_ASroute_gw_src;
 147   gw_dst = A_surfxml_ASroute_gw_dst;
 148   xbt_assert2(strlen(src)>0||strlen(dst)>0||strlen(gw_src)>0||strlen(gw_dst)>0,
 149       "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
 150   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 151 }
 152
 153 /**
 154  * \brief Set the endponints for a bypassRoute
 155  */
 156 static void parse_S_bypassRoute_new_and_endpoints(void) {
 157   if( src != NULL && dst != NULL && link_list != NULL )
 158     THROW2(arg_error,0,"Bypass Route between %s to %s can not be defined",A_surfxml_bypassRoute_src,A_surfxml_bypassRoute_dst);
 159   src = A_surfxml_bypassRoute_src;
 160   dst = A_surfxml_bypassRoute_dst;
 161   gw_src = A_surfxml_bypassRoute_gw_src;
 162   gw_dst = A_surfxml_bypassRoute_gw_dst;
 163   xbt_assert2(strlen(src)>0||strlen(dst)>0||strlen(gw_src)>0||strlen(gw_dst)>0,
 164       "Some limits are null in the route between \"%s\" and \"%s\"",src,dst);
 165   link_list = xbt_dynar_new(sizeof(char*), &xbt_free_ref);
 166 }
 167
 168 /**
 169  * \brief Set a new link on the actual list of link for a route or ASroute
 170  */
 171 static void parse_E_link_c_ctn_new_elem(void) {
 172   char *val;
 173   val = xbt_strdup(A_surfxml_link_c_ctn_id);
 174   xbt_dynar_push(link_list, &val);
 175 }
 176
 177 /**
 178  * \brief Store the route by calling the set_route function of the current routing component
 179  */
 180 static void parse_E_route_store_route(void) {
 181   route_t route = xbt_new0(s_route_t,1);
 182   route->link_list = link_list;
 183   xbt_assert1(generic_processing_units_exist(current_routing,src),"the \"%s\" processing units gateway does not exist",src);
 184   xbt_assert1(generic_processing_units_exist(current_routing,dst),"the \"%s\" processing units gateway does not exist",dst);
 185   xbt_assert1(current_routing->set_route,"no defined method \"set_route\" in \"%s\"",current_routing->name);
 186   (*(current_routing->set_route))(current_routing,src,dst,route);
 187   link_list = NULL;
 188   src = NULL;
 189   dst = NULL;
 190 }
 191
 192 /**
 193  * \brief Store the ASroute by calling the set_ASroute function of the current routing component
 194  */
 195 static void parse_E_ASroute_store_route(void) {
 196   route_extended_t e_route = xbt_new0(s_route_extended_t,1);
 197   e_route->generic_route.link_list = link_list;
 198   e_route->src_gateway = xbt_strdup(gw_src);
 199   e_route->dst_gateway = xbt_strdup(gw_dst);
 200   xbt_assert1(generic_autonomous_system_exist(current_routing,src),"the \"%s\" autonomous system does not exist",src);
 201   xbt_assert1(generic_autonomous_system_exist(current_routing,dst),"the \"%s\" autonomous system does not exist",dst);
 202   xbt_assert1(generic_processing_units_exist(current_routing,gw_src),"the \"%s\" processing units gateway does not exist",gw_src);
 203   xbt_assert1(generic_processing_units_exist(current_routing,gw_dst),"the \"%s\" processing units gateway does not exist",gw_dst);
 204   xbt_assert1(current_routing->set_ASroute,"no defined method \"set_ASroute\" in \"%s\"",current_routing->name);
 205   (*(current_routing->set_ASroute))(current_routing,src,dst,e_route);
 206   link_list = NULL;
 207   src = NULL;
 208   dst = NULL;
 209   gw_src = NULL;
 210   gw_dst = NULL;
 211 }
 212
 213 /**
 214  * \brief Store the bypass route by calling the set_bypassroute function of the current routing component
 215  */
 216 static void parse_E_bypassRoute_store_route(void) {
 217   route_extended_t e_route = xbt_new0(s_route_extended_t,1);
 218   e_route->generic_route.link_list = link_list;
 219   e_route->src_gateway = xbt_strdup(gw_src);
 220   e_route->dst_gateway = xbt_strdup(gw_dst);
 221   xbt_assert1(generic_autonomous_system_exist(current_routing,src),"the \"%s\" autonomous system does not exist",src);
 222   xbt_assert1(generic_autonomous_system_exist(current_routing,dst),"the \"%s\" autonomous system does not exist",dst);
 223   xbt_assert1(generic_processing_units_exist(current_routing,gw_src),"the \"%s\" processing units gateway does not exist",gw_src);
 224   xbt_assert1(generic_processing_units_exist(current_routing,gw_dst),"the \"%s\" processing units gateway does not exist",gw_dst);
 225   xbt_assert1(current_routing->set_bypassroute,"no defined method \"set_bypassroute\" in \"%s\"",current_routing->name);
 226   (*(current_routing->set_bypassroute))(current_routing,src,dst,e_route);
 227   link_list = NULL;
 228   src = NULL;
 229   dst = NULL;
 230   gw_src = NULL;
 231   gw_dst = NULL;
 232 }
 233
 234 /**
 235  * \brief Make a new routing component
 236  *
 237  * Detect the routing model type of the routing component, make the new structure and
 238  * set the parsing functions to allows parsing the part of the routing tree
 239  */
 240 static void parse_S_AS(void) {
 241   routing_component_t new_routing;
 242   model_type_t model = NULL;
 243   char* wanted = A_surfxml_AS_routing;
 244   int cpt;
 245   /* seach the routing model */
 246   for (cpt=0;routing_models[cpt].name;cpt++)
 247     if (!strcmp(wanted,routing_models[cpt].name))
 248           model = &routing_models[cpt];
 249   /* if its not exist, error */
 250   if( model == NULL ) {
 251     fprintf(stderr,"Routing model %s not found. Existing models:\n",wanted);
 252     for (cpt=0;routing_models[cpt].name;cpt++)
 253       if (!strcmp(wanted,routing_models[cpt].name))
 254         fprintf(stderr,"   %s: %s\n",routing_models[cpt].name,routing_models[cpt].desc);
 255     xbt_die(NULL);
 256   }
 257
 258   /* make a new routing component */
 259   new_routing = (routing_component_t)(*(model->create))();
 260   new_routing->routing = model;
 261   new_routing->hierarchy = SURF_ROUTING_NULL;
 262   new_routing->name = xbt_strdup(A_surfxml_AS_id);
 263   new_routing->routing_sons = xbt_dict_new();
 264   INFO2("Routing %s for AS %s",A_surfxml_AS_routing,A_surfxml_AS_id);
 265
 266   if( current_routing == NULL && global_routing->root == NULL ){
 267
 268     /* it is the first one */
 269     new_routing->routing_father = NULL;
 270     global_routing->root = new_routing;
 271
 272   } else if( current_routing != NULL && global_routing->root != NULL ) {
 273
 274     xbt_assert1(!xbt_dict_get_or_null(current_routing->routing_sons,A_surfxml_AS_id),
 275            "The AS \"%s\" already exist",A_surfxml_AS_id);
 276      /* it is a part of the tree */
 277     new_routing->routing_father = current_routing;
 278     /* set the father behavior */
 279     if( current_routing->hierarchy == SURF_ROUTING_NULL ) current_routing->hierarchy = SURF_ROUTING_RECURSIVE;
 280     /* add to the sons dictionary */
 281     xbt_dict_set(current_routing->routing_sons,A_surfxml_AS_id,(void*)new_routing,NULL);
 282     /* add to the father element list */
 283     (*(current_routing->set_autonomous_system))(current_routing,A_surfxml_AS_id);
 284     /* unload the prev parse rules */
 285     (*(current_routing->routing->unload))();
 286
 287   } else {
 288     THROW0(arg_error,0,"All defined components must be belong to a AS");
 289   }
 290   /* set the new parse rules */
 291   (*(new_routing->routing->load))();
 292   /* set the new current component of the tree */
 293   current_routing = new_routing;
 294 }
 295
 296 /**
 297  * \brief Finish the creation of a new routing component
 298  *
 299  * When you finish to read the routing component, other structures must be created.
 300  * the "end" method allow to do that for any routing model type
 301  */
 302 static void parse_E_AS(void) {
 303
 304   if( current_routing == NULL ) {
 305     THROW1(arg_error,0,"Close AS(%s), that never open",A_surfxml_AS_id);
 306   } else {
 307       xbt_assert1(!xbt_dict_get_or_null(global_routing->where_network_elements,current_routing->name),
 308           "The AS \"%s\" already exist",current_routing->name);
 309       xbt_dict_set(global_routing->where_network_elements,current_routing->name,current_routing->routing_father,NULL);
 310       (*(current_routing->routing->unload))();
 311       (*(current_routing->routing->end))();
 312       current_routing = current_routing->routing_father;
 313       if( current_routing != NULL )
 314         (*(current_routing->routing->load))();
 315   }
 316 }
 317
 318 /* Aux Business methods */
 319
 320 /**
 321  * \brief Get the AS father and the first elements of the chain
 322  *
 323  * \param src the source host name
 324  * \param dst the destination host name
 325  *
 326  * Get the common father of the to processing units, and the first different
 327  * father in the chain
 328  */
 329 static xbt_dynar_t elements_father(const char* src,const char* dst) {
 330
 331   xbt_assert0(src&&dst,"bad parameters for \"elements_father\" method");
 332
 333   xbt_dynar_t result = xbt_dynar_new(sizeof(char*), NULL);
 334
 335   routing_component_t src_as, dst_as;
 336   int index_src, index_dst, index_father_src, index_father_dst;
 337   xbt_dynar_t path_src = NULL;
 338   xbt_dynar_t path_dst = NULL;
 339   routing_component_t current = NULL;
 340   routing_component_t* current_src = NULL;
 341   routing_component_t* current_dst = NULL;
 342   routing_component_t* father = NULL;
 343
 344   /* (1) find the as where the src and dst are located */
 345   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
 346   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
 347   xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
 348
 349   /* (2) find the path to the root routing component */
 350   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
 351   current = src_as;
 352   while( current != NULL ) {
 353     xbt_dynar_push(path_src,&current);
 354     current = current->routing_father;
 355   }
 356   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
 357   current = dst_as;
 358   while( current != NULL ) {
 359     xbt_dynar_push(path_dst,&current);
 360     current = current->routing_father;
 361   }
 362
 363   /* (3) find the common father */
 364   index_src  = (path_src->used)-1;
 365   index_dst  = (path_dst->used)-1;
 366   current_src = xbt_dynar_get_ptr(path_src,index_src);
 367   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 368   while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
 369     current_src = xbt_dynar_get_ptr(path_src,index_src);
 370     current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 371     index_src--;
 372     index_dst--;
 373   }
 374   index_src++;
 375   index_dst++;
 376   current_src = xbt_dynar_get_ptr(path_src,index_src);
 377   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
 378
 379   /* (4) they are not in the same routing component, make the path */
 380   index_father_src = index_src+1;
 381   index_father_dst = index_dst+1;
 382
 383   if(*current_src==*current_dst)
 384     father = current_src;
 385   else
 386     father = xbt_dynar_get_ptr(path_src,index_father_src);
 387
 388   /* (5) result generation */
 389   xbt_dynar_push(result,father); /* first same the father of src and dst */
 390   xbt_dynar_push(result,current_src); /* second the first different father of src */
 391   xbt_dynar_push(result,current_dst); /* three  the first different father of dst */
 392
 393   xbt_dynar_free(&path_src);
 394   xbt_dynar_free(&path_dst);
 395
 396   return result;
 397 }
 398
 399 /* Global Business methods */
 400
 401 /**
 402  * \brief Recursive function for get_route
 403  *
 404  * \param src the source host name
 405  * \param dst the destination host name
 406  *
 407  * This fuction is call by "get_route". It allow to walk through the
 408  * routing components tree.
 409  */
 410 static route_extended_t _get_route(const char* src,const char* dst) {
 411
 412   void* link;
 413   unsigned int cpt=0;
 414
 415   DEBUG2("Solve route  \"%s\" to \"%s\"",src,dst);
 416
 417   xbt_assert0(src&&dst,"bad parameters for \"_get_route\" method");
 418
 419   route_extended_t e_route, e_route_cnt, e_route_src, e_route_dst;
 420
 421   xbt_dynar_t elem_father_list = elements_father(src,dst);
 422
 423   routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 424   routing_component_t src_father    = xbt_dynar_get_as(elem_father_list, 1, routing_component_t);
 425   routing_component_t dst_father    = xbt_dynar_get_as(elem_father_list, 2, routing_component_t);
 426
 427   e_route = xbt_new0(s_route_extended_t,1);
 428   e_route->src_gateway = NULL;
 429   e_route->dst_gateway = NULL;
 430   e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 431
 432   if(src_father==dst_father) { /* SURF_ROUTING_BASE */
 433
 434     if( strcmp(src,dst) ){
 435       e_route_cnt = (*(common_father->get_route))(common_father,src,dst);
 436       xbt_assert2(e_route_cnt,"no route between \"%s\" and \"%s\"",src,dst);
 437       xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 438         xbt_dynar_push(e_route->generic_route.link_list,&link);
 439       }
 440       xbt_dynar_free( &(e_route_cnt->generic_route.link_list) );
 441       xbt_free(e_route_cnt);
 442     }
 443
 444   } else { /* SURF_ROUTING_RECURSIVE */
 445
 446     route_extended_t e_route_bypass = (*(common_father->get_bypass_route))(common_father,src,dst);
 447
 448     if(e_route_bypass)
 449       e_route_cnt = e_route_bypass;
 450     else
 451       e_route_cnt = (*(common_father->get_route))(common_father,src_father->name,dst_father->name);
 452
 453     xbt_assert2(e_route_cnt,"no route between \"%s\" and \"%s\"",src_father->name,dst_father->name);
 454
 455     xbt_assert2( (e_route_cnt->src_gateway==NULL) == (e_route_cnt->dst_gateway==NULL) ,
 456       "bad gateway for route between \"%s\" and \"%s\"",src,dst);
 457
 458     if( src != e_route_cnt->src_gateway ) {
 459       e_route_src = _get_route(src,e_route_cnt->src_gateway);
 460       xbt_assert2(e_route_src,"no route between \"%s\" and \"%s\"",src,e_route_cnt->src_gateway);
 461       xbt_dynar_foreach(e_route_src->generic_route.link_list, cpt, link) {
 462         xbt_dynar_push(e_route->generic_route.link_list,&link);
 463       }
 464     }
 465
 466     xbt_dynar_foreach(e_route_cnt->generic_route.link_list, cpt, link) {
 467       xbt_dynar_push(e_route->generic_route.link_list,&link);
 468     }
 469
 470     if( e_route_cnt->dst_gateway != dst ) {
 471       e_route_dst = _get_route(e_route_cnt->dst_gateway,dst);
 472       xbt_assert2(e_route_dst,"no route between \"%s\" and \"%s\"",e_route_cnt->dst_gateway,dst);
 473       xbt_dynar_foreach(e_route_dst->generic_route.link_list, cpt, link) {
 474         xbt_dynar_push(e_route->generic_route.link_list,&link);
 475       }
 476     }
 477
 478     e_route->src_gateway = e_route_cnt->src_gateway;
 479     e_route->dst_gateway = e_route_cnt->dst_gateway;
 480
 481     xbt_dynar_free( &(e_route_src->generic_route.link_list) );
 482     xbt_free(e_route_src);
 483     xbt_dynar_free( &(e_route_cnt->generic_route.link_list) );
 484     xbt_free(e_route_cnt);
 485     xbt_dynar_free( &(e_route_dst->generic_route.link_list) );
 486     xbt_free(e_route_dst);
 487   }
 488
 489   xbt_dynar_free(&elem_father_list);
 490
 491   return e_route;
 492 }
 493
 494 /**
 495  * \brief Generic method: find a route between hosts
 496  *
 497  * \param src the source host name
 498  * \param dst the destination host name
 499  *
 500  * walk through the routing components tree and find a route between hosts
 501  * by calling the differents "get_route" functions in each routing component
 502  */
 503 static xbt_dynar_t get_route(const char* src,const char* dst) {
 504
 505   if(global_routing->last_route) xbt_dynar_free( &(global_routing->last_route) );
 506
 507   route_extended_t e_route;
 508   xbt_dynar_t elem_father_list = elements_father(src,dst);
 509   routing_component_t common_father = xbt_dynar_get_as(elem_father_list, 0, routing_component_t);
 510
 511   if(strcmp(src,dst))
 512     e_route = _get_route(src,dst);
 513   else
 514     e_route = (*(common_father->get_route))(common_father,src,dst);
 515
 516   xbt_assert2(e_route,"no route between \"%s\" and \"%s\"",src,dst);
 517   global_routing->last_route = e_route->generic_route.link_list;
 518
 519   xbt_free(e_route);
 520   xbt_dynar_free(&elem_father_list);
 521
 522   if( xbt_dynar_length(global_routing->last_route)==0 )
 523     return NULL;
 524   else
 525     return global_routing->last_route;
 526 }
 527
 528 /**
 529  * \brief Recursive function for finalize
 530  *
 531  * \param rc the source host name
 532  *
 533  * This fuction is call by "finalize". It allow to finalize the
 534  * AS or routing components. It delete all the structures.
 535  */
 536 static void _finalize(routing_component_t rc) {
 537   if(rc) {
 538     xbt_dict_cursor_t cursor = NULL;
 539     char *key;
 540     routing_component_t elem;
 541     xbt_dict_foreach(rc->routing_sons, cursor, key, elem) {
 542       _finalize(elem);
 543     }
 544     xbt_dict_t tmp_sons = rc->routing_sons;
 545     char* tmp_name = rc->name;
 546     xbt_dict_free(&tmp_sons);
 547     xbt_free(tmp_name);
 548     xbt_assert1(rc->finalize,"no defined method \"finalize\" in \"%s\"",current_routing->name);
 549     (*(rc->finalize))(rc);
 550   }
 551 }
 552
 553 /**
 554  * \brief Generic method: delete all the routing structures
 555  *
 556  * walk through the routing components tree and delete the structures
 557  * by calling the differents "finalize" functions in each routing component
 558  */
 559 static void finalize(void) {
 560   /* delete recursibly all the tree */
 561   _finalize(global_routing->root);
 562   /* delete "where" dict */
 563   xbt_dict_free(&(global_routing->where_network_elements));
 564   /* delete last_route */
 565   xbt_dynar_free(&(global_routing->last_route));
 566   /* delete global routing structure */
 567   xbt_free(global_routing);
 568 }
 569
 570 /**
 571  * \brief Generic method: create the global routing schema
 572  *
 573  * Make a global routing structure and set all the parsing functions.
 574  */
 575 void routing_model_create(size_t size_of_links, void* loopback) {
 576
 577   /* config the uniq global routing */
 578   global_routing = xbt_new0(s_routing_global_t,1);
 579   global_routing->where_network_elements = xbt_dict_new();
 580   global_routing->root = NULL;
 581   global_routing->get_route = get_route;
 582   global_routing->finalize = finalize;
 583   global_routing->loopback = loopback;
 584   global_routing->size_of_link = size_of_links;
 585   global_routing->last_route = xbt_dynar_new(size_of_links, NULL);
 586
 587   /* no current routing at moment */
 588   current_routing = NULL;
 589
 590   /* parse generic elements */
 591   surfxml_add_callback(STag_surfxml_host_cb_list, &parse_S_host);
 592   surfxml_add_callback(STag_surfxml_router_cb_list, &parse_S_router);
 593
 594   surfxml_add_callback(STag_surfxml_route_cb_list, &parse_S_route_new_and_endpoints);
 595   surfxml_add_callback(STag_surfxml_ASroute_cb_list, &parse_S_ASroute_new_and_endpoints);
 596   surfxml_add_callback(STag_surfxml_bypassRoute_cb_list, &parse_S_bypassRoute_new_and_endpoints);
 597
 598   surfxml_add_callback(ETag_surfxml_link_c_ctn_cb_list, &parse_E_link_c_ctn_new_elem);
 599
 600   surfxml_add_callback(ETag_surfxml_route_cb_list, &parse_E_route_store_route);
 601   surfxml_add_callback(ETag_surfxml_ASroute_cb_list, &parse_E_ASroute_store_route);
 602   surfxml_add_callback(ETag_surfxml_bypassRoute_cb_list, &parse_E_bypassRoute_store_route);
 603
 604   surfxml_add_callback(STag_surfxml_AS_cb_list, &parse_S_AS);
 605   surfxml_add_callback(ETag_surfxml_AS_cb_list, &parse_E_AS);
 606 }
 607
 608 /* ************************************************************************** */
 609 /* *************************** FULL ROUTING ********************************* */
 610
 611 #define TO_ROUTE_FULL(i,j) routing->routing_table[(i)+(j)*table_size]
 612
 613 /* Routing model structure */
 614
 615 typedef struct {
 616   s_routing_component_t generic_routing;
 617   xbt_dict_t parse_routes; /* store data during the parse process */
 618   xbt_dict_t to_index; /* char* -> network_element_t */
 619   xbt_dict_t bypassRoutes;
 620   route_extended_t *routing_table;
 621 } s_routing_component_full_t,*routing_component_full_t;
 622
 623 /* Business methods */
 624
 625 static route_extended_t full_get_route(routing_component_t rc, const char* src,const char* dst) {
 626   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
 627
 628   /* set utils vars */
 629   routing_component_full_t routing = (routing_component_full_t)rc;
 630   int table_size = xbt_dict_length(routing->to_index);
 631
 632   generic_src_dst_check(rc,src,dst);
 633   int *src_id = xbt_dict_get_or_null(routing->to_index,src);
 634   int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
 635   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
 636
 637   route_extended_t e_route = NULL;
 638   route_extended_t new_e_route = NULL;
 639   void* link;
 640   unsigned int cpt=0;
 641
 642   e_route = TO_ROUTE_FULL(*src_id,*dst_id);
 643
 644   if(e_route) {
 645     new_e_route = xbt_new0(s_route_extended_t,1);
 646     new_e_route->src_gateway = e_route->src_gateway;
 647     new_e_route->dst_gateway = e_route->dst_gateway;
 648     new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 649     xbt_dynar_foreach(e_route->generic_route.link_list, cpt, link) {
 650       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
 651     }
 652   }
 653   return new_e_route;
 654 }
 655
 656 static void full_finalize(routing_component_t rc) {
 657   routing_component_full_t routing = (routing_component_full_t)rc;
 658   int table_size = xbt_dict_length(routing->to_index);
 659   int i,j;
 660   if (routing) {
 661     /* Delete routing table */
 662     for (i=0;i<table_size;i++)
 663       for (j=0;j<table_size;j++)
 664         generic_free_extended_route(TO_ROUTE_FULL(i,j));
 665     xbt_free(routing->routing_table);
 666     /* Delete bypass dict */
 667     xbt_dict_free(&routing->bypassRoutes);
 668     /* Delete index dict */
 669     xbt_dict_free(&(routing->to_index));
 670     /* Delete structure */
 671     xbt_free(rc);
 672   }
 673 }
 674
 675 /* Creation routing model functions */
 676
 677 static void* model_full_create(void) {
 678   routing_component_full_t new_component =  xbt_new0(s_routing_component_full_t,1);
 679   new_component->generic_routing.set_processing_units = generic_set_processing_units;
 680   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
 681   new_component->generic_routing.set_route = generic_set_route;
 682   new_component->generic_routing.set_ASroute = generic_set_ASroute;
 683   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
 684   new_component->generic_routing.get_route = full_get_route;
 685   new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
 686   new_component->generic_routing.finalize = full_finalize;
 687   new_component->to_index = xbt_dict_new();
 688   new_component->bypassRoutes = xbt_dict_new();
 689   new_component->parse_routes = xbt_dict_new();
 690   return new_component;
 691 }
 692
 693 static void model_full_load(void) {
 694  /* use "surfxml_add_callback" to add a parse function call */
 695 }
 696
 697 static void model_full_unload(void) {
 698  /* use "surfxml_del_callback" to remove a parse function call */
 699 }
 700
 701 static void  model_full_end(void) {
 702
 703   char *key, *end;
 704   const char* sep = "#";
 705   int src_id, dst_id;
 706   unsigned int i, j;
 707   route_t route;
 708   route_extended_t e_route;
 709   void* data;
 710
 711   xbt_dict_cursor_t cursor = NULL;
 712   xbt_dynar_t keys = NULL;
 713
 714   /* set utils vars */
 715   routing_component_full_t routing = ((routing_component_full_t)current_routing);
 716   int table_size = xbt_dict_length(routing->to_index);
 717
 718   /* Create the routing table */
 719   routing->routing_table = xbt_new0(route_extended_t, table_size * table_size);
 720
 721   /* Put the routes in position */
 722   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 723     keys = xbt_str_split_str(key, sep);
 724     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
 725     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
 726     TO_ROUTE_FULL(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,1);
 727      xbt_dynar_free(&keys);
 728    }
 729
 730    /* delete the parse table */
 731   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 732     route = (route_t)data;
 733     xbt_dynar_free(&(route->link_list));
 734     xbt_free(data);
 735   }
 736
 737   /* delete parse dict */
 738   xbt_dict_free(&(routing->parse_routes));
 739
 740   /* Add the loopback if needed */
 741   if(current_routing->hierarchy == SURF_ROUTING_BASE) {
 742     for (i = 0; i < table_size; i++) {
 743       e_route = TO_ROUTE_FULL(i, i);
 744       if(!e_route) {
 745         e_route = xbt_new0(s_route_extended_t,1);
 746         e_route->src_gateway = NULL;
 747         e_route->dst_gateway = NULL;
 748         e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 749         xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
 750         TO_ROUTE_FULL(i, i) = e_route;
 751       }
 752     }
 753   }
 754
 755   /* Shrink the dynar routes (save unused slots) */
 756   for (i=0;i<table_size;i++)
 757     for (j=0;j<table_size;j++)
 758       if(TO_ROUTE_FULL(i,j))
 759         xbt_dynar_shrink(TO_ROUTE_FULL(i,j)->generic_route.link_list,0);
 760 }
 761
 762 /* ************************************************************************** */
 763 /* *************************** FLOYD ROUTING ******************************** */
 764
 765 #define TO_FLOYD_COST(i,j) cost_table[(i)+(j)*table_size]
 766 #define TO_FLOYD_PRED(i,j) (routing->predecessor_table)[(i)+(j)*table_size]
 767 #define TO_FLOYD_LINK(i,j) (routing->link_table)[(i)+(j)*table_size]
 768
 769 /* Routing model structure */
 770
 771 typedef struct {
 772   s_routing_component_t generic_routing;
 773   /* vars for calculate the floyd algorith. */
 774   int *predecessor_table;
 775   route_extended_t *link_table; /* char* -> int* */
 776   xbt_dict_t to_index;
 777   xbt_dict_t bypassRoutes;
 778   /* store data during the parse process */
 779   xbt_dict_t parse_routes;
 780 } s_routing_component_floyd_t,*routing_component_floyd_t;
 781
 782 /* Business methods */
 783
 784 static route_extended_t floyd_get_route(routing_component_t rc, const char* src,const char* dst) {
 785   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
 786
 787   /* set utils vars */
 788   routing_component_floyd_t routing = (routing_component_floyd_t) rc;
 789   int table_size = xbt_dict_length(routing->to_index);
 790
 791   generic_src_dst_check(rc,src,dst);
 792   int *src_id = xbt_dict_get_or_null(routing->to_index,src);
 793   int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
 794   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
 795
 796   /* create a result route */
 797   route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
 798   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 799   new_e_route->src_gateway = NULL;
 800   new_e_route->dst_gateway = NULL;
 801
 802   int first = 1;
 803   int pred = *dst_id;
 804   int prev_pred = 0;
 805   char *gw_src,*gw_dst, *prev_gw_src,*prev_gw_dst, *first_gw;
 806   unsigned int cpt;
 807   void* link;
 808   xbt_dynar_t links;
 809
 810   do {
 811     prev_pred = pred;
 812     pred = TO_FLOYD_PRED(*src_id, pred);
 813     if(pred == -1) /* if no pred in route -> no route to host */
 814       break;
 815     xbt_assert2(TO_FLOYD_LINK(pred,prev_pred),"Invalid link for the route between \"%s\" or \"%s\"", src, dst);
 816
 817     prev_gw_src = gw_src;
 818     prev_gw_dst = gw_dst;
 819
 820     route_extended_t e_route = TO_FLOYD_LINK(pred,prev_pred);
 821     gw_src = e_route->src_gateway;
 822     gw_dst = e_route->dst_gateway;
 823
 824     if(first) first_gw = gw_dst;
 825
 826     if(rc->hierarchy == SURF_ROUTING_RECURSIVE && !first && strcmp(gw_dst,prev_gw_src)) {
 827       xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
 828       xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
 829       links = e_route_as_to_as;
 830       int pos = 0;
 831       xbt_dynar_foreach(links, cpt, link) {
 832         xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
 833         pos++;
 834       }
 835     }
 836
 837     links = e_route->generic_route.link_list;
 838     xbt_dynar_foreach(links, cpt, link) {
 839       xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
 840     }
 841     first=0;
 842
 843   } while(pred != *src_id);
 844   xbt_assert4(pred != -1, "no route from host %d to %d (\"%s\" to \"%s\")", *src_id, *dst_id,src,dst);
 845
 846   if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
 847     new_e_route->src_gateway = gw_src;
 848     new_e_route->dst_gateway = first_gw;
 849   }
 850
 851   return new_e_route;
 852 }
 853
 854 static void floyd_finalize(routing_component_t rc) {
 855    routing_component_floyd_t routing = (routing_component_floyd_t)rc;
 856   int i,j,table_size;
 857   if (routing) {
 858     table_size = xbt_dict_length(routing->to_index);
 859     /* Delete link_table */
 860     for (i=0;i<table_size;i++)
 861       for (j=0;j<table_size;j++)
 862         generic_free_extended_route(TO_FLOYD_LINK(i,j));
 863     xbt_free(routing->link_table);
 864     /* Delete bypass dict */
 865     xbt_dict_free(&routing->bypassRoutes);
 866     /* Delete index dict */
 867     xbt_dict_free(&(routing->to_index));
 868     /* Delete dictionary index dict, predecessor and links table */
 869     xbt_free(routing->predecessor_table);
 870     /* Delete structure */
 871     xbt_free(rc);
 872   }
 873 }
 874
 875 static void* model_floyd_create(void) {
 876   routing_component_floyd_t new_component = xbt_new0(s_routing_component_floyd_t,1);
 877   new_component->generic_routing.set_processing_units = generic_set_processing_units;
 878   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
 879   new_component->generic_routing.set_route = generic_set_route;
 880   new_component->generic_routing.set_ASroute = generic_set_ASroute;
 881   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
 882   new_component->generic_routing.get_route = floyd_get_route;
 883   new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
 884   new_component->generic_routing.finalize = floyd_finalize;
 885   new_component->to_index = xbt_dict_new();
 886   new_component->bypassRoutes = xbt_dict_new();
 887   new_component->parse_routes = xbt_dict_new();
 888   return new_component;
 889 }
 890
 891 static void  model_floyd_load(void) {
 892  /* use "surfxml_add_callback" to add a parse function call */
 893 }
 894
 895 static void  model_floyd_unload(void) {
 896  /* use "surfxml_del_callback" to remove a parse function call */
 897 }
 898
 899 static void  model_floyd_end(void) {
 900
 901   routing_component_floyd_t routing = ((routing_component_floyd_t)current_routing);
 902   xbt_dict_cursor_t cursor = NULL;
 903   double * cost_table;
 904   char *key,*data, *end;
 905   const char *sep = "#";
 906   xbt_dynar_t keys;
 907   int src_id, dst_id;
 908   unsigned int i,j,a,b,c;
 909
 910   /* set the size of inicial table */
 911   int table_size = xbt_dict_length(routing->to_index);
 912
 913   /* Create Cost, Predecessor and Link tables */
 914   cost_table = xbt_new0(double, table_size*table_size); /* link cost from host to host */
 915   routing->predecessor_table = xbt_new0(int, table_size*table_size); /* predecessor host numbers */
 916   routing->link_table = xbt_new0(route_extended_t, table_size*table_size); /* actual link between src and dst */
 917
 918   /* Initialize costs and predecessors*/
 919   for(i = 0; i<table_size;i++)
 920     for(j = 0; j<table_size;j++) {
 921         TO_FLOYD_COST(i,j) = DBL_MAX;
 922         TO_FLOYD_PRED(i,j) = -1;
 923         TO_FLOYD_LINK(i,j) = NULL; /* fixed, missing in the previous version */
 924     }
 925
 926    /* Put the routes in position */
 927   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 928     keys = xbt_str_split_str(key, sep);
 929     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
 930     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
 931     TO_FLOYD_LINK(src_id,dst_id) = generic_new_extended_route(current_routing->hierarchy,data,0);
 932     TO_FLOYD_PRED(src_id,dst_id) = src_id;
 933     /* set link cost */
 934     TO_FLOYD_COST(src_id,dst_id) = ((TO_FLOYD_LINK(src_id,dst_id))->generic_route.link_list)->used; /* count of links, old model assume 1 */
 935     xbt_dynar_free(&keys);
 936   }
 937
 938   /* Add the loopback if needed */
 939   if(current_routing->hierarchy == SURF_ROUTING_BASE) {
 940     for (i = 0; i < table_size; i++) {
 941       route_extended_t e_route = TO_FLOYD_LINK(i, i);
 942       if(!e_route) {
 943         e_route = xbt_new0(s_route_extended_t,1);
 944         e_route->src_gateway = NULL;
 945         e_route->dst_gateway = NULL;
 946         e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
 947         xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
 948         TO_FLOYD_LINK(i,i) = e_route;
 949         TO_FLOYD_PRED(i,i) = i;
 950         TO_FLOYD_COST(i,i) = 1;
 951       }
 952     }
 953   }
 954   /* Calculate path costs */
 955   for(c=0;c<table_size;c++) {
 956     for(a=0;a<table_size;a++) {
 957       for(b=0;b<table_size;b++) {
 958         if(TO_FLOYD_COST(a,c) < DBL_MAX && TO_FLOYD_COST(c,b) < DBL_MAX) {
 959           if(TO_FLOYD_COST(a,b) == DBL_MAX ||
 960             (TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b) < TO_FLOYD_COST(a,b))) {
 961             TO_FLOYD_COST(a,b) = TO_FLOYD_COST(a,c)+TO_FLOYD_COST(c,b);
 962             TO_FLOYD_PRED(a,b) = TO_FLOYD_PRED(c,b);
 963           }
 964         }
 965       }
 966     }
 967   }
 968
 969    /* delete the parse table */
 970   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
 971     route_t route = (route_t)data;
 972     xbt_dynar_free(&(route->link_list));
 973     xbt_free(data);
 974   }
 975
 976   /* delete parse dict */
 977   xbt_dict_free(&(routing->parse_routes));
 978
 979   /* cleanup */
 980   xbt_free(cost_table);
 981 }
 982
 983 /* ************************************************************************** */
 984 /* ********** Dijkstra & Dijkstra Cached ROUTING **************************** */
 985
 986 typedef struct {
 987   s_routing_component_t generic_routing;
 988   xbt_dict_t to_index;
 989   xbt_dict_t bypassRoutes;
 990   xbt_graph_t route_graph;   /* xbt_graph */
 991   xbt_dict_t graph_node_map; /* map */
 992   xbt_dict_t route_cache;    /* use in cache mode */
 993   int cached;
 994   xbt_dict_t parse_routes;
 995 } s_routing_component_dijkstra_t,*routing_component_dijkstra_t;
 996
 997
 998 typedef struct graph_node_data {
 999   int id;
1000   int graph_id; /* used for caching internal graph id's */
1001 } s_graph_node_data_t, * graph_node_data_t;
1002
1003 typedef struct graph_node_map_element {
1004   xbt_node_t node;
1005 } s_graph_node_map_element_t, * graph_node_map_element_t;
1006
1007 typedef struct route_cache_element {
1008   int * pred_arr;
1009   int size;
1010 } s_route_cache_element_t, * route_cache_element_t;
1011
1012 /* Free functions */
1013
1014 static void route_cache_elem_free(void *e) {
1015   route_cache_element_t elm=(route_cache_element_t)e;
1016   if (elm) {
1017     xbt_free(elm->pred_arr);
1018     xbt_free(elm);
1019   }
1020 }
1021
1022 static void graph_node_map_elem_free(void *e) {
1023   graph_node_map_element_t elm = (graph_node_map_element_t)e;
1024   if(elm) {
1025     xbt_free(elm);
1026   }
1027 }
1028
1029 static void graph_edge_data_free(void *e) {
1030   route_extended_t e_route = (route_extended_t)e;
1031   if(e_route) {
1032     xbt_dynar_free(&(e_route->generic_route.link_list));
1033     if(e_route->src_gateway) xbt_free(e_route->src_gateway);
1034     if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
1035     xbt_free(e_route);
1036   }
1037 }
1038
1039 /* Utility functions */
1040
1041 static xbt_node_t route_graph_new_node(routing_component_dijkstra_t rc, int id, int graph_id) {
1042   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1043   xbt_node_t node = NULL;
1044   graph_node_data_t data = NULL;
1045   graph_node_map_element_t elm = NULL;
1046
1047   data = xbt_new0(struct graph_node_data, 1);
1048   data->id = id;
1049   data->graph_id = graph_id;
1050   node = xbt_graph_new_node(routing->route_graph, data);
1051
1052   elm = xbt_new0(struct graph_node_map_element, 1);
1053   elm->node = node;
1054   xbt_dict_set_ext(routing->graph_node_map, (char*)(&id), sizeof(int), (xbt_set_elm_t)elm, &graph_node_map_elem_free);
1055
1056   return node;
1057 }
1058
1059 static graph_node_map_element_t graph_node_map_search(routing_component_dijkstra_t rc, int id) {
1060   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1061   graph_node_map_element_t elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&id), sizeof(int));
1062   return elm;
1063 }
1064
1065 /* Parsing */
1066
1067 static void route_new_dijkstra(routing_component_dijkstra_t rc, int src_id, int dst_id, route_extended_t e_route ) {
1068   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1069
1070   xbt_node_t src = NULL;
1071   xbt_node_t dst = NULL;
1072   graph_node_map_element_t src_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&src_id), sizeof(int));
1073   graph_node_map_element_t dst_elm = (graph_node_map_element_t)xbt_dict_get_or_null_ext(routing->graph_node_map, (char*)(&dst_id), sizeof(int));
1074
1075   if(src_elm)
1076     src = src_elm->node;
1077
1078   if(dst_elm)
1079     dst = dst_elm->node;
1080
1081   /* add nodes if they don't exist in the graph */
1082   if(src_id == dst_id && src == NULL && dst == NULL) {
1083     src = route_graph_new_node(rc,src_id, -1);
1084     dst = src;
1085   } else {
1086     if(src == NULL) {
1087       src = route_graph_new_node(rc,src_id, -1);
1088     }
1089     if(dst == NULL) {
1090       dst = route_graph_new_node(rc,dst_id, -1);
1091     }
1092   }
1093
1094   /* add link as edge to graph */
1095   xbt_graph_new_edge(routing->route_graph, src, dst, e_route);
1096 }
1097
1098 static void add_loopback_dijkstra(routing_component_dijkstra_t rc) {
1099   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1100
1101   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1102
1103   xbt_node_t node = NULL;
1104   unsigned int cursor2;
1105   xbt_dynar_foreach(nodes, cursor2, node) {
1106     xbt_dynar_t out_edges = xbt_graph_node_get_outedges(node);
1107     xbt_edge_t edge = NULL;
1108     unsigned int cursor;
1109
1110     int found = 0;
1111     xbt_dynar_foreach(out_edges, cursor, edge) {
1112       xbt_node_t other_node = xbt_graph_edge_get_target(edge);
1113       if(other_node == node) {
1114         found = 1;
1115         break;
1116       }
1117     }
1118
1119     if(!found) {
1120       route_extended_t e_route = xbt_new0(s_route_extended_t,1);
1121       e_route->src_gateway = NULL;
1122       e_route->dst_gateway = NULL;
1123       e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1124       xbt_dynar_push(e_route->generic_route.link_list,&global_routing->loopback);
1125       xbt_graph_new_edge(routing->route_graph, node, node, e_route);
1126     }
1127   }
1128 }
1129
1130 /* Business methods */
1131
1132 static route_extended_t dijkstra_get_route(routing_component_t rc, const char* src,const char* dst) {
1133   xbt_assert1(rc&&src&&dst, "Invalid params for \"get_route\" function at AS \"%s\"",rc->name);
1134
1135   /* set utils vars */
1136   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1137
1138   generic_src_dst_check(rc,src,dst);
1139   int *src_id = xbt_dict_get_or_null(routing->to_index,src);
1140   int *dst_id = xbt_dict_get_or_null(routing->to_index,dst);
1141   xbt_assert2(src_id && dst_id, "Ask for route \"from\"(%s)  or \"to\"(%s) no found in the local table",src,dst);
1142
1143   /* create a result route */
1144   route_extended_t new_e_route = xbt_new0(s_route_extended_t,1);
1145   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1146   new_e_route->src_gateway = NULL;
1147   new_e_route->dst_gateway = NULL;
1148
1149   int *pred_arr = NULL;
1150   int src_node_id = 0;
1151   int dst_node_id = 0;
1152   int * nodeid = NULL;
1153   int v;
1154   route_extended_t e_route;
1155   int size = 0;
1156   unsigned int cpt;
1157   void* link;
1158   xbt_dynar_t links = NULL;
1159   route_cache_element_t elm = NULL;
1160   xbt_dynar_t nodes = xbt_graph_get_nodes(routing->route_graph);
1161
1162   /* Use the graph_node id mapping set to quickly find the nodes */
1163   graph_node_map_element_t src_elm = graph_node_map_search(routing,*src_id);
1164   graph_node_map_element_t dst_elm = graph_node_map_search(routing,*dst_id);
1165   xbt_assert2(src_elm != NULL && dst_elm != NULL, "src %d or dst %d does not exist", *src_id, *dst_id);
1166   src_node_id = ((graph_node_data_t)xbt_graph_node_get_data(src_elm->node))->graph_id;
1167   dst_node_id = ((graph_node_data_t)xbt_graph_node_get_data(dst_elm->node))->graph_id;
1168
1169   /* if the src and dst are the same */  /* fixed, missing in the previous version */
1170   if( src_node_id == dst_node_id ) {
1171
1172     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
1173     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
1174     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_s_v, node_e_v);
1175
1176     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1177
1178     e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1179
1180     links = e_route->generic_route.link_list;
1181     xbt_dynar_foreach(links, cpt, link) {
1182       xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1183     }
1184
1185     return new_e_route;
1186   }
1187
1188   if(routing->cached) {
1189     /*check if there is a cached predecessor list avail */
1190     elm = (route_cache_element_t)xbt_dict_get_or_null_ext(routing->route_cache, (char*)(&src_id), sizeof(int));
1191   }
1192
1193   if(elm) { /* cached mode and cache hit */
1194     pred_arr = elm->pred_arr;
1195   } else { /* not cached mode or cache miss */
1196     double * cost_arr = NULL;
1197     xbt_heap_t pqueue = NULL;
1198     int i = 0;
1199
1200     int nr_nodes = xbt_dynar_length(nodes);
1201     cost_arr = xbt_new0(double, nr_nodes); /* link cost from src to other hosts */
1202     pred_arr = xbt_new0(int, nr_nodes);    /* predecessors in path from src */
1203     pqueue = xbt_heap_new(nr_nodes, xbt_free);
1204
1205     /* initialize */
1206     cost_arr[src_node_id] = 0.0;
1207
1208     for(i = 0; i < nr_nodes; i++) {
1209       if(i != src_node_id) {
1210         cost_arr[i] = DBL_MAX;
1211       }
1212
1213       pred_arr[i] = 0;
1214
1215       /* initialize priority queue */
1216       nodeid = xbt_new0(int, 1);
1217       *nodeid = i;
1218       xbt_heap_push(pqueue, nodeid, cost_arr[i]);
1219
1220     }
1221
1222     /* apply dijkstra using the indexes from the graph's node array */
1223     while(xbt_heap_size(pqueue) > 0) {
1224       int * v_id = xbt_heap_pop(pqueue);
1225       xbt_node_t v_node = xbt_dynar_get_as(nodes, *v_id, xbt_node_t);
1226       xbt_dynar_t out_edges = xbt_graph_node_get_outedges(v_node);
1227       xbt_edge_t edge = NULL;
1228       unsigned int cursor;
1229
1230       xbt_dynar_foreach(out_edges, cursor, edge) {
1231         xbt_node_t u_node = xbt_graph_edge_get_target(edge);
1232         graph_node_data_t data = xbt_graph_node_get_data(u_node);
1233         int u_id = data->graph_id;
1234         route_extended_t tmp_e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1235         int cost_v_u = (tmp_e_route->generic_route.link_list)->used;  /* count of links, old model assume 1 */
1236
1237         if(cost_v_u + cost_arr[*v_id] < cost_arr[u_id]) {
1238           pred_arr[u_id] = *v_id;
1239           cost_arr[u_id] = cost_v_u + cost_arr[*v_id];
1240           nodeid = xbt_new0(int, 1);
1241           *nodeid = u_id;
1242           xbt_heap_push(pqueue, nodeid, cost_arr[u_id]);
1243         }
1244       }
1245
1246       /* free item popped from pqueue */
1247       xbt_free(v_id);
1248     }
1249
1250     xbt_free(cost_arr);
1251     xbt_heap_free(pqueue);
1252   }
1253
1254   /* compose route path with links */
1255   char *gw_src,*gw_dst, *prev_gw_src,*prev_gw_dst, *first_gw;
1256
1257   for(v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
1258     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
1259     xbt_node_t node_v = xbt_dynar_get_as(nodes, v, xbt_node_t);
1260     xbt_edge_t edge = xbt_graph_get_edge(routing->route_graph, node_pred_v, node_v);
1261
1262     xbt_assert2(edge != NULL, "no route between host %d and %d", *src_id, *dst_id);
1263
1264     prev_gw_src = gw_src;
1265     prev_gw_dst = gw_dst;
1266
1267     e_route = (route_extended_t)xbt_graph_edge_get_data(edge);
1268     gw_src = e_route->src_gateway;
1269     gw_dst = e_route->dst_gateway;
1270
1271     if(v==dst_node_id) first_gw = gw_dst;
1272
1273     if(rc->hierarchy == SURF_ROUTING_RECURSIVE && v!=dst_node_id && strcmp(gw_dst,prev_gw_src)) {
1274       xbt_dynar_t e_route_as_to_as = (*(global_routing->get_route))(gw_dst,prev_gw_src);
1275       xbt_assert2(e_route_as_to_as,"no route between \"%s\" and \"%s\"",gw_dst,prev_gw_src);
1276       links = e_route_as_to_as;
1277       int pos = 0;
1278       xbt_dynar_foreach(links, cpt, link) {
1279         xbt_dynar_insert_at(new_e_route->generic_route.link_list,pos,&link);
1280         pos++;
1281       }
1282     }
1283
1284     links = e_route->generic_route.link_list;
1285     xbt_dynar_foreach(links, cpt, link) {
1286       xbt_dynar_unshift(new_e_route->generic_route.link_list,&link);
1287     }
1288     size++;
1289   }
1290
1291   if(rc->hierarchy == SURF_ROUTING_RECURSIVE) {
1292     new_e_route->src_gateway = gw_src;
1293     new_e_route->dst_gateway = first_gw;
1294   }
1295
1296   if(routing->cached && elm == NULL) {
1297     /* add to predecessor list of the current src-host to cache */
1298     elm = xbt_new0(struct route_cache_element, 1);
1299     elm->pred_arr = pred_arr;
1300     elm->size = size;
1301     xbt_dict_set_ext(routing->route_cache, (char*)(&src_id), sizeof(int), (xbt_set_elm_t)elm, &route_cache_elem_free);
1302   }
1303
1304   if(!routing->cached)
1305     xbt_free(pred_arr);
1306
1307   return new_e_route;
1308 }
1309
1310 static void dijkstra_finalize(routing_component_t rc) {
1311   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) rc;
1312
1313   if (routing) {
1314     xbt_graph_free_graph(routing->route_graph, &xbt_free, &graph_edge_data_free, &xbt_free);
1315     xbt_dict_free(&routing->graph_node_map);
1316     if(routing->cached)
1317       xbt_dict_free(&routing->route_cache);
1318     /* Delete bypass dict */
1319     xbt_dict_free(&routing->bypassRoutes);
1320     /* Delete index dict */
1321     xbt_dict_free(&(routing->to_index));
1322     /* Delete structure */
1323     xbt_free(routing);
1324   }
1325 }
1326
1327 /* Creation routing model functions */
1328
1329 static void* model_dijkstra_both_create(int cached) {
1330   routing_component_dijkstra_t new_component = xbt_new0(s_routing_component_dijkstra_t,1);
1331   new_component->generic_routing.set_processing_units = generic_set_processing_units;
1332   new_component->generic_routing.set_autonomous_system = generic_set_autonomous_system;
1333   new_component->generic_routing.set_route = generic_set_route;
1334   new_component->generic_routing.set_ASroute = generic_set_ASroute;
1335   new_component->generic_routing.set_bypassroute = generic_set_bypassroute;
1336   new_component->generic_routing.get_route = dijkstra_get_route;
1337   new_component->generic_routing.get_bypass_route = generic_get_bypassroute;
1338   new_component->generic_routing.finalize = dijkstra_finalize;
1339   new_component->cached = cached;
1340   new_component->to_index = xbt_dict_new();
1341   new_component->bypassRoutes = xbt_dict_new();
1342   new_component->parse_routes = xbt_dict_new();
1343   return new_component;
1344 }
1345
1346 static void* model_dijkstra_create(void) {
1347   return model_dijkstra_both_create(0);
1348 }
1349
1350 static void* model_dijkstracache_create(void) {
1351   return model_dijkstra_both_create(1);
1352 }
1353
1354 static void  model_dijkstra_both_load(void) {
1355  /* use "surfxml_add_callback" to add a parse function call */
1356 }
1357
1358 static void  model_dijkstra_both_unload(void) {
1359  /* use "surfxml_del_callback" to remove a parse function call */
1360 }
1361
1362 static void  model_dijkstra_both_end(void) {
1363   routing_component_dijkstra_t routing = (routing_component_dijkstra_t) current_routing;
1364    xbt_dict_cursor_t cursor = NULL;
1365    char *key, *data, *end;
1366    const char *sep = "#";
1367    xbt_dynar_t keys;
1368   xbt_node_t node = NULL;
1369   unsigned int cursor2;
1370   xbt_dynar_t nodes = NULL;
1371   int src_id, dst_id;
1372   route_t route;
1373
1374   /* Create the topology graph */
1375   routing->route_graph = xbt_graph_new_graph(1, NULL);
1376   routing->graph_node_map = xbt_dict_new();
1377
1378   if(routing->cached)
1379     routing->route_cache = xbt_dict_new();
1380
1381   /* Put the routes in position */
1382   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1383     keys = xbt_str_split_str(key, sep);
1384     src_id = strtol(xbt_dynar_get_as(keys, 0, char *), &end, 10);
1385     dst_id = strtol(xbt_dynar_get_as(keys, 1, char *), &end, 10);
1386     route_extended_t e_route = generic_new_extended_route(current_routing->hierarchy,data,0);
1387     route_new_dijkstra(routing,src_id,dst_id,e_route);
1388     xbt_dynar_free(&keys);
1389   }
1390
1391   /* delete the parse table */
1392   xbt_dict_foreach(routing->parse_routes, cursor, key, data) {
1393     route = (route_t)data;
1394     xbt_dynar_free(&(route->link_list));
1395     xbt_free(data);
1396   }
1397
1398   /* delete parse dict */
1399   xbt_dict_free(&(routing->parse_routes));
1400
1401   /* Add the loopback if needed */
1402   if(current_routing->hierarchy == SURF_ROUTING_BASE)
1403     add_loopback_dijkstra(routing);
1404
1405   /* initialize graph indexes in nodes after graph has been built */
1406   nodes = xbt_graph_get_nodes(routing->route_graph);
1407
1408   xbt_dynar_foreach(nodes, cursor2, node) {
1409     graph_node_data_t data = xbt_graph_node_get_data(node);
1410     data->graph_id = cursor2;
1411   }
1412
1413 }
1414
1415 /* ************************************************************************** */
1416 /* ******************************* NO ROUTING ******************************* */
1417
1418 /* Routing model structure */
1419 typedef struct {
1420   s_routing_component_t generic_routing;
1421 } s_routing_component_none_t,*routing_component_none_t;
1422
1423 /* Business methods */
1424 static route_extended_t none_get_route(routing_component_t rc, const char* src,const char* dst){
1425   return NULL;
1426 }
1427 static route_extended_t none_get_bypass_route(routing_component_t rc, const char* src,const char* dst){
1428   return NULL;
1429 }
1430 static void none_finalize(routing_component_t rc) {
1431   xbt_free(rc);
1432 }
1433
1434 static void none_set_processing_units(routing_component_t rc, const char* name) {}
1435 static void none_set_autonomous_system(routing_component_t rc, const char* name) {}
1436
1437 /* Creation routing model functions */
1438 static void* model_none_create(void) {
1439   routing_component_none_t new_component =  xbt_new0(s_routing_component_none_t,1);
1440   new_component->generic_routing.set_processing_units = none_set_processing_units;
1441   new_component->generic_routing.set_autonomous_system = none_set_autonomous_system;
1442   new_component->generic_routing.set_route = NULL;
1443   new_component->generic_routing.set_ASroute = NULL;
1444   new_component->generic_routing.set_bypassroute = NULL;
1445   new_component->generic_routing.get_route = none_get_route;
1446   new_component->generic_routing.get_bypass_route = none_get_bypass_route;
1447   new_component->generic_routing.finalize = none_finalize;
1448   return new_component;
1449 }
1450
1451 static void  model_none_load(void) {}
1452 static void  model_none_unload(void) {}
1453 static void  model_none_end(void) {}
1454
1455 /* ************************************************** */
1456 /* ********** PATERN FOR NEW ROUTING **************** */
1457
1458 /* The minimal configuration of a new routing model need the next functions,
1459  * also you need to set at the start of the file, the new model in the model
1460  * list. Remember keep the null ending of the list.
1461  */
1462 /*** Routing model structure ***/
1463 typedef struct {
1464   s_routing_component_t generic_routing;
1465   /* things that your routing model need */
1466 } s_routing_component_NEW_t,*routing_component_NEW_t;
1467
1468 /*** Parse routing model functions ***/
1469 static void model_NEW_set_processing_units(routing_component_t rc, const char* name) {}
1470 static void model_NEW_set_autonomous_system(routing_component_t rc, const char* name) {}
1471 static void model_NEW_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {}
1472 static void model_NEW_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t route) {}
1473 static void model_NEW_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {}
1474
1475 /*** Business methods ***/
1476 static route_extended_t NEW_get_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
1477 static route_extended_t NEW_get_bypass_route(routing_component_t rc, const char* src,const char* dst) {return NULL;}
1478 static void NEW_finalize(routing_component_t rc) {}
1479
1480 /*** Creation routing model functions ***/
1481 static void* model_NEW_create(void) {
1482   routing_component_full_t new_component =  xbt_new0(s_routing_component_full_t,1);
1483   new_component->generic_routing.set_processing_units = model_NEW_set_processing_units;
1484   new_component->generic_routing.set_autonomous_system = model_NEW_set_autonomous_system;
1485   new_component->generic_routing.set_route = model_NEW_set_route;
1486   new_component->generic_routing.set_ASroute = model_NEW_set_ASroute;
1487   new_component->generic_routing.set_bypassroute = model_NEW_set_bypassroute;
1488   new_component->generic_routing.get_route = NEW_get_route;
1489   new_component->generic_routing.get_bypass_route = NEW_get_bypass_route;
1490   new_component->generic_routing.finalize = NEW_finalize;
1491   /* initialization of internal structures */
1492   return new_component;
1493 } /* mandatory */
1494 static void  model_NEW_load(void) {}   /* mandatory */
1495 static void  model_NEW_unload(void) {} /* mandatory */
1496 static void  model_NEW_end(void) {}    /* mandatory */
1497
1498 /* ************************************************************************** */
1499 /* ************************* GENERIC PARSE FUNCTIONS ************************ */
1500
1501 static void generic_set_processing_units(routing_component_t rc, const char* name) {
1502   DEBUG1("Load process unit \"%s\"",name);
1503   model_type_t modeltype = rc->routing;
1504   int *id = xbt_new0(int,1);
1505   xbt_dict_t _to_index;
1506   if(modeltype==&routing_models[SURF_MODEL_FULL])
1507     _to_index = ((routing_component_full_t)rc)->to_index;
1508
1509   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1510     _to_index = ((routing_component_floyd_t)rc)->to_index;
1511
1512   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1513           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1514     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1515
1516   else xbt_die("\"generic_set_processing_units\" not support");
1517   *id = xbt_dict_length(_to_index);
1518   xbt_dict_set(_to_index,name,id,xbt_free);
1519 }
1520
1521 static void generic_set_autonomous_system(routing_component_t rc, const char* name) {
1522   DEBUG1("Load Autonomous system \"%s\"",name);
1523   model_type_t modeltype = rc->routing;
1524   int *id = xbt_new0(int,1);
1525   xbt_dict_t _to_index;
1526   if(modeltype==&routing_models[SURF_MODEL_FULL])
1527     _to_index = ((routing_component_full_t)rc)->to_index;
1528
1529   else if(modeltype==&routing_models[SURF_MODEL_FLOYD])
1530     _to_index = ((routing_component_floyd_t)rc)->to_index;
1531
1532   else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1533           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE])
1534     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1535
1536   else xbt_die("\"generic_set_autonomous_system\" not support");
1537   *id = xbt_dict_length(_to_index);
1538   xbt_dict_set(_to_index,name,id,xbt_free);
1539 }
1540
1541 static void generic_set_route(routing_component_t rc, const char* src, const char* dst, route_t route) {
1542   DEBUG2("Load Route from \"%s\" to \"%s\"",src,dst);
1543   model_type_t modeltype = rc->routing;
1544   xbt_dict_t _parse_routes;
1545   xbt_dict_t _to_index;
1546   char *route_name;
1547   int *src_id, *dst_id;
1548
1549   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1550     _parse_routes = ((routing_component_full_t)rc)->parse_routes;
1551     _to_index = ((routing_component_full_t)rc)->to_index;
1552
1553   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1554     _parse_routes = ((routing_component_floyd_t)rc)->parse_routes;
1555     _to_index = ((routing_component_floyd_t)rc)->to_index;
1556
1557   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1558           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1559     _parse_routes = ((routing_component_dijkstra_t)rc)->parse_routes;
1560     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1561
1562   } else xbt_die("\"generic_set_route\" not support");
1563
1564   src_id = xbt_dict_get_or_null(_to_index, src);
1565   dst_id = xbt_dict_get_or_null(_to_index, dst);
1566
1567   xbt_assert2(src_id&&dst_id,"Network elements %s or %s not found", src, dst);
1568   route_name = bprintf("%d#%d",*src_id,*dst_id);
1569
1570   xbt_assert2(xbt_dynar_length(route->link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1571   xbt_assert2(!xbt_dict_get_or_null(_parse_routes,route_name),
1572     "The route between \"%s\" and \"%s\" already exist",src,dst);
1573
1574   xbt_dict_set(_parse_routes, route_name, route, NULL);
1575   xbt_free(route_name);
1576 }
1577
1578 static void generic_set_ASroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1579   DEBUG4("Load ASroute from \"%s(%s)\" to \"%s(%s)\"",src,e_route->src_gateway,dst,e_route->dst_gateway);
1580   model_type_t modeltype = rc->routing;
1581   xbt_dict_t _parse_routes;
1582   xbt_dict_t _to_index;
1583   char *route_name;
1584   int *src_id, *dst_id;
1585
1586   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1587     _parse_routes = ((routing_component_full_t)rc)->parse_routes;
1588     _to_index = ((routing_component_full_t)rc)->to_index;
1589
1590   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1591     _parse_routes = ((routing_component_floyd_t)rc)->parse_routes;
1592     _to_index = ((routing_component_floyd_t)rc)->to_index;
1593
1594   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1595           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1596     _parse_routes = ((routing_component_dijkstra_t)rc)->parse_routes;
1597     _to_index = ((routing_component_dijkstra_t)rc)->to_index;
1598
1599   } else xbt_die("\"generic_set_route\" not support");
1600
1601   src_id = xbt_dict_get_or_null(_to_index, src);
1602   dst_id = xbt_dict_get_or_null(_to_index, dst);
1603
1604   xbt_assert2(src_id&&dst_id,"Network elements %s or %s not found", src, dst);
1605   route_name = bprintf("%d#%d",*src_id,*dst_id);
1606
1607   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1608   xbt_assert4(!xbt_dict_get_or_null(_parse_routes,route_name),
1609     "The route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
1610
1611   xbt_dict_set(_parse_routes, route_name, e_route, NULL);
1612   xbt_free(route_name);
1613 }
1614
1615 static void generic_set_bypassroute(routing_component_t rc, const char* src, const char* dst, route_extended_t e_route) {
1616   DEBUG2("Load bypassRoute from \"%s\" to \"%s\"",src,dst);
1617   model_type_t modeltype = rc->routing;
1618   xbt_dict_t dict_bypassRoutes;
1619   char *route_name;
1620   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1621     dict_bypassRoutes = ((routing_component_full_t)rc)->bypassRoutes;
1622   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1623     dict_bypassRoutes = ((routing_component_floyd_t)rc)->bypassRoutes;
1624   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1625           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1626     dict_bypassRoutes = ((routing_component_dijkstra_t)rc)->bypassRoutes;
1627   } else xbt_die("\"generic_set_bypassroute\" not support");
1628   route_name = bprintf("%s#%s",src,dst);
1629   xbt_assert2(xbt_dynar_length(e_route->generic_route.link_list)>0, "Invalid count of links, must be greater than zero (%s,%s)",src,dst);
1630   xbt_assert4(!xbt_dict_get_or_null(dict_bypassRoutes,route_name),
1631     "The bypass route between \"%s\"(\"%s\") and \"%s\"(\"%s\") already exist",src,e_route->src_gateway,dst,e_route->dst_gateway);
1632
1633   route_extended_t new_e_route = generic_new_extended_route(SURF_ROUTING_RECURSIVE,e_route,0);
1634   xbt_dynar_free( &(e_route->generic_route.link_list) );
1635   xbt_free(e_route);
1636
1637   xbt_dict_set(dict_bypassRoutes, route_name, new_e_route, (void(*)(void*))generic_free_extended_route );
1638   xbt_free(route_name);
1639 }
1640
1641 /* ************************************************************************** */
1642 /* *********************** GENERIC BUSINESS METHODS ************************* */
1643
1644 static route_extended_t generic_get_bypassroute(routing_component_t rc, const char* src, const char* dst) {
1645   model_type_t modeltype = rc->routing;
1646   xbt_dict_t dict_bypassRoutes;
1647
1648   if(modeltype==&routing_models[SURF_MODEL_FULL]) {
1649     dict_bypassRoutes = ((routing_component_full_t)rc)->bypassRoutes;
1650   } else if(modeltype==&routing_models[SURF_MODEL_FLOYD]) {
1651     dict_bypassRoutes = ((routing_component_floyd_t)rc)->bypassRoutes;
1652   } else if(modeltype==&routing_models[SURF_MODEL_DIJKSTRA]||
1653           modeltype==&routing_models[SURF_MODEL_DIJKSTRACACHE]) {
1654     dict_bypassRoutes = ((routing_component_dijkstra_t)rc)->bypassRoutes;
1655   } else xbt_die("\"generic_set_bypassroute\" not support");
1656
1657
1658   routing_component_t src_as, dst_as;
1659   int index_src, index_dst;
1660   xbt_dynar_t path_src = NULL;
1661   xbt_dynar_t path_dst = NULL;
1662   routing_component_t current = NULL;
1663   routing_component_t* current_src = NULL;
1664   routing_component_t* current_dst = NULL;
1665
1666   /* (1) find the as where the src and dst are located */
1667   src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
1668   dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
1669   xbt_assert2(src_as&&dst_as, "Ask for route \"from\"(%s) or \"to\"(%s) no found",src,dst);
1670
1671   /* (2) find the path to the root routing component */
1672   path_src = xbt_dynar_new(sizeof(routing_component_t), NULL);
1673   current = src_as;
1674   while( current != NULL ) {
1675     xbt_dynar_push(path_src,&current);
1676     current = current->routing_father;
1677   }
1678   path_dst = xbt_dynar_new(sizeof(routing_component_t), NULL);
1679   current = dst_as;
1680   while( current != NULL ) {
1681     xbt_dynar_push(path_dst,&current);
1682     current = current->routing_father;
1683   }
1684
1685   /* (3) find the common father */
1686   index_src  = (path_src->used)-1;
1687   index_dst  = (path_dst->used)-1;
1688   current_src = xbt_dynar_get_ptr(path_src,index_src);
1689   current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1690   while( index_src >= 0 && index_dst >= 0 && *current_src == *current_dst ) {
1691     routing_component_t *tmp_src,*tmp_dst;
1692     tmp_src = xbt_dynar_pop_ptr(path_src);
1693     tmp_dst = xbt_dynar_pop_ptr(path_dst);
1694     index_src--;
1695     index_dst--;
1696     current_src = xbt_dynar_get_ptr(path_src,index_src);
1697     current_dst = xbt_dynar_get_ptr(path_dst,index_dst);
1698   }
1699
1700   int max_index_src = (path_src->used)-1;
1701   int max_index_dst = (path_dst->used)-1;
1702
1703   int max_index = max(max_index_src,max_index_dst);
1704   int i, max;
1705
1706  route_extended_t e_route_bypass = NULL;
1707
1708   for( max=0;max<=max_index;max++)
1709   {
1710     for(i=0;i<max;i++)
1711     {
1712       if( i <= max_index_src  && max <= max_index_dst ) {
1713         char* route_name = bprintf("%s#%s",
1714                                    (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,i)))->name,
1715                                    (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,max)))->name);
1716         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
1717         xbt_free(route_name);
1718       }
1719       if( e_route_bypass ) break;
1720       if( max <= max_index_src  && i <= max_index_dst ) {
1721         char* route_name = bprintf("%s#%s",
1722                                    (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,max)))->name,
1723                                    (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,i)))->name);
1724         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
1725         xbt_free(route_name);
1726       }
1727       if( e_route_bypass ) break;
1728     }
1729
1730     if( e_route_bypass ) break;
1731
1732     if( max <= max_index_src  && max <= max_index_dst ) {
1733         char* route_name = bprintf("%s#%s",
1734                                    (*(routing_component_t*)(xbt_dynar_get_ptr(path_src,max)))->name,
1735                                    (*(routing_component_t*)(xbt_dynar_get_ptr(path_dst,max)))->name);
1736         e_route_bypass = xbt_dict_get_or_null(dict_bypassRoutes,route_name);
1737         xbt_free(route_name);
1738       }
1739     if( e_route_bypass ) break;
1740   }
1741
1742   xbt_dynar_free(&path_src);
1743   xbt_dynar_free(&path_dst);
1744
1745   route_extended_t new_e_route = NULL;
1746
1747   if(e_route_bypass) {
1748     void* link;
1749     unsigned int cpt=0;
1750     new_e_route = xbt_new0(s_route_extended_t,1);
1751     new_e_route->src_gateway = e_route_bypass->src_gateway;
1752     new_e_route->dst_gateway = e_route_bypass->dst_gateway;
1753     new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1754     xbt_dynar_foreach(e_route_bypass->generic_route.link_list, cpt, link) {
1755       xbt_dynar_push(new_e_route->generic_route.link_list,&link);
1756     }
1757   }
1758
1759   return new_e_route;
1760 }
1761
1762 /* ************************************************************************** */
1763 /* ************************* GENERIC AUX FUNCTIONS ************************** */
1764
1765 static route_extended_t generic_new_extended_route(e_surf_routing_hierarchy_t hierarchy, void* data, int order) {
1766
1767   char *link_name;
1768   route_extended_t e_route, new_e_route;
1769   route_t route;
1770   unsigned int cpt;
1771   xbt_dynar_t links, links_id;
1772
1773   new_e_route = xbt_new0(s_route_extended_t,1);
1774   new_e_route->generic_route.link_list = xbt_dynar_new(global_routing->size_of_link,NULL);
1775   new_e_route->src_gateway = NULL;
1776   new_e_route->dst_gateway = NULL;
1777
1778   xbt_assert0(hierarchy == SURF_ROUTING_BASE || hierarchy == SURF_ROUTING_RECURSIVE,
1779       "the hierarchy type is not defined");
1780
1781   if(hierarchy == SURF_ROUTING_BASE ) {
1782
1783     route = (route_t)data;
1784     links = route->link_list;
1785
1786   } else if(hierarchy == SURF_ROUTING_RECURSIVE ) {
1787
1788     e_route = (route_extended_t)data;
1789     xbt_assert0(e_route->src_gateway&&e_route->dst_gateway,"bad gateway, is null");
1790     links = e_route->generic_route.link_list;
1791
1792     /* remeber not erase the gateway names */
1793     new_e_route->src_gateway = e_route->src_gateway;
1794     new_e_route->dst_gateway = e_route->dst_gateway;
1795   }
1796
1797   links_id = new_e_route->generic_route.link_list;
1798
1799   xbt_dynar_foreach(links, cpt, link_name) {
1800
1801     void* link = xbt_dict_get_or_null(surf_network_model->resource_set, link_name);
1802     if (link)
1803     {
1804       if( order )
1805         xbt_dynar_push(links_id,&link);
1806       else
1807         xbt_dynar_unshift(links_id,&link);
1808     }
1809     else
1810       THROW1(mismatch_error,0,"Link %s not found", link_name);
1811   }
1812
1813   return new_e_route;
1814 }
1815
1816 static void generic_free_extended_route(route_extended_t e_route) {
1817   if(e_route) {
1818     xbt_dynar_free(&(e_route->generic_route.link_list));
1819     if(e_route->src_gateway) xbt_free(e_route->src_gateway);
1820     if(e_route->dst_gateway) xbt_free(e_route->dst_gateway);
1821     xbt_free(e_route);
1822   }
1823 }
1824
1825 static routing_component_t generic_as_exist(routing_component_t find_from, routing_component_t to_find) {
1826   xbt_dict_cursor_t cursor = NULL;
1827   char *key;
1828   int found=0;
1829   routing_component_t elem;
1830   xbt_dict_foreach(find_from->routing_sons, cursor, key, elem) {
1831     if( to_find == elem || generic_as_exist(elem,to_find) ){
1832       found=1;
1833       break;
1834     }
1835   }
1836   if(found) return to_find;
1837   return NULL;
1838 }
1839
1840 static routing_component_t generic_autonomous_system_exist(routing_component_t rc, char* element) {
1841   routing_component_t element_as, result, elem;
1842   xbt_dict_cursor_t cursor = NULL;
1843   char *key;
1844   element_as = xbt_dict_get_or_null(global_routing->where_network_elements,element);
1845   result = ((routing_component_t)-1);
1846   if(element_as!=rc)
1847     result = generic_as_exist(rc,element_as);
1848
1849   if(result)
1850   {
1851     xbt_dict_foreach(element_as->routing_sons, cursor, key, elem) {
1852       if( !strcmp(elem->name,element) ) return element_as;
1853     }
1854   }
1855   return NULL;
1856 }
1857
1858 static routing_component_t generic_processing_units_exist(routing_component_t rc, char* element) {
1859   routing_component_t element_as;
1860   element_as = xbt_dict_get_or_null(global_routing->where_network_elements,element);
1861   if(element_as==rc) return element_as;
1862   return generic_as_exist(rc,element_as);
1863 }
1864
1865 static void generic_src_dst_check(routing_component_t rc, const char* src, const char* dst) {
1866
1867   routing_component_t src_as = xbt_dict_get_or_null(global_routing->where_network_elements,src);
1868   routing_component_t dst_as = xbt_dict_get_or_null(global_routing->where_network_elements,dst);
1869
1870   xbt_assert3(src_as != NULL && dst_as  != NULL,
1871       "Ask for route \"from\"(%s) or \"to\"(%s) no found at AS \"%s\"",src,dst,rc->name);
1872   xbt_assert4(src_as == dst_as,
1873       "The src(%s in %s) and dst(%s in %s) are in differents AS",src,src_as->name,dst,dst_as->name);
1874   xbt_assert2(rc == dst_as,
1875       "The routing component of src and dst is not the same as the network elements belong (%s==%s)",rc->name,dst_as->name);
1876 }