Squashed commit of the following:
authorHenning Rogge <hrogge@googlemail.com>
Tue, 13 Jul 2010 16:51:44 +0000 (18:51 +0200)
committerHenning Rogge <hrogge@googlemail.com>
Tue, 13 Jul 2010 16:51:44 +0000 (18:51 +0200)
commit 32a35a124746e3ed02f78d92f528311b8132a031
Author: Henning Rogge <hrogge@googlemail.com>
Date:   Tue Jul 13 18:36:56 2010 +0200

    Small fix for avl conversion

commit 338cf516764351fddaef384b80a426e142c16c00
Author: Henning Rogge <hrogge@googlemail.com>
Date:   Tue Jul 13 17:59:49 2010 +0200

    Convert OLSRd to new AVL tree library

44 files changed:
lib/cl_roam/src/cl_roam.c
lib/debuginfo/src/olsrd_debuginfo.c
lib/debuginfo/src/olsrd_debuginfo.h
lib/dot_draw/src/olsrd_dot_draw.c
lib/httpinfo/src/olsrd_httpinfo.c
lib/lq_etx_ff/src/lq_plugin_etx_ff.c
lib/nameservice/src/mapwrite.c
lib/nameservice/src/nameservice.c
lib/quagga/src/quagga.c
lib/txtinfo/src/olsrd_txtinfo.c
src/common/avl.c
src/common/avl.h
src/common/avl_comp.c [new file with mode: 0644]
src/common/avl_comp.h [new file with mode: 0644]
src/common/avl_olsr_comp.c
src/common/avl_olsr_comp.h
src/duplicate_set.c
src/duplicate_set.h
src/hna_set.c
src/hna_set.h
src/interfaces.c
src/interfaces.h
src/lq_mpr.c
src/main.c
src/mid_set.c
src/mid_set.h
src/neighbor_table.c
src/neighbor_table.h
src/net_olsr.c
src/net_olsr.h
src/olsr_comport_http.c
src/olsr_comport_http.h
src/olsr_comport_txt.c
src/olsr_comport_txt.h
src/olsr_cookie.c
src/olsr_cookie.h
src/olsr_spf.c
src/plugin_loader.c
src/plugin_loader.h
src/process_routes.c
src/routing_table.c
src/routing_table.h
src/tc_set.c
src/tc_set.h

index 63cc648..fb69819 100644 (file)
@@ -178,6 +178,7 @@ struct guest_client * get_client_by_ip(union olsr_ip_addr ip) {
 static void *
 relay_spread_host(union olsr_ip_addr host_ip, union olsr_ip_addr master_ip, uint8_t TTL, uint8_t Hopcount) {
   struct interface *ifp;
+  struct list_iterator iterator;
   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
   uint8_t *curr = msg_buffer;
   uint8_t *length_field, *last;
@@ -215,17 +216,16 @@ relay_spread_host(union olsr_ip_addr host_ip, union olsr_ip_addr master_ip, uint
   //Put in Message size
   pkt_put_u16(&length_field, curr - msg_buffer);
 
-  OLSR_FOR_ALL_INTERFACES(ifp)
-        {
-          if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
-            net_output(ifp);
-            set_buffer_timer(ifp);
-          }
-          // buffer gets pushed NOW
-          net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
-          net_output(ifp);
-          set_buffer_timer(ifp);
-        }OLSR_FOR_ALL_INTERFACES_END(ifp)
+  OLSR_FOR_ALL_INTERFACES(ifp, iterator) {
+    if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
+      net_output(ifp);
+      set_buffer_timer(ifp);
+    }
+    // buffer gets pushed NOW
+    net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
+    net_output(ifp);
+    set_buffer_timer(ifp);
+  }
 
   OLSR_INFO(LOG_PLUGINS, "Relayed some foo!");
 
@@ -787,17 +787,16 @@ static void olsr_event1(void *foo __attribute__ ((unused)) ) {
 
 static void olsr_event2(void *foo  __attribute__ ((unused))) {
   struct nbr_entry *nbr;
+  struct list_iterator iterator;
 
-  OLSR_FOR_ALL_NBR_ENTRIES(nbr)
-        {
-          int rc;
-          pthread_t thread;
-          rc = pthread_create(&thread, NULL, check_neighbour_host, (void *) nbr);
-          if (rc) {
-            printf("ERROR; return code from pthread_create() is %d\n", rc);
-            exit(-1);
-          }
-
-        }OLSR_FOR_ALL_NBR_ENTRIES_END();
+  OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) {
+    int rc;
+    pthread_t thread;
+    rc = pthread_create(&thread, NULL, check_neighbour_host, (void *) nbr);
+    if (rc) {
+      printf("ERROR; return code from pthread_create() is %d\n", rc);
+      exit(-1);
+    }
+  }
 }
 
index e151b60..4c35b10 100644 (file)
@@ -208,8 +208,8 @@ olsrd_plugin_init(void)
 
   memset(&total_msg_traffic, 0, sizeof(total_msg_traffic));
   memset(&total_pkt_traffic, 0, sizeof(total_pkt_traffic));
-  avl_init(&stat_msg_tree, avl_comp_default);
-  avl_init(&stat_pkt_tree, avl_comp_default);
+  avl_init(&stat_msg_tree, avl_comp_default, false, NULL);
+  avl_init(&stat_pkt_tree, avl_comp_default, false, NULL);
 
   olsr_parser_add_function(&olsr_msg_statistics, PROMISCUOUS);
   olsr_preprocessor_add_function(&olsr_packet_statistics);
@@ -225,7 +225,7 @@ static struct debug_msgtraffic *get_msgtraffic_entry(union olsr_ip_addr *ip) {
     memcpy(&tr->ip, ip, sizeof(union olsr_ip_addr));
     tr->node.key = &tr->ip;
 
-    avl_insert(&stat_msg_tree, &tr->node, false);
+    avl_insert(&stat_msg_tree, &tr->node);
   }
   return tr;
 }
@@ -241,7 +241,7 @@ static struct debug_pkttraffic *get_pkttraffic_entry(union olsr_ip_addr *ip, str
 
     tr->int_name = strdup(in ? in->int_name : "---");
 
-    avl_insert(&stat_pkt_tree, &tr->node, false);
+    avl_insert(&stat_pkt_tree, &tr->node);
   }
   return tr;
 }
@@ -251,6 +251,7 @@ update_statistics_ptr(void *data __attribute__ ((unused)))
 {
   struct debug_msgtraffic *msg;
   struct debug_pkttraffic *pkt;
+  struct list_iterator iterator;
   uint32_t last_slot, i;
 
   last_slot = current_slot;
@@ -260,7 +261,7 @@ update_statistics_ptr(void *data __attribute__ ((unused)))
   }
 
   /* move data from "current" template to slot array */
-  OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(msg) {
+  OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(msg, iterator) {
     /* subtract old values from node count and total count */
     for (i=0; i<DTR_MSG_COUNT; i++) {
       msg->total.data[i] -= msg->traffic[current_slot].data[i];
@@ -283,9 +284,9 @@ update_statistics_ptr(void *data __attribute__ ((unused)))
       avl_delete(&stat_msg_tree, &msg->node);
       olsr_cookie_free(statistics_msg_mem, msg);
     }
-  } OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES_END()
+  }
 
-  OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(pkt) {
+  OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(pkt, iterator) {
     /* subtract old values from node count and total count */
     for (i=0; i<DTR_PKT_COUNT; i++) {
       pkt->total.data[i] -= pkt->traffic[current_slot].data[i];
@@ -309,7 +310,7 @@ update_statistics_ptr(void *data __attribute__ ((unused)))
       free(pkt->int_name);
       olsr_cookie_free(statistics_pkt_mem, pkt);
     }
-  } OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES_END()
+  }
 }
 
 /* update message statistics */
@@ -405,6 +406,7 @@ debuginfo_msgstat(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param __attribute__ ((unused)))
 {
   struct debug_msgtraffic *tr;
+  struct list_iterator iterator;
 
   if (abuf_appendf(&con->out, "Slot size: %d seconds\tSlot count: %d\n", traffic_interval, traffic_slots) < 0) {
     return ABUF_ERROR;
@@ -417,11 +419,11 @@ debuginfo_msgstat(struct comport_connection *con,
   }
 
   if (param == NULL || strcasecmp(param, "node") == 0) {
-    OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(tr) {
+    OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(tr, iterator) {
       if (debuginfo_print_msgstat(&con->out, &tr->ip, &tr->traffic[current_slot])) {
         return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES_END()
+    }
   }
   else {
     uint32_t mult = 1, divisor = 1;
@@ -451,14 +453,14 @@ debuginfo_msgstat(struct comport_connection *con,
       return CONTINUE;
     }
 
-    OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(tr) {
+    OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(tr, iterator) {
       for (i=0; i<DTR_MSG_COUNT; i++) {
         cnt.data[i] = (tr->total.data[i] * mult) / divisor;
       }
       if (debuginfo_print_msgstat(&con->out, &tr->ip, &cnt)) {
         return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES_END()
+    }
   }
 
   return CONTINUE;
@@ -478,6 +480,7 @@ debuginfo_pktstat(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param __attribute__ ((unused)))
 {
   struct debug_pkttraffic *tr;
+  struct list_iterator iterator;
 
   if (abuf_appendf(&con->out, "Slot size: %d seconds\tSlot count: %d\n", traffic_interval, traffic_slots) < 0) {
     return ABUF_ERROR;
@@ -490,11 +493,11 @@ debuginfo_pktstat(struct comport_connection *con,
   }
 
   if (param == NULL || strcasecmp(param, "node") == 0) {
-    OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(tr) {
+    OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(tr, iterator) {
       if (debuginfo_print_pktstat(&con->out, &tr->ip, tr->int_name, &tr->traffic[current_slot])) {
         return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES_END()
+    }
   }
   else {
     uint32_t mult = 1, divisor = 1;
@@ -524,14 +527,14 @@ debuginfo_pktstat(struct comport_connection *con,
       return CONTINUE;
     }
 
-    OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(tr) {
+    OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(tr, iterator) {
       for (i=0; i<DTR_PKT_COUNT; i++) {
         cnt.data[i] = (tr->total.data[i] * mult) / divisor;
       }
       if (debuginfo_print_pktstat(&con->out, &tr->ip, tr->int_name, &cnt)) {
         return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES_END()
+    }
   }
 
   return CONTINUE;
@@ -539,8 +542,9 @@ debuginfo_pktstat(struct comport_connection *con,
 
 static INLINE bool debuginfo_print_cookies_mem(struct autobuf *buf, const char *format) {
   struct olsr_cookie_info *c;
+  struct list_iterator iterator;
 
-  OLSR_FOR_ALL_COOKIES(c) {
+  OLSR_FOR_ALL_COOKIES(c, iterator) {
     if (c == NULL || c->ci_type != OLSR_COOKIE_TYPE_MEMORY) {
       continue;
     }
@@ -549,14 +553,15 @@ static INLINE bool debuginfo_print_cookies_mem(struct autobuf *buf, const char *
         (unsigned long)c->ci_size, c->ci_usage, c->ci_free_list_usage) < 0) {
       return true;
     }
-  } OLSR_FOR_ALL_COOKIES_END()
+  }
   return false;
 }
 
 static INLINE bool debuginfo_print_cookies_timer(struct autobuf *buf, const char *format) {
   struct olsr_cookie_info *c;
+  struct list_iterator iterator;
 
-  OLSR_FOR_ALL_COOKIES(c) {
+  OLSR_FOR_ALL_COOKIES(c, iterator) {
     if (c == NULL || c->ci_type != OLSR_COOKIE_TYPE_TIMER) {
       continue;
     }
@@ -564,7 +569,7 @@ static INLINE bool debuginfo_print_cookies_timer(struct autobuf *buf, const char
                        c->ci_usage, c->ci_changes) < 0) {
       return true;
     }
-  } OLSR_FOR_ALL_COOKIES_END()
+  }
   return false;
 }
 
index fa164c4..7ba3312 100644 (file)
@@ -100,13 +100,8 @@ struct debug_pkttraffic {
   struct debug_pkttraffic_count traffic[0];
 };
 
-AVLNODE2STRUCT(msgnode2traffic, debug_msgtraffic, node);
-#define OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(tr) OLSR_FOR_ALL_AVL_ENTRIES(&stat_msg_tree, msgnode2traffic, tr)
-#define OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
-
-AVLNODE2STRUCT(pktnode2traffic, debug_pkttraffic, node);
-#define OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(tr) OLSR_FOR_ALL_AVL_ENTRIES(&stat_pkt_tree, pktnode2traffic, tr)
-#define OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_MSGTRAFFIC_ENTRIES(tr, iterator) avl_for_each_element_safe(&stat_msg_tree, tr, node, iterator.loop, iterator.safe)
+#define OLSR_FOR_ALL_PKTTRAFFIC_ENTRIES(tr, iterator) avl_for_each_element_safe(&stat_pkt_tree, tr, node, iterator.loop, iterator.safe)
 
 #endif
 
index 8b905eb..0b20410 100644 (file)
@@ -264,37 +264,34 @@ pcf_event(int ipc_connection, int chgs_neighborhood, int chgs_topology, int chgs
     struct nbr_entry *neighbor_table_tmp;
     struct tc_entry *tc;
     struct ip_prefix_entry *hna;
-    struct list_iterator iterator;
+    struct list_iterator iterator, iterator2;
 
     /* Print tables to IPC socket */
     ipc_send_str(ipc_connection, "digraph topology\n{\n");
 
     /* Neighbors */
-    OLSR_FOR_ALL_NBR_ENTRIES(neighbor_table_tmp) {
+    OLSR_FOR_ALL_NBR_ENTRIES(neighbor_table_tmp, iterator) {
       ipc_print_neigh_link(ipc_connection, neighbor_table_tmp);
-    } OLSR_FOR_ALL_NBR_ENTRIES_END();
+    }
 
     /* Topology */
-    OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
       struct tc_edge_entry *tc_edge;
-      OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+      OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator2) {
         if (tc_edge->edge_inv) {
           ipc_print_tc_link(ipc_connection, tc, tc_edge);
         }
       }
-      OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
     }
-    OLSR_FOR_ALL_TC_ENTRIES_END();
 
     /* HNA entries */
-    OLSR_FOR_ALL_TC_ENTRIES(tc) {
+    OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
       /* Check all networks */
       struct hna_net *tmp_net;
-      OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, tmp_net) {
+      OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, tmp_net, iterator2) {
         ipc_print_net(ipc_connection, &tc->addr, &tmp_net->hna_prefix);
       }
-    } OLSR_FOR_ALL_TC_HNA_ENTRIES_END();
-    OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+    }
 
     /* Local HNA entries */
     OLSR_FOR_ALL_IPPREFIX_ENTRIES(&olsr_cnf->hna_entries, hna, iterator) {
index a3bd321..17ad26e 100644 (file)
@@ -770,6 +770,8 @@ static void
 build_routes_body(struct autobuf *abuf)
 {
   struct rt_entry *rt;
+  struct list_iterator iterator;
+
   const char *colspan = resolve_ip_addresses ? " colspan=\"2\"" : "";
   section_title(abuf, "OLSR Routes in Kernel");
   abuf_appendf(abuf,
@@ -777,9 +779,9 @@ build_routes_body(struct autobuf *abuf)
                colspan, colspan);
 
   /* Walk the route table */
-  OLSR_FOR_ALL_RT_ENTRIES(rt) {
+  OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
     build_route(abuf, rt);
-  } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+  }
 
   abuf_puts(abuf, "</table>\n");
 }
@@ -929,7 +931,7 @@ build_neigh_body(struct autobuf *abuf)
 {
   struct nbr_entry *neigh;
   struct link_entry *lnk;
-  struct list_iterator iterator;
+  struct list_iterator iterator, iterator2;
   size_t i;
   const char *colspan = resolve_ip_addresses ? " colspan=\"2\"" : "";
 
@@ -963,7 +965,7 @@ build_neigh_body(struct autobuf *abuf)
                "<tr><th%s>IP Address</th><th>SYM</th><th>MPR</th><th>MPRS</th><th>Willingness</th><th>2 Hop Neighbors</th></tr>\n",
                colspan);
   /* Neighbors */
-  OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
+  OLSR_FOR_ALL_NBR_ENTRIES(neigh, iterator) {
     struct nbr_con *connector;
     int thop_cnt;
     abuf_puts(abuf, "<tr>");
@@ -981,13 +983,13 @@ build_neigh_body(struct autobuf *abuf)
     abuf_puts(abuf, "<td><select>\n" "<option>IP ADDRESS</option>\n");
 
     thop_cnt = 0;
-    OLSR_FOR_ALL_NBR_CON_ENTRIES(neigh, connector) {
+    OLSR_FOR_ALL_NBR_CON_ENTRIES(neigh, connector, iterator2) {
       struct ipaddr_str strbuf;
       abuf_appendf(abuf, "<option>%s</option>\n", olsr_ip_to_string(&strbuf, &connector->nbr2->nbr2_addr));
       thop_cnt++;
-    } OLSR_FOR_ALL_NBR_CON_ENTRIES_END()
+    }
     abuf_appendf(abuf, "</select> (%d)</td></tr>\n", thop_cnt);
-  } OLSR_FOR_ALL_NBR_ENTRIES_END()
+  }
 
   abuf_puts(abuf, "</table>\n");
 }
@@ -996,6 +998,7 @@ static void
 build_topo_body(struct autobuf *abuf)
 {
   struct tc_entry *tc;
+  struct list_iterator iterator, iterator2;
   const char *colspan = resolve_ip_addresses ? " colspan=\"2\"" : "";
 
   section_title(abuf, "Topology Entries");
@@ -1003,9 +1006,9 @@ build_topo_body(struct autobuf *abuf)
   abuf_puts(abuf, "<th colspan=\"3\">Linkcost</th>");
   abuf_puts(abuf, "</tr>\n");
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct tc_edge_entry *tc_edge;
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator2) {
       if (tc_edge->edge_inv) {
         char lqbuffer[LQTEXT_MAXLENGTH];
         abuf_puts(abuf, "<tr>");
@@ -1015,8 +1018,8 @@ build_topo_body(struct autobuf *abuf)
                      olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer, sizeof(lqbuffer)));
         abuf_puts(abuf, "</tr>\n");
       }
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
-  } OLSR_FOR_ALL_TC_ENTRIES_END();
+    }
+  }
 
   abuf_puts(abuf, "</table>\n");
 }
@@ -1025,24 +1028,25 @@ static void
 build_mid_body(struct autobuf *abuf)
 {
   struct tc_entry *tc;
+  struct list_iterator iterator, iterator2;
   const char *colspan = resolve_ip_addresses ? " colspan=\"2\"" : "";
 
   section_title(abuf, "MID Entries");
   abuf_appendf(abuf, "<tr><th%s>Main Address</th><th>Aliases</th></tr>\n", colspan);
 
   /* MID */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct mid_entry *alias;
     abuf_puts(abuf, "<tr>");
     build_ipaddr_with_link(abuf, &tc->addr, -1);
     abuf_puts(abuf, "<td><select>\n<option>IP ADDRESS</option>\n");
 
-    OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+    OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator2) {
       struct ipaddr_str strbuf;
       abuf_appendf(abuf, "<option>%s</option>\n", olsr_ip_to_string(&strbuf, &alias->mid_alias_addr));
-    } OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
+    }
     abuf_appendf(abuf, "</select> (%u)</td></tr>\n", tc->mid_tree.count);
