- More changes needed for Kruskal's algorithm

- Implemented a breadth-first search algorithm as a cheap substitution for a
  single-source shortest path algorithm.

diff --git a/src/connection.c b/src/connection.c
index 8fb9611..1bad118 100644 (file)
--- a/src/connection.c
+++ b/src/connection.c
@@ -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: connection.c,v 1.1.2.22 2001/10/28 08:41:19 guus Exp $
+    $Id: connection.c,v 1.1.2.23 2001/10/28 22:42:49 guus Exp $

 */
 
 #include "config.h"
 */
 
 #include "config.h"


@@ -25,6 +25,7 @@
 #include <stdio.h>
 #include <syslog.h>
 #include <string.h>
 #include <stdio.h>
 #include <syslog.h>
 #include <string.h>

+#include <sys/time.h>

 
 #include <avl_tree.h>
 #include <list.h>
 
 #include <avl_tree.h>
 #include <list.h>


@@ -65,6 +66,11 @@ connection_t *new_connection(void)
   connection_t *c;
 cp
   c = (connection_t *)xmalloc_and_zero(sizeof(connection_t));
   connection_t *c;
 cp
   c = (connection_t *)xmalloc_and_zero(sizeof(connection_t));

+
+  if(!c)
+    return NULL;
+
+  gettimeofday(&c->start, NULL);

 cp
   return c;
 }
 cp
   return c;
 }

diff --git a/src/connection.h b/src/connection.h
index 9f2bf27..5307147 100644 (file)
--- a/src/connection.h
+++ b/src/connection.h
@@ -17,12 +17,14 @@
     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: connection.h,v 1.1.2.19 2001/10/28 10:16:18 guus Exp $
+    $Id: connection.h,v 1.1.2.20 2001/10/28 22:42:49 guus Exp $

 */
 
 #ifndef __TINC_CONNECTION_H__
 #define __TINC_CONNECTION_H__
 
 */
 
 #ifndef __TINC_CONNECTION_H__
 #define __TINC_CONNECTION_H__
 

+#include <sys/time.h>
+

 #include <avl_tree.h>
 #include <list.h>
 
 #include <avl_tree.h>
 #include <list.h>
 


