+@@ -266,6 +276,154 @@
+ }
+
+ // XXX - bad complexity
++#define SVEN_OPT
++#undef SVEN_OPT_DBG
++
++/*
++ * The function extract_best() is most expensive (>50% CPU in profiling).
++ * It is called in two modes: while doing Dijkstra route calculation and
++ * while searching for a direct route/hna. The latter can be optimized
++ * because the stored verices do not change from call to call and it is
++ * more sufficient to have them sorted/popped from a list rather than
++ * searching the complete list by every call. Sven-Ola@gmx.de, 11/2006
++ */
++
++#ifdef SVEN_OPT
++static struct dijk_vertex **etx_cache = 0;
++static int etx_cache_count;
++static int etx_cache_get;
++static int etx_cache_saved = 0;
++
++static int etx_cache_compare(const void *a, const void *b)
++{
++ // Oh jeah. I love this macro assembler :)
++
++ if ((*(struct dijk_vertex **)a)->path_etx > (*(struct dijk_vertex **)b)->path_etx) return 1;
++ if ((*(struct dijk_vertex **)a)->path_etx < (*(struct dijk_vertex **)b)->path_etx) return -1;
++
++ // This is for debugging only: etx==etx then compare pointers
++ // to make it possible to compare to the original search algo.
++ if (*(struct dijk_vertex **)a > *(struct dijk_vertex **)b) return 1;
++ if (*(struct dijk_vertex **)a < *(struct dijk_vertex **)b) return -1;
++
++ return 0;
++}
++
++static struct dijk_vertex *extract_best_route(struct list *vertex_list)
++{
++#ifdef SVEN_OPT_DBG
++ float best_etx = INFINITE_ETX + 1.0;
++#endif
++ struct list_node *node;
++ struct dijk_vertex *vert;
++ struct dijk_vertex *res = NULL;
++
++#ifdef SVEN_OPT_DBG
++ node = list_get_head(vertex_list);
++
++ // loop through all vertices
++
++ while (node != NULL)
++ {
++ vert = node->data;
++
++ // see whether the current vertex is better than what we have
++
++ if (!vert->done && vert->path_etx < best_etx)
++ {
++ best_etx = vert->path_etx;
++ res = vert;
++ }
++ else if (!vert->done && vert->path_etx == best_etx && vert < res)
++ {
++ // Otherwise order is undefined if etx==etx and debug will complain
++ best_etx = vert->path_etx;
++ res = vert;
++ }
++
++ node = list_get_next(node);
++ }
++#endif
++ if (NULL == etx_cache)
++ {
++ int count = 0;
++ node = list_get_head(vertex_list);
++ while (node != NULL)
++ {
++ vert = node->data;
++ if (!vert->done && vert->path_etx < INFINITE_ETX) count++;
++ node = list_get_next(node);
++ }
++ if (0 < count)
++ {
++ etx_cache = olsr_malloc(sizeof(etx_cache[0]) * count, "ETX Cache");
++#ifdef SVEN_OPT_DBG
++ printf("count=%d, Malloc(%d)=%p\n", count, sizeof(etx_cache[0]) * count, etx_cache);
++#endif
++ node = list_get_head(vertex_list);
++ etx_cache_count = 0;
++ etx_cache_get = 0;
++ while (node != NULL)
++ {
++ vert = node->data;
++ if (!vert->done && vert->path_etx < INFINITE_ETX)
++ {
++ etx_cache[etx_cache_count] = vert;
++ etx_cache_count++;
++ }
++ node = list_get_next(node);
++ }
++#ifdef SVEN_OPT_DBG
++ printf("qsort(etx_cache_count=%d)\n", etx_cache_count);
++#endif
++ qsort(etx_cache, etx_cache_count, sizeof(etx_cache[0]), etx_cache_compare);
++#ifdef SVEN_OPT_DBG
++ if (0 < etx_cache_count)
++ {
++ int i = 0;
++ while(i < etx_cache_count && i < 10)
++ {
++ printf("%d: %p=%f\n", i, etx_cache[i], etx_cache[i]->path_etx);
++ i++;
++ }
++ }
++#endif
++ }
++ }
++
++#ifdef SVEN_OPT_DBG
++ if (NULL != etx_cache)
++ {
++ struct dijk_vertex *rescache = NULL;
++ if (etx_cache_get < etx_cache_count)
++ {
++ rescache = etx_cache[etx_cache_get++];
++ }
++ if (res != rescache)
++ {
++ printf("miss: etx_cache_get=%d, res=%p,%f != rescache=%p,%f\n",
++ etx_cache_get, res, (NULL != res ? res->path_etx : -1), rescache, (NULL != rescache ? rescache->path_etx : -1));
++ }
++ else
++ {
++ etx_cache_saved++;
++ }
++ }
++#else
++ if (NULL != etx_cache && etx_cache_get < etx_cache_count)
++ {
++ res = etx_cache[etx_cache_get++];
++ }
++#endif
++
++ // if we've found a vertex, remove it from the set
++
++ if (res != NULL)
++ res->done = OLSR_TRUE;
++
++ return res;
++}
++#endif // SVEN_OPT
+
+ static struct dijk_vertex *extract_best(struct list *vertex_list)
+ {
+@@ -371,7 +529,11 @@