-  } OLSR_FOR_ALL_TC_ENTRIES_END();
+  }
 
   abuf_puts(abuf, "</table>\n");
 }
index 0b803aa..e051b67 100644 (file)
@@ -258,9 +258,9 @@ lq_etxff_timer(void __attribute__ ((unused)) * context)
     link->linkcost = lq_etxff_calc_link_entry_cost(link);
   }
 
-  OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
+  OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) {
     olsr_neighbor_cost_may_changed(nbr);
-  } OLSR_FOR_ALL_NBR_ENTRIES_END()
+  }
 }
 
 static struct timer_entry *lq_etxff_timer_struct = NULL;
index 15737f4..fdc8adb 100644 (file)
@@ -99,7 +99,7 @@ mapwrite_work(FILE * fmap)
   struct ipaddr_str strbuf1, strbuf2;
   struct tc_entry *tc;
   struct tc_edge_entry *tc_edge;
-
+  struct list_iterator iterator, iterator2;
   if (!my_names || !fmap)
     return;
 
@@ -123,17 +123,15 @@ mapwrite_work(FILE * fmap)
     }
   }
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct mid_entry *alias;
-    OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+    OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator2) {
       if (0 > fprintf(fmap, "Mid('%s','%s');\n",
                       olsr_ip_to_string(&strbuf1, &tc->addr), olsr_ip_to_string(&strbuf2, &alias->mid_alias_addr))) {
         return;
       }
     }
-    OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
   }
-  OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 
   lookup_defhna_latlon(&ip);
   sprintf(my_latlon_str, "%f,%f,%d", my_lat, my_lon, get_isdefhna_latlon());
@@ -159,8 +157,8 @@ mapwrite_work(FILE * fmap)
     }
   }
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator2) {
       char *lla = lookup_position_latlon(&tc->addr);
       char *llb = lookup_position_latlon(&tc_edge->T_dest_addr);
       if (NULL != lla && NULL != llb) {
@@ -189,9 +187,7 @@ mapwrite_work(FILE * fmap)
         }
       }
     }
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
   }
-  OLSR_FOR_ALL_TC_ENTRIES_END();
 }
 
 #ifndef WIN32
index 7bb4d80..56005f9 100644 (file)
@@ -1048,6 +1048,7 @@ write_hosts_file(void)
 #ifdef MID_ENTRIES
   struct mid_entry *alias;
   struct tc_entry *tc;
+  struct list_iterator iterator;
 #endif
 
   if (!name_table_changed)
@@ -1107,7 +1108,7 @@ write_hosts_file(void)
           unsigned short mid_num = 1;
           char mid_prefix[MID_MAXLEN];
 
-          OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+          OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator) {
             struct ipaddr_str midbuf;
 
             // generate mid prefix
@@ -1122,7 +1123,7 @@ write_hosts_file(void)
                     mid_prefix, name->name, my_suffix, olsr_ip_to_string(&strbuf, &entry->originator), mid_num);
 
             mid_num++;
-          } OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
+          }
         }
 #endif
       }
@@ -1603,14 +1604,12 @@ 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))) {
-    rt = rt_tree2rt(rt_tree_node);
+  if (NULL != (rt = avl_find_element(&routingtree, &prefix, rt, rt_tree_node))) {
     *ip = rt->rt_best->rtp_nexthop.gateway;
   }
 }
