Support multiple values per key.
authorThomas Lopatic <thomas@lopatic.de>
Thu, 29 Mar 2007 00:05:50 +0000 (00:05 +0000)
committerThomas Lopatic <thomas@lopatic.de>
Thu, 29 Mar 2007 00:05:50 +0000 (00:05 +0000)
src/lq_avl.c
src/lq_avl.h
src/lq_route.c

index 6735a3b..4f9d604 100755 (executable)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_avl.c,v 1.7 2007/03/27 22:02:22 tlopatic Exp $
+ * $Id: lq_avl.c,v 1.8 2007/03/29 00:05:50 tlopatic Exp $
  */
 
 #include <stddef.h>
@@ -272,27 +272,36 @@ static void remove(struct avl_node *node)
     node->next->prev = node->prev;
 }
 
-int avl_insert(struct avl_tree *tree, struct avl_node *new)
+int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
 {
   struct avl_node *node;
+  struct avl_node *last;
   int diff;
 
-  new->balance = 0;
+  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)
   {
-    new->parent = NULL;
     tree->root = new;
     return 0;
   }
 
   node = find_rec(tree->root, new->key, tree->comp);
 
+  last = node;
+
+  while (last->next != NULL && last->next->leader == 0)
+    last = last->next;
+
   if (0 == tree->comp)
     diff = inline_avl_comp_ipv4(new->key, node->key);
 
@@ -300,7 +309,15 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
     diff = (*tree->comp)(new->key, node->key);
 
   if (diff == 0)
-    return -1;
+  {
+    if (allow_duplicates == 0)
+      return -1;
+
+    new->leader = 0;
+
+    insert_after(last, new);
+    return 0;
+  }
 
   if (node->balance == 1)
   {
@@ -314,7 +331,7 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
   
   if (node->balance == -1)
   {
-    insert_after(node, new);
+    insert_after(last, new);
 
     node->balance = 0;
     new->parent = node;
@@ -333,7 +350,7 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
     return 0;
   }
 
-  insert_after(node, new);
+  insert_after(last, new);
 
   node->balance = 1;
   new->parent = node;
@@ -573,17 +590,52 @@ static void delete_worker(struct avl_tree *tree, struct avl_node *node)
 
 void avl_delete(struct avl_tree *tree, struct avl_node *node)
 {
-  delete_worker(tree, node);
-  remove(node);
+  struct avl_node *next;
+  struct avl_node *parent;
+  struct avl_node *left;
+  struct avl_node *right;
+
+  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;
 
-  node->balance = 0xdeadbeef;
+        else
+          parent->right = next;
+      }
 
-  node->left = (struct avl_node *)0xdeadbeef;
-  node->right = (struct avl_node *)0xdeadbeef;
+      if (left != NULL)
+        left->parent = next;
 
-  node->key = (void *)0xdeadbeef;
+      if (right != NULL)
+        right->parent = next;
+    }
 
-  node->data = (void *)0xdeadbeef;
+    else
+      delete_worker(tree, node);
+  }
+
+  remove(node);
 }
 
 struct avl_node *avl_walk_first(struct avl_tree *tree)
index 35abd44..0a226c9 100755 (executable)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_avl.h,v 1.7 2007/03/27 19:37:13 tlopatic Exp $
+ * $Id: lq_avl.h,v 1.8 2007/03/29 00:05:50 tlopatic Exp $
  */
 
 #ifndef _LQ_AVL_H
@@ -45,7 +45,6 @@
 
 struct avl_node
 {
-  int balance;
   struct avl_node *parent;
   struct avl_node *left;
   struct avl_node *right;
@@ -53,6 +52,8 @@ struct avl_node
   struct avl_node *prev;
   void *key;
   void *data;
+  char balance;
+  char leader;
 };
 
 struct avl_tree
@@ -63,7 +64,7 @@ struct avl_tree
 
 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 *);
+int avl_insert(struct avl_tree *, struct avl_node *, int);
 void avl_delete(struct avl_tree *, struct avl_node *);
 struct avl_node *avl_walk_first(struct avl_tree *);
 struct avl_node *avl_walk_next(struct avl_node *);
index 5ef9080..506e584 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.44 2007/02/10 17:36:51 bernd67 Exp $
+ * $Id: lq_route.c,v 1.45 2007/03/29 00:05:50 tlopatic Exp $
  */
 
 #include "defs.h"
@@ -108,7 +108,7 @@ static void add_vertex(struct avl_tree *vertex_tree, union olsr_ip_addr *addr,
     avl_init(&vert->edge_tree, avl_comp);
     list_init(&vert->edge_list);
 
-    avl_insert(vertex_tree, &vert->tree_node);
+    avl_insert(vertex_tree, &vert->tree_node, 0);
   }
 }
 
@@ -159,7 +159,7 @@ static void add_edge(struct avl_tree *vertex_tree,
     edge->dest = dvert;
     edge->etx = etx;
 
-    avl_insert(&svert->edge_tree, &edge->tree_node);
+    avl_insert(&svert->edge_tree, &edge->tree_node, 0);
     list_add_tail(&svert->edge_list, &edge->node);
   }
 
@@ -179,7 +179,7 @@ static void add_edge(struct avl_tree *vertex_tree,
     edge->dest = svert;
     edge->etx = etx;
 
-    avl_insert(&dvert->edge_tree, &edge->tree_node);
+    avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
     list_add_tail(&dvert->edge_list, &edge->node);
   }
 }