@@ -71,6 +73,8 @@ typedef struct connection_t {
   int socket;                      /* socket used for this connection */
   long int options;                /* options for this connection */
   struct connection_status_t status; /* status info */
   int socket;                      /* socket used for this connection */
   long int options;                /* options for this connection */
   struct connection_status_t status; /* status info */

+  int estimated_weight;            /* estimation for the weight of the edge for this connection */
+  struct timeval start;            /* time this connection was started, used for above estimation */

 
   struct node_t *node;             /* node associated with the other end */
   struct edge_t *edge;         /* edge associated with this connection */
 
   struct node_t *node;             /* node associated with the other end */
   struct edge_t *edge;         /* edge associated with this connection */

diff --git a/src/edge.c b/src/edge.c
index aee1be0..92abbb3 100644 (file)
--- a/src/edge.c
+++ b/src/edge.c
@@ -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: edge.c,v 1.1.2.2 2001/10/28 10:16:18 guus Exp $
+    $Id: edge.c,v 1.1.2.3 2001/10/28 22:42:49 guus Exp $

 */
 
 #include "config.h"
 */
 
 #include "config.h"


@@ -65,17 +65,11 @@ int edge_compare(edge_t *a, edge_t *b)
 
 */
 
 
 */
 

-int edge_weight_compare(edge_t *a, edge_t *b)
+int edge_name_compare(edge_t *a, edge_t *b)

 {
   int result;
   char *name_a1, *name_a2, *name_b1, *name_b2;
   
 {
   int result;
   char *name_a1, *name_a2, *name_b1, *name_b2;
   

-  
-  result = a->weight - b->weight;
-  
-  if(result)
-    return result;
-

   if(strcmp(a->from->name, a->to->name) < 0)
     name_a1 = a->from->name, name_a2 = a->to->name;
   else
   if(strcmp(a->from->name, a->to->name) < 0)
     name_a1 = a->from->name, name_a2 = a->to->name;
   else


@@ -94,6 +88,18 @@ int edge_weight_compare(edge_t *a, edge_t *b)
     return strcmp(name_a2, name_b2);
 }
 
     return strcmp(name_a2, name_b2);
 }
 

+int edge_weight_compare(edge_t *a, edge_t *b)
+{
+  int result;
+  
+  result = a->weight - b->weight;
+  
+  if(result)
+    return result;
+  else
+    return edge_name_compare(a, b);
+}
+

 void init_edges(void)
 {
 cp
 void init_edges(void)
 {
 cp


@@ -102,6 +108,20 @@ cp
 cp
 }
 
 cp
 }
 

+avl_tree_t *new_edge_tree(void)
+{
+cp
+  edge_tree = avl_alloc_tree((avl_compare_t)edge_name_compare, NULL);
+cp
+}
+
+void free_edge_tree(avl_tree_t *edge_tree)
+{
+cp
+  avl_delete_tree(edge_tree);
+cp
+}
+

 void exit_edges(void)
 {
 cp
 void exit_edges(void)
 {
 cp


@@ -113,8 +133,9 @@ cp
 
 edge_t *new_edge(void)
 {
 
 edge_t *new_edge(void)
 {

+  edge_t *e;

 cp
 cp

-  edge_t *e = (edge_t *)xmalloc_and_zero(sizeof(*e));
+  e = (edge_t *)xmalloc_and_zero(sizeof(*e));

 cp
   return e;
 }
 cp
   return e;
 }


@@ -131,6 +152,8 @@ void edge_add(edge_t *e)
 cp
   avl_insert(edge_tree, e);
   avl_insert(edge_weight_tree, e);
 cp
   avl_insert(edge_tree, e);
   avl_insert(edge_weight_tree, e);

+  avl_insert(e->from->edge_tree, e);
+  avl_insert(e->to->edge_tree, e);

 cp
 }
 
 cp
 }
 


@@ -139,6 +162,8 @@ void edge_del(edge_t *e)
 cp
   avl_delete(edge_tree, e);
   avl_delete(edge_weight_tree, e);
 cp
   avl_delete(edge_tree, e);
   avl_delete(edge_weight_tree, e);

+  avl_delete(e->from->edge_tree, e);
+  avl_delete(e->to->edge_tree, e);

 cp
 }
 
 cp
 }
 

diff --git a/src/edge.h b/src/edge.h
index 3bd475e..4fff387 100644 (file)
--- a/src/edge.h
+++ b/src/edge.h
@@ -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: edge.h,v 1.1.2.2 2001/10/28 10:16:18 guus Exp $
+    $Id: edge.h,v 1.1.2.3 2001/10/28 22:42:49 guus Exp $

 */
 
 #ifndef __TINC_EDGE_H__
 */
 
 #ifndef __TINC_EDGE_H__


@@ -55,6 +55,8 @@ extern void init_edges(void);
 extern void exit_edges(void);
 extern edge_t *new_edge(void);
 extern void free_edge(edge_t *);
 extern void exit_edges(void);
 extern edge_t *new_edge(void);
 extern void free_edge(edge_t *);

+extern avl_tree_t *new_edge_tree(void);
+extern void free_edge_tree(avl_tree_t *);

 extern void edge_add(edge_t *);
 extern void edge_del(edge_t *);
 extern edge_t *lookup_edge(struct node_t *, struct node_t *);
 extern void edge_add(edge_t *);
 extern void edge_del(edge_t *);
 extern edge_t *lookup_edge(struct node_t *, struct node_t *);

diff --git a/src/graph.c b/src/graph.c
index 50695e4..c7ca8af 100644 (file)
--- a/src/graph.c
+++ b/src/graph.c
@@ -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.1 2001/10/28 10:16:18 guus Exp $
+    $Id: graph.c,v 1.1.2.2 2001/10/28 22:42:49 guus Exp $

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


