WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/adt/btree.c



#include <debug.h>
#include <panic.h>
#include <typedefs.h>
#include <print.h>
 
static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
static void node_initialize(btree_node_t *node);
static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
static btree_node_t *node_combine(btree_node_t *node);
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
static bool try_rotation_from_left(btree_node_t *rnode);
static bool try_rotation_from_right(btree_node_t *lnode);
 
#define ROOT_NODE(n)        (!(n)->parent)
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)

 * @param t B-tree.
 * @param key Key to be inserted.
 * @param value Value to be inserted.
 * @param leaf_node Leaf node where the insertion should begin.
 */
void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
{
    btree_node_t *lnode;
   
    ASSERT(value);
   

 * @param key Key to be inserted.
 * @param value Value to be inserted.
 * @param rsubtree Right subtree of the inserted key.
 * @param node Start inserting into this node.
 */
void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
{
    if (node->keys < BTREE_MAX_KEYS) {
        /*
         * Node conatins enough space, the key can be stored immediately.
         */

         * The key-value-rsubtree triplet has been inserted because
         * some keys could have been moved to the right sibling.
         */
    } else {
        btree_node_t *rnode;
        btree_key_t median;
       
        /*
         * Node is full and both siblings (if both exist) are full too.
         * Split the node and insert the smallest key from the node containing
         * bigger keys (i.e. the new node) into its parent.

 *
 * @param B-tree.
 * @param key Key to be removed from the B-tree along with its associated value.
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
 */
void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
{
    btree_node_t *lnode;
   
    lnode = leaf_node;
    if (!lnode) {

 *
 * @param B-tree.
 * @param key Key to be removed from the B-tree along with its associated value.
 * @param node Node where the key being removed resides.
 */
void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
{
    if (ROOT_NODE(node)) {
        if (node->keys == 1 && node->subtree[0]) {
            /*
             * Free the current root and set new root.

 * @param key Key to be searched.
 * @param leaf_node Address where to put pointer to visited leaf node.
 *
 * @return Pointer to value or NULL if there is no such key.
 */
void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
{
    btree_node_t *cur, *next;
   
    /*
     * Iteratively descend to the leaf that can contain the searched key.

 * @param node B-tree node into wich the new key is to be inserted.
 * @param key The key to be inserted.
 * @param value Pointer to value to be inserted.
 * @param lsubtree Pointer to the left subtree.
 */
void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
{
    int i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {

 * @param node B-tree node into wich the new key is to be inserted.
 * @param key The key to be inserted.
 * @param value Pointer to value to be inserted.
 * @param rsubtree Pointer to the right subtree.
 */
void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
{
    int i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {

 * is removed from the node as well.
 *
 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
{
    int i, j;
   
    for (i = 0; i < node->keys; i++) {
        if (key == node->key[i]) {

 * is removed from the node as well.
 *
 * @param node B-tree node.
 * @param key Key to be removed.
 */
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
{
    int i, j;
   
    for (i = 0; i < node->keys; i++) {
        if (key == node->key[i]) {

 * @param rsubtree Pointer to the right subtree of the key being added.
 * @param median Address in memory, where the median key will be stored.
 *
 * @return Newly created right sibling of node.
 */
btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
{
    btree_node_t *rnode;
    int i, j;
 
    ASSERT(median);

 * @param rnode Right sibling.
 * @param idx Index of the parent node key that is taking part in the rotation.
 */
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
{
    btree_key_t key;
 
    key = lnode->key[lnode->keys - 1];
       
    if (LEAF_NODE(lnode)) {
        void *value;

 * @param rnode Right sibling.
 * @param idx Index of the parent node key that is taking part in the rotation.
 */
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
{
    btree_key_t key;
 
    key = rnode->key[0];
       
    if (LEAF_NODE(rnode)) {
        void *value;

 * @param insvalue Value to be inserted.
 * @param rsubtree Right subtree of inskey.
 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
{
    index_t idx;
    btree_node_t *lnode;
 
    /*

 * @param insvalue Value to be inserted.
 * @param rsubtree Right subtree of inskey.
 *
 * @return True if the rotation was performed, false otherwise.
 */
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
{
    index_t idx;
    btree_node_t *rnode;
 
    /*

Rev 1164	Rev 1177
Line 44...	Line 44...
44	#include <debug.h>	44	#include <debug.h>
45	#include <panic.h>	45	#include <panic.h>
46	#include <typedefs.h>	46	#include <typedefs.h>
47	#include <print.h>	47	#include <print.h>
48		48
49	static void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node);	49	static void _btree_insert(btree_t t, btree_key_t key, void value, btree_node_t rsubtree, btree_node_t node);
50	static void _btree_remove(btree_t t, __native key, btree_node_t node);	50	static void _btree_remove(btree_t t, btree_key_t key, btree_node_t node);
51	static void node_initialize(btree_node_t *node);	51	static void node_initialize(btree_node_t *node);
52	static void node_insert_key_and_lsubtree(btree_node_t node, __native key, void value, btree_node_t *lsubtree);	52	static void node_insert_key_and_lsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *lsubtree);
53	static void node_insert_key_and_rsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	53	static void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);
54	static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);	54	static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
55	static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);	55	static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
56	static btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median);	56	static btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median);
57	static btree_node_t node_combine(btree_node_t node);	57	static btree_node_t node_combine(btree_node_t node);
58	static index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right);	58	static index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right);
59	static void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx);	59	static void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx);
60	static void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx);	60	static void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx);
61	static bool try_insert_by_rotation_to_left(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	61	static bool try_insert_by_rotation_to_left(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);
62	static bool try_insert_by_rotation_to_right(btree_node_t node, __native key, void value, btree_node_t *rsubtree);	62	static bool try_insert_by_rotation_to_right(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree);
63	static bool try_rotation_from_left(btree_node_t *rnode);	63	static bool try_rotation_from_left(btree_node_t *rnode);
64	static bool try_rotation_from_right(btree_node_t *lnode);	64	static bool try_rotation_from_right(btree_node_t *lnode);
65		65
66	#define ROOT_NODE(n) (!(n)->parent)	66	#define ROOT_NODE(n) (!(n)->parent)
67	#define INDEX_NODE(n) ((n)->subtree[0] != NULL)	67	#define INDEX_NODE(n) ((n)->subtree[0] != NULL)
Line 106...	Line 106...
106	* @param t B-tree.	106	* @param t B-tree.
107	* @param key Key to be inserted.	107	* @param key Key to be inserted.
108	* @param value Value to be inserted.	108	* @param value Value to be inserted.
109	* @param leaf_node Leaf node where the insertion should begin.	109	* @param leaf_node Leaf node where the insertion should begin.
110	*/	110	*/
111	void btree_insert(btree_t t, __native key, void value, btree_node_t *leaf_node)	111	void btree_insert(btree_t t, btree_key_t key, void value, btree_node_t *leaf_node)
112	{	112	{
113	btree_node_t *lnode;	113	btree_node_t *lnode;
114		114
115	ASSERT(value);	115	ASSERT(value);
116		116
Line 130...	Line 130...
130	* @param key Key to be inserted.	130	* @param key Key to be inserted.
131	* @param value Value to be inserted.	131	* @param value Value to be inserted.
132	* @param rsubtree Right subtree of the inserted key.	132	* @param rsubtree Right subtree of the inserted key.
133	* @param node Start inserting into this node.	133	* @param node Start inserting into this node.
134	*/	134	*/
135	void _btree_insert(btree_t t, __native key, void value, btree_node_t rsubtree, btree_node_t node)	135	void _btree_insert(btree_t t, btree_key_t key, void value, btree_node_t rsubtree, btree_node_t node)
136	{	136	{
137	if (node->keys < BTREE_MAX_KEYS) {	137	if (node->keys < BTREE_MAX_KEYS) {
138	/*	138	/*
139	* Node conatins enough space, the key can be stored immediately.	139	* Node conatins enough space, the key can be stored immediately.
140	*/	140	*/
Line 149...	Line 149...
149	* The key-value-rsubtree triplet has been inserted because	149	* The key-value-rsubtree triplet has been inserted because
150	* some keys could have been moved to the right sibling.	150	* some keys could have been moved to the right sibling.
151	*/	151	*/
152	} else {	152	} else {
153	btree_node_t *rnode;	153	btree_node_t *rnode;
154	__native median;	154	btree_key_t median;
155		155
156	/*	156	/*
157	* Node is full and both siblings (if both exist) are full too.	157	* Node is full and both siblings (if both exist) are full too.
158	* Split the node and insert the smallest key from the node containing	158	* Split the node and insert the smallest key from the node containing
159	* bigger keys (i.e. the new node) into its parent.	159	* bigger keys (i.e. the new node) into its parent.
Line 191...	Line 191...
191	*	191	*
192	* @param B-tree.	192	* @param B-tree.
193	* @param key Key to be removed from the B-tree along with its associated value.	193	* @param key Key to be removed from the B-tree along with its associated value.
194	* @param leaf_node If not NULL, pointer to the leaf node where the key is found.	194	* @param leaf_node If not NULL, pointer to the leaf node where the key is found.
195	*/	195	*/
196	void btree_remove(btree_t t, __native key, btree_node_t leaf_node)	196	void btree_remove(btree_t t, btree_key_t key, btree_node_t leaf_node)
197	{	197	{
198	btree_node_t *lnode;	198	btree_node_t *lnode;
199		199
200	lnode = leaf_node;	200	lnode = leaf_node;
201	if (!lnode) {	201	if (!lnode) {
Line 211...	Line 211...
211	*	211	*
212	* @param B-tree.	212	* @param B-tree.
213	* @param key Key to be removed from the B-tree along with its associated value.	213	* @param key Key to be removed from the B-tree along with its associated value.
214	* @param node Node where the key being removed resides.	214	* @param node Node where the key being removed resides.
215	*/	215	*/
216	void _btree_remove(btree_t t, __native key, btree_node_t node)	216	void _btree_remove(btree_t t, btree_key_t key, btree_node_t node)
217	{	217	{
218	if (ROOT_NODE(node)) {	218	if (ROOT_NODE(node)) {
219	if (node->keys == 1 && node->subtree[0]) {	219	if (node->keys == 1 && node->subtree[0]) {
220	/*	220	/*
221	* Free the current root and set new root.	221	* Free the current root and set new root.
Line 288...	Line 288...
288	* @param key Key to be searched.	288	* @param key Key to be searched.
289	* @param leaf_node Address where to put pointer to visited leaf node.	289	* @param leaf_node Address where to put pointer to visited leaf node.
290	*	290	*
291	* @return Pointer to value or NULL if there is no such key.	291	* @return Pointer to value or NULL if there is no such key.
292	*/	292	*/
293	void btree_search(btree_t t, __native key, btree_node_t **leaf_node)	293	void btree_search(btree_t t, btree_key_t key, btree_node_t **leaf_node)
294	{	294	{
295	btree_node_t cur, next;	295	btree_node_t cur, next;
296		296
297	/*	297	/*
298	* Iteratively descend to the leaf that can contain the searched key.	298	* Iteratively descend to the leaf that can contain the searched key.
Line 414...	Line 414...
414	* @param node B-tree node into wich the new key is to be inserted.	414	* @param node B-tree node into wich the new key is to be inserted.
415	* @param key The key to be inserted.	415	* @param key The key to be inserted.
416	* @param value Pointer to value to be inserted.	416	* @param value Pointer to value to be inserted.
417	* @param lsubtree Pointer to the left subtree.	417	* @param lsubtree Pointer to the left subtree.
418	*/	418	*/
419	void node_insert_key_and_lsubtree(btree_node_t node, __native key, void value, btree_node_t *lsubtree)	419	void node_insert_key_and_lsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *lsubtree)
420	{	420	{
421	int i;	421	int i;
422		422
423	for (i = 0; i < node->keys; i++) {	423	for (i = 0; i < node->keys; i++) {
424	if (key < node->key[i]) {	424	if (key < node->key[i]) {
Line 450...	Line 450...
450	* @param node B-tree node into wich the new key is to be inserted.	450	* @param node B-tree node into wich the new key is to be inserted.
451	* @param key The key to be inserted.	451	* @param key The key to be inserted.
452	* @param value Pointer to value to be inserted.	452	* @param value Pointer to value to be inserted.
453	* @param rsubtree Pointer to the right subtree.	453	* @param rsubtree Pointer to the right subtree.
454	*/	454	*/
455	void node_insert_key_and_rsubtree(btree_node_t node, __native key, void value, btree_node_t *rsubtree)	455	void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree)
456	{	456	{
457	int i;	457	int i;
458		458
459	for (i = 0; i < node->keys; i++) {	459	for (i = 0; i < node->keys; i++) {
460	if (key < node->key[i]) {	460	if (key < node->key[i]) {
Line 482...	Line 482...
482	* is removed from the node as well.	482	* is removed from the node as well.
483	*	483	*
484	* @param node B-tree node.	484	* @param node B-tree node.
485	* @param key Key to be removed.	485	* @param key Key to be removed.
486	*/	486	*/
487	void node_remove_key_and_lsubtree(btree_node_t *node, __native key)	487	void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
488	{	488	{
489	int i, j;	489	int i, j;
490		490
491	for (i = 0; i < node->keys; i++) {	491	for (i = 0; i < node->keys; i++) {
492	if (key == node->key[i]) {	492	if (key == node->key[i]) {
Line 510...	Line 510...
510	* is removed from the node as well.	510	* is removed from the node as well.
511	*	511	*
512	* @param node B-tree node.	512	* @param node B-tree node.
513	* @param key Key to be removed.	513	* @param key Key to be removed.
514	*/	514	*/
515	void node_remove_key_and_rsubtree(btree_node_t *node, __native key)	515	void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
516	{	516	{
517	int i, j;	517	int i, j;
518		518
519	for (i = 0; i < node->keys; i++) {	519	for (i = 0; i < node->keys; i++) {
520	if (key == node->key[i]) {	520	if (key == node->key[i]) {
Line 547...	Line 547...
547	* @param rsubtree Pointer to the right subtree of the key being added.	547	* @param rsubtree Pointer to the right subtree of the key being added.
548	* @param median Address in memory, where the median key will be stored.	548	* @param median Address in memory, where the median key will be stored.
549	*	549	*
550	* @return Newly created right sibling of node.	550	* @return Newly created right sibling of node.
551	*/	551	*/
552	btree_node_t node_split(btree_node_t node, __native key, void value, btree_node_t rsubtree, __native *median)	552	btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median)
553	{	553	{
554	btree_node_t *rnode;	554	btree_node_t *rnode;
555	int i, j;	555	int i, j;
556		556
557	ASSERT(median);	557	ASSERT(median);
Line 682...	Line 682...
682	* @param rnode Right sibling.	682	* @param rnode Right sibling.
683	* @param idx Index of the parent node key that is taking part in the rotation.	683	* @param idx Index of the parent node key that is taking part in the rotation.
684	*/	684	*/
685	void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx)	685	void rotate_from_left(btree_node_t lnode, btree_node_t rnode, index_t idx)
686	{	686	{
687	__native key;	687	btree_key_t key;
688		688
689	key = lnode->key[lnode->keys - 1];	689	key = lnode->key[lnode->keys - 1];
690		690
691	if (LEAF_NODE(lnode)) {	691	if (LEAF_NODE(lnode)) {
692	void *value;	692	void *value;
Line 719...	Line 719...
719	* @param rnode Right sibling.	719	* @param rnode Right sibling.
720	* @param idx Index of the parent node key that is taking part in the rotation.	720	* @param idx Index of the parent node key that is taking part in the rotation.
721	*/	721	*/
722	void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx)	722	void rotate_from_right(btree_node_t lnode, btree_node_t rnode, index_t idx)
723	{	723	{
724	__native key;	724	btree_key_t key;
725		725
726	key = rnode->key[0];	726	key = rnode->key[0];
727		727
728	if (LEAF_NODE(rnode)) {	728	if (LEAF_NODE(rnode)) {
729	void *value;	729	void *value;
Line 758...	Line 758...
758	* @param insvalue Value to be inserted.	758	* @param insvalue Value to be inserted.
759	* @param rsubtree Right subtree of inskey.	759	* @param rsubtree Right subtree of inskey.
760	*	760	*
761	* @return True if the rotation was performed, false otherwise.	761	* @return True if the rotation was performed, false otherwise.
762	*/	762	*/
763	bool try_insert_by_rotation_to_left(btree_node_t node, __native inskey, void insvalue, btree_node_t *rsubtree)	763	bool try_insert_by_rotation_to_left(btree_node_t node, btree_key_t inskey, void insvalue, btree_node_t *rsubtree)
764	{	764	{
765	index_t idx;	765	index_t idx;
766	btree_node_t *lnode;	766	btree_node_t *lnode;
767		767
768	/*	768	/*
Line 805...	Line 805...
805	* @param insvalue Value to be inserted.	805	* @param insvalue Value to be inserted.
806	* @param rsubtree Right subtree of inskey.	806	* @param rsubtree Right subtree of inskey.
807	*	807	*
808	* @return True if the rotation was performed, false otherwise.	808	* @return True if the rotation was performed, false otherwise.
809	*/	809	*/
810	bool try_insert_by_rotation_to_right(btree_node_t node, __native inskey, void insvalue, btree_node_t *rsubtree)	810	bool try_insert_by_rotation_to_right(btree_node_t node, btree_key_t inskey, void insvalue, btree_node_t *rsubtree)
811	{	811	{
812	index_t idx;	812	index_t idx;
813	btree_node_t *rnode;	813	btree_node_t *rnode;
814		814
815	/*	815	/*

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/adt/btree.c – Rev 1164 → 1177