Use AVL trees for vertex and edge lookup.
authorThomas Lopatic <thomas@lopatic.de>
Sat, 22 Jan 2005 14:30:57 +0000 (14:30 +0000)
committerThomas Lopatic <thomas@lopatic.de>
Sat, 22 Jan 2005 14:30:57 +0000 (14:30 +0000)
src/lq_avl.c [new file with mode: 0755]
src/lq_avl.h [new file with mode: 0755]
src/lq_route.c

diff --git a/src/lq_avl.c b/src/lq_avl.c
new file mode 100755 (executable)
index 0000000..0f01c48
--- /dev/null
@@ -0,0 +1,266 @@
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * 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 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.
+ *
+ * $Id: lq_avl.c,v 1.1 2005/01/22 14:30:57 tlopatic Exp $
+ */
+
+#include <stddef.h>
+
+#include "lq_avl.h"
+
+#define AVLMAX(x, y) ((x > y) ? x : y)
+#define AVLMIN(x, y) ((x < y) ? x : y)
+
+void avl_init(struct avl_tree *tree, int (*comp)(void *, void *))
+{
+  tree->root = NULL;
+  tree->comp = comp;
+}
+
+static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
+                                     int (*comp)(void *, void *))
+{
+  int diff;
+
+  diff = (*comp)(key, node->key);
+
+  if (diff < 0)
+  {
+    if (node->left != NULL)
+      return avl_find_rec(node->left, key, comp);
+
+    return node;
+  }
+
+  if (diff > 0)
+  {
+    if (node->right != NULL)
+      return avl_find_rec(node->right, key, comp);
+
+    return node;
+  }
+
+  return node;
+}
+
+struct avl_node *avl_find(struct avl_tree *tree, void *key)
+{
+  struct avl_node *node;
+
+  if (tree->root == NULL)
+    return NULL;
+
+  node = avl_find_rec(tree->root, key, tree->comp);
+
+  if ((*tree->comp)(node->key, key) != 0)
+    return NULL;
+
+  return node;
+}
+
+static void rotate_right(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *left, *parent;
+
+  left = node->left;
+  parent = node->parent;
+
+  left->parent = parent;
+  node->parent = left;
+
+  if (parent == NULL)
+    tree->root = left;
+
+  else
+  {
+    if (parent->left == node)
+      parent->left = left;
+
+    else
+      parent->right = left;
+  }
+
+  node->left = left->right;
+  left->right = node;
+
+  if (node->left != NULL)
+    node->left->parent = node;
+
+  node->balance += 1 - AVLMIN(left->balance, 0);
+  left->balance += 1 + AVLMAX(node->balance, 0);
+}
+
+static void rotate_left(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *right, *parent;
+
+  right = node->right;
+  parent = node->parent;
+
+  right->parent = parent;
+  node->parent = right;
+
+  if (parent == NULL)
+    tree->root = right;
+
+  else
+  {
+    if (parent->left == node)
+      parent->left = right;
+
+    else
+      parent->right = right;
+  }
+
+  node->right = right->left;
+  right->left = node;
+
+  if (node->right != NULL)
+    node->right->parent = node;
+
+  node->balance -= 1 + AVLMAX(right->balance, 0);
+  right->balance -= 1 - AVLMIN(node->balance, 0);
+}
+
+static void post_insert(struct avl_tree *tree, struct avl_node *node)
+{
+  struct avl_node *parent;
+
+  if ((parent = node->parent) == NULL)
+    return;
+
+  if (node == parent->left)
+  {
+    parent->balance--;
+
+    if (parent->balance == 0)
+      return;
+
+    if (parent->balance == -1)
+    {
+      post_insert(tree, parent);
+      return;
+    }
+
+    if (node->balance == -1)
+    {
+      rotate_right(tree, parent);
+      return;
+    }
+
+    rotate_left(tree, node);
+    rotate_right(tree, node->parent->parent);
+    return;
+  }
+
+  parent->balance++;
+
+  if (parent->balance == 0)
+    return;
+
+  if (parent->balance == 1)
+  {
+    post_insert(tree, parent);
+    return;
+  }
+
+  if (node->balance == 1)
+  {
+    rotate_left(tree, parent);
+    return;
+  }
+
+  rotate_right(tree, node);
+  rotate_left(tree, node->parent->parent);
+  return;
+}
+
+int avl_insert(struct avl_tree *tree, struct avl_node *new)
+{
+  struct avl_node *node;
+  int diff;
+
+  new->balance = 0;
+  new->left = NULL;
+  new->right = NULL;
+
+  if (tree->root == NULL)
+  {
+    new->parent = NULL;
+    tree->root = new;
+    return 0;
+  }
+
+  node = avl_find_rec(tree->root, new->key, tree->comp);
+
+  diff = (*tree->comp)(new->key, node->key);
+
+  if (diff == 0)
+    return -1;
+
+  if (node->balance == 1)
+  {
+    node->balance = 0;
+    new->parent = node;
+    node->left = new;
+    return 0;
+  }
+  
+  if (node->balance == -1)
+  {
+    node->balance = 0;
+    new->parent = node;
+    node->right = new;
+    return 0;
+  }
+
+  if (diff < 0)
+  {
+    node->balance = -1;
+    new->parent = node;
+    node->left = new;
+    post_insert(tree, node);
+    return 0;
+  }
+
+  node->balance = 1;
+  new->parent = node;
+  node->right = new;
+  post_insert(tree, node);
+  return 0;
+}
diff --git a/src/lq_avl.h b/src/lq_avl.h
new file mode 100755 (executable)
index 0000000..f659bd1
--- /dev/null
@@ -0,0 +1,60 @@
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
+ * 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 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.
+ *
+ * $Id: lq_avl.h,v 1.1 2005/01/22 14:30:57 tlopatic Exp $
+ */
+
+struct avl_node
+{
+  int balance;
+  struct avl_node *parent;
+  struct avl_node *left;
+  struct avl_node *right;
+  void *key;
+  void *data;
+};
+
+struct avl_tree
+{
+  struct avl_node *root;
+  int (*comp)(void *, void *);
+};
+
+void avl_init(struct avl_tree *, int (*)(void *, void *));
+struct avl_node *avl_find(struct avl_tree *, void *);
+int avl_insert(struct avl_tree *, struct avl_node *);
index 351ddff..42edead 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.21 2005/01/22 12:25:25 tlopatic Exp $
+ * $Id: lq_route.c,v 1.22 2005/01/22 14:30:57 tlopatic Exp $
  */
 
 #include "defs.h"
 #include "mid_set.h"
 #include "hna_set.h"
 #include "lq_list.h"
+#include "lq_avl.h"
 #include "lq_route.h"
 
 struct dijk_edge
 {
+  struct avl_node tree_node;
   struct list_node node;
   struct dijk_vertex *dest;
   float etx;
@@ -58,35 +60,30 @@ struct dijk_edge
 
 struct dijk_vertex
 {
+  struct avl_node tree_node;
   struct list_node node;
   union olsr_ip_addr addr;
+  struct avl_tree edge_tree;
   struct list edge_list;
   float path_etx;
   struct dijk_vertex *prev;
   olsr_bool done;
 };
 
-// XXX - bad complexity
+static int avl_comp(void *ip1, void *ip2)
+{
+  return memcmp(ip1, ip2, ipsize);
+}
 
-static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
-                       float path_etx)
+static void add_vertex(struct avl_tree *vertex_tree, struct list *vertex_list,
+                       union olsr_ip_addr *addr, float path_etx)
 {
-  struct list_node *node;
+  struct avl_node *node;
   struct dijk_vertex *vert;
 
   // see whether this destination is already in our list
 
-  node = list_get_head(vertex_list);
-
-  while (node != NULL)
-  {
-    vert = node->data;
-
-    if (COMP_IP(&vert->addr, addr))
-      break;
-
-    node = list_get_next(node);
-  }
+  node = avl_find(vertex_tree, addr);
 
   // if it's not in our list, add it
 
@@ -94,6 +91,9 @@ static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
   {
     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
 
+    vert->tree_node.data = vert;
+    vert->tree_node.key = &vert->addr;
+
     vert->node.data = vert;
 
     COPY_IP(&vert->addr, addr);
@@ -102,82 +102,67 @@ static void add_vertex(struct list *vertex_list, union olsr_ip_addr *addr,
     vert->prev = NULL;
     vert->done = OLSR_FALSE;
 
+    avl_init(&vert->edge_tree, avl_comp);
     list_init(&vert->edge_list);
 
+    avl_insert(vertex_tree, &vert->tree_node);
     list_add_tail(vertex_list, &vert->node);
   }
 }
 
-// XXX - bad complexity
-
-static void add_edge(struct list *vertex_list, union olsr_ip_addr *src,
-                     union olsr_ip_addr *dst, float etx)
+static void add_edge(struct avl_tree *vertex_tree, struct list *vertex_list,
+                     union olsr_ip_addr *src, union olsr_ip_addr *dst,
+                     float etx)
 {
-  struct list_node *node;
-  struct dijk_vertex *vert;
+  struct avl_node *node;
   struct dijk_vertex *svert;
   struct dijk_vertex *dvert;
   struct dijk_edge *edge;
 
-  // source and destination lookup
+  // source lookup
 
-  node = list_get_head(vertex_list);
+  node = avl_find(vertex_tree, src);
 
-  svert = NULL;
-  dvert = NULL;
+  // source vertex does not exist
 
-  while (node != NULL)
-  {
-    vert = node->data;
-
-    if (COMP_IP(&vert->addr, src))
-    {
-      svert = vert;
-
-      if (dvert != NULL)
-        break;
-    }
+  if (node == NULL)
+    return;
 
-    else if (COMP_IP(&vert->addr, dst))
-    {
-      dvert = vert;
+  svert = node->data;
 
-      if (svert != NULL)
-        break;
-    }
+  // destination lookup
 
-    node = list_get_next(node);
-  }
+  node = avl_find(vertex_tree, dst);
 
-  // source or destination vertex does not exist
+  // destination vertex does not exist
 
-  if (svert == NULL || dvert == NULL)
+  if (node == NULL)
     return;
 
-  node = list_get_head(&svert->edge_list);
-
-  while (node != NULL)
-  {
-    edge = node->data;
+  dvert = node->data;
 
-    if (edge->dest == dvert)
-      break;
+  // edge lookup
 
-    node = list_get_next(node);
-  }
+  node = avl_find(&svert->edge_tree, dst);
 
   // edge already exists
 
   if (node != NULL)
     return;
 
+  // add edge
+
   edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge");
 
+  edge->tree_node.data = edge;
+  edge->tree_node.key = &dvert->addr;
+
   edge->node.data = edge;
 
   edge->dest = dvert;
   edge->etx = etx;
 
+  avl_insert(&svert->edge_tree, &edge->tree_node);
   list_add_tail(&svert->edge_list, &edge->node);
 }
 
@@ -294,6 +279,7 @@ static char *etx_to_string(float etx)
 
 void olsr_calculate_lq_routing_table(void)
 {
+  struct avl_tree vertex_tree;
   struct list vertex_list;
   int i;
   struct tc_entry *tcsrc;
@@ -313,11 +299,12 @@ void olsr_calculate_lq_routing_table(void)
 
   // initialize the graph
 
+  avl_init(&vertex_tree, avl_comp);
   list_init(&vertex_list);
 
   // add ourselves to the vertex list
 
-  add_vertex(&vertex_list, &main_addr, 0.0);
+  add_vertex(&vertex_tree, &vertex_list, &main_addr, 0.0);
 
   // add our neighbours
 
@@ -325,7 +312,8 @@ void olsr_calculate_lq_routing_table(void)
     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
          neigh = neigh->next)
       if (neigh->status == SYM)
-        add_vertex(&vertex_list, &neigh->neighbor_main_addr, INFINITE_ETX);
+        add_vertex(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
+                   INFINITE_ETX);
 
   // add remaining vertices
 
@@ -334,13 +322,15 @@ void olsr_calculate_lq_routing_table(void)
     {
       // add source
 
-      add_vertex(&vertex_list, &tcsrc->T_last_addr, INFINITE_ETX);
+      add_vertex(&vertex_tree, &vertex_list, &tcsrc->T_last_addr,
+                 INFINITE_ETX);
 
       // add destinations of this source
 
       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
            tcdst = tcdst->next)
-        add_vertex(&vertex_list, &tcdst->T_dest_addr, INFINITE_ETX);
+        add_vertex(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
+                   INFINITE_ETX);
     }
 
   // add edges to and from our neighbours
@@ -357,11 +347,11 @@ void olsr_calculate_lq_routing_table(void)
           {
             etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
 
-            add_edge(&vertex_list, &main_addr, &neigh->neighbor_main_addr,
-                     etx);
+            add_edge(&vertex_tree, &vertex_list, &main_addr,
+                     &neigh->neighbor_main_addr, etx);
 
-            add_edge(&vertex_list, &neigh->neighbor_main_addr, &main_addr,
-                     etx);
+            add_edge(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
+                     &main_addr, etx);
           }
       }
 
@@ -377,11 +367,11 @@ void olsr_calculate_lq_routing_table(void)
           {
             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
 
-            add_edge(&vertex_list, &tcsrc->T_last_addr, &tcdst->T_dest_addr,
-                     etx);
+            add_edge(&vertex_tree, &vertex_list, &tcsrc->T_last_addr,
+                     &tcdst->T_dest_addr, etx);
 
-            add_edge(&vertex_list, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
-                     etx);
+            add_edge(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
+                     &tcsrc->T_last_addr, etx);
           }
       }