* patch by Hannes Gredler <hannes@gredler.at> to consolidate the the link-state datab...
authorBernd Petrovitsch <bernd@firmix.at>
Thu, 13 Sep 2007 15:31:59 +0000 (15:31 +0000)
committerBernd Petrovitsch <bernd@firmix.at>
Thu, 13 Sep 2007 15:31:59 +0000 (15:31 +0000)
13 files changed:
CHANGELOG
lib/bmf/src/NetworkInterfaces.c
lib/dot_draw/src/olsrd_dot_draw.c
lib/httpinfo/src/olsrd_httpinfo.c
lib/nameservice/src/nameservice.c
lib/pgraph/src/olsrd_pgraph.c
lib/tas/src/plugin.c
lib/txtinfo/src/olsrd_txtinfo.c
src/lq_route.c
src/lq_route.h
src/process_package.c
src/tc_set.c
src/tc_set.h

index f9d9b41..47a60dd 100644 (file)
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,5 +1,5 @@
 This file states changes as of version 0.2.4:
-$Id: CHANGELOG,v 1.84 2007/09/11 23:22:38 bernd67 Exp $
+$Id: CHANGELOG,v 1.85 2007/09/13 15:31:58 bernd67 Exp $
 
 0.5.4 ---------------------------------------------------------------------
 
@@ -77,6 +77,17 @@ non RT related stuff:
 And Sven-Ola Tuecke <mail2news@commando.de> fixed an instability issue on interface
 up/down operations (see 102-olsrd-rt-refactoring-fixes.patch below).
 
+PATCH by Hannes Gredler <hannes@gredler.at> which "consolidates
+the link-state database and the spf-calculation in order
+to calculate routes more efficiently".
+To quote him (more):
+----  snip  ----
+- use the link-state (tc) database for SPF calculations rather than
+  replicating the notion of vertices and edges for a SPF run.
+  this heavily reduces malloc() calls and shrinks the total CPU
+  load of the route calculation path between 60%-80%.
+----  snip  ----
+
 PATCHES by Sven-Ola Tuecke to be found on from
 http://download-master.berlin.freifunk.net/sven-ola/nylon/packages/olsrd/files/
 - 102-olsrd-rt-refactoring-fixes.patch
index fa531fd..eed7a34 100644 (file)
@@ -862,16 +862,16 @@ void GetBestTwoNeighbors(
         tcLastHop = olsr_lookup_tc_entry(MainAddressOf(forwardedBy));
         if (tcLastHop != NULL)
         {
-          struct topo_dst* tcDest;
+          struct tc_edge_entry* tc_edge;
 
-          /* TODO: olsr_tc_lookup_dst() is not thread-safe. */
-          tcDest = olsr_tc_lookup_dst(tcLastHop, MainAddressOf(&walker->neighbor_iface_addr));
+          /* TODO: olsr_lookup_tc_edge() is not thread-safe. */
+          tc_edge = olsr_lookup_tc_edge(tcLastHop, MainAddressOf(&walker->neighbor_iface_addr));
 
-          if (tcDest != NULL)
+          if (tc_edge != NULL)
           {
             float tcEtx = CalcEtx(
-              tcDest->link_quality,
-              tcDest->inverse_link_quality);
+              tc_edge->link_quality,
+              tc_edge->inverse_link_quality);
 
             if (previousLinkEtx + currEtx > tcEtx)
             {
index 5bf9bbf..e84f805 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_dot_draw.c,v 1.26 2007/07/23 12:58:38 bernd67 Exp $
+ * $Id: olsrd_dot_draw.c,v 1.27 2007/09/13 15:31:58 bernd67 Exp $
  */
 
 /*
@@ -102,7 +102,7 @@ static void
 ipc_print_neigh_link(struct neighbor_entry *neighbor);
 
 static void
-ipc_print_tc_link(struct tc_entry *entry, struct topo_dst *dst_entry);
+ipc_print_tc_link(struct tc_entry *entry, struct tc_edge_entry *dst_entry);
 
 static void
 ipc_print_net(union olsr_ip_addr *, union olsr_ip_addr *, union hna_netmask *);
@@ -297,8 +297,8 @@ pcf_event(int changes_neighborhood,
   int res;
   olsr_u8_t index;
   struct neighbor_entry *neighbor_table_tmp;
-  struct tc_entry *entry;
-  struct topo_dst *dst_entry;
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge;
   struct hna_entry *tmp_hna;
   struct hna_net *tmp_net;
 
@@ -323,22 +323,11 @@ pcf_event(int changes_neighborhood,
        }
 
       /* Topology */  
-      for(index=0;index<HASHSIZE;index++)
-       {
-         /* For all TC entries */
-         entry = tc_table[index].next;
-         while(entry != &tc_table[index])
-           {
-             /* For all destination entries of that TC entry */
-             dst_entry = entry->destinations.next;
-             while(dst_entry != &entry->destinations)
-               {
-                 ipc_print_tc_link(entry, dst_entry);
-                 dst_entry = dst_entry->next;
-               }
-             entry = entry->next;
-           }
-       }
+      OLSR_FOR_ALL_TC_ENTRIES(tc) {
+          OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+              ipc_print_tc_link(tc, tc_edge);
+          } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+      } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
       /* HNA entries */
       for(index=0;index<HASHSIZE;index++)
@@ -388,13 +377,13 @@ calc_etx(double loss, double neigh_loss)
 
 
 static void
-ipc_print_tc_link(struct tc_entry *entry, struct topo_dst *dst_entry)
+ipc_print_tc_link(struct tc_entry *entry, struct tc_edge_entry *dst_entry)
 {
   char buf[256];
   const char* adr;
   double etx = calc_etx( dst_entry->link_quality, dst_entry->inverse_link_quality );
 
-  adr = olsr_ip_to_string(&entry->T_last_addr);
+  adr = olsr_ip_to_string(&entry->addr);
   sprintf( buf, "\"%s\" -> ", adr );
   ipc_send_str(buf);
   
index 1cc4009..da9fd44 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_httpinfo.c,v 1.74 2007/09/12 14:08:00 bernd67 Exp $
+ * $Id: olsrd_httpinfo.c,v 1.75 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 /*
@@ -1064,49 +1064,35 @@ static int build_neigh_body(char *buf, olsr_u32_t bufsize)
 static int build_topo_body(char *buf, olsr_u32_t bufsize)
 {
   int size = 0;
-  olsr_u8_t index;
-  struct tc_entry *entry;
-  struct topo_dst *dst_entry;
-
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge;
 
   size += snprintf(&buf[size], bufsize-size, "<h2>Topology entries</h2>\n<table width=\"100%%\" BORDER=0 CELLSPACING=0 CELLPADDING=0 ALIGN=center><tr><th>Destination IP</th><th>Last Hop IP</th>");
   if (olsr_cnf->lq_level > 0)
     size += snprintf(&buf[size], bufsize-size, "<th>LQ</th><th>ILQ</th><th>ETX</th>");
   size += snprintf(&buf[size], bufsize-size, "</tr>\n");
 
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+      OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 
-  /* Topology */  
-  for(index=0;index<HASHSIZE;index++)
-    {
-      /* For all TC entries */
-      entry = tc_table[index].next;
-      while(entry != &tc_table[index])
-       {
-         /* For all destination entries of that TC entry */
-         dst_entry = entry->destinations.next;
-         while(dst_entry != &entry->destinations)
-           {
-              size += snprintf(&buf[size], bufsize-size, "<tr>");
-              size += build_ipaddr_with_link(&buf[size], bufsize, &dst_entry->T_dest_addr, -1);
-              size += build_ipaddr_with_link(&buf[size], bufsize, &entry->T_last_addr, -1);
-              if (olsr_cnf->lq_level > 0)
-                {
-                  const double d = dst_entry->link_quality * dst_entry->inverse_link_quality;
-                 size += snprintf(&buf[size], bufsize-size,
-                                 "<td align=\"right\">%0.2f</td>"
-                                 "<td align=\"right\">%0.2f</td>"
-                                 "<td align=\"right\">%0.2f</td>\n",
-                                 dst_entry->link_quality,
-                                 dst_entry->inverse_link_quality,
-                                 d ? 1.0 / d : 0.0);
-                }
-             size += snprintf(&buf[size], bufsize-size, "</tr>\n");
-
-             dst_entry = dst_entry->next;
-           }
-         entry = entry->next;
-       }
-    }
+          size += snprintf(&buf[size], bufsize-size, "<tr>");
+          size += build_ipaddr_with_link(&buf[size], bufsize, &tc_edge->T_dest_addr, -1);
+          size += build_ipaddr_with_link(&buf[size], bufsize, &tc->addr, -1);
+          if (olsr_cnf->lq_level > 0)
+          {
+              const double d = tc_edge->link_quality * tc_edge->inverse_link_quality;
+              size += snprintf(&buf[size], bufsize-size,
+                               "<td align=\"right\">%0.2f</td>"
+                               "<td align=\"right\">%0.2f</td>"
+                               "<td align=\"right\">%0.2f</td>\n",
+                               tc_edge->link_quality,
+                               tc_edge->inverse_link_quality,
+                               d ? 1.0 / d : 0.0);
+          }
+          size += snprintf(&buf[size], bufsize-size, "</tr>\n");
+
+      } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
   size += snprintf(&buf[size], bufsize-size, "</table>\n");
 
index 47a93a5..f7fc661 100644 (file)
@@ -31,7 +31,7 @@
  *
  */
 
-/* $Id: nameservice.c,v 1.28 2007/09/05 16:11:10 bernd67 Exp $ */
+/* $Id: nameservice.c,v 1.29 2007/09/13 15:31:59 bernd67 Exp $ */
 
 /*
  * Dynamic linked library for UniK OLSRd
@@ -1440,6 +1440,8 @@ write_latlon_file(void)
        FILE* js;
        struct olsr_if *ifs;
        union olsr_ip_addr ip;
+    struct tc_entry *tc;
+    struct tc_edge_entry *tc_edge;
 
        if (!latlon_table_changed) return;
        OLSR_PRINTF(2, "NAME PLUGIN: writing latlon file\n");
@@ -1511,27 +1513,21 @@ write_latlon_file(void)
                        }
                }
        }
-       for (hash = 0; hash < HASHSIZE; hash++) 
-       {
-               struct tc_entry *entry = tc_table[hash].next;
-               while(entry != &tc_table[hash])
-               {
-                       struct topo_dst *dst_entry = entry->destinations.next;
-                       while(dst_entry != &entry->destinations)
-                       {
-                               fprintf(js, "Link('%s','%s',%f,%f,%f);\n", 
-                                       olsr_ip_to_string(&dst_entry->T_dest_addr),
-                                       olsr_ip_to_string(&entry->T_last_addr), 
-                                       dst_entry->link_quality,
-                                       dst_entry->inverse_link_quality,
-                                       (dst_entry->link_quality * dst_entry->inverse_link_quality) ?
-                                               1.0 / (dst_entry->link_quality * dst_entry->inverse_link_quality) :
-                                               0.0);
-                               dst_entry = dst_entry->next;
-                       }
-                       entry = entry->next;
-               }
-       }
+
+    OLSR_FOR_ALL_TC_ENTRIES(tc) {
+        OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+
+            fprintf(js, "Link('%s','%s',%f,%f,%f);\n", 
+                                       olsr_ip_to_string(&tc_edge->T_dest_addr),
+                                       olsr_ip_to_string(&tc->addr), 
+                                       tc_edge->link_quality,
+                                       tc_edge->inverse_link_quality,
+                                       (tc_edge->link_quality * tc_edge->inverse_link_quality) ?
+                    1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality) :
+                    0.0);
+
+        } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+    } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
        fclose(js);
        latlon_table_changed = OLSR_FALSE;
index e3dbead..b56730f 100755 (executable)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_pgraph.c,v 1.7 2007/08/30 22:49:12 bernd67 Exp $
+ * $Id: olsrd_pgraph.c,v 1.8 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 /*
@@ -145,7 +145,7 @@ static struct link_entry *olsr_neighbor_best_link(union olsr_ip_addr *main);
 
 static void ipc_print_neigh_link(struct neighbor_entry *neighbor);
 
-static void ipc_print_tc_link(struct tc_entry *entry, struct topo_dst *dst_entry);
+static void ipc_print_tc_link(struct tc_entry *entry, struct tc_edge_entry *dst_entry);
 
 #if 0
 static void ipc_print_net(union olsr_ip_addr *, union olsr_ip_addr *, union hna_netmask *);
@@ -321,8 +321,8 @@ static int pcf_event(int changes_neighborhood,
   int res;
   olsr_u8_t index;
   struct neighbor_entry *neighbor_table_tmp;
-  struct tc_entry *entry;
-  struct topo_dst *dst_entry;
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge;
 
   res = 0;
 
@@ -346,22 +346,11 @@ static int pcf_event(int changes_neighborhood,
        }
 
       /* Topology */  
-      for(index=0;index<HASHSIZE;index++)
-       {
-         /* For all TC entries */
-         entry = tc_table[index].next;
-         while(entry != &tc_table[index])
-           {
-             /* For all destination entries of that TC entry */
-             dst_entry = entry->destinations.next;
-             while(dst_entry != &entry->destinations)
-               {
-                 ipc_print_tc_link(entry, dst_entry);
-                 dst_entry = dst_entry->next;
-               }
-             entry = entry->next;
-           }
-       }
+      OLSR_FOR_ALL_TC_ENTRIES(tc) {
+          OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+              ipc_print_tc_link(tc, tc_edge);
+          } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+      } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
       ipc_send(" end ", strlen(" end "));
 
@@ -410,7 +399,7 @@ static double calc_etx(double loss, double neigh_loss)
 }
 #endif
 
