[Olsr-cvs] olsrd-current/src lq_avl.c,1.5,1.6 lq_avl.h,1.6,1.7

[Thomas Lopatic]

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

Modified Files:
	lq_avl.c lq_avl.h 
Log Message:
Modify linked list when inserting a node into or removing a node from the
tree.


Index: lq_avl.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** lq_avl.h	27 Mar 2007 00:45:15 -0000	1.6
--- lq_avl.h	27 Mar 2007 19:37:13 -0000	1.7
***************
*** 51,54 ****
--- 51,55 ----
    struct avl_node *right;
    struct avl_node *next;
+   struct avl_node *prev;
    void *key;
    void *data;
***************
*** 65,69 ****
  int avl_insert(struct avl_tree *, struct avl_node *);
  void avl_delete(struct avl_tree *, struct avl_node *);
! struct avl_node *avl_walk_init(struct avl_tree *);
  struct avl_node *avl_walk_next(struct avl_node *);
  
--- 66,70 ----
  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 *);
  struct avl_node *avl_walk_next(struct avl_node *);
  

Index: lq_avl.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** lq_avl.c	27 Mar 2007 00:45:15 -0000	1.5
--- lq_avl.c	27 Mar 2007 19:37:13 -0000	1.6
***************
*** 242,245 ****
--- 242,276 ----
  }
  
+ static void insert_before(struct avl_node *pos_node, struct avl_node *node)
+ {
+   if (pos_node->prev != NULL)
+     pos_node->prev->next = node;
+ 
+   node->prev = pos_node->prev;
+   node->next = pos_node;
+ 
+   pos_node->prev = node;
+ }
+ 
+ static void insert_after(struct avl_node *pos_node, struct avl_node *node)
+ {
+   if (pos_node->next != NULL)
+     pos_node->next->prev = node;
+ 
+   node->prev = pos_node;
+   node->next = pos_node->next;
+ 
+   pos_node->next = node;
+ }
+ 
+ static void remove(struct avl_node *node)
+ {
+   if (node->prev != NULL)
+     node->prev->next = node->next;
+ 
+   if (node->next != NULL)
+     node->next->prev = node->prev;
+ }
+ 
  int avl_insert(struct avl_tree *tree, struct avl_node *new)
  {
***************
*** 251,254 ****
--- 282,288 ----
    new->right = NULL;
  
+   new->next = NULL;
+   new->prev = NULL;
+ 
    if (tree->root == NULL)
    {
***************
*** 271,274 ****
--- 305,310 ----
    if (node->balance == 1)
    {
+     insert_before(node, new);
+ 
      node->balance = 0;
      new->parent = node;
***************
*** 279,282 ****
--- 315,320 ----
    if (node->balance == -1)
    {
+     insert_after(node, new);
+ 
      node->balance = 0;
      new->parent = node;
***************
*** 287,290 ****
--- 325,330 ----
    if (diff < 0)
    {
+     insert_before(node, new);
+ 
      node->balance = -1;
      new->parent = node;
***************
*** 294,297 ****
--- 334,339 ----
    }
  
+   insert_after(node, new);
+ 
    node->balance = 1;
    new->parent = node;
***************
*** 533,536 ****
--- 575,579 ----
  {
    delete_worker(tree, node);
+   remove(node);
  
    node->balance = 0xdeadbeef;
***************
*** 544,567 ****
  }
  
! static struct avl_node *walk_init_rec(struct avl_node *node, struct avl_node *tail)
! {
!   if (node == NULL)
!     return tail;
! 
!   tail = walk_init_rec(node->left, tail);
! 
!   node->next = NULL;
! 
!   if (tail != NULL)
!     tail->next = node;
! 
!   tail = node;
! 
!   tail = walk_init_rec(node->right, tail);
! 
!   return tail;
! }
! 
! struct avl_node *avl_walk_init(struct avl_tree *tree)
  {
    struct avl_node *node = tree->root;
--- 587,591 ----
  }
  
! struct avl_node *avl_walk_first(struct avl_tree *tree)
  {
    struct avl_node *node = tree->root;
***************
*** 570,575 ****
      return NULL;
  
-   walk_init_rec(node, NULL);
- 
    return local_min(node);
  }
--- 594,597 ----