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.