convert the nbr_list references subtree to use avl trees
authorHannes Gredler <hannes@gredler.at>
Fri, 29 May 2009 18:45:51 +0000 (20:45 +0200)
committerHannes Gredler <hannes@gredler.at>
Fri, 29 May 2009 18:45:51 +0000 (20:45 +0200)
src/lq_mpr.c
src/mpr.c
src/neighbor_table.c
src/process_package.c
src/two_hop_neighbor_table.c
src/two_hop_neighbor_table.h

index 4c2769c..ff25079 100644 (file)
@@ -109,63 +109,66 @@ olsr_calculate_lq_mpr(void)
       best_1hop = lnk->linkcost;
 
       /* 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)
+      OLSR_FOR_ALL_NBR_LIST_ENTRIES(neigh2, walker) {
+        if (walker->path_linkcost < best_1hop) {
           break;
+        }
+      } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(neigh2, walker);
 
       /* 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)
+      if (!walker) {
         continue;
-    }
+      }
 
-    /* find the connecting 1-hop neighbours with the
-     * best total link qualities */
+      /* find the connecting 1-hop neighbours with the
+       * best total link qualities */
 
-    /* mark all 1-hop neighbours as not selected */
+      /* mark all 1-hop neighbours as not selected */
 
-    for (walker = neigh2->nbr2_nblist.next; walker != &neigh2->nbr2_nblist; walker = walker->next)
-      walker->neighbor->skip = false;
+      OLSR_FOR_ALL_NBR_LIST_ENTRIES(neigh2, walker) {
+        walker->neighbor->skip = false;
+      } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(neigh2, walker);
 
-    for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
-      /* look for the best 1-hop neighbour that we haven't
-       * yet 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;
+        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;
-        }
+        OLSR_FOR_ALL_NBR_LIST_ENTRIES(neigh2, walker) {
+          if (walker->neighbor->status == SYM && !walker->neighbor->skip && walker->path_linkcost < best) {
+            neigh = walker->neighbor;
+            best = walker->path_linkcost;
+          }
+        } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(neigh2, walker);
 
-      /* 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;
+        /* 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 (neigh->is_mpr != neigh->was_mpr)
+            mpr_changes = true;
+        }
 
-      /* no neighbour found => the requested MPR coverage cannot
-       * be satisfied => stop */
+        /* no neighbour found => the requested MPR coverage cannot
+         * be satisfied => stop */
 
-      else
-        break;
-    }
-  } OLSR_FOR_ALL_NBR2_ENTRIES_END(NEIGH2);
+        else
+          break;
+      }
+    } OLSR_FOR_ALL_NBR2_ENTRIES_END(NEIGH2);
 
-  if (mpr_changes && olsr_cnf->tc_redundancy > 0)
-    signal_link_changes(true);
+    if (mpr_changes && olsr_cnf->tc_redundancy > 0)
+      signal_link_changes(true);
+  }
 }
-
 /*
  * Local Variables:
  * c-basic-offset: 2
index 1b8cf46..353550b 100644 (file)
--- a/src/mpr.c
+++ b/src/mpr.c
@@ -100,14 +100,11 @@ olsr_chosen_mpr(struct nbr_entry *one_hop_neighbor, uint16_t * two_hop_covered_c
                  olsr_ip_to_string(&buf, &second_hop_entries->nbr2->nbr2_addr));
       continue;
     }
-    //      if(!second_hop_entries->nbr2->nbr2_state)
-    //if(second_hop_entries->nbr2->mpr_covered_count < olsr_cnf->mpr_coverage)
-    //{
+
     /*
-       Now the neighbor is covered by this mpr
+     * Now the neighbor is covered by this mpr
      */
     second_hop_entries->nbr2->mpr_covered_count++;
