convert the nbr2 table to use avl trees
authorHannes Gredler <hannes@gredler.at>
Fri, 29 May 2009 17:09:37 +0000 (19:09 +0200)
committerHannes Gredler <hannes@gredler.at>
Fri, 29 May 2009 17:09:37 +0000 (19:09 +0200)
src/lq_mpr.c
src/mid_set.c
src/mpr.c
src/process_package.c
src/two_hop_neighbor_table.c
src/two_hop_neighbor_table.h

index 2f02309..4c2769c 100644 (file)
@@ -52,7 +52,7 @@ olsr_calculate_lq_mpr(void)
 {
   struct nbr2_entry *neigh2;
   struct nbr_list_entry *walker;
-  int i, k;
+  int k;
   struct nbr_entry *neigh;
   olsr_linkcost best, best_1hop;
   bool mpr_changes = false;
@@ -82,87 +82,85 @@ olsr_calculate_lq_mpr(void)
   }
   OLSR_FOR_ALL_NBR_ENTRIES_END(neigh);
 
-  for (i = 0; i < HASHSIZE; i++) {
-    /* loop through all 2-hop neighbours */
+  /* loop through all 2-hop neighbours */
+  OLSR_FOR_ALL_NBR2_ENTRIES(neigh2) {
 
-    for (neigh2 = two_hop_neighbortable[i].next; neigh2 != &two_hop_neighbortable[i]; neigh2 = neigh2->next) {
-      best_1hop = LINK_COST_BROKEN;
+    best_1hop = LINK_COST_BROKEN;
 
-      /* check whether this 2-hop neighbour is also a neighbour */
+    /* check whether this 2-hop neighbour is also a neighbour */
 
-      neigh = olsr_lookup_nbr_entry(&neigh2->nbr2_addr);
+    neigh = olsr_lookup_nbr_entry(&neigh2->nbr2_addr);
 
-      /* if it's a neighbour and also symmetric, then examine
-         the link quality */
+    /* if it's a neighbour and also symmetric, then examine
+       the link quality */
 
-      if (neigh != NULL && neigh->status == SYM) {
-        /* if the direct link is better than the best route via
-         * an MPR, then prefer the direct link and do not select
-         * an MPR for this 2-hop neighbour */
+    if (neigh != NULL && neigh->status == SYM) {
+      /* if the direct link is better than the best route via
+       * an MPR, then prefer the direct link and do not select
+       * an MPR for this 2-hop neighbour */
 
-        /* determine the link quality of the direct link */
+      /* determine the link quality of the direct link */
 
-        struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
+      struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
 
-        if (!lnk)
-          continue;
+      if (!lnk)
+        continue;
 
-        best_1hop = lnk->linkcost;
+      best_1hop = lnk->linkcost;
 
-        /* see wether we find a better route via an MPR */
+      /* see wether we find a better route via an MPR */
 
-        for (walker = neigh2->nbr2_nblist.next; walker != &neigh2->nbr2_nblist; walker = walker->next)
-          if (walker->path_linkcost < best_1hop)
-            break;
+      for (walker = neigh2->nbr2_nblist.next; walker != &neigh2->nbr2_nblist; walker = walker->next)
+        if (walker->path_linkcost < best_1hop)
+          break;
 
-        /* we've reached the end of the list, so we haven't found
-         * a better route via an MPR - so, skip MPR selection for
-         * this 1-hop neighbor */
+      /* we've reached the end of the list, so we haven't found
+       * a better route via an MPR - so, skip MPR selection for
+       * this 1-hop neighbor */
 
-        if (walker == &neigh2->nbr2_nblist)
-          continue;
-      }
+      if (walker == &neigh2->nbr2_nblist)
+        continue;
+    }
+
+    /* find the connecting 1-hop neighbours with the
+     * best total link qualities */
+
+    /* mark all 1-hop neighbours as not selected */
 
-      /* find the connecting 1-hop neighbours with the
-       * best total link qualities */
+    for (walker = neigh2->nbr2_nblist.next; walker != &neigh2->nbr2_nblist; walker = walker->next)
+      walker->neighbor->skip = false;
 
-      /* mark all 1-hop neighbours as not selected */
+    for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
+      /* look for the best 1-hop neighbour that we haven't
+       * yet selected */
+
+      neigh = NULL;
+      best = LINK_COST_BROKEN;
 
       for (walker = neigh2->nbr2_nblist.next; walker != &neigh2->nbr2_nblist; walker = walker->next)
-        walker->neighbor->skip = false;
-
-      for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
-        /* look for the best 1-hop neighbour that we haven't
-         * yet selected */
-
-        neigh = NULL;
-        best = LINK_COST_BROKEN;
-
-        for (walker = neigh2->nbr2_nblist.next; walker != &neigh2->nbr2_nblist; walker = walker->next)
-          if (walker->neighbor->status == SYM && !walker->neighbor->skip && walker->path_linkcost < best) {
-            neigh = walker->neighbor;
-            best = walker->path_linkcost;
-          }
-
-        /* Found a 1-hop neighbor that we haven't previously selected.
-         * Use it as MPR only when the 2-hop path through it is better than
-         * any existing 1-hop path. */
-        if ((neigh != NULL) && (best < best_1hop)) {
-          neigh->is_mpr = true;
-          neigh->skip = true;
-
-          if (neigh->is_mpr != neigh->was_mpr)
-            mpr_changes = true;
+        if (walker->neighbor->status == SYM && !walker->neighbor->skip && walker->path_linkcost < best) {
+          neigh = walker->neighbor;
+          best = walker->path_linkcost;
         }
 
-        /* no neighbour found => the requested MPR coverage cannot
-         * be satisfied => stop */
+      /* Found a 1-hop neighbor that we haven't previously selected.
+       * Use it as MPR only when the 2-hop path through it is better than
+       * any existing 1-hop path. */
+      if ((neigh != NULL) && (best < best_1hop)) {
+        neigh->is_mpr = true;
+        neigh->skip = true;
 
-        else
-          break;
+        if (neigh->is_mpr != neigh->was_mpr)
+          mpr_changes = true;
       }
+
+      /* no neighbour found => the requested MPR coverage cannot
+       * be satisfied => stop */
+
+      else
+        break;
     }
-  }
+  } OLSR_FOR_ALL_NBR2_ENTRIES_END(NEIGH2);
 
   if (mpr_changes && olsr_cnf->tc_redundancy > 0)
     signal_link_changes(true);
index 890ecb6..757d066 100644 (file)
@@ -128,7 +128,7 @@ olsr_flush_nbr2_duplicates(struct mid_entry *alias)
 
   OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
     struct nbr_entry *nbr;
-    struct nbr2_entry *nbr2 = olsr_lookup_two_hop_neighbor_table_mid(&alias->mid_alias_addr);
+    struct nbr2_entry *nbr2 = olsr_lookup_nbr2_entry_alias(&alias->mid_alias_addr);
 
     /* Delete possible 2 hop neighbor */
     if (nbr2) {
index e4b98cd..1b8cf46 100644 (file)
--- a/src/mpr.c
+++ b/src/mpr.c
@@ -223,22 +223,18 @@ olsr_check_mpr_changes(void)
 
 
 /**
- *Clears out proccess registration
- *on two hop neighbors
+ * Clears out proccess registration on two hop neighbors
  */
 static void
 olsr_clear_two_hop_processed(void)
 {
-  int idx;
+  struct nbr2_entry *nbr2;
+
+  OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) {
 
-  for (idx = 0; idx < HASHSIZE; idx++) {
-    struct nbr2_entry *nbr2;
-    for (nbr2 = two_hop_neighbortable[idx].next; nbr2 != &two_hop_neighbortable[idx]; nbr2 = nbr2->next) {
       /* Clear */
       nbr2->processed = 0;
-    }
-  }
-
+  } OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2);
 }
 
 