-static void ipc_print_tc_link(struct tc_entry *entry, struct topo_dst *dst_entry)
+static void ipc_print_tc_link(struct tc_entry *entry, struct tc_edge_entry *dst_entry)
 {
   char buf[256];
   int len;
@@ -418,7 +407,7 @@ static void ipc_print_tc_link(struct tc_entry *entry, struct topo_dst *dst_entry
   const char* adr;
 //  double etx = calc_etx( dst_entry->link_quality, dst_entry->inverse_link_quality );
 
-  main_adr = olsr_ip_to_string(&entry->T_last_addr);
+  main_adr = olsr_ip_to_string(&entry->addr);
   adr = olsr_ip_to_string(&dst_entry->T_dest_addr);
   len = sprintf( buf, "add link %s %s\n", main_adr, adr );
   ipc_send(buf, len);
index 29402cd..1f2b4e7 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: plugin.c,v 1.11 2007/09/05 16:17:35 bernd67 Exp $
+ * $Id: plugin.c,v 1.12 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 #include <string.h>
@@ -82,7 +82,6 @@ static union olsr_ip_addr *mainAddr;
 static struct interface *intTab = NULL;
 static struct neighbor_entry *neighTab = NULL;
 static struct mid_entry *midTab = NULL;
-static struct tc_entry *tcTab = NULL;
 static struct hna_entry *hnaTab = NULL;
 static struct olsrd_config *config = NULL;
 
@@ -243,38 +242,40 @@ int iterRouteTabNext(char *buff, int len)
 
 void iterRouteTabInit(void)
 {
-    avl_init(&routingtree, avl_comp_prefix_default);
-    routingtree_version = 0;
+  struct avl_node *node;
+
+  avl_init(&routingtree, avl_comp_prefix_default);
+  routingtree_version = 0;
+
+  node = avl_walk_first(&routingtree);
+  iterRouteTab = node ? node->data : NULL;
 
-    iterRouteTab = (avl_walk_first(&routingtree)->data);
 }
 
 int iterTcTabNext(char *buff, int len)
 {
   int res;
   int i;
-  struct topo_dst *dest;
+  struct tc_edge_entry *tc_edge;
   
   if (iterTcTab == NULL)
     return -1;
 
   res = snprintf(buff, len,
                  "main~%s~[~destinations~",
-                 rawIpAddrToString(&iterTcTab->T_last_addr, ipAddrLen));
-
-  i = 0;
+                 rawIpAddrToString(&iterTcTab->addr, ipAddrLen));
 
   len -= res;
   buff += res;
 
   len -= 2;
+  i = 0;
+
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(iterTcTab, tc_edge) {
 
-  for (dest = iterTcTab->destinations.next; dest != &iterTcTab->destinations;
-       dest = dest->next)
-  {
     res = snprintf(buff, len, "[~%d~address~%s~etx~%f~]~", i,
-                   rawIpAddrToString(&dest->T_dest_addr, ipAddrLen),
-                   lqToEtx(dest->link_quality, dest->inverse_link_quality));
+                   rawIpAddrToString(&tc_edge->T_dest_addr, ipAddrLen),
+                   lqToEtx(tc_edge->link_quality, tc_edge->inverse_link_quality));
 
     if (res < len)
       buff += res;
@@ -285,40 +286,23 @@ int iterTcTabNext(char *buff, int len)
       break;
 
     i++;
-  }
-
+  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(iterTcTab, tc_edge);
+  
   strcpy(buff, "]~");
 
-  iterTcTab = iterTcTab->next;
-
-  if (iterTcTab == &tcTab[iterIndex])
-  {
-    iterTcTab = NULL;
-    
-    while (++iterIndex < HASHSIZE)
-      if (tcTab[iterIndex].next != &tcTab[iterIndex])
-      {
-        iterTcTab = tcTab[iterIndex].next;
-        break;
-      }
-  }
+  iterTcTab = olsr_getnext_tc_entry(iterTcTab);
 
   return 0;
 }
 
 void iterTcTabInit(void)
 {
-  iterTcTab = NULL;
-
-  if (tcTab == NULL)
-    return;
+  struct avl_node *node;
+  
+  avl_init(&tc_tree, avl_comp_prefix_default);
 
-  for (iterIndex = 0; iterIndex < HASHSIZE; iterIndex++)
-    if (tcTab[iterIndex].next != &tcTab[iterIndex])
-    {
-      iterTcTab = tcTab[iterIndex].next;
-      break;
-    }
+  node = avl_walk_first(&tc_tree);
+  iterTcTab = node ? node->data : NULL;
 }
 
 static void parserFunc(union olsr_message *msg, struct interface *inInt,
@@ -464,7 +448,6 @@ int olsrd_plugin_init(void)
   intTab = ifnet;
   neighTab = neighbortable;
   midTab = mid_set;
-  tcTab = tc_table;
   hnaTab = hna_set;
   config = olsr_cnf;
 
@@ -496,3 +479,9 @@ void olsrd_get_plugin_parameters(const struct olsrd_plugin_parameters **params,
     *params = plugin_parameters;
     *size = sizeof(plugin_parameters)/sizeof(*plugin_parameters);
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 014bf6d..246f423 100644 (file)
@@ -40,7 +40,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_txtinfo.c,v 1.9 2007/09/05 16:17:36 bernd67 Exp $
+ * $Id: olsrd_txtinfo.c,v 1.10 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 /*
@@ -336,32 +336,24 @@ static void ipc_print_routes(void)
 
 static void ipc_print_topology(void)
 {
-    int index;
-    struct tc_entry *entry;
-    struct topo_dst *dst_entry;
+    struct tc_entry *tc;
+    struct tc_edge_entry *tc_edge;
 
     ipc_sendf("Table: Topology\nDestination IP\tLast hop IP\tLQ\tILQ\tETX\n");
 
     /* Topology */  
-    for(index = 0; index < HASHSIZE; index++) {
-        /* For all TC entries */
-        entry = tc_table[index].next;
-        while(entry != &tc_table[index]) {
-            /* For all destination entries of that TC entry */
-            dst_entry = entry->destinations.next;
-            while(dst_entry != &entry->destinations) {
-                ipc_sendf( "%s\t%s\t%0.2f\t%0.2f\t%0.2f\n", 
-                           olsr_ip_to_string(&dst_entry->T_dest_addr),
-                           olsr_ip_to_string(&entry->T_last_addr), 
-                           dst_entry->link_quality,
-                           dst_entry->inverse_link_quality,
-                           (dst_entry->link_quality * dst_entry->inverse_link_quality) ? 1.0 / (dst_entry->link_quality * dst_entry->inverse_link_quality) : 0.0);
-               
-                dst_entry = dst_entry->next;
-           }
-            entry = entry->next;
-       }
-    }
+    OLSR_FOR_ALL_TC_ENTRIES(tc) {
+        OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+            ipc_sendf( "%s\t%s\t%0.2f\t%0.2f\t%0.2f\n", 
+                       olsr_ip_to_string(&tc_edge->T_dest_addr),
+                       olsr_ip_to_string(&tc->addr), 
+                       tc_edge->link_quality,
+                       tc_edge->inverse_link_quality,
+                       (tc_edge->link_quality * tc_edge->inverse_link_quality) ? 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality) : 0.0);
+
+        } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+    } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+
     ipc_sendf("\n");
 }
 
