Changes in kernel/generic/src/adt/avl.c [a35b458:1b20da0] in mainline

File:

• kernel/generic/src/adt/avl.c (modified) (24 diffs)

kernel/generic/src/adt/avl.c

@@ -66 +66 @@
 {
         avltree_node_t *p;
-
+        
         /*
          * Iteratively descend to the leaf that can contain the searched key.
@@ -92 +92 @@
 {
         avltree_node_t *p = t->root;
-
+        
         /*
          * Check whether the tree is empty.
@@ -98 +98 @@
         if (!p)
                 return NULL;
-
+        
         /*
          * Iteratively descend to the leftmost leaf in the tree.
@@ -104 +104 @@
         while (p->lft != NULL)
                 p = p->lft;
-
+        
         return p;
 }
@@ -151 +151 @@
 #define REBALANCE_INSERT_LR()           REBALANCE_INSERT_XY(lft, rgt, 1)
 #define REBALANCE_INSERT_RL()           REBALANCE_INSERT_XY(rgt, lft, -1)
-
+        
 /** Insert new node into AVL tree.
  *
@@ -172 +172 @@
          */
         key = newnode->key + t->base;
-
+        
         /*
          * Iteratively descend to the leaf that can contain the new node.
@@ -244 +244 @@
                 }
         }
-
+        
         /*
          * To balance the tree, we must check and balance top node.
@@ -260 +260 @@
                          */
                         assert(par->balance == 1);
-
+                        
                         REBALANCE_INSERT_LR();
                 }
@@ -275 +275 @@
                          */
                         assert(par->balance == -1);
-
+                
                         REBALANCE_INSERT_RL();
                 }
@@ -375 +375 @@
         assert(t);
         assert(node);
-
+        
         if (node->lft == NULL) {
                 if (node->rgt) {
@@ -451 +451 @@
                 cur->par = node->par;
         }
-
+        
         /*
          * Repair the parent node's pointer which pointed previously to the
@@ -457 +457 @@
          */
         (void) repair(t, node, node, cur, NULL, false);
-
+        
         /*
          * Repair cycle which repairs balances of nodes on the way from from the
@@ -484 +484 @@
                                          * RL rotation.
                                          */
-
+                                        
                                         cur = par->lft;
                                         par->lft = cur->rgt;
@@ -490 +490 @@
                                         gpa->rgt = cur->lft;
                                         cur->lft = gpa;
-
+                                        
                                         /*
                                          * Repair balances and paternity of
@@ -497 +497 @@
                                          */
                                         REBALANCE_DELETE_RL();
-
+                                        
                                         /*
                                          * Repair paternity.
@@ -513 +513 @@
                                          * RR rotation.
                                          */
-
+                                        
                                         gpa->rgt = par->lft;
                                         if (par->lft)
                                                 par->lft->par = gpa;
                                         par->lft = gpa;
-
+                                        
                                         /*
                                          * Repair paternity.
@@ -524 +524 @@
                                         par->par = gpa->par;
                                         gpa->par = par;
-
+                                        
                                         if (par->balance == 0) {
                                                 /*
@@ -575 +575 @@
                                  */
                                 par = gpa->lft;
-
+                                
                                 if (par->balance == 1) {
                                         /*
                                          * LR rotation.
                                          */
-
+                                        
                                         cur = par->rgt;
                                         par->rgt = cur->lft;
@@ -586 +586 @@
                                         gpa->lft = cur->rgt;
                                         cur->rgt = gpa;
-
+                                        
                                         /*
                                          * Repair balances and paternity of
@@ -619 +619 @@
                                         par->par = gpa->par;
                                         gpa->par = par;
-
+                                        
                                         if (par->balance == 0) {
                                                 /*
@@ -630 +630 @@
                                                 par->balance = 1;
                                                 gpa->balance = -1;
-
+                                                
                                                 (void) repair(t, par, gpa, par,
                                                     NULL, false);
@@ -637 +637 @@
                                                 par->balance = 0;
                                                 gpa->balance = 0;
-
+                                                
                                                 if (!repair(t, par, gpa, par,
                                                     &dir, false))
@@ -667 +667 @@
 {
         avltree_node_t *node;
-
+        
         /*
          * Start searching for the smallest key in the tree starting in the root
@@ -673 +673 @@
          * must have the smallest key).
          */
-
+         
         node = t->root;
         if (!node)
                 return false;
-
+        
         while (node->lft != NULL)
                 node = node->lft;
-
+        
         avltree_delete(t, node);