Major Changes:
[olsrd.git] / src / tc_set.c
index b6f8e92..0d0ba4e 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
- * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
+ * 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.19 2004/12/19 12:20:00 kattemat Exp $
+ * $Id: tc_set.c,v 1.38 2007/11/29 00:49:39 bernd67 Exp $
  */
 
-
 #include "tc_set.h"
+#include "ipcalc.h"
+#include "mid_set.h"
+#include "link_set.h"
 #include "olsr.h"
 #include "scheduler.h"
 #include "lq_route.h"
+#include "lq_avl.h"
+#include "lq_packet.h"
+#include "net_olsr.h"
+
+#include <assert.h>
+
+/* 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
+olsr_init_tc(void)
 {
-  int index;
-  
-  /* Set timer to zero */
-  send_empty_tc.tv_sec = 0;
-  send_empty_tc.tv_usec = 0;
+  OLSR_PRINTF(5, "TC: init topo\n");
 
-  changes = OLSR_FALSE;
+  olsr_register_timeout_function(&olsr_time_out_tc_set, OLSR_TRUE);
 
-  olsr_printf(5, "TC: init topo\n");
+  avl_init(&tc_tree, avl_comp_default);
 
-  olsr_register_timeout_function(&olsr_time_out_tc_set);
+  /*
+   * Add a TC entry for ourselves.
+   */
+  tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
+}
 
-  for(index=0;index<HASHSIZE;index++)
-    {
-      tc_table[index].next = &tc_table[index];
-      tc_table[index].prev = &tc_table[index];
+/**
+ * The main ip address has changed.
+ * Do the needful.
+ */
+void
+olsr_change_myself_tc(void)
+{
+  struct tc_edge_entry *tc_edge;
+
+  if (tc_myself) {
+    /*
+     * Check if there was a change.
+     */
+    if (ipequal(&tc_myself->addr, &olsr_cnf->main_addr)) {
+      return;
     }
 
-  return 1;
-}
+    /*
+     * Flush all edges and our own tc_entry.
+     */
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc_myself, tc_edge) {
+      olsr_delete_tc_edge_entry(tc_edge);
+    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc_myself, tc_edge);
+    olsr_delete_tc_entry(tc_myself);
+  }
 
+  /*
+   * The old entry for ourselves is gone, generate a new one and trigger SPF.
+   */
+  tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
+  changes_topology = OLSR_TRUE;
+}
 
 /**
- *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)
+void
+olsr_delete_tc_entry(struct tc_entry *tc)
 {
+#if 0
+  struct ipaddr_str buf;
+  OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(%buf, &tc->addr));
+#endif
 
-  //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;
-}
-
+  /* 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
- *
- *@param adr the address to look for
+ * Look up a entry from the TC tree based on address
  *
- *@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_add_tc_entry(union olsr_ip_addr *adr)
+olsr_getnext_tc_entry(struct tc_entry *tc)
 {
-  struct tc_entry *new_entry;
-  olsr_u32_t hash;
+  struct avl_node *node = avl_walk_next(&tc->vertex_node);
 
-  olsr_printf(1, "TC: adding entry %s\n", olsr_ip_to_string(adr));
+  if (node) {
+    return node->data;
+  }
 
-  hash = olsr_hashing(adr);
+  return NULL;
+}
 
-  new_entry = olsr_malloc(sizeof(struct tc_entry), "New TC entry");
+/**
+ * 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 *tc;
+#if 0
+  struct ipaddr_str buf;
+  OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
+#endif
+
+  tc = olsr_malloc(sizeof(struct tc_entry), "add TC entry");
+  if (!tc) {
+    return NULL;
+  }
+  memset(tc, 0, sizeof(struct tc_entry));
 
   /* 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->addr = *adr;
+  tc->vertex_node.data = tc;
+  tc->vertex_node.key = &tc->addr;
 
-  /* 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;
-  */
+   * Insert into the global tc tree.
+   */
+  avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
 
-  return new_entry;
+  /*
+   * Initialize subtree for further edges to come.
+   */
+  avl_init(&tc->edge_tree, avl_comp_default);
+
+  return tc;
 }
 