index 1c3fffd..c0c0110 100644 (file)
@@ -38,7 +38,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.50 2007/09/05 16:17:36 bernd67 Exp $
+ * $Id: lq_route.c,v 1.51 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 #include "defs.h"
 #include "lq_avl.h"
 #include "lq_route.h"
 
-struct olsr_spf_edge
-{
-  struct avl_node tree_node;
-  struct olsr_spf_vertex *dest;
-  float etx;
-};
-
-struct olsr_spf_vertex
-{
-  struct avl_node tree_node; /* node keyed by ip address */
-  struct avl_node cand_tree_node; /* node keyed by etx */
-  struct list_node path_list_node; /* SPF result list */
-  union olsr_ip_addr addr;
-  struct avl_tree edge_tree;
-  struct link_entry *next_hop; /* the link to the 1st hop neighbor */
-  float path_etx;
-  olsr_u8_t hops;
-};
-
 /*
  * avl_comp_etx
  *
@@ -103,7 +84,7 @@ avl_comp_etx (void *etx1, void *etx2)
  */
 static void
 olsr_spf_add_cand_tree (struct avl_tree *tree,
-                        struct olsr_spf_vertex *vert)
+                        struct tc_entry *vert)
 {
   vert->cand_tree_node.key = &vert->path_etx;
   vert->cand_tree_node.data = vert;
@@ -114,7 +95,7 @@ olsr_spf_add_cand_tree (struct avl_tree *tree,
               vert->path_etx);
 #endif
 
-  avl_insert(tree, &vert->cand_tree_node, 1);
+  avl_insert(tree, &vert->cand_tree_node, AVL_DUP);
 }
 
 /*
@@ -124,7 +105,7 @@ olsr_spf_add_cand_tree (struct avl_tree *tree,
  */
 static void
 olsr_spf_del_cand_tree (struct avl_tree *tree,
-                        struct olsr_spf_vertex *vert)
+                        struct tc_entry *vert)
 {
 
 #ifdef DEBUG
@@ -144,7 +125,7 @@ olsr_spf_del_cand_tree (struct avl_tree *tree,
 static void
 olsr_spf_add_path_list (struct list_node *head,
                         int *path_count,
-                        struct olsr_spf_vertex *vert)
+                        struct tc_entry *vert)
 {
   vert->path_list_node.data = vert;
 
@@ -160,149 +141,11 @@ olsr_spf_add_path_list (struct list_node *head,
 }
 
 /*
- * olsr_spf_add_vertex
- *
- * Add a node to the tree of all nodes in the network.
- */
-static struct olsr_spf_vertex *
-olsr_spf_add_vertex (struct avl_tree *vertex_tree,
-                     union olsr_ip_addr *addr, float path_etx)
-{
-  struct avl_node *node;
-  struct olsr_spf_vertex *vert;
-
-  // see whether this destination is already in our tree
-
-  node = avl_find(vertex_tree, addr);
-
-  if (node) {
-    return node->data;
-  }
-
-  // if it's not in our list, add it
-
-  vert = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra vertex");
-
-  vert->tree_node.data = vert;
-  vert->tree_node.key = &vert->addr;
-
-  COPY_IP(&vert->addr, addr);
-    
-  vert->path_etx = path_etx;
-  vert->next_hop = NULL;
-  vert->hops = 0;
-
-  avl_init(&vert->edge_tree, avl_comp_default);
-
-  avl_insert(vertex_tree, &vert->tree_node, 0);
-  return vert;
-}
-
-static struct olsr_spf_vertex *
-olsr_spf_add_edge (struct avl_tree *vertex_tree,
-                   union olsr_ip_addr *src, union olsr_ip_addr *dst,
-                   float etx)
-{
-  struct avl_node *node;
-  struct olsr_spf_vertex *svert;
-  struct olsr_spf_vertex *dvert;
-  struct olsr_spf_edge *edge;
-
-  // source lookup
-
-  node = avl_find(vertex_tree, src);
-
-  // source vertex does not exist
-
-  if (node == NULL)
-    return NULL;
-
-  svert = node->data;
-
-  // destination lookup
-
-  node = avl_find(vertex_tree, dst);
-
-  // destination vertex does not exist
-
-  if (node == NULL)
-    return NULL;
-
-  dvert = node->data;
-
-  // check for existing forward edge
-
-  if (avl_find(&svert->edge_tree, dst) == NULL)
-  {
-    // add forward edge
-
-    edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra forward edge");
-
-    edge->tree_node.data = edge;
-    edge->tree_node.key = &dvert->addr;
-
-    edge->dest = dvert;
-    edge->etx = etx;
-
-    avl_insert(&svert->edge_tree, &edge->tree_node, 0);
-  }
-
-  // check for existing inverse edge
-
-  if (avl_find(&dvert->edge_tree, src) == NULL)
-  {
-    // add inverse edge
-
-    edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra inverse edge");
-
-    edge->tree_node.data = edge;
-    edge->tree_node.key = &svert->addr;
-
-    edge->dest = svert;
-    edge->etx = etx;
-
-    avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
-  }
-
-  return svert;
-}
-
-static void olsr_free_everything(struct avl_tree *vertex_tree)
-{
-  struct avl_node *vert_node;
-  struct avl_node *edge_node;
-  struct olsr_spf_vertex *vert;
-  struct olsr_spf_edge *edge;
-
-  vert_node = avl_walk_first(vertex_tree);
-
-  // loop through all vertices
-
-  while (vert_node)
-  {
-    vert = vert_node->data;
-    edge_node = avl_walk_first(&vert->edge_tree);
-
-    // loop through all edges of the current vertex
-
-    while (edge_node != NULL)
-    {
-      edge = edge_node->data;
-      edge_node = avl_walk_next(edge_node);
-      free(edge);
-    }
-
-    vert_node = avl_walk_next(vert_node);
-    free(vert);
-  }
-}
-
-/*
  * olsr_spf_extract_best
  *
  * return the node with the minimum pathcost.
  */
-static struct olsr_spf_vertex *
+static struct tc_entry *
 olsr_spf_extract_best (struct avl_tree *tree)
 {
   struct avl_node *node;
@@ -313,8 +156,7 @@ olsr_spf_extract_best (struct avl_tree *tree)
 }
 
 
-#ifdef DEBUG
-static char *olsr_etx_to_string(float etx)
+char *olsr_etx_to_string(float etx)
 {
   static char buff[20];
 
@@ -324,7 +166,6 @@ static char *olsr_etx_to_string(float etx)
   snprintf(buff, 20, "%.6f", etx);
   return buff;
 }
-#endif
 
 
 /*
@@ -335,9 +176,10 @@ static char *olsr_etx_to_string(float etx)
  * path cost is better.
  */
 static void
-olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
+olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
 {
-  struct olsr_spf_edge *edge;
+  struct tc_entry *new_vert;
+  struct tc_edge_entry *tc_edge;
   struct avl_node *edge_node;
   float new_etx;
 
@@ -347,53 +189,77 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
               vert->path_etx);
 #endif
 
-  edge_node = avl_walk_first(&vert->edge_tree);
+  /*
+   * loop through all edges of this vertex.
+   */
+  for (edge_node = avl_walk_first(&vert->edge_tree);
+       edge_node;
+       edge_node = avl_walk_next(edge_node)) {
 
-  // loop through all edges of this vertex
+    tc_edge = edge_node->data;
 
-  while (edge_node != NULL)
-  {
-    edge = edge_node->data;
+    /*
+     * We are not interested in dead-end or dying edges.
+     */
+    if (!tc_edge->edge_inv || (tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
+#ifdef DEBUG
+      OLSR_PRINTF(1, "SPF:   ignoring edge %s\n",
+                  olsr_ip_to_string(&tc_edge->T_dest_addr));
+      if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
+        OLSR_PRINTF(1, "SPF:     edge down\n");
+      }
+      if (!tc_edge->edge_inv) {
+        OLSR_PRINTF(1, "SPF:     no inverse edge\n");
+      }
+#endif
+      continue;
+    }
 
-    // total quality of the path through this vertex to the
-    // destination of this edge
+    /*
+     * total quality of the path through this vertex
+     * to the destination of this edge
+     */
+    new_etx = vert->path_etx + tc_edge->etx;
 
-    new_etx = vert->path_etx + edge->etx;
+#ifdef DEBUG
+      OLSR_PRINTF(1, "SPF:   exploring edge %s, cost %s\n",
+                  olsr_ip_to_string(&(tc_edge->T_dest_addr)),
+                  olsr_etx_to_string(new_vert->path_etx));
+#endif
 
-    // if it's better than the current path quality of this
-    // edge's destination, then we've found a better path to
-    // this destination
+      /* 
+       * if it's better than the current path quality of this edge's
+       * destination node, then we've found a better path to this node.
+       */
+    new_vert = tc_edge->edge_inv->tc;
+    if (new_etx < new_vert->path_etx) {
 
-    if (new_etx < edge->dest->path_etx)
-    {
       /* if this node has been on the candidate tree delete it */
-      if (edge->dest->path_etx != INFINITE_ETX) {
-        olsr_spf_del_cand_tree(cand_tree, edge->dest);
+      if (new_vert->path_etx != INFINITE_ETX) {
+        olsr_spf_del_cand_tree(cand_tree, new_vert);
       }
 
       /* re-insert on candidate tree with the better metric */
-      edge->dest->path_etx = new_etx;
-      olsr_spf_add_cand_tree(cand_tree, edge->dest);
+      new_vert->path_etx = new_etx;
+      olsr_spf_add_cand_tree(cand_tree, new_vert);
 
       /* pull-up the next-hop and bump the hop count */
       if (vert->next_hop) {
-        edge->dest->next_hop = vert->next_hop;
+        new_vert->next_hop = vert->next_hop;
       }
-      edge->dest->hops = vert->hops + 1;
+      new_vert->hops = vert->hops + 1;
 
 #ifdef DEBUG
       OLSR_PRINTF(1, "SPF:   better path to %s, cost %s -> %s, via %s, hops %u\n",
-                  olsr_ip_to_string(&(edge->dest->addr)),
-                  olsr_etx_to_string(edge->dest->path_etx),
+                  olsr_ip_to_string(&new_vert->addr),
+                  olsr_etx_to_string(new_vert->path_etx),
                   olsr_etx_to_string(new_etx),
                   olsr_ip_to_string(vert->next_hop ?
                                     &vert->next_hop->neighbor_iface_addr : NULL),
-                  edge->dest->hops);
+                  new_vert->->hops);
 #endif
 
     }
-
-    edge_node = avl_walk_next(edge_node);
   }
 }
 
@@ -413,7 +279,7 @@ static void
 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
                    int *path_count)
 {
-  struct olsr_spf_vertex *vert;
+  struct tc_entry *vert;
 
   *path_count = 0;
 
@@ -433,133 +299,90 @@ olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
 void
 olsr_calculate_routing_table (void)
 {
-  struct avl_tree vertex_tree, cand_tree;
+  struct avl_tree cand_tree;
   struct list_node path_list;
   int i, plen, max_host_plen, path_count = 0;
-  struct tc_entry *tcsrc;
-  struct topo_dst *tcdst;
-  struct olsr_spf_vertex *vert, *myself;
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge;
+  struct tc_entry *vert;
   struct neighbor_entry *neigh;
   struct mid_address *mid_walker;
-  float etx;
   struct hna_entry *hna_gw;
   struct hna_net *hna;
-  struct neighbor_2_entry *neigh2;
   struct interface *inter;
   struct link_entry *link;
 
 #ifdef SPF_PROFILING
-  struct timeval t1, t2, t3, t4, t5, t6, spf_init, spf_run, route, kernel, cleanup, total;
+  struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
 
   gettimeofday(&t1, NULL);
 #endif
 
   max_host_plen = olsr_host_rt_maxplen();
 
-  // initialize the graph
-
-  avl_init(&vertex_tree, avl_comp_default);
+  /*
+   * Prepare the candidate tree and result list.
+   */
   avl_init(&cand_tree, avl_comp_etx);
   list_head_init(&path_list);
-
   olsr_bump_routingtree_version();
 
-  // add ourselves to the vertex and candidate tree
-
-  myself = olsr_spf_add_vertex(&vertex_tree, &olsr_cnf->main_addr, ZERO_ETX);
-  olsr_spf_add_cand_tree(&cand_tree, myself);
-
   /*
-   * Add our neighbours.
+   * Initialize vertices in the lsdb.
    */
-  for (i = 0; i < HASHSIZE; i++)
-    for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
-         neigh = neigh->next) {
-
-      if (neigh->status != SYM)
-        continue;
-
-      olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
-    }
-
-  // add our two-hop neighbours
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    tc->next_hop = NULL;
+    tc->path_etx = INFINITE_ETX;
+    tc->hops = 0;
+  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
-  for (i = 0; i < HASHSIZE; i++)
-    for (neigh2 = two_hop_neighbortable[i].next;
-         neigh2 != &two_hop_neighbortable[i];
-         neigh2 = neigh2->next) {
-
-      olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
-    }
-  // add remaining vertices
-
-  for (i = 0; i < HASHSIZE; i++)
-    for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
-    {
-      // add source
-
-      olsr_spf_add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
-
-      // add destinations of this source
-
-      for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
-           tcdst = tcdst->next)
-        olsr_spf_add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
-    }
-
-  // add edges to and from our neighbours
+  /*
+   * zero ourselves and add us to the candidate tree.
+   */
+  tc_myself->path_etx = ZERO_ETX;
+  olsr_spf_add_cand_tree(&cand_tree, tc_myself);
 
+  /*
+   * add edges to and from our neighbours.
+   */
   for (i = 0; i < HASHSIZE; i++)
     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
          neigh = neigh->next) {
 
       if (neigh->status == SYM) {
 
+        tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
        if (!link) {
+
+          /*
+           * If there is no best link to this neighbor
+           * and we had an edge before then flush the edge.
+           */
+          if (tc_edge) {
+            olsr_delete_tc_edge_entry(tc_edge);
+          }
          continue;
         }
 
-        if (olsr_cnf->lq_level < 2) {
-          /* for non-lq the etx is always 1.0 */
-          vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
-                                   &olsr_cnf->main_addr, 1.0 );
-          vert->next_hop = link;
-
-        } else if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
-                   link->neigh_link_quality2 >= MIN_LINK_QUALITY) {
-            
-          etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
-
-          vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
-                                     &olsr_cnf->main_addr, etx);
-          vert->next_hop = link;
+        /*
+         * Set the next-hops of our neighbors. 
+         */
+        if (!tc_edge) {
+          tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
+                                           0, link->last_htime,
+                                           link->loss_link_quality2,
+                                           link->neigh_link_quality2);
+        } else {
+          tc_edge->link_quality = link->loss_link_quality2;
+          tc_edge->inverse_link_quality = link->neigh_link_quality2;
+          olsr_calc_tc_edge_entry_etx(tc_edge);
         }
