Subversion Repositories HelenOS

Rev

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

Rev 1136 Rev 1140
Line 26... Line 26...
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
27
 */
28
 
28
 
29
/*
29
/*
30
 * This B-tree has the following properties:
30
 * This B-tree has the following properties:
31
 * - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4)
31
 * - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
32
 * - values (i.e. pointers to values) are stored only in leaves
32
 * - values (i.e. pointers to values) are stored only in leaves
33
 * - leaves are linked in a list
33
 * - leaves are linked in a list
34
 * - technically, it is a B+-tree (because of the previous properties)
34
 * - technically, it is a B+-tree (because of the previous properties)
35
 *
35
 *
36
 * Be carefull when using these trees. They need to allocate
36
 * Be carefull when using these trees. They need to allocate
Line 59... Line 59...
59
 
59
 
60
#define ROOT_NODE(n)        (!(n)->parent)
60
#define ROOT_NODE(n)        (!(n)->parent)
61
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
61
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
62
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
62
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
63
 
63
 
-
 
64
#define FILL_FACTOR     ((BTREE_M-1)/2)
-
 
65
 
64
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
66
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
65
#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
67
#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
66
#define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
68
#define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
67
#define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
69
#define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
68
 
70
 
Line 169... Line 171...
169
        _btree_insert(t, median, NULL, rnode, node->parent);
171
        _btree_insert(t, median, NULL, rnode, node->parent);
170
    }  
172
    }  
171
       
173
       
172
}
174
}
173
 
175
 
-
 
176
/** Remove B-tree node.
-
 
177
 *
-
 
178
 * @param B-tree.
-
 
179
 * @param key Key to be removed from the B-tree along with its associated value.
-
 
180
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
174
/* TODO */
181
 */
175
void btree_remove(btree_t *t, __native key)
182
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
176
{
183
{
-
 
184
    btree_node_t *lnode;
-
 
185
   
-
 
186
    lnode = leaf_node;
-
 
187
    if (!lnode) {
-
 
188
        if (!btree_search(t, key, &lnode)) {
-
 
189
            panic("B-tree %P does not contain key %d\n", t, key);
-
 
190
        }
-
 
191
    }
-
 
192
   
-
 
193
    /* TODO */
-
 
194
 
177
}
195
}
178
 
196
 
179
/** Search key in a B-tree.
197
/** Search key in a B-tree.
180
 *
198
 *
181
 * @param t B-tree.
199
 * @param t B-tree.