+/**
+ * format a tc_edge contents into a buffer
+ */
+char *
+olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
+{
+  static char buf[128];
+  struct ipaddr_str addrbuf, dstbuf;
+  struct tc_entry *tc = tc_edge->tc;
+
+  snprintf(buf, sizeof(buf),
+           "%s > %s, lq %.3f, inv-lq %.3f, etx %.3f",
+           olsr_ip_to_string(&addrbuf, &tc->addr),
+           olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
+           tc_edge->link_quality,
+           tc_edge->inverse_link_quality,
+           tc_edge->etx);
+
+  return buf;
+}
 
 /**
- *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);
+}
+
+/*
+ * 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)
+{
+  if (tc_edge->link_quality < MIN_LINK_QUALITY &&
+      tc_edge->inverse_link_quality < MIN_LINK_QUALITY) {
+    tc_edge->etx = INFINITE_ETX;
+  } else {
+    tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
+  }
+}
 
-int
-olsr_tc_delete_mprs(struct tc_entry *entry, struct tc_message *msg)
+/**
+ * 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,
+                       olsr_u16_t ansn, unsigned int vtime,
+                       float link_quality, float neigh_link_quality)
 {
-  struct topo_dst *tmp_dsts, *dst_to_del;
-  int retval;
+  struct tc_entry *tc_neighbor;
+  struct tc_edge_entry *tc_edge, *tc_edge_inv;
+
+  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));
 
-  //olsr_printf(5, "TC: deleting MPRS\n");
+  /* Fill entry */
+  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;
+
+  if (olsr_cnf->lq_level > 0) {
+    tc_edge->link_quality = neigh_link_quality;
+    tc_edge->inverse_link_quality = link_quality;
+  } else {
+
+    /*
+     * 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;
+  }
 
-  tmp_dsts = entry->destinations.next;
-  retval = 0;
+  /*
+   * Insert into the edge tree.
+   */
+  avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
 
-  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;
+  /*
+   * Connect backpointer.
+   */
+  tc_edge->tc = tc;
 
-         /* dequeue */
-         DEQUEUE_ELEM(dst_to_del);
+#if 0
+  OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
+#endif
 
-         free(dst_to_del);
-         retval = 1;
-       }
-      else
-       tmp_dsts = tmp_dsts->next;
+  /*
+   * 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;
 
     }
+  }
 
-  return retval;
+  /*
+   * Update the etx.
+   */
+  olsr_calc_tc_edge_entry_etx(tc_edge);
+
+  return tc_edge;
 }
 
 
 /**
- *Update the destinations registered on an entry.
- *Creates new dest-entries if not registered.
- *Bases update on a receivied TC message
+ * Delete a TC edge entry.
  *
- *@param entry the TC entry to check
- *@msg the TC message to update by
- *
- *@return 1 if entries are added 0 if not
+ * @param tc the TC entry
+ * @param tc_edge the TC edge entry
  */
