refactor the neighbor database
authorHannes Gredler <hannes@gredler.at>
Tue, 19 May 2009 17:55:14 +0000 (19:55 +0200)
committerHannes Gredler <hannes@gredler.at>
Tue, 19 May 2009 17:55:14 +0000 (19:55 +0200)
-replace hashes through AVL trees
-reduce memory churn for MPR election

src/mid_set.c
src/mpr.c
src/neighbor_table.c
src/neighbor_table.h
src/process_package.c
src/two_hop_neighbor_table.c
src/two_hop_neighbor_table.h

index 52df3d9..55d0853 100644 (file)
@@ -150,10 +150,7 @@ olsr_flush_nbr2_duplicates(struct mid_entry *alias)
 
         replace_neighbor_link_set(nbr, real_nbr);
 
-        /* Dequeue */
-        DEQUEUE_ELEM(nbr);
-        /* Delete */
-        free(nbr);
+        olsr_delete_nbr_entry(&alias->mid_alias_addr);
 
         changes_neighborhood = true;
       }
index c443866..40b32c0 100644 (file)
--- a/src/mpr.c
+++ b/src/mpr.c
  */
 
 static uint16_t add_will_always_nodes(void);
-
-static void
-  olsr_optimize_mpr_set(void);
-
-static void
-  olsr_clear_mprs(void);
-
-static void
-  olsr_clear_two_hop_processed(void);
-
+static void olsr_optimize_mpr_set(void);
+static void olsr_clear_mprs(void);
+static void olsr_clear_two_hop_processed(void);
 static struct nbr_entry *olsr_find_maximum_covered(int);
-
 static uint16_t olsr_calculate_two_hop_neighbors(void);
-
-static int
-  olsr_check_mpr_changes(void);
-
-static int
-  olsr_chosen_mpr(struct nbr_entry *, uint16_t *);
-
-static struct nbr2_list_entry *olsr_find_2_hop_neighbors_with_1_link(int);
-
+static int olsr_check_mpr_changes(void);
+static int olsr_chosen_mpr(struct nbr_entry *, uint16_t *);
 
 /* End:
  * Prototypes for internal functions
  */
 
 
-
-/**
- *Find all 2 hop neighbors with 1 link
- *connecting them to us trough neighbors
- *with a given willingness.
- *
- *@param willingness the willigness of the neighbors
- *
- *@return a linked list of allocated nbr2_list_entry structures
- */
-static struct nbr2_list_entry *
-olsr_find_2_hop_neighbors_with_1_link(int willingness)
-{
-
-
-  int idx;
-  struct nbr2_list_entry *two_hop_list_tmp = NULL;
-  struct nbr2_list_entry *two_hop_list = NULL;
-  struct nbr_entry *dup_neighbor;
-  struct neighbor_2_entry *two_hop_neighbor = NULL;
-#if !defined REMOVE_LOG_DEBUG
-  struct ipaddr_str buf;
-#endif
-  for (idx = 0; idx < HASHSIZE; idx++) {
-
-    for (two_hop_neighbor = two_hop_neighbortable[idx].next;
-         two_hop_neighbor != &two_hop_neighbortable[idx]; two_hop_neighbor = two_hop_neighbor->next) {
-
-      //two_hop_neighbor->neighbor_2_state=0;
-      //two_hop_neighbor->mpr_covered_count = 0;
-
-      dup_neighbor = olsr_lookup_nbr_entry(&two_hop_neighbor->neighbor_2_addr);
-
-      if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
-        OLSR_DEBUG(LOG_MPR, "(1)Skipping 2h neighbor %s - already 1hop\n",
-                   olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
-
-        continue;
-      }
-
-      if (two_hop_neighbor->neighbor_2_pointer == 1) {
-        if ((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness) &&
-            (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM)) {
-          two_hop_list_tmp = olsr_malloc(sizeof(struct nbr2_list_entry), "MPR two hop list");
-
-          OLSR_DEBUG(LOG_MPR, "ONE LINK ADDING %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
-
-          /* Only queue one way here */
-          two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
-
-          two_hop_list_tmp->next = two_hop_list;
-
-          two_hop_list = two_hop_list_tmp;
-        }
-      }
-
-    }
-
-  }
-
-  return (two_hop_list_tmp);
-}
-
-
-
-
-
-
 /**
  *This function processes the chosen MPRs and updates the counters
  *used in calculations
@@ -174,8 +91,8 @@ olsr_chosen_mpr(struct nbr_entry *one_hop_neighbor, uint16_t * two_hop_covered_c
 
   one_hop_neighbor->is_mpr = true;      //NBS_MPR;
 
-  for (second_hop_entries = one_hop_neighbor->neighbor_2_list.next;
-       second_hop_entries != &one_hop_neighbor->neighbor_2_list; second_hop_entries = second_hop_entries->next) {
+  OLSR_FOR_ALL_NBR2_LIST_ENTRIES(one_hop_neighbor, second_hop_entries) {
+
     dup_neighbor = olsr_lookup_nbr_entry(&second_hop_entries->neighbor_2->neighbor_2_addr);
 
     if ((dup_neighbor != NULL) && (dup_neighbor->status == SYM)) {
@@ -208,9 +125,7 @@ olsr_chosen_mpr(struct nbr_entry *one_hop_neighbor, uint16_t * two_hop_covered_c
       }
       the_one_hop_list = the_one_hop_list->next;
     }
-
-    //}
-  }
+  } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(one_hop_neighbor, second_hop_entries);
 
   *two_hop_covered_count = count;
   return count;
@@ -248,8 +163,7 @@ olsr_find_maximum_covered(int willingness)
       maximum = a_neighbor->neighbor_2_nocov;
       mpr_candidate = a_neighbor;
     }
-  }
-  OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
+  } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 
   return mpr_candidate;
 }
@@ -273,13 +187,10 @@ olsr_clear_mprs(void)
     }
 
     /* Clear two hop neighbors coverage count/ */
-    for (two_hop_list = a_neighbor->neighbor_2_list.next;
-         two_hop_list != &a_neighbor->neighbor_2_list; two_hop_list = two_hop_list->next) {
+    OLSR_FOR_ALL_NBR2_LIST_ENTRIES(a_neighbor, two_hop_list) {
       two_hop_list->neighbor_2->mpr_covered_count = 0;
-    }
-
-  }
-  OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
+    } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(a_neighbor, two_hop_list);
+  } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 }
 
 
@@ -305,8 +216,7 @@ olsr_check_mpr_changes(void)
         retval = 1;
       }
     }
