[Olsr-cvs] olsrd-current/src lq_route.c,1.35,1.36

[Thomas Lopatic]

Update of /cvsroot/olsrd/olsrd-current/src
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv8366/src

Modified Files:
	lq_route.c 
Log Message:
Use a sorted vertex list so that we are deterministic in case we have two
or more equally good routes.


Index: lq_route.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.c,v
retrieving revision 1.35
retrieving revision 1.36
diff -C2 -d -r1.35 -r1.36
*** lq_route.c	25 May 2005 16:33:25 -0000	1.35
--- lq_route.c	23 Oct 2005 20:11:50 -0000	1.36
***************
*** 91,96 ****
  static int (*avl_comp)(void *, void *);
  
! static void add_vertex(struct avl_tree *vertex_tree, struct list *vertex_list,
!                        union olsr_ip_addr *addr, float path_etx)
  {
    struct avl_node *node;
--- 91,96 ----
  static int (*avl_comp)(void *, void *);
  
! static void add_vertex(struct avl_tree *vertex_tree, union olsr_ip_addr *addr,
!                        float path_etx)
  {
    struct avl_node *node;
***************
*** 110,115 ****
      vert->tree_node.key = &vert->addr;
  
-     vert->node.data = vert;
- 
      COPY_IP(&vert->addr, addr);
      
--- 110,113 ----
***************
*** 122,130 ****
  
      avl_insert(vertex_tree, &vert->tree_node);
-     list_add_tail(vertex_list, &vert->node);
    }
  }
  
! static void add_edge(struct avl_tree *vertex_tree, struct list *vertex_list,
                       union olsr_ip_addr *src, union olsr_ip_addr *dst,
                       float etx)
--- 120,127 ----
  
      avl_insert(vertex_tree, &vert->tree_node);
    }
  }
  
! static void add_edge(struct avl_tree *vertex_tree,
                       union olsr_ip_addr *src, union olsr_ip_addr *dst,
                       float etx)
***************
*** 198,201 ****
--- 195,238 ----
  }
  
+ static void create_vertex_list_rec(struct list *vertex_list,
+                                    struct avl_node *node,
+                                    int (*comp)(void *, void *))
+ {
+   struct dijk_vertex *vert = node->data;
+ 
+   if (node->left != NULL)
+     create_vertex_list_rec(vertex_list, node->left, comp);
+ 
+   // add the vertex to the list, if it's not us
+ 
+   if ((*comp)(&main_addr, node->key) != 0)
+   {
+     vert->node.data = vert;
+     list_add_tail(vertex_list, &vert->node);
+   }
+ 
+   if (node->right != NULL)
+     create_vertex_list_rec(vertex_list, node->right, comp);
+ }
+ 
+ static void create_vertex_list(struct avl_tree *vertex_tree,
+                                struct list *vertex_list)
+ {
+   struct avl_node *node;
+   struct dijk_vertex *vert;
+ 
+   // make ourselves the first vertex in the list
+ 
+   node = avl_find(vertex_tree, &main_addr);
+   vert = node->data;
+ 
+   vert->node.data = vert;
+   list_add_tail(vertex_list, &vert->node);
+ 
+   // add the remaining vertices ordered by their main address
+ 
+   create_vertex_list_rec(vertex_list, vertex_tree->root, vertex_tree->comp);
+ }
+ 
  static void free_everything(struct list *vertex_list)
  {
***************
*** 343,349 ****
    list_init(&vertex_list);
  
!   // add ourselves to the vertex list
  
!   add_vertex(&vertex_tree, &vertex_list, &main_addr, 0.0);
  
    // add our neighbours
--- 380,386 ----
    list_init(&vertex_list);
  
!   // add ourselves to the vertex tree
  
!   add_vertex(&vertex_tree, &main_addr, 0.0);
  
    // add our neighbours
***************
*** 353,358 ****
           neigh = neigh->next)
        if (neigh->status == SYM)
!         add_vertex(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
!                    INFINITE_ETX);
  
    // add our two-hop neighbours
--- 390,394 ----
           neigh = neigh->next)
        if (neigh->status == SYM)
!         add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
  
    // add our two-hop neighbours
***************
*** 362,367 ****
           neigh2 != &two_hop_neighbortable[i];
           neigh2 = neigh2->next)
!       add_vertex(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
!                  INFINITE_ETX);
  
    // add remaining vertices
--- 398,402 ----
           neigh2 != &two_hop_neighbortable[i];
           neigh2 = neigh2->next)
!       add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
  
    // add remaining vertices
***************
*** 372,377 ****
        // add source
  
!       add_vertex(&vertex_tree, &vertex_list, &tcsrc->T_last_addr,
!                  INFINITE_ETX);
  
        // add destinations of this source
--- 407,411 ----
        // add source
  
!       add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
  
        // add destinations of this source
***************
*** 379,384 ****
        for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
             tcdst = tcdst->next)
!         add_vertex(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
!                    INFINITE_ETX);
      }
  
--- 413,417 ----
        for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
             tcdst = tcdst->next)
!         add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
      }
  
***************
*** 397,402 ****
              etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
  
!             add_edge(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
!                      &main_addr, etx);
            }
        }
--- 430,434 ----
              etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
  
!             add_edge(&vertex_tree, &neigh->neighbor_main_addr, &main_addr, etx);
            }
        }
***************
*** 419,423 ****
            etx = 1.0 / neigh_walker->second_hop_link_quality;
  
!           add_edge(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
                     &neigh->neighbor_main_addr, etx);
          }
--- 451,455 ----
            etx = 1.0 / neigh_walker->second_hop_link_quality;
  
!           add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
                     &neigh->neighbor_main_addr, etx);
          }
***************
*** 436,444 ****
              etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
  
!             add_edge(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
!                      &tcsrc->T_last_addr, etx);
            }
        }
  
    // run Dijkstra's algorithm
  
--- 468,480 ----
              etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
  
!             add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
!                      etx);
            }
        }
  
+   // create a sorted vertex list from the vertex tree
+ 
+   create_vertex_list(&vertex_tree, &vertex_list);
+ 
    // run Dijkstra's algorithm