eliminate the data field from an avl_node
authorHannes Gredler <hannes@gredler.at>
Sun, 20 Apr 2008 16:27:25 +0000 (18:27 +0200)
committerHannes Gredler <hannes@gredler.at>
Sun, 20 Apr 2008 16:27:25 +0000 (18:27 +0200)
lib/nameservice/src/nameservice.c
lib/tas/src/plugin.c
lib/txtinfo/src/olsrd_txtinfo.c
src/common/avl.h
src/lq_route.c
src/process_routes.c
src/routing_table.c
src/routing_table.h
src/tc_set.c
src/tc_set.h

index df93286..ca11ebd 100644 (file)
@@ -1552,15 +1552,16 @@ olsr_bool get_isdefhna_latlon(void)
  */
 void lookup_defhna_latlon(union olsr_ip_addr *ip)
 {
+  struct rt_entry *rt;
   struct avl_node *rt_tree_node;
   struct olsr_ip_prefix prefix;
 
   memset(ip, 0, sizeof(ip));
   memset(&prefix, 0, sizeof(prefix));
 
-  if (NULL != (rt_tree_node = avl_find(&routingtree, &prefix)))
-  {
-    *ip = ((struct rt_entry *)rt_tree_node->data)->rt_best->rtp_nexthop.gateway;
+  if (NULL != (rt_tree_node = avl_find(&routingtree, &prefix))) {
+       rt = rt_tree2rt(rt_tree_node);
+    *ip = rt->rt_best->rtp_nexthop.gateway;
   }
 }
 
index 0395cd5..cfc9e7d 100644 (file)
@@ -235,7 +235,7 @@ int iterRouteTabNext(char *buff, int len)
 
   rt_tree_node = avl_walk_next(&iterRouteTab->rt_tree_node);
   if (rt_tree_node) {
-      iterRouteTab = rt_tree_node->data;
+      iterRouteTab = rt_tree2rt(rt_tree_node);
   } else {
       iterRouteTab = NULL;
   }
@@ -251,7 +251,7 @@ void iterRouteTabInit(void)
   routingtree_version = 0;
 
   node = avl_walk_first(&routingtree);
-  iterRouteTab = node ? node->data : NULL;
+  iterRouteTab = node ? rt_tree2rt(node) : NULL;
 
 }
 
@@ -266,11 +266,7 @@ tas_getnext_tc_entry(struct tc_entry *tc)
 {
   struct avl_node *node = avl_walk_next(&tc->vertex_node);
 
-  if (node) {
-    return node->data;
-  }
-
-  return NULL;
+  return (node ? vertex_tree2tc(node) : NULL);
 }
 
 int iterTcTabNext(char *buff, int len)
