Subversion Repositories HelenOS

Rev

Rev 2450 | Rev 2496 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 2450 Rev 2461
Line 35... Line 35...
35 
 * @brief   AVL tree implementation.
 35 
 * @brief   AVL tree implementation.
36 
 *
 36 
 *
37 
 * This file implements AVL tree type and operations.
 37 
 * This file implements AVL tree type and operations.
38 
 *
 38 
 *
39 
 * Implemented AVL tree has the following properties:
 39 
 * Implemented AVL tree has the following properties:
40 
 * @li it is binary search tree with non-unique keys
 40 
 * @li It is binary search tree with non-unique keys.
41 
 * @li Difference of heights of left and right subtree of every node is max 1.
 41 
 * @li Difference of heights of left and right subtree of every node is max 1.
42 
 *
 42 
 *
43 
 * Every node has pointer to its parent which allows insertion of multiple identical keys
 43 
 * Every node has pointer to its parent which allows insertion of multiple identical keys
44 
 * into tree.
 44 
 * into tree.
45 
 *
 45 
 *
Line 47... Line 47...
47 
 * node key. There is no rule in which order nodes with the same key are visited.
 47 
 * node key. There is no rule in which order nodes with the same key are visited.
48 
 */
 48 
 */
49 
 
 49 
 
50 
#include <adt/avl.h>
 50 
#include <adt/avl.h>
51 
#include <debug.h>
 51 
#include <debug.h>
52 
#include <panic.h>
 - 
 
53 
 
 52 
 
54 
 
 53 
 
55 
#define AVLTREE_LEFT 0
 54 
#define AVLTREE_LEFT 0
56 
#define AVLTREE_RIGHT 1
 55 
#define AVLTREE_RIGHT 1
57 
 
 56 
 
Line 129... Line 128...
129 
     */
 128 
     */
130 
    key = newnode->key + t->base;
 129 
    key = newnode->key + t->base;
131 
   
 130 
   
132 
 
 131 
 
133 
    /*
 132 
    /*
134 
     * Iteratively descend to the leaf that can will contain new node.
 133 
     * Iteratively descend to the leaf that can contain new node.
135 
     * Last node with non-zero balance in the way to leaf is stored as top -
 134 
     * Last node with non-zero balance in the way to leaf is stored as top -
136 
     * it si place of possible balance failure.
 135 
     * it si place of possible balance fault.
137 
     */
 136 
     */
138 
    dpc = &t->root;
 137 
    dpc = &t->root;
139 
    gpa = NULL;
 138 
    gpa = NULL;
140 
    top = t->root;
 139 
    top = t->root;
141 
    while ((par = (*dpc)) != NULL) {
 140 
    while ((par = (*dpc)) != NULL) {
Line 695... Line 694...
695 
 * @param t AVL tree structure.
 694 
 * @param t AVL tree structure.
696 
 */
 695 
 */
697 
bool avltree_delete_min(avltree_t *t)
 696 
bool avltree_delete_min(avltree_t *t)
698 
{
 697 
{
699 
    avltree_node_t *node;
 698 
    avltree_node_t *node;
700 
    uint64_t key;
 - 
 
701 
   
 699 
   
702 
    /*
 700 
    /*
703 
     * Start search of smallest key in tree in the root node and
 701 
     * Start search of smallest key in tree in the root node and
704 
     * continue in cycle to the most left node in the tree which
 702 
     * continue in cycle to the most left node in the tree which
705 
     * must have smallest key.
 703 
     * must have smallest key.
Line 709... Line 707...
709 
   
 707 
   
710 
    while (node->lft != NULL)
 708 
    while (node->lft != NULL)
711 
        node = node->lft;
 709 
        node = node->lft;
712 
   
 710 
   
713 
    /*
 711 
    /*
714 
     * Store key and use avltree_delete function to delete node from tree.
 712 
     * Use avltree_delete function to delete node from tree.
715 
     */
 713 
     */
716 
    key = node->key;
 - 
 
717 
    avltree_delete(t,node);
 714 
    avltree_delete(t,node);
718 
 
 715 
 
719 
    return true;
 716 
    return true;
720 
}
 717 
}