refactor the neighbor database (second attempt)
authorHannes Gredler <hannes@gredler.at>
Thu, 21 May 2009 09:30:33 +0000 (11:30 +0200)
committerHannes Gredler <hannes@gredler.at>
Thu, 21 May 2009 09:30:33 +0000 (11:30 +0200)
lib/httpinfo/src/olsrd_httpinfo.c
lib/txtinfo/src/olsrd_txtinfo.c
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 5526b62..ef348fd 100644 (file)
@@ -969,11 +969,12 @@ build_neigh_body(struct autobuf *abuf)
 
     abuf_puts(abuf, "<td><select>\n" "<option>IP ADDRESS</option>\n");
 
-
-    for (list_2 = neigh->neighbor_2_list.next, thop_cnt = 0; list_2 != &neigh->neighbor_2_list; list_2 = list_2->next, thop_cnt++) {
+    thop_cnt = 0;
+    OLSR_FOR_ALL_NBR2_LIST_ENTRIES(neigh, list_2) {
       struct ipaddr_str strbuf;
       abuf_appendf(abuf, "<option>%s</option>\n", olsr_ip_to_string(&strbuf, &list_2->neighbor_2->neighbor_2_addr));
-    }
+      thop_cnt++;
+    } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(neigh, list_2);
     abuf_appendf(abuf, "</select> (%d)</td></tr>\n", thop_cnt);
   } OLSR_FOR_ALL_NBR_ENTRIES_END(neigh);
 
index 11159b7..7a19226 100644 (file)
@@ -518,9 +518,9 @@ ipc_print_neigh(struct ipc_conn *conn)
     struct nbr2_list_entry *list_2;
     struct ipaddr_str buf1;
     int thop_cnt = 0;