@@ -34,12 +34,15 @@
    removed, and during the MST algorithm we just have go linearly through that
    tree, adding safe edges until #edges = #nodes - 1.
 
    removed, and during the MST algorithm we just have go linearly through that
    tree, adding safe edges until #edges = #nodes - 1.
 

-   For the SSSP algorithm Dijkstra's seems to be a nice choice.
+   For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
+   simple breadth-first search is presented here.

 */
 
 #include <syslog.h>
 #include "config.h"
 
 */
 
 #include <syslog.h>
 #include "config.h"
 

+#include <avl_tree.h>
+

 #include "node.h"
 #include "edge.h"
 #include "connection.h"
 #include "node.h"
 #include "edge.h"
 #include "connection.h"


@@ -47,35 +50,35 @@
 #include "system.h"
 
 /* Implementation of Kruskal's algorithm.
 #include "system.h"
 
 /* Implementation of Kruskal's algorithm.

-   Running time: O(V)
-   Please note that sorting on weight is already done by add_vertex().
+   Running time: O(E)
+   Please note that sorting on weight is already done by add_edge().

 */
 
 */
 

-void kruskal(void)
+void mst_kruskal(void)

 {
   avl_node_t *node;
   edge_t *e;
   node_t *n;
   connection_t *c;
 {
   avl_node_t *node;
   edge_t *e;
   node_t *n;
   connection_t *c;

-  int nodes;
+  int nodes = 0;

   int safe_edges = 0;
   
   syslog(LOG_DEBUG, _("Running Kruskal's algorithm:"));
 
   int safe_edges = 0;
   
   syslog(LOG_DEBUG, _("Running Kruskal's algorithm:"));
 

-  /* Clear MST status on nodes */
+  /* Clear visited status on nodes */

 
   for(node = node_tree->head; node; node = node->next)
     {
       n = (node_t *)node->data;
 
   for(node = node_tree->head; node; node = node->next)
     {
       n = (node_t *)node->data;

-      n->status.mst = 0;
-      node++;
+      n->status.visited = 0;
+      nodes++;

     }
 
   /* Clear MST status on connections */
 
   for(node = connection_tree->head; node; node = node->next)
     {
     }
 
   /* Clear MST status on connections */
 
   for(node = connection_tree->head; node; node = node->next)
     {

-      c = (edge_t *)node->data;
+      c = (connection_t *)node->data;

       c->status.mst = 0;
     }
 
       c->status.mst = 0;
     }
 


@@ -89,11 +92,11 @@ void kruskal(void)
 
       e = (edge_t *)node->data;
       
 
       e = (edge_t *)node->data;
       

-      if(e->from->status.mst && e->to->status.mst)
+      if(e->from->status.visited && e->to->status.visited)

         continue;
 
         continue;
 

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

       if(e->connection)
         e->connection->status.mst = 1;
 
       if(e->connection)
         e->connection->status.mst = 1;
 


@@ -109,3 +112,79 @@ void kruskal(void)
       syslog(LOG_ERR, _("Implementation of Kruskal's algorithm is screwed: %d nodes, found %d safe edges"), nodes, safe_edges);
     }
 }
       syslog(LOG_ERR, _("Implementation of Kruskal's algorithm is screwed: %d nodes, found %d safe edges"), nodes, safe_edges);
     }
 }

