Revert to edge and graph stuff. This time, use a directed graph.

[tinc] / src / graph.c

diff --git a/src/graph.c b/src/graph.c
index 29e25db..b5e8193 100644 (file)
--- a/src/graph.c
+++ b/src/graph.c
@@ -1,7 +1,7 @@
 /*
     graph.c -- graph algorithms
 /*
     graph.c -- graph algorithms

-    Copyright (C) 2001-2002 Guus Sliepen <guus@sliepen.warande.net>,
-                  2001-2002 Ivo Timmermans <itimmermans@bigfoot.com>
+    Copyright (C) 2001-2002 Guus Sliepen <guus@sliepen.eu.org>,
+                  2001-2002 Ivo Timmermans <ivo@o2w.nl>

 
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by
 
     This program is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published by


@@ -17,7 +17,7 @@
     along with this program; if not, write to the Free Software
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
     along with this program; if not, write to the Free Software
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 

-    $Id: graph.c,v 1.1.2.10 2002/03/19 22:48:25 guus Exp $
+    $Id: graph.c,v 1.1.2.15 2002/09/04 13:48:51 guus Exp $

 */
 
 /* We need to generate two trees from the graph:
 */
 
 /* We need to generate two trees from the graph:


@@ -44,10 +44,13 @@
    destination address and port of a node if possible.
 */
 
    destination address and port of a node if possible.
 */
 

+#include "config.h"
+
+#include <stdio.h>

 #include <syslog.h>
 #include "config.h"
 #include <string.h>
 #include <syslog.h>
 #include "config.h"
 #include <string.h>

-#if defined(HAVE_FREEBSD) || defined(HAVE_OPENBSD)
+#ifdef HAVE_SYS_PARAM_H

  #include <sys/param.h>
 #endif
 #include <netinet/in.h>
  #include <sys/param.h>
 #endif
 #include <netinet/in.h>


@@ -59,6 +62,8 @@
 #include "node.h"
 #include "edge.h"
 #include "connection.h"
 #include "node.h"
 #include "edge.h"
 #include "connection.h"

+#include "process.h"
+#include "device.h"

 
 #include "system.h"
 
 
 #include "system.h"
 


@@ -104,7 +109,7 @@ void mst_kruskal(void)
 
   /* Starting point */
   
 
   /* Starting point */
   

-  ((edge_t *)edge_weight_tree->head->data)->from.node->status.visited = 1;
+  ((edge_t *)edge_weight_tree->head->data)->from->status.visited = 1;

 
   /* Add safe edges */
 
 
   /* Add safe edges */
 


@@ -113,24 +118,25 @@ void mst_kruskal(void)
       next = node->next;
       e = (edge_t *)node->data;
 
       next = node->next;
       e = (edge_t *)node->data;
 

-      if(e->from.node->status.visited == e->to.node->status.visited)
+      if(!e->reverse || e->from->status.visited == e->to->status.visited)

         {
           skipped = 1;
           continue;
         }
 
         {
           skipped = 1;
           continue;
         }
 

-      e->from.node->status.visited = 1;
-      e->to.node->status.visited = 1;
+      e->from->status.visited = 1;
+      e->to->status.visited = 1;

       if(e->connection)
         e->connection->status.mst = 1;
 
       safe_edges++;
 
       if(debug_lvl >= DEBUG_SCARY_THINGS)
       if(e->connection)
         e->connection->status.mst = 1;
 
       safe_edges++;
 
       if(debug_lvl >= DEBUG_SCARY_THINGS)

-       syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from.node->name, e->to.node->name, e->weight);
+       syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight);

 
       if(skipped)
         {
 
       if(skipped)
         {

+         skipped = 0;

           next = edge_weight_tree->head;
           continue;
         }
           next = edge_weight_tree->head;
           continue;
         }


@@ -149,9 +155,12 @@ void sssp_bfs(void)
   avl_node_t *node, *from, *next, *to;
   edge_t *e;
   node_t *n;
   avl_node_t *node, *from, *next, *to;
   edge_t *e;
   node_t *n;

-  halfconnection_t to_hc, from_hc;

   avl_tree_t *todo_tree;
   int indirect;
   avl_tree_t *todo_tree;
   int indirect;

+  char *name;
+  char *address, *port;
+  char *envp[7];
+  int i;

 
   todo_tree = avl_alloc_tree(NULL, NULL);
 
 
   todo_tree = avl_alloc_tree(NULL, NULL);
 


