Changeset 70

Show
Ignore:
Timestamp:
09/13/06 21:26:53 (4 years ago)
Author:
aqua
Message:

btree is almost completed -_-;; (I think so );;

Location:
btree/src
Files:
3 modified

Legend:

Unmodified
Added
Removed

  • btree/src/btree.c

    r60 r70  
    99 
    1010/* get depth of btree */ 
    11 int get_depth( btree* tree ){ 
    12  
    13         char    buf[BLOCK_SIZE]; 
     11static int get_depth( btree* tree ){ 
     12 
     13        char buf[BLOCK_SIZE]; 
    1414        int     depth = 0; 
    1515        int     offset = tree->root; 
    … …  
    2121                /* get prev child node */ 
    2222                lseek( tree->fd, offset, SEEK_SET ); 
    23                 read( tree->fd, buf, BLOCK_SIZE ); 
     23                read(  tree->fd, buf, BLOCK_SIZE ); 
    2424                node = (btree_node*) buf;                
    2525                depth++; 
    … …  
    2929 
    3030        return depth; 
     31 
     32} 
     33 
     34/*  
     35 * new block (EOF offset)  
     36 */ 
     37static int btree_new_block( btree* tree ){ 
     38 
     39        return lseek( tree->fd, 0, SEEK_END ); 
     40 
     41} 
     42 
     43/*  
     44 * writing one block  
     45 */ 
     46static void btree_write_block( btree* tree, int offset, char* buf ){ 
     47 
     48        lseek( tree->fd, offset, SEEK_SET ); 
     49        write( tree->fd,  buf, BLOCK_SIZE ); 
     50 
     51} 
     52 
     53/*  
     54 * reading one block & casting it to btree_node  
     55 */ 
     56static btree_node* btree_read_block( btree* tree, int offset, char* buf ){ 
     57 
     58        lseek( tree->fd, offset, SEEK_SET ); 
     59        read( tree->fd,  buf, BLOCK_SIZE ); 
     60 
     61        return (btree_node*)buf; 
    3162 
    3263} 
    … …  
    5384                new->depth = get_depth( new ); 
    5485        } 
    55         else 
     86        else { 
    5687                /* empty tree */ 
    57                 new->depth = -1; 
     88                new->root = -1; 
     89                new->depth = 0; 
     90        } 
    5891 
    5992        return new; 
    6093         
     94} 
     95 
     96static void  
     97btree_insert_to_node( btree* tree, btree_node* node, btree_entry* var ){ 
     98 
     99        int i; 
     100 
     101        /* wrong compare function */ 
     102        for( i = node->n ; i > 0 ; i-- ){ 
     103 
     104                fprintf( stderr, "%d::\n", i ); 
     105                //if( tree->compare( node->entry[i-1].value, var->value) > 0 ) 
     106                if( tree->compare( &(node->entry[i-1]), var ) > 0 ) 
     107                        memcpy(&(node->entry[i]), &(node->entry[i-1]), sizeof(btree_entry)); 
     108                else { 
     109                        memcpy(&(node->entry[i]), var, sizeof(btree_entry) ); 
     110                        break; 
     111                } 
     112 
     113        } 
     114        (node->n)++; 
     115 
     116} 
     117 
     118static btree_entry*  
     119btree_split_node( btree* tree, btree_node* c, btree_entry* v ){ 
     120 
     121        static btree_entry ret; 
     122        btree_node* n; 
     123 
     124        char buf[BLOCK_SIZE]; 
     125        int  left, i, j; 
     126 
     127#ifdef DEBUG 
     128        memset(buf, 0, BLOCK_SIZE); 
     129#endif 
     130        n = (btree_node*)buf; 
     131 
     132        // split data to new node *has bug backward first */ 
     133        left = c->n - ENTRY_PER_NODE/2; 
     134        for( i = (ENTRY_PER_NODE/2-1), j = (c->n-1) ; i >= 0 ; i--, j-- ){ 
     135 
     136                if( tree->compare(&(c->entry[j]), v) > 0 ) 
     137                        memcpy( &(n->entry[i]), &(c->entry[j]), sizeof(btree_entry) ); 
     138 
     139                else { 
     140                        memcpy( &(n->entry[i]), v, sizeof(btree_entry) ); 
     141                        break; 
     142                } 
     143 
     144        } 
     145        for( ; i >= 0 ; i--, j-- ) 
     146                memcpy( &(n->entry[i]), &(c->entry[j]), sizeof(btree_entry) ); 
     147 
     148        // adjust n 
     149        c->n = left; 
     150        n->n = ENTRY_PER_NODE/2; 
     151 
     152        // if var is not inserted yet, insert it. 
     153        if( j == (left-1) ) 
     154                btree_insert_to_node( tree, c, v ); 
     155 
     156        // var is inserted already, node->entry[left] goes upper node; 
     157        c->n = left;  
     158 
     159        memcpy( &ret, &(c->entry[left]), sizeof(btree_entry) ); 
     160        ret.child = btree_new_block( tree ); 
     161 
     162        n->child = c->entry[left].child; 
     163         
     164        /* write the splitted node */ 
     165        btree_write_block( tree, ret.child, buf ); 
     166 
     167        return &ret; 
     168 
    61169} 
    62170 
    … …  
    71179 *    will help using this btree with general purpose. 
    72180 */ 
    73 int btree_insert( btree* tree,          /* tree pointer */  
    74                   int cur,              /* offset of current node */ 
    75                   btree_entry* var,     /* which should be inserted */ 
    76                   btree_node* p_node,   /* parent_node */ 
    77                   int p_nth             /* parent entry's id */ 
    78                 ){ 
    79  
    80         btree_node* node, tmp_node; 
    81         static btree_entry entry; 
    82  
     181btree_entry* btree_real_insert( btree* tree, int cur, btree_entry* var ){ 
     182 
     183        btree_node* node; 
     184        btree_entry* up; 
     185         
    83186        char buf[BLOCK_SIZE]; 
    84         char tmp[BLOCK_SIZE]; 
    85  
    86         int nth; 
    87         int l, r; 
     187        int i, l, r, c; 
     188 
     189        if( cur < 0 ){ 
     190                return var; 
     191        } 
    88192 
    89193        /* get node */ 
    90         // lseek 
    91         // read 
    92         node = (btree_node*)buf; 
    93  
    94         /* get MAX_ENTRY(whose key isn't bigger than the key) */ 
    95         // binary_search ... 
    96  
    97         /* if the entry has the key we find then update entry & write */ 
    98         // compare node->entry[nth].key == var.key, then update it 
    99         // write  
    100         // return NULL; 
    101  
    102         /* 
    103          * else if there exist child of the entry,  
    104          *   call btree_insert( extry->child, .... ) recursively; 
    105          *     if it doesn't return NULL , we need to insert the entry  
    106          */ 
    107         if( 0 /* when first entry's key is bigger than var's key */ ) 
    108                 if( btree_insert( tree, node->child, var, node, -1 ) ) 
    109                         var = &entry; 
    110                 else  
    111                         return 0; 
     194        node = btree_read_block( tree, cur, buf ); 
     195 
     196        /* binary_search  */ 
     197        l = 0; 
     198        r = node->n - 1; 
     199        while ( l <= r ){ 
     200                c = (r + l) / 2; 
     201                i = tree->compare( &(node->entry[c]), var ); 
     202 
     203                if( i <  0 )            // less 
     204                        l = c + 1; 
     205                else if( i > 0 )        // greater 
     206                        r = c - 1; 
     207                else {                          // same: update it & write & return; 
     208                        node->entry[c].value++; 
     209                        btree_write_block( tree, cur, buf ); 
     210                        return NULL; 
     211                } 
     212        } 
     213 
     214        /* when first entry's key is bigger than var's key */  
     215        if( r < 0 ) 
     216                up = btree_real_insert( tree, node->child, var ); 
    112217        else  
    113                 if( btree_insert(tree, node->entry[nth].child, var, node, nth) ) 
    114                         var = &entry; 
    115                 else 
    116                         return 0;  
    117  
    118         /* 
    119          * else  
    120          *   1. enough space in this node  
    121          *      -> insert & write 
    122          *   2. enough space in prev node  
    123          *      -> divide to previous node and insert the key 
    124          *   3. enough space in next node 
    125          *      -> divide to next node and insert the key 
    126          *   4. there's no space among prev, cur, next node, 
    127          *      -> split the node 
    128          */ 
     218                up = btree_real_insert( tree, node->entry[c].child, var ); 
     219 
     220        /* if child node is splitted, then insert returned entry to current node */ 
     221        if( up != NULL )  
     222                var = up; 
     223        else 
     224                return NULL;  
     225 
     226        /* If there's enough space then insert & wrtie block */ 
    129227        if( node->n < ENTRY_PER_NODE ){ 
    130                 // insert  
    131                 // write  
    132                 return 0; 
    133         } 
    134          
    135         // tmp_node = get_node( prev ); 
    136         // divide to prev node if possible 
    137         { 
    138                 // btree_divide( prev, cur, p, p_nth, 0 ) 
    139                 // write prev 
    140                 // write cur 
    141                 // write parent 
    142                 return 0; 
    143         } 
    144  
    145         // tmp_node = get_node( next ); 
    146         // divide to next node if possible 
    147         { 
    148                 // btree_divide( cur, next, p, p_nth, 0 ) 
    149                 // write cur 
    150                 // write next 
    151                 // write parent 
    152                 return 0; 
    153         } 
    154  
    155         // split node 
    156         { 
    157                 int is_root; 
    158                 if( node->prev_node == -1 && node->next_node == -1 ) 
    159                         is_root = 1; 
    160                 else 
    161                         is_root = 0; 
    162  
    163                 // split data to new node 
    164                 // memset(tmp_node, 0, BLOCK_SIZE); 
    165                 // move move 
    166  
    167                 // adjust n 
    168                 // node->n = ...; 
    169  
    170                 // finally fill the entry (return value) 
    171                 // never change entry variable before here... 
    172  
    173                 /* 
    174                  * if the node is splitted and this node was root, 
    175                  *      then create new root node & write it  
    176                  * 
    177                  * if there's no prev & next node, we can assume it's root node 
    178                  */ 
    179                 if( is_root ) 
    180                         //do_something 
    181                         ; 
    182  
    183                 return 1; 
    184         } 
    185  
     228                btree_insert_to_node( tree, node, var ); 
     229                btree_write_block( tree, cur, buf ); 
     230                return NULL; 
     231        } 
     232        /* else split is required */  
     233        up = btree_split_node( tree, node, var ); 
     234 
     235        /* write current node */ 
     236        btree_write_block( tree, cur, buf ); 
     237 
     238        return up; 
     239 
     240} 
     241 
     242void btree_insert( btree* tree, char* key ){ 
     243 
     244        btree_entry kvar; 
     245        btree_entry* up; 
     246 
     247        btree_node* node; 
     248 
     249        char buf[BLOCK_SIZE]; 
     250 
     251        strncpy( kvar.key, key, KEY_SIZE-1 ); 
     252        kvar.key[KEY_SIZE-1] ='\0'; 
     253 
     254        kvar.value = 1; 
     255        kvar.child = -1; 
     256 
     257        /* if tree is empty */ 
     258        if( tree->depth < 0 ) 
     259                up = &kvar;              
     260        else 
     261                up = btree_real_insert( tree, tree->root, &kvar ); 
     262 
     263        if( up != NULL ){ 
     264#ifdef DEBUG 
     265                memset(buf, 0, BLOCK_SIZE); 
     266#endif 
     267                node = (btree_node*) buf; 
     268                node->n = 1; 
     269                node->child = tree->root; 
     270                memcpy( &(node->entry[0]), up, sizeof(btree_entry) ); 
     271 
     272                tree->root = btree_new_block(tree); 
     273                btree_write_block( tree, tree->root, buf ); 
     274 
     275                tree->depth++; 
     276        } 
    186277} 
    187278 
    … …  
    261352//void btree_update( btree* root, char* key, int value ); 
    262353 
     354int compare( btree_entry* v1, btree_entry* v2 ){ 
     355 
     356        return strcmp(v1->key, v2->key); 
     357 
     358} 
     359 
    263360int main( int argc, char** argv ){ 
    264361        btree* tree; 
    265362 
    266363        tree = btree_open( "test.idx" ); 
     364        tree->compare = &compare; 
    267365        if( tree == NULL ){ 
    268366                printf( "failed to open test.idx\n" ); 
    … …  
    270368        } 
    271369          
     370        btree_insert( tree, "1234" ); 
     371 
    272372        printf( "root node is in offset %d\n", tree->root ); 
    273373        btree_print( tree ); 

  • btree/src/btree.h

    r58 r70  
    2828        int     root;   /* offset of root node */ 
    2929        int     depth;  /* depth of tree */ 
     30        int (*compare)( btree_entry* l, btree_entry* r ); 
    3031} btree; 
    3132 

  • btree/src/test.c

    r58 r70  
    11#include <stdio.h> 
     2#include <stdlib.h> 
     3 
     4#include <string.h> 
    25 
    36#include "btree.h"