+
+/* Implementation of a simple breadth-first search algorithm.
+   Running time: O(E)
+*/
+
+void sssp_bfs(void)
+{
+  avl_node_t *node, *from, *next, *to;
+  edge_t *e;
+  node_t *n, *check;
+  int nodes = 0;
+  int visited = 0;
+  avl_tree_t *todo_tree;
+  
+  syslog(LOG_DEBUG, _("Running BFS algorithm:"));
+
+  todo_tree = avl_alloc_tree(NULL, NULL);
+
+  /* Clear visited status on nodes */
+
+  for(node = node_tree->head; node; node = node->next)
+    {
+      n = (node_t *)node->data;
+      n->status.visited = 0;
+      nodes++;
+    }
+
+  /* Begin with myself */
+
+  myself->status.visited = 1;
+  myself->nexthop = myself;
+  myself->via = myself;
+  node = avl_alloc_node();
+  node->data = myself;
+  avl_insert_top(todo_tree, node);
+  visited++;
+
+  /* Loop while todo_tree is filled */
+
+  while(todo_tree->head)
+    {
+      for(from = todo_tree->head; from; from = next)
+        {
+          next = from->next;
+          n = (node_t *)from->data;
+          
+          for(to = n->edge_tree->head; to; to = to->next)
+            {
+              e = (edge_t *)to->data;
+
+              if(e->from == n)
+                check = e->to;
+              else
+                check = e->from;
+
+              if(!check->status.visited)
+                {
+                  check->status.visited = 1;
+                  check->nexthop = (n->nexthop == myself)?n:n->nexthop;
+                  check->via = check; /* FIXME: only if !(e->options & INDIRECT), otherwise use n->via */
+                  avl_insert_before(todo_tree, todo_tree->head, to);
+                  visited++;
+                }
+            }
+
+           avl_delete_node(todo_tree, from);
+        }
+    }
+
+  syslog(LOG_DEBUG, _("Done."));
+
+  if(visited != nodes)
+    {
+      syslog(LOG_ERR, _("Implementation of BFS algorithm is screwed: %d nodes, visited %d"), nodes, visited);
+    }
+}

diff --git a/src/node.c b/src/node.c
index 3776d18..f50d365 100644 (file)
--- a/src/node.c
+++ b/src/node.c
@@ -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: node.c,v 1.1.2.3 2001/10/27 13:13:35 guus Exp $
+    $Id: node.c,v 1.1.2.4 2001/10/28 22:42:49 guus Exp $

 */
 
 #include "config.h"
 */
 
 #include "config.h"


@@ -73,7 +73,8 @@ node_t *new_node(void)
 {
   node_t *n = (node_t *)xmalloc_and_zero(sizeof(*n));
 cp
 {
   node_t *n = (node_t *)xmalloc_and_zero(sizeof(*n));
 cp

-  n->subnet_tree = avl_alloc_tree((avl_compare_t)subnet_compare, NULL);
+  n->subnet_tree = new_subnet_tree();
+  n->edge_tree = new_edge_tree();

   n->queue = list_alloc((list_action_t)free);
 cp
   return n;
   n->queue = list_alloc((list_action_t)free);
 cp
   return n;


@@ -90,6 +91,10 @@ cp
     free(n->hostname);
   if(n->key)
     free(n->key);
     free(n->hostname);
   if(n->key)
     free(n->key);

+  if(n->subnet_tree)
+    free_subnet_tree(n->subnet_tree);
+  if(n->edge_tree)
+    free_edge_tree(n->edge_tree);

   free(n);
 cp
 }
   free(n);
 cp
 }

diff --git a/src/node.h b/src/node.h
index b7c77e6..cc81b3b 100644 (file)
--- a/src/node.h
+++ b/src/node.h
@@ -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: node.h,v 1.1.2.6 2001/10/28 10:16:18 guus Exp $
+    $Id: node.h,v 1.1.2.7 2001/10/28 22:42:49 guus Exp $

 */
 
 #ifndef __TINC_NODE_H__
 */
 
 #ifndef __TINC_NODE_H__