-    the_one_hop_list = second_hop_entries->nbr2->nbr2_nblist.next;
 
     OLSR_DEBUG(LOG_MPR, "[%s] has coverage %d\n",
                olsr_ip_to_string(&buf, &second_hop_entries->nbr2->nbr2_addr),
@@ -116,15 +113,13 @@ olsr_chosen_mpr(struct nbr_entry *one_hop_neighbor, uint16_t * two_hop_covered_c
     if (second_hop_entries->nbr2->mpr_covered_count >= olsr_cnf->mpr_coverage)
       count++;
 
-    while (the_one_hop_list != &second_hop_entries->nbr2->nbr2_nblist) {
-
+    OLSR_FOR_ALL_NBR_LIST_ENTRIES(second_hop_entries->nbr2, the_one_hop_list) {
       if ((the_one_hop_list->neighbor->status == SYM)) {
         if (second_hop_entries->nbr2->mpr_covered_count >= olsr_cnf->mpr_coverage) {
           the_one_hop_list->neighbor->nbr2_nocov--;
         }
       }
-      the_one_hop_list = the_one_hop_list->next;
-    }
+    } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(second_hop_entries->nbr2, the_one_hop_list);
   } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(one_hop_neighbor, second_hop_entries);
 
   *two_hop_covered_count = count;
@@ -362,7 +357,7 @@ olsr_calculate_mpr(void)
         continue;
       }
 
-      nbr = nbr2->nbr2_nblist.next->neighbor;
+      nbr = nbr_list_node_to_nbr_list(avl_walk_first(&nbr2->nbr2_nbr_list_tree))->neighbor;
 
       /* Already an elected MPR ? */
       if (nbr->is_mpr) {
index 652b527..d8bfaa1 100644 (file)
@@ -210,7 +210,7 @@ olsr_delete_nbr_entry(const union olsr_ip_addr * addr)
   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) {
-    olsr_delete_neighbor_pointer(nbr2_list->nbr2, nbr);
+    olsr_delete_nbr_list_by_addr(nbr2_list->nbr2, &nbr->neighbor_main_addr);
     olsr_delete_nbr2_list_entry(nbr2_list);
   } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list);
 
@@ -373,7 +373,7 @@ olsr_expire_nbr2_list(void *context)
   nbr = nbr2_list->nbr2_nbr;
   nbr2 = nbr2_list->nbr2;
 
-  olsr_delete_neighbor_pointer(nbr2, nbr);
+  olsr_delete_nbr_list_by_addr(nbr2, &nbr->neighbor_main_addr);
   olsr_delete_nbr2_list_entry(nbr2_list);
 }
 
index 8e5f6ed..b586f17 100644 (file)
@@ -118,8 +118,8 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
        * loop through the one-hop neighbors that see this
        * 'two_hop_neighbor'
        */