index 0676cd7..762216d 100644 (file)
@@ -99,12 +99,12 @@ zebra_cleanup(void)
 {
   int i;
   struct rt_entry *tmp;
+  struct list_iterator iterator;
 
   if (zebra.options & OPTION_EXPORT) {
-    OLSR_FOR_ALL_RT_ENTRIES(tmp) {
+    OLSR_FOR_ALL_RT_ENTRIES(tmp, iterator) {
       zebra_del_route(tmp);
     }
-    OLSR_FOR_ALL_RT_ENTRIES_END(tmp);
   }
 
   for (i = 0; i < ZEBRA_ROUTE_MAX; i++)
@@ -118,6 +118,7 @@ static void
 zebra_reconnect(void)
 {
   struct rt_entry *tmp;
+  struct list_iterator iterator;
   int i;
 
   zebra_connect();
@@ -125,10 +126,9 @@ zebra_reconnect(void)
     return;                     // try again next time
 
   if (zebra.options & OPTION_EXPORT) {
-    OLSR_FOR_ALL_RT_ENTRIES(tmp) {
+    OLSR_FOR_ALL_RT_ENTRIES(tmp, iterator) {
       zebra_add_route(tmp);
     }
-    OLSR_FOR_ALL_RT_ENTRIES_END(tmp);
   }
 
   for (i = 0; i < ZEBRA_ROUTE_MAX; i++)
index d7ca43a..b8e9310 100644 (file)
@@ -352,6 +352,7 @@ txtinfo_neigh(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param)
 {
   struct nbr_entry *neigh;
+  struct list_iterator iterator;
   const char *template;
   int indexLength;
 
@@ -366,7 +367,7 @@ txtinfo_neigh(struct comport_connection *con,
   }
 
   /* Neighbors */
-  OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
+  OLSR_FOR_ALL_NBR_ENTRIES(neigh, iterator) {
     olsr_ip_to_string(&buf_neighip, &neigh->nbr_addr);
     strscpy(buf_sym, neigh->is_sym ? OLSR_YES : OLSR_NO, sizeof(buf_sym));
     strscpy(buf_mrp, neigh->is_mpr ? OLSR_YES : OLSR_NO, sizeof(buf_mrp));
@@ -378,7 +379,7 @@ txtinfo_neigh(struct comport_connection *con,
     if (abuf_templatef(&con->out, template, values_neigh, tmpl_indices, indexLength) < 0) {
         return ABUF_ERROR;
     }
-  } OLSR_FOR_ALL_NBR_ENTRIES_END()
+  }
 
   return CONTINUE;
 }
@@ -438,6 +439,7 @@ txtinfo_routes(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param __attribute__ ((unused)))
 {
   struct rt_entry *rt;
+  struct list_iterator iterator;
   const char *template;
   int indexLength;
 
@@ -455,7 +457,7 @@ txtinfo_routes(struct comport_connection *con,
   }
 
   /* Walk the route table */
-  OLSR_FOR_ALL_RT_ENTRIES(rt) {
+  OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
     if (!rt->rt_best) {
       /* ignore entries without paths, they will be erased soon */
       continue;
@@ -472,7 +474,7 @@ txtinfo_routes(struct comport_connection *con,
     if (abuf_templatef(&con->out, template, values_routes, tmpl_indices, indexLength) < 0) {
         return ABUF_ERROR;
     }
-  } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+  }
   return CONTINUE;
 }
 
@@ -484,6 +486,7 @@ txtinfo_topology(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param __attribute__ ((unused)))
 {
   struct tc_entry *tc;
+  struct list_iterator iterator, iterator2;
   const char *template;
   int indexLength;
 
@@ -501,7 +504,7 @@ txtinfo_topology(struct comport_connection *con,
   }
 
   /* Topology */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct tc_edge_entry *tc_edge;
     olsr_ip_to_string(&buf_localip, &tc->addr);
     if (tc->validity_timer) {
@@ -511,7 +514,7 @@ txtinfo_topology(struct comport_connection *con,
       strscpy(buf_vtime.buf, "0.0", sizeof(buf_vtime));
     }
 
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator2) {
       olsr_ip_to_string(&buf_neighip, &tc_edge->T_dest_addr);
       strscpy(buf_virtual, tc_edge->virtual ? OLSR_YES : OLSR_NO, sizeof(buf_virtual));
       if (tc_edge->virtual) {
@@ -527,8 +530,8 @@ txtinfo_topology(struct comport_connection *con,
       if (abuf_templatef(&con->out, template, values_topology, tmpl_indices, indexLength) < 0) {
           return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
-  } OLSR_FOR_ALL_TC_ENTRIES_END()
+    }
+  }
 
   return CONTINUE;
 }
@@ -541,7 +544,7 @@ txtinfo_hna(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param __attribute__ ((unused)))
 {
   const struct ip_prefix_entry *hna;
-  struct list_iterator iterator;
+  struct list_iterator iterator, iterator2;
   struct tc_entry *tc;
   const char *template;
   int indexLength;
@@ -570,7 +573,7 @@ txtinfo_hna(struct comport_connection *con,
   }
 
   /* HNA entries */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct hna_net *tmp_net;
 
     olsr_ip_to_string(&buf_localip, &tc->addr);
@@ -582,14 +585,14 @@ txtinfo_hna(struct comport_connection *con,
     }
 
     /* Check all networks */
-    OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, tmp_net) {
+    OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, tmp_net, iterator2) {
       olsr_ip_prefix_to_string(&buf_destprefix, &tmp_net->hna_prefix);
 
       if (abuf_templatef(&con->out, template, values_hna, tmpl_indices, indexLength) < 0) {
           return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_TC_HNA_ENTRIES_END();
-  } OLSR_FOR_ALL_TC_ENTRIES_END();
+    }
+  }
 
   return CONTINUE;
 }
@@ -603,7 +606,7 @@ txtinfo_mid(struct comport_connection *con,
 {
   struct tc_entry *tc;
   struct interface *interface;
-  struct list_iterator iterator;
+  struct list_iterator iterator, iterator2;
 
   const char *template;
   int indexLength;
@@ -633,7 +636,7 @@ txtinfo_mid(struct comport_connection *con,
   }
 
   /* MID root is the TC entry */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct mid_entry *alias;
 
     olsr_ip_to_string(&buf_localip, &tc->addr);
@@ -645,16 +648,15 @@ txtinfo_mid(struct comport_connection *con,
         strscpy(buf_vtime.buf, "0.0", sizeof(buf_vtime));
       }
 
-      OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+      OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator2) {
         olsr_ip_to_string(&buf_aliasip, &alias->mid_alias_addr);
 
         if (abuf_templatef(&con->out, template, values_mid, tmpl_indices, indexLength) < 0) {
           return ABUF_ERROR;
         }
       }
-      OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
     }
-  } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
+  }
   return CONTINUE;
 }
 
index f43ae9c..446ee30 100644 (file)
@@ -1,7 +1,7 @@
-
 /*
- * The olsr.org Optimized Link-State Routing daemon(olsrd)
- * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
+ * PacketBB handler library (see RFC 5444)
+ * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
+ * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  *
- * Visit http://www.olsr.org for more information.
+ * Visit http://www.olsr.org/git for more information.
  *
  * If you find this software useful feel free to make a donation
  * to the project. For more information see the website or contact
  * the copyright holders.
- *
  */
 
+#include <stdbool.h>
 #include <stddef.h>
+#include <stdint.h>
 #include <time.h>
 #include <string.h>
 
-#include "ipcalc.h"
-#include "common/avl.h"
-#include "net_olsr.h"
-#include "assert.h"
+#include "avl.h"
+#include "list.h"
 
-/*
- * default comparison pointers set to the respective (v4/v6) compare function.
+/**
+ * internal type save inline function to calculate the maximum of
+ * to integers without macro implementation.
+ *
+ * @param x first parameter of maximum function
+ * @param y second parameter of maximum function
+ * @return largest integer of both parameters
+ */
+static inline int avl_max(int x, int y) {
+  return x > y ? x : y;
+}
+
+/**
+ * internal type save inline function to calculate the minimum of
+ * to integers without macro implementation.
+ *
+ * @param x first parameter of minimum function
+ * @param y second parameter of minimum function
+ * @return smallest integer of both parameters
+ */
+static inline int avl_min(int x, int y) {
+  return x < y ? x : y;
+}
+
+static struct avl_node *
+avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
+static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
+static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
+static void post_insert(struct avl_tree *tree, struct avl_node *node);
+static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
+static void avl_remove(struct avl_tree *tree, struct avl_node *node);
+
+/**
+ * Initialize a new avl_tree struct
+ * @param tree pointer to avl-tree
+ * @param comp pointer to comparator for the tree
+ * @param allow_dups true if the tree allows multiple
+ *   elements with the same
+ * @param ptr custom parameter for comparator
  */
 void
-avl_init(struct avl_tree *tree, avl_tree_comp comp)
+avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
 {
+  list_init_head(&tree->list_head);
   tree->root = NULL;
-  tree->first = NULL;
-  tree->last = NULL;
   tree->count = 0;
-
-  assert(comp);
   tree->comp = comp;
+  tree->allow_dups = allow_dups;
+  tree->cmp_ptr = ptr;
+}
+
+/**
+ * Internal function to support returning the element from a avl tree query
+ * @param tree pointer to avl tree
+ * @param key pointer to key
+ * @param offset offset of node inside the embedded struct
+ * @param mode mode of lookup operation (less equal, equal or greater equal)
+ * @param pointer to elemen, NULL if no fitting one was found
+ */
+void *
+__avl_find_element(struct avl_tree *tree, const void *key, size_t offset, enum avl_find_mode mode) {
+  void *node = NULL;
+
+  switch (mode) {
+    case AVL_FIND_EQUAL:
+      node = avl_find(tree, key);
+      break;
+    case AVL_FIND_LESSEQUAL:
+      node = avl_find_lessequal(tree, key);
+      break;
+    case AVL_FIND_GREATEREQUAL:
+      node = avl_find_greaterequal(tree, key);
+      break;
+  }
+  return node == NULL ? NULL : (((char *)node) - offset);
 }
 
+/**
+ * Finds a node in an avl-tree with a certain key
+ * @param tree pointer to avl-tree
+ * @param key pointer to key
+ * @return pointer to avl-node with key, NULL if no node with
+ *    this key exists.
+ */
 struct avl_node *
 avl_find(struct avl_tree *tree, const void *key)
 {
@@ -72,30 +140,260 @@ avl_find(struct avl_tree *tree, const void *key)
   if (tree->root == NULL)
     return NULL;
 
+  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
 
-  /*
-   * Crawl through the tree.
-   */
-  for (node = tree->root;;) {
-    diff = (*tree->comp) (key, node->key);
+  return diff == 0 ? node : NULL;
+}
 
-    if (diff < 0) {
-      if (node->left != NULL) {
-        node = node->left;
-        continue;
-      }
+/**
+ * Finds the last node in an avl-tree with a key less or equal
+ * than the specified key
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @return pointer to avl-node, NULL if no node with
+ *    key less or equal specified key exists.
+ */
+struct avl_node *
+avl_find_lessequal(struct avl_tree *tree, const void *key) {
+  struct avl_node *node, *next;
+  int diff;
+
+  if (tree->root == NULL)
+    return NULL;
+
+  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
+
+  /* go left as long as key<node.key */
+  while (diff < 0) {
+    if (list_is_first(&tree->list_head, &node->list)) {
+      return NULL;
+    }
+
+    node = (struct avl_node *)node->list.prev;
+    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
+  }
+
+  /* go right as long as key>=next_node.key */
+  next = node;
+  while (diff >= 0) {
+    node = next;
+    if (list_is_last(&tree->list_head, &node->list)) {
+      break;
+    }
+
+    next = (struct avl_node *)node->list.next;
+    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
+  }
+  return node;
+}
+
+/**
+ * Finds the first node in an avl-tree with a key greater or equal
+ * than the specified key
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @return pointer to avl-node, NULL if no node with
+ *    key greater or equal specified key exists.
+ */
+struct avl_node *
+avl_find_greaterequal(struct avl_tree *tree, const void *key) {
+  struct avl_node *node, *next;
+  int diff;
+
+  if (tree->root == NULL)
+    return NULL;
+
+  node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
+
+  /* go right as long as key>node.key */
+  while (diff > 0) {
+    if (list_is_last(&tree->list_head, &node->list)) {
+      return NULL;
+    }
+
+    node = (struct avl_node *)node->list.next;
+    diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
+  }
+
+  /* go left as long as key<=next_node.key */
+  next = node;
+  while (diff <= 0) {
+    node = next;
+    if (list_is_first(&tree->list_head, &node->list)) {
+      break;
+    }
+
+    next = (struct avl_node *)node->list.prev;
+    diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
+  }
+  return node;
+}
+
+/**
+ * Inserts an avl_node into a tree
+ * @param tree pointer to tree
+ * @param new pointer to node
+ * @return 0 if node was inserted successfully, -1 if it was not inserted
+ *   because of a key collision
+ */
+int
+avl_insert(struct avl_tree *tree, struct avl_node *new)
+{
+  struct avl_node *node, *next, *last;
+  int diff;
+
+  new->parent = NULL;
+
+  new->left = NULL;
+  new->right = NULL;
+
+  new->balance = 0;
+  new->leader = true;
+
+  if (tree->root == NULL) {
+    list_add_head(&tree->list_head, &new->list);
+    tree->root = new;
+    tree->count = 1;
+    return 0;
+  }
+
+  node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
+
+  last = node;
+
+  while (!list_is_last(&tree->list_head, &last->list)) {
+    next = list_next_element(last, list);
+    if (next->leader) {
+      break;
     }
+    last = next;
+  }
+
+  diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
+
+  if (diff == 0) {
+    if (!tree->allow_dups)
+      return -1;
+
+    new->leader = 0;
+
+    avl_insert_after(tree, last, new);
+    return 0;
+  }
+
+  if (node->balance == 1) {
+    avl_insert_before(tree, node, new);
+
+    node->balance = 0;
+    new->parent = node;
+    node->left = new;
+    return 0;
+  }
+
+  if (node->balance == -1) {
+    avl_insert_after(tree, last, new);
+
+    node->balance = 0;
+    new->parent = node;
+    node->right = new;
+    return 0;
+  }
+
+  if (diff < 0) {
+    avl_insert_before(tree, node, new);
+
+    node->balance = -1;
+    new->parent = node;
+    node->left = new;
+    post_insert(tree, node);
+    return 0;
+  }
 
-    if (diff > 0) {
-      if (node->right != NULL) {
-        node = node->right;
-        continue;
+  avl_insert_after(tree, last, new);
+
+  node->balance = 1;
+  new->parent = node;
+  node->right = new;
+  post_insert(tree, node);
+  return 0;
+}
+
+/**
+ * Remove a node from an avl tree
+ * @param tree pointer to tree
+ * @param node pointer to node
+ */
+void
+avl_delete(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *next;
+  struct avl_node *parent;
+  struct avl_node *left;
+  struct avl_node *right;
+  if (node->leader) {
+    if (tree->allow_dups
+        && !list_is_last(&tree->list_head, &node->list)
+        && !(next = list_next_element(node, list))->leader) {
+      next->leader = true;
+      next->balance = node->balance;
+
+      parent = node->parent;
+      left = node->left;
+      right = node->right;
+
+      next->parent = parent;
+      next->left = left;
+      next->right = right;
+
+      if (parent == NULL)
+        tree->root = next;
+
+      else {
+        if (node == parent->left)
+          parent->left = next;
+
+        else
+          parent->right = next;
       }
+
+      if (left != NULL)
+        left->parent = next;
+
+      if (right != NULL)
+        right->parent = next;
     }
-    break;
+
+    else
+      avl_delete_worker(tree, node);
   }
 
-  return (diff == 0) ? node : NULL;
+  avl_remove(tree, node);
+  node->key = NULL;
+}
+
+static struct avl_node *
+avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
+{
+  int diff;
+
+  diff = (*comp) (key, node->key, cmp_ptr);
+  *cmp_result = diff;
+
+  if (diff < 0) {
+    if (node->left != NULL)
+      return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
+
+    return node;
+  }
+
+  if (diff > 0) {
+    if (node->right != NULL)
+      return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
+
+    return node;
+  }
+
+  return node;
 }
 
 static void
@@ -126,8 +424,8 @@ avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
   if (node->left != NULL)
     node->left->parent = node;
 
-  node->balance += 1 - MIN(left->balance, 0);
-  left->balance += 1 + MAX(node->balance, 0);
+  node->balance += 1 - avl_min(left->balance, 0);
+  left->balance += 1 + avl_max(node->balance, 0);
 }
 
 static void
@@ -158,8 +456,8 @@ avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
   if (node->right != NULL)
     node->right->parent = node;
 
-  node->balance -= 1 + MAX(right->balance, 0);
-  right->balance -= 1 - MIN(node->balance, 0);
+  node->balance -= 1 + avl_max(right->balance, 0);
+  right->balance -= 1 - avl_min(node->balance, 0);
 }
 
 static void
@@ -213,151 +511,24 @@ post_insert(struct avl_tree *tree, struct avl_node *node)
 static void
 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
 {
-  if (pos_node->prev != NULL)
-    pos_node->prev->next = node;
-  else
-    tree->first = node;
-
-  node->prev = pos_node->prev;
-  node->next = pos_node;
-
-  pos_node->prev = node;
-
+  list_add_before(&pos_node->list, &node->list);
   tree->count++;
 }
 
 static void
 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
 {
-  if (pos_node->next != NULL)
-    pos_node->next->prev = node;
-  else
-    tree->last = node;
-
-  node->prev = pos_node;
-  node->next = pos_node->next;
-
-  pos_node->next = node;
-
+  list_add_after(&pos_node->list, &node->list);
   tree->count++;
 }
 
 static void
 avl_remove(struct avl_tree *tree, struct avl_node *node)
 {
-  if (node->prev != NULL)
-    node->prev->next = node->next;
-  else
-    tree->first = node->next;
-
-  if (node->next != NULL)
-    node->next->prev = node->prev;
-  else
-    tree->last = node->prev;
-
+  list_remove(&node->list);
   tree->count--;
 }
 
-int
-avl_insert(struct avl_tree *tree, struct avl_node *new, bool allow_duplicates)
-{
-  struct avl_node *node;
-  struct avl_node *last;
-  int diff;
-
-  new->parent = NULL;
-
-  new->left = NULL;
-  new->right = NULL;
-
-  new->next = NULL;
-  new->prev = NULL;
-
-  new->balance = 0;
-  new->leader = 1;
-
-  if (tree->root == NULL) {
-    tree->root = new;
-    tree->first = new;
-    tree->last = new;
-    tree->count = 1;
-    return 0;
-  }
-
-  /*
-   * First locate insertion point.
-   */
-  for (node = tree->root;;) {
-    diff = (*tree->comp) (new->key, node->key);
-
-    if (diff < 0) {
-      if (node->left != NULL) {
-        node = node->left;
-        continue;
-      }
-    }
-
-    if (diff > 0) {
-      if (node->right != NULL) {
-        node = node->right;
-        continue;
-      }
-    }
-    break;
-  }
-
-  last = node;
-
-  while (last->next != NULL && last->next->leader == 0)
-    last = last->next;
-
-  if (diff == 0) {
-    if (!allow_duplicates)
-      return -1;
-
-    new->leader = 0;
-
-    avl_insert_after(tree, last, new);
-    return 0;
-  }
-
-  if (node->balance == 1) {
-    avl_insert_before(tree, node, new);
-
-    node->balance = 0;
-    new->parent = node;
-    node->left = new;
-    return 0;
-  }
-
-  if (node->balance == -1) {
-    avl_insert_after(tree, last, new);
-
-    node->balance = 0;
-    new->parent = node;
-    node->right = new;
-    return 0;
-  }
-
-  if (diff < 0) {
-    avl_insert_before(tree, node, new);
-
-    node->balance = -1;
-    new->parent = node;
-    node->left = new;
-    post_insert(tree, node);
-    return 0;
-  }
-
-  avl_insert_after(tree, last, new);
-
-  node->balance = 1;
-  new->parent = node;
-  node->right = new;
-  post_insert(tree, node);
-  return 0;
-}
-
 static void
 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
 {
@@ -578,59 +749,6 @@ avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
   parent->right = min;
 }
 
-#include "valgrind/valgrind.h"
-
-void
-avl_delete(struct avl_tree *tree, struct avl_node *node)
-{
-  struct avl_node *next;
-  struct avl_node *parent;
-  struct avl_node *left;
-  struct avl_node *right;
-
-  /* sanity check */
-  assert(tree->count > 0);
-
-  if (node->leader != 0) {
-    next = node->next;
-
-    if (next != NULL && next->leader == 0) {
-      next->leader = 1;
-      next->balance = node->balance;
-
-      parent = node->parent;
-      left = node->left;
-      right = node->right;
-
-      next->parent = parent;
-      next->left = left;
-      next->right = right;
-
-      if (parent == NULL)
-        tree->root = next;
-
-      else {
-        if (node == parent->left)
-          parent->left = next;
-
-        else
-          parent->right = next;
-      }
-
-      if (left != NULL)
-        left->parent = next;
-
-      if (right != NULL)
-        right->parent = next;
-    }
-
-    else
-      avl_delete_worker(tree, node);
-  }
-
-  avl_remove(tree, node);
-}
-
 /*
  * Local Variables:
  * c-basic-offset: 2
index d1772d1..38168b6 100644 (file)
@@ -1,7 +1,7 @@
-
 /*
- * The olsr.org Optimized Link-State Routing daemon(olsrd)
- * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
+ * PacketBB handler library (see RFC 5444)
+ * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
+ * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  *
- * Visit http://www.olsr.org for more information.
+ * Visit http://www.olsr.org/git for more information.
  *
  * If you find this software useful feel free to make a donation
  * to the project. For more information see the website or contact
  * the copyright holders.
- *
  */
 
 #ifndef _AVL_H
 #define _AVL_H
 
-#include "../defs.h"
 #include <stddef.h>
+#include <stdbool.h>
+
+#include "list.h"
+#include "container_of.h"
 
+/* Support for OLSR.org linker symbol export */
+#define EXPORT(sym) sym
+
+/**
+ * This element is a member of a avl-tree. It must be contained in all
+ * larger structs that should be put into a tree.
+ */
 struct avl_node {
+  /**
+   * Linked list node for supporting easy iteration and multiple
+   * elments with the same key.
+   *
+   * this must be the first element of an avl_node to
+   * make casting for lists easier
+   */
+  struct list_entity list;
+
+  /**
+   * Pointer to parent node in tree, NULL if root node
+   */
   struct avl_node *parent;
+
+  /**
+   * Pointer to left child
+   */
   struct avl_node *left;
+
+  /**
+   * Pointer to right child
+   */
   struct avl_node *right;
-  struct avl_node *next;
-  struct avl_node *prev;
+
+  /**
+   * pointer to key of node
+   */
   void *key;
+
+  /**
+   * balance state of AVL tree (0,-1,+1)
+   */
   signed char balance;
-  unsigned char leader;
+
+  /**
+   * true if first of a series of nodes with same key
+   */
+  bool leader;
 };
 
-typedef int (*avl_tree_comp) (const void *, const void *);
+/**
+ * Prototype for avl comparators
+ * @param k1 first key
+ * @param k2 second key
+ * @param ptr custom data for tree comparator
+ * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
+ */
+typedef int (*avl_tree_comp) (const void *k1, const void *k2, void *ptr);
 
+/**
+ * This struct is the central management part of an avl tree.
+ * One of them is necessary for each avl_tree.
+ */
 struct avl_tree {
+  /**
+   * Head of linked list node for supporting easy iteration
+   * and multiple elments with the same key.
+   */
+  struct list_entity list_head;
+
+  /**
+   * pointer to the root node of the avl tree, NULL if tree is empty
+   */
   struct avl_node *root;
-  struct avl_node *first;
-  struct avl_node *last;
+
+  /**
+   * number of nodes in the avl tree
+   */
   unsigned int count;
+
+  /**
+   * true if multiple nodes with the same key are
+   * allowed in the tree, false otherwise
+   */
+  bool allow_dups;
+
+  /**
+   * pointer to the tree comparator
+   *
+   * First two parameters are keys to compare,
+   * third parameter is a copy of cmp_ptr
+   */
   avl_tree_comp comp;
+
+  /**
+   * custom pointer delivered to the tree comparator
+   */
+  void *cmp_ptr;
+};
+
+/**
+ * internal enum for avl_find_... macros
+ */
+enum avl_find_mode {
+  AVL_FIND_EQUAL,
+  AVL_FIND_LESSEQUAL,
+  AVL_FIND_GREATEREQUAL
 };
 
-void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp);
-struct avl_node *EXPORT(avl_find) (struct avl_tree *, const void *);
-int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *, bool);
+void EXPORT(avl_init)(struct avl_tree *, avl_tree_comp, bool, void *);
+struct avl_node *EXPORT(avl_find)(struct avl_tree *, const void *);
+struct avl_node *EXPORT(avl_find_greaterequal)(struct avl_tree *tree, const void *key);
+struct avl_node *EXPORT(avl_find_lessequal)(struct avl_tree *tree, const void *key);
+int EXPORT(avl_insert)(struct avl_tree *, struct avl_node *);
 void EXPORT(avl_delete)(struct avl_tree *, struct avl_node *);
+void *EXPORT(__avl_find_element)(struct avl_tree *tree, const void *key,
+    size_t offset, enum avl_find_mode mode);
 
-static INLINE struct avl_node *
-avl_walk_first(struct avl_tree *tree)
-{
-  return tree->first;
-}
-static INLINE struct avl_node *
-avl_walk_last(struct avl_tree *tree)
-{
-  return tree->last;
-}
-static INLINE struct avl_node *
-avl_walk_next(struct avl_node *node)
-{
-  return node->next;
-}
-static INLINE struct avl_node *
-avl_walk_prev(struct avl_node *node)
-{
-  return node->prev;
+/**
+ * @param tree pointer to avl-tree
+ * @param node pointer to node of the tree
+ * @return true if node is the first one of the tree, false otherwise
+ */
+static inline bool
+avl_is_first(struct avl_tree *tree, struct avl_node *node) {
+  return tree->list_head.next == &node->list;
 }
 
-/* and const versions*/
-static INLINE const struct avl_node *
-avl_walk_first_c(const struct avl_tree *tree)
-{
-  return tree->first;
-}
-static INLINE const struct avl_node *
-avl_walk_last_c(const struct avl_tree *tree)
-{
-  return tree->last;
-}
-static INLINE const struct avl_node *
-avl_walk_next_c(const struct avl_node *node)
-{
-  return node->next;
-}
-static INLINE const struct avl_node *
-avl_walk_prev_c(const struct avl_node *node)
-{
-  return node->prev;
+/**
+ * @param tree pointer to avl-tree
+ * @param node pointer to node of the tree
+ * @return true if node is the last one of the tree, false otherwise
+ */
+static inline bool
+avl_is_last(struct avl_tree *tree, struct avl_node *node) {
+  return tree->list_head.prev == &node->list;
 }
 
-/*
- * Macro to define an inline function to map from a listold_node offset back to the
- * base of the datastructure. That way you save an extra data pointer.
- */
-#define AVLNODE2STRUCT(funcname, structname, avlnodename) \
-static INLINE struct structname * funcname (struct avl_node *ptr)\
-{\
-  if (!ptr) return NULL; \
-  return ((struct structname *) ((char *)ptr - offsetof(struct structname,avlnodename))); \
+/**
+ * @param tree pointer to avl-tree
+ * @return true if the tree is empty, false otherwise
+ */
+static inline bool
+avl_is_empty(struct avl_tree *tree) {
+  return tree->count == 0;
 }
 
-#define OLSR_FOR_ALL_AVL_ENTRIES(avltreeptr, convfunc, variable) \
-{ \
-  struct avl_node *convfunc##node, *convfunc##next_node; \
-  for (convfunc##node = avl_walk_first(avltreeptr); convfunc##node; convfunc##node = convfunc##next_node) { \
-    convfunc##next_node = avl_walk_next(convfunc##node); \
-    variable = convfunc (convfunc##node);
-#define OLSR_FOR_ALL_AVL_ENTRIES_END() }}
+/**
+ * @param tree pointer to avl-tree
+ * @param key pointer to key
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_element name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to tree element with the specified key,
+ *    NULL if no element was found
+ */
+#define avl_find_element(tree, key, element, node_element) \
+  ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_EQUAL))
+
+/**
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_element name of the avl_node element inside the
+ *    larger struct
+ * return pointer to last tree element with less or equal key than specified key,
+ *    NULL if no element was found
+ */
+#define avl_find_le_element(tree, key, element, node_element) \
+  ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_LESSEQUAL))
+
+/**
+ * @param tree pointer to avl-tree
+ * @param key pointer to specified key
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_element name of the avl_node element inside the
+ *    larger struct
+ * return pointer to first tree element with greater or equal key than specified key,
+ *    NULL if no element was found
+ */
+#define avl_find_ge_element(tree, key, element, node_element) \
+  ((typeof(*(element)) *)__avl_find_element(tree, key, offsetof(typeof(*(element)), node_element), AVL_FIND_GREATEREQUAL))
+
+/**
+ * This function must not be called for an empty tree
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node element
+ *    (don't need to be initialized)
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the first element of the avl_tree
+ *    (automatically converted to type 'element')
+ */
+#define avl_first_element(tree, element, node_member) \
+  container_of((tree)->list_head.next, typeof(*(element)), node_member)
+
+/**
+ * @param tree pointer to tree
+ * @param element pointer to a node struct that contains the avl_node
+ *    (don't need to be initialized)
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the last element of the avl_tree
+ *    (automatically converted to type 'element')
+ */
+#define avl_last_element(tree, element, node_member) \
+  container_of((tree)->list_head.prev, typeof(*(element)), node_member)
+
+/**
+ * This function must not be called for the last element of
+ * an avl tree
+ *
+ * @param element pointer to a node of the tree
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the node after 'element'
+ *    (automatically converted to type 'element')
+ */
+#define avl_next_element(element, node_member) \
+  container_of((&(element)->node_member.list)->next, typeof(*(element)), node_member)
+
+/**
+ * This function must not be called for the first element of
+ * an avl tree
+ *
+ * @param element pointer to a node of the tree
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @return pointer to the node before 'element'
+ *    (automatically converted to type 'element')
+ */
+#define avl_prev_element(element, node_member) \
+  container_of((&(element)->node_member.list)->prev, typeof(*(element)), node_member)
+
+/**
+ * Loop over all elements of an avl_tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as
+ *    the internal iterator
+ */
+#define avl_for_each_element(tree, element, node_member, loop_ptr) \
+  list_for_each_element(&(tree)->list_head, element, node_member, loop_ptr)
+
+/**
+ * Loop over all elements of an avl_tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as
+ *    the internal iterator
+ */
+#define avl_for_each_element_reverse(tree, element, node_member, loop_ptr) \
+  list_for_each_element_reverse(&(tree)->list_head, element, node_member, loop_ptr)
+
+/**
+ * Loop over a block of elements of a tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param first pointer to first element of loop
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator
+ */
+#define avl_for_element_range(first, last, element, node_member, loop_ptr) \
+  __list_for_element_range(&(first)->node_member.list, &(last)->node_member.list, element, node_member, loop_ptr)
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ *
+ * @param first pointer to first element of loop
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator
+ */
+#define avl_for_element_range_reverse(first, last, element, node_member, loop_ptr) \
+  __list_for_element_range_reverse(&(first)->node_member.list, &(last)->node_member.list, element, node_member, loop_ptr)
+
+/**
+ * Loop over a block of elements of a tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the element 'first' to the end of the tree.
+ *
+ * @param tree pointer to avl-tree
+ * @param first pointer to first element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator
+ */
+#define avl_for_element_to_last(tree, first, element, node_member, loop_ptr) \
+  __list_for_element_range(&(first)->node_member.list, (tree)->list_head.prev, element, node_member, loop_ptr)
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the element 'first' to the end of the tree.
+ *
+ * @param tree pointer to avl-tree
+ * @param first pointer to first element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator
+ */
+#define avl_for_element_to_last_reverse(tree, first, element, node_member, loop_ptr) \
+  __list_for_element_range_reverse(&(first)->node_member.list, (tree)->list_head.prev, element, node_member, loop_ptr)
+
+/**
+ * Loop over a block of elements of a tree, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the start of the tree to the element 'last'.
+ *
+ * @param tree pointer to avl-tree
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator
+ */
+#define avl_for_first_to_element(tree, last, element, node_member, loop_ptr) \
+    __list_for_element_range((tree)->list_head.next, &(last)->node_member.list, element, node_member, loop_ptr)
+
+/**
+ * Loop over a block of elements of a tree backwards, used similar to a for() command.
+ * This loop should not be used if elements are removed from the tree during
+ * the loop.
+ * The loop runs from the start of the tree to the element 'last'.
+ *
+ * @param tree pointer to avl-tree
+ * @param last pointer to last element of loop
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the list during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator
+ */
+#define avl_for_first_to_element_reverse(tree, last, element, node_member, loop_ptr) \
+    __list_for_element_range_reverse((tree)->list_head.next, &(last)->node_member.list, element, node_member, loop_ptr)
+
+/**
+ * Loop over all elements of an avl_tree, used similar to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator for the loop
+ * @param safe_ptr pointer to an list_entity which is used to store
+ *    the next node during the loop
+ */
+#define avl_for_each_element_safe(tree, element, node_member, loop_ptr, safe_ptr) \
+  list_for_each_element_safe(&(tree)->list_head, element, node_member, loop_ptr, safe_ptr)
+
+/**
+ * Loop over all elements of an avl_tree backwards, used similar to a for() command.
+ * This loop can be used if the current element might be removed from
+ * the tree during the loop. Other elements should not be removed during
+ * the loop.
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator for the loop
+ * @param safe_ptr pointer to an list_entity which is used to store
+ *    the next node during the loop
+ */
+#define avl_for_each_element_reverse_safe(tree, element, node_member, loop_ptr, safe_ptr) \
+  list_for_each_element_reverse_safe(&(tree)->list_head, element, node_member, loop_ptr, safe_ptr)
+
+/**
+ * A special loop that removes all elements of the tree and cleans up the tree
+ * root. The loop body is responsible to free the node elements of the tree.
+ *
+ * This loop is much faster than a normal one for clearing the tree because it
+ * does not rebalance the tree after each removal. Do NOT use a break command
+ * inside.
+ * You can free the memory of the elements within the loop.
+ * Do NOT call avl_delete() on the elements within the loop,
+ *
+ * @param tree pointer to avl-tree
+ * @param element pointer to a node of the tree, this element will
+ *    contain the current node of the tree during the loop
+ * @param node_member name of the avl_node element inside the
+ *    larger struct
+ * @param loop_ptr pointer to an list_entity which is used as the
+ *    internal iterator for the loop
+ * @param safe_ptr pointer to an list_entity which is used to store
+ *    the next node during the loop
+ */
+#define avl_remove_all_elements(tree, element, node_member, loop_ptr, safe_ptr) \
+  for (loop_ptr = (tree)->list_head.next, safe_ptr = loop_ptr->next, \
+         element = container_of(loop_ptr, typeof(*(element)), node_member), \
+         list_init_head(&(tree)->list_head), \
+         (tree)->root = NULL, (tree)->count = 0; \
+       loop_ptr != &(tree)->list_head; \
+       loop_ptr = safe_ptr, safe_ptr = loop_ptr->next, \
+         element = container_of(loop_ptr, typeof(*(element)), node_member))
 
 #endif /* _AVL_H */
 
diff --git a/src/common/avl_comp.c b/src/common/avl_comp.c
new file mode 100644 (file)
index 0000000..27de12c
--- /dev/null
@@ -0,0 +1,122 @@
+/*
+ * PacketBB handler library (see RFC 5444)
+ * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org/git for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include "common/avl_comp.h"
+
+/**
+ * AVL tree comparator for unsigned 32 bit integers
+ * Custom pointer is not used.
+ * @param k1 pointer to key 1
+ * @param k2 pointer to key 2
+ * @param ptr custom pointer for avl comparater (unused)
+ * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
+ */
+int
+avl_comp_uint32(const void *k1, const void *k2, void *ptr __attribute__ ((unused)))
+{
+  const uint32_t *key1 = (const uint32_t *)k1;
+  const uint32_t *key2 = (const uint32_t *)k2;
+  if (*key1 > *key2) {
+    return 1;
+  }
+  if (*key1 < *key2) {
+    return -1;
+  }
+  return 0;
+}
+
+/**
+ * AVL tree comparator for unsigned 16 bit integers
+ * Custom pointer is not used.
+ * @param k1 pointer to key 1
+ * @param k2 pointer to key 2
+ * @param ptr custom pointer for avl comparater (unused)
+ * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
+ */
+int
+avl_comp_uint16(const void *k1, const void *k2, void *ptr __attribute__ ((unused)))
+{
+  const uint16_t *key1 = (const uint16_t *)k1;
+  const uint16_t *key2 = (const uint16_t *)k2;
+  if (*key1 > *key2) {
+    return 1;
+  }
+  if (*key1 < *key2) {
+    return -1;
+  }
+  return 0;
+}
+
+/**
+ * AVL tree comparator for unsigned 8 bit integers
+ * Custom pointer is not used
+ * @param p1 pointer to key 1
+ * @param p2 pointer to key 2
+ * @param ptr custom pointer for avl comparater (unused)
+ * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
+ */
+int
+avl_comp_uint8(const void *p1, const void *p2, void *ptr __attribute__ ((unused)))
+{
+  const uint8_t *i1 = p1;
+  const uint8_t *i2 = p2;
+  if (*i1 > *i2)
+    return 1;
+  if (*i1 < *i2)
+    return -1;
+  return 0;
+}
+
+/**
+ * AVL tree comparator for arbitrary memory blocks.
+ * Custom pointer is the length of the memory to compare.
+ * @param k1 pointer to key 1
+ * @param k2 pointer to key 2
+ * @param ptr length of memory blocks to compare (size_t)
+ * @return +1 if k1>k2, -1 if k1<k2, 0 if k1==k2
+ */
+int
+avl_comp_mem(const void *k1, const void *k2, void *ptr) {
+  const size_t length = (const size_t)ptr;
+  return memcmp(k1, k2, length);
+}
+
diff --git a/src/common/avl_comp.h b/src/common/avl_comp.h
new file mode 100644 (file)
index 0000000..3230dc6
--- /dev/null
@@ -0,0 +1,54 @@
+/*
+ * PacketBB handler library (see RFC 5444)
+ * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
+ * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org/git for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ */
+
+#ifndef AVL_COMP_H_
+#define AVL_COMP_H_
+
+#include "common/avl.h"
+
+/* Support for OLSR.org linker symbol export */
+#define EXPORT(sym) sym
+
+int EXPORT(avl_comp_uint32)(const void *k1, const void *k2, void *ptr);
+int EXPORT(avl_comp_uint16)(const void *k1, const void *k2, void *ptr);
+int EXPORT(avl_comp_uint8)(const void *k1, const void *k2, void *ptr);
+int EXPORT(avl_comp_mem)(const void *k1, const void *k2, void *ptr);
+
+#endif /* AVL_COMP_H_ */
index e6ea074..aa8d0d9 100644 (file)
@@ -14,33 +14,33 @@ avl_tree_comp avl_comp_prefix_default = NULL;
 avl_tree_comp avl_comp_prefix_origin_default = NULL;
 
 int
-avl_comp_ipv4(const void *ip1, const void *ip2)
+avl_comp_ipv4(const void *ip1, const void *ip2, void *ptr __attribute__ ((unused)))
 {
   return ip4cmp(ip1, ip2);
 }
 
 int
-avl_comp_ipv6(const void *ip1, const void *ip2)
+avl_comp_ipv6(const void *ip1, const void *ip2, void *ptr __attribute__ ((unused)))
 {
   return ip6cmp(ip1, ip2);
 }
 
 int
-avl_comp_mac(const void *ip1, const void *ip2)
+avl_comp_mac(const void *ip1, const void *ip2, void *ptr __attribute__ ((unused)))
 {
   return memcmp(ip1, ip2, 6);
 }
 
-int avl_comp_strcasecmp(const void *txt1, const void *txt2) {
+int avl_comp_strcasecmp(const void *txt1, const void *txt2, void *ptr __attribute__ ((unused))) {
   return strcasecmp(txt1, txt2);
 }
 
-int avl_comp_int(const void *p1, const void *p2) {
+int avl_comp_int(const void *p1, const void *p2, void *ptr __attribute__ ((unused))) {
   const int *i1 = p1, *i2 = p2;
   return *i1 - *i2;
 }
 
-int avl_comp_interface_id(const void *p1, const void *p2) {
+int avl_comp_interface_id(const void *p1, const void *p2, void *ptr __attribute__ ((unused))) {
   const struct olsr_interface_id *id1 = p1, *id2 = p2;
   int diff;
 
index a4d6c8b..3a27e61 100644 (file)
@@ -14,11 +14,12 @@ extern avl_tree_comp avl_comp_default;
 extern avl_tree_comp avl_comp_addr_origin_default;
 extern avl_tree_comp avl_comp_prefix_default;
 extern avl_tree_comp avl_comp_prefix_origin_default;
-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 *);
-extern int avl_comp_strcasecmp(const void *, const void *);
-extern int avl_comp_int(const void *, const void *);
-extern int avl_comp_interface_id(const void *, const void *);
+
+extern int avl_comp_ipv4(const void *, const void *, void *);
+extern int avl_comp_ipv6(const void *, const void *, void *);
+extern int avl_comp_mac(const void *, const void *, void *);
+extern int avl_comp_strcasecmp(const void *, const void *, void *);
+extern int avl_comp_int(const void *, const void *, void *);
+extern int avl_comp_interface_id(const void *, const void *, void *);
 
 #endif /* AVL_OLSR_COMP_H_ */
index 9a72009..982a737 100644 (file)
@@ -78,8 +78,8 @@ olsr_init_duplicate_set(void)
 {
   OLSR_INFO(LOG_DUPLICATE_SET, "Initialize duplicate set...\n");
 
-  avl_init(&forward_set, avl_comp_default);
-  avl_init(&processing_set, avl_comp_default);
+  avl_init(&forward_set, avl_comp_default, false, NULL);
+  avl_init(&processing_set, avl_comp_default, false, NULL);
 
   /*
    * Get some cookies for getting stats to ease troubleshooting.
@@ -132,13 +132,14 @@ void
 olsr_flush_duplicate_entries(void)
 {
   struct dup_entry *entry;
+  struct list_iterator iterator;
 
-  OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(entry) {
+  OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(entry, iterator) {
     olsr_delete_duplicate_entry(entry);
-  } OLSR_FOR_ALL_FORWARD_DUP_ENTRIES_END()
-    OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(entry) {
+  }
+  OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(entry, iterator) {
     olsr_delete_duplicate_entry(entry);
-  } OLSR_FOR_ALL_PROCESS_DUP_ENTRIES_END()
+  }
 }
 
 bool
@@ -167,7 +168,7 @@ olsr_is_duplicate_message(struct olsr_message *m, bool forwarding, enum duplicat
   if (entry == NULL) {
     entry = olsr_create_duplicate_entry(&m->originator, m->seqno);
     if (entry != NULL) {
-      avl_insert(tree, &entry->avl, 0);
+      avl_insert(tree, &entry->avl);
       entry->tree = tree;
       entry->validity_timer = olsr_start_timer(DUPLICATE_CLEANUP_INTERVAL, DUPLICATE_CLEANUP_JITTER,
                                                OLSR_TIMER_ONESHOT, &olsr_expire_duplicate_entry, entry, duplicate_timer_cookie);
@@ -242,29 +243,30 @@ olsr_print_duplicate_table(void)
 #if !defined REMOVE_LOG_INFO
   /* The whole function makes no sense without it. */
   struct dup_entry *entry;
+  struct list_iterator iterator;
   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
 
   OLSR_INFO(LOG_DUPLICATE_SET, "\n--- %s ------------------------------------------------- DUPLICATE SET (forwarding)\n\n",
             olsr_wallclock_string());
   OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %8s %s\n", ipwidth, "Node IP", "DupArray", "VTime");
 
-  OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(entry) {
+  OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(entry, iterator) {
     struct ipaddr_str addrbuf;
     OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %08x %s\n",
                  ipwidth, olsr_ip_to_string(&addrbuf, entry->avl.key), entry->array,
                  olsr_clock_string(entry->validity_timer->timer_clock));
-  } OLSR_FOR_ALL_FORWARD_DUP_ENTRIES_END()
+  }
 
     OLSR_INFO(LOG_DUPLICATE_SET, "\n--- %s ------------------------------------------------- DUPLICATE SET (processing)\n\n",
               olsr_wallclock_string());
   OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %8s %s\n", ipwidth, "Node IP", "DupArray", "VTime");
 
-  OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(entry) {
+  OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(entry, iterator) {
     struct ipaddr_str addrbuf;
     OLSR_INFO_NH(LOG_DUPLICATE_SET, "%-*s %08x %s\n",
                  ipwidth, olsr_ip_to_string(&addrbuf, entry->avl.key), entry->array,
                  olsr_clock_string(entry->validity_timer->timer_clock));
-  } OLSR_FOR_ALL_PROCESS_DUP_ENTRIES_END()
+  }
 #endif
 }
 
index 97b6949..231953f 100644 (file)
@@ -76,13 +76,8 @@ bool olsr_is_duplicate_message(struct olsr_message *m, bool forward_set, enum du
 void olsr_print_duplicate_table(void);
 void olsr_flush_duplicate_entries(void);
 
-AVLNODE2STRUCT(duptree2dupentry, dup_entry, avl);
-
-#define OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(dup) OLSR_FOR_ALL_AVL_ENTRIES(&forward_set, duptree2dupentry, dup)
-#define OLSR_FOR_ALL_FORWARD_DUP_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
-
-#define OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(dup) OLSR_FOR_ALL_AVL_ENTRIES(&processing_set, duptree2dupentry, dup)
-#define OLSR_FOR_ALL_PROCESS_DUP_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_FORWARD_DUP_ENTRIES(dup, iterator) avl_for_each_element_safe(&forward_set, dup, avl, iterator.loop, iterator.safe)
+#define OLSR_FOR_ALL_PROCESS_DUP_ENTRIES(dup, iterator) avl_for_each_element_safe(&processing_set, dup, avl, iterator.loop, iterator.safe)
 
 extern struct avl_tree forward_set, processing_set;
 #endif /*DUPLICATE_SET_H_ */
index 62298e2..50d7860 100644 (file)
@@ -79,7 +79,10 @@ olsr_init_hna_set(void)
 static struct hna_net *
 olsr_lookup_hna_net(struct tc_entry *tc, const struct olsr_ip_prefix *prefix)
 {
-  return (hna_tc_tree2hna(avl_find(&tc->hna_tree, prefix)));
+  struct hna_net *hna;
+
+  hna = avl_find_element(&tc->hna_tree, prefix, hna, hna_tc_node);
+  return hna;
 }
 
 /**
@@ -107,7 +110,7 @@ olsr_add_hna_net(struct tc_entry *tc, const struct olsr_ip_prefix *prefix)
    * Insert into the per-tc hna subtree.
    */
   new_net->hna_tc_node.key = &new_net->hna_prefix;
-  avl_insert(&tc->hna_tree, &new_net->hna_tc_node, false);
+  avl_insert(&tc->hna_tree, &new_net->hna_tc_node);
 
   return new_net;
 }
@@ -151,14 +154,16 @@ void
 olsr_flush_hna_nets(struct tc_entry *tc)
 {
   struct hna_net *hna_net;
+  struct list_iterator iterator;
+
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
 #endif
 
   OLSR_DEBUG(LOG_TC, "flush hna nets of '%s' (%u)\n", olsr_ip_to_string(&buf, &tc->addr), tc->edge_tree.count);
-  OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net) {
+  OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net, iterator) {
     olsr_delete_hna_net(hna_net);
-  } OLSR_FOR_ALL_TC_HNA_ENTRIES_END()
+  }
 }
 
 /**
@@ -235,16 +240,17 @@ olsr_print_hna_set(void)
   struct ipaddr_str buf;
   struct ipprefix_str prefixstr;
   struct hna_net *hna_net;
+  struct list_iterator iterator;
 
   OLSR_INFO(LOG_HNA, "\n--- %s ------------------------------------------------- HNA\n\n", olsr_wallclock_string());
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     OLSR_INFO_NH(LOG_HNA, "HNA-gw %s:\n", olsr_ip_to_string(&buf, &tc->addr));
 
-    OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net) {
+    OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net, iterator) {
       OLSR_INFO_NH(LOG_HNA, "\t%-27s\n", olsr_ip_prefix_to_string(&prefixstr, &hna_net->hna_prefix));
-    } OLSR_FOR_ALL_TC_HNA_ENTRIES_END();
-  } OLSR_FOR_ALL_TC_ENTRIES_END();
+    }
+  }
 #endif
 }
 
@@ -252,12 +258,13 @@ static void
 olsr_prune_hna_entries(struct tc_entry *tc)
 {
   struct hna_net *hna_net;
+  struct list_iterator iterator;
 
-  OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net) {
+  OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_net, iterator) {
     if (hna_net->tc_entry_seqno != tc->hna_seq) {
       olsr_delete_hna_net(hna_net);
     }
-  } OLSR_FOR_ALL_TC_HNA_ENTRIES_END();
+  }
 }
 
 /**
index e67fa62..1cc4ba0 100644 (file)
@@ -58,9 +58,7 @@ struct hna_net {
 
 #define OLSR_HNA_NET_JITTER 5   /* percent */
 
-AVLNODE2STRUCT(hna_tc_tree2hna, hna_net, hna_tc_node)
-#define OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_set) OLSR_FOR_ALL_AVL_ENTRIES(&tc->hna_tree, hna_tc_tree2hna, hna_set)
-#define OLSR_FOR_ALL_TC_HNA_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_TC_HNA_ENTRIES(tc, hna_set, iterator) avl_for_each_element_safe(&tc->hna_tree, hna_set, hna_tc_node, iterator.loop, iterator.safe)
 
 /* HNA msg input parser */
 void olsr_input_hna(struct olsr_message *, struct interface *, union olsr_ip_addr *, enum duplicate_status);
index 838c44b..b330969 100644 (file)
@@ -98,7 +98,7 @@ init_interfaces(void)
 
   /* Initial values */
   list_init_head(&interface_head);
-  avl_init(&interface_lost_tree, avl_comp_default);
+  avl_init(&interface_lost_tree, avl_comp_default, false, NULL);
 
   /*
    * Get some cookies for getting stats to ease troubleshooting.
@@ -152,20 +152,17 @@ static void add_lost_interface_ip(union olsr_ip_addr *ip, uint32_t hello_timeout
   lost->node.key = &lost->ip;
   lost->ip = *ip;
   lost->valid_until = olsr_getTimestamp(hello_timeout * 2);
-  avl_insert(&interface_lost_tree, &lost->node, false);
+  avl_insert(&interface_lost_tree, &lost->node);
 
   OLSR_DEBUG(LOG_INTERFACE, "Added %s to lost interface list for %d ms\n",
       olsr_ip_to_string(&buf, ip), hello_timeout*2);
 }
 
 static struct interface_lost *get_lost_interface_ip(union olsr_ip_addr *ip) {
-  struct avl_node *node;
+  struct interface_lost *lost;
   assert(ip);
-  node = avl_find(&interface_lost_tree, ip);
-  if (node) {
-    return node_tree2lostif(node);
-  }
-  return NULL;
+  lost = avl_find_element(&interface_lost_tree, ip, lost, node);
+  return lost;
 }
 
 bool
@@ -184,9 +181,9 @@ void destroy_interfaces(void) {
     remove_interface(ptr);
   }
 
-  OLSR_FOR_ALL_LOSTIF_ENTRIES(lost) {
+  OLSR_FOR_ALL_LOSTIF_ENTRIES(lost, iterator) {
     remove_lost_interface_ip(lost);
-  } OLSR_FOR_ALL_LOSTIF_ENTRIES_END();
+  }
 }
 
 /**
@@ -197,6 +194,7 @@ check_interface_updates(void *foo __attribute__ ((unused)))
 {
   struct olsr_if_config *tmp_if;
   struct interface_lost *lost;
+  struct list_iterator iterator;
 
   OLSR_DEBUG(LOG_INTERFACE, "Checking for updates in the interface set\n");
 
@@ -221,11 +219,11 @@ check_interface_updates(void *foo __attribute__ ((unused)))
   }
 
   /* clean up lost interface tree */
-  OLSR_FOR_ALL_LOSTIF_ENTRIES(lost) {
+  OLSR_FOR_ALL_LOSTIF_ENTRIES(lost, iterator) {
     if (olsr_isTimedOut(lost->valid_until)) {
       remove_lost_interface_ip(lost);
     }
-  } OLSR_FOR_ALL_LOSTIF_ENTRIES_END()
+  }
 }
 
 /**
index a226ba9..f63b822 100644 (file)
@@ -179,10 +179,7 @@ struct interface_lost {
   uint32_t valid_until;
 };
 
-AVLNODE2STRUCT(node_tree2lostif, interface_lost, node);
-
-#define OLSR_FOR_ALL_LOSTIF_ENTRIES(lostif) OLSR_FOR_ALL_AVL_ENTRIES(&interface_lost_tree, node_tree2lostif, lostif)
-#define OLSR_FOR_ALL_LOSTIF_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_LOSTIF_ENTRIES(lostif, iterator) avl_for_each_element_safe(&interface_lost_tree, lostif, node, iterator.loop, iterator.safe)
 
 #define OLSR_BUFFER_HOLD_JITTER 25      /* percent */
 #define OLSR_BUFFER_HOLD_TIME  100      /* milliseconds */
index 285b061..b86c9ce 100644 (file)
@@ -50,16 +50,16 @@ void
 olsr_calculate_lq_mpr(void)
 {
   struct nbr2_entry *nbr2;
+  struct nbr_entry *neigh;
   struct nbr_con *walker;
   struct link_entry *lnk;
-  struct list_iterator iterator;
+  struct list_iterator iterator, iterator2;
   int k;
-  struct nbr_entry *neigh;
   olsr_linkcost best, best_1hop;
   bool mpr_changes = false;
   bool found_better_path;
 
-  OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
+  OLSR_FOR_ALL_NBR_ENTRIES(neigh, iterator) {
 
     /* Memorize previous MPR status. */
     neigh->was_mpr = neigh->is_mpr;
@@ -78,10 +78,10 @@ olsr_calculate_lq_mpr(void)
       mpr_changes = true;
     }
 
-  } OLSR_FOR_ALL_NBR_ENTRIES_END();
+  }
 
   /* loop through all 2-hop neighbours */
-  OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) {
+  OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, iterator) {
 
     best_1hop = LINK_COST_BROKEN;
 
@@ -106,12 +106,12 @@ olsr_calculate_lq_mpr(void)
       /* see wether we find a better route via an MPR */
       walker = NULL;
       found_better_path = false;
-      OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker) {
+      OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, iterator2) {
         if (walker->path_linkcost < best_1hop) {
           found_better_path = true;
           break;
         }
-      } OLSR_FOR_ALL_NBR_CON_ENTRIES_END()
+      }
 
       /* we've reached the end of the list, so we haven't found
        * a better route via an MPR - so, skip MPR selection for
@@ -126,9 +126,9 @@ olsr_calculate_lq_mpr(void)
        */
 
       /* mark all 1-hop neighbours as not selected */