@@ -32,7 +32,7 @@ typedef struct node_status_t {
   int active:1;                    /* 1 if active.. */
   int validkey:1;                  /* 1 if we currently have a valid key for him */
   int waitingforkey:1;             /* 1 if we already sent out a request */
   int active:1;                    /* 1 if active.. */
   int validkey:1;                  /* 1 if we currently have a valid key for him */
   int waitingforkey:1;             /* 1 if we already sent out a request */

-  int mst:1;                       /* 1 if this node has been visited by the MST algorithm */
+  int visited:1;                   /* 1 if this node has been visited by one of the graph algorithms */

   int unused:28;
 } node_status_t;
 
   int unused:28;
 } node_status_t;
 


@@ -50,13 +50,15 @@ typedef struct node_t {
   char *key;                       /* Cipher key and iv */
   int keylength;                   /* Cipher key and iv length*/
 
   char *key;                       /* Cipher key and iv */
   int keylength;                   /* Cipher key and iv length*/
 

-  list_t *queue;               /* Queue for packets awaiting to be encrypted */
+  list_t *queue;                   /* Queue for packets awaiting to be encrypted */

 
   struct node_t *nexthop;          /* nearest node from us to him */
   struct node_t *via;              /* next hop for UDP packets */
   
   avl_tree_t *subnet_tree;         /* Pointer to a tree of subnets belonging to this node */
 
 
   struct node_t *nexthop;          /* nearest node from us to him */
   struct node_t *via;              /* next hop for UDP packets */
   
   avl_tree_t *subnet_tree;         /* Pointer to a tree of subnets belonging to this node */
 

+  avl_tree_t *edge_tree;           /* Edges with this node as one of the endpoints */
+

   struct connection_t *connection; /* Connection associated with this node (if a direct connection exists) */
 } node_t;
 
   struct connection_t *connection; /* Connection associated with this node (if a direct connection exists) */
 } node_t;
 

diff --git a/src/protocol.c b/src/protocol.c
index 2771405..63b10b1 100644 (file)
--- a/src/protocol.c
+++ b/src/protocol.c
@@ -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: protocol.c,v 1.28.4.111 2001/10/28 10:16:18 guus Exp $
+    $Id: protocol.c,v 1.28.4.112 2001/10/28 22:42:49 guus Exp $

 */
 
 #include "config.h"
 */
 
 #include "config.h"


@@ -526,18 +526,26 @@ int send_ack(connection_t *c)
 {
   /* ACK message contains rest of the information the other end needs
      to create node_t and edge_t structures. */
 {
   /* ACK message contains rest of the information the other end needs
      to create node_t and edge_t structures. */

+
+  struct timeval now;
+
+  /* Estimate weight */
+  
+  gettimeofday(&now, NULL);
+  c->estimated_weight = (now.tv_sec - c->start.tv_sec) * 1000 + (now.tv_usec - c->start.tv_usec) / 1000;

 cp
 cp

-  return send_request(c, "%d %d", ACK, myself->port);
+  return send_request(c, "%d %hd %d", ACK, myself->port, c->estimated_weight);

 }
 
 int ack_h(connection_t *c)
 {
   port_t port;
 }
 
 int ack_h(connection_t *c)
 {
   port_t port;

+  int weight;

   node_t *n;
   subnet_t *s;
   avl_node_t *node, *node2;
 cp
   node_t *n;
   subnet_t *s;
   avl_node_t *node, *node2;
 cp

-  if(sscanf(c->buffer, "%*d %hd", &port) != 1)
+  if(sscanf(c->buffer, "%*d %hd %d", &port, &weight) != 2)

     {
        syslog(LOG_ERR, _("Got bad %s from %s (%s)"), "ACK", c->name, c->hostname);
        return -1;
     {
        syslog(LOG_ERR, _("Got bad %s from %s (%s)"), "ACK", c->name, c->hostname);
        return -1;


@@ -600,7 +608,7 @@ cp
   
   c->edge->from = myself;
   c->edge->to = n;
   
   c->edge->from = myself;
   c->edge->to = n;

-  c->edge->weight = 1;
+  c->edge->weight = (weight + c->estimated_weight) / 2;

   c->edge->connection = c;
 
   edge_add(c->edge);
   c->edge->connection = c;
 
   edge_add(c->edge);

diff --git a/src/subnet.c b/src/subnet.c
index fff384f..99d97bc 100644 (file)
--- a/src/subnet.c
+++ b/src/subnet.c
@@ -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: subnet.c,v 1.1.2.26 2001/10/27 13:13:35 guus Exp $
+    $Id: subnet.c,v 1.1.2.27 2001/10/28 22:42:49 guus Exp $

 */
 
 #include "config.h"
 */
 
 #include "config.h"


@@ -40,13 +40,6 @@
 
 avl_tree_t *subnet_tree;
 
 
 avl_tree_t *subnet_tree;
 

-void init_subnets(void)
-{
-cp
-  subnet_tree = avl_alloc_tree((avl_compare_t)subnet_compare, (avl_action_t)free_subnet);
-cp
-}
-

 /* Subnet comparison */
 
 int subnet_compare_mac(subnet_t *a, subnet_t *b)
 /* Subnet comparison */
 
 int subnet_compare_mac(subnet_t *a, subnet_t *b)


@@ -121,6 +114,36 @@ cp
     }
 }
 
     }
 }
 