-      for (nbr_list = nbr2_list->nbr2->nbr2_nblist.next;
-           nbr_list != &nbr2_list->nbr2->nbr2_nblist; nbr_list = nbr_list->next) {
+      OLSR_FOR_ALL_NBR_LIST_ENTRIES(nbr2_list->nbr2, nbr_list) {
+
         /*
          * have we found the one-hop neighbor that sent the
          * HELLO message that we're current processing?
@@ -127,7 +127,7 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
         if (nbr_list->neighbor == neighbor) {
           nbr_list->path_linkcost = LINK_COST_BROKEN;
         }
-      }
+      } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(nbr2_list->nbr2, nbr_list);
     } else {
       struct nbr2_entry *two_hop_neighbor = olsr_add_nbr2_entry(&message_neighbors->addr);
 
@@ -168,11 +168,10 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
       }
 
       /*
-       *  loop through the one-hop neighbors that see this
-       * 'nbr2_list->nbr2'
+       * Loop through the one-hop neighbors that see this 'nbr2_list->nbr2'
        */
-      for (nbr_list = nbr2_list->nbr2->nbr2_nblist.next;
-           nbr_list != &nbr2_list->nbr2->nbr2_nblist; nbr_list = nbr_list->next) {
+      OLSR_FOR_ALL_NBR_LIST_ENTRIES(nbr2_list->nbr2, nbr_list) {
+
         /*
          * have we found the one-hop neighbor that sent the
          * HELLO message that we're current processing?
@@ -202,7 +201,7 @@ process_message_neighbors(struct nbr_entry *neighbor, const struct lq_hello_mess
             }
           }
         }
-      }
+      } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(nbr2_list->nbr2, nbr_list);
     }
   }
 }
index 8edf879..8abc079 100644 (file)
@@ -92,6 +92,21 @@ olsr_unlock_nbr2(struct nbr2_entry *nbr2)
   olsr_delete_two_hop_neighbor_table(nbr2);
 }
 
+/*
+ * Lookup a neighbor list. 
+ */
+static struct nbr_list_entry *
+olsr_lookup_nbr_list_entry(struct nbr2_entry *nbr2, const union olsr_ip_addr *addr)
+{
+  struct avl_node *node;
+
+  node = avl_find(&nbr2->nbr2_nbr_list_tree, addr);
+  if (node) {
+    return nbr_list_node_to_nbr_list(node);
+  }
+  return NULL;
+}
+
 /**
  *Remove a one hop neighbor from a two hop neighbors
  *one hop list.
@@ -103,22 +118,17 @@ olsr_unlock_nbr2(struct nbr2_entry *nbr2)
  *@return nada
  */
 void
-olsr_delete_neighbor_pointer(struct nbr2_entry *two_hop_entry, struct nbr_entry *neigh)
+olsr_delete_nbr_list_by_addr(struct nbr2_entry *nbr2, const union olsr_ip_addr *addr)
 {
-  struct nbr_list_entry *entry = two_hop_entry->nbr2_nblist.next;
-  while (entry != &two_hop_entry->nbr2_nblist) {
-    if (entry->neighbor == neigh) {
-      struct nbr_list_entry *entry_to_delete = entry;
-      entry = entry->next;
-
-      /* dequeue */
-      DEQUEUE_ELEM(entry_to_delete);
-
-      free(entry_to_delete);
-    } else {
-      entry = entry->next;
-    }
+  struct nbr_list_entry *nbr_list;
+
+  nbr_list = olsr_lookup_nbr_list_entry(nbr2, addr);
+  if (!nbr_list) {
+    return;
   }
+
+  avl_delete(&nbr2->nbr2_nbr_list_tree, &nbr_list->nbr_list_node);
+  free(nbr_list);
 }
 
 /**
@@ -144,17 +154,18 @@ olsr_delete_two_hop_neighbor_table(struct nbr2_entry *nbr2)
         olsr_delete_nbr2_list_entry(nbr2_list);
         break;
       }
-    } OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list)
-  } OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
+    }
+    OLSR_FOR_ALL_NBR2_LIST_ENTRIES_END(nbr, nbr2_list)
+  }
+  OLSR_FOR_ALL_NBR_ENTRIES_END(nbr);
 
   /*
    * Delete all the one hop backlinks hanging off this nbr2
    */
-  while (nbr2->nbr2_nblist.next != &nbr2->nbr2_nblist) {
-    nbr_list = nbr2->nbr2_nblist.next; 
-    DEQUEUE_ELEM(nbr_list);
-    free(nbr_list);
+  OLSR_FOR_ALL_NBR_LIST_ENTRIES(nbr2, nbr_list) {
+    avl_delete(&nbr2->nbr2_nbr_list_tree, &nbr_list->nbr_list_node);
   }
+  OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(nbr2, nbr_list);
 
   avl_delete(&nbr2_tree, &nbr2->nbr2_node);
   free(nbr2);
@@ -186,8 +197,10 @@ olsr_add_nbr2_entry(const union olsr_ip_addr *addr)
   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;
+
+  /* Init neighbor reference subtree */
+  avl_init(&nbr2->nbr2_nbr_list_tree, avl_comp_default);
+
   nbr2->nbr2_refcount = 0;
   nbr2->nbr2_addr = *addr;
 
@@ -242,6 +255,34 @@ olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *addr)
   return olsr_lookup_nbr2_entry_alias(main_addr);
 }
 
+/*
+ * Add a nbr_list reference to a nbr2 refernce subtree.
+ */
+static void
+olsr_add_nbr_list_entry(struct nbr_entry *nbr, struct nbr2_entry *nbr2)
+{
+  struct nbr_list_entry *nbr_list;
+
+  /*
+   * Check if the entry exists.
+   */
+  nbr_list = olsr_lookup_nbr_list_entry(nbr2, &nbr->neighbor_main_addr);
+  if (!nbr_list) {
+
+    /*
+     * Unknown, Create a fresh one.
+     */
+    nbr_list = olsr_malloc(sizeof(struct nbr_list_entry), "Link entries 1");
+    nbr_list->neighbor = nbr;   /* XXX refcount */
+    nbr_list->second_hop_linkcost = LINK_COST_BROKEN;
+    nbr_list->path_linkcost = LINK_COST_BROKEN;
+    nbr_list->saved_path_linkcost = LINK_COST_BROKEN;
+
+    nbr_list->nbr_list_node.key = &nbr->neighbor_main_addr;
+    avl_insert(&nbr2->nbr2_nbr_list_tree, &nbr_list->nbr_list_node, AVL_DUP_NO);
+  }
+}
+
 /**
  * Links a one-hop neighbor with a 2-hop neighbor.
  *
@@ -252,22 +293,7 @@ olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *addr)
 void
 olsr_link_nbr_nbr2(struct nbr_entry *nbr, struct nbr2_entry *nbr2, float vtime)
 {
-  struct nbr_list_entry *nbr_list;
-
-  nbr_list = olsr_malloc(sizeof(struct nbr_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->nbr2_nblist.next->prev = nbr_list;
-  nbr_list->next = nbr2->nbr2_nblist.next;
-  nbr2->nbr2_nblist.next = nbr_list;
-  nbr_list->prev = &nbr2->nbr2_nblist;
-
+  olsr_add_nbr_list_entry(nbr, nbr2);
   olsr_add_nbr2_list_entry(nbr, nbr2, vtime);
 }
 
@@ -284,6 +310,8 @@ olsr_print_two_hop_neighbor_table(void)
   /* The whole function makes no sense without it. */
   struct nbr2_entry *neigh2;
   struct nbr_list_entry *entry;
+  struct ipaddr_str buf;
+  struct lqtextbuffer lqbuffer;
   bool first;
 
   OLSR_INFO(LOG_2NEIGH, "\n--- %s ----------------------- TWO-HOP NEIGHBORS\n\n"
@@ -291,18 +319,14 @@ olsr_print_two_hop_neighbor_table(void)
 
   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;
-
+    OLSR_FOR_ALL_NBR_LIST_ENTRIES(neigh2, entry) {
       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;
-    }
+    } OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(neigh2, entry);
   } OLSR_FOR_ALL_NBR2_ENTRIES_END(neigh2);
 #endif
 }
index 98a81e2..afbd58a 100644 (file)
 
 
 struct nbr_list_entry {
+  struct avl_node nbr_list_node;
   struct nbr_entry *neighbor;          /* backpointer to owning nbr entry */
   olsr_linkcost second_hop_linkcost;
   olsr_linkcost path_linkcost;
   olsr_linkcost saved_path_linkcost;
-  struct nbr_list_entry *next;
-  struct nbr_list_entry *prev;
 };
 
+AVLNODE2STRUCT(nbr_list_node_to_nbr_list, struct nbr_list_entry, nbr_list_node);
 
 struct nbr2_entry {
   struct avl_node nbr2_node;
@@ -66,13 +66,13 @@ struct nbr2_entry {
   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;
+  struct avl_tree nbr2_nbr_list_tree;  /* subtree for nbr pointers */
 } __attribute__ ((packed));;
 
 AVLNODE2STRUCT(nbr2_node_to_nbr2, struct nbr2_entry, nbr2_node);
 
 /*
- * macros for traversing two-hop neighbors.
+ * macros for traversing two-hop neighbors and neighbor ref lists.
  * it is recommended to use this because it hides all the internal
  * datastructure from the callers.
  *
@@ -88,6 +88,15 @@ AVLNODE2STRUCT(nbr2_node_to_nbr2, struct nbr2_entry, nbr2_node);
     nbr2 = nbr2_node_to_nbr2(nbr2_tree_node);
 #define OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2) }}
 
+#define OLSR_FOR_ALL_NBR_LIST_ENTRIES(nbr2, nbr_list) \
+{ \
+  struct avl_node *nbr_list_node, *next_nbr_list_node; \
+  for (nbr_list_node = avl_walk_first(&nbr2->nbr2_nbr_list_tree); \
+    nbr_list_node; nbr_list_node = next_nbr_list_node) { \
+    next_nbr_list_node = avl_walk_next(nbr_list_node); \
+    nbr_list = nbr_list_node_to_nbr_list(nbr_list_node);
+#define OLSR_FOR_ALL_NBR_LIST_ENTRIES_END(nbr2, nbr_list) }}
+
 /*
  * The two hop neighbor tree
  */
@@ -96,7 +105,7 @@ 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_nbr_list_by_addr(struct nbr2_entry *, const union olsr_ip_addr *);
 void olsr_delete_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 *);