-      }
-    }
-
-  /* add remaining edges from TC messages */
-
-  for (i = 0; i < HASHSIZE; i++)
-    for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
-      for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
-           tcdst = tcdst->next) {
-
-        if (olsr_cnf->lq_level < 2) {
-
-          /* for non-lq the etx is always 1.0 */
-          olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
-                            &tcsrc->T_last_addr, 1.0);
-
-        } else if (tcdst->link_quality >= MIN_LINK_QUALITY &&
-                   tcdst->inverse_link_quality >= MIN_LINK_QUALITY) {
-
-          etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
-
-          olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
-                            &tcsrc->T_last_addr, etx);
+        if (tc_edge->edge_inv) {
+          tc_edge->edge_inv->tc->next_hop = link;
         }
       }
+    }
 
 #ifdef SPF_PROFILING
   gettimeofday(&t2, NULL);
@@ -651,23 +474,17 @@ olsr_calculate_routing_table (void)
   gettimeofday(&t5, NULL);
 #endif
 
-  /* free the SPF graph */
-
-  olsr_free_everything(&vertex_tree);
-
 #ifdef SPF_PROFILING
-  gettimeofday(&t6, NULL);
-
   timersub(&t2, &t1, &spf_init);
   timersub(&t3, &t2, &spf_run);
   timersub(&t4, &t3, &route);
   timersub(&t5, &t4, &kernel);
