squillace91
3/23/2013 - 5:11 PM
B_tree funcionando tudo certinho, mas quando voce busca e depois insere, é inserido um lixo no final. ela está tratando a incializacao.
B_tree funcionando tudo certinho, mas quando voce busca e depois insere, é inserido um lixo no final. ela está tratando a incializacao.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include "b_tree_atual.h"
int main() {
Chave chave, inicializadora;
short rrn, pos;
strcpy(inicializadora.chave, "SHE01\0");
BTPAGE page;
if (btopen()){ /* try to open btree.dat and get root */
root = getroot();
printf("Arquivo de índice aberto com sucesso!\n");
}
else
root = create_tree(inicializadora); /* if btree.dat not there, create it */
//Insercoes
strcpy(chave.chave, "BBB02\0");
chave.rrn_dados = 22;
insert(root, chave);
strcpy(chave.chave, "CCC02\0");
insert(root, chave);
strcpy(chave.chave, "DDD02\0");
insert(root, chave);
strcpy(chave.chave, "EEE02\0");
insert(root, chave);
strcpy(chave.chave, "FFF02\0");
insert(root, chave);
strcpy(chave.chave, "GGG02\0");
insert(root, chave);
strcpy(chave.chave, "HHH02\0");
insert(root, chave);
strcpy(chave.chave, "III02\0");
chave.rrn_dados = 32;
insert(root, chave);
strcpy(chave.chave, "JJJ02\0");
insert(root, chave);
strcpy(chave.chave, "KKK02\0");
insert(root, chave);
strcpy(chave.chave, "LLL02\0");
insert(root, chave);
strcpy(chave.chave, "MMM02\0");
insert(root, chave);
strcpy(chave.chave, "NNN02\0");
insert(root, chave);
strcpy(chave.chave, "OOO02\0");
insert(root, chave);
strcpy(chave.chave, "PPP02\0");
insert(root, chave);
strcpy(chave.chave, "QQQ02\0");
insert(root, chave);
strcpy(chave.chave, "RRR02\0");
insert(root, chave);
strcpy(chave.chave, "SSS02\0");
chave.rrn_dados = 45;
insert(root, chave);
strcpy(chave.chave, "TTT02\0");
insert(root, chave);
strcpy(chave.chave, "UUU02\0");
insert(root, chave);
strcpy(chave.chave, "VVV02\0");
insert(root, chave);
strcpy(chave.chave, "VVX02\0");
insert(root, chave);
strcpy(chave.chave, "VVW02\0");
insert(root, chave);
strcpy(chave.chave, "WWW02\0");
insert(root, chave);
strcpy(chave.chave, "WWY02\0");
insert(root, chave);
strcpy(chave.chave, "YYY02\0");
insert(root, chave);
strcpy(chave.chave, "XXX02\0");
insert(root, chave);
strcpy(chave.chave, "ZZZ02\0");
insert(root, chave);
printf("\n");
print_btree(root);
strcpy(chave.chave, "SSS02\0");
if (search_key_on_tree(root, chave, &rrn, &pos))
printf("RRN %d\n", rrn);
else
printf("Nao achouw\n");
// Removendo Chaves e usando print_btree pra visualizar e verificar
strcpy(chave.chave, "ZZZ02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
print_btree(root);
strcpy(chave.chave, "YYY02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
print_btree(root);
strcpy(chave.chave, "VVX02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
printf("\n\n");
print_btree(root);
strcpy(chave.chave, "PPP02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
printf("\n\n");
print_btree(root);
strcpy(chave.chave, "XXX02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
printf("\n\n");
print_btree(root);
strcpy(chave.chave, "UUU02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
strcpy(chave.chave, "VVV02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
printf("\n\n");
print_btree(root);
strcpy(chave.chave, "WWW02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
strcpy(chave.chave, "QQQ02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
strcpy(chave.chave, "RRR02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
strcpy(chave.chave, "VVW02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
strcpy(chave.chave, "WWY02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
printf("\n\n");
print_btree(root);
strcpy(chave.chave, "TTT02\0");
printf("\n\nREMOVENDO %s\n", chave.chave);
remove_key(root, chave);
printf("\n\n");
printf(" RAIZ %d\n", root);
print_btree(root);
//Procurando Chave
strcpy(chave.chave, "JJI02\0");
if (search_key_on_tree(root, chave, &rrn, &pos))
printf("RRN %d\n", rrn);
else
printf("Nao achouw\n");
btclose();
return 0;
}#ifndef INCLUDED_b_tree_atual
#define INCLUDED_b_tree_atual
#endif
//Constantes
#define MINKEYS 2
#define MAXKEYS 2*MINKEYS
#define NIL (-1)
#define NOKEY "#####"
#define NO 0
#define YES 1
//Declaração de estruturas
typedef struct Chave {
char chave[6];
long rrn_dados;
}Chave;
typedef struct BTPAGE{
short keycount; /* number of keys in page */
Chave key[MAXKEYS]; /* the actual keys */
long child[MAXKEYS + 1]; /* ptrs to rrns of descendants */
} BTPAGE;
#define PAGESIZE sizeof(BTPAGE)
//Variaveis globais
extern short root; /* rrn of root page */
extern FILE *btfd; /* file descriptor of btree file */
extern int infd; /* file descriptor of input file */
//Funcoes
void btclose();
int btopen();
BTPAGE btread(short rrn);
int btwrite(short rrn, BTPAGE *page_ptr);
short create_root(Chave key, short left, short right);
short create_tree();
short get_rrn_new_page();
short getroot();
void insert(short rrn, Chave key);
int recursive_insert(short rrn, Chave key, short *promo_r_child, Chave *promo_key);
void ins_in_page(Chave key, short r_child, BTPAGE *p_page);
void pageinit(BTPAGE *p_page);
void putroot(short root);
int search_node(Chave key, BTPAGE *p_page, short *pos);
void split(Chave key, short r_child, BTPAGE *p_oldpage, Chave *promo_key,
short *promo_r_child, BTPAGE *p_newpage);
int search_key_on_tree(short rrn, Chave key, short *found_rrn, short *found_pos);
void remove_key(short rrn, Chave key);
int recursive_remove_key(short rrn, Chave key, int *is_change, Chave *promo_key);
void fixup_page(short rrn, short pos, BTPAGE *page);
int redistribution(short rrn, short pos, Chave key, BTPAGE page);
void shellSort(Chave *vet, int size);
int concatenation(short rrn, short pos, Chave key, BTPAGE page);
void print_btree(short rrn);
void printPage(BTPAGE *page);#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stdio.h"
#include "sys/stat.h"
#include "fcntl.h"
#include "b_tree_atual.h"
// Ponteiro Global do Arquivo de Indice e Raiz, usado em todas as funções praticamente
FILE *btfd; /* global file descriptor for "btree.dat" */
short root;
/* Funcao para abrir o arquivo de indices para leitura e escrita binaria
* Retorna 0 Senão existe, e 1 se existe
*/
int btopen() {
btfd = fopen("index.dat", "r+b");
if (!btfd)
return 0;
else
return 1;
}
// fecha o arquivo de índice
void btclose() {
putroot(root);
fclose(btfd);
}
/* Le o primeiro short do arquivo de indice que é a raiz e retorna o valor
* caso contrário ERRO
*/
short getroot() {
short root;
fseek(btfd, 0L, 0);
if (fread(&root, sizeof(short), 1, btfd) == 0) {
printf("Error: Unable to get root.\007\n");
exit(1);
}
return root;
}
/* Sempre que há mudança no nivel da arvore, eh criada uma nova
* raiz, assim a função escreve no arquivo no inicio a nova raiz
*/
void putroot(short root) {
fseek(btfd, 0L, 0);
fwrite(&root, sizeof (short), 1, btfd);
}
/* Se arvore nao existe, cria arquivo de indice, cria a pagina raiz e
* adiciona a primeria chave pra nao ficar vazia e retorna o RRN da raiz
*/
short create_tree(Chave key) {
btfd = fopen("index.dat", "a+b");
fclose(btfd); /* Have to close and reopen to insure */
btopen(); /* read/write access on many systems. */
return (create_root(key, NIL, NIL));
}
/* Funcao usada no split pra pegar o RRN da proxima pagina a ser adicionada
* no final do arquivo, retorna esse RRN
*/
short get_rrn_new_page() {
long addr;
fseek(btfd, 0L, SEEK_END);
addr = ftell(btfd);
return ((short) addr / PAGESIZE);
}
/* Retorna a pagina do arquivo de indice referente ao RRN passado
* como Paramentro
*/
BTPAGE btread(short rrn) {
BTPAGE page;
long addr;
addr = (long) rrn * (long) PAGESIZE + 2L;
fseek(btfd, addr, 0);
fread(&page, PAGESIZE, 1, btfd);
return page;
}
/* Escreve no arquivo a pagina passada como parametro
* e grava na posicao do RRN passado, retorna se escreveu ou se deu erro
*/
int btwrite(short rrn, BTPAGE *page_ptr) {
long addr;
addr = (long) rrn * (long) PAGESIZE + 2L;
fseek(btfd, addr, 0);
return (fwrite(page_ptr, PAGESIZE, 1, btfd));
}
/* Cria a pagina que será raiz e retorna o RRN dela
* e inicializa a pagina com pageinit()
*/
short create_root(Chave key, short left, short right) {
BTPAGE page;
short rrn;
rrn = get_rrn_new_page();
pageinit(&page);
page.key[0] = key;
page.child[0] = left;
page.child[1] = right;
page.keycount = 1;
btwrite(rrn, &page);
putroot(rrn);
return (rrn);
}
/* recebe uma pagina como referencia e inicializa setando os filhso pra -1
* e as chaves para NOKEY, no nosso caso #####
*/
void pageinit(BTPAGE *p_page) /* p_page: pointer to a page */ {
int j;
for (j = 0; j < MAXKEYS; j++) { //Inicializa a pg preenchendo os filhos e chaves com nil e #
strcpy(p_page->key[j].chave, NOKEY);
p_page->key[j].rrn_dados = NIL;
p_page->child[j] = NIL;
}
p_page->child[MAXKEYS] = NIL;
}
/* Funcao utilizada para procurar uma determinada chave numa pagina passada
* A referencia de *pos indica qual a posição eh ou deveria ocorrer a chave
* retorna se achou ou nao
*/
int search_node(Chave key, BTPAGE *p_page, short *pos)
/* pos: position where key is or should be inserted */ {
int i;
for (i = 0; i < p_page->keycount && strcmp(key.chave, p_page->key[i].chave) > 0; i++)
;
*pos = i;
if (*pos < p_page->keycount && strcmp(key.chave, p_page->key[*pos].chave)==0)
return (YES); /* key is in page */
else
return (NO); /* key is not in page */
}
/* Funcao que efetivamente insere uma chave numa pagina
* ordenando as chave r_child eh o novo filho dessa pagina se houver
*/
void ins_in_page(Chave key, short r_child, BTPAGE *p_page) {
int i;
for (i = p_page->keycount; strcmp(key.chave, p_page->key[i - 1].chave) < 0 && i > 0; i--) {
p_page->key[i] = p_page->key[i - 1];
p_page->child[i + 1] = p_page->child[i];
}
p_page->keycount++;
p_page->key[i] = key;
p_page->child[i + 1] = r_child;
}
/* Funcao para testes pessoais de projeto, nao utilizada
* no projeto efetivamente
*
void printPage(BTPAGE *page) {
printf("QNT chave: %d\n", page->keycount);
int i;
for (i = 0; i < MAXKEYS; i++) {
printf("<|%ld|>", page->child[i]);
printf(" %s ", page->key[i].chave);
}
printf("<|%ld|>", page->child[i]);
printf("\n");
}
*/
/* split ()
Arguments:
key: key to be inserted
promo_key: key to be promoted up from here
r_child: child rrn to be inserted
promo_r_child: rrn to be promoted up from here
p_oldpage: pointer to old page structure
p_newpage: pointer to new page structure
*/
/* Funcao split que separa chaves entre pagina antiga e nova
* e isso por referencia, pois o insert vai cuidar de escreve-las no arquivo
* Ela também escolhe quem será promovido por meido de *promo_key
*/
void split(Chave key, short r_child, BTPAGE *p_oldpage, Chave *promo_key,
short *promo_r_child, BTPAGE *p_newpage) {
int i;
short mid; /* tells where split is to occur */
Chave workkeys[MAXKEYS + 1]; /* temporarily holds keys, before split */
short workch[MAXKEYS + 2]; /* temporarily holds children, before split */
for (i = 0; i < MAXKEYS; i++) { /* move keys and children from */
workkeys[i] = p_oldpage->key[i]; /* old page into work arrays */
workch[i] = p_oldpage->child[i];
}
workch[i] = p_oldpage->child[i];
for (i = MAXKEYS; strcmp(key.chave, workkeys[i - 1].chave) < 0 && i > 0; i--) { /* insert new key */
workkeys[i] = workkeys[i - 1];
workch[i + 1] = workch[i];
}
workkeys[i] = key;
workch[i + 1] = r_child;
*promo_r_child = get_rrn_new_page(); /* create new page for split, */
pageinit(p_newpage); /* and promote rrn of new page */
*promo_key = workkeys[(int) (MAXKEYS + 1) / 2];
for (i = 0; i < MINKEYS; i++) { /* move first half of keys and */
p_oldpage->key[i] = workkeys[i]; /* children to old page, second */
p_oldpage->child[i] = workch[i]; /* half to new page */
p_newpage->key[i] = workkeys[i + 1 + MINKEYS];
p_newpage->child[i] = workch[i + 1 + MINKEYS];
strcpy(p_oldpage->key[i + MINKEYS].chave, NOKEY); /* mark second half of old */
p_oldpage->key[i + MINKEYS].rrn_dados = NIL;
p_oldpage->child[i + 1 + MINKEYS] = NIL; /* page as empty */
}
p_oldpage->child[MINKEYS] = workch[MINKEYS];
p_newpage->child[MINKEYS] = workch[i + 1 + MINKEYS];
p_newpage->keycount = MAXKEYS - MINKEYS;
p_oldpage->keycount = MINKEYS;
*promo_key = workkeys[MINKEYS]; /* promote middle key */
r_child = *promo_r_child;
key = *promo_key;
}
/* Funcão Driver que trata de setar a nova pagina raiz quando há split e
* uma nova pagina é criada
* Ela chama recursive_insert que vasculha e trata as possiveis ocorrencias e
* apenas retornara se houver promocao, caso contrario adiciona
* se chave jah existe nao adiciona, os parametros sao RRN da raiz e a Chave key
*/
void insert(short rrn, Chave key){
int promoted; /* boolean: tells if a promotion from below */
short promo_rrn; /* rrn promoted from below */
Chave promo_key; /* key promoted from below */
promoted = recursive_insert(rrn, key, &promo_rrn, &promo_key);
if (promoted)
root = create_root(promo_key, getroot(), promo_rrn);
}
// Insere recursivamente, retorna promocao ou nao pra insert()
int recursive_insert(short rrn, Chave key, short *promo_r_child, Chave *promo_key) {
BTPAGE page, /* current page */
newpage; /* new page created if split occurs */
int found, promoted; /* boolean values */
short pos,
p_b_rrn; /* rrn promoted from below */
Chave p_b_key; /* key promoted from below */
if (rrn == NIL) { /* past bottom of tree... "promote" */
*promo_key = key; /* original key so that it will be */
*promo_r_child = NIL; /* inserted at leaf level */
return (YES);
} else {
page = btread(rrn);
found = search_node(key, &page, &pos);
if (found) {
printf("Error: attempt to insert duplicate key: %s \n\007", key.chave);
return (0);
}
promoted = recursive_insert(page.child[pos], key, &p_b_rrn, &p_b_key);
if (!promoted) {
return (NO); /* no promotion */
} else if (page.keycount < MAXKEYS) {
ins_in_page(p_b_key, p_b_rrn, &page); /* OK to insert key and */
btwrite(rrn, &page); /* pointer in this page. */
return (NO); /* no promotion */
} else {
split(p_b_key, p_b_rrn, &page, promo_key, promo_r_child, &newpage);
btwrite(rrn, &page);
btwrite(*promo_r_child, &newpage);
return (YES); /* promotion */
}
}
}
/* Função de Busca que procura por chave na arvore de indices
* Caso encontra, retorna Verdadeiro e *found_rrn guarda o RRN do arquivo de dados
* da chave referente
* Caso nao encontra, retorna falso
*/
int search_key_on_tree(short rrn, Chave key, short *found_rrn, short *found_pos) {
BTPAGE page;
short pos;
int found;
if (rrn == NIL)
return (NO); //chave de busca não encontrada
else {
page = btread(rrn);
found = search_node(key, &page, &pos);
if (found) {
*found_rrn = page.key[pos].rrn_dados; //RRN corrente contém a chave
*found_pos = pos; //POS contém a posição da chave em PAGE
return (YES);
}//a chave de busca não foi encontrada,
else
//a chave de busca não foi encontrada, então se procura a chave no nó filho
return (search_key_on_tree(page.child[pos], key, found_rrn, found_pos));
}
}
/* Ordenacao utilizada na distribuicao e concatenação pra ordenar as paginas
* o vetor de chave eh passado por referência
*/
void shellSort(Chave *vet, int size) {
int i, j;
char value[6];
int gap = 1;
do {
gap = 3 * gap + 1;
} while (gap < size);
do {
gap /= 3;
for (i = gap; i < size; i++) {
strcpy(value, vet[i].chave);
j = i - gap;
while ((j >= 0) && (strcmp(value, vet[j].chave) < 0)) {
strcpy(vet[j + gap].chave, vet[j].chave);
j -= gap;
}
strcpy(vet[j + gap].chave, value);
}
} while (gap > 1);
}
/* Funcao pra organizar uma pagina quando uma chave é retirada
* As paginas que chegam aqui como referência sao rearranjadas de forma
* a retirar a chave da posicao pos e reagrupar chave e filhos
*/
void fixup_page(short rrn, short pos, BTPAGE *page) {
int i;
if (pos == (MAXKEYS - 1)) {
strcpy(page->key[pos].chave, NOKEY);
page->child[pos + 1] = -1;
} else {
page->key[pos] = page->key[pos + 1];
page->child[pos + 1] = page->child[pos + 2];
for (i = pos + 1; i < (MAXKEYS - 1); i++) {
if (page->key[i].chave != NOKEY) {
page->key[i] = page->key[i + 1];
page->child[i + 1] = page->child[i + 2];
}
}
strcpy(page->key[i].chave, NOKEY);
}
page->keycount--;
}
/* Função muito do mau pra fazer caras! Olha o tamanho desse trem, que bom que consegui, TENSO!
* Mas entao, ela recebe o RRN do PAI, a posicao do filho o qual teve underflow
* e a pagina pai por valor pra que eu nao precise carregar da memoria
* as filhas sao lidas do arquivo, eh escolhido a irma que servirá para dividir as chaves
* eh feita a divisão, alterações necessárias, e entao grava no arquivo o pai e as filhas
* Retorna sim se a distribuição eh possivel, pois se nao for, devo fazer um concatenação
* dai o remover cuida disso
*/
int redistribution(short rrn, short pos, Chave key, BTPAGE page) {
BTPAGE filha, irma_filha;
Chave workkeys[MAXKEYS + MINKEYS]; /* Guarda as chave para redistribuir entre filha e irma_filha */
short workch[MAXKEYS + MINKEYS + 1]; /* Guarda os filhos dessas chaves pra redistribuir */
int j = 0, i = 0, posicao_relativa_irma = 0; // Diz se a irma escolhida eh da direira ou esquerda 0 ESQ e 1 DIR
filha = btread(page.child[pos]);
if (pos == 0) {
irma_filha = btread(page.child[pos + 1]);
posicao_relativa_irma = 1;
} else if (pos == (MAXKEYS - 1))
irma_filha = btread(page.child[pos - 1]);
else {
irma_filha = btread(page.child[pos - 1]);
pos--;
if (irma_filha.keycount <= MINKEYS) {
pos++;
irma_filha = btread(page.child[pos + 1]);
posicao_relativa_irma = 1;
}
}
if (irma_filha.keycount > MINKEYS) {
while (strcmp(filha.key[i].chave, NOKEY) != 0) {
workkeys[i] = filha.key[i];
workch[i] = filha.child[i];
i++;
}
workkeys[i] = page.key[pos];
workch[i] = filha.child[i];
j = i + 1;
i = 0;
while ((strcmp(irma_filha.key[i].chave, NOKEY) != 0) && (j < MAXKEYS + MINKEYS)) {
workkeys[j] = irma_filha.key[i];
workch[j] = irma_filha.child[i];
i++;
j++;
}
workch[j] = irma_filha.child[i];
shellSort(&workkeys, MAXKEYS + MINKEYS);
if (posicao_relativa_irma == 0) { // Verifica se pagina irma eh da esquerda ou direita, pois muda a ordem de dsitribuicao
for (i = 0; i <= MINKEYS; i++) { /* Move filhos para a pagina filha, seus filhos tbm */
if (i < MINKEYS) {
irma_filha.key[i] = workkeys[i];
filha.child[MINKEYS + i] = workch[i];
filha.child[i] = workch[i + 1 + MAXKEYS];
}
irma_filha.child[i] = workch[i + MINKEYS];
filha.key[i] = workkeys[i + 1 + MINKEYS];
strcpy(irma_filha.key[i + MINKEYS - 1].chave, NOKEY);
}
filha.keycount = filha.keycount + irma_filha.keycount - MINKEYS;
irma_filha.keycount = MINKEYS;
btwrite(page.child[pos], &irma_filha);
btwrite(page.child[pos + 1], &filha);
} else {
for (i = 0; i <= MINKEYS; i++) {
if (i < 2)
filha.key[i] = workkeys[i];
filha.child[i] = workch[i];
irma_filha.key[i] = workkeys[i + 1 + MINKEYS];
irma_filha.child[i] = workch[i + 2 + MINKEYS];
strcpy(irma_filha.key[i + MINKEYS - 1].chave, NOKEY);
}
irma_filha.child[i] = workch[i];
irma_filha.keycount = irma_filha.keycount + filha.keycount - MINKEYS;
filha.keycount = MINKEYS;
btwrite(page.child[pos], &filha);
btwrite(page.child[pos + 1], &irma_filha);
}
page.key[pos] = workkeys[MINKEYS];
btwrite(rrn, &page);
return (YES);
} else
return (NO);
}
/* Essa funcao nao eh tao do mau quanto a Distribution porque a base dela vem da outra
* entao nao tive que começar do zero
* Entao, ela recebe o RRN do PAI, a posicao do filho o qual teve underflow
* e a pagina pai por valor pra que eu nao precise carregar da memoria
* as filhas sao lidas do arquivo, eh escolhido a irma que servirá para ceder suas chaves
* eh feita a junção da chave, alterações necessárias, e entao grava no arquivo o pai e a filha concatenada
* O retorno está comentado dentro da função no final
*/
int concatenation(short rrn, short pos, Chave key, BTPAGE page) {
BTPAGE filha, irma_filha;
Chave workkeys[MAXKEYS];
short workch[MAXKEYS + 1];
short pos_key;
int j = 0, i = 0, posicao_relativa_irma = 0; // Diz se a irma escolhida eh da direira ou esquerda 0 ESQ e 1 DIR
filha = btread(page.child[pos]);
if (pos == 0) {
irma_filha = btread(page.child[pos + 1]);
posicao_relativa_irma = 1;
} else if (pos == page.keycount)
irma_filha = btread(page.child[pos - 1]);
else {
irma_filha = btread(page.child[pos - 1]);
if (irma_filha.keycount < MINKEYS) {
irma_filha = btread(page.child[pos + 1]);
posicao_relativa_irma = 1;
}
}
if (irma_filha.keycount == MINKEYS) {
while (strcmp(filha.key[i].chave, NOKEY) != 0) {
workkeys[i] = filha.key[i];
workch[i] = filha.child[i];
i++;
}
if (!posicao_relativa_irma)
pos--;
workkeys[i] = page.key[pos];
workch[i] = filha.child[i];
j = i + 1;
i = 0;
while ((strcmp(irma_filha.key[i].chave, NOKEY) != 0) && (j < MAXKEYS)) {
workkeys[j] = irma_filha.key[i];
workch[j] = irma_filha.child[i];
i++;
j++;
}
workch[j] = irma_filha.child[i];
shellSort(&workkeys, MAXKEYS);
/* Gravando e zerando a Pagina que vai ficar vazia, pois RRN nao pode ser reutilizado
* e preciso verificar se a pagina eh da esquerda ou direita por conta de sempre gravar
* na filha esquerda da pagina, assim pos é recontado
*/
irma_filha.keycount = 0;
if (!posicao_relativa_irma) {
pos++;
btwrite(page.child[pos], &irma_filha);
pos--;
} else
btwrite(page.child[pos], &irma_filha);
// Fim do gravar pagina zerada devido a concatenacao ###############################
fixup_page(rrn, pos, &page);
for (i = 0; i < MAXKEYS; i++)
filha.key[i] = workkeys[i];
if (posicao_relativa_irma == 0) { // Verifica se irma da pagina eh a ersquerda ou direita, muda a atribuicao a ordem
for (i = 0; i <= MINKEYS; i++) {
filha.child[i] = workch[MINKEYS + i];
filha.child[MINKEYS + i + 1] = workch[i];
}
} else {
for (i = 0; i <= MAXKEYS; i++) {
filha.child[i] = workch[i];
}
}
filha.keycount = MAXKEYS;
btwrite(page.child[pos], &filha);
/*Gravando a irma que fica com 0 chaves, dai depende se é da esquerda ou direira,
* pois foi decrementado antes se fosse direita pra sempre gravar na esquerda
por conta dos irmao da pagina pderem ser deslocados*/
btwrite(rrn, &page);
}
/* Verifica se o underflow eh na raiz e se ela tem pelo menos uma chave, pois ela pode, caso contrario
* a Raiz tem 0 chaves e ocorre concatenacao no remocao recursivo, e o root recebe o rrn
* da nova raiz que eh a filha desse escopo
*/
if ((page.keycount == 1) && (rrn == root))
return (NO);
if ((page.keycount == 0) && (rrn == root)) {
root = page.child[pos];
return (YES);
}
//Retorna se deu underflow no pai, para fazer redistribuicao ou concatenacao
if ((page.keycount < MINKEYS))
return (YES);
return (NO);
}
/* Funcao Driver que chama a remoção recursiva
* recebe o RRN da Raiz e a chave a remover
* Caso de unerflow na raiz e ela fique com zero chave, eh setado no arquivo
* quer será a proxima raiz, assim a concatenação feita anteriormente eh a respectiva raiz
*/
void remove_key(short rrn, Chave key) {
int underflow, is_change = 0; /* Boolean pra underflow e int para eh troca ou nao */
Chave promo_key; /* Chave de troca entre pai e filho */
BTPAGE page;
page = btread(root);
underflow = recursive_remove_key(rrn, key, &is_change, &promo_key);
if (underflow)
putroot(root);
}
/* Ai tah a danada da remoção, Complicado viu, Graças a Deus que eu Consegui
* Ela recebe o RRN da pagina corrente onde tah buscando a chave a remover,
* a chave em sim, um int que verifica se esta havendo uma troca e por fim
* uma chave auxiliar que guarda a chave que sera trocada entre pai e filho
* Ela retorna recursivamente pra cada nivel se deu ou nao split, assim sao tratados
* os momentos de chamar a Distribuição e a remoção, lembrando que só Concateno quando
* nao eh possivel fazer a dsitribuição. Outros comentarios estao dentro.
*/
int recursive_remove_key(short rrn, Chave key, int *is_change, Chave * aux_key) {
BTPAGE page; /* Pagina corrente */
int found, underflow; /* Valores booleanos para underflow e chave encontrada */
short pos; /* Posicao de onde chave ocorre ou deveria ocorrer */
Chave p_b_key; /* Chave de troca entre pai e filho */
if (rrn == NIL) { /* Chegou no NIL, volta o nivel */
return (NO);
} else {
page = btread(rrn); // le a pagina do rrn corrente
if (!*is_change) // Verifica se eh troca
found = search_node(key, &page, &pos); // Caso nao seja troca, procura a chave na pagina
else {
pos = 0; // caso seja troca, vou pra esquerda a procura do sucessor
found = 1; // Pra isso entro no encotrado e faços a verificações, pois aqui ou encontra ou encontra
}
if (found) { // caso encontrado eu entro
if ((page.keycount > MINKEYS) || (page.child[pos] != -1)) { //Verifica qnt de chave ou se nao eh folha, no caso da troca de chave
if (page.child[pos] == -1) { // se for folha eu achei a chave que quero, seja pra troca ou remoção ela sera removida
*aux_key = page.key[pos]; // Guardo a chave pra trocar com o pai se for o caso
fixup_page(rrn, pos, &page); // Arrumo a folha sem a chave da posicao pos
btwrite(rrn, &page);
return (NO);
} else { // eh troca e nao eh folha, tenho que buscar a successora
*is_change = 1;
underflow = recursive_remove_key(page.child[pos + 1], key, is_change, &p_b_key);
page.key[pos] = p_b_key; // Depois de buscar a sucessora, seto ela para o pai
btwrite(rrn, &page);
if (underflow) { // Houve underflow na troca, eu tento distribuir, senao concatenar
if (redistribution(rrn, (pos + 1), key, page)) {
return (NO);
} else {
return (concatenation(rrn, (pos + 1), key, page)); // Concatenacao retorna se deu underflow no pai
}
}
*is_change = 0; // Aqui nao deu underflow, tah todo mundo feliz, volto a troca pra falso
return (NO);
}
} else { // quantidade de chave eh menor ou igual a minimo e eh pagina folha pra remover
if (*is_change) { // Verifico se eh troca, pois preciso guardar a chave de troca antes de excluir
if (page.child[pos] == -1) {
*aux_key = page.key[pos];
fixup_page(rrn, pos, &page);
btwrite(rrn, &page);
}
} else { // Nao eh troca eu removo normalmente
if (page.child[pos] == -1) {
fixup_page(rrn, pos, &page);
btwrite(rrn, &page);
}
}
return (YES); // retorna YES para underflow, pois como tinha o minimo de chave e eu removi mais uma, se deduz que...
}
} // Chave nao encotrada, dai eu busco na filha onde deveria ocorrer
underflow = recursive_remove_key(page.child[pos], key, is_change, &p_b_key);
if (underflow) { // Se deu underflow no pai e eh possivel de didistribuir eu o faço e retorno nao
if (redistribution(rrn, pos, key, page))
return (NO);
else /* caso nao de pra redistribuir, eu concateno e retorno o valor da concatenação, que indicará se de underflow na raiz */
return (concatenation(rrn, pos, key, page));
}
}
return (NO);
}
/* Imprime a arvore de indices em ordem de nivel,
* por exeplo, imprime a raiz, sua filha, sua neta, sua bisneta e vai indo, depois volta imprimindo
* as irmas da filha, da neta, da bisneta
* recebe o RRN da raiz
*/
void print_btree(short rrn) {
BTPAGE page;
int i;
page = btread(rrn);
//print pagina #
printf("RRN %d\t", rrn);
printf("Qtd Chave %d\t", page.keycount);
//print chave na pagina
for (i = 0; i < page.keycount; ++i)
printf("%s ", page.key[i].chave);
//adiciona espaços
for (i = page.keycount; i < MAXKEYS; ++i)
printf(" ");
printf("\t");
//print filhos da pagina
for (i = 0; i <= page.keycount; ++i)
printf("%ld ", page.child[i]);
printf("\n");
//print o nivel a baixo e proximo da recursivamente
for (i = 0; i <= page.keycount; ++i) {
if (page.child[i] != NIL)
print_btree(page.child[i]);
}
return;
}