@@ -186,52 +195,50 @@ void sssp_bfs(void)
           for(to = n->edge_tree->head; to; to = to->next)        /* "to" is the edge connected to "from" */
             {
               e = (edge_t *)to->data;
           for(to = n->edge_tree->head; to; to = to->next)        /* "to" is the edge connected to "from" */
             {
               e = (edge_t *)to->data;

-
-              if(e->from.node == n)                              /* "from_hc" is the halfconnection with .node == from */
-                to_hc = e->to, from_hc = e->from;
-              else
-                to_hc = e->from, from_hc = e->to;
+             
+             if(!e->reverse)
+                continue;

 
               /* Situation:
 
                          /
                         /
 
               /* Situation:
 
                          /
                         /

-                ------(n)from_hc-----to_hc
+                ------(n)-----(e->to)

                         \
                          \
 
                         \
                          \
 

-                 n->address is set to the to_hc.udpaddress of the edge left of n.
-                We are currently examining the edge right of n:
+                 n->address is set to the e->address of the edge left of n to n.
+                We are currently examining the edge e right of n from n:

 
 

-                 - If from_hc.udpaddress != n->address, then to_hc.node is probably
+                 - If e->reverse->address != n->address, then e->to is probably

                   not reachable for the nodes left of n. We do as if the indirectdata
                   flag is set on edge e.
                   not reachable for the nodes left of n. We do as if the indirectdata
                   flag is set on edge e.

-                - If edge e provides for better reachability of to_hc.node, update
-                  to_hc.node and (re)add it to the todo_tree to (re)examine the reachability
+                - If edge e provides for better reachability of e->to, update
+                  e->to and (re)add it to the todo_tree to (re)examine the reachability

                   of nodes behind it.
              */
 
                   of nodes behind it.
              */
 

-              indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &from_hc.udpaddress));
+              indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &e->reverse->address));

 
 

-              if(to_hc.node->status.visited && (!to_hc.node->status.indirect || indirect))
+              if(e->to->status.visited && (!e->to->status.indirect || indirect))

                continue;
 
                continue;
 

-              to_hc.node->status.visited = 1;
-              to_hc.node->status.indirect = indirect;
-              to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
-              to_hc.node->via = indirect ? n->via : to_hc.node;
-             to_hc.node->options = e->options;
-              if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress))
-             {
-                node = avl_unlink(node_udp_tree, to_hc.node);
-                to_hc.node->address = to_hc.udpaddress;
-               if(to_hc.node->hostname)
-                 free(to_hc.node->hostname);
-               to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress);
-                avl_insert_node(node_udp_tree, node);
-             }
+              e->to->status.visited = 1;
+              e->to->status.indirect = indirect;
+              e->to->nexthop = (n->nexthop == myself) ? e->to : n->nexthop;
+              e->to->via = indirect ? n->via : e->to;
+             e->to->options = e->options;
+              if(sockaddrcmp(&e->to->address, &e->address))
+               {
+                  node = avl_unlink(node_udp_tree, e->to);
+                  e->to->address = e->address;
+                 if(e->to->hostname)
+                   free(e->to->hostname);
+                 e->to->hostname = sockaddr2hostname(&e->to->address);
+                  avl_insert_node(node_udp_tree, node);
+               }

               node = avl_alloc_node();
               node = avl_alloc_node();

-              node->data = to_hc.node;
+              node->data = e->to;

               avl_insert_before(todo_tree, from, node);
             }
 
               avl_insert_before(todo_tree, from, node);
             }
 


@@ -248,26 +255,36 @@ void sssp_bfs(void)
       next = node->next;
       n = (node_t *)node->data;
 
       next = node->next;
       n = (node_t *)node->data;
 

-      if(n->status.visited)
+      if(n->status.visited != n->status.reachable)

       {
       {

-        if(!n->status.reachable)
-       {
-          if(debug_lvl >= DEBUG_TRAFFIC)
+        n->status.reachable = !n->status.reachable;
+        if(debug_lvl >= DEBUG_TRAFFIC)
+         if(n->status.reachable)

             syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname);
             syslog(LOG_DEBUG, _("Node %s (%s) became reachable"), n->name, n->hostname);

-          n->status.reachable = 1;
-       }
-      }
-      else
-      {
-        if(n->status.reachable)
-       {
-          if(debug_lvl >= DEBUG_TRAFFIC)
-            syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"), n->name, n->hostname);
-          n->status.reachable = 0;
-         n->status.validkey = 0;
-         n->status.waitingforkey = 0;
-         n->sent_seqno = 0;
-       }
+         else
+           syslog(LOG_DEBUG, _("Node %s (%s) became unreachable"), n->name, n->hostname);
+
+       n->status.validkey = 0;
+       n->status.waitingforkey = 0;
+       n->sent_seqno = 0;
+
+       asprintf(&envp[0], "NETNAME=%s", netname?netname:"");
+       asprintf(&envp[1], "DEVICE=%s", device?device:"");
+       asprintf(&envp[2], "INTERFACE=%s", interface?interface:"");
+       asprintf(&envp[3], "NODE=%s", n->name);
+       sockaddr2str(&n->address, &address, &port);
+        asprintf(&envp[4], "REMOTEADDRESS=%s", address);
+       asprintf(&envp[5], "REMOTEPORT=%s", port);
+       envp[6] = NULL;
+
+       asprintf(&name, n->status.reachable?"hosts/%s-up":"hosts/%s-down", n->name);
+       execute_script(name, envp);
+       free(name);
+        free(address);
+       free(port);
+
+       for(i = 0; i < 7; i++)
+         free(envp[i]);

       }
     }
 }
       }
     }
 }