WebSVN – HelenOS – Diff – /branches/rcu/kernel/generic/src/adt/avl.c

  * @brief   AVL tree implementation.
+ *
  * This file implements AVL tree type and operations.
+ *
  * Implemented AVL tree has the following properties:
- * @li It is binary search tree with non-unique keys.
+ * @li It is a binary search tree with non-unique keys.
- * @li Difference of heights of left and right subtree of every node is max 1.
+ * @li Difference of heights of the left and the right subtree of every node is
+ *     one at maximum.
+ *
- * Every node has pointer to its parent which allows insertion of multiple identical keys
+ * Every node has a pointer to its parent which allows insertion of multiple
- * into tree.
+ * identical keys into the tree.
+ *
- * Be careful of using this tree because of base atribute, which is added to every inserted
+ * Be careful when using this tree because of the base atribute which is added
- * node key. There is no rule in which order nodes with the same key are visited.
+ * to every inserted node key. There is no rule in which order nodes with the
+ * same key are visited.
  */
 #include <adt/avl.h>
 #include <debug.h>
-#define AVLTREE_LEFT 0
+#define LEFT    0
-#define AVLTREE_RIGHT 1
+#define RIGHT   1
-/** Search first occurence of given key in AVL tree.
+/** Search for the first occurence of the given key in an AVL tree.
+ *
  * @param t AVL tree.
  * @param key Key to be searched.
+ *
- * @return Pointer to node or NULL if there is no such key.
+ * @return Pointer to a node or NULL if there is no such key.
  */
 avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
+{
     avltree_node_t *p;
     while (p != NULL) {
         if (p->key > key)
             p = p->lft;
         else if (p->key < key)
             p = p->rgt;
-        else {
+        else
             return p;
-        }
+    }
     return NULL;
+}
-/** Find node with smallest key in AVL tree.
+/** Find the node with the smallest key in an AVL tree.
+ *
  * @param t AVL tree.
+ *
- * @return Pointer to node or NULL if there is no node in the tree.
+ * @return Pointer to a node or NULL if there is no node in the tree.
  */
 avltree_node_t *avltree_find_min(avltree_t *t)