-  timersub(&t6, &t5, &cleanup);
-  timersub(&t6, &t1, &total);
-  olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern/cleanup): %d, %d, %d, %d, %d, %d\n",
+  timersub(&t5, &t1, &total);
+  olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
+              "%d, %d, %d, %d, %d\n",
               path_count, routingtree.count,
               (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
-              (int)route.tv_usec, (int)kernel.tv_usec,  (int)cleanup.tv_usec);
+              (int)route.tv_usec, (int)kernel.tv_usec);
 #endif
 }
 
index 5cdf09c..4a0887f 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.h,v 1.5 2007/09/05 16:11:10 bernd67 Exp $
+ * $Id: lq_route.h,v 1.6 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 #ifndef _LQ_ROUTE_H
@@ -47,5 +47,6 @@
 #define MIN_LINK_QUALITY 0.01
 
 void olsr_calculate_routing_table(void);
+char *olsr_etx_to_string(float);
 
 #endif
index 88cebb8..efd2d37 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: process_package.c,v 1.41 2007/08/02 22:07:19 bernd67 Exp $
+ * $Id: process_package.c,v 1.42 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 
@@ -228,8 +228,8 @@ olsr_tc_tap(struct tc_message *message, struct interface *in_if,
       goto forward;
     }
 
-  OLSR_PRINTF(3, "Processing TC from %s\n",
-              olsr_ip_to_string(&message->originator));
+  OLSR_PRINTF(3, "Processing TC from %s, seq 0x%04x\n",
+              olsr_ip_to_string(&message->originator), message->ansn);
 
   /*
    *      If the sender interface (NB: not originator) of this message
@@ -272,10 +272,6 @@ olsr_tc_tap(struct tc_message *message, struct interface *in_if,
       /* Update destinations */
       if(olsr_tc_update_mprs(tc_last, message))
         changes_topology = OLSR_TRUE;
-
-      /* Delete possible empty TC entry */
-      if(changes_topology)
-        olsr_tc_delete_entry_if_empty(tc_last);
     }
 
   else
index c78d333..c8fa4e0 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
+ * LSDB rewrite (c) 2007, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: tc_set.c,v 1.27 2007/08/02 22:07:19 bernd67 Exp $
+ * $Id: tc_set.c,v 1.28 2007/09/13 15:31:59 bernd67 Exp $
  */
 
-
 #include "tc_set.h"
 #include "olsr.h"
 #include "scheduler.h"
 #include "lq_route.h"
+#include "lq_avl.h"
+#include "assert.h"
 
-
-struct tc_entry tc_table[HASHSIZE];
-
+/* Root of the link state database */
+struct avl_tree tc_tree;
+struct tc_entry *tc_myself; /* Shortcut to ourselves */
 
 /**
  * Initialize the topology set
  *
  */
-
 int
 olsr_init_tc(void)
 {
-  int idx;
   OLSR_PRINTF(5, "TC: init topo\n");
 
   olsr_register_timeout_function(&olsr_time_out_tc_set);
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      tc_table[idx].next = &tc_table[idx];
-      tc_table[idx].prev = &tc_table[idx];
-    }
+  avl_init(&tc_tree, avl_comp_default);
 
+  /*
+   * Add a TC entry for ourselves.
+   */
+  tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
   return 1;
 }
 
-
 /**
- *Delete a TC entry if it has no associated
- *destinations
+ * Delete a TC entry.
  *
- *@param entry the TC entry to check and possibly delete
+ * @param entry the TC entry to delete
  *
- *@return 1 if entry deleted 0 if not
  */
-
-int
-olsr_tc_delete_entry_if_empty(struct tc_entry *entry)
+static void
+olsr_delete_tc_entry(struct tc_entry *tc)
 {
 
-  //OLSR_PRINTF(1, "TC: del entry if empty\n");
-
-  if(entry->destinations.next == &entry->destinations)
-    {
-      /* dequeue */
-      DEQUEUE_ELEM(entry);
-      //entry->prev->next = entry->next;
-      //entry->next->prev = entry->prev;
-      OLSR_PRINTF(1, "TC-SET: Deleting empty entry %s ->\n", olsr_ip_to_string(&entry->T_last_addr));
-      free(entry);
-      return 1;
-    }
-  return 0;
-}
+#if 0
+  OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&tc->addr));
+#endif
 
+  /* The edgetree must be empty before */
+  assert(!tc->edge_tree.count);
 
+  avl_delete(&tc_tree, &tc->vertex_node);
+  free(tc);
+}
 
 /**
- * Look up a entry from the TC tabe based
- * on address
+ * Look up a entry from the TC tree based on address
  *
- *@param adr the address to look for
- *
- *@return the entry found or NULL
+ * @param adr the address to look for
+ * @return the entry found or NULL
  */
-
 struct tc_entry *
 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
 {
-  struct tc_entry *entries;
-  olsr_u32_t hash;
+  struct avl_node *node;
 
-  //OLSR_PRINTF(1, "TC: lookup entry\n");
+#if 0
+  OLSR_PRINTF(1, "TC: lookup entry\n");
+#endif
 
-  hash = olsr_hashing(adr);
+  node = avl_find(&tc_tree, adr);
 
-  for(entries = tc_table[hash].next; 
-      entries != &tc_table[hash]; 
-      entries = entries->next)
-    {
-      //printf("TC lookup checking: %s\n", olsr_ip_to_string(&entries->T_last_addr));
-      if(COMP_IP(adr, &entries->T_last_addr))
-       return entries;
-    }
+  if (node) {
+    return node->data;
+  }
 
   return NULL;
 }
 
-
 /**
- *Add a new tc_entry to the tc set
- *
- *@param (last)adr address of the entry
+ * Grab the next topology entry.
  *
- *@return a pointer to the created entry
+ * @param adr the address to look for
+ * @return the entry found or NULL
  */