+/* Initialising trees */
+
+void init_subnets(void)
+{
+cp
+  subnet_tree = avl_alloc_tree((avl_compare_t)subnet_compare, (avl_action_t)free_subnet);
+cp
+}
+
+void exit_subnets(void)
+{
+cp
+  avl_delete_tree(subnet_tree);
+cp
+}
+
+avl_tree_t *new_subnet_tree(void)
+{
+cp
+  return avl_alloc_tree((avl_compare_t)subnet_compare, NULL);
+cp
+}
+
+void free_subnet_tree(avl_tree_t *subnet_tree)
+{
+cp
+  avl_delete_tree(subnet_tree);
+cp
+}
+

 /* Allocating and freeing space for subnets */
 
 subnet_t *new_subnet(void)
 /* Allocating and freeing space for subnets */
 
 subnet_t *new_subnet(void)

diff --git a/src/subnet.h b/src/subnet.h
index 50cfefd..d1dd965 100644 (file)
--- a/src/subnet.h
+++ b/src/subnet.h
@@ -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: subnet.h,v 1.1.2.12 2001/10/27 13:13:35 guus Exp $
+    $Id: subnet.h,v 1.1.2.13 2001/10/28 22:42:49 guus Exp $

 */
 
 #ifndef __TINC_SUBNET_H__
 */
 
 #ifndef __TINC_SUBNET_H__


@@ -72,11 +72,13 @@ typedef struct subnet_t {
 extern subnet_t *new_subnet(void);
 extern void free_subnet(subnet_t *);
 extern void init_subnets(void);
 extern subnet_t *new_subnet(void);
 extern void free_subnet(subnet_t *);
 extern void init_subnets(void);

+extern void exit_subnets(void);
+extern avl_tree_t *new_subnet_tree(void);
+extern void free_subnet_tree(avl_tree_t *);

 extern void subnet_add(struct node_t *, subnet_t *);
 extern void subnet_del(struct node_t *, subnet_t *);
 extern char *net2str(subnet_t *);
 extern subnet_t *str2net(char *);
 extern void subnet_add(struct node_t *, subnet_t *);
 extern void subnet_del(struct node_t *, subnet_t *);
 extern char *net2str(subnet_t *);
 extern subnet_t *str2net(char *);

-extern int subnet_compare(subnet_t *, subnet_t *);

 extern subnet_t *lookup_subnet(struct node_t *, subnet_t *);
 extern subnet_t *lookup_subnet_mac(mac_t *);
 extern subnet_t *lookup_subnet_ipv4(ipv4_t *);
 extern subnet_t *lookup_subnet(struct node_t *, subnet_t *);
 extern subnet_t *lookup_subnet_mac(mac_t *);
 extern subnet_t *lookup_subnet_ipv4(ipv4_t *);