index 76dc19d..8e5f6ed 100644 (file)
@@ -68,10 +68,6 @@ static void hello_tap(struct lq_hello_message *, struct interface *, const union
 static void
 process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_message *message)
 {
-#if !defined REMOVE_LOG_DEBUG
-    struct ipaddr_str buf;
-#endif
-
   struct lq_hello_neighbor *message_neighbors;
   olsr_linkcost first_hop_pathcost;
   struct link_entry *lnk;
@@ -133,16 +129,8 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
         }
       }
     } else {
-      struct nbr2_entry *two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&message_neighbors->addr);
-      if (two_hop_neighbor == NULL) {
-        OLSR_DEBUG(LOG_LINKS, "Adding 2 hop neighbor %s\n\n", olsr_ip_to_string(&buf, &message_neighbors->addr));
-        two_hop_neighbor = olsr_malloc(sizeof(*two_hop_neighbor), "Process HELLO");
-        two_hop_neighbor->nbr2_nblist.next = &two_hop_neighbor->nbr2_nblist;
-        two_hop_neighbor->nbr2_nblist.prev = &two_hop_neighbor->nbr2_nblist;
-        two_hop_neighbor->nbr2_refcount = 0;
-        two_hop_neighbor->nbr2_addr = message_neighbors->addr;
-        olsr_insert_two_hop_neighbor_table(two_hop_neighbor);
-      }
+      struct nbr2_entry *two_hop_neighbor = olsr_add_nbr2_entry(&message_neighbors->addr);
+
       /*
        * linking to this two_hop_neighbor entry
        */