+struct tc_entry *
+olsr_getnext_tc_entry(struct tc_entry *tc)
+{
+  struct avl_node *node;
+
+  node = avl_walk_next(&tc->vertex_node);
+
+  if (node) {
+    return node->data;
+  }
 
+  return NULL;
+}
+
+/**
+ * Add a new tc_entry to the tc tree
+ *
+ * @param (last)adr address of the entry
+ * @return a pointer to the created entry
+ */
 struct tc_entry *
 olsr_add_tc_entry(union olsr_ip_addr *adr)
 {
-  struct tc_entry *new_entry;
-  olsr_u32_t hash;
+  struct tc_entry *tc;
 
-  OLSR_PRINTF(1, "TC: adding entry %s\n", olsr_ip_to_string(adr));
+#if 0
+  OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(adr));
+#endif
 
-  hash = olsr_hashing(adr);
-
-  new_entry = olsr_malloc(sizeof(struct tc_entry), "New TC entry");
+  tc = olsr_malloc(sizeof(struct tc_entry), "add TC entry");
+  if (!tc) {
+    return NULL;
+  }
 
   /* Fill entry */
-  COPY_IP(&new_entry->T_last_addr, adr);
-  new_entry->destinations.next = &new_entry->destinations;
-  new_entry->destinations.prev = &new_entry->destinations;
+  COPY_IP(&tc->addr, adr);
+  tc->vertex_node.data = tc;
+  tc->vertex_node.key = &tc->addr;
+
+  /*
+   * Insert into the global tc tree.
+   */
+  avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
 
-  /* Queue entry */
-  QUEUE_ELEM(tc_table[hash], new_entry);
   /*
-  new_entry->next = tc_table[hash].next;
-  new_entry->prev = tc_table[hash].next->prev;
-  tc_table[hash].next->prev = new_entry;
-  tc_table[hash].next = new_entry;
-  */
+   * Initialize subtree for further edges to come.
+   */
+  avl_init(&tc->edge_tree, avl_comp_default);
 
-  return new_entry;
+  return tc;
 }
 
+/**
+ * format a tc_edge contents into a buffer
+ */
+char *
+olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
+{
+  struct tc_entry *tc;
+  static char buff[128];
+
+  tc = tc_edge->tc;
+
+  snprintf(buff, sizeof(buff),
+           "%s > %s, lq %.3f, inv-lq %.3f, etx %.3f",
+           olsr_ip_to_string(&tc->addr),
+           olsr_ip_to_string(&tc_edge->T_dest_addr),
+           tc_edge->link_quality,
+           tc_edge->inverse_link_quality,
+           tc_edge->etx);
+
+  return buff;
+}
 
 /**
- *Delete all destinations that have a
- *lower ANSN than the one in the message
- *
- *@param entry the entry to delete destenations from
- *@param msg the message to fetch the ANSN from
+ * Set the TC edge expiration timer.
  *
- *@return 1 if any destinations were deleted 0 if not
+ * all timer setting shall be done using this function since
+ * it does also the correct insertion and sorting in the timer tree.
+ * The timer param is a relative timer expressed in milliseconds.
  */
+static void
+olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
+{
+  tc_edge->T_time = GET_TIMESTAMP(timer);
+}
 
-int
-olsr_tc_delete_mprs(struct tc_entry *entry, struct tc_message *msg)
+/*
+ * If the edge does not have a minimum acceptable link quality
+ * set the etx cost to infinity such that it gets ignored during
+ * SPF calculation.
+ */
+void
+olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
 {
-  struct topo_dst *tmp_dsts, *dst_to_del;
-  int retval;
+  if (tc_edge->link_quality >= MIN_LINK_QUALITY &&
+      tc_edge->inverse_link_quality >= MIN_LINK_QUALITY) {
+        
+    tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
+  } else {
+    tc_edge->etx = INFINITE_ETX;
+  }
+}
 
-  //OLSR_PRINTF(5, "TC: deleting MPRS\n");
+/**
+ * Add a new tc_edge_entry to the tc_edge_tree
+ *
+ * @param (last)adr address of the entry
+ * @return a pointer to the created entry
+ */
+struct tc_edge_entry *
+olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
+                       u_int16_t ansn, unsigned int vtime,
+                       float link_quality, float neigh_link_quality)
+{
+  struct tc_entry *tc_neighbor;
+  struct tc_edge_entry *tc_edge, *tc_edge_inv;
 
-  tmp_dsts = entry->destinations.next;
-  retval = 0;
+  tc_edge = olsr_malloc(sizeof(struct tc_edge_entry), "add TC edge");
+  if (!tc_edge) {
+    return NULL;
+  }
+  memset(tc_edge, 0, sizeof(struct tc_edge_entry));
 
-  while(tmp_dsts != &entry->destinations)
-    {
-      if(SEQNO_GREATER_THAN(msg->ansn, tmp_dsts->T_seq))
-       {
-         /* Delete entry */
-         dst_to_del = tmp_dsts;
-         tmp_dsts = tmp_dsts->next;
+  /* Fill entry */
+  COPY_IP(&tc_edge->T_dest_addr, addr);
+  olsr_set_tc_edge_timer(tc_edge, vtime*1000);
+  tc_edge->T_seq = ansn;
+  tc_edge->edge_node.data = tc_edge;
+  tc_edge->edge_node.key = &tc_edge->T_dest_addr;
 
-         /* dequeue */
-         DEQUEUE_ELEM(dst_to_del);
+  if (olsr_cnf->lq_level > 0) {
 
-         free(dst_to_del);
-         retval = 1;
-       }
-      else
-       tmp_dsts = tmp_dsts->next;
+    tc_edge->link_quality = neigh_link_quality;
+    tc_edge->inverse_link_quality = link_quality;
 
-    }
+  } else {
 
-  return retval;
-}
+    /*
+     * Set the link quality to 1.0 to mimikry a hopcount alike
+     * behaviour for nodes not supporting the LQ extensions.
+     */
+    tc_edge->link_quality = 1.0;
+    tc_edge->inverse_link_quality = 1.0;
+  }
 
+  /*
+   * Insert into the edge tree.
+   */
+  avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
 
-/**
- *Update the destinations registered on an entry.
- *Creates new dest-entries if not registered.
- *Bases update on a receivied TC message
- *
- *@param entry the TC entry to check
- *@msg the TC message to update by
- *
- *@return 1 if entries are added 0 if not
- */
+  /*
+   * Connect backpointer.
+   */
+  tc_edge->tc = tc;
 
-int
-olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
-{
-  struct tc_mpr_addr *mprs;
-  struct topo_dst *new_topo_dst, *existing_dst;
-  int retval;
+#if 0
+  OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
+#endif
 
-  //OLSR_PRINTF(1, "TC: update MPRS\n");
+  /*
+   * Check if the neighboring router and the inverse edge is in the lsdb.
+   * Create short cuts to the inverse edge for faster SPF execution.
+   */
+  tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
+  if (tc_neighbor) {
+
+#if 0
+    OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
+                olsr_ip_to_string(&tc_neighbor->addr));
+#endif
+
+    tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
+    if (tc_edge_inv) {
+
+#if 0
+      OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
+                  olsr_ip_to_string(&tc_edge_inv->T_dest_addr));
+#endif
+
+      /*
+       * Connect the edges mutually.
+       */
+      tc_edge_inv->edge_inv = tc_edge;
+      tc_edge->edge_inv = tc_edge_inv;
 
-  retval = 0;
+    }
+  }
 
+  /*
+   * Update the etx.
+   */
+  olsr_calc_tc_edge_entry_etx(tc_edge);
 
-  mprs = msg->multipoint_relay_selector_address;
-  
-  /* Add all the MPRs */
+  return tc_edge;
+}
 
