낭만리얼백구~ 세번째스토리

btree_t *alloc_btree(int inc_size, int data_size)
{
btree_t * bt ;
bt->dy = alloc_dy_array(inc_size, data_size);
bt->root = -1 ;
bt->data_size = data_size ;

return bt ;
}

void free_btree(btree_t *bt)
{
if(bt->dy) free_dy_array(bt->dy);
bt->root = 0;
bt->data_size = 0;
}

int bt_clear(btree_t *bt)
{
bt->root = -1;
dy_clear(bt->dy);
}

int bt_get_itemnum(btree_t *bt)
{
return dy_get_itemnum(bt->dy);
}

int bt_insert_item(btree_t *bt, void *data, tree_comp comp, tree_equal equal,void *tmp_data)
{
long cur, data_pos, *ins_pos ;
sambuf_t *al ;
int cmp, gap ;

al = bt->dy->lists_real ;
cur = bt->root ;

if( cur == -1 )
{
if((data_pos=dy_add_item(bt->dy,data)) < 0) return data_pos ;
bt->root = data_pos ;
memcpy((char *)al->data+al->data_size*data_pos+bt->data_size,&cur,LS);
memcpy((char *)al->data+al->data_size*data_pos+bt->data_size+LS,&cur,LS);

return SMDK_NO_ERROR ;
}

while( 1 )
{
cmp = comp(dy_get_item(bt->dy,cur), data, tmp_data);
if( cmp > 0 )
{
ins_pos = (long *)((char *)al->data+al->data_size*cur+bt->data_size);
}
else if( cmp < 0 )
{
ins_pos = (long *)((char *)al->data+al->data_size*cur+bt->data_size+LS);
}
else
{
if( equal )
{
equal((void *)((char *)al->data+al->data_size*cur),data);
return 0;
}
}

if( *ins_pos==-1) break;
cur = *ins_pos ;
}

gap = (int)ins_pos - (int)al->data ;
if((data_pos=dy_add_item(bt->dy,data))<0) return data_pos ;

ins_pos = (long *)((char *)al->data + gap);

memcpy((char *)al->data+al->data_size*data_pos+bt->data_size, ins_pos, LS);
memcpy((char *)al->data+al->data_size*data_pos+bt->data_size+LS,ins_pos, LS);
memcpy(ins_pos, &data_pos, LS);

return SMDK_NO_ERROR ;
}

int bt_delete_item(btree_t *bt, void *data, tree_comp comp, void *tmp_data)
{
long data_pos, tmp_pos, prev_pos, *left, *right;
long *cur, *prev, *tmp ;
sambuf_t *al ;

if((data_pos=bt_search(bt, data, &prev_pos, comp, tmp_data)) < 0) return data_pos ;

al = bt->dy->lists_real ;

left = (long *)((char *)al->data+al->data_size*data_pos*bt->data_size);
right = left + 1;

// binary tree 재구성.
if( *left!=-1 )
{
if( *right!=-1 )
{
cur = right ;
prev = NULL ;

while(1)
{
//왼쪽자식이 없을때까지..
tmp = (long *)((char *)al->data+al->data_size*(*cur)+bt->data_size);
if( *tmp==-1 )
{
*cur = *left ;
memcpy((char *)al->data+al->data_size*data_pos,(char *)al->data+al->data_size*(*cur),al->data_size);

//가장 왼쪽에 부모노드가 있으면
if( prev!=NULL )
{
tmp = (long *)((char *)al->data+al->data_size*(*prev)+bt->data_size);
*tmp = -1 ;
tmp_pos = *cur ;
}
else
{
memcpy((char *)al->data+al->data_size*(*cur),(char *)al->data+al->data_size*(*tmp),al->data_size);
tmp_pos = *tmp ;
}
}
else
{
tmp_pos = *cur ;
}

break;
}//while(1)..

prev = cur ;
cur = tmp ;
}
// right node가 없을때.
else
{
tmp_pos = *left ;
memcpy((char *)al->data+al->data_size*data_pos,(char *)al->data+al->data_size*tmp_pos,al->data_size);
}
}
// left node가 없을때.
else
{
// right node가 있을때.
if( *right!=-1)
{
tmp_pos = *right ;
memcpy((char *)al->data+al->data_size*data_pos,(char *)al->data+al->data_size*tmp_pos, al->data_size);
}
// right node가 없을때.
else
{
//지워지는 node의 자식 node가 없으면 부모의 자식 node를 -1로.
if( prev_pos==-1 )
{
bt->root = -1;
}
else
{
left = (long *)((char *)al->data+al->data_size*prev_pos+bt->data_size);
if( *left==data_pos ) *left = -1;
else *(left+1) = -1;
}

tmp_pos = data_pos ;
}
}

return dy_delete_item(bt->dy,tmp_pos);
}