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.