-  while(mprs != NULL)
-    {
-      existing_dst = olsr_tc_lookup_dst(entry, &mprs->address);
 
-      if(existing_dst == NULL)
-       {
-         /* New entry */
-         new_topo_dst = olsr_malloc(sizeof(struct topo_dst), "add TC destination");
+/**
+ * Delete a TC edge entry.
+ *
+ * @param tc the TC entry
+ * @param tc_edge the TC edge entry
+ */
+void
+olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
+{
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge_inv;
 
-         memset(new_topo_dst, 0, sizeof(struct topo_dst));
+#if 0
+  OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
+#endif
 
-         COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
-         new_topo_dst->T_time = GET_TIMESTAMP(msg->vtime*1000);
-         new_topo_dst->T_seq = msg->ansn;
+  tc = tc_edge->tc;
+  avl_delete(&tc->edge_tree, &tc_edge->edge_node);
 
-          if (olsr_cnf->lq_level > 0)
-            {
-              new_topo_dst->link_quality = mprs->neigh_link_quality;
-              new_topo_dst->inverse_link_quality = mprs->link_quality;
+  /*
+   * Clear the backpointer of our inverse edge.
+   */
+  tc_edge_inv = tc_edge->edge_inv;
+  if (tc_edge_inv) {
+    tc_edge_inv->edge_inv = NULL;
+  }
 
-              new_topo_dst->saved_link_quality = new_topo_dst->link_quality;
-              new_topo_dst->saved_inverse_link_quality =
-                new_topo_dst->inverse_link_quality;
-            }
+  /*
+   * Delete the tc_entry if the last edge is gone.
+   */
+  if (!tc_edge->tc->edge_tree.count) {
+
+    /*
+     * Only remove remote tc entries.
+     */
+    if (tc_edge->tc != tc_myself) {
+      olsr_delete_tc_entry(tc_edge->tc);
+    }
+  }
 
-         /* Add to queue */
-         new_topo_dst->prev = &entry->destinations;
-         new_topo_dst->next = entry->destinations.next;
-         entry->destinations.next->prev = new_topo_dst;
-         entry->destinations.next = new_topo_dst;
+  free(tc_edge);
+}
 
-         retval = 1;
-       }
-      else
-       {
-         /* Update entry */
-         existing_dst->T_time = GET_TIMESTAMP(msg->vtime*1000);
-         existing_dst->T_seq = msg->ansn;
 
-          if (olsr_cnf->lq_level > 0)
-            {
-              double saved_lq, rel_lq;
+/**
+ * Delete all destinations that have a
+ * lower ANSN than the one in the message
+ *
+ * @param tc the entry to delete edges from
+ * @param msg the message to fetch the ANSN from
+ * @return 1 if any destinations were deleted 0 if not
+ */
+int
+olsr_tc_delete_mprs(struct tc_entry *tc, struct tc_message *msg)
+{
+  struct tc_edge_entry *tc_edge;
+  int retval;
 
-              saved_lq = existing_dst->saved_link_quality;
+#if 0
+  OLSR_PRINTF(5, "TC: deleting MPRS\n");
+#endif
 
-              if (saved_lq == 0.0)
-                saved_lq = -1.0;
+  retval = 0;
 
-              existing_dst->link_quality = mprs->neigh_link_quality;
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+
+    if (SEQNO_GREATER_THAN(msg->ansn, tc_edge->T_seq)) {
+
+      /*
+       * Do not delete the edge now, just mark the edge as down.
+       * Downed edges will be ignored by the SPF computation.
+       * It could be that a TC message spans across multiple packets,
+       * which causes an edge delete followed by an edge add.
+       * If the edge gets refreshed in subsequent packets then we have
+       * avoided a two edge transistion.
+       * If the edge really went away then after the garbace collection
+       * timer has expired olsr_time_out_tc_set() will do the needful.
+       */
+      tc_edge->flags |= OLSR_TC_EDGE_DOWN;
+      olsr_set_tc_edge_timer(tc_edge, OLSR_TC_EDGE_GC_TIME);
+      retval = 1;
+    }
+  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
 
-              rel_lq = existing_dst->link_quality / saved_lq;
+  return retval;
+}
 
-              if (rel_lq > 1.1 || rel_lq < 0.9)
-                {
-                  existing_dst->saved_link_quality =
-                    existing_dst->link_quality;
+/*
+ * Determine if a etx change was more than 10%
+ * Need to know this for triggering a SPF calculation.
+ */
+static olsr_bool
+olsr_etx_significant_change(float etx1, float etx2)
+{
+  float rel_lq;
 
-                  if (msg->hop_count <= olsr_cnf->lq_dlimit)
-                    retval = 1;
+  if (etx1 == 0.0 || etx2 == 0.0) {
+    return OLSR_TRUE;
+  }
 
-                  else
-                    OLSR_PRINTF(3, "Skipping Dijkstra (4)\n");
-                }
+  rel_lq = etx1 / etx2;
 
-              saved_lq = existing_dst->saved_inverse_link_quality;
+  if (rel_lq > 1.1 || rel_lq < 0.9) {
+    return OLSR_TRUE;
+  }
 
-              if (saved_lq == 0.0)
-                saved_lq = -1.0;
+  return OLSR_FALSE;
+}
 
-              existing_dst->inverse_link_quality = mprs->link_quality;
+/**
+ * Update the destinations registered on an entry.
+ * Creates new dest-entries if not registered.
+ * Bases update on a receivied TC message
+ *
+ * @param entry the TC entry to check
+ * @msg the TC message to update by
+ * @return 1 if entries are added 0 if not
+ */
+int
+olsr_tc_update_mprs(struct tc_entry *tc, struct tc_message *msg)
+{
+  struct tc_mpr_addr *mprs;
+  struct tc_edge_entry *tc_edge;
+  int edge_change;
 
-              rel_lq = existing_dst->inverse_link_quality / saved_lq;
+#if 0
+  OLSR_PRINTF(1, "TC: update MPRS\n");
+#endif
 
-              if (rel_lq > 1.1 || rel_lq < 0.9)
-                {
-                  existing_dst->saved_inverse_link_quality =
-                    existing_dst->inverse_link_quality;
+  edge_change = 0;
 
-                  if (msg->hop_count <= olsr_cnf->lq_dlimit)
-                    retval = 1;
+  mprs = msg->multipoint_relay_selector_address;
+  
+  /* Add all the MPRs */
 
-                  else
-                    OLSR_PRINTF(3, "Skipping Dijkstra (5)\n");
-                }
-            }
-       }
+  while (mprs) {
+
+    /* First check if we know this edge */
+    tc_edge = olsr_lookup_tc_edge(tc, &mprs->address);
+
+    if(!tc_edge) {
+      
+      /*
+       * Yet unknown - create it.
+       */
+      olsr_add_tc_edge_entry(tc, &mprs->address, msg->ansn,
+                             (unsigned int )msg->vtime,
+                             mprs->link_quality, mprs->neigh_link_quality);
+      edge_change = 1;
+
+    } else {
+
+      /*
+       * We know this edge - Update entry.
+       */
+      olsr_set_tc_edge_timer(tc_edge, msg->vtime*1000);
+      tc_edge->T_seq = msg->ansn;
+
+      /*
+       * Clear the (possibly set) down flag.
+       */
+      tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
+
+      /*
+       * Determine if the etx change is meaningful enough
+       * in order to trigger a SPF calculation.
+       */
+      if (olsr_etx_significant_change(tc_edge->link_quality,
+                                      mprs->neigh_link_quality)) {
+
+        if (msg->hop_count <= olsr_cnf->lq_dlimit)
+          edge_change = 1;
+      }
+      tc_edge->link_quality = mprs->neigh_link_quality;
+
+      if (olsr_etx_significant_change(tc_edge->inverse_link_quality,
+                                      mprs->link_quality)) {
+
+        if (msg->hop_count <= olsr_cnf->lq_dlimit)
+          edge_change = 1;
+      }
+      tc_edge->inverse_link_quality = mprs->link_quality;
+
+      /*
+       * Update the etx.
+       */
+      olsr_calc_tc_edge_entry_etx(tc_edge);
+
+#if 0
+      if (edge_change) {          
+        OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
+                    olsr_tc_edge_to_string(tc_edge));
+      }
+#endif
 
-      mprs = mprs->next;
     }
+    mprs = mprs->next;
+  }
 
-  return retval;
+  return edge_change;
 }
 
-
-
 /**
- *Lookup a destination in a TC entry
+ * Lookup an edge hanging off a TC entry.
  *
- *@param entry the entry to check
- *@param dst_addr the destination address to check for
- *
- *@return a pointer to the topo_dst found - or NULL
+ * @param entry the entry to check
+ * @param dst_addr the destination address to check for
+ * @return a pointer to the tc_edge found - or NULL
  */
-struct topo_dst *
-olsr_tc_lookup_dst(struct tc_entry *entry, union olsr_ip_addr *dst_addr)
+struct tc_edge_entry *
+olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
 {
-  struct topo_dst *dsts;
+  struct avl_node *edge_node;
   
-  //OLSR_PRINTF(1, "TC: lookup dst\n");
+#if 0
+  OLSR_PRINTF(1, "TC: lookup dst\n");
+#endif
+
+  edge_node = avl_find(&tc->edge_tree, edge_addr);
+
+  if (edge_node) {
+    return edge_node->data;
+  }
 
-  for(dsts = entry->destinations.next; 
-      dsts != &entry->destinations; 
-      dsts = dsts->next)
-    {
-      if(COMP_IP(dst_addr, &dsts->T_dest_addr))
-       return dsts;
-    }
   return NULL;
 }
 
 /**
- * Time out entries
+ * Walk the timers and time out entries.
  *
- *@return nada
+ * @return nada
  */
