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

[Thomas Lopatic]

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

Modified Files:
	lq_avl.c lq_avl.h 
Log Message:
AVL tree walk functions.


Index: lq_avl.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** lq_avl.h	25 Mar 2007 23:19:44 -0000	1.5
--- lq_avl.h	27 Mar 2007 00:45:15 -0000	1.6
***************
*** 50,53 ****
--- 50,54 ----
    struct avl_node *left;
    struct avl_node *right;
+   struct avl_node *next;
    void *key;
    void *data;
***************
*** 64,67 ****
--- 65,70 ----
  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 *);
  
  #define inline_avl_comp_ipv4(ip1, ip2) \

Index: lq_avl.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_avl.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** lq_avl.c	25 Mar 2007 23:19:44 -0000	1.4
--- lq_avl.c	27 Mar 2007 00:45:15 -0000	1.5
***************
*** 55,81 ****
  }
  
! static struct avl_node *avl_find_rec_ipv4(struct avl_node *node, void *key)
  {
!   if (*(unsigned int *)key < *(unsigned int *)node->key) {
!     if (node->left != NULL) {
!       return avl_find_rec_ipv4(node->left, key);
!     }
    }
!   else if (*(unsigned int *)key > *(unsigned int *)node->key) {
!     if (node->right != NULL) {
!       return avl_find_rec_ipv4(node->right, key);
!     }
    }
    return node;
  }
  
! static struct avl_node *avl_find_rec(struct avl_node *node, void *key,
!                                      int (*comp)(void *, void *))
  {
    int diff;
  
!   if (0 == comp) {
!     return avl_find_rec_ipv4(node, key);
!   }
  
    diff = (*comp)(key, node->key);
--- 55,82 ----
  }
  
! static struct avl_node *find_rec_ipv4(struct avl_node *node, void *key)
  {
!   if (*(unsigned int *)key < *(unsigned int *)node->key)
!   {
!     if (node->left != NULL)
!       return find_rec_ipv4(node->left, key);
    }
! 
!   else if (*(unsigned int *)key > *(unsigned int *)node->key)
!   {
!     if (node->right != NULL)
!       return find_rec_ipv4(node->right, key);
    }
+ 
    return node;
  }
  
! static struct avl_node *find_rec(struct avl_node *node, void *key,
!                                  int (*comp)(void *, void *))
  {
    int diff;
  
!   if (0 == comp)
!     return find_rec_ipv4(node, key);
  
    diff = (*comp)(key, node->key);
***************
*** 84,88 ****
    {
      if (node->left != NULL)
!       return avl_find_rec(node->left, key, comp);
  
      return node;
--- 85,89 ----
    {
      if (node->left != NULL)
!       return find_rec(node->left, key, comp);
  
      return node;
***************
*** 92,96 ****
    {
      if (node->right != NULL)
!       return avl_find_rec(node->right, key, comp);
  
      return node;
--- 93,97 ----
    {
      if (node->right != NULL)
!       return find_rec(node->right, key, comp);
  
      return node;
***************
*** 107,117 ****
      return NULL;
  
!   node = avl_find_rec(tree->root, key, tree->comp);
  
!   if (0 == tree->comp) {
      if (0 != inline_avl_comp_ipv4(node->key, key))
        return NULL;
    }
!   else {
      if ((*tree->comp)(node->key, key) != 0)
        return NULL;
--- 108,121 ----
      return NULL;
  
!   node = find_rec(tree->root, key, tree->comp);
  
!   if (0 == tree->comp)
!   {
      if (0 != inline_avl_comp_ipv4(node->key, key))
        return NULL;
    }
! 
!   else
!   {
      if ((*tree->comp)(node->key, key) != 0)
        return NULL;
***************
*** 254,268 ****
    }
  
!   node = avl_find_rec(tree->root, new->key, tree->comp);
  
    if (0 == tree->comp)
-   {
      diff = inline_avl_comp_ipv4(new->key, node->key);
-   }
  
    else
-   {
      diff = (*tree->comp)(new->key, node->key);
-   }
  
    if (diff == 0)
--- 258,268 ----
    }
  
!   node = find_rec(tree->root, new->key, tree->comp);
  
    if (0 == tree->comp)
      diff = inline_avl_comp_ipv4(new->key, node->key);
  
    else
      diff = (*tree->comp)(new->key, node->key);
  
    if (diff == 0)
***************
*** 544,545 ****
--- 544,580 ----
  }
  
+ 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;
+ 
+   if (node == NULL)
+     return NULL;
+ 
+   walk_init_rec(node, NULL);
+ 
+   return local_min(node);
+ }
+ 
+ struct avl_node *avl_walk_next(struct avl_node *node)
+ {
+   return node->next;
+ }