+{
     avltree_node_t *p = t->root;
     /*
-     * Check whether tree is empty.
+     * Check whether the tree is empty.
      */
+    if (!p)
-    if (!p) return NULL;
+        return NULL;
     /*
      * Iteratively descend to the leftmost leaf in the tree.
      */
     while (p->lft != NULL)
     /*
      * Creating absolute key.
      */
     key = newnode->key + t->base;
     /*
-     * Iteratively descend to the leaf that can contain new node.
+     * Iteratively descend to the leaf that can contain the new node.
      * Last node with non-zero balance in the way to leaf is stored as top -
-     * it si place of possible balance fault.
+     * it is a place of possible inbalance.
      */
     dpc = &t->root;
     gpa = NULL;
     top = t->root;
     while ((par = (*dpc)) != NULL) {
         if (par->balance != 0) {
             top = par;
+        }
         gpa = par;
-        dpc = par->key > key? &par->lft: &par->rgt;
+        dpc = par->key > key ? &par->lft: &par->rgt;
+    }
     /*
      * Initialize new node.
      */
     newnode->rgt = NULL;
     newnode->par = gpa;
     newnode->balance = 0;
     /*
-     * Insert first node into empty tree.
+     * Insert first node into the empty tree.
      */
     if (t->root == NULL) {
         *dpc = newnode;
         return;
+    }
      * Insert new node into previously found leaf place.
      */
     *dpc = newnode;
     /*
-     * If tree contains one node - end.
+     * If the tree contains one node - end.
      */
-    if (top == NULL) return;
+    if (top == NULL)
+        return;
     /*
-     * Store pointer of top's father which points to the node with potentialy broken
+     * Store pointer of top's father which points to the node with
-     * balance (top).
+     * potentially broken balance (top).
      */
-    if (top->par == NULL)
+    if (top->par == NULL) {
         dpc = &t->root;
-    else
+    } else {
         if (top->par->lft == top)
-            dpc = &(top->par->lft);
+            dpc = &top->par->lft;
         else
-            dpc = &(top->par->rgt);
+            dpc = &top->par->rgt;
+    }
     /*
-     * Repair all balances on the way from top node to newly inserted node.
+     * Repair all balances on the way from top node to the newly inserted
+     * node.
      */
     par = top;
     while (par != newnode) {
         if (par->key > key) {
             par->balance--;
             par = par->rgt;
+        }
+    }
     /*
-     * To balance tree we must check and balance top node.
+     * To balance the tree, we must check and balance top node.
      */
     if (top->balance == -2) {
         par = top->lft;
         if (par->balance == -1) {
             /*
              * LL rotation.
              */
             top->lft = par->rgt;
-            if (top->lft != NULL) top->lft->par = top;
+            if (top->lft != NULL)
+                top->lft->par = top;
             par->par = top->par;
             top->par = par;
             par->rgt = top;
             par->balance = top->balance = 0;
             *dpc = par;
              */
             ASSERT(par->balance == 1);
             gpa = par->rgt;
             par->rgt = gpa->lft;
-            if (gpa->lft != NULL) gpa->lft->par = par;
+            if (gpa->lft != NULL)
+                gpa->lft->par = par;
             gpa->lft = par;
             par->par = gpa;
             top->lft = gpa->rgt;
-            if (gpa->rgt != NULL) gpa->rgt->par = top;
+            if (gpa->rgt != NULL)
+                gpa->rgt->par = top;
             gpa->rgt = top;
             gpa->par = top->par;
             top->par = gpa;
             if (gpa->balance == -1) {
         if (par->balance == 1) {
             /*
              * RR rotation.
              */
             top->rgt = par->lft;
-            if (top->rgt != NULL) top->rgt->par = top;
+            if (top->rgt != NULL)
+                top->rgt->par = top;
             par->par = top->par;
             top->par = par;
             par->lft = top;
             par->balance = top->balance = 0;
             *dpc = par;
              */
             ASSERT(par->balance == -1);
             gpa = par->lft;
             par->lft = gpa->rgt;
-            if (gpa->rgt != NULL) gpa->rgt->par = par;
+            if (gpa->rgt != NULL)
+                gpa->rgt->par = par;
             gpa->rgt = par;
             par->par = gpa;
             top->rgt = gpa->lft;
-            if (gpa->lft != NULL) gpa->lft->par = top;
+            if (gpa->lft != NULL)
+                gpa->lft->par = top;
             gpa->lft = top;
             gpa->par = top->par;
             top->par = gpa;
             if (gpa->balance == 1) {
         return;
+    }
+}
-/** Delete node from AVL tree.
+/** Delete a node from the AVL tree.
+ *
- * Because of allowed multiple identical keys parent pointers are essential
+ * Because multiple identical keys are allowed, the parent pointers are
- * during deletition.
+ * essential during deletion.
+ *
  * @param t AVL tree structure.
- * @param node Address of node which will be deleted.
+ * @param node Address of the node which will be deleted.
  */
 void avltree_delete(avltree_t *t, avltree_node_t *node)
+{
     avltree_node_t *cur;
     avltree_node_t *par;
     uint8_t dir;
     ASSERT(t);
     ASSERT(node);
     if (node->lft == NULL) {
         if (node->rgt) {
             /*
-             * Replace node with its only right son.
+             * Replace the node with its only right son.
+             *
-             * Balance of right son will be repaired in balancing cycle.
+             * Balance of the right son will be repaired in the
+             * balancing cycle.
              */
             cur = node->rgt;
             cur->par = node->par;
             gpa = cur;
-            dir = AVLTREE_RIGHT;
+            dir = RIGHT;
             cur->balance = node->balance;
         } else {
             if (node->par == NULL) {
                 /*
-                 * Tree has only one node - it will be empty tree and balancing can end.
+                 * The tree has only one node - it will become
+                 * an empty tree and the balancing can end.
                  */
                 t->root = NULL;
                 return;
+            }
             /*
-             * Node has no child, will be deleted with no substitution.
+             * The node has no child, it will be deleted with no
+             * substitution.
              */
             gpa = node->par;
             cur = NULL;
-            dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
+            dir = (gpa->lft == node) ? LEFT: RIGHT;
+        }
     } else {
         /*
-         * Node has left and right son. Find a node with smallest key in left subtree
+         * The node has left and right son. Find a node with the
+         * smallest key in the left subtree and replace the deleted node
-         * and replace deleted node with that node.
+         * with that node.
          */
         for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
+            ;
-        //cur obsahuje uzel, ktery vlozim misto uzlu node
         if (cur != node->lft) {
             /*
-             * The most right node of deleted node's left subtree was found. Replace
+             * The rightmost node of the deleted node's left subtree
+             * was found. Replace the deleted node with this node.
-             * deleted node with this node. Cutting founded node has two cases in
+             * Cutting off of the found node has two cases that
-             * dependence on its left son.
+             * depend on its left son.
              */
             if (cur->lft) {
                 /*
-                 * Founded node has left son.
+                 * The found node has a left son.
                  */
                 gpa = cur->lft;
                 gpa->par = cur->par;
-                dir = AVLTREE_LEFT;
+                dir = LEFT;
                 gpa->balance = cur->balance;
             } else {
-                dir = AVLTREE_RIGHT;
+                dir = RIGHT;
                 gpa = cur->par;
+            }
             cur->par->rgt = cur->lft;
             cur->lft = node->lft;
             cur->lft->par = cur;
         } else {
             /*
+             * The left son of the node hasn't got a right son. The
-             * Left son of node hasn't got right son. Left son will take deleted node's place.
+             * left son will take the deleted node's place.
              */
-            dir = AVLTREE_LEFT;
+            dir = LEFT;
             gpa = cur;
+        }
+        if (node->rgt)
-        if (node->rgt) node->rgt->par = cur;
+            node->rgt->par = cur;
         cur->rgt = node->rgt;
         cur->balance = node->balance;
         cur->par = node->par;
+    }
     /*
-     * Repair parent nodes pointer which pointed previously to deleted node.
+     * Repair the parent node's pointer which pointed previously to the
+     * deleted node.
      */
     if (node->par == NULL) {
         t->root = cur;
     } else {
         if (node->par->lft == node) {
             node->par->rgt = cur;
+        }
+    }
     /*
-     * Repair cycle which repairs balances of nodes in way from cutted noded down to root.
+     * Repair cycle which repairs balances of nodes on the way from from the
+     * cut-off node up to the root.
      */
-    for(;;) {
+    for (;;) {
-        if (dir == AVLTREE_LEFT) {
+        if (dir == LEFT) {
             /*
-             * Deletition was made in left subtree.
+             * Deletion was made in the left subtree.
              */
             gpa->balance++;
-            if (gpa->balance == +1) {
+            if (gpa->balance == 1) {
                 /*
-                 * Stop balancing, tree is balanced.
+                 * Stop balancing, the tree is balanced.
                  */
                 break;
-            } else if (gpa->balance == +2) {
+            } else if (gpa->balance == 2) {
                 /*
-                 * Bad balance, heights of left and right subtrees differs more then is allowed.
+                 * Bad balance, heights of left and right
+                 * subtrees differ more than by one.
                  */
                 par = gpa->rgt;
                 if (par->balance == -1) {
                     /*
                     cur->rgt = par;
                     gpa->rgt = cur->lft;
                     cur->lft = gpa;
                     /*
-                     * Repair balances and paternity of childs in dependence on
+                     * Repair balances and paternity of
+                     * children, depending on the balance
-                     * balance factor of grand child (cur).
+                     * factor of the grand child (cur).
                      */
-                    if (cur->balance == +1) {
+                    if (cur->balance == 1) {
                         par->balance = 0;
                         gpa->balance = -1;
+                        if (gpa->rgt)
-                        if (gpa->rgt) gpa->rgt->par = gpa;
+                            gpa->rgt->par = gpa;
                         par->lft->par = par;
                     } else if (cur->balance == 0) {
                         par->balance = gpa->balance = 0;
+                        if (gpa->rgt)
-                        if (gpa->rgt) gpa->rgt->par = gpa;
+                            gpa->rgt->par = gpa;
+                        if (par->lft)
-                        if (par->lft) par->lft->par = par;
+                            par->lft->par = par;
                     } else {
-                        par->balance = +1;
+                        par->balance = 1;
                         gpa->balance = 0;
+                        if (par->lft)
-                        if (par->lft) par->lft->par = par;
+                            par->lft->par = par;
                         gpa->rgt->par = gpa;
+                    }
                     cur->balance = 0;
                     /*
                     cur->par = gpa->par;
                     gpa->par = cur;
                     par->par = cur;
                     /*
+                     * Repair the pointer which pointed to
-                     * Repair pointer which pointed to balanced node. If it was root then balancing
+                     * the balanced node. If it was root
+                     * then the balancing is finished.
+                     * Otherwise continue with the next
-                     * is finished else continue in next iteration (parent node).
+                     * iteration (parent node).
                      */
                     if (cur->par == NULL) {
                         t->root = cur;
                         break;
-                    } else
+                    } else {
                         if (cur->par->lft == gpa) {
                             cur->par->lft = cur;
-                            dir = AVLTREE_LEFT;
+                            dir = LEFT;
                         } else {
                             cur->par->rgt = cur;
-                            dir = AVLTREE_RIGHT;
+                            dir = RIGHT;
+                        }
+                    }
                     gpa = cur->par;
                 } else {
                     /*
                      * RR rotation.
                      */
                     gpa->rgt = par->lft;
+                    if (par->lft)
-                    if (par->lft) par->lft->par = gpa;
+                        par->lft->par = gpa;
                     par->lft = gpa;
                     /*
                      * Repair paternity.
                      */
                     par->par = gpa->par;
                     gpa->par = par;
                     if (par->balance == 0) {
                         /*
+                         * The right child of the
+                         * balanced node is balanced,
-                         * Right child of balanced node is balanced, after RR rotation is done, whole
+                         * after RR rotation is done,
-                         * tree will be balanced.
+                         * the whole tree will be
+                         * balanced.
                          */
                         par->balance = -1;
-                        gpa->balance = +1;
+                        gpa->balance = 1;
                         /*
+                         * Repair the pointer which
-                         * Repair pointer which pointed to balanced node and finish balancing.
+                         * pointed to the balanced node
+                         * and finish balancing.
                          */
                         if (par->par == NULL) {
                             t->root = par;
-                        } else
+                        } else {
-                            if (par->par->lft == gpa) {
+                            if (par->par->lft ==
+                                gpa) {
-                                par->par->lft = par;
+                                par->par->lft =
+                                    par;
                             } else {
-                                par->par->rgt = par;
+                                par->par->rgt =
+                                    par;
+                            }
+                        }
                         break;
                     } else {
                         par->balance = gpa->balance = 0;
                         /*
+                         * Repair the pointer which
+                         * pointed to the balanced node.
-                         * Repair pointer which pointed to balanced node. If it was root then balancing
+                         * If it was root then balancing
+                         * is finished. Otherwise
+                         * continue with the next
-                         * is finished else continue in next iteration (parent node).
+                         * iteration (parent node).
                          */
                         if (par->par == NULL) {
                             t->root = par;
                             break;
                         } else {
+                            if (par->par->lft ==
+                                gpa) {
-                            if (par->par->lft == gpa) {
+                                par->par->lft =
-                                par->par->lft = par;
+                                    par;
-                                dir = AVLTREE_LEFT;
+                                dir = LEFT;
                             } else {
-                                par->par->rgt = par;
+                                par->par->rgt =
+                                    par;
-                                dir = AVLTREE_RIGHT;
+                                dir = RIGHT;
+                            }
+                        }
+                    }
                     gpa = par->par;
+                }
             } else {
                 /*
+                 * Repair the pointer which pointed to the
-                 * Repair pointer which pointed to balanced node. If it was root then balancing
+                 * balanced node. If it was root then balancing
-                 * is finished else continue in next iteration (parent node).
+                 * is finished else continue with the next
+                 * iteration (parent node).
                  */
-                if (!gpa->par) break;
+                if (!gpa->par)
+                    break;
                 if (gpa->par->lft == gpa) {
-                    dir = AVLTREE_LEFT;
+                    dir = LEFT;
                 } else {
-                    dir = AVLTREE_RIGHT;
+                    dir = RIGHT;
+                }
                 gpa = gpa->par;
+            }
         } else {
             /*
-             * Deletition was made in right subtree.
+             * Deletion was made in the right subtree.
              */
             gpa->balance--;
             if (gpa->balance == -1) {
                 /*
-                 * Stop balancing, tree is balanced.
+                 * Stop balancing, the tree is balanced.
                  */
                 break;
             } else if (gpa->balance == -2) {
                 /*
-                 * Bad balance, heights of left and right subtrees differs more then is allowed.
+                 * Bad balance, heights of left and right
+                 * subtrees differ more than by one.
                  */
                 par = gpa->lft;
-                if (par->balance == +1) {
+                if (par->balance == 1) {
                     /*
                      * LR rotation.
                      */
                     cur = par->rgt;
                     cur->lft = par;
                     gpa->lft = cur->rgt;
                     cur->rgt = gpa;
                     /*
-                     * Repair balances and paternity of childs in dependence on
+                     * Repair balances and paternity of
+                     * children, depending on the balance
-                     * balance factor of grand child (cur).
+                     * factor of the grand child (cur).
                      */
                     if (cur->balance == -1) {
                         par->balance = 0;
-                        gpa->balance = +1;
+                        gpa->balance = 1;
+                        if (gpa->lft)
-                        if (gpa->lft) gpa->lft->par = gpa;
+                            gpa->lft->par = gpa;
                         par->rgt->par = par;
                     } else if (cur->balance == 0) {
                         par->balance = gpa->balance = 0;
+                        if (gpa->lft)
-                        if (gpa->lft) gpa->lft->par = gpa;
+                            gpa->lft->par = gpa;
+                        if (par->rgt)
-                        if (par->rgt) par->rgt->par = par;
+                            par->rgt->par = par;
                     } else {
                         par->balance = -1;
                         gpa->balance = 0;
+                        if (par->rgt)
-                        if (par->rgt) par->rgt->par = par;
+                            par->rgt->par = par;
                         gpa->lft->par = gpa;
+                    }
                     cur->balance = 0;
                     /*
                     cur->par = gpa->par;
                     gpa->par = cur;
                     par->par = cur;
                     /*
+                     * Repair the pointer which pointed to
-                     * Repair pointer which pointed to balanced node. If it was root then balancing
+                     * the balanced node. If it was root
+                     * then balancing is finished. Otherwise
-                     * is finished else continue in next iteration (parent node).
+                     * continue with the next iteration
+                     * (parent node).
                      */
                     if (cur->par == NULL) {
                         t->root = cur;
                         break;
-                    } else
+                    } else {
                         if (cur->par->lft == gpa) {
                             cur->par->lft = cur;
-                            dir = AVLTREE_LEFT;
+                            dir = LEFT;
                         } else {
                             cur->par->rgt = cur;
-                            dir = AVLTREE_RIGHT;
+                            dir = RIGHT;
+                        }
+                    }
                     gpa = cur->par;
                 } else {
                     /*
                      * LL rotation.
                      */
                     gpa->lft = par->rgt;
+                    if (par->rgt)
-                    if (par->rgt) par->rgt->par = gpa;
+                        par->rgt->par = gpa;
                     par->rgt = gpa;
                     /*
                      * Repair paternity.
                      */
                     par->par = gpa->par;
                     gpa->par = par;
                     if (par->balance == 0) {
                         /*
+                         * The left child of the
-                         * Left child of balanced node is balanced, after RR rotation is done, whole
+                         * balanced node is balanced,
+                         * after LL rotation is done,
-                         * tree will be balanced.
+                         * the whole tree will be
+                         * balanced.
                          */
-                        par->balance = +1;
+                        par->balance = 1;
                         gpa->balance = -1;
                         /*
+                         * Repair the pointer which
-                         * Repair pointer which pointed to balanced node and finish balancing.
+                         * pointed to the balanced node
+                         * and finish balancing.
                          */
                         if (par->par == NULL) {
                             t->root = par;
-                        } else
+                        } else {
-                            if (par->par->lft == gpa) {
+                            if (par->par->lft ==
+                                gpa) {
-                                par->par->lft = par;
+                                par->par->lft =
+                                    par;
                             } else {
-                                par->par->rgt = par;
+                                par->par->rgt =
+                                    par;
+                            }
+                        }
                         break;
                     } else {
                         par->balance = gpa->balance = 0;
                         /*
+                         * Repair the pointer which
+                         * pointed to the balanced node.
-                         * Repair pointer which pointed to balanced node. If it was root then balancing
+                         * If it was root then balancing
+                         * is finished. Otherwise
+                         * continue with the next
-                         * is finished else continue in next iteration (parent node).
+                         * iteration (parent node).
                          */
                         if (par->par == NULL) {
                             t->root = par;
                             break;
                         } else {
-                            if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna
+                            if (par->par->lft ==
+                                gpa) {
-                                par->par->lft = par;
+                                par->par->lft =
+                                    par;
-                                dir = AVLTREE_LEFT;
+                                dir = LEFT;
                             } else {
-                                par->par->rgt = par;
+                                par->par->rgt =
+                                    par;
-                                dir = AVLTREE_RIGHT;
+                                dir = RIGHT;
+                            }
+                        }
+                    }
                     gpa = par->par;
+                }
             } else {
                 /*
+                 * Repair the pointer which pointed to the
-                 * Repair pointer which pointed to balanced node. If it was root then balancing
+                 * balanced node. If it was root then balancing
-                 * is finished else continue in next iteration (parent node).
+                 * is finished. Otherwise continue with the next
+                 * iteration (parent node).
                  */
-                if (!gpa->par) break;
+                if (!gpa->par)
+                    break;
                 if (gpa->par->lft == gpa) {
-                    dir = AVLTREE_LEFT;
+                    dir = LEFT;
                 } else {
-                    dir = AVLTREE_RIGHT;
+                    dir = RIGHT;
+                }
                 gpa = gpa->par;
+            }
+        }
+    }
+}
-/** Delete node from AVL tree with the smallest key.
+/** Delete a node with the smallest key from the AVL tree.
+ *
  * @param t AVL tree structure.
  */
 bool avltree_delete_min(avltree_t *t)
+{
     avltree_node_t *node;
     /*
-     * Start search of smallest key in tree in the root node and
+     * Start searching for the smallest key in the tree starting in the root
-     * continue in cycle to the most left node in the tree which
+     * node and continue in cycle to the leftmost node in the tree (which
-     * must have smallest key.
+     * must have the smallest key).
      */
     node = t->root;
+    if (!node)
-    if (!node) return false;
+        return false;
     while (node->lft != NULL)
         node = node->lft;
-    /*
-     * Use avltree_delete function to delete node from tree.
-     */
-    avltree_delete(t,node);
+    avltree_delete(t, node);
     return true;
+}
+/** @}
+ */

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/adt/avl.c – Rev 2461 → 2496