-  }
-  OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
+  } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 
   return retval;
 }
@@ -354,9 +264,7 @@ olsr_calculate_two_hop_neighbors(void)
       continue;
     }
 
-    for (twohop_neighbors = a_neighbor->neighbor_2_list.next;
-         twohop_neighbors != &a_neighbor->neighbor_2_list; twohop_neighbors = twohop_neighbors->next) {
-
+    OLSR_FOR_ALL_NBR2_LIST_ENTRIES(a_neighbor, twohop_neighbors) {
       dup_neighbor = olsr_lookup_nbr_entry(&twohop_neighbors->neighbor_2->neighbor_2_addr);
 
       if ((dup_neighbor == NULL) || (dup_neighbor->status != SYM)) {
@@ -366,14 +274,13 @@ olsr_calculate_two_hop_neighbors(void)
           twohop_neighbors->neighbor_2->processed = 1;
         }
       }
-    }
+    } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(a_neighbor, twohop_neighbors);
     a_neighbor->neighbor_2_nocov = n_count;
 
     /* Add the two hop count */
     sum += count;
 
-  }
-  OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
+  } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 
   OLSR_DEBUG(LOG_MPR, "Two hop neighbors: %d\n", sum);
   return sum;
@@ -401,8 +308,7 @@ add_will_always_nodes(void)
 
     OLSR_DEBUG(LOG_MPR, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
 
-  }
-  OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
+  } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
 
   return count;
 }
@@ -414,49 +320,96 @@ add_will_always_nodes(void)
 void
 olsr_calculate_mpr(void)
 {
+#if !defined REMOVE_LOG_DEBUG
+  struct ipaddr_str buf;
+#endif
+
+  struct neighbor_2_entry *nbr2;
+  struct nbr_entry *nbr;
+  struct nbr_entry *mprs;
   uint16_t two_hop_covered_count;
   uint16_t two_hop_count;
-  int i;
+  int willingness;
 
   olsr_clear_mprs();
   two_hop_count = olsr_calculate_two_hop_neighbors();
   two_hop_covered_count = add_will_always_nodes();
 
   /*
-   *Calculate MPRs based on WILLINGNESS
+   * Calculate MPRs based on WILLINGNESS.
    */
+  for (willingness = WILL_ALWAYS - 1; willingness > WILL_NEVER; willingness--) {
 
-  for (i = WILL_ALWAYS - 1; i > WILL_NEVER; i--) {
-    struct nbr_entry *mprs;
-    struct nbr2_list_entry *two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);
-
-    while (two_hop_list != NULL) {
-      struct nbr2_list_entry *tmp;
-      if (!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
-        olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count);
-      tmp = two_hop_list;
-      two_hop_list = two_hop_list->next;;
-      free(tmp);
-    }
+    /*
+     * Find all 2 hop neighbors with 1 link
+     * connecting them to us trough neighbors
+     * with a given willingness.
+     */
+    OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) {
+
+      /*
+       * Eliminate 2 hop neighbors which already are in our 1 hop neighborhood.
+       */
+      nbr = olsr_lookup_nbr_entry(&nbr2->neighbor_2_addr);
+      if (nbr && (nbr->status != NOT_SYM)) {
+        OLSR_DEBUG(LOG_MPR, "Skipping 2-hop neighbor2 %s - already 1hop\n",
+                   olsr_ip_to_string(&buf, &nbr2->neighbor_2_addr));
+        continue;
+      }
+
+      /*
+       * Eliminate 2 hop neighbors which are not single link.
+       */
+      if (nbr2->neighbor_2_pointer != 1) {
+        OLSR_DEBUG(LOG_MPR, "Skipping 2-hop neighbor %s - not single link\n",
+                   olsr_ip_to_string(&buf, &nbr2->neighbor_2_addr));
+        continue;
+      }
+
+      nbr = nbr2->neighbor_2_nblist.next->neighbor;
+
+      /* Already an elected MPR ? */
+      if (nbr->is_mpr) {
+        OLSR_DEBUG(LOG_MPR, "Skipping 2-hop neighbor %s - already MPR\n",
+                   olsr_ip_to_string(&buf, &nbr2->neighbor_2_addr));
+        continue;
+      }
+
+      /* Match willingness */
+      if (nbr->willingness != willingness) {
+        continue;
+      }
+
+      /* Only symmetric neighbors */
+      if (nbr->status != SYM) {
+        continue;
+      }
+
+      /*
+       * This 2 hop neighbor is good enough.
+       */
+      OLSR_DEBUG(LOG_MPR, "One link adding %s\n", olsr_ip_to_string(&buf, &nbr2->neighbor_2_addr));
+      olsr_chosen_mpr(nbr, &two_hop_covered_count);
+
+    } OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2);
 
     if (two_hop_covered_count >= two_hop_count) {
-      i = WILL_NEVER;
+      willingness = WILL_NEVER;
       break;
     }
 
-    while ((mprs = olsr_find_maximum_covered(i)) != NULL) {
+    while ((mprs = olsr_find_maximum_covered(willingness)) != NULL) {
       olsr_chosen_mpr(mprs, &two_hop_covered_count);
 
       if (two_hop_covered_count >= two_hop_count) {
-        i = WILL_NEVER;
+        willingness = WILL_NEVER;
         break;
       }
-
     }
   }
 
   /*
-     increment the mpr sequence number
+   * Increment the MPR sequence number.
    */
 
   /* Optimize selection */
@@ -467,7 +420,6 @@ olsr_calculate_mpr(void)
     if (olsr_cnf->tc_redundancy > 0)
       signal_link_changes(true);
   }
-
 }
 
 /**
@@ -501,9 +453,7 @@ olsr_optimize_mpr_set(void)
         struct nbr2_list_entry *two_hop_list;
         int remove_it = 1;
 
-        for (two_hop_list = a_neighbor->neighbor_2_list.next;
-             two_hop_list != &a_neighbor->neighbor_2_list; two_hop_list = two_hop_list->next) {
-
+        OLSR_FOR_ALL_NBR2_LIST_ENTRIES(a_neighbor, two_hop_list) {
           const struct nbr_entry *dup_neighbor = olsr_lookup_nbr_entry(&two_hop_list->neighbor_2->neighbor_2_addr);
 
           if ((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM)) {
@@ -517,15 +467,14 @@ olsr_optimize_mpr_set(void)
             remove_it = 0;
             break;
           }
-        }
+        } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(a_neighbor, two_hop_list_list);
 
         if (remove_it) {
           OLSR_DEBUG(LOG_MPR, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&buf, &a_neighbor->neighbor_main_addr));
           a_neighbor->is_mpr = false;
         }
       }
-    }
-    OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
+    } OLSR_FOR_ALL_NBR_ENTRIES_END(a_neighbor);
   }
 }
 
index 91cfb77..279d58d 100644 (file)
@@ -54,7 +54,8 @@
 
 #include <stdlib.h>
 
-
+/* Root of the one hop neighbor database */
+struct avl_tree nbr_tree;
 struct nbr_entry neighbortable[HASHSIZE];
 
 /* Some cookies for stats keeping */
