Subversion Repositories HelenOS-historic

Rev

Rev 1248 | Rev 1704 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1248 Rev 1483
Line 48... Line 48...
48 
#include <debug.h>
 48 
#include <debug.h>
49 
#include <panic.h>
 49 
#include <panic.h>
50 
#include <typedefs.h>
 50 
#include <typedefs.h>
51 
#include <print.h>
 51 
#include <print.h>
52 
 
 52 
 
- 
 
 53 
static void btree_destroy_subtree(btree_node_t *root);
53 
static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
 54 
static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
54 
static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
 55 
static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
55 
static void node_initialize(btree_node_t *node);
 56 
static void node_initialize(btree_node_t *node);
56 
static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
 57 
static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
57 
static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
 58 
static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
Line 99... Line 100...
99 
}
 100 
}
100 
 
 101 
 
101 
/** Destroy empty B-tree. */
 102 
/** Destroy empty B-tree. */
102 
void btree_destroy(btree_t *t)
 103 
void btree_destroy(btree_t *t)
103 
{
 104 
{
104 
    ASSERT(!t->root->keys);
 - 
 
105 
    slab_free(btree_node_slab, t->root);
 105 
    btree_destroy_subtree(t->root);
106 
}
 106 
}
107 
 
 107 
 
108 
/** Insert key-value pair into B-tree.
 108 
/** Insert key-value pair into B-tree.
109 
 *
 109 
 *
110 
 * @param t B-tree.
 110 
 * @param t B-tree.
Line 126... Line 126...
126 
    }
 126 
    }
127 
   
 127 
   
128 
    _btree_insert(t, key, value, NULL, lnode);
 128 
    _btree_insert(t, key, value, NULL, lnode);
129 
}
 129 
}
130 
 
 130 
 
- 
 
 131 
/** Destroy subtree rooted in a node.
- 
 
 132 
 *
- 
 
 133 
 * @param root Root of the subtree.
- 
 
 134 
 */
- 
 
 135 
void btree_destroy_subtree(btree_node_t *root)
- 
 
 136 
{
- 
 
 137 
    int i;
- 
 
 138 
 
- 
 
 139 
    if (root->keys) {
- 
 
 140 
        for (i = 0; i < root->keys + 1; i++) {
- 
 
 141 
            if (root->subtree[i])
- 
 
 142 
                btree_destroy_subtree(root->subtree[i]);
- 
 
 143 
        }
- 
 
 144 
    }
- 
 
 145 
    slab_free(btree_node_slab, root);
- 
 
 146 
}
- 
 
 147 
 
131 
/** Recursively insert into B-tree.
 148 
/** Recursively insert into B-tree.
132 
 *
 149 
 *
133 
 * @param t B-tree.
 150 
 * @param t B-tree.
134 
 * @param key Key to be inserted.
 151 
 * @param key Key to be inserted.
135 
 * @param value Value to be inserted.
 152 
 * @param value Value to be inserted.