-
 void
 olsr_time_out_tc_set(void)
 {
-  int idx;
-
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      /* For all TC entries */
-      struct tc_entry *entry = tc_table[idx].next;
-      while(entry != &tc_table[idx])
-       {
-          struct tc_entry *entry2;
-         //printf("INDEX: %d\n", idx);
-         /* For all destination entries of that TC entry */
-         int deleted = 0;
-         struct topo_dst *dst_entry = entry->destinations.next;
-         while(dst_entry != &entry->destinations)
-           {
-             /* If timed out - delete */
-             if(TIMED_OUT(dst_entry->T_time))
-               {
-                  struct topo_dst *dst_to_delete;
-                 deleted = 1;
-                 /* Dequeue */
-                 DEQUEUE_ELEM(dst_entry);
-                 dst_to_delete = dst_entry;
-                 dst_entry = dst_entry->next;
-
-                 /* Delete */
-                 free(dst_to_delete);
-
-                 changes_topology = OLSR_TRUE;
-
-               }
-             else
-               dst_entry = dst_entry->next;
-           }
-         /* Delete entry if no destinations */
-         entry2 = entry;
-         entry = entry->next;
-         if(deleted)
-           olsr_tc_delete_entry_if_empty(entry2);
-       }
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge;
+
+  OLSR_FOR_ALL_TC_ENTRIES(tc)
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+
+    /*
+     * Delete outdated edges.
+     */
+    if(TIMED_OUT(tc_edge->T_time)) {
+      olsr_delete_tc_edge_entry(tc_edge);
+      changes_topology = OLSR_TRUE;
     }
+  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+  OLSR_FOR_ALL_TC_ENTRIES_END(tc)
 }
 
-
 /**
- *Print the topology table to stdout
+ * Print the topology table to stdout
  */
 int
 olsr_print_tc_table(void)
 {
-  int i;
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge;
   char *fstr;
   float etx;
   
@@ -443,26 +600,28 @@ olsr_print_tc_table(void)
       fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
     }
 
-  for (i = 0; i < HASHSIZE; i++)
-    {
-      struct tc_entry *entry;
-      for(entry = tc_table[i].next;entry != &tc_table[i];entry = entry->next)
-        {
-          struct topo_dst *dst_entry;
-          for(dst_entry = entry->destinations.next;dst_entry != &entry->destinations;dst_entry = dst_entry->next)
-            {
-              if (dst_entry->link_quality < MIN_LINK_QUALITY ||
-                  dst_entry->inverse_link_quality < MIN_LINK_QUALITY)
-                etx = 0.0;
-              else
-                etx = 1.0 / (dst_entry->link_quality * dst_entry->inverse_link_quality);
-
-              OLSR_PRINTF(1, fstr, olsr_ip_to_string(&entry->T_last_addr),
-                          olsr_ip_to_string(&dst_entry->T_dest_addr),
-                          dst_entry->link_quality, dst_entry->inverse_link_quality,
-                          etx);
-            }
-        }
-    }
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+
+      if (tc_edge->link_quality < MIN_LINK_QUALITY ||
+          tc_edge->inverse_link_quality < MIN_LINK_QUALITY) {
+        etx = 0.0;
+      } else {
+        etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
+      }
+
+      OLSR_PRINTF(1, fstr, olsr_ip_to_string(&tc->addr),
+                  olsr_ip_to_string(&tc_edge->T_dest_addr),
+                  tc_edge->link_quality, tc_edge->inverse_link_quality, etx);
+
+    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+
   return 1;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 0c16691..708c73b 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
+ * LSDB rewrite (c) 2007, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -36,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: tc_set.h,v 1.15 2005/05/29 12:47:46 br1 Exp $
+ * $Id: tc_set.h,v 1.16 2007/09/13 15:31:59 bernd67 Exp $
  */
 
 #ifndef _OLSR_TOP_SET
 #include "defs.h"
 #include "packet.h"
 
-struct topo_dst
+/*
+ * This file holds the definitions for the link state database.
+ * The lsdb consists of nodes and edges.
+ * During input parsing all nodes and edges are extracted and syntesized.
+ * The SPF calculation operates on these datasets.
+ */
+
+struct tc_edge_entry
 {
-  union olsr_ip_addr T_dest_addr;
-  clock_t            T_time;
-  olsr_u16_t         T_seq;
-  struct topo_dst   *next;
-  struct topo_dst   *prev;
-  double             link_quality;
-  double             inverse_link_quality;
-  double             saved_link_quality;
-  double             saved_inverse_link_quality;
+  struct avl_node    edge_node; /* edge_tree node in tc_entry */
+  union olsr_ip_addr T_dest_addr; /* edge_node key */
+  struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
+  struct tc_entry    *tc; /* backpointer to owning tc entry */
+  clock_t            T_time; /* expiration timer, timer_node key */
+  olsr_u16_t         T_seq; /* sequence number */
+  olsr_u16_t         flags; /* misc flags */
+  float              etx; /* metric used for SPF calculation */
+  float              link_quality;
+  float              inverse_link_quality;
 };
 
+#define OLSR_TC_EDGE_DOWN (1 <<  0) /* this edge is down */
+
+/*
+ * Garbage collection time for downed edges
+ */
+#define OLSR_TC_EDGE_GC_TIME 15*1000 /* milliseconds */
 
 struct tc_entry
 {
-  union olsr_ip_addr T_last_addr;
-  struct topo_dst    destinations;
-  struct tc_entry   *next;
-  struct tc_entry   *prev;
+  struct avl_node    vertex_node; /* node keyed by ip address */
+  struct avl_node    cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
+  struct list_node   path_list_node; /* SPF result list */
+  union olsr_ip_addr addr; /* vertex_node key */
+  struct avl_tree    edge_tree; /* subtree for edges */
+  struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
+  float              path_etx; /* SPF calculated distance, cand_tree_node key */
+  olsr_u8_t          hops; /* SPF calculated hopcount */
 };
 
-
-/* Queue */
-extern struct tc_entry tc_table[HASHSIZE];
-
-
-int
-olsr_init_tc(void);
-
-
-int
-olsr_tc_delete_mprs(struct tc_entry *, struct tc_message *);
-
-
-struct tc_entry *
-olsr_lookup_tc_entry(union olsr_ip_addr *);
-
-
-struct topo_dst *
-olsr_tc_lookup_dst(struct tc_entry *, union olsr_ip_addr *);
-
-
-int
-olsr_tc_delete_entry_if_empty(struct tc_entry *);
-
-
-struct tc_entry *
-olsr_add_tc_entry(union olsr_ip_addr *);
-
-
-int
-olsr_tc_update_mprs(struct tc_entry *, struct tc_message *);
-
-int
-olsr_print_tc_table(void);
-
-void
-olsr_time_out_tc_set(void);
+/*
+ * macros for traversing the vertices and edges in the link state database.
+ * it is recommended to use this because it hides all the internal
+ * datastructure from the callers.
+ *
+ * the loop prefetches the next node in order to not loose context if
+ * for example the caller wants to delete the current entry.
+ */
+#define OLSR_FOR_ALL_TC_ENTRIES(tc) \
+{ \
+  struct avl_node *tc_tree_node, *next_tc_tree_node; \
+  for (tc_tree_node = avl_walk_first(&tc_tree); \
+    tc_tree_node; tc_tree_node = next_tc_tree_node) { \
+    next_tc_tree_node = avl_walk_next(tc_tree_node); \
+    tc = tc_tree_node->data;
+#define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
+
+#define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
+{ \
+  struct avl_node *tc_edge_node, *next_tc_edge_node; \
+  for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
+    tc_edge_node; tc_edge_node = next_tc_edge_node) { \
+    next_tc_edge_node = avl_walk_next(tc_edge_node); \
+    tc_edge = tc_edge_node->data;
+#define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
+
+extern struct avl_tree tc_tree;
+extern struct tc_entry *tc_myself;
+
+int olsr_init_tc(void);
+int olsr_tc_delete_mprs(struct tc_entry *, struct tc_message *);
+int olsr_tc_update_mprs(struct tc_entry *, struct tc_message *);
+int olsr_print_tc_table(void);
+void olsr_time_out_tc_set(void);
+
+/* tc_entry manipulation */
+struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
+struct tc_entry *olsr_add_tc_entry(union olsr_ip_addr *);
+struct tc_entry *olsr_getnext_tc_entry(struct tc_entry *);
+
+/* tc_edge_entry manipulation */
+char *olsr_tc_edge_to_string(struct tc_edge_entry *);
+struct tc_edge_entry *olsr_lookup_tc_edge(struct tc_entry *,
+                                          union olsr_ip_addr *);
+struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *,
+                                             union olsr_ip_addr *, u_int16_t,
+                                             unsigned int, float, float);
+void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
+void olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */