Modify linked list when inserting a node into or removing a node from the
authorThomas Lopatic <thomas@lopatic.de>
Tue, 27 Mar 2007 19:37:13 +0000 (19:37 +0000)
committerThomas Lopatic <thomas@lopatic.de>
Tue, 27 Mar 2007 19:37:13 +0000 (19:37 +0000)
tree.

src/lq_avl.c
src/lq_avl.h

index c92524f..3896c0d 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.5 2007/03/27 00:45:15 tlopatic Exp $
+ * $Id: lq_avl.c,v 1.6 2007/03/27 19:37:13 tlopatic Exp $
  */
 
 #include <stddef.h>
@@ -241,6 +241,37 @@ static void post_insert(struct avl_tree *tree, struct avl_node *node)
   return;
 }
 
+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)
 {
   struct avl_node *node;
@@ -250,6 +281,9 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
   new->left = NULL;
   new->right = NULL;
 
+  new->next = NULL;
+  new->prev = NULL;
+
   if (tree->root == NULL)
   {
     new->parent = NULL;
@@ -270,6 +304,8 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
 
   if (node->balance == 1)
   {
+    insert_before(node, new);
+
     node->balance = 0;
     new->parent = node;
     node->left = new;
@@ -278,6 +314,8 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
   
   if (node->balance == -1)
   {
+    insert_after(node, new);
+
     node->balance = 0;
     new->parent = node;
     node->right = new;
@@ -286,6 +324,8 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
 
   if (diff < 0)
   {
+    insert_before(node, new);
+
     node->balance = -1;
     new->parent = node;
     node->left = new;
@@ -293,6 +333,8 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new)
     return 0;
   }
 
+  insert_after(node, new);
+
   node->balance = 1;
   new->parent = node;
   node->right = new;
@@ -532,6 +574,7 @@ 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);
 
   node->balance = 0xdeadbeef;
 
@@ -543,34 +586,13 @@ void avl_delete(struct avl_tree *tree, struct avl_node *node)
   node->data = (void *)0xdeadbeef;
 }
 
-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 *avl_walk_first(struct avl_tree *tree)
 {
   struct avl_node *node = tree->root;
 
   if (node == NULL)
     return NULL;
 
-  walk_init_rec(node, NULL);
-
   return local_min(node);
 }
 
index a570b98..35abd44 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.6 2007/03/27 00:45:15 tlopatic Exp $
+ * $Id: lq_avl.h,v 1.7 2007/03/27 19:37:13 tlopatic Exp $
  */
 
 #ifndef _LQ_AVL_H
@@ -50,6 +50,7 @@ struct avl_node
   struct avl_node *left;
   struct avl_node *right;
   struct avl_node *next;
+  struct avl_node *prev;
   void *key;
   void *data;
 };
@@ -64,7 +65,7 @@ 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_init(struct avl_tree *);
+struct avl_node *avl_walk_first(struct avl_tree *);
 struct avl_node *avl_walk_next(struct avl_node *);
 
 #define inline_avl_comp_ipv4(ip1, ip2) \