index db99994..8edf879 100644 (file)
 
 #include <stdlib.h>
 
-struct nbr2_entry two_hop_neighbortable[HASHSIZE];
+/* Root of the two hop neighbor database */
+struct avl_tree nbr2_tree;
 
 /**
- *Initialize 2 hop neighbor table
+ * Initialize 2 hop neighbor table
  */
 void
 olsr_init_two_hop_table(void)
 {
-  int idx;
+  OLSR_INFO(LOG_NEIGHTABLE, "Initializing neighbor2 tree.\n");
+  avl_init(&nbr2_tree, avl_comp_default);
 
-  OLSR_INFO(LOG_2NEIGH, "Initialize two-hop neighbortable...\n");
-
-  for (idx = 0; idx < HASHSIZE; idx++) {
-    two_hop_neighbortable[idx].next = &two_hop_neighbortable[idx];
-    two_hop_neighbortable[idx].prev = &two_hop_neighbortable[idx];
-  }
+  /* XXX cookie allocation */
 }
 
 /**
@@ -159,65 +156,71 @@ olsr_delete_two_hop_neighbor_table(struct nbr2_entry *nbr2)
     free(nbr_list);
   }
 
-  DEQUEUE_ELEM(nbr2);
+  avl_delete(&nbr2_tree, &nbr2->nbr2_node);
   free(nbr2);
 }
 
 /**
- *Insert a new entry to the two hop neighbor table.
+ * Insert a new entry to the two hop neighbor table.
  *
- *@param two_hop_neighbor the entry to insert
+ * @param two_hop_neighbor the entry to insert
  *
- *@return nada
+ * @return nada
  */
-void
-olsr_insert_two_hop_neighbor_table(struct nbr2_entry *two_hop_neighbor)
+struct nbr2_entry *
+olsr_add_nbr2_entry(const union olsr_ip_addr *addr)
 {
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
 #endif
-  uint32_t hash = olsr_ip_hashing(&two_hop_neighbor->nbr2_addr);
+  struct nbr2_entry *nbr2;
 
-  OLSR_DEBUG(LOG_2NEIGH, "Adding 2 hop neighbor %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->nbr2_addr));
+  /*
+   * Check first if the entry exists.
+   */
+  nbr2 = olsr_lookup_two_hop_neighbor_table(addr);
+  if (nbr2) {
+    return nbr2;
+  }
+
+  OLSR_DEBUG(LOG_2NEIGH, "Adding 2 hop neighbor %s\n", olsr_ip_to_string(&buf, addr));
+
+  nbr2 = olsr_malloc(sizeof(*nbr2), "Process HELLO");
+  nbr2->nbr2_nblist.next = &nbr2->nbr2_nblist;
+  nbr2->nbr2_nblist.prev = &nbr2->nbr2_nblist;
+  nbr2->nbr2_refcount = 0;
+  nbr2->nbr2_addr = *addr;
 
-  /* Queue */
-  QUEUE_ELEM(two_hop_neighbortable[hash], two_hop_neighbor);
+  /* Add to global neighbor 2 tree */
+  nbr2->nbr2_node.key = &nbr2->nbr2_addr;
+  avl_insert(&nbr2_tree, &nbr2->nbr2_node, AVL_DUP_NO);
+
+  return nbr2;
 }
 
+
 /**
- *Look up an entry in the two hop neighbor table.
+ * Lookup a neighbor2 entry in the neighbortable2 based on an address.
  *
- *@param dest the IP address of the entry to find
+ * @param addr the IP address of the neighbor to look up
  *
- *@return a pointer to a nbr2_entry struct
- *representing the two hop neighbor
+ * @return a pointer to the neighbor2 struct registered on the given
+ *  address. NULL if not found.
  */
 struct nbr2_entry *
-olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *dest)
+olsr_lookup_nbr2_entry_alias(const union olsr_ip_addr *addr)
 {
-  struct nbr2_entry *nbr2;
-  uint32_t hash = olsr_ip_hashing(dest);
+  struct avl_node *node;
 
-  for (nbr2 = two_hop_neighbortable[hash].next; nbr2 != &two_hop_neighbortable[hash]; nbr2 = nbr2->next) {
-    struct tc_entry *tc;
-
-    if (olsr_ipcmp(&nbr2->nbr2_addr, dest) == 0) {
-      return nbr2;
-    }
-    /*
-     * Locate the hookup point and check if this is a registered alias.
-     */
-    tc = olsr_locate_tc_entry(&nbr2->nbr2_addr);
-    if (olsr_lookup_tc_mid_entry(tc, dest)) {
-      return nbr2;
-    }
+  node = avl_find(&nbr2_tree, addr);
+  if (node) {
+    return nbr2_node_to_nbr2(node);
   }
   return NULL;
 }
 
 /**
  *Look up an entry in the two hop neighbor table.
- *NO CHECK FOR MAIN ADDRESS OR ALIASES!
  *
  *@param dest the IP address of the entry to find
  *
@@ -225,19 +228,20 @@ olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *dest)
  *representing the two hop neighbor
  */
 struct nbr2_entry *
-olsr_lookup_two_hop_neighbor_table_mid(const union olsr_ip_addr *dest)
+olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *addr)
 {
-  struct nbr2_entry *nbr2;
-  uint32_t hash = olsr_ip_hashing(dest);
+  const union olsr_ip_addr *main_addr;
 
-  for (nbr2 = two_hop_neighbortable[hash].next; nbr2 != &two_hop_neighbortable[hash]; nbr2 = nbr2->next) {
-    if (olsr_ipcmp(&nbr2->nbr2_addr, dest) == 0)
-      return nbr2;
+  /*
+   * Find main address of node
+   */
+  main_addr = olsr_lookup_main_addr_by_alias(addr);
+  if (!main_addr) {
+    main_addr = addr;
   }
-  return NULL;
+  return olsr_lookup_nbr2_entry_alias(main_addr);
 }
 
-
 /**
  * Links a one-hop neighbor with a 2-hop neighbor.
  *
@@ -278,30 +282,28 @@ olsr_print_two_hop_neighbor_table(void)
 {
 #if !defined REMOVE_LOG_INFO
   /* The whole function makes no sense without it. */
-  int i;
+  struct nbr2_entry *neigh2;
+  struct nbr_list_entry *entry;
+  bool first;
 
   OLSR_INFO(LOG_2NEIGH, "\n--- %s ----------------------- TWO-HOP NEIGHBORS\n\n"
             "IP addr (2-hop)  IP addr (1-hop)  Total cost\n", olsr_wallclock_string());
 
-  for (i = 0; i < HASHSIZE; i++) {
-    struct nbr2_entry *neigh2;
-    for (neigh2 = two_hop_neighbortable[i].next; neigh2 != &two_hop_neighbortable[i]; neigh2 = neigh2->next) {
-      struct nbr_list_entry *entry;
-      bool first = true;
+  OLSR_FOR_ALL_NBR2_ENTRIES(neigh2) {
+    first = true;
 
-      for (entry = neigh2->nbr2_nblist.next; entry != &neigh2->nbr2_nblist; entry = entry->next) {
-        struct ipaddr_str buf;
-        struct lqtextbuffer lqbuffer;
+    for (entry = neigh2->nbr2_nblist.next; entry != &neigh2->nbr2_nblist; entry = entry->next) {
+      struct ipaddr_str buf;
+      struct lqtextbuffer lqbuffer;
 
-        OLSR_INFO_NH(LOG_2NEIGH, "%-15s  %-15s  %s\n",
-                     first ? olsr_ip_to_string(&buf, &neigh2->nbr2_addr) : "",
-                     olsr_ip_to_string(&buf, &entry->neighbor->neighbor_main_addr),
-                     get_linkcost_text(entry->path_linkcost, false, &lqbuffer));
+      OLSR_INFO_NH(LOG_2NEIGH, "%-15s  %-15s  %s\n",
+                   first ? olsr_ip_to_string(&buf, &neigh2->nbr2_addr) : "",
+                   olsr_ip_to_string(&buf, &entry->neighbor->neighbor_main_addr),
+                   get_linkcost_text(entry->path_linkcost, false, &lqbuffer));
 
-        first = false;
-      }
+      first = false;
     }
-  }
+  } OLSR_FOR_ALL_NBR2_ENTRIES_END(neigh2);
 #endif
 }
 
index 7cc8a22..98a81e2 100644 (file)
@@ -61,15 +61,16 @@ struct nbr_list_entry {
 
 
 struct nbr2_entry {
+  struct avl_node nbr2_node;
   union olsr_ip_addr nbr2_addr;
-  struct nbr2_entry *prev;
-  struct nbr2_entry *next;
   unsigned int mpr_covered_count;      /* Used in mpr calculation */
   unsigned int processed:1;            /* Used in mpr calculation */
   unsigned int nbr2_refcount;          /* Reference counter */
   struct nbr_list_entry nbr2_nblist;
 } __attribute__ ((packed));;
 
+AVLNODE2STRUCT(nbr2_node_to_nbr2, struct nbr2_entry, nbr2_node);
+
 /*
  * macros for traversing two-hop neighbors.
  * it is recommended to use this because it hides all the internal
@@ -79,24 +80,27 @@ struct nbr2_entry {
  * for example the caller wants to delete the current entry.
  */
 #define OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) \
-  { \
-  int _idx; \
-  for (_idx = 0; _idx < HASHSIZE; _idx++) { \
-  for(nbr2 = two_hop_neighbortable[_idx].next; \
-  nbr2 != &two_hop_neighbortable[_idx]; \
-  nbr2 = nbr2->next)
+{ \
+  struct avl_node *nbr2_tree_node, *next_nbr2_tree_node; \
+  for (nbr2_tree_node = avl_walk_first(&nbr2_tree); \
+    nbr2_tree_node; nbr2_tree_node = next_nbr2_tree_node) { \
+    next_nbr2_tree_node = avl_walk_next(nbr2_tree_node); \
+    nbr2 = nbr2_node_to_nbr2(nbr2_tree_node);
 #define OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2) }}
 
-extern struct nbr2_entry two_hop_neighbortable[HASHSIZE];
+/*
+ * The two hop neighbor tree
+ */
+extern struct avl_tree EXPORT(nbr2_tree);
 
 void olsr_init_two_hop_table(void);
 void olsr_lock_nbr2(struct nbr2_entry *);
 void olsr_unlock_nbr2(struct nbr2_entry *);
 void olsr_delete_neighbor_pointer(struct nbr2_entry *, struct nbr_entry *);
 void olsr_delete_two_hop_neighbor_table(struct nbr2_entry *);
-void olsr_insert_two_hop_neighbor_table(struct nbr2_entry *);
+struct nbr2_entry *olsr_add_nbr2_entry(const union olsr_ip_addr *);
 struct nbr2_entry *olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *);
-struct nbr2_entry *olsr_lookup_two_hop_neighbor_table_mid(const union olsr_ip_addr *);
+struct nbr2_entry *olsr_lookup_nbr2_entry_alias(const union olsr_ip_addr *);
 void olsr_link_nbr_nbr2(struct nbr_entry *, struct nbr2_entry *, float);
 void olsr_print_two_hop_neighbor_table(void);