Subversion Repositories HelenOS

Rev

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

Rev 2499 Rev 2501
Line 50... Line 50...
50 
 */
 50 
 */
51 
 
 51 
 
52 
#include <adt/avl.h>
 52 
#include <adt/avl.h>
53 
#include <debug.h>
 53 
#include <debug.h>
54 
 
 54 
 
55 
 
 - 
 
56 
#define LEFT    0
 55 
#define LEFT    0
57 
#define RIGHT   1
 56 
#define RIGHT   1
58 
 
 57 
 
59 
 
 - 
 
60 
/** Search for the first occurence of the given key in an AVL tree.
 58 
/** Search for the first occurence of the given key in an AVL tree.
61 
 *
 59 
 *
62 
 * @param t AVL tree.
 60 
 * @param t AVL tree.
63 
 * @param key Key to be searched.
 61 
 * @param key Key to be searched.
64 
 *
 62 
 *
65 
 * @return Pointer to a node or NULL if there is no such key.
 63 
 * @return Pointer to a node or NULL if there is no such key.
66 
 */
 64 
 */
67 
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
 65 
avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
68 
{
 66 
{
69 
    avltree_node_t *p;
 67 
    avltree_node_t *p;
70 
   
 68 
   
71 
    /*
 69 
    /*
72 
     * Iteratively descend to the leaf that can contain the searched key.
 70 
     * Iteratively descend to the leaf that can contain the searched key.
Line 118... Line 116...
118 
{  
 116 
{  
119 
    avltree_node_t *par;
 117 
    avltree_node_t *par;
120 
    avltree_node_t *gpa;
 118 
    avltree_node_t *gpa;
121 
    avltree_node_t *top;
 119 
    avltree_node_t *top;
122 
    avltree_node_t **dpc;
 120 
    avltree_node_t **dpc;
123 
    uint64_t key;
 121 
    avltree_key_t key;
124 
 
 122 
 
125 
    ASSERT(t);
 123 
    ASSERT(t);
126 
    ASSERT(newnode);
 124 
    ASSERT(newnode);
127 
 
 125 
 
128 
    /*
 126 
    /*
Line 705... Line 703...
705 
    avltree_delete(t, node);
 703 
    avltree_delete(t, node);
706 
 
 704 
 
707 
    return true;
 705 
    return true;
708 
}
 706 
}
709 
 
 707 
 
- 
 
 708 
static void _avltree_walk(avltree_node_t *node, avltree_walker_t walker)
- 
 
 709 
{
- 
 
 710 
    if (node->lft)
- 
 
 711 
        _avltree_walk(node->lft, walker);
- 
 
 712 
    walker(node);
- 
 
 713 
    if (node->rgt)
- 
 
 714 
        _avltree_walk(node->rgt, walker);
- 
 
 715 
}
- 
 
 716 
 
- 
 
 717 
/** Walk the AVL tree and apply the walker function on each visited node.
- 
 
 718 
 *
- 
 
 719 
 * @param t     AVL tree to be walked.
- 
 
 720 
 * @param walker    Walker function that will be called on each visited
- 
 
 721 
 *          node.
- 
 
 722 
 */
- 
 
 723 
void avltree_walk(avltree_t *t, avltree_walker_t walker)
- 
 
 724 
{
- 
 
 725 
    _avltree_walk(t->root, walker);
- 
 
 726 
}
- 
 
 727 
 
710 
/** @}
 728 
/** @}
711 
 */
 729 
 */
712 
 
 730