@@ -321,10 +317,10 @@ void iterTcTabInit(void)
 {
   struct avl_node *node;
   
-  avl_init(&tc_tree, avl_comp_prefix_default);
+  avl_init(&tc_tree, avl_comp_default);
 
   node = avl_walk_first(&tc_tree);
-  iterTcTab = node ? node->data : NULL;
+  iterTcTab = (node ? vertex_tree2tc(node) : NULL);
 }
 
 static void parserFunc(union olsr_message *msg,
index 9070eb9..3ae0ca3 100644 (file)
@@ -371,18 +371,12 @@ static void ipc_print_routes(void)
 {
     struct ipaddr_str buf1, buf2;
     struct rt_entry *rt;
-    struct avl_node *rt_tree_node;
     struct lqtextbuffer lqbuffer;
     
     ipc_sendf("Table: Routes\nDestination\tGateway\tMetric\tETX\tInterface\n");
 
     /* Walk the route table */
-    for (rt_tree_node = avl_walk_first(&routingtree);
-         rt_tree_node;
-         rt_tree_node = avl_walk_next(rt_tree_node)) {
-
-        rt = rt_tree_node->data;
-
+    OLSR_FOR_ALL_RT_ENTRIES(rt) {
         ipc_sendf( "%s/%d\t%s\t%d\t%s\t%s\t\n",
                    olsr_ip_to_string(&buf1, &rt->rt_dst.prefix),
                    rt->rt_dst.prefix_len,
@@ -390,7 +384,8 @@ static void ipc_print_routes(void)
                    rt->rt_best->rtp_metric.hops,
                    get_linkcost_text(rt->rt_best->rtp_metric.cost, OLSR_TRUE, &lqbuffer),
                    if_ifwithindex_name(rt->rt_best->rtp_nexthop.iif_index));
-    }
+    } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+
     ipc_sendf("\n");
 
 }
@@ -422,7 +417,6 @@ static void ipc_print_topology(void)
 static void ipc_print_hna(void)
 {
     int size;
-    int index;
     struct ip_prefix_list *hna;
     struct hna_entry *tmp_hna;
     struct hna_net *tmp_net;
index 5759b51..1d1b294 100644 (file)
@@ -54,7 +54,6 @@ struct avl_node {
   struct avl_node *next;
   struct avl_node *prev;
   void *key;
-  void *data;
   signed char balance;
   unsigned char leader;
 };
@@ -126,6 +125,19 @@ extern int avl_comp_ipv4(const void *, const void *);
 extern int avl_comp_ipv6(const void *, const void *);
 extern int avl_comp_mac(const void *, const void *);
 
+/*
+ * Macro to define an inline function to map from a list_node offset back to the
+ * base of the datastructure. That way you save an extra data pointer.
+ */
+#define AVLNODE2STRUCT(funcname, structname, avlnodename) \
+static inline structname * funcname (struct avl_node *ptr)\
+{\
+  return( \
+    ptr ? \
+      (structname *) (((olsr_u8_t *) ptr) - offsetof(structname, avlnodename)) : \
+      NULL); \
+}
+
 #endif /* _AVL_H */
 
 /*
index cb04f0d..fcfbeec 100644 (file)
@@ -105,7 +105,6 @@ olsr_spf_add_cand_tree (struct avl_tree *tree,
   struct lqtextbuffer lqbuffer;
 #endif
   tc->cand_tree_node.key = &tc->path_cost;
-  tc->cand_tree_node.data = tc;
 
 #ifdef DEBUG
   OLSR_PRINTF(2, "SPF: insert candidate %s, cost %s\n",
@@ -175,7 +174,7 @@ olsr_spf_extract_best (struct avl_tree *tree)
 {
   struct avl_node *node = avl_walk_first(tree);
 
-  return (node ? node->data :  NULL);
+  return (node ? cand_tree2tc(node) :  NULL);
 }
 
 
@@ -210,7 +209,7 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
        edge_node = avl_walk_next(edge_node)) {
 
     struct tc_entry *new_tc;
-    struct tc_edge_entry *tc_edge = edge_node->data;
+    struct tc_edge_entry *tc_edge = edge_tree2tc_edge(edge_node);
 
     /*
      * We are not interested in dead-end or dying edges.
@@ -472,7 +471,7 @@ olsr_calculate_routing_table (void *context __attribute__((unused)))
          rtp_tree_node;
          rtp_tree_node = avl_walk_next(rtp_tree_node)) {
 
-      rtp = rtp_tree_node->data;
+      rtp = rtp_tree2rtp(rtp_tree_node);
 
       if (rtp->rtp_rt) {
 
index a331deb..e5af19e 100644 (file)
@@ -306,7 +306,7 @@ olsr_delete_outdated_routes(struct rt_entry *rt)
      */
     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
 
-    rtp = rtp_tree_node->data;
+    rtp = rtp_tree2rtp(rtp_tree_node);
 
     /*
      * check the version number which gets incremented on every SPF run.
index 0280859..d17ca00 100644 (file)
@@ -186,7 +186,7 @@ olsr_lookup_routing_table(const union olsr_ip_addr *dst)
 
   rt_tree_node = avl_find(&routingtree, &prefix);
 
-  return rt_tree_node ? rt_tree_node->data : NULL;
+  return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
 }
 
 /**
@@ -230,7 +230,6 @@ olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
   rt->rt_dst = *prefix;
 
   rt->rt_tree_node.key = &rt->rt_dst;
-  rt->rt_tree_node.data = rt;
   avl_insert(&routingtree, &rt->rt_tree_node, AVL_DUP_NO);
 
   /* init the originator subtree */
@@ -258,7 +257,6 @@ olsr_alloc_rt_path(struct tc_entry *tc,
 
   /* set key and backpointer prior to tree insertion */
   rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
-  rtp->rtp_prefix_tree_node.data = rtp;
 
   /* insert to the tc prefix tree */
   avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
@@ -312,7 +310,7 @@ olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc,
     }
 
   } else {
-    rt = node->data;
+    rt = rt_tree2rt(node);
   }
 
 
@@ -321,7 +319,6 @@ olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc,
 
   /* set key and backpointer prior to tree insertion */
   rtp->rtp_tree_node.key = &rtp->rtp_originator;
-  rtp->rtp_tree_node.data = rtp;
 
   /* insert to the route entry originator tree */
   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
@@ -476,11 +473,11 @@ olsr_rt_best(struct rt_entry *rt)
 
   assert(node != 0); /* should not happen */
 
-  rt->rt_best = node->data;
+  rt->rt_best = rtp_tree2rtp(node);
 
   /* walk all remaining originator entries */
   while ((node = avl_walk_next(node))) {
-    struct rt_path *rtp = node->data;
+    struct rt_path *rtp = rtp_tree2rtp(node);
 
     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
       rt->rt_best = rtp;
@@ -560,7 +557,7 @@ olsr_insert_routing_table(union olsr_ip_addr *dst, int plen,
     changes_hna = OLSR_TRUE;
 
   } else {
-    rtp = node->data;
+    rtp = rtp_prefix_tree2rtp(node);
   }
 
   return rtp;
@@ -609,7 +606,7 @@ olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
   node = avl_find(&tc->prefix_tree, &prefix);
 
   if (node) {
-    rtp = node->data;
+    rtp = rtp_prefix_tree2rtp(node);
     olsr_free_rt_path(rtp);
 
     /* overload the hna change bit for flagging a prefix change */
@@ -665,21 +662,21 @@ olsr_rtp_to_string(const struct rt_path *rtp)
  *
  */
 void
-olsr_print_routing_table(const struct avl_tree *tree)
+olsr_print_routing_table(struct avl_tree *tree)
 {
 #ifndef NODEBUG
   /* The whole function makes no sense without it. */
-  const struct avl_node *rt_tree_node;
+  struct avl_node *rt_tree_node;
   struct lqtextbuffer lqbuffer;
   
   OLSR_PRINTF(6, "ROUTING TABLE\n");
 
-  for (rt_tree_node = avl_walk_first_c(tree);
+  for (rt_tree_node = avl_walk_first(tree);
        rt_tree_node != NULL;
-       rt_tree_node = avl_walk_next_c(rt_tree_node)) {
-    const struct avl_node *rtp_tree_node;
+       rt_tree_node = avl_walk_next(rt_tree_node)) {
+    struct avl_node *rtp_tree_node;
     struct ipaddr_str prefixstr, origstr, gwstr;
-    const struct rt_entry * const rt = rt_tree_node->data;
+    struct rt_entry *rt = rt_tree2rt(rt_tree_node);
 
     /* first the route entry */
     OLSR_PRINTF(6, "%s/%u, via %s, best-originator %s\n",
@@ -689,10 +686,10 @@ olsr_print_routing_table(const struct avl_tree *tree)
            olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
 
     /* walk the per-originator path tree of routes */
-    for (rtp_tree_node = avl_walk_first_c(&rt->rt_path_tree);
+    for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
          rtp_tree_node != NULL;
-         rtp_tree_node = avl_walk_next_c(rtp_tree_node)) {
-      const struct rt_path * const rtp = rtp_tree_node->data;
+         rtp_tree_node = avl_walk_next(rtp_tree_node)) {
+      struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
       OLSR_PRINTF(6, "\tfrom %s, cost %s, metric %u, via %s, %s, v %u\n",
              olsr_ip_to_string(&origstr, &rtp->rtp_originator),
              get_linkcost_text(rtp->rtp_metric.cost, OLSR_TRUE, &lqbuffer),
index ca11383..83159b0 100644 (file)
@@ -93,6 +93,7 @@ struct rt_entry
   struct list_node      rt_change_node; /* queue for kernel FIB add/chg/del */
 };
 
+AVLNODE2STRUCT(rt_tree2rt, struct rt_entry, rt_tree_node);
 LISTNODE2STRUCT(changelist2rt, struct rt_entry, rt_change_node);
 
 /*
@@ -117,6 +118,9 @@ struct rt_path
   olsr_u8_t             rtp_origin; /* internal, MID or HNA */
 };
 
+AVLNODE2STRUCT(rtp_tree2rtp, struct rt_path, rtp_tree_node);
+AVLNODE2STRUCT(rtp_prefix_tree2rtp, struct rt_path, rtp_prefix_tree_node);
+
 /*
  * In olsrd we have three different route types.
  * Internal routes are generated by simple reachability
@@ -148,7 +152,7 @@ enum olsr_rt_origin {
   for (rt_tree_node = avl_walk_first(&routingtree); \
     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
     next_rt_tree_node = avl_walk_next(rt_tree_node); \
-    rt = rt_tree_node->data;
+    rt = rt_tree2rt(rt_tree_node);
 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
 
 /*
@@ -169,7 +173,7 @@ enum olsr_rt_origin {
   for (rt_tree_node = avl_walk_first(&routingtree); \
     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
     next_rt_tree_node = avl_walk_next(rt_tree_node); \
-    rt = rt_tree_node->data; \
+    rt = rt_tree2rt(rt_tree_node); \
     if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
       continue; 
 #define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }}
@@ -215,7 +219,7 @@ olsr_u8_t olsr_fib_metric(const struct rt_metric *);
 
 char *olsr_rt_to_string(const struct rt_entry *);
 char *olsr_rtp_to_string(const struct rt_path *);
-void olsr_print_routing_table(const struct avl_tree *);
+void olsr_print_routing_table(struct avl_tree *);
 
 const struct rt_nexthop * olsr_get_nh(const struct rt_entry *);
 
index 353da75..f9fe526 100644 (file)
@@ -138,7 +138,6 @@ olsr_add_tc_entry(union olsr_ip_addr *adr)
 
   /* Fill entry */
   tc->addr = *adr;
-  tc->vertex_node.data = tc;
   tc->vertex_node.key = &tc->addr;
 
   /*
@@ -255,11 +254,7 @@ olsr_lookup_tc_entry(union olsr_ip_addr *adr)
 
   node = avl_find(&tc_tree, adr);
 
-  if (node) {
-    return node->data;
-  }
-
-  return NULL;
+  return (node ? vertex_tree2tc(node) : NULL);
 }
 
 /*
@@ -373,7 +368,6 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
   tc_edge->T_dest_addr = *addr;
   olsr_set_tc_edge_timer(tc_edge, vtime*1000);
   tc_edge->T_seq = ansn;
-  tc_edge->edge_node.data = tc_edge;
   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
   
   /*
@@ -615,11 +609,7 @@ olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
 
   edge_node = avl_find(&tc->edge_tree, edge_addr);
 
-  if (edge_node) {
-    return edge_node->data;
-  }
-
-  return NULL;
+  return (edge_node ? edge_tree2tc_edge(edge_node) : NULL);
 }
 
 /**
index 8059dce..cc94a22 100644 (file)
@@ -68,6 +68,8 @@ struct tc_edge_entry
   char               linkquality[0];
 };
 
+AVLNODE2STRUCT(edge_tree2tc_edge, struct tc_edge_entry, edge_node);
+
 #define OLSR_TC_EDGE_DOWN (1 << 0) /* this edge is down */
 #define OLSR_TC_EDGE_JITTER 5 /* percent */
 
@@ -95,6 +97,8 @@ struct tc_entry
   olsr_bool          err_seq_valid; /* do we have an error (unplauible seq/ansn) */
 };
 
+AVLNODE2STRUCT(vertex_tree2tc, struct tc_entry, vertex_node);
+AVLNODE2STRUCT(cand_tree2tc, struct tc_entry, cand_tree_node);
 LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
 
 /*
@@ -111,7 +115,7 @@ LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
   for (tc_tree_node = avl_walk_first(&tc_tree); \
     tc_tree_node; tc_tree_node = next_tc_tree_node) { \
     next_tc_tree_node = avl_walk_next(tc_tree_node); \
-    tc = tc_tree_node->data;
+    tc = vertex_tree2tc(tc_tree_node);
 #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
 
 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
@@ -120,7 +124,7 @@ LISTNODE2STRUCT(pathlist2tc, struct tc_entry, path_list_node);
   for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
     tc_edge_node; tc_edge_node = next_tc_edge_node) { \
     next_tc_edge_node = avl_walk_next(tc_edge_node); \
-    tc_edge = tc_edge_node->data;
+    tc_edge = edge_tree2tc_edge(tc_edge_node);
 #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
 
 extern struct avl_tree tc_tree;