-
-int
-olsr_tc_update_mprs(struct tc_entry *entry, struct tc_message *msg)
+void
+olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
 {
-  struct tc_mpr_addr *mprs;
-  struct topo_dst *new_topo_dst, *existing_dst;
-  int retval;
+  struct tc_entry *tc;
+  struct tc_edge_entry *tc_edge_inv;
 
-  //olsr_printf(1, "TC: update MPRS\n");
+#if 0
+  OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
+#endif
 
-  retval = 0;
+  tc = tc_edge->tc;
+  avl_delete(&tc->edge_tree, &tc_edge->edge_node);
 
+  /*
+   * Clear the backpointer of our inverse edge.
+   */
+  tc_edge_inv = tc_edge->edge_inv;
+  if (tc_edge_inv) {
+    tc_edge_inv->edge_inv = NULL;
+  }
 
-  mprs = msg->multipoint_relay_selector_address;
-  
-  /* Add all the MPRs */
-
-  while(mprs != NULL)
-    {
-      existing_dst = olsr_tc_lookup_dst(entry, &mprs->address);
+  /*
+   * 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);
+    }
+  }
 
-      if(existing_dst == NULL)
-       {
-         /* New entry */
-         new_topo_dst = olsr_malloc(sizeof(struct topo_dst), "add TC destination");
+  free(tc_edge);
+}
 
-         memset(new_topo_dst, 0, sizeof(struct topo_dst));
 
-         COPY_IP(&new_topo_dst->T_dest_addr, &mprs->address);
-         olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &new_topo_dst->T_time);
-         new_topo_dst->T_seq = msg->ansn;
+/**
+ * Delete all destinations that have a lower ANSN.
+ *
+ * @param tc the entry to delete edges from
+ * @param ansn the advertised neighbor set sequence number
+ * @return 1 if any destinations were deleted 0 if not
+ */
+static int
+olsr_delete_outdated_tc_edges(struct tc_entry *tc, olsr_u16_t ansn)
+{
+  struct tc_edge_entry *tc_edge;
+  int retval = 0;
+
+#if 0
+  OLSR_PRINTF(5, "TC: deleting MPRS\n");
+#endif
+
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+    if (SEQNO_GREATER_THAN(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 garbage 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);
 
-          if (olsr_cnf->lq_level > 0)
-            {
-              new_topo_dst->link_quality = mprs->neigh_link_quality;
-              new_topo_dst->inverse_link_quality = mprs->link_quality;
+  return retval;
+}
 
-              new_topo_dst->saved_link_quality = new_topo_dst->link_quality;
-              new_topo_dst->saved_inverse_link_quality =
-                new_topo_dst->inverse_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;
 
-         /* 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;
+  if (etx1 == 0.0 || etx2 == 0.0) {
+    return OLSR_TRUE;
+  }
 
-         retval = 1;
-       }
-      else
-       {
-         /* Update entry */
-         olsr_get_timestamp((olsr_u32_t) msg->vtime*1000, &existing_dst->T_time);
-         existing_dst->T_seq = msg->ansn;
+  rel_lq = etx1 / etx2;
 
-          if (olsr_cnf->lq_level > 0)
-            {
-              double saved_lq, rel_lq;
+  if (rel_lq > 1.1 || rel_lq < 0.9) {
+    return OLSR_TRUE;
+  }
 
-              saved_lq = existing_dst->saved_link_quality;
+  return OLSR_FALSE;
+}
 
-              if (saved_lq == 0.0)
-                saved_lq = -1.0;
+/**
+ * Update an edge registered on an entry.
+ * Creates new edge-entries if not registered.
+ * Bases update on a received TC message
+ *
+ * @param entry the TC entry to check
+ * @pkt the TC edge entry in the packet
+ * @return 1 if entries are added 0 if not
+ */
+static int
+olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
+                    olsr_u8_t type, const unsigned char **curr)
+{
+  struct tc_edge_entry *tc_edge;
+  double link_quality, neigh_link_quality;
+  union olsr_ip_addr neighbor;
+  int edge_change;
 
-              existing_dst->link_quality = mprs->neigh_link_quality;
+  edge_change = 0;
 
-              rel_lq = existing_dst->link_quality / saved_lq;
+  /*
+   * Fetch the per-edge data
+   * LQ messages also contain LQ data.
+   */
+  pkt_get_ipaddress(curr, &neighbor);
+
+  if (type == LQ_TC_MESSAGE) {
+    pkt_get_lq(curr, &link_quality);
+    pkt_get_lq(curr, &neigh_link_quality);
+    pkt_ignore_u16(curr);
+  } else {
+    link_quality = 1.0;
+    neigh_link_quality = 1.0;
+  }
 
-              if (rel_lq > 1.1 || rel_lq < 0.9)
-                {
-                  existing_dst->saved_link_quality =
-                    existing_dst->link_quality;
+  /* First check if we know this edge */
+  tc_edge = olsr_lookup_tc_edge(tc, &neighbor);
+
+  if(!tc_edge) {
+      
+    /*
+     * Yet unknown - create it.
+     * Check if the address is allowed.
+     */
+    if (!olsr_validate_address(&neighbor)) {
+      return 0;
+    }
 
-                  retval = 1;
-                }
+    olsr_add_tc_edge_entry(tc, &neighbor, ansn, vtime_s,
+                           link_quality, neigh_link_quality);
+    edge_change = 1;
 
-              saved_lq = existing_dst->saved_inverse_link_quality;
+  } else {
 
-              if (saved_lq == 0.0)
-                saved_lq = -1.0;
+    /*
+     * We know this edge - Update entry.
+     */
+    olsr_set_tc_edge_timer(tc_edge, vtime_s*1000);
+    tc_edge->T_seq = ansn;
 
-              existing_dst->inverse_link_quality = mprs->link_quality;
+    /*
+     * Clear the (possibly set) down flag.
+     */
+    tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
 
-              rel_lq = existing_dst->inverse_link_quality / saved_lq;
+    /*
+     * Determine if the etx change is meaningful enough
+     * in order to trigger a SPF calculation.
+     */
+    if (olsr_etx_significant_change(tc_edge->link_quality,
+                                    neigh_link_quality)) {
 
-              if (rel_lq > 1.1 || rel_lq < 0.9)
-                {
-                  existing_dst->saved_inverse_link_quality =
-                    existing_dst->inverse_link_quality;
+      if (tc->msg_hops <= olsr_cnf->lq_dlimit)
+        edge_change = 1;
+    }
+    tc_edge->link_quality = neigh_link_quality;
 
-                  retval = 1;
-                }
-            }
-       }
+    if (olsr_etx_significant_change(tc_edge->inverse_link_quality,
+                                    link_quality)) {
 
-      mprs = mprs->next;
+      if (tc->msg_hops <= olsr_cnf->lq_dlimit)
+        edge_change = 1;
     }
+    tc_edge->inverse_link_quality = link_quality;
 
-  return retval;
-}
+    /*
+     * 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
 
+  }
 
+  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");
-
-  for(dsts = entry->destinations.next; 
-      dsts != &entry->destinations; 
-      dsts = dsts->next)
-    {
-      if(COMP_IP(dst_addr, &dsts->T_dest_addr))
-       return dsts;
-    }
-  return NULL;
-}
-
-
+#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;
+  }
 
+  return NULL;
+}
 
 /**
- * Time out entries
+ * Walk the timers and time out entries.
  *
- *@return nada
+ * @return nada
  */