@@ -63,17 +64,10 @@ struct olsr_cookie_info *nbr2_list_timer_cookie = NULL;
 void
 olsr_init_neighbor_table(void)
 {
-  int i;
-
   OLSR_INFO(LOG_NEIGHTABLE, "Initialize neighbor table...\n");
-
-  for (i = 0; i < HASHSIZE; i++) {
-    neighbortable[i].next = &neighbortable[i];
-    neighbortable[i].prev = &neighbortable[i];
-  }
+  avl_init(&nbr_tree, avl_comp_default);
 
   nbr2_list_timer_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_TIMER);
-
 }
 
 /**
@@ -145,23 +139,21 @@ olsr_delete_nbr2_list_entry(struct nbr_entry *neighbor, struct neighbor_2_entry
  *representing the two hop neighbor if found. NULL if not found.
  */
 struct nbr2_list_entry *
-olsr_lookup_nbr2_list_entry(const struct nbr_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
+olsr_lookup_nbr2_list_entry(struct nbr_entry *nbr,
+                            const union olsr_ip_addr *addr)
 {
-  struct nbr2_list_entry *entry;
-
-  for (entry = neighbor->neighbor_2_list.next; entry != &neighbor->neighbor_2_list; entry = entry->next) {
-
-    if (olsr_ipcmp(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address) == 0)
-      return entry;
+  struct avl_node *node;
 
+  node = avl_find(&nbr->nbr2_list_tree, addr);
+  if (node) {
+    return nbr2_list_node_to_nbr2_list(node);
   }
   return NULL;
-}
-
+}  
 
 
 /**
- *Delete a neighbr table entry.
+ *Delete a neighbor table entry.
  *
  *Remember: Deleting a neighbor entry results
  *the deletion of its 2 hop neighbors list!!!
index 3e49ab0..16fc005 100644 (file)
@@ -49,6 +49,7 @@
 
 
 struct nbr2_list_entry {
+  struct avl_node nbr2_list_node;
   struct nbr_entry *nbr2_nbr;     /* backpointer to owning nbr entry */
   struct neighbor_2_entry *neighbor_2;
   struct timer_entry *nbr2_list_timer;
@@ -56,22 +57,29 @@ struct nbr2_list_entry {
   struct nbr2_list_entry *prev;
 };
 
+AVLNODE2STRUCT(nbr2_list_node_to_nbr2_list, struct nbr2_list_entry, nbr2_list_node);
+
 #define OLSR_NBR2_LIST_JITTER 5 /* percent */
 
 struct nbr_entry {
+  struct avl_node nbr_node; /* nbr keyed by ip address */
   union olsr_ip_addr neighbor_main_addr;
+  struct avl_tree nbr2_list_tree; /* subtree for nbr2 pointers */ 
   unsigned int status:3;
   unsigned int willingness:3;
   unsigned int is_mpr:1;
   unsigned int was_mpr:1;             /* Used to detect changes in MPR */
   unsigned int skip:1;
-  int neighbor_2_nocov;
+  unsigned int neighbor_2_nocov;
   unsigned int linkcount;
+  unsigned int nbr_refcount;
   struct nbr2_list_entry neighbor_2_list;
   struct nbr_entry *next;
   struct nbr_entry *prev;
 } __attribute__ ((packed));
 
+AVLNODE2STRUCT(nbr_node_to_nbr, struct nbr_entry, nbr_node);
+
 #define OLSR_FOR_ALL_NBR_ENTRIES(nbr) \
 { \
   int _idx; \
@@ -81,6 +89,11 @@ struct nbr_entry {
         nbr = nbr->next)
 #define OLSR_FOR_ALL_NBR_ENTRIES_END(nbr) }}
 
+/*
+ * The one hop neighbor tree
+ */
+extern struct avl_tree
+EXPORT(nbr_tree);
 
 /*
  * The neighbor table
@@ -88,38 +101,38 @@ struct nbr_entry {
 extern struct nbr_entry
 EXPORT(neighbortable)[HASHSIZE];
 
-     extern struct olsr_cookie_info *nbr2_list_timer_cookie;
-
-     void
-       olsr_init_neighbor_table(void);
+extern struct olsr_cookie_info *nbr2_list_timer_cookie;
 
-     int
-       olsr_delete_nbr2_list_entry(struct nbr_entry *, struct neighbor_2_entry *);
+void
+olsr_init_neighbor_table(void);
 
-     struct nbr2_list_entry *olsr_lookup_nbr2_list_entry(const struct nbr_entry *, const union olsr_ip_addr *);
+int
+olsr_delete_neighbor_2_pointer(struct nbr_entry *, struct neighbor_2_entry *);
 
-     int
-       olsr_delete_nbr_entry(const union olsr_ip_addr *);
+struct nbr2_list_entry *olsr_lookup_nbr2_list_entry(struct nbr_entry *,
+                                                    const union olsr_ip_addr *);
+int
+olsr_delete_neighbor_table(const union olsr_ip_addr *);
 
-     struct nbr_entry *olsr_add_nbr_entry(const union olsr_ip_addr *);
+struct nbr_entry *olsr_insert_neighbor_table(const union olsr_ip_addr *);
 
-     struct nbr_entry *olsr_lookup_nbr_entry(const union olsr_ip_addr *);
+struct nbr_entry *olsr_lookup_neighbor_table(const union olsr_ip_addr *);
 
-     struct nbr_entry *olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *);
+struct nbr_entry *olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *);
 
-     void
-       olsr_time_out_two_hop_neighbors(struct nbr_entry *);
+void
+olsr_time_out_two_hop_neighbors(struct nbr_entry *);
 
-     void
-       olsr_time_out_neighborhood_tables(void);
-     void olsr_expire_nbr2_list(void *);
+void
+olsr_time_out_neighborhood_tables(void);
+void olsr_expire_nbr2_list(void *);
 
-     void
-       olsr_print_neighbor_table(void);
+void
+olsr_print_neighbor_table(void);
 
 
-     int
-       olsr_update_nbr_status(struct nbr_entry *, int);
+int
+update_neighbor_status(struct nbr_entry *, int);
 
 #endif
 
index f613dae..67868b3 100644 (file)
@@ -54,8 +54,6 @@ static bool olsr_input_hello(union olsr_message *ser, struct interface *inif, un
 
 static void process_message_neighbors(struct nbr_entry *, const struct lq_hello_message *);
 
-static void linking_this_2_entries(struct nbr_entry *, struct neighbor_2_entry *, olsr_reltime);
-
 static bool lookup_mpr_status(const struct lq_hello_message *, const struct interface *);
 
 static void hello_tap(struct lq_hello_message *, struct interface *, const union olsr_ip_addr *);
@@ -141,7 +139,7 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
          */
         changes_neighborhood = true;
         changes_topology = true;
-        linking_this_2_entries(neighbor, two_hop_neighbor, message->comm.vtime);
+        olsr_link_nbr_nbr2(neighbor, two_hop_neighbor, message->comm.vtime);
       }
     }
   }