-      OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker) {
+      OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, iterator2) {
         walker->nbr->skip = false;
-      } OLSR_FOR_ALL_NBR_CON_ENTRIES_END();
+      }
 
       for (k = 0; k < olsr_cnf->mpr_coverage; k++) {
 
@@ -136,12 +136,12 @@ olsr_calculate_lq_mpr(void)
         neigh = NULL;
         best = LINK_COST_BROKEN;
 
-        OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker) {
+        OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, walker, iterator2) {
           if (walker->nbr->is_sym && !walker->nbr->skip && walker->path_linkcost < best) {
             neigh = walker->nbr;
             best = walker->path_linkcost;
           }
-        } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END();
+        }
 
         /*
          * Found a 1-hop neighbor that we haven't previously selected.
@@ -163,7 +163,7 @@ olsr_calculate_lq_mpr(void)
           break;
         }
       }
-  } OLSR_FOR_ALL_NBR2_ENTRIES_END();
+  }
 
   /* ugly hack */
   OLSR_FOR_ALL_LINK_ENTRIES(lnk, iterator) {
index 5650b8d..23be376 100644 (file)
 #include <assert.h>
 #include <errno.h>
 
-#include "ipcalc.h"
 #include "defs.h"
+#include "common/avl.h"
+#include "common/avl_olsr_comp.h"
 #include "olsr.h"
 #include "log.h"
+#include "ipcalc.h"
 #include "scheduler.h"
 #include "parser.h"
 #include "plugin_loader.h"
@@ -212,6 +214,7 @@ main(int argc, char *argv[])
 #endif
 
   /* Set avl tree comparator */
+#if 0
   if (olsr_cnf->ipsize == 4) {
     avl_comp_default = avl_comp_ipv4;
     avl_comp_addr_origin_default = avl_comp_ipv4_addr_origin;
@@ -223,7 +226,7 @@ main(int argc, char *argv[])
     avl_comp_prefix_default = avl_comp_ipv6_prefix;
     avl_comp_prefix_origin_default = avl_comp_ipv6_prefix_origin;
   }
-
+#endif
   /* initialize logging */
   olsr_log_init();
 
@@ -526,13 +529,14 @@ static void
 olsr_shutdown(void)
 {
   struct mid_entry *mid;
+  struct list_iterator iterator;
 
   olsr_delete_all_kernel_routes();
 
   /* Flush MID database */
-  OLSR_FOR_ALL_MID_ENTRIES(mid) {
+  OLSR_FOR_ALL_MID_ENTRIES(mid, iterator) {
     olsr_delete_mid_entry(mid);
-  } OLSR_FOR_ALL_MID_ENTRIES_END();
+  }
 
   /* Flush TC database */
   olsr_delete_all_tc_entries();
index f97cf17..3926e57 100644 (file)
@@ -72,7 +72,7 @@ olsr_init_mid_set(void)
 {
   OLSR_INFO(LOG_MID, "Initialize MID set...\n");
 
-  avl_init(&mid_tree, avl_comp_default);
+  avl_init(&mid_tree, avl_comp_default, false, NULL);
 
   /*
    * Get some cookies for getting stats to ease troubleshooting.
@@ -139,12 +139,15 @@ olsr_flush_tc_duplicates(struct mid_entry *alias) {
 static void
 olsr_flush_nbr2_duplicates(struct mid_entry *alias)
 {
-  struct tc_entry *tc = alias->mid_tc;
+  struct tc_entry *tc;
+  struct list_iterator iterator;
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf1, buf2;
 #endif
 
-  OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+  tc = alias->mid_tc;
+
+  OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator) {
     struct nbr_entry *nbr;
     struct nbr2_entry *nbr2 = olsr_lookup_nbr2_entry(&alias->mid_alias_addr, false);
 
@@ -174,7 +177,6 @@ olsr_flush_nbr2_duplicates(struct mid_entry *alias)
       }
     }
   }
-  OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, mid_alias);
 }
 
 /**
@@ -256,13 +258,13 @@ olsr_insert_mid_entry(const union olsr_ip_addr *main_addr,
    * Insert into the per-tc mid subtree.
    */
   alias->mid_tc_node.key = &alias->mid_alias_addr;
-  avl_insert(&tc->mid_tree, &alias->mid_tc_node, false);
+  avl_insert(&tc->mid_tree, &alias->mid_tc_node);
 
   /*
    * Insert into the global mid tree.
    */
   alias->mid_node.key = &alias->mid_alias_addr;
-  avl_insert(&mid_tree, &alias->mid_node, false);
+  avl_insert(&mid_tree, &alias->mid_node);
 
   /*
    * Add a rt_path for the alias.
@@ -332,7 +334,9 @@ olsr_update_mid_entry(const union olsr_ip_addr *main_addr,
 struct mid_entry *
 olsr_lookup_tc_mid_entry(struct tc_entry *tc, const union olsr_ip_addr *adr)
 {
-  return (alias_tree2mid(avl_find(&tc->mid_tree, adr)));
+  struct mid_entry *mid;
+  mid = avl_find_element(&tc->mid_tree, adr, mid, mid_tc_node);
+  return mid;
 }
 
 /**
@@ -344,7 +348,9 @@ olsr_lookup_tc_mid_entry(struct tc_entry *tc, const union olsr_ip_addr *adr)
 static struct mid_entry *
 olsr_lookup_mid_entry(const union olsr_ip_addr *adr)
 {
-  return (global_tree2mid(avl_find(&mid_tree, adr)));
+  struct mid_entry *mid;
+  mid = avl_find_element(&mid_tree, adr, mid, mid_node);
+  return mid;
 }
 
 /**
@@ -407,10 +413,10 @@ void
 olsr_flush_mid_entries(struct tc_entry *tc)
 {
   struct mid_entry *alias;
-
-  OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+  struct list_iterator iterator;
+  OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator) {
     olsr_delete_mid_entry(alias);
-  } OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
+  }
 }
 
 /**
@@ -423,15 +429,16 @@ olsr_print_mid_set(void)
 #if !defined REMOVE_LOG_INFO
   struct tc_entry *tc;
   struct mid_entry *alias;
+  struct list_iterator iterator;
   struct ipaddr_str buf1, buf2;
 
   OLSR_INFO(LOG_MID, "\n--- %s ------------------------------------------------- MID\n\n", olsr_wallclock_string());
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
-    OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
+    OLSR_FOR_ALL_TC_MID_ENTRIES(tc, alias, iterator) {
       OLSR_INFO_NH(LOG_MID, "%-15s: %s\n", olsr_ip_to_string(&buf1, &tc->addr), olsr_ip_to_string(&buf2, &alias->mid_alias_addr));
-    } OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, alias);
-  } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
+    }
+  }
 #endif
 }
 
index 1a08bb4..c470ad2 100644 (file)
@@ -56,13 +56,8 @@ struct mid_entry {
   struct timer_entry *mid_timer;       /* Vtime */
 };
 
-AVLNODE2STRUCT(global_tree2mid, mid_entry, mid_node);
-#define OLSR_FOR_ALL_MID_ENTRIES(mid_alias) OLSR_FOR_ALL_AVL_ENTRIES(&mid_tree, global_tree2mid, mid_alias)
-#define OLSR_FOR_ALL_MID_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
-
-AVLNODE2STRUCT(alias_tree2mid, mid_entry, mid_tc_node);
-#define OLSR_FOR_ALL_TC_MID_ENTRIES(tc, mid_alias) OLSR_FOR_ALL_AVL_ENTRIES(&tc->mid_tree, alias_tree2mid, mid_alias)
-#define OLSR_FOR_ALL_TC_MID_ENTRIES_END(tc, mid_alias) OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_MID_ENTRIES(mid_alias, iterator) avl_for_each_element_safe(&mid_tree, mid_alias, mid_node, iterator.loop, iterator.safe)
+#define OLSR_FOR_ALL_TC_MID_ENTRIES(tc, mid_alias, iterator) avl_for_each_element_safe(&tc->mid_tree, mid_alias, mid_tc_node, iterator.loop, iterator.safe)
 
 #define OLSR_MID_JITTER 5       /* percent */
 
index 8f13ffd..80c6ff8 100644 (file)
@@ -73,8 +73,8 @@ void
 olsr_init_neighbor_table(void)
 {
   OLSR_INFO(LOG_NEIGHTABLE, "Initializing neighbor tree.\n");
-  avl_init(&nbr_tree, avl_comp_default);
-  avl_init(&nbr2_tree, avl_comp_default);
+  avl_init(&nbr_tree, avl_comp_default, false, NULL);
+  avl_init(&nbr2_tree, avl_comp_default, false, NULL);
 
   nbr_connector_timer_cookie = olsr_alloc_cookie("Neighbor connector", OLSR_COOKIE_TYPE_TIMER);
   nbr_connector_mem_cookie = olsr_alloc_cookie("Neighbor connector", OLSR_COOKIE_TYPE_MEMORY);
@@ -119,7 +119,7 @@ olsr_add_nbr_entry(const union olsr_ip_addr *addr)
   nbr->is_sym = false;
 
   /* Init subtree for nbr2 connectors */
-  avl_init(&nbr->con_tree, avl_comp_default);
+  avl_init(&nbr->con_tree, avl_comp_default, false, NULL);
 
   nbr->linkcount = 0;
   nbr->is_mpr = false;
@@ -137,7 +137,7 @@ olsr_add_nbr_entry(const union olsr_ip_addr *addr)
 
   /* Add to the global neighbor tree */
   nbr->nbr_node.key = &nbr->nbr_addr;
-  avl_insert(&nbr_tree, &nbr->nbr_node, false);
+  avl_insert(&nbr_tree, &nbr->nbr_node);
 
   return nbr;
 }
@@ -152,7 +152,7 @@ void
 olsr_delete_nbr_entry(struct nbr_entry *nbr)
 {
   struct nbr_con *connector;
-
+  struct list_iterator iterator;
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
 #endif
@@ -162,9 +162,9 @@ olsr_delete_nbr_entry(struct nbr_entry *nbr)
   /*
    * Remove all references pointing to this neighbor.
    */
-  OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, connector) {
+  OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, connector, iterator) {
     olsr_delete_nbr_con(connector);
-  } OLSR_FOR_ALL_NBR_CON_ENTRIES_END()
+  }
 
   /* remove corresponding tc_edge if not already removed by olsr_delete_all_tc_entries() */
   if (nbr->tc_edge) {
@@ -197,7 +197,7 @@ struct nbr_entry *
 olsr_lookup_nbr_entry(const union olsr_ip_addr *addr, bool lookupalias)
 {
   const union olsr_ip_addr *main_addr = NULL;
-  struct avl_node *node;
+  struct nbr_entry *nbr;
 
   /*
    * Find main address of node
@@ -209,11 +209,8 @@ olsr_lookup_nbr_entry(const union olsr_ip_addr *addr, bool lookupalias)
     main_addr = addr;
   }
 
-  node = avl_find(&nbr_tree, addr);
-  if (node) {
-    return nbr_node_to_nbr(node);
-  }
-  return NULL;
+  nbr = avl_find_element(&nbr_tree, addr, nbr, nbr_node);
+  return nbr;
 }
 
 void olsr_update_nbr_status(struct nbr_entry *entry) {
@@ -287,13 +284,13 @@ olsr_add_nbr2_entry(const union olsr_ip_addr *addr) {
   nbr2 = olsr_cookie_malloc(nbr2_mem_cookie);
 
   /* Init neighbor connector subtree */
-  avl_init(&nbr2->con_tree, avl_comp_default);
+  avl_init(&nbr2->con_tree, avl_comp_default, false, NULL);
 
   nbr2->nbr2_addr = *addr;
 
   /* Add to global neighbor 2 tree */
   nbr2->nbr2_node.key = &nbr2->nbr2_addr;
-  avl_insert(&nbr2_tree, &nbr2->nbr2_node, false);
+  avl_insert(&nbr2_tree, &nbr2->nbr2_node);
 
   return nbr2;
 }
@@ -306,6 +303,7 @@ olsr_add_nbr2_entry(const union olsr_ip_addr *addr) {
 void
 olsr_delete_nbr2_entry(struct nbr2_entry *nbr2) {
   struct nbr_con *connector;
+  struct list_iterator iterator;
 
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
@@ -316,9 +314,9 @@ olsr_delete_nbr2_entry(struct nbr2_entry *nbr2) {
   /*
    * Remove all references pointing to this two hop neighbor.
    */
-  OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector) {
+  OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector, iterator) {
     internal_delete_nbr_con(connector);
-  } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END();
+  }
 
   /* Remove from global neighbor tree */
   avl_delete(&nbr2_tree, &nbr2->nbr2_node);
@@ -330,7 +328,7 @@ olsr_delete_nbr2_entry(struct nbr2_entry *nbr2) {
 struct nbr2_entry *
 olsr_lookup_nbr2_entry(const union olsr_ip_addr *addr, bool lookupalias) {
   const union olsr_ip_addr *main_addr = NULL;
-  struct avl_node *node;
+  struct nbr2_entry *entry;
 
   /*
    * Find main address of node
@@ -342,11 +340,8 @@ olsr_lookup_nbr2_entry(const union olsr_ip_addr *addr, bool lookupalias) {
     main_addr = addr;
   }
 
-  node = avl_find(&nbr2_tree, addr);
-  if (node) {
-    return nbr2_node_to_nbr2(node);
-  }
-  return NULL;
+  entry = avl_find_element(&nbr2_tree, addr, entry, nbr2_node);
+  return entry;
 }
 
 /**
@@ -382,8 +377,8 @@ olsr_link_nbr_nbr2(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr, u
   connector->nbr_tree_node.key = &nbr2->nbr2_addr;
   connector->nbr2_tree_node.key = &nbr->nbr_addr;
 
-  avl_insert(&nbr->con_tree, &connector->nbr_tree_node, false);
-  avl_insert(&nbr2->con_tree, &connector->nbr2_tree_node, false);
+  avl_insert(&nbr->con_tree, &connector->nbr_tree_node);
+  avl_insert(&nbr2->con_tree, &connector->nbr2_tree_node);
 
   connector->path_linkcost = LINK_COST_BROKEN;
 
@@ -436,12 +431,8 @@ olsr_delete_nbr_con(struct nbr_con *connector) {
  */
 struct nbr_con *
 olsr_lookup_nbr_con_entry(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_addr) {
-  struct avl_node *node;
-
-  node = avl_find(&nbr->con_tree, nbr2_addr);
-  if (node) {
-    return nbr_con_node_to_connector(node);
-  }
+  struct nbr_con *con;
+  con = avl_find_element(&nbr->con_tree, nbr2_addr, con, nbr_tree_node);
   return NULL;
 }
 
@@ -455,12 +446,8 @@ olsr_lookup_nbr_con_entry(struct nbr_entry *nbr, const union olsr_ip_addr *nbr2_
  */
 struct nbr_con *
 olsr_lookup_nbr2_con_entry(struct nbr2_entry *nbr2, const union olsr_ip_addr *nbr_addr) {
-  struct avl_node *node;
-
-  node = avl_find(&nbr2->con_tree, nbr_addr);
-  if (node) {
-    return nbr2_con_node_to_connector(node);
-  }
+  struct nbr_con *con;
+  con = avl_find_element(&nbr2->con_tree, nbr_addr, con, nbr2_tree_node);
   return NULL;
 }
 
@@ -495,13 +482,14 @@ olsr_print_neighbor_table(void)
   struct ipaddr_str buf;
   struct nbr2_entry *nbr2;
   struct nbr_con *connector;
+  struct list_iterator iterator, iterator2;
   char lqbuffer[LQTEXT_MAXLENGTH];
   bool first;
 
   OLSR_INFO(LOG_NEIGHTABLE, "\n--- %s ------------------------------------------------ NEIGHBORS\n\n"
             "%-*s\tSYM\tMPR\tMPRS\twill\n", olsr_wallclock_string(), ipwidth, "IP address");
 
-  OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
+  OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) {
 
     lnk = get_best_link_to_neighbor_ip(&nbr->nbr_addr);
     if (!lnk) {
@@ -514,22 +502,22 @@ olsr_print_neighbor_table(void)
                  nbr->is_mpr ? "YES" : "NO",
                  nbr->mprs_count == 0  ? "NO  " : "YES ",
                  nbr->willingness);
-  } OLSR_FOR_ALL_NBR_ENTRIES_END();
+  }
 
   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());
 
-  OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) {
+  OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, iterator) {
     first = true;
-    OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector) {
+    OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, connector, iterator2) {
       OLSR_INFO_NH(LOG_2NEIGH, "%-*s  %-*s  %s\n",
                    ipwidth, first ? olsr_ip_to_string(&buf, &nbr2->nbr2_addr) : "",
                    ipwidth, olsr_ip_to_string(&buf, &connector->nbr->nbr_addr),
                    olsr_get_linkcost_text(connector->path_linkcost, false, lqbuffer, sizeof(lqbuffer)));
 
       first = false;
-    } OLSR_FOR_ALL_NBR2_CON_ENTRIES_END()
-  } OLSR_FOR_ALL_NBR2_ENTRIES_END()
+    }
+  }
 
 #endif
 }
index e9a23fe..88621de 100644 (file)
@@ -102,13 +102,9 @@ struct nbr2_entry {
  * the loop prefetches the next node in order to not loose context if
  * for example the caller wants to delete the current entry.
  */
-AVLNODE2STRUCT(nbr_node_to_nbr, nbr_entry, nbr_node);
-#define OLSR_FOR_ALL_NBR_ENTRIES(nbr) OLSR_FOR_ALL_AVL_ENTRIES(&nbr_tree, nbr_node_to_nbr, nbr)
-#define OLSR_FOR_ALL_NBR_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) avl_for_each_element_safe(&nbr_tree, nbr, nbr_node, iterator.loop, iterator.safe)
 
-AVLNODE2STRUCT(nbr_con_node_to_connector, nbr_con, nbr_tree_node);
-#define OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, con) OLSR_FOR_ALL_AVL_ENTRIES(&nbr->con_tree, nbr_con_node_to_connector, con)
-#define OLSR_FOR_ALL_NBR_CON_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_NBR_CON_ENTRIES(nbr, con, iterator) avl_for_each_element_safe(&nbr->con_tree, con, nbr_tree_node, iterator.loop, iterator.safe)
 
 /*
  * macros for traversing two-hop neighbors and neighbor ref lists.
@@ -118,13 +114,9 @@ AVLNODE2STRUCT(nbr_con_node_to_connector, nbr_con, nbr_tree_node);
  * the loop prefetches the next node in order to not loose context if
  * for example the caller wants to delete the current entry.
  */
-AVLNODE2STRUCT(nbr2_node_to_nbr2, nbr2_entry, nbr2_node);
-#define OLSR_FOR_ALL_NBR2_ENTRIES(nbr2) OLSR_FOR_ALL_AVL_ENTRIES(&nbr2_tree, nbr2_node_to_nbr2, nbr2)
-#define OLSR_FOR_ALL_NBR2_ENTRIES_END(nbr2) OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_NBR2_ENTRIES(nbr2, iterator) avl_for_each_element_safe(&nbr2_tree, nbr2, nbr2_node, iterator.loop, iterator.safe)
 
-AVLNODE2STRUCT(nbr2_con_node_to_connector, nbr_con, nbr2_tree_node);
-#define OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, con) OLSR_FOR_ALL_AVL_ENTRIES(&nbr2->con_tree, nbr2_con_node_to_connector, con)
-#define OLSR_FOR_ALL_NBR2_CON_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_NBR2_CON_ENTRIES(nbr2, con, iterator) avl_for_each_element_safe(&nbr2->con_tree, con, nbr2_tree_node, iterator.loop, iterator.safe)
 
 /*
  * The one hop neighbor and two hop neighbor trees.
index 276f970..651c7e0 100644 (file)
@@ -97,7 +97,7 @@ init_net(void)
   const char *const *defaults = olsr_cnf->ip_version == AF_INET ? deny_ipv4_defaults : deny_ipv6_defaults;
 
   /* Init filter tree */
-  avl_init(&filter_tree, avl_comp_default);
+  avl_init(&filter_tree, avl_comp_default, false, NULL);
 
   if (*defaults) {
     OLSR_INFO(LOG_NETWORKING, "Initializing invalid IP list.\n");
@@ -117,10 +117,11 @@ void
 deinit_netfilters(void)
 {
   struct filter_entry *filter;
-  OLSR_FOR_ALL_FILTERS(filter) {
+  struct list_iterator iterator;
+  OLSR_FOR_ALL_FILTERS(filter, iterator) {
     avl_delete(&filter_tree, &filter->filter_node);
     free(filter);
-  } OLSR_FOR_ALL_FILTERS_END();
+  }
 }
 
 /**
@@ -403,7 +404,7 @@ olsr_add_invalid_address(const union olsr_ip_addr *addr)
 
   filter->filter_addr = *addr;
   filter->filter_node.key = &filter->filter_addr;
-  avl_insert(&filter_tree, &filter->filter_node, false);
+  avl_insert(&filter_tree, &filter->filter_node);
 
   OLSR_INFO(LOG_NETWORKING, "Added %s to filter set\n", olsr_ip_to_string(&buf, &filter->filter_addr));
 }
@@ -412,9 +413,7 @@ olsr_add_invalid_address(const union olsr_ip_addr *addr)
 bool
 olsr_validate_address(const union olsr_ip_addr *addr)
 {
-  const struct filter_entry *filter = filter_tree2filter(avl_find(&filter_tree, addr));
-
-  if (filter) {
+  if (avl_find(&filter_tree, addr)) {
 #if !defined REMOVE_LOG_DEBUG
     struct ipaddr_str buf;
 #endif
index e386efd..0cafd77 100644 (file)
@@ -61,9 +61,7 @@ struct filter_entry {
   union olsr_ip_addr filter_addr;
 };
 
-AVLNODE2STRUCT(filter_tree2filter, filter_entry, filter_node);
-#define OLSR_FOR_ALL_FILTERS(filter) OLSR_FOR_ALL_AVL_ENTRIES(&filter_tree, filter_tree2filter, filter)
-#define OLSR_FOR_ALL_FILTERS_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_FILTERS(filter, iterator) avl_for_each_element_safe(&filter_tree, filter, filter_node, iterator.loop, iterator.safe)
 
 void init_net(void);
 
index cf64496..c61fbea 100644 (file)
@@ -144,7 +144,7 @@ olsr_com_html2telnet_gate(struct comport_connection *con, struct http_request *r
 
 void
 olsr_com_init_http(void) {
-  avl_init(&http_handler_tree, &avl_comp_strcasecmp);
+  avl_init(&http_handler_tree, &avl_comp_strcasecmp, false, NULL);
 
   htmlsite_cookie = olsr_alloc_cookie("comport http sites", OLSR_COOKIE_TYPE_MEMORY);
   olsr_cookie_set_memory_size(htmlsite_cookie, sizeof(struct olsr_html_site));
@@ -158,9 +158,11 @@ olsr_com_init_http(void) {
 
 void olsr_com_destroy_http(void) {
   struct olsr_html_site *site;
-  OLSR_FOR_ALL_HTML_ENTRIES(site) {
+  struct list_iterator iterator;
+
+  OLSR_FOR_ALL_HTML_ENTRIES(site, iterator) {
     olsr_com_remove_htmlsite(site);
-  } OLSR_FOR_ALL_HTML_ENTRIES_END()
+  }
 }
 
 struct olsr_html_site *
@@ -174,7 +176,7 @@ olsr_com_add_htmlsite(const char *path, const char *content, size_t length) {
   site->site_data = content;
   site->site_length = length;
 
-  avl_insert(&http_handler_tree, &site->node, false);
+  avl_insert(&http_handler_tree, &site->node);
   return site;
 }
 
@@ -189,7 +191,7 @@ olsr_com_add_htmlhandler(void(*sitehandler)(struct comport_connection *con, stru
   site->static_site = false;
   site->sitehandler = sitehandler;
 
-  avl_insert(&http_handler_tree, &site->node, false);
+  avl_insert(&http_handler_tree, &site->node);
   return site;
 }
 
index 6307830..a4acbce 100644 (file)
@@ -94,9 +94,7 @@ struct olsr_html_site {
   void (*sitehandler)(struct comport_connection *con, struct http_request *request);
 };
 
-AVLNODE2STRUCT(html_tree2site, olsr_html_site, node);
-#define OLSR_FOR_ALL_HTML_ENTRIES(site) OLSR_FOR_ALL_AVL_ENTRIES(&http_handler_tree, html_tree2site, site)
-#define OLSR_FOR_ALL_HTML_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_HTML_ENTRIES(site, iterator) avl_for_each_element_safe(&http_handler_tree, site, node, iterator.loop, iterator.safe)
 
 void olsr_com_init_http(void);
 void olsr_com_destroy_http(void);
index 86c5243..95704a8 100644 (file)
@@ -52,6 +52,8 @@
 #include "olsr_comport_txt.h"
 #include "plugin_loader.h"
 
+#define OLSR_FOR_EACH_TXTCMD_ENTRY(cmd, iterator) avl_for_each_element_safe(&txt_normal_tree, cmd, node, iterator.loop, iterator.safe)
+
 struct txt_repeat_data {
   struct timer_entry *timer;
   struct autobuf *buf;
@@ -122,8 +124,8 @@ void
 olsr_com_init_txt(void) {
   size_t i;
 
-  avl_init(&txt_normal_tree, &avl_comp_strcasecmp);
-  avl_init(&txt_help_tree, &avl_comp_strcasecmp);
+  avl_init(&txt_normal_tree, &avl_comp_strcasecmp, false, NULL);
+  avl_init(&txt_help_tree, &avl_comp_strcasecmp, false, NULL);
 
   txtcommand_cookie = olsr_alloc_cookie("comport txt commands", OLSR_COOKIE_TYPE_MEMORY);
   olsr_cookie_set_memory_size(txtcommand_cookie, sizeof(struct olsr_txtcommand));
@@ -152,7 +154,7 @@ olsr_com_add_normal_txtcommand (const char *command, olsr_txthandler handler) {
   txt->node.key = strdup(command);
   txt->handler = handler;
 
-  avl_insert(&txt_normal_tree, &txt->node, false);
+  avl_insert(&txt_normal_tree, &txt->node);
   return txt;
 }
 
@@ -164,7 +166,7 @@ olsr_com_add_help_txtcommand (const char *command, olsr_txthandler handler) {
   txt->node.key = strdup(command);
   txt->handler = handler;
 
-  avl_insert(&txt_help_tree, &txt->node, false);
+  avl_insert(&txt_help_tree, &txt->node);
   return txt;
 }
 
@@ -342,9 +344,10 @@ static enum olsr_txtcommand_result
 olsr_txtcmd_help(struct comport_connection *con,
     const char *cmd __attribute__ ((unused)), const char *param) {
   struct olsr_txtcommand *ptr;
+  struct list_iterator iterator;
 
   if (param != NULL) {
-    ptr = (struct olsr_txtcommand *)avl_find(&txt_help_tree, cmd);
+    ptr = avl_find_element(&txt_help_tree, cmd, ptr, node);
     if (ptr != NULL) {
       return ptr->handler(con, param, NULL);
     }
@@ -355,12 +358,10 @@ olsr_txtcmd_help(struct comport_connection *con,
     return ABUF_ERROR;
   }
 
-  ptr = (struct olsr_txtcommand *)avl_walk_first(&txt_normal_tree);
-  while (ptr) {
+  OLSR_FOR_EACH_TXTCMD_ENTRY(ptr, iterator) {
     if (abuf_appendf(&con->out, "  %s\n", (char *)ptr->node.key) < 0) {
       return ABUF_ERROR;
     }
-    ptr = (struct olsr_txtcommand *)avl_walk_next(&ptr->node);
   }
 
   if (abuf_puts(&con->out, "Use 'help <command> to see a help text for a certain command\n") < 0) {
@@ -472,17 +473,18 @@ olsr_txtcmd_version(struct comport_connection *con,
 static enum olsr_txtcommand_result
 olsr_txtcmd_plugin(struct comport_connection *con, const char *cmd, const char *param) {
   struct olsr_plugin *plugin;
+  struct list_iterator iterator;
   char *para2 = NULL;
   if (param == NULL || strcasecmp(param, "list") == 0) {
     if (abuf_puts(&con->out, "Table:\n") < 0) {
       return ABUF_ERROR;
     }
-    OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin) {
+    OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin, iterator) {
       if (abuf_appendf(&con->out, " %-30s\t%s\t%s\n",
           plugin->name, plugin->internal_active ? "active" : "", plugin->internal_dlhandle == NULL ? "static" : "") < 0) {
         return ABUF_ERROR;
       }
-    } OLSR_FOR_ALL_PLUGIN_ENTRIES_END()
+    }
     return CONTINUE;
   }
 
index 59886aa..c52b4cb 100644 (file)
@@ -65,8 +65,6 @@ struct olsr_txtcommand {
   olsr_txthandler handler;
 };
 
-AVLNODE2STRUCT(txt_tree2cmd, olsr_txtcommand, node);
-
 void olsr_com_init_txt(void);
 void olsr_com_destroy_txt(void);
 
index fcf6c48..4f1717f 100644 (file)
 struct avl_tree olsr_cookie_tree;
 
 void olsr_cookie_init(void) {
-  avl_init(&olsr_cookie_tree, &avl_comp_strcasecmp);
+  avl_init(&olsr_cookie_tree, &avl_comp_strcasecmp, false, NULL);
 }
 
 /*
  * Allocate a cookie for the next available cookie id.
  */
 struct olsr_cookie_info *
-olsr_alloc_cookie(const char *cookie_name, olsr_cookie_type cookie_type)
+olsr_alloc_cookie(const char *cookie_name, enum olsr_cookie_type cookie_type)
 {
   static uint16_t next_brand_id = 1;
 
@@ -88,7 +88,7 @@ olsr_alloc_cookie(const char *cookie_name, olsr_cookie_type cookie_type)
     ci->ci_membrand = 0;
   }
 
-  avl_insert(&olsr_cookie_tree, &ci->node, true);
+  avl_insert(&olsr_cookie_tree, &ci->node);
   return ci;
 }
 
@@ -137,13 +137,14 @@ void
 olsr_delete_all_cookies(void)
 {
   struct olsr_cookie_info *info;
+  struct list_iterator iterator;
 
   /*
    * Walk the full index range and kill 'em all.
    */
-  OLSR_FOR_ALL_COOKIES(info) {
+  OLSR_FOR_ALL_COOKIES(info, iterator) {
     olsr_free_cookie(info);
-  } OLSR_FOR_ALL_COOKIES_END()
+  }
 }
 
 /*
index 24d238f..76c7852 100644 (file)
 
 extern struct avl_tree olsr_cookie_tree;
 
-typedef enum olsr_cookie_type_ {
+enum olsr_cookie_type {
   OLSR_COOKIE_TYPE_MIN,
   OLSR_COOKIE_TYPE_MEMORY,
   OLSR_COOKIE_TYPE_TIMER,
   OLSR_COOKIE_TYPE_MAX
-} olsr_cookie_type;
+};
 
 /*
  * This is a cookie. A cookie is a tool aimed for olsrd developers.
@@ -63,7 +63,7 @@ typedef enum olsr_cookie_type_ {
 struct olsr_cookie_info {
   struct avl_node node;
   char *ci_name;                       /* Name */
-  olsr_cookie_type ci_type;            /* Type of cookie */
+  enum olsr_cookie_type ci_type;       /* Type of cookie */
   unsigned int ci_flags;               /* Misc. flags */
   unsigned int ci_usage;               /* Stats, resource usage */
   unsigned int ci_changes;             /* Stats, resource churn */
@@ -75,9 +75,7 @@ struct olsr_cookie_info {
   uint16_t ci_membrand;
 };
 
-AVLNODE2STRUCT(cookie_node2cookie, olsr_cookie_info, node);
-#define OLSR_FOR_ALL_COOKIES(ci) OLSR_FOR_ALL_AVL_ENTRIES(&olsr_cookie_tree, cookie_node2cookie, ci)
-#define OLSR_FOR_ALL_COOKIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_COOKIES(ci, iterator) avl_for_each_element_safe(&olsr_cookie_tree, ci, node, iterator.loop, iterator.safe)
 
 /* Cookie flags */
 #define COOKIE_NO_MEMCLEAR  ( 1 << 0)   /* Do not clear memory */
@@ -97,7 +95,7 @@ struct olsr_cookie_mem_brand {
 
 /* Externals. */
 void olsr_cookie_init(void);
-struct olsr_cookie_info *EXPORT(olsr_alloc_cookie) (const char *, olsr_cookie_type);
+struct olsr_cookie_info *EXPORT(olsr_alloc_cookie) (const char *, enum olsr_cookie_type);
 void olsr_delete_all_cookies(void);
 void EXPORT(olsr_cookie_set_memory_size) (struct olsr_cookie_info *, size_t);
 void EXPORT(olsr_cookie_set_memory_clear) (struct olsr_cookie_info *, bool);
index c99ecab..4b47efd 100644 (file)
@@ -61,7 +61,7 @@ struct timer_entry *spf_backoff_timer = NULL;
  * after compiler optimization.
  */
 static int
-avl_comp_etx(const void *etx1, const void *etx2)
+avl_comp_etx(const void *etx1, const void *etx2, void *ptr __attribute__ ((unused)))
 {
   if (*(const olsr_linkcost *)etx1 < *(const olsr_linkcost *)etx2) {
     return -1;
@@ -91,7 +91,7 @@ olsr_spf_add_cand_tree(struct avl_tree *tree, struct tc_entry *tc)
   OLSR_DEBUG(LOG_ROUTING, "SPF: insert candidate %s, cost %s\n",
              olsr_ip_to_string(&buf, &tc->addr), olsr_get_linkcost_text(tc->path_cost, false, lqbuffer, sizeof(lqbuffer)));
 
-  avl_insert(tree, &tc->cand_tree_node, true);
+  avl_insert(tree, &tc->cand_tree_node);
 }
 
 /*
@@ -145,7 +145,11 @@ olsr_spf_add_path_list(struct list_entity *head, int *path_count, struct tc_entr
 static struct tc_entry *
 olsr_spf_extract_best(struct avl_tree *tree)
 {
-  return (tree->count > 0 ? cand_tree2tc(avl_walk_first(tree)) : NULL);
+  struct tc_entry *tc = NULL;
+  if (tree->count) {
+    tc = avl_first_element(tree, tc, cand_tree_node);
+  }
+  return tc;
 }
 
 
@@ -160,6 +164,7 @@ static void
 olsr_spf_relax(struct avl_tree *cand_tree, struct tc_entry *tc)
 {
   struct tc_edge_entry *tc_edge;
+  struct list_iterator iterator;
   olsr_linkcost new_cost;
 
 #if !defined REMOVE_LOG_DEBUG
@@ -173,7 +178,7 @@ olsr_spf_relax(struct avl_tree *cand_tree, struct tc_entry *tc)
   /*
    * loop through all edges of this vertex.
    */
-  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) {
     struct tc_entry *new_tc;
 
     assert (tc_edge->edge_inv);
@@ -226,7 +231,7 @@ olsr_spf_relax(struct avl_tree *cand_tree, struct tc_entry *tc)
                  olsr_get_linkcost_text(new_cost, true, lqbuffer, sizeof(lqbuffer)),
                  tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>", new_tc->hops);
     }
-  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END()
+  }
 }
 
 /*
@@ -276,7 +281,6 @@ olsr_calculate_routing_table(void)
   struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
 #endif
   struct avl_tree cand_tree;
-  struct avl_node *rtp_tree_node;
   struct list_entity path_list;          /* head of the path_list */
   struct tc_entry *tc;
   struct rt_path *rtp;
@@ -284,6 +288,7 @@ olsr_calculate_routing_table(void)
   struct nbr_entry *neigh;
   struct link_entry *link;
   int path_count = 0;
+  struct list_iterator iterator;
 
   /* We are done if our backoff timer is running */
   if (spf_backoff_timer) {
@@ -300,22 +305,20 @@ olsr_calculate_routing_table(void)
   /*
    * Prepare the candidate tree and result list.
    */
-  avl_init(&cand_tree, avl_comp_etx);
+  avl_init(&cand_tree, avl_comp_etx, true, NULL);
   list_init_head(&path_list);
   olsr_bump_routingtree_version();
 
   /*
    * Initialize vertices in the lsdb.
    */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     tc->next_hop = NULL;
     tc->path_cost = ROUTE_COST_BROKEN;
     tc->hops = 0;
     tc->cand_tree_node.key = NULL;
     list_init_head(&tc->path_list_node);
   }
-  OLSR_FOR_ALL_TC_ENTRIES_END(tc);
-
 
   /*
    * Check if there was a change in the main IP address.
@@ -341,7 +344,7 @@ olsr_calculate_routing_table(void)
   /*
    * Set the next-hops of our neighbor link.
    */
-  OLSR_FOR_ALL_NBR_ENTRIES(neigh) {
+  OLSR_FOR_ALL_NBR_ENTRIES(neigh, iterator) {
     tc_edge = neigh->tc_edge;
 
     if (neigh->is_sym) {
@@ -351,7 +354,6 @@ olsr_calculate_routing_table(void)
       tc_edge->edge_inv->tc->next_hop = get_best_link_to_neighbor(neigh);
     }
   }
-  OLSR_FOR_ALL_NBR_ENTRIES_END()
 
 #ifdef SPF_PROFILING
   gettimeofday(&t2, NULL);
@@ -397,10 +399,7 @@ olsr_calculate_routing_table(void)
      * If the prefix is already in the RIB, refresh the entry such
      * that olsr_delete_outdated_routes() does not purge it off.
      */
-    for (rtp_tree_node = avl_walk_first(&tc->prefix_tree); rtp_tree_node; rtp_tree_node = avl_walk_next(rtp_tree_node)) {
-
-      rtp = rtp_prefix_tree2rtp(rtp_tree_node);
-
+    OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp, iterator) {
       if (rtp->rtp_rt) {
 
         /*
index 9c0df9c..3f5caf6 100644 (file)
@@ -76,21 +76,20 @@ olsr_hookup_plugin(struct olsr_plugin *pl_def) {
   assert (pl_def->name);
   fprintf(stdout, "hookup %s\n", pl_def->name);
   if (!plugin_tree_initialized) {
-    avl_init(&plugin_tree, avl_comp_strcasecmp);
+    avl_init(&plugin_tree, avl_comp_strcasecmp, false, NULL);
     plugin_tree_initialized = true;
   }
   pl_def->p_node.key = strdup(pl_def->name);
-  avl_insert(&plugin_tree, &pl_def->p_node, false);
+  avl_insert(&plugin_tree, &pl_def->p_node);
 }
 
 struct olsr_plugin *olsr_get_plugin(const char *libname) {
-  struct avl_node *node;
+  struct olsr_plugin *plugin;
   /* SOT: Hacked away the funny plugin check which fails if pathname is included */
   if (strrchr(libname, '/')) libname = strrchr(libname, '/') + 1;
-  if ((node = avl_find(&plugin_tree, libname)) != NULL) {
-    return plugin_node2tree(node);
-  }
-  return NULL;
+
+  plugin = avl_find_element(&plugin_tree, libname, plugin, p_node);
+  return plugin;
 }
 
 void
@@ -100,7 +99,7 @@ olsr_init_pluginsystem(void) {
 
   /* could already be initialized */
   if (!plugin_tree_initialized) {
-    avl_init(&plugin_tree, avl_comp_strcasecmp);
+    avl_init(&plugin_tree, avl_comp_strcasecmp, false, NULL);
     plugin_tree_initialized = true;
   }
 }
@@ -138,9 +137,10 @@ void olsr_plugins_init(bool fail_fast) {
 
 void olsr_plugins_enable(enum plugin_type type, bool fail_fast) {
   struct olsr_plugin *plugin;
+  struct list_iterator iterator;
 
   /* activate all plugins (configured and static linked ones) */
-  OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin) {
+  OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin, iterator) {
     if ((type != PLUGIN_TYPE_ALL && type != plugin->type) || plugin->internal_active) {
       continue;
     }
@@ -152,18 +152,18 @@ void olsr_plugins_enable(enum plugin_type type, bool fail_fast) {
       }
       OLSR_WARN(LOG_PLUGINS, "Error, cannot activate plugin %s.\n", plugin->name);
     }
-  } OLSR_FOR_ALL_PLUGIN_ENTRIES_END(plugin)
+  }
   OLSR_INFO(LOG_PLUGINS, "All plugins loaded.\n");
 }
 
 void
 olsr_destroy_pluginsystem(void) {
   struct olsr_plugin *plugin;
-
-  OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin) {
+  struct list_iterator iterator;
+  OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin, iterator) {
     olsr_disable_plugin(plugin);
     olsr_internal_unload_plugin(plugin, true);
-  } OLSR_FOR_ALL_PLUGIN_ENTRIES_END(plugin)
+  }
 }
 
 static struct olsr_plugin *
@@ -220,7 +220,7 @@ olsr_load_legacy_plugin(const char *libname, void *dlhandle) {
   /* get parameters */
   get_plugin_parameters(&plugin->internal_param, &plugin->internal_param_cnt);
 
-  avl_insert(&plugin_tree, &plugin->p_node, false);
+  avl_insert(&plugin_tree, &plugin->p_node);
   return plugin;
 }
 
index bab84c4..d430f74 100644 (file)
@@ -111,9 +111,7 @@ struct olsr_plugin {
   bool internal_active;
 };
 
-AVLNODE2STRUCT(plugin_node2tree, olsr_plugin, p_node)
-#define OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin) OLSR_FOR_ALL_AVL_ENTRIES(&plugin_tree, plugin_node2tree, plugin)
-#define OLSR_FOR_ALL_PLUGIN_ENTRIES_END(plugin) OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_PLUGIN_ENTRIES(plugin, iterator) avl_for_each_element_safe(&plugin_tree, plugin, p_node, iterator.loop, iterator.safe)
 
 struct olsr_plugin *EXPORT(olsr_get_plugin)(const char *libname);
 
index 7f06196..e078d0a 100644 (file)
@@ -265,17 +265,9 @@ static void
 olsr_delete_outdated_routes(struct rt_entry *rt)
 {
   struct rt_path *rtp;
-  struct avl_node *rtp_tree_node, *next_rtp_tree_node;
-
-  for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
-
-    /*
-     * pre-fetch the next node before loosing context.
-     */
-    next_rtp_tree_node = avl_walk_next(rtp_tree_node);
-
-    rtp = rtp_tree2rtp(rtp_tree_node);
+  struct list_iterator iterator;
 
+  OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) {
     /*
      * check the version number which gets incremented on every SPF run.
      * comparing for unequalness avoids handling version number wraps.
@@ -283,7 +275,7 @@ olsr_delete_outdated_routes(struct rt_entry *rt)
     if (routingtree_version != rtp->rtp_version) {
 
       /* remove from the originator tree */
-      avl_delete(&rt->rt_path_tree, rtp_tree_node);
+      avl_delete(&rt->rt_path_tree, &rtp->rtp_tree_node);
       rtp->rtp_rt = NULL;
     }
   }
@@ -302,12 +294,13 @@ void
 olsr_update_rib_routes(void)
 {
   struct rt_entry *rt;
+  struct list_iterator iterator;
 
   OLSR_DEBUG(LOG_ROUTING, "Updating kernel routes...\n");
 
   /* walk all routes in the RIB. */
 
-  OLSR_FOR_ALL_RT_ENTRIES(rt) {
+  OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
 
     /* eliminate first unused routes */
     olsr_delete_outdated_routes(rt);
@@ -339,7 +332,6 @@ olsr_update_rib_routes(void)
       }
     }
   }
-  OLSR_FOR_ALL_RT_ENTRIES_END();
 }
 
 /**
@@ -358,7 +350,7 @@ olsr_update_kernel_routes(void)
   /* route additions */
   olsr_add_routes(&add_kernel_list);
 #ifdef DEBUG
-  olsr_print_routing_table(&routingtree);
+  olsr_print_routing_table();
 #endif
 }
 
index 9521c26..54ea903 100644 (file)
@@ -264,7 +264,7 @@ olsr_init_routing_table(void)
   OLSR_INFO(LOG_ROUTING, "RIB: initialize routing tree...\n");
 
   /* the routing tree */
-  avl_init(&routingtree, avl_comp_prefix_default);
+  avl_init(&routingtree, avl_comp_prefix_default, false, NULL);
   routingtree_version = 0;
 
   /*
@@ -288,15 +288,14 @@ olsr_init_routing_table(void)
 struct rt_entry *
 olsr_lookup_routing_table(const union olsr_ip_addr *dst)
 {
-  struct avl_node *rt_tree_node;
+  struct rt_entry *rt;
   struct olsr_ip_prefix prefix;
 
   prefix.prefix = *dst;
   prefix.prefix_len = 8 * olsr_cnf->ipsize;
 
-  rt_tree_node = avl_find(&routingtree, &prefix);
-
-  return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
+  rt = avl_find_element(&routingtree, &prefix, rt, rt_tree_node);
+  return rt;
 }
 
 /**
@@ -343,10 +342,10 @@ olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
   rt->rt_dst = *prefix;
 
   rt->rt_tree_node.key = &rt->rt_dst;
-  avl_insert(&routingtree, &rt->rt_tree_node, false);
+  avl_insert(&routingtree, &rt->rt_tree_node);
 
   /* init the originator subtree */
-  avl_init(&rt->rt_path_tree, avl_comp_addr_origin_default);
+  avl_init(&rt->rt_path_tree, avl_comp_addr_origin_default, false, NULL);
 
   return rt;
 }
@@ -372,7 +371,7 @@ olsr_alloc_rt_path(struct tc_entry *tc, struct olsr_ip_prefix *prefix, uint8_t o
   rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
 
   /* insert to the tc prefix tree */
-  avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, false);
+  avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node);
 
   /* backlink to the owning tc entry */
   rtp->rtp_tc = tc;
@@ -402,7 +401,6 @@ void
 olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
 {
   struct rt_entry *rt;
-  struct avl_node *node;
 
   /*
    * no unreachable routes please.
@@ -421,26 +419,21 @@ olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry
   /*
    * first check if there is a route_entry for the prefix.
    */
-  node = avl_find(&routingtree, &rtp->rtp_dst);
-
-  if (!node) {
+  rt = avl_find_element(&routingtree, &rtp->rtp_dst, rt, rt_tree_node);
 
+  if (!rt) {
     /* no route entry yet */
     rt = olsr_alloc_rt_entry(&rtp->rtp_dst);
-
     if (!rt) {
       return;
     }
-
-  } else {
-    rt = rt_tree2rt(node);
   }
 
   /*
    * Insert to the route entry originator tree
    * The key has been initialized in olsr_alloc_rt_path().
    */
-  avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, false);
+  avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node);
 
   /* backlink to the owning route entry */
   rtp->rtp_rt = rt;
@@ -566,16 +559,13 @@ void
 olsr_rt_best(struct rt_entry *rt)
 {
   /* grab the first entry */
-  struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
-
-  assert(node != NULL);         /* should not happen */
+  struct rt_path *rtp, *best;
+  struct list_iterator iterator;
 
-  rt->rt_best = rtp_tree2rtp(node);
-
-  /* walk all remaining originator entries */
-  while ((node = avl_walk_next(node))) {
-    struct rt_path *rtp = rtp_tree2rtp(node);
+  assert (!avl_is_empty(&rt->rt_path_tree));
 
+  best = NULL;
+  OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) {
     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
       rt->rt_best = rtp;
     }
@@ -608,7 +598,6 @@ olsr_insert_routing_table(const union olsr_ip_addr *dst, int plen, const union o
 #endif
   struct tc_entry *tc;
   struct rt_path *rtp;
-  struct avl_node *node;
   struct olsr_ip_prefix prefix;
 
   /*
@@ -632,9 +621,9 @@ olsr_insert_routing_table(const union olsr_ip_addr *dst, int plen, const union o
   prefix.prefix_len = plen;
   prefix.prefix_origin = origin;
 
-  node = avl_find(&tc->prefix_tree, &prefix);
+  rtp = avl_find_element(&tc->prefix_tree, &prefix, rtp, rtp_prefix_tree_node);
 
-  if (!node) {
+  if (!rtp) {
 
     /* no rt_path for this prefix yet */
     rtp = olsr_alloc_rt_path(tc, &prefix, origin);
@@ -648,9 +637,6 @@ olsr_insert_routing_table(const union olsr_ip_addr *dst, int plen, const union o
 
     /* overload the hna change bit for flagging a prefix change */
     changes_hna = true;
-
-  } else {
-    rtp = rtp_prefix_tree2rtp(node);
   }
 
   return rtp;
@@ -668,7 +654,6 @@ olsr_delete_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr
 
   struct tc_entry *tc;
   struct rt_path *rtp;
-  struct avl_node *node;
   struct olsr_ip_prefix prefix;
 
   /*
@@ -690,10 +675,8 @@ olsr_delete_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr
   prefix.prefix_len = plen;
   prefix.prefix_origin = origin;
 
-  node = avl_find(&tc->prefix_tree, &prefix);
-
-  if (node) {
-    rtp = rtp_prefix_tree2rtp(node);
+  rtp = avl_find_element(&tc->prefix_tree, &prefix, rtp, rtp_prefix_tree_node);
+  if (rtp) {
     olsr_delete_rt_path(rtp);
 
     OLSR_DEBUG(LOG_ROUTING, "RIB: del prefix %s/%d from %s\n",
@@ -752,20 +735,21 @@ olsr_rtp_to_string(const struct rt_path *rtp)
  *
  */
 void
-olsr_print_routing_table(struct avl_tree *tree __attribute__ ((unused)))
+olsr_print_routing_table(void)
 {
   /* The whole function makes no sense without it. */
 #if !defined REMOVE_LOG_INFO
-  struct avl_node *rt_tree_node;
+  struct rt_entry *rt;
+  struct rt_path *rtp;
+
   char lqbuffer[LQTEXT_MAXLENGTH];
+  struct list_iterator iterator, iterator2;
 
   OLSR_INFO(LOG_ROUTING, "ROUTING TABLE\n");
 
-  for (rt_tree_node = avl_walk_first(tree); rt_tree_node != NULL; rt_tree_node = avl_walk_next(rt_tree_node)) {
-    struct avl_node *rtp_tree_node;
+  OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
     struct ipaddr_str origstr, gwstr;
     struct ipprefix_str prefixstr;
-    struct rt_entry *rt = rt_tree2rt(rt_tree_node);
 
     /* first the route entry */
     OLSR_INFO_NH(LOG_ROUTING, "%s, via %s dev %s, best-originator %s\n",
@@ -775,8 +759,7 @@ olsr_print_routing_table(struct avl_tree *tree __attribute__ ((unused)))
                  olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator.prefix));
 
     /* walk the per-originator path tree of routes */
-    for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = avl_walk_next(rtp_tree_node)) {
-      struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
+    OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator2) {
       OLSR_INFO_NH(LOG_ROUTING, "\tfrom %s, cost %s, metric %u, via %s, dev %s, v %u\n",
                    olsr_ip_to_string(&origstr, &rtp->rtp_originator.prefix),
                    olsr_get_linkcost_text(rtp->rtp_metric.cost, true, lqbuffer, sizeof(lqbuffer)),
index 11a8ba1..4095241 100644 (file)
@@ -113,8 +113,7 @@ struct rt_path {
   uint32_t rtp_version;                /* for detection of outdated rt_paths */
 };
 
-AVLNODE2STRUCT(rtp_tree2rtp, rt_path, rtp_tree_node);
-AVLNODE2STRUCT(rtp_prefix_tree2rtp, rt_path, rtp_prefix_tree_node);
+#define OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) avl_for_each_element_safe(&rt->rt_path_tree, rtp, rtp_tree_node, iterator.loop, iterator.safe)
 
 /*
  * Different routes types used in olsrd.
@@ -139,10 +138,7 @@ enum olsr_rt_origin {
  * the loop prefetches the next node in order to not loose context if
  * for example the caller wants to delete the current rt_entry.
  */
-AVLNODE2STRUCT(rt_tree2rt, rt_entry, rt_tree_node);
-#define OLSR_FOR_ALL_RT_ENTRIES(rt) OLSR_FOR_ALL_AVL_ENTRIES(&routingtree, rt_tree2rt, rt)
-#define OLSR_FOR_ALL_RT_ENTRIES_END(rt) OLSR_FOR_ALL_AVL_ENTRIES_END()
-
+#define OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) avl_for_each_element_safe(&routingtree, rt, rt_tree_node, iterator.loop, iterator.safe)
 
 /**
  * IPv4 <-> IPv6 wrapper
@@ -229,7 +225,7 @@ olsr_fib_metric(const struct rt_metric *met)
 
 char *olsr_rt_to_string(const struct rt_entry *);
 char *olsr_rtp_to_string(const struct rt_path *);
-void olsr_print_routing_table(struct avl_tree *);
+void olsr_print_routing_table(void);
 
 /**
  * depending on the operation (add/chg/del) the nexthop
index 2b21927..215a72b 100644 (file)
@@ -106,15 +106,15 @@ olsr_add_tc_entry(const union olsr_ip_addr *adr)
   /*
    * Insert into the global tc tree.
    */
-  avl_insert(&tc_tree, &tc->vertex_node, false);
+  avl_insert(&tc_tree, &tc->vertex_node);
 
   /*
    * Initialize subtrees for edges, prefixes, HNAs and MIDs.
    */
-  avl_init(&tc->edge_tree, avl_comp_default);
-  avl_init(&tc->prefix_tree, avl_comp_prefix_origin_default);
-  avl_init(&tc->mid_tree, avl_comp_default);
-  avl_init(&tc->hna_tree, avl_comp_prefix_default);
+  avl_init(&tc->edge_tree, avl_comp_default, true, NULL);
+  avl_init(&tc->prefix_tree, avl_comp_prefix_origin_default, false, NULL);
+  avl_init(&tc->mid_tree, avl_comp_default, false, NULL);
+  avl_init(&tc->hna_tree, avl_comp_prefix_default, false, NULL);
 
   /*
    * Add a rt_path for ourselves.
@@ -133,7 +133,7 @@ olsr_init_tc(void)
 {
   OLSR_INFO(LOG_TC, "Initialize topology set...\n");
 
-  avl_init(&tc_tree, avl_comp_default);
+  avl_init(&tc_tree, avl_comp_default, false, NULL);
 
   /*
    * Get some cookies for getting stats to ease troubleshooting.
@@ -154,6 +154,7 @@ void
 olsr_change_myself_tc(void)
 {
   struct nbr_entry *entry;
+  struct list_iterator iterator;
   bool main_ip_change = false;
 
   if (tc_myself) {
@@ -166,14 +167,14 @@ olsr_change_myself_tc(void)
     }
 
     /* flush local edges */
-    OLSR_FOR_ALL_NBR_ENTRIES(entry) {
+    OLSR_FOR_ALL_NBR_ENTRIES(entry, iterator) {
       if (entry->tc_edge) {
         /* clean up local edges if necessary */
         entry->tc_edge->neighbor = NULL;
         olsr_delete_tc_edge_entry(entry->tc_edge);
         entry->tc_edge = NULL;
       }
-    } OLSR_FOR_ALL_NBR_ENTRIES_END()
+    }
 
     /*
      * Flush our own tc_entry.
@@ -194,7 +195,7 @@ olsr_change_myself_tc(void)
   tc_myself = olsr_add_tc_entry(&olsr_cnf->router_id);
 
   if (main_ip_change) {
-    OLSR_FOR_ALL_NBR_ENTRIES(entry) {
+    OLSR_FOR_ALL_NBR_ENTRIES(entry, iterator) {
     /**
      * check if a main ip change destroyed our TC entries
      */
@@ -202,7 +203,7 @@ olsr_change_myself_tc(void)
         entry->tc_edge = olsr_add_tc_edge_entry(tc_myself, &entry->nbr_addr, 0);
         entry->tc_edge->neighbor = entry;
       }
-    } OLSR_FOR_ALL_NBR_ENTRIES_END()
+    }
   }
   changes_topology = true;
 }
@@ -219,6 +220,7 @@ olsr_delete_tc_entry(struct tc_entry *tc)
 {
   struct tc_edge_entry *tc_edge;
   struct rt_path *rtp;
+  struct list_iterator iterator;
 
 #if !defined REMOVE_LOG_DEBUG
   struct ipaddr_str buf;
@@ -226,9 +228,9 @@ olsr_delete_tc_entry(struct tc_entry *tc)
   OLSR_DEBUG(LOG_TC, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
 
   /* The delete all non-virtual edges */
-  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) {
     olsr_delete_tc_edge_entry(tc_edge);
-  } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
+  }
 
   /* Stop running timers */
   olsr_stop_timer(tc->validity_timer);
@@ -244,9 +246,9 @@ olsr_delete_tc_entry(struct tc_entry *tc)
     return;
   }
 
-  OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
+  OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp, iterator) {
     olsr_delete_rt_path(rtp);
-  } OLSR_FOR_ALL_PREFIX_ENTRIES_END();
+  }
 
   /* Flush all MID aliases and kill the MID timer */
   olsr_flush_mid_entries(tc);
@@ -267,10 +269,10 @@ olsr_delete_tc_entry(struct tc_entry *tc)
 struct tc_entry *
 olsr_lookup_tc_entry(const union olsr_ip_addr *adr)
 {
-  struct avl_node *node;
+  struct tc_entry *tc;
 
-  node = avl_find(&tc_tree, adr);
-  return node ? vertex_tree2tc(node) : NULL;
+  tc = avl_find_element(&tc_tree, adr, tc, vertex_node);
+  return tc;
 }
 
 /*
@@ -379,7 +381,7 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, const union olsr_ip_addr *addr, uint
    * However we need duplicate key support for the case of local
    * parallel links where we add one tc_edge per link_entry.
    */
-  avl_insert(&tc->edge_tree, &tc_edge->edge_node, true);
+  avl_insert(&tc->edge_tree, &tc_edge->edge_node);
 
   /*
    * Connect backpointer.
@@ -498,17 +500,17 @@ static bool
 delete_outdated_tc_edges(struct tc_entry *tc)
 {
   struct tc_edge_entry *tc_edge;
+  struct list_iterator iterator;
   bool retval = false;
 
   OLSR_DEBUG(LOG_TC, "TC: deleting outdated TC-edge entries\n");
 
-  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) {
     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
       olsr_delete_tc_edge_entry(tc_edge);
       retval = true;
     }
   }
-  OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
 
   if (retval)
     changes_topology = true;
@@ -527,14 +529,15 @@ static int
 olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_addr *lower_border, union olsr_ip_addr *upper_border)
 {
   struct tc_edge_entry *tc_edge;
+  struct list_iterator iterator;
   int retval = 0;
   bool passedLowerBorder = false;
 
   OLSR_DEBUG(LOG_TC, "TC: deleting revoked TCs\n");
 
-  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+  OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) {
     if (!passedLowerBorder) {
-      if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
+      if (avl_comp_default(lower_border, &tc_edge->T_dest_addr, NULL) <= 0) {
         passedLowerBorder = true;
       } else {
         continue;
@@ -542,7 +545,7 @@ olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_a
     }
 
     if (passedLowerBorder) {
-      if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
+      if (avl_comp_default(upper_border, &tc_edge->T_dest_addr, NULL) <= 0) {
         break;
       }
     }
@@ -552,7 +555,6 @@ olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_a
       retval = 1;
     }
   }
-  OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
 
   if (retval)
     changes_topology = true;
@@ -633,11 +635,10 @@ olsr_tc_update_edge(struct tc_entry *tc, uint16_t ansn, const unsigned char **cu
 struct tc_edge_entry *
 olsr_lookup_tc_edge(struct tc_entry *tc, const union olsr_ip_addr *edge_addr)
 {
-  struct avl_node *edge_node;
-
-  edge_node = avl_find(&tc->edge_tree, edge_addr);
+  struct tc_edge_entry *edge;
 
-  return edge_node ? edge_tree2tc_edge(edge_node) : NULL;
+  edge = avl_find_element(&tc->edge_tree, edge_addr, edge, edge_node);
+  return edge;
 }
 
 /**
@@ -649,6 +650,7 @@ olsr_print_tc_table(void)
 #if !defined REMOVE_LOG_INFO
   /* The whole function makes no sense without it. */
   struct tc_entry *tc;
+  struct list_iterator iterator, iterator2;
   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
   static char NONE[] = "-";
 
@@ -656,7 +658,7 @@ olsr_print_tc_table(void)
   OLSR_INFO_NH(LOG_TC, "%-*s %-*s %-7s      %8s %12s %5s\n", ipwidth,
                "Source IP addr", ipwidth, "Dest IP addr", "", olsr_get_linklabel(0), "vtime", "ansn");
 
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     struct tc_edge_entry *tc_edge;
     struct millitxt_buf tbuf;
     char *vtime = NONE;
@@ -666,7 +668,7 @@ olsr_print_tc_table(void)
       vtime = tbuf.buf;
     }
 
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator2) {
       struct ipaddr_str addrbuf, dstaddrbuf;
       char lqbuffer1[LQTEXT_MAXLENGTH];
 
@@ -678,8 +680,8 @@ olsr_print_tc_table(void)
                    olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer1, sizeof(lqbuffer1)),
                    vtime, tc_edge->ansn);
 
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
-  } OLSR_FOR_ALL_TC_ENTRIES_END();
+    }
+  }
 #endif
 }
 
@@ -866,10 +868,11 @@ void
 olsr_delete_all_tc_entries(void) {
   struct tc_entry *tc;
   struct tc_edge_entry *edge;
+  struct list_iterator iterator, iterator2;
 
   /* delete tc_edges */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, edge) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
+    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, edge, iterator2) {
       if (edge->neighbor) {
         /* break connector with neighbor */
         edge->neighbor->tc_edge = NULL;
@@ -877,13 +880,13 @@ olsr_delete_all_tc_entries(void) {
       }
       edge->edge_inv = NULL;
       internal_delete_tc_edge_entry(edge);
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END()
-  } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
+    }
+  }
 
   /* delete tc_entries */
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
+  OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) {
     olsr_delete_tc_entry(tc);
-  } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
+  }
 
   /* kill tc_myself */
   tc_myself = NULL;
@@ -936,6 +939,7 @@ olsr_output_lq_tc_internal(void *ctx  __attribute__ ((unused)), union olsr_ip_ad
   struct list_iterator iterator;
   struct nbr_entry *nbr;
   struct link_entry *link;
+  struct nbr_entry *prevNbr;
   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
   uint8_t *curr = msg_buffer;
   uint8_t *length_field, *border_flags, *seqno, *last;
@@ -978,24 +982,23 @@ olsr_output_lq_tc_internal(void *ctx  __attribute__ ((unused)), union olsr_ip_ad
 
   last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize - olsr_sizeof_TCLQ();
 
-  OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
+  OLSR_FOR_ALL_NBR_ENTRIES(nbr, iterator) {
     /* allow fragmentation */
     if (skip) {
-      struct nbr_entry *prevNbr;
       if (olsr_ipcmp(&nbr->nbr_addr, nextIp) != 0) {
         continue;
       }
       skip = false;
 
       /* rewrite lower border flag */
-      prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
+      prevNbr = avl_prev_element(nbr, nbr_node);
       *border_flags = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
     }
 
     /* too long ? */
     if (curr > last) {
       /* rewrite upper border flag */
-      struct nbr_entry *prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
+      prevNbr = avl_prev_element(nbr, nbr_node);
 
       *(border_flags+1) = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
       *nextIp = nbr->nbr_addr;
@@ -1046,7 +1049,7 @@ olsr_output_lq_tc_internal(void *ctx  __attribute__ ((unused)), union olsr_ip_ad
     olsr_serialize_tc_lq(&curr, link);
 
     sendTC = true;
-  } OLSR_FOR_ALL_NBR_ENTRIES_END()
+  }
 
   if (!sendTC && skip) {
     OLSR_DEBUG(LOG_TC, "Nothing to send for this TC...\n");
index 0be60c6..d2c7a34 100644 (file)
@@ -99,9 +99,6 @@ struct tc_entry {
 
 #define OLSR_TC_VTIME_JITTER 5 /* percent */
 
-
-AVLNODE2STRUCT(cand_tree2tc, tc_entry, cand_tree_node);
-
 /*
  * macros for traversing vertices, edges and prefixes in the link state database.
  * it is recommended to use this because it hides all the internal
@@ -110,16 +107,9 @@ AVLNODE2STRUCT(cand_tree2tc, tc_entry, cand_tree_node);
  * the loop prefetches the next node in order to not loose context if
  * for example the caller wants to delete the current entry.
  */
-AVLNODE2STRUCT(vertex_tree2tc, tc_entry, vertex_node);
-#define OLSR_FOR_ALL_TC_ENTRIES(tc) OLSR_FOR_ALL_AVL_ENTRIES(&tc_tree, vertex_tree2tc, tc)
-#define OLSR_FOR_ALL_TC_ENTRIES_END(tc) OLSR_FOR_ALL_AVL_ENTRIES_END()
-
-AVLNODE2STRUCT(edge_tree2tc_edge, tc_edge_entry, edge_node);
-#define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) OLSR_FOR_ALL_AVL_ENTRIES(&tc->edge_tree, edge_tree2tc_edge, tc_edge)
-#define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
-
-#define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) OLSR_FOR_ALL_AVL_ENTRIES(&tc->prefix_tree, rtp_prefix_tree2rtp, rtp)
-#define OLSR_FOR_ALL_PREFIX_ENTRIES_END() OLSR_FOR_ALL_AVL_ENTRIES_END()
+#define OLSR_FOR_ALL_TC_ENTRIES(tc, iterator) avl_for_each_element_safe(&tc_tree, tc, vertex_node, iterator.loop, iterator.safe)
+#define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge, iterator) avl_for_each_element_safe(&tc->edge_tree, tc_edge, edge_node, iterator.loop, iterator.safe)
+#define OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp, iterator) avl_for_each_element_safe(&tc->prefix_tree, rtp, rtp_prefix_tree_node, iterator.loop, iterator.safe)
 
 extern struct avl_tree EXPORT(tc_tree);
 extern struct tc_entry *tc_myself;