[Olsr-cvs] olsrd-current/src lq_avl.c, 1.7, 1.8 lq_avl.h, 1.7, 1.8 lq_route.c, 1.44, 1.45

[Thomas Lopatic]

Update of /cvsroot/olsrd/olsrd-current/src
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv23810/src

Modified Files:
	lq_avl.c lq_avl.h lq_route.c 
Log Message:
Support multiple values per key.


Index: lq_route.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.c,v
retrieving revision 1.44
retrieving revision 1.45
diff -C2 -d -r1.44 -r1.45
*** lq_route.c	10 Feb 2007 17:36:51 -0000	1.44
--- lq_route.c	29 Mar 2007 00:05:50 -0000	1.45
***************
*** 109,113 ****
      list_init(&vert->edge_list);
  
!     avl_insert(vertex_tree, &vert->tree_node);
    }
  }
--- 109,113 ----
      list_init(&vert->edge_list);
  
!     avl_insert(vertex_tree, &vert->tree_node, 0);
    }
  }
***************
*** 160,164 ****
      edge->etx = etx;
  
!     avl_insert(&svert->edge_tree, &edge->tree_node);
      list_add_tail(&svert->edge_list, &edge->node);
    }
--- 160,164 ----
      edge->etx = etx;
  
!     avl_insert(&svert->edge_tree, &edge->tree_node, 0);
      list_add_tail(&svert->edge_list, &edge->node);
    }
***************
*** 180,184 ****
      edge->etx = etx;
  
!     avl_insert(&dvert->edge_tree, &edge->tree_node);
      list_add_tail(&dvert->edge_list, &edge->node);
    }
--- 180,184 ----
      edge->etx = etx;
  
!     avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
      list_add_tail(&dvert->edge_list, &edge->node);
    }

Index: lq_avl.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.h,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** lq_avl.h	27 Mar 2007 19:37:13 -0000	1.7
--- lq_avl.h	29 Mar 2007 00:05:50 -0000	1.8
***************
*** 46,50 ****
  struct avl_node
  {
-   int balance;
    struct avl_node *parent;
    struct avl_node *left;
--- 46,49 ----
***************
*** 54,57 ****
--- 53,58 ----
    void *key;
    void *data;
+   char balance;
+   char leader;
  };
  
***************
*** 64,68 ****
  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 *);
  void avl_delete(struct avl_tree *, struct avl_node *);
  struct avl_node *avl_walk_first(struct avl_tree *);
--- 65,69 ----
  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);
  void avl_delete(struct avl_tree *, struct avl_node *);
  struct avl_node *avl_walk_first(struct avl_tree *);

Index: lq_avl.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** lq_avl.c	27 Mar 2007 22:02:22 -0000	1.7
--- lq_avl.c	29 Mar 2007 00:05:50 -0000	1.8
***************
*** 273,282 ****
  }
  
! 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;
--- 273,284 ----
  }
  
! 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->parent = NULL;
! 
    new->left = NULL;
    new->right = NULL;
***************
*** 285,291 ****
    new->prev = NULL;
  
    if (tree->root == NULL)
    {
-     new->parent = NULL;
      tree->root = new;
      return 0;
--- 287,295 ----
    new->prev = NULL;
  
+   new->balance = 0;
+   new->leader = 1;
+ 
    if (tree->root == NULL)
    {
      tree->root = new;
      return 0;
***************
*** 294,297 ****
--- 298,306 ----
    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);
***************
*** 301,305 ****
  
    if (diff == 0)
!     return -1;
  
    if (node->balance == 1)
--- 310,322 ----
  
    if (diff == 0)
!   {
!     if (allow_duplicates == 0)
!       return -1;
! 
!     new->leader = 0;
! 
!     insert_after(last, new);
!     return 0;
!   }
  
    if (node->balance == 1)
***************
*** 315,319 ****
    if (node->balance == -1)
    {
!     insert_after(node, new);
  
      node->balance = 0;
--- 332,336 ----
    if (node->balance == -1)
    {
!     insert_after(last, new);
  
      node->balance = 0;
***************
*** 334,338 ****
    }
  
!   insert_after(node, new);
  
    node->balance = 1;
--- 351,355 ----
    }
  
!   insert_after(last, new);
  
    node->balance = 1;
***************
*** 574,588 ****
  void avl_delete(struct avl_tree *tree, struct avl_node *node)
  {
!   delete_worker(tree, node);
!   remove(node);
  
!   node->balance = 0xdeadbeef;
  
!   node->left = (struct avl_node *)0xdeadbeef;
!   node->right = (struct avl_node *)0xdeadbeef;
  
!   node->key = (void *)0xdeadbeef;
  
!   node->data = (void *)0xdeadbeef;
  }
  
--- 591,640 ----
  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 != 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
!       delete_worker(tree, node);
!   }
! 
!   remove(node);
  }