Subversion Repositories HelenOS

Rev

Rev 2450 | 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
}