-    for (list_2 = neigh->neighbor_2_list.next; list_2 != &neigh->neighbor_2_list; list_2 = list_2->next) {
+    OLSR_FOR_ALL_NBR2_LIST_ENTRIES(neigh, list_2) {
       thop_cnt++;
-    }
+    } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(neigh, list_2);
     if (!conn->csv) {
       if (abuf_appendf(&conn->resp,
                        "%s\t%s\t%s\t%s\t%d\t%d\n",
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..dba6854 100644 (file)
 
 #include <stdlib.h>
 
-
-struct nbr_entry neighbortable[HASHSIZE];
+/* Root of the one hop neighbor database */
+struct avl_tree nbr_tree;
 
 /* Some cookies for stats keeping */
 struct olsr_cookie_info *nbr2_list_timer_cookie = NULL;
+struct olsr_cookie_info *nbr2_list_mem_cookie = NULL;
+struct olsr_cookie_info *nbr_mem_cookie = NULL;
 
+/*
+ * Init neighbor tables.
+ */
 void
 olsr_init_neighbor_table(void)
 {
-  int i;
+  OLSR_INFO(LOG_NEIGHTABLE, "Initializing neighbor tree.\n");
+  avl_init(&nbr_tree, avl_comp_default);
+
+  nbr2_list_timer_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_TIMER);
 
-  OLSR_INFO(LOG_NEIGHTABLE, "Initialize neighbor table...\n");
+  nbr2_list_mem_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_MEMORY);
+  olsr_cookie_set_memory_size(nbr2_list_mem_cookie, sizeof(struct nbr2_list_entry));
 
-  for (i = 0; i < HASHSIZE; i++) {
-    neighbortable[i].next = &neighbortable[i];
-    neighbortable[i].prev = &neighbortable[i];
+  nbr_mem_cookie = olsr_alloc_cookie("1-Hop Neighbor", OLSR_COOKIE_TYPE_MEMORY);
+  olsr_cookie_set_memory_size(nbr_mem_cookie, sizeof(struct nbr_entry));
+}
+
+
+/**
+ * Add a neighbor 2 reference to a neighbor.
+ */
+struct nbr2_list_entry *
+olsr_add_nbr2_list_entry(struct nbr_entry *nbr, struct neighbor_2_entry *nbr2, float vtime)
+{
+  struct nbr2_list_entry *nbr2_list;
+
+  /*
+   * check first if the entry exists.
+   */
+  nbr2_list = olsr_lookup_nbr2_list_entry(nbr, &nbr2->neighbor_2_addr);
+  if (nbr2_list) {
+
+    /* 
+     * Refresh timer.
+     */
+    olsr_change_timer(nbr2_list->nbr2_list_timer, vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
+    return nbr2_list;
   }
 
-  nbr2_list_timer_cookie = olsr_alloc_cookie("2-Hop Neighbor List", OLSR_COOKIE_TYPE_TIMER);
+  /*
+   * Reference not found, allocate and init a fresh one.
+   */
+  nbr2_list = olsr_cookie_malloc(nbr2_list_mem_cookie);
+
+  nbr2_list->neighbor_2 = nbr2;
+  nbr2->neighbor_2_pointer++;   /* XXX move to olsr_lock_nbr2 () */
+  nbr2_list->nbr2_nbr = nbr;    /* XXX nbr needs refcount protection as well */
 
+  /*
+   * Start the timer.
+   */
+  olsr_start_timer(vtime, OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT,
+                   &olsr_expire_nbr2_list, nbr2_list, nbr2_list_timer_cookie->ci_id);
+
+  return nbr2_list;
 }
 
+
 /**
  * Unlink, delete and free a nbr2_list entry.
  */
 static void
-olsr_del_nbr2_list(struct nbr2_list_entry *nbr2_list)
+olsr_delete_nbr2_list_entry(struct nbr2_list_entry *nbr2_list)
 {
   struct neighbor_2_entry *nbr2;
+  struct nbr_entry *nbr;
 
   nbr2 = nbr2_list->neighbor_2;
+  nbr = nbr2_list->nbr2_nbr;
 
+  /* XXX move to olsr_unlock_nbr2() */
   if (nbr2->neighbor_2_pointer < 1) {
     DEQUEUE_ELEM(nbr2);
     free(nbr2);
@@ -97,10 +145,10 @@ olsr_del_nbr2_list(struct nbr2_list_entry *nbr2_list)
   olsr_stop_timer(nbr2_list->nbr2_list_timer);
   nbr2_list->nbr2_list_timer = NULL;
 
-  /* Dequeue */
-  DEQUEUE_ELEM(nbr2_list);
+  /* Remove from neighbor2 reference subtree */
+  avl_delete(&nbr->nbr2_list_tree, &nbr2_list->nbr2_list_node);
 
-  free(nbr2_list);
+  olsr_cookie_free(nbr2_list_mem_cookie, nbr2_list);
 
   /* Set flags to recalculate the MPR set and the routing table */
   changes_neighborhood = true;
@@ -115,211 +163,183 @@ olsr_del_nbr2_list(struct nbr2_list_entry *nbr2_list)
  *
  * @return positive if entry deleted
  */
-int
-olsr_delete_nbr2_list_entry(struct nbr_entry *neighbor, struct neighbor_2_entry *neigh2)
+bool
+olsr_delete_nbr2_list_entry_by_addr(struct nbr_entry *nbr, union olsr_ip_addr *addr)
 {
   struct nbr2_list_entry *nbr2_list;
 
-  nbr2_list = neighbor->neighbor_2_list.next;
+  nbr2_list = olsr_lookup_nbr2_list_entry(nbr, addr);
 
-  while (nbr2_list != &neighbor->neighbor_2_list) {
-    if (nbr2_list->neighbor_2 == neigh2) {
-      olsr_del_nbr2_list(nbr2_list);
-      return 1;
-    }
-    nbr2_list = nbr2_list->next;
+  if (nbr2_list) {
+    olsr_delete_nbr2_list_entry(nbr2_list);
+    return true;
   }
-  return 0;
+
+  return false;
 }
 
 
 /**
- *Check if a two hop neighbor is reachable via a given
- *neighbor.
+ * Check if a two hop neighbor is reachable via a given
+ * neighbor.
  *
- *@param neighbor neighbor-entry to check via
- *@param neighbor_main_address the addres of the two hop neighbor
- *to find.
+ * @param nbr neighbor-entry to check via
+ * @param addr the addres of the two hop neighbor to find.
  *
- *@return a pointer to the nbr2_list_entry struct
- *representing the two hop neighbor if found. NULL if not found.
+ * @return a pointer to the nbr2_list_entry struct
+ * 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!!!
- *@param neighbor the neighbor entry to delete
+ * Remember: Deleting a neighbor entry results the deletion of its 2 hop neighbors list!!!
+ * @param addr the neighbor entry to delete
  *
- *@return nada
+ * @return TRUE on success, FALSE otherwise.
  */
-
-int
-olsr_delete_nbr_entry(const union olsr_ip_addr *neighbor_addr)
+bool
+olsr_delete_nbr_entry(const union olsr_ip_addr * addr)
 {
-  struct nbr2_list_entry *two_hop_list, *two_hop_to_delete;
-  uint32_t hash;
-  struct nbr_entry *entry;
+  struct nbr2_list_entry *nbr2_list;
+  struct nbr_entry *nbr;
 
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
 #endif
-  OLSR_DEBUG(LOG_NEIGHTABLE, "delete neighbor: %s\n", olsr_ip_to_string(&buf, neighbor_addr));
-
-  hash = olsr_ip_hashing(neighbor_addr);
-
-  entry = neighbortable[hash].next;
 
   /*
    * Find neighbor entry
    */
-  while (entry != &neighbortable[hash]) {
-    if (olsr_ipcmp(&entry->neighbor_main_addr, neighbor_addr) == 0)
-      break;
-
-    entry = entry->next;
+  nbr = olsr_lookup_nbr_entry(addr);
+  if (!nbr) {
+    return false;
   }
 
-  if (entry == &neighbortable[hash])
-    return 0;
+  OLSR_DEBUG(LOG_NEIGHTABLE, "Delete 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
 
+  OLSR_FOR_ALL_NBR2_LIST_ENTRIES(nbr, nbr2_list) {
+    nbr2_list->neighbor_2->neighbor_2_pointer--;        /* XXX move to olsr_nbr2_unlock() */
+    olsr_delete_neighbor_pointer(nbr2_list->neighbor_2, nbr);
+    olsr_delete_nbr2_list_entry(nbr2_list);
+  } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list);
 
-  two_hop_list = entry->neighbor_2_list.next;
-
-  while (two_hop_list != &entry->neighbor_2_list) {
-    two_hop_to_delete = two_hop_list;
-    two_hop_list = two_hop_list->next;
-
-    two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
-    olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2, entry);
-
-    olsr_del_nbr2_list(two_hop_to_delete);
-  }
+  /* Remove from global neighbor tree */
+  avl_delete(&nbr_tree, &nbr->nbr_node);
 
-
-  /* Dequeue */
-  DEQUEUE_ELEM(entry);
-
-  free(entry);
+  olsr_cookie_free(nbr_mem_cookie, nbr);
 
   changes_neighborhood = true;
-  return 1;
 
+  return true;
 }
 
 
-
 /**
- *Insert a neighbor entry in the neighbor table
- *
- *@param main_addr the main address of the new node
+ * Insert a neighbor entry in the neighbor table.
  *
- *@return 0 if neighbor already exists 1 if inserted
+ * @param addr the main address of the new node
+ * @return pointer to an already existting (or new created) neighbor entry
  */
 struct nbr_entry *
-olsr_add_nbr_entry(const union olsr_ip_addr *main_addr)
+olsr_add_nbr_entry(const union olsr_ip_addr *addr)
 {
-  uint32_t hash;
-  struct nbr_entry *new_neigh;
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
 #endif
+  struct nbr_entry *nbr;
 
-  hash = olsr_ip_hashing(main_addr);
-
-  /* Check if entry exists */
-
-  for (new_neigh = neighbortable[hash].next; new_neigh != &neighbortable[hash]; new_neigh = new_neigh->next) {
-    if (olsr_ipcmp(&new_neigh->neighbor_main_addr, main_addr) == 0)
-      return new_neigh;
+  /*
+   * Check if neighbor entry exists.
+   */
+  nbr = olsr_lookup_nbr_entry(addr);
+  if (nbr) {
+    return nbr;
   }
 
-  OLSR_DEBUG(LOG_NEIGHTABLE, "delete neighbor: %s\n", olsr_ip_to_string(&buf, main_addr));
+  OLSR_DEBUG(LOG_NEIGHTABLE, "Add 1-hop neighbor: %s\n", olsr_ip_to_string(&buf, addr));
 
-  new_neigh = olsr_malloc(sizeof(struct nbr_entry), "New neighbor entry");
+  nbr = olsr_cookie_malloc(nbr_mem_cookie);
 
   /* Set address, willingness and status */
-  new_neigh->neighbor_main_addr = *main_addr;
-  new_neigh->willingness = WILL_NEVER;
-  new_neigh->status = NOT_SYM;
+  nbr->neighbor_main_addr = *addr;
+  nbr->willingness = WILL_NEVER;
+  nbr->status = NOT_SYM;
 
-  new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
-  new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
+  /* Init subtree for nbr2 pointers */
+  avl_init(&nbr->nbr2_list_tree, avl_comp_default);
 
-  new_neigh->linkcount = 0;
-  new_neigh->is_mpr = false;
-  new_neigh->was_mpr = false;
+  nbr->linkcount = 0;
+  nbr->is_mpr = false;
+  nbr->was_mpr = false;
 
-  /* Queue */
-  QUEUE_ELEM(neighbortable[hash], new_neigh);
+  /* Add to the global neighbor tree */
+  avl_insert(&nbr_tree, &nbr->nbr_node, AVL_DUP_NO);
 
-  return new_neigh;
+  return nbr;
 }
 
 
 
 /**
- *Lookup a neighbor entry in the neighbortable based on an address.
- *
- *@param dst the IP address of the neighbor to look up
+ * Lookup a neighbor entry in the neighbortable based on an address.
+ * Unalias the passed in address before.
+ * 
+ * @param addr the IP address of the neighbor to look up
  *
- *@return a pointer to the neighbor struct registered on the given
- *address. NULL if not found.
+ * @return a pointer to the neighbor struct registered on the given
+ * address. NULL if not found.
  */
 struct nbr_entry *
-olsr_lookup_nbr_entry(const union olsr_ip_addr *dst)
+olsr_lookup_nbr_entry(const union olsr_ip_addr *addr)
 {
+  const union olsr_ip_addr *main_addr;
+
   /*
-   *Find main address of node
+   * Find main address of node
    */
-  union olsr_ip_addr *tmp_ip = olsr_lookup_main_addr_by_alias(dst);
-  if (tmp_ip != NULL)
-    dst = tmp_ip;
-  return olsr_lookup_nbr_entry_alias(dst);
+  main_addr = olsr_lookup_main_addr_by_alias(addr);
+  if (!main_addr) {
+    main_addr = addr;
+  }
+
+  return olsr_lookup_nbr_entry_alias(main_addr);
 }
 
 
 /**
- *Lookup a neighbor entry in the neighbortable based on an address.
+ * Lookup a neighbor entry in the neighbortable based on an address.
  *
- *@param dst the IP address of the neighbor to look up
+ * @param addr the IP address of the neighbor to look up
  *
- *@return a pointer to the neighbor struct registered on the given
- *address. NULL if not found.
+ * @return a pointer to the neighbor struct registered on the given
+ *  address. NULL if not found.
  */
 struct nbr_entry *
-olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *dst)
+olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *addr)
 {
-  struct nbr_entry *entry;
-  uint32_t hash = olsr_ip_hashing(dst);
+  struct avl_node *node;
 
-  for (entry = neighbortable[hash].next; entry != &neighbortable[hash]; entry = entry->next) {
-    if (olsr_ipcmp(&entry->neighbor_main_addr, dst) == 0)
-      return entry;
+  node = avl_find(&nbr_tree, addr);
+  if (node) {
+    return nbr_node_to_nbr(node);
   }
-
   return NULL;
-
 }
 
 
-
 int
 olsr_update_nbr_status(struct nbr_entry *entry, int lnk)
 {
@@ -375,43 +395,45 @@ olsr_expire_nbr2_list(void *context)
   nbr = nbr2_list->nbr2_nbr;
   nbr2 = nbr2_list->neighbor_2;
 
-  nbr2->neighbor_2_pointer--;
+  nbr2->neighbor_2_pointer--;   /* XXX move to olsr_unlock_nbr2() */
   olsr_delete_neighbor_pointer(nbr2, nbr);
 
-  olsr_del_nbr2_list(nbr2_list);
+  olsr_delete_nbr2_list_entry(nbr2_list);
 }
 
 
 /**
- *Prints the registered neighbors and two hop neighbors
- *to STDOUT.
+ * Print the registered neighbors and two hop neighbors to STDOUT.
  *
- *@return nada
+ * @return nada
  */
 void
 olsr_print_neighbor_table(void)
 {
 #if !defined REMOVE_LOG_INFO
   /* The whole function doesn't do anything else. */
+
   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 39;
-  int idx;
+  struct nbr_entry *nbr;
+  struct link_entry *lnk;
+  struct ipaddr_str buf;
+
   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
             "%*s  LQ    SYM   MPR   MPRS  will\n", olsr_wallclock_string(), ipwidth, "IP address");
 
-  for (idx = 0; idx < HASHSIZE; idx++) {
-    struct nbr_entry *neigh;
-    for (neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
-      struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
-      if (lnk) {
-        struct ipaddr_str buf;
-        OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s  %s  %s  %s  %d\n",
-                     ipwidth, olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
-                     neigh->status == SYM ? "YES " : "NO  ",
-                     neigh->is_mpr ? "YES " : "NO  ",
-                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ", neigh->willingness);
-      }
+  OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
+
+    lnk = get_best_link_to_neighbor(&nbr->neighbor_main_addr);
+    if (!lnk) {
+      continue;
     }
-  }
+
+    OLSR_INFO_NH(LOG_NEIGHTABLE, "%-*s  %s  %s  %s  %d\n",
+                 ipwidth, olsr_ip_to_string(&buf, &nbr->neighbor_main_addr),
+                 nbr->status == SYM ? "YES " : "NO  ",
+                 nbr->is_mpr ? "YES " : "NO  ",
+                 olsr_lookup_mprs_set(&nbr->neighbor_main_addr) == NULL ? "NO  " : "YES ", nbr->willingness);
+  } OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
 #endif
 }
 
index 3e49ab0..f27ed38 100644 (file)
 
 #include "defs.h"
 #include "olsr_types.h"
-#include "hashing.h"
-
+#include "common/avl.h"
 
+/*
+ * This is a neighbor2 list entry.
+ * It is used to describe a set of references to two-hop neighbors.
+ * This AVL tree node is hanging off an nbr_entry.
+ */
 struct nbr2_list_entry {
-  struct nbr_entry *nbr2_nbr;     /* backpointer to owning nbr 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;
-  struct nbr2_list_entry *next;
-  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;
   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 was_mpr:1;              /* Used to detect changes in MPR */
   unsigned int skip:1;
   int neighbor_2_nocov;
   unsigned int linkcount;
-  struct nbr2_list_entry neighbor_2_list;
-  struct nbr_entry *next;
-  struct nbr_entry *prev;
+  struct avl_tree nbr2_list_tree;      /* subtree for nbr2 pointers */
 } __attribute__ ((packed));
 
+AVLNODE2STRUCT(nbr_node_to_nbr, struct nbr_entry, nbr_node);
+
+/*
+ * macros for traversing neighbors and neighbor2 ref 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_NBR_ENTRIES(nbr) \
 { \
-  int _idx; \
-  for (_idx = 0; _idx < HASHSIZE; _idx++) { \
-    for(nbr = neighbortable[_idx].next; \
-        nbr != &neighbortable[_idx]; \
-        nbr = nbr->next)
+  struct avl_node *nbr_tree_node, *next_nbr_tree_node; \
+  for (nbr_tree_node = avl_walk_first(&nbr_tree); \
+    nbr_tree_node; nbr_tree_node = next_nbr_tree_node) { \
+    next_nbr_tree_node = avl_walk_next(nbr_tree_node); \
+    nbr = nbr_node_to_nbr(nbr_tree_node);
 #define OLSR_FOR_ALL_NBR_ENTRIES_END(nbr) }}
 
+#define OLSR_FOR_ALL_NBR2_LIST_ENTRIES(nbr, nbr2_list) \
+{ \
+  struct avl_node *nbr2_list_node, *next_nbr2_list_node; \
+  for (nbr2_list_node = avl_walk_first(&nbr->nbr2_list_tree); \
+    nbr2_list_node; nbr2_list_node = next_nbr2_list_node) { \
+    next_nbr2_list_node = avl_walk_next(nbr2_list_node); \
+    nbr2_list = nbr2_list_node_to_nbr2_list(nbr2_list_node);
+#define OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list) }}
 
 /*
- * The neighbor table
+ * The one hop neighbor tree
  */
-extern struct nbr_entry
-EXPORT(neighbortable)[HASHSIZE];
-
-     extern struct olsr_cookie_info *nbr2_list_timer_cookie;
-
-     void
-       olsr_init_neighbor_table(void);
-
-     int
-       olsr_delete_nbr2_list_entry(struct nbr_entry *, struct neighbor_2_entry *);
-
-     struct nbr2_list_entry *olsr_lookup_nbr2_list_entry(const struct nbr_entry *, const union olsr_ip_addr *);
-
-     int
-       olsr_delete_nbr_entry(const union olsr_ip_addr *);
-
-     struct nbr_entry *olsr_add_nbr_entry(const union olsr_ip_addr *);
-
-     struct nbr_entry *olsr_lookup_nbr_entry(const union olsr_ip_addr *);
-
-     struct nbr_entry *olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *);
-
-     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_print_neighbor_table(void);
-
-
-     int
-       olsr_update_nbr_status(struct nbr_entry *, int);
-
-#endif
+extern struct avl_tree EXPORT(nbr_tree);
+extern struct olsr_cookie_info *nbr2_list_timer_cookie;
+
+void olsr_init_neighbor_table(void);
+bool olsr_delete_nbr2_list_entry_by_addr(struct nbr_entry *, union olsr_ip_addr *);
+struct nbr2_list_entry *olsr_lookup_nbr2_list_entry(struct nbr_entry *, const union olsr_ip_addr *);
+struct nbr2_list_entry *olsr_add_nbr2_list_entry(struct nbr_entry *, struct neighbor_2_entry *, float);
+bool olsr_delete_nbr_entry(const union olsr_ip_addr *);
+void olsr_link_nbr_nbr2(struct nbr_entry *, struct neighbor_2_entry *, float);
+struct nbr_entry *olsr_add_nbr_entry(const union olsr_ip_addr *);
+struct nbr_entry *olsr_lookup_nbr_entry(const union olsr_ip_addr *);
+struct nbr_entry *olsr_lookup_nbr_entry_alias(const union olsr_ip_addr *);
+void olsr_time_out_two_hop_neighbors(struct nbr_entry *);
+void olsr_expire_nbr2_list(void *);
+void olsr_print_neighbor_table(void);
+int olsr_update_nbr_status(struct nbr_entry *, int);
+
+#endif /* OLSR_NEIGH_TBL */
 
 /*
  * Local Variables:
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