Subversion Repositories HelenOS

Rev

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

Rev 2089 Rev 2106
Line 46... Line 46...
46 
/** B-tree node structure. */
 46 
/** B-tree node structure. */
47 
typedef struct btree_node {
 47 
typedef struct btree_node {
48 
    /** Number of keys. */
 48 
    /** Number of keys. */
49 
    count_t keys;
 49 
    count_t keys;
50 
 
 50 
 
- 
 
 51 
    /**
51 
    /** Keys. We currently support only single keys. Additional room for one extra key is provided. */
 52 
     * Keys. We currently support only single keys. Additional room for one
- 
 
 53 
     * extra key is provided.
- 
 
 54 
     */
52 
    btree_key_t key[BTREE_MAX_KEYS + 1];
 55 
    btree_key_t key[BTREE_MAX_KEYS + 1];
53 
 
 56 
 
54 
    /**
 57 
    /**
55 
     * Pointers to values. Sorted according to the key array. Defined only in leaf-level.
 58 
     * Pointers to values. Sorted according to the key array. Defined only in
56 
     * There is room for storing value for the extra key.
 59 
     * leaf-level. There is room for storing value for the extra key.
57 
     */
 60 
     */
58 
    void *value[BTREE_MAX_KEYS + 1];
 61 
    void *value[BTREE_MAX_KEYS + 1];
59 
   
 62 
   
60 
    /**
 63 
    /**
61 
     * Pointers to descendants of this node sorted according to the key array.
 64 
     * Pointers to descendants of this node sorted according to the key
- 
 
 65 
     * array.
- 
 
 66 
     *
62 
     * subtree[0] points to subtree with keys lesser than to key[0].
 67 
     * subtree[0] points to subtree with keys lesser than to key[0].
63 
     * subtree[1] points to subtree with keys greater than or equal to key[0] and lesser than key[1].
 68 
     * subtree[1] points to subtree with keys greater than or equal to
- 
 
 69 
     *        key[0] and lesser than key[1].
64 
     * ...
 70 
     * ...
65 
     * There is room for storing a subtree pointer for the extra key.
 71 
     * There is room for storing a subtree pointer for the extra key.
66 
     */
 72 
     */
67 
    struct btree_node *subtree[BTREE_M + 1];
 73 
    struct btree_node *subtree[BTREE_M + 1];
68 
 
 74 
 
69 
    /** Pointer to parent node. Root node has NULL parent. */
 75 
    /** Pointer to parent node. Root node has NULL parent. */
70 
    struct btree_node *parent;
 76 
    struct btree_node *parent;
71 
 
 77 
 
- 
 
 78 
    /**
72 
    /** Link connecting leaf-level nodes. Defined only when this node is a leaf. */
 79 
     * Link connecting leaf-level nodes. Defined only when this node is a
- 
 
 80 
     * leaf. */
73 
    link_t leaf_link;
 81 
    link_t leaf_link;
74 
 
 82 
 
75 
    /** Variables needed by btree_print(). */  
 83 
    /* Variables needed by btree_print(). */   
76 
    link_t bfs_link;
 84 
    link_t bfs_link;
77 
    int depth;
 85 
    int depth;
78 
} btree_node_t;
 86 
} btree_node_t;
79 
 
 87 
 
80 
/** B-tree structure. */
 88 
/** B-tree structure. */
Line 86... Line 94...
86 
extern void btree_init(void);
 94 
extern void btree_init(void);
87 
 
 95 
 
88 
extern void btree_create(btree_t *t);
 96 
extern void btree_create(btree_t *t);
89 
extern void btree_destroy(btree_t *t);
 97 
extern void btree_destroy(btree_t *t);
90 
 
 98 
 
91 
extern void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node);
 99 
extern void btree_insert(btree_t *t, btree_key_t key, void *value,
- 
 
 100 
    btree_node_t *leaf_node);
92 
extern void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node);
 101 
extern void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node);
93 
extern void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node);
 102 
extern void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node);
94 
 
 103 
 
95 
extern btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node);
 104 
extern btree_node_t *btree_leaf_node_left_neighbour(btree_t *t,
- 
 
 105 
    btree_node_t *node);
96 
extern btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node);
 106 
extern btree_node_t *btree_leaf_node_right_neighbour(btree_t *t,
- 
 
 107 
    btree_node_t *node);
97 
 
 108 
 
98 
extern void btree_print(btree_t *t);
 109 
extern void btree_print(btree_t *t);
99 
#endif
 110 
#endif
100 
 
 111 
 
101 
/** @}
 112 
/** @}