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



 *
 * @param root Root of the subtree.
 */
void btree_destroy_subtree(btree_node_t *root)
{
    count_t i;
 
    if (root->keys) {
        for (i = 0; i < root->keys + 1; i++) {
            if (root->subtree[i])
                btree_destroy_subtree(root->subtree[i]);

        if (!try_rotation_from_left(node))
            try_rotation_from_right(node);
    }
   
    if (node->keys > FILL_FACTOR) {
        count_t i;
 
        /*
         * The key can be immediatelly removed.
         *
         * Note that the right subtree is removed because when

        if (key < cur->key[0]) {
            next = cur->subtree[0];
            continue;
        } else {
            void *val;
            count_t i;
       
            /*
             * Now if the key is smaller than cur->key[i]
             * it can only mean that the value is in cur->subtree[i]
             * or it is not in the tree at all.

 * @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)
{
    count_t i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {
            count_t j;
       
            for (j = node->keys; j > i; j--) {
                node->key[j] = node->key[j - 1];
                node->value[j] = node->value[j - 1];
                node->subtree[j + 1] = node->subtree[j];

 * @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)
{
    count_t i;
 
    for (i = 0; i < node->keys; i++) {
        if (key < node->key[i]) {
            count_t j;
       
            for (j = node->keys; j > i; j--) {
                node->key[j] = node->key[j - 1];
                node->value[j] = node->value[j - 1];
                node->subtree[j + 1] = node->subtree[j];

 * @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)
{
    count_t i, j;
   
    for (i = 0; i < node->keys; i++) {
        if (key == node->key[i]) {
            for (j = i + 1; j < node->keys; j++) {
                node->key[j - 1] = node->key[j];

 * @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)
{
    count_t i, j;
   
    for (i = 0; i < node->keys; i++) {
        if (key == node->key[i]) {
            for (j = i + 1; j < node->keys; j++) {
                node->key[j - 1] = node->key[j];

 * @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;
    count_t i, j;
 
    ASSERT(median);
    ASSERT(node->keys == BTREE_MAX_KEYS);
 
    /*

   
    /*
     * Copy big keys, values and subtree pointers to the new right sibling.
     * If this is an index node, do not copy the median.
     */
    i = (count_t) INDEX_NODE(node);
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
        rnode->key[j] = node->key[i];
        rnode->value[j] = node->value[i];
        rnode->subtree[j] = node->subtree[i];
       

 */
btree_node_t *node_combine(btree_node_t *node)
{
    index_t idx;
    btree_node_t *rnode;
    count_t i;
 
    ASSERT(!ROOT_NODE(node));
   
    idx = find_key_by_subtree(node->parent, node, false);
    if (idx == node->parent->keys) {

 *
 * @return Index of the key associated with the subtree.
 */
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
{
    count_t i;
   
    for (i = 0; i < node->keys + 1; i++) {
        if (subtree == node->subtree[i])
            return i - (int) (right != false);
    }

 *
 * @param t Print out B-tree.
 */
void btree_print(btree_t *t)
{
    count_t i;
    int depth = t->root->depth;
    link_t head, *cur;
 
    printf("Printing B-tree:\n");
    list_initialize(&head);
    list_append(&t->root->bfs_link, &head);

Rev 2089	Rev 2111
Line 135...	Line 135...
135	*	135	*
136	* @param root Root of the subtree.	136	* @param root Root of the subtree.
137	*/	137	*/
138	void btree_destroy_subtree(btree_node_t *root)	138	void btree_destroy_subtree(btree_node_t *root)
139	{	139	{
140	int i;	140	count_t i;
141		141
142	if (root->keys) {	142	if (root->keys) {
143	for (i = 0; i < root->keys + 1; i++) {	143	for (i = 0; i < root->keys + 1; i++) {
144	if (root->subtree[i])	144	if (root->subtree[i])
145	btree_destroy_subtree(root->subtree[i]);	145	btree_destroy_subtree(root->subtree[i]);
Line 267...	Line 267...
267	if (!try_rotation_from_left(node))	267	if (!try_rotation_from_left(node))
268	try_rotation_from_right(node);	268	try_rotation_from_right(node);
269	}	269	}
270		270
271	if (node->keys > FILL_FACTOR) {	271	if (node->keys > FILL_FACTOR) {
272	int i;	272	count_t i;
273		273
274	/*	274	/*
275	* The key can be immediatelly removed.	275	* The key can be immediatelly removed.
276	*	276	*
277	* Note that the right subtree is removed because when	277	* Note that the right subtree is removed because when
Line 333...	Line 333...
333	if (key < cur->key[0]) {	333	if (key < cur->key[0]) {
334	next = cur->subtree[0];	334	next = cur->subtree[0];
335	continue;	335	continue;
336	} else {	336	} else {
337	void *val;	337	void *val;
338	int i;	338	count_t i;
339		339
340	/*	340	/*
341	* Now if the key is smaller than cur->key[i]	341	* Now if the key is smaller than cur->key[i]
342	* it can only mean that the value is in cur->subtree[i]	342	* it can only mean that the value is in cur->subtree[i]
343	* or it is not in the tree at all.	343	* or it is not in the tree at all.
Line 440...	Line 440...
440	* @param value Pointer to value to be inserted.	440	* @param value Pointer to value to be inserted.
441	* @param lsubtree Pointer to the left subtree.	441	* @param lsubtree Pointer to the left subtree.
442	*/	442	*/
443	void node_insert_key_and_lsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *lsubtree)	443	void node_insert_key_and_lsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *lsubtree)
444	{	444	{
445	int i;	445	count_t i;
446		446
447	for (i = 0; i < node->keys; i++) {	447	for (i = 0; i < node->keys; i++) {
448	if (key < node->key[i]) {	448	if (key < node->key[i]) {
449	int j;	449	count_t j;
450		450
451	for (j = node->keys; j > i; j--) {	451	for (j = node->keys; j > i; j--) {
452	node->key[j] = node->key[j - 1];	452	node->key[j] = node->key[j - 1];
453	node->value[j] = node->value[j - 1];	453	node->value[j] = node->value[j - 1];
454	node->subtree[j + 1] = node->subtree[j];	454	node->subtree[j + 1] = node->subtree[j];
Line 476...	Line 476...
476	* @param value Pointer to value to be inserted.	476	* @param value Pointer to value to be inserted.
477	* @param rsubtree Pointer to the right subtree.	477	* @param rsubtree Pointer to the right subtree.
478	*/	478	*/
479	void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree)	479	void node_insert_key_and_rsubtree(btree_node_t node, btree_key_t key, void value, btree_node_t *rsubtree)
480	{	480	{
481	int i;	481	count_t i;
482		482
483	for (i = 0; i < node->keys; i++) {	483	for (i = 0; i < node->keys; i++) {
484	if (key < node->key[i]) {	484	if (key < node->key[i]) {
485	int j;	485	count_t j;
486		486
487	for (j = node->keys; j > i; j--) {	487	for (j = node->keys; j > i; j--) {
488	node->key[j] = node->key[j - 1];	488	node->key[j] = node->key[j - 1];
489	node->value[j] = node->value[j - 1];	489	node->value[j] = node->value[j - 1];
490	node->subtree[j + 1] = node->subtree[j];	490	node->subtree[j + 1] = node->subtree[j];
Line 508...	Line 508...
508	* @param node B-tree node.	508	* @param node B-tree node.
509	* @param key Key to be removed.	509	* @param key Key to be removed.
510	*/	510	*/
511	void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)	511	void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
512	{	512	{
513	int i, j;	513	count_t i, j;
514		514
515	for (i = 0; i < node->keys; i++) {	515	for (i = 0; i < node->keys; i++) {
516	if (key == node->key[i]) {	516	if (key == node->key[i]) {
517	for (j = i + 1; j < node->keys; j++) {	517	for (j = i + 1; j < node->keys; j++) {
518	node->key[j - 1] = node->key[j];	518	node->key[j - 1] = node->key[j];
Line 536...	Line 536...
536	* @param node B-tree node.	536	* @param node B-tree node.
537	* @param key Key to be removed.	537	* @param key Key to be removed.
538	*/	538	*/
539	void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)	539	void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
540	{	540	{
541	int i, j;	541	count_t i, j;
542		542
543	for (i = 0; i < node->keys; i++) {	543	for (i = 0; i < node->keys; i++) {
544	if (key == node->key[i]) {	544	if (key == node->key[i]) {
545	for (j = i + 1; j < node->keys; j++) {	545	for (j = i + 1; j < node->keys; j++) {
546	node->key[j - 1] = node->key[j];	546	node->key[j - 1] = node->key[j];
Line 574...	Line 574...
574	* @return Newly created right sibling of node.	574	* @return Newly created right sibling of node.
575	*/	575	*/
576	btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median)	576	btree_node_t node_split(btree_node_t node, btree_key_t key, void value, btree_node_t rsubtree, btree_key_t *median)
577	{	577	{
578	btree_node_t *rnode;	578	btree_node_t *rnode;
579	int i, j;	579	count_t i, j;
580		580
581	ASSERT(median);	581	ASSERT(median);
582	ASSERT(node->keys == BTREE_MAX_KEYS);	582	ASSERT(node->keys == BTREE_MAX_KEYS);
583		583
584	/*	584	/*
Line 601...	Line 601...
601		601
602	/*	602	/*
603	* Copy big keys, values and subtree pointers to the new right sibling.	603	* Copy big keys, values and subtree pointers to the new right sibling.
604	* If this is an index node, do not copy the median.	604	* If this is an index node, do not copy the median.
605	*/	605	*/
606	i = (int) INDEX_NODE(node);	606	i = (count_t) INDEX_NODE(node);
607	for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {	607	for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
608	rnode->key[j] = node->key[i];	608	rnode->key[j] = node->key[i];
609	rnode->value[j] = node->value[i];	609	rnode->value[j] = node->value[i];
610	rnode->subtree[j] = node->subtree[i];	610	rnode->subtree[j] = node->subtree[i];
611		611
Line 636...	Line 636...
636	*/	636	*/
637	btree_node_t node_combine(btree_node_t node)	637	btree_node_t node_combine(btree_node_t node)
638	{	638	{
639	index_t idx;	639	index_t idx;
640	btree_node_t *rnode;	640	btree_node_t *rnode;
641	int i;	641	count_t i;
642		642
643	ASSERT(!ROOT_NODE(node));	643	ASSERT(!ROOT_NODE(node));
644		644
645	idx = find_key_by_subtree(node->parent, node, false);	645	idx = find_key_by_subtree(node->parent, node, false);
646	if (idx == node->parent->keys) {	646	if (idx == node->parent->keys) {
Line 685...	Line 685...
685	*	685	*
686	* @return Index of the key associated with the subtree.	686	* @return Index of the key associated with the subtree.
687	*/	687	*/
688	index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right)	688	index_t find_key_by_subtree(btree_node_t node, btree_node_t subtree, bool right)
689	{	689	{
690	int i;	690	count_t i;
691		691
692	for (i = 0; i < node->keys + 1; i++) {	692	for (i = 0; i < node->keys + 1; i++) {
693	if (subtree == node->subtree[i])	693	if (subtree == node->subtree[i])
694	return i - (int) (right != false);	694	return i - (int) (right != false);
695	}	695	}
Line 938...	Line 938...
938	*	938	*
939	* @param t Print out B-tree.	939	* @param t Print out B-tree.
940	*/	940	*/
941	void btree_print(btree_t *t)	941	void btree_print(btree_t *t)
942	{	942	{
-		943	count_t i;
943	int i, depth = t->root->depth;	944	int depth = t->root->depth;
944	link_t head, *cur;	945	link_t head, *cur;
945		946
946	printf("Printing B-tree:\n");	947	printf("Printing B-tree:\n");
947	list_initialize(&head);	948	list_initialize(&head);
948	list_append(&t->root->bfs_link, &head);	949	list_append(&t->root->bfs_link, &head);

Subversion Repositories HelenOS

(root)/trunk/kernel/generic/src/adt/btree.c – Rev 2089 → 2111