@@ -214,45 +212,6 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
   }
 }
 
-/**
- * Links a one-hop neighbor with a 2-hop neighbor.
- *
- * @param neighbor the 1-hop neighbor
- * @param two_hop_neighbor the 2-hop neighbor
- * @return nada
- */
-static void
-linking_this_2_entries(struct nbr_entry *neighbor, struct neighbor_2_entry *two_hop_neighbor, olsr_reltime vtime)
-{
-  struct neighbor_list_entry *list_of_1_neighbors = olsr_malloc(sizeof(*list_of_1_neighbors), "Link entries 1");
-  struct nbr2_list_entry *list_of_2_neighbors = olsr_malloc(sizeof(*list_of_2_neighbors), "Link entries 2");
-
-  list_of_1_neighbors->neighbor = neighbor;
-  list_of_1_neighbors->path_linkcost = LINK_COST_BROKEN;
-  list_of_1_neighbors->saved_path_linkcost = LINK_COST_BROKEN;
-  list_of_1_neighbors->second_hop_linkcost = LINK_COST_BROKEN;
-
-  /* Queue */
-  two_hop_neighbor->neighbor_2_nblist.next->prev = list_of_1_neighbors;
-  list_of_1_neighbors->next = two_hop_neighbor->neighbor_2_nblist.next;
-  two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
-  list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
-
-  list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
-  list_of_2_neighbors->nbr2_nbr = neighbor;     /* XXX refcount */
-  list_of_2_neighbors->nbr2_list_timer =
-    olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER,
-                     OLSR_TIMER_ONESHOT, &olsr_expire_nbr2_list, list_of_2_neighbors, nbr2_list_timer_cookie->ci_id);
-
-  /* Queue */
-  neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
-  list_of_2_neighbors->next = neighbor->neighbor_2_list.next;
-  neighbor->neighbor_2_list.next = list_of_2_neighbors;
-  list_of_2_neighbors->prev = &neighbor->neighbor_2_list;
-
-  /*increment the pointer counter */
-  two_hop_neighbor->neighbor_2_pointer++;
-}
 
 /**
  * Check if a hello message states this node as a MPR.
index a057259..1b2a83e 100644 (file)
@@ -39,6 +39,7 @@
  *
  */
 #include "two_hop_neighbor_table.h"
+#include "olsr.h"
 #include "ipcalc.h"
 #include "defs.h"
 #include "mid_set.h"
@@ -115,7 +116,7 @@ olsr_delete_two_hop_neighbor_table(struct neighbor_2_entry *two_hop_neighbor)
     struct nbr_entry *one_hop_entry = one_hop_list->neighbor;
     struct neighbor_list_entry *entry_to_delete = one_hop_list;
 
-    olsr_delete_nbr2_list_entry(one_hop_entry, two_hop_neighbor);
+    olsr_delete_nbr2_list_entry_by_addr(one_hop_entry, &two_hop_neighbor->neighbor_2_addr);
     one_hop_list = one_hop_list->next;
     /* no need to dequeue */
     free(entry_to_delete);
@@ -200,6 +201,37 @@ olsr_lookup_two_hop_neighbor_table_mid(const union olsr_ip_addr *dest)
   return NULL;
 }
 
+
+/**
+ * Links a one-hop neighbor with a 2-hop neighbor.
+ *
+ * @param neighbor the 1-hop neighbor
+ * @param two_hop_neighbor the 2-hop neighbor
+ * @return nada
+ */
+void
+olsr_link_nbr_nbr2(struct nbr_entry *nbr, struct neighbor_2_entry *nbr2, float vtime)
+{
+  struct neighbor_list_entry *nbr_list;
+
+  nbr_list = olsr_malloc(sizeof(struct neighbor_list_entry), "Link entries 1");
+
+  nbr_list->neighbor = nbr;
+
+  nbr_list->second_hop_linkcost = LINK_COST_BROKEN;
+  nbr_list->path_linkcost = LINK_COST_BROKEN;
+  nbr_list->saved_path_linkcost = LINK_COST_BROKEN;
+
+  /* Add nbr_list to nbr2 */
+  nbr2->neighbor_2_nblist.next->prev = nbr_list;
+  nbr_list->next = nbr2->neighbor_2_nblist.next;
+  nbr2->neighbor_2_nblist.next = nbr_list;
+  nbr_list->prev = &nbr2->neighbor_2_nblist;
+
+  olsr_add_nbr2_list_entry(nbr, nbr2, vtime);
+}
+
+
 /**
  *Print the two hop neighbor table to STDOUT.
  *
index 2f14581..992c4a5 100644 (file)
@@ -70,28 +70,33 @@ struct neighbor_2_entry {
   struct neighbor_2_entry *next;
 };
 
+/*
+ * macros for traversing two-hop neighbors lists.
+ * 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_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)
+#define OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2) }}
 
 extern struct neighbor_2_entry two_hop_neighbortable[HASHSIZE];
 
-
-void
-  olsr_init_two_hop_table(void);
-
-void
-  olsr_delete_neighbor_pointer(struct neighbor_2_entry *, struct nbr_entry *);
-
-void
-  olsr_delete_two_hop_neighbor_table(struct neighbor_2_entry *);
-
-void
-  olsr_insert_two_hop_neighbor_table(struct neighbor_2_entry *);
-
+void olsr_init_two_hop_table(void); 
+void olsr_delete_neighbor_pointer(struct neighbor_2_entry *, struct nbr_entry *);
+void olsr_delete_two_hop_neighbor_table(struct neighbor_2_entry *);
+void olsr_insert_two_hop_neighbor_table(struct neighbor_2_entry *);
 struct neighbor_2_entry *olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *);
-
 struct neighbor_2_entry *olsr_lookup_two_hop_neighbor_table_mid(const union olsr_ip_addr *);
-
-void
-  olsr_print_two_hop_neighbor_table(void);
+void olsr_link_nbr_nbr2(struct nbr_entry *, struct neighbor_2_entry *, float);
+void olsr_print_two_hop_neighbor_table(void);
 
 #endif