Subversion Repositories HelenOS

Rev

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

Rev 2416 Rev 2421
Line 1... Line 1...
1 
/*
 1 
/*
2 
 * Copyright (c) 2006 Vojtech Mencl
 2 
 * Copyright (c) 2007 Vojtech Mencl
3 
 * All rights reserved.
 3 
 * All rights reserved.
4 
 *
 4 
 *
5 
 * Redistribution and use in source and binary forms, with or without
 5 
 * Redistribution and use in source and binary forms, with or without
6 
 * modification, are permitted provided that the following conditions
 6 
 * modification, are permitted provided that the following conditions
7 
 * are met:
 7 
 * are met:
Line 59... Line 59...
59 
/** Search first occurence of given key in AVL tree.
 59 
/** Search first occurence of given key in AVL tree.
60 
 *
 60 
 *
61 
 * @param t AVL tree.
 61 
 * @param t AVL tree.
62 
 * @param key Key to be searched.
 62 
 * @param key Key to be searched.
63 
 *
 63 
 *
64 
 * @return Pointer to value or NULL if there is no such key.
 64 
 * @return Pointer to node or NULL if there is no such key.
65 
 */
 65 
 */
66 
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
 66 
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
67 
{
 67 
{
68 
    avltree_node_t *p;
 68 
    avltree_node_t *p;
69 
   
 69 
   
Line 82... Line 82...
82 
    }
 82 
    }
83 
    return NULL;
 83 
    return NULL;
84 
}
 84 
}
85 
 
 85 
 
86 
 
 86 
 
- 
 
 87 
/** Find node with smallest key in AVL tree.
- 
 
 88 
 *
- 
 
 89 
 * @param t AVL tree.
- 
 
 90 
 *
- 
 
 91 
 * @return Pointer to node or NULL if there is no node in the tree.
- 
 
 92 
 */
- 
 
 93 
avltree_node_t *avltree_find_min(avltree_t *t)
- 
 
 94 
{
- 
 
 95 
    avltree_node_t *p = t->root;
- 
 
 96 
   
- 
 
 97 
    /*
- 
 
 98 
     * Check whether tree is empty.
- 
 
 99 
     */
- 
 
 100 
    if (!p) return NULL;
- 
 
 101 
   
- 
 
 102 
    /*
- 
 
 103 
     * Iteratively descend to the leftmost leaf in the tree.
- 
 
 104 
     */
- 
 
 105 
    while (p->lft != NULL)
- 
 
 106 
        p = p->lft;
- 
 
 107 
   
- 
 
 108 
    return p;
- 
 
 109 
}
- 
 
 110 
 
87 
/** Insert new node into AVL tree.
 111 
/** Insert new node into AVL tree.
88 
 *
 112 
 *
89 
 * @param t AVL tree.
 113 
 * @param t AVL tree.
90 
 * @param newnode New node to be inserted.
 114 
 * @param newnode New node to be inserted.
91 
 */
 115 
 */
Line 112... Line 136...
112 
     * it si place of possible balance failure.
 136 
     * it si place of possible balance failure.
113 
     */
 137 
     */
114 
    dpc = &t->root;
 138 
    dpc = &t->root;
115 
    gpa = NULL;
 139 
    gpa = NULL;
116 
    top = t->root;
 140 
    top = t->root;
117 
    while (par = *dpc) {
 141 
    while ((par = (*dpc)) != NULL) {
118 
        if (par->balance != 0) {
 142 
        if (par->balance != 0) {
119 
            top = par;
 143 
            top = par;
120 
        }
 144 
        }
121 
        gpa = par;
 145 
        gpa = par;
122 
        dpc = par->key > key? &par->lft: &par->rgt;
 146 
        dpc = par->key > key? &par->lft: &par->rgt;
Line 668... Line 692...
668 
 
 692 
 
669 
/** Delete node from AVL tree with the smallest key and set base of tree to that key.
 693 
/** Delete node from AVL tree with the smallest key and set base of tree to that key.
670 
 *
 694 
 *
671 
 * @param t AVL tree structure.
 695 
 * @param t AVL tree structure.
672 
 */
 696 
 */
673 
avltree_node_t *avltree_delete_min(avltree_t *t)
 697 
bool avltree_delete_min(avltree_t *t)
674 
{
 698 
{
675 
    avltree_node_t *node;
 699 
    avltree_node_t *node;
676 
    uint64_t key;
 700 
    uint64_t key;
677 
   
 701 
   
678 
    /*
 702 
    /*