-
 void
-olsr_time_out_tc_set()
+olsr_time_out_tc_set(void)
 {
-  int index, deleted;
-  struct tc_entry *entry, *entry2;
-  struct topo_dst *dst_entry, *dst_to_delete;
-
-
-  for(index=0;index<HASHSIZE;index++)
-    {
-      /* For all TC entries */
-      entry = tc_table[index].next;
-      while(entry != &tc_table[index])
-       {
-         //printf("INDEX: %d\n", index);
-         /* For all destination entries of that TC entry */
-         deleted = 0;
-         dst_entry = entry->destinations.next;
-         while(dst_entry != &entry->destinations)
-           {
-             /* If timed out - delete */
-             if(TIMED_OUT(&dst_entry->T_time))
-               {
-                 deleted = 1;
-                 /* Dequeue */
-                 DEQUEUE_ELEM(dst_entry);
-                 //dst_entry->prev->next = dst_entry->next;
-                 //dst_entry->next->prev = dst_entry->prev;
-
-                 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;
+
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    struct tc_edge_entry *tc_edge;
+    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)
+}
 
-  return;
+/**
+ * Print the topology table to stdout
+ */
+void
+olsr_print_tc_table(void)
+{
+#ifndef NODEBUG
+  /* The whole function makes no sense without it. */
+  struct tc_entry *tc;
+  const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
+
+  OLSR_PRINTF(1,
+              "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n"
+              "%-*s %-*s %-5s  %-5s  %s\n",
+              nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, (int)now.tv_usec / 10000,
+              ipwidth, "Source IP addr", ipwidth, "Dest IP addr", "LQ", "ILQ", "ETX");
+
+  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    struct tc_edge_entry *tc_edge;
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+      struct ipaddr_str addrbuf, dstaddrbuf;
+      OLSR_PRINTF(1, "%-*s %-*s  %5.3f  %5.3f  %.2f\n",
+                  ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
+                  ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
+                  tc_edge->link_quality,
+                  tc_edge->inverse_link_quality,
+                  olsr_calc_tc_etx(tc_edge));
+    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
+  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+#endif
 }
 
+float olsr_calc_tc_etx(const struct tc_edge_entry *tc_edge)
+{
+  return tc_edge->link_quality < MIN_LINK_QUALITY ||
+         tc_edge->inverse_link_quality < MIN_LINK_QUALITY
+             ? 0.0
+             : 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
+}
 
-/**
- *Print the topology table to stdout
+/*
+ * Process an incoming TC or TC_LQ message.
+ *
+ * If the message is interesting enough, update our edges for it,
+ * trigger SPF and finally flood it to all our 2way neighbors.
+ *
+ * The order for extracting data off the message does matter, 
+ * as every call to pkt_get increases the packet offset and
+ * hence the spot we are looking at.
  */
-int
-olsr_print_tc_table()
+void
+olsr_input_tc(union olsr_message *msg, struct interface *input_if,
+              union olsr_ip_addr *from_addr)
 {
-  int i;
-  struct tc_entry *entry;
-  struct topo_dst *dst_entry;
-  char *fstr;
-  float etx;
-  
-  olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n",
-              nowtm->tm_hour,
-              nowtm->tm_min,
-              nowtm->tm_sec,
-              now.tv_usec / 10000);
-
-  if (olsr_cnf->ip_version == AF_INET)
-  {
-    olsr_printf(1, "Source IP addr   Dest IP addr     LQ     ILQ    ETX\n");
-    fstr = "%-15s  %-15s  %5.3f  %5.3f  %.2f\n";
+#ifndef NODEBUG 
+  struct ipaddr_str buf;
+#endif
+  olsr_u16_t size, msg_seq, ansn;
+  olsr_u8_t type, ttl, msg_hops;
+  double vtime;
+  unsigned int vtime_s;
+  union olsr_ip_addr originator;
+  union olsr_ip_addr *main_addr;
+  const unsigned char *limit, *curr;
+  struct tc_entry *tc;
+
+  curr = (void *)msg;
+  if (!msg) {
+    return;
   }
 
-  else
-  {
-    olsr_printf(1, "Source IP addr                Dest IP addr                    LQ     ILQ    ETX\n");
-    fstr = "%-30s%-30s  %5.3f  %5.3f  %.2f\n";
+  /* We are only interested in TC message types. */
+  pkt_get_u8(&curr, &type);
+  if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
+    return;
   }
 
-  for (i = 0; i < HASHSIZE; i++)
-  {
-    entry = tc_table[i].next;
+  pkt_get_double(&curr, &vtime);
+  vtime_s = (unsigned int)vtime;
+  pkt_get_u16(&curr, &size);
 
-    while (entry != &tc_table[i])
-    {
-      dst_entry = entry->destinations.next;
+  pkt_get_ipaddress(&curr, &originator);
 
-      while(dst_entry != &entry->destinations)
-      {
-        if (dst_entry->link_quality < MIN_LINK_QUALITY ||
-            dst_entry->inverse_link_quality < MIN_LINK_QUALITY)
-          etx = 0.0;
+  /* Copy header values */
+  pkt_get_u8(&curr, &ttl);
+  pkt_get_u8(&curr, &msg_hops);
+  pkt_get_u16(&curr, &msg_seq);
+  pkt_get_u16(&curr, &ansn);
+  pkt_ignore_u16(&curr);
 
-        else
-          etx = 1.0 / (dst_entry->link_quality *
-                       dst_entry->inverse_link_quality);
+  /*
+   * Check if we know this guy and if we already know what he has to say.
+   */
+  tc = olsr_lookup_tc_entry(&originator);
+  if (tc) {
+    if (!SEQNO_GREATER_THAN(msg_seq, tc->msg_seq)) {
+      return;
+    }
+  }
 
-        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);
+  /* Check the sender address. */
+  if (!olsr_validate_address(&originator)) {
+    return;
+  }
 
-        dst_entry = dst_entry->next;
-      }
+  /* Check the main address. */
+  main_addr = mid_lookup_main_addr(from_addr);
+  if (!main_addr) {
+    main_addr = from_addr;
+  }
+  if (!olsr_validate_address(main_addr)) {
+    return;
+  }
+
+  /*
+   * Generate an new tc_entry in the lsdb and store the sequence number.
+   */
+  if (!tc) {
+    tc = olsr_add_tc_entry(&originator);
+    tc->msg_seq = msg_seq;
+  }
+
+  OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
+              olsr_ip_to_string(&buf, &originator), ansn);
+
+  /*
+   * If the sender interface (NB: not originator) of this message
+   * is not in the symmetric 1-hop neighborhood of this node, the
+   * message MUST be discarded.
+   */
+  if (check_neighbor_link(from_addr) != SYM_LINK) {
+    OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
+                olsr_ip_to_string(&buf, from_addr));
+    return;
+  }
+
+  /*
+   * Update the tc entry.
+   */
+  tc->msg_hops = msg_hops;
+  tc->msg_seq = msg_seq;
 
-      entry = entry->next;
+  /*
+   * Now walk the edge advertisements contained in the packet.
+   * Play some efficiency games here, like checking first
+   * if the edge exists in order to avoid address validation.
+   */
+  limit = (void *)msg + size;
+  while (curr < limit) {
+    if (olsr_tc_update_edge(tc, vtime_s, ansn, type, &curr)) {
+      changes_topology = OLSR_TRUE;
     }
   }
 
-  return 1;
+  /*
+   * Do the edge garbage collection at the end in order
+   * to avoid malloc() churn.
+   */
+  if (olsr_delete_outdated_tc_edges(tc, ansn)) {
+    changes_topology = OLSR_TRUE;
+  }
+
+  /*
+   * Last, flood the message to our other neighbors.
+   */
+  olsr_forward_message(msg, &originator, msg_seq, input_if, from_addr);
+  return;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */