Skip to content

Instantly share code, notes, and snippets.

@pvsousalima

pvsousalima/main.c

Last active December 15, 2015 02:49
Show Gist options
  • Save pvsousalima/5189991 to your computer and use it in GitHub Desktop.
Save pvsousalima/5189991 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
main.c
/*
* File: main.c
* Author: pedro
*
* Created on 18 de Março de 2013, 10:10
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Order 2
#define MAXKEYS 2*Order
#define NIL -1
#define TRUE 1
#define FALSE 0
#define PROMOTION -2
#define NO_PROMOTION -3
#define ERROR -4
#define NOT_FOUND -5
#define FOUND -6
#define LEAF -7
#define NOT_LEAF -8
#define UNDERFLOW -9
#define NOT_UNDERFLOW -10
#define CONCATENATE -11
FILE *Btree = NULL;
FILE *Data = NULL;
/*
*
*/
/*Initial Header with the reference for tree.*/
typedef struct Index {
long TreeRRN;
long CurrentRRN;
long DataRRN;
} Index;
Index*ind = NULL;
typedef struct References {
/* data */
char Reference[6]; //Author's reference.
long FileRRN; //Reference for Structure on File.
} References;
/*Structure of page*/
typedef struct Page {
/* data */
long RRN;
short NumberOfKeys;
References ReferencesArray[MAXKEYS];
long RRNsArray[MAXKEYS + 1];
} Page;
/*Structure of page*/
typedef struct AuxPage {
/* data */
long RRN;
short NumberOfKeys;
References ReferencesArray[MAXKEYS + 1];
long RRNsArray[MAXKEYS + 2];
} AuxPage;
void ParseString(char *string) {
long len = strlen(string);
long i = 0;
for (i = 0; i < len; i++) {
if (string[i] == '#') {
printf("\n");
return;
}
if (string[i] != '@') {
printf("%c", string[i]);
} else {
printf(" ");
}
}
}
//Initialize a new page
void Initialize(Page*page) {
page->NumberOfKeys = 0;
page->RRN = ind->CurrentRRN;
ind->CurrentRRN++;
int i = 0;
for (i = 0; i < MAXKEYS; i++) {
strcpy(page->ReferencesArray[i].Reference, "#####\0");
}
for (i = 0; i < MAXKEYS + 1; i++) {
page->RRNsArray[i] = NIL;
}
printf("Initialized a new Page\n");
printf("Number of Keys: %d\n", page->NumberOfKeys);
printf("RRN of this Page %li\n", page->RRN);
printf("Actual RRN: %lu\n", ind->CurrentRRN);
printf("\n");
}
//make an reference for the index of the page.
/*Write a page on disk*/
void WritePage(Page* page, long RRN) {
fseek(Btree, sizeof (struct Index) +RRN * sizeof (struct Page), SEEK_SET);
fwrite(&(*page), sizeof (struct Page), 1, Btree);
// printf("Page with RRN %lu writed successfully\n", page->RRN);
free(page);
}
/*Return a pointer for a specific page*/
Page* getPage(long RRN) {
rewind(Btree);
fseek(Btree, sizeof (struct Index) +RRN * sizeof (struct Page), SEEK_SET);
Page* page = malloc(sizeof (struct Page));
fread(&(*page), sizeof (struct Page), 1, Btree);
return page;
}
void WriteIndex() {
fseek(Btree, 0 * sizeof (struct Index), SEEK_SET);
fwrite(&(*ind), sizeof (struct Index), 1, Btree);
}
//Open a local Btree
int Driver() {
Data = fopen("/home/pedro/data.dat", "r+");
Btree = fopen("/home/pedro/index.dat", "rb+");
if (Btree == NULL && Data == NULL) {
Btree = fopen("/home/pedro/index.dat", "wb+");
Data = fopen("/home/pedro/data.dat", "w+");
ind = malloc(sizeof (struct Index));
ind->CurrentRRN = 0;
ind->TreeRRN = 0;
/*Grava o cabeçalho.*/
fseek(Btree, 0 * sizeof (struct Index), SEEK_SET);
fwrite(&(*ind), sizeof (struct Index), 1, Btree);
/*Allocate the first page*/
Page *Root = malloc(sizeof (struct Page));
Initialize(Root);
WritePage(Root, Root->RRN);
} else {
ind = malloc(sizeof (struct Index));
fseek(Btree, 0 * sizeof (struct Index), SEEK_SET);
fread(&(*ind), sizeof (struct Index), 1, Btree);
}
}
void PrintKeys(Page* page) {
int i = 0;
printf("\n\nPrinting Keys.\nRRN of the page: %li\nNumber of Keys %d\n", page->RRN, page->NumberOfKeys);
printf("Keys:\n");
for (i = 0; i < MAXKEYS/*page->NumberOfKeys*/; i++) {
printf("%s ", page->ReferencesArray[i].Reference);
}
printf("\n");
}
void PrintChildren(Page*page) {
int i = 0;
for (i = 0; i < MAXKEYS + 1; i++) {
printf(" %li ", page->RRNsArray[i]);
}
}
int BinarySearch(Page* page, char *Key, int*found) {
int first = 0, last = page->NumberOfKeys - 1, middle = 0;
while (first <= last) {
middle = (first + last) / 2;
if (strcmp(Key, (char*) page->ReferencesArray[middle].Reference) < 0) {
last = middle - 1;
} else if (strcmp(Key, (char*) page->ReferencesArray[middle].Reference) > 0) {
first = middle + 1;
} else {
*found = TRUE;
return middle;
}
}
return first;
}
int SearchKey(long RRN, char *Key, long *FOUND_RRN, int *FOUND_POS) {
Page* page = getPage(RRN);
if (RRN == NIL) {
free(page);
//Not Found
return NIL;
} else {
// printf("Page of RRN %lu on memory\n", page->RRN);
//Print Keys of specific page
// PrintKeys(page);
//Position and return
int Position = 0, found = -1;
//Search on page
Position = BinarySearch(&(*page), Key, &found);
if (found == TRUE) {
*FOUND_RRN = (long) RRN;
*FOUND_POS = (long) Position;
free(page);
printf("\n");
return TRUE;
} else {
free(page);
return (SearchKey(page->RRNsArray[Position], Key, FOUND_RRN, FOUND_POS));
}
}
}
void InsertKey(Page* page, char *Key, long R_SON, long DataRRN) {
/* int i = 0;
for (i = page->NumberOfKeys; strcmp(Key, page->ReferencesArray[i - 1].Reference) < 0 && i > 0; i--) {
strcpy(page->ReferencesArray[i].Reference, page->ReferencesArray[i - 1].Reference);
page->RRNsArray[i + 1] = page->RRNsArray[i];
}
page->NumberOfKeys++;
strcpy(page->ReferencesArray[i].Reference, Key);
page->RRNsArray[i + 1] = R_SON;*/
int Position = 0;
int found = -1, i = page->NumberOfKeys;
Position = BinarySearch(page, Key, &found);
while (i > Position && strcmp(Key, page->ReferencesArray[i - 1].Reference) < 0) {
page->ReferencesArray[i] = page->ReferencesArray[i - 1];
page->RRNsArray[i + 1] = page->RRNsArray[i];
i--;
}
strcpy(page->ReferencesArray[Position].Reference, Key);
page->ReferencesArray[Position].FileRRN = DataRRN;
page->RRNsArray[Position + 1] = R_SON;
(page->NumberOfKeys)++;
}
void Split(char *key, long r_child, Page *p_oldpage, char *promo_key, long *promo_r_child, Page *p_newpage) {
int i;
short mid; /* tells where split is to occur */
References 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 */
strcpy(workkeys[i].Reference, p_oldpage->ReferencesArray[i].Reference);
workch[i] = p_oldpage->RRNsArray[i];
}
workch[i] = p_oldpage->RRNsArray[i];
for (i = MAXKEYS; (strcmp(key, workkeys[i - 1].Reference) < 0) && i > 0; i--) { /* insert new key */
workkeys[i] = workkeys[i - 1];
workch[i + 1] = workch[i];
}
strcpy(workkeys[i].Reference, key);
workch[i + 1] = r_child;
Initialize(p_newpage); /* and promote rrn of new page */
*promo_r_child = p_newpage->RRN; /* create new page for split, */
//printf("FILHO À DIREITA NEW_PAGE: %li\n", p_newpage->RRN);
//printf("FILHO À ESQUERDA, OLD_PAGE: %li\n", p_oldpage->RRN);
for (i = 0; i < Order; i++) { /* move first half of keys and */
strcpy(p_oldpage->ReferencesArray[i].Reference, workkeys[i].Reference);
/* children to old page, second */
p_oldpage->RRNsArray[i] = workch[i]; /* half to new page */
strcpy(p_newpage->ReferencesArray[i].Reference, workkeys[i + 1 + Order].Reference);
p_newpage->RRNsArray[i] = workch[i + 1 + Order];
strcpy(p_oldpage->ReferencesArray[i + Order].Reference, "#####\0");
/* mark second half of old */
p_oldpage->RRNsArray[i + 1 + Order] = NIL; /* page as empty */
}
p_oldpage->RRNsArray[Order] = workch[Order];
p_newpage->RRNsArray[Order] = workch[i + 1 + Order];
p_newpage->NumberOfKeys = MAXKEYS - Order;
p_oldpage->NumberOfKeys = Order;
strcpy(promo_key, workkeys[Order].Reference);
/* promote middle key */
}
Page *createRoot(char *Key, long right, long left) {
Page*root = malloc(sizeof (struct Page));
Initialize(root);
strcpy(root->ReferencesArray[0].Reference, Key);
root->RRNsArray[0] = left;
root->RRNsArray[1] = right;
root->NumberOfKeys = 1;
ind->TreeRRN = root->RRN;
return root;
}
int Insert(long CurrentRRN, char *Key, long DataRRN, long *PROMO_R_CHILD, char *PROMO_KEY) {
char p_b_key[6];
long p_b_rrn;
if (CurrentRRN == NIL) { //Chegou na folha.
strcpy(&(*PROMO_KEY), Key);
*PROMO_R_CHILD = NIL;
return PROMOTION;
} else {
Page *page = getPage(CurrentRRN);
int found = -1;
int Position = BinarySearch(page, Key, &found);
if (found == TRUE) {
printf("Chave %s não inserida. Já existe na árvore.\n", Key);
return ERROR;
}
int RETURN_VALUE = Insert(page->RRNsArray[Position], Key, DataRRN, &p_b_rrn, p_b_key);
if (RETURN_VALUE == ERROR || RETURN_VALUE == NO_PROMOTION) {
free(page);
return RETURN_VALUE;
} else if (page->NumberOfKeys < MAXKEYS) {//Há espaço!!
InsertKey(page, p_b_key, p_b_rrn, DataRRN);
// printf("Chave %s inserida na página de RRN %li na posição %d e seu filho direita %li\n", p_b_key, CurrentRRN, Position, p_b_rrn);
printf("Chave %s inserida\n", p_b_key);
WritePage(page, CurrentRRN);
return NO_PROMOTION;
} else {
Page *newpage = malloc(sizeof (struct Page));
Split(p_b_key, p_b_rrn, page, PROMO_KEY, PROMO_R_CHILD, newpage);
WritePage(page, page->RRN);
WritePage(newpage, newpage->RRN);
return PROMOTION;
}
}
}
int DriverRoot(char *Key, long DataRRN) {
long PROMO_R_CHILD;
char PROMO_KEY[6];
int Result = -1;
Page *Root = NULL;
if (Result = Insert(ind->TreeRRN, Key, DataRRN, &PROMO_R_CHILD, PROMO_KEY) == PROMOTION) {
// printf("Cria nova raiz\n");
// printf("Está voltando %s e seu filho direita %li\n", PROMO_KEY, PROMO_R_CHILD);
Root = createRoot(PROMO_KEY, PROMO_R_CHILD, ind->TreeRRN);
WritePage(Root, Root->RRN);
} else {
/* Root = getPage(ind->TreeRRN);
InsertKey(Root, PROMO_KEY, PROMO_R_CHILD);*/
// printf("Não houve promoção para a raíz.\n");
}
}
void Organize(Page *page, int Position) {
if (Position == (MAXKEYS - 1)) {/*Last position just remove.*/
strcpy(page->ReferencesArray[Position].Reference, "#####\0");
page->NumberOfKeys--;
} else {
int i;
for (i = Position; i < page->NumberOfKeys - 1; i++) {
strcpy(page->ReferencesArray[i].Reference, page->ReferencesArray[i + 1].Reference);
}
strcpy(page->ReferencesArray[i].Reference, "#####\0");
page->NumberOfKeys--;
for (i = Position; i < page->NumberOfKeys + 1; i++) {
page->RRNsArray[i] = page->RRNsArray[i + 1];
}
page->RRNsArray[i] = -1;
}
}
void DeletePage(long *ProblemRRN) {
Page *PageForDelete = getPage(*ProblemRRN);
PageForDelete->NumberOfKeys = 0;
PageForDelete->RRN = -1;
Organize(PageForDelete, 0);
WritePage(PageForDelete, *ProblemRRN);
}
void DriverRemove(char *Key) {
/*Primeira chamada da raíz*/
int Result = ERROR;
int Trocando = FALSE;
char ChaveTroca[6];
long ProblemRRN;
Result = Remove(ind->TreeRRN, Key, &Result, ChaveTroca, NULL, &Trocando, &ProblemRRN);
if (Result == TRUE || Result == NOT_UNDERFLOW) {
printf("Chave %s Removida\n", Key);
} else if (Result == UNDERFLOW) {
printf("UNDERFLOW NA RAIZZZZZZZZZZZZZ\n");
/*Tratar!!!!*/
Page *Root = getPage(ProblemRRN);
ind->TreeRRN = Root->RRNsArray[0];
int Redistribution_Result = Redistribution(Root, ProblemRRN);
if (Redistribution_Result == CONCATENATE) {
Concatenate(Root, ProblemRRN);
}
DeletePage(&ProblemRRN);
WritePage(Root, Root->RRN);
} else if (Result == NOT_FOUND) {
printf("Chave \"%s\" não foi encontrada para remoção.\n", Key);
}
}
/*Returns if a page is Leaf or not.*/
int isPageLeaf(Page *page) {
int i = 0, test = LEAF;
while (i < page->RRNsArray[page->NumberOfKeys]) {
if (page->RRNsArray[i] != NIL) {
test = NOT_LEAF;
}
i++;
}
if (test == LEAF) {
return LEAF;
} else {
return NOT_LEAF;
}
}
int Concatenate(Page *CurrentPage, long *ProblemRRN, long DataRRN) {
/*Pesquisa a posição no Array de RRNS, qual o RRN que deu problema.*/
int i = 0, Position = -1;
for (i = 0; i <= CurrentPage->NumberOfKeys + 1; i++) {
if ((*ProblemRRN) == CurrentPage->RRNsArray[i]) {
Position = i;
}
}
/*Está na última posição, não há irmãs à direita. Só devemos olhar para a esquerda.*/
if ((*ProblemRRN) == CurrentPage->RRNsArray[CurrentPage->NumberOfKeys]) {
Page *LeftSister = getPage(CurrentPage->RRNsArray[Position - 1]);
Page *ProblemPage = getPage(*ProblemRRN);
/*Array temporário para segurar as chaves da irmã à esquerda*/
References workkeys[LeftSister->NumberOfKeys];
/*Copia as chaves da página problemática para o vetor temporário*/
int i = 0;
for (i = 0; i < ProblemPage->NumberOfKeys; i++) {
strcpy(workkeys[i].Reference, ProblemPage->ReferencesArray[i].Reference);
}
/*Apaga o RRN para a página que foi excluída na página pai.*/
CurrentPage->RRNsArray[Position] = -1;
/*Desce o pai*/
char Dad[6];
strcpy(&(*Dad), CurrentPage->ReferencesArray[Position - 1].Reference);
printf("PAI: %s\n", Dad);
/*Insere o pai na página irmã .*/
InsertKey(LeftSister, Dad, -1, DataRRN);
/*Insere as chaves da página problemática na sua irmã à esquerda.*/
for (i = 0; i < ProblemPage->NumberOfKeys; i++) {
InsertKey(LeftSister, workkeys[i].Reference, -1, DataRRN);
}
/*Deleta a página problemática*/
DeletePage(ProblemRRN);
Organize(CurrentPage, Position - 1);
if (CurrentPage->NumberOfKeys < Order) {
WritePage(LeftSister, LeftSister->RRN);
return UNDERFLOW;
}
WritePage(LeftSister, LeftSister->RRN);
return TRUE;
} else {
/*Não há irmãs à esquerda, olha só para a direita.*/
if ((*ProblemRRN) == CurrentPage->RRNsArray[0]) {
Page *RightSister = getPage(CurrentPage->RRNsArray[Position + 1]);
printf("Irmã direita.\n");
PrintKeys(RightSister);
Page *ProblemPage = getPage(*ProblemRRN);
/*Array temporário para segurar as chaves da irmã à direita*/
References workkeys[RightSister->NumberOfKeys];
/*Copia as chaves da página problemática para o vetor temporário*/
int i = 0;
printf("Chaves:\n");
for (i = 0; i < ProblemPage->NumberOfKeys; i++) {
strcpy(workkeys[i].Reference, ProblemPage->ReferencesArray[i].Reference);
printf("%s ", ProblemPage->ReferencesArray[i].Reference);
}
/*Apaga o RRN para a página que foi excluída na página pai.*/
CurrentPage->RRNsArray[Position] = -1;
/*Desce o pai*/
char Dad[6];
strcpy(&(*Dad), CurrentPage->ReferencesArray[Position].Reference);
printf("PAI: %s\n", Dad);
/*Insere as chaves da página problemática na sua irmã à direita.*/
for (i = 0; i < ProblemPage->NumberOfKeys; i++) {
InsertKey(RightSister, workkeys[i].Reference, -1, DataRRN);
}
/*Deleta a página problemática*/
DeletePage(ProblemRRN);
/*Insere o pai na página irmã .*/
InsertKey(RightSister, Dad, -1, DataRRN);
CurrentPage->RRNsArray[Position] = RightSister->RRN;
Organize(CurrentPage, Position);
if (CurrentPage->NumberOfKeys < Order) {
WritePage(RightSister, RightSister->RRN);
return UNDERFLOW;
}
WritePage(RightSister, RightSister->RRN);
return TRUE;
} else {
Page *RightSister = getPage(CurrentPage->RRNsArray[Position + 1]);
printf("Irmã direita.\n");
PrintKeys(RightSister);
Page *ProblemPage = getPage(*ProblemRRN);
/*Array temporário para segurar as chaves da irmã à direita*/
References workkeys[RightSister->NumberOfKeys];
/*Copia as chaves da página problemática para o vetor temporário*/
int i = 0;
for (i = 0; i < ProblemPage->NumberOfKeys; i++) {
strcpy(workkeys[i].Reference, ProblemPage->ReferencesArray[i].Reference);
}
/*Deleta a página problemática*/
DeletePage(ProblemRRN);
/*Apaga o RRN para a página que foi excluída na página pai.*/
CurrentPage->RRNsArray[Position] = -1;
/*Desce o pai*/
char Dad[6];
strcpy(&(*Dad), CurrentPage->ReferencesArray[Position].Reference);
printf("PAI: %s\n", Dad);
/*Insere o pai na página irmã .*/
InsertKey(RightSister, Dad, -1, DataRRN);
/*Insere as chaves da página problemática na sua irmã à direita.*/
for (i = 0; i < ProblemPage->NumberOfKeys; i++) {
InsertKey(RightSister, workkeys[i].Reference, -1, DataRRN);
}
CurrentPage->RRNsArray[Position] = RightSister->RRN;
Organize(CurrentPage, Position);
if (CurrentPage->NumberOfKeys < Order) {
WritePage(RightSister, RightSister->RRN);
return UNDERFLOW;
}
WritePage(RightSister, RightSister->RRN);
}
}
}
int Redistribution(Page *CurrentPage, long *ProblemRRN, long DataRRN) {
/*Pesquisa a posição no Array de RRNS, qual o RRN que deu problema.*/
int i = 0, Position = -1;
for (i = 0; i <= CurrentPage->NumberOfKeys + 1; i++) {
if ((*ProblemRRN) == CurrentPage->RRNsArray[i]) {
Position = i;
}
}
/*Não há irmãs à esquerda, olha só para a direita.*/
if ((*ProblemRRN) == CurrentPage->RRNsArray[0]) {
Page *RightSister = getPage(CurrentPage->RRNsArray[Position + 1]);
printf("Irmã direita.\n");
PrintKeys(RightSister);
/*Olha-se a irmã da direita a fim de se verificar a possibilidade de Redistribuição de chaves.*/
if (RightSister->NumberOfKeys > Order) {
printf("É possível redistribuir para a direita!!!!!!!!!!\n");
Page*ProblemPage = getPage(CurrentPage->RRNsArray[Position]);
/*Desce o pai*/
char Dad[6];
strcpy(Dad, CurrentPage->ReferencesArray[Position].Reference);
/*Insere o pai na página problemática.*/
InsertKey(ProblemPage, Dad, -1, DataRRN);
/*salva-se a página problemática*/
WritePage(ProblemPage, ProblemPage->RRN);
strcpy(CurrentPage->ReferencesArray[Position].Reference, RightSister->ReferencesArray[0].Reference);
Organize(RightSister, 0);
WritePage(RightSister, RightSister->RRN);
printf("Redistribuição concluída.\n");
return TRUE;
} else {
/*Redistribuição não foi possível. Concatenar.*/
free(RightSister);
return CONCATENATE;
}
}
if ((*ProblemRRN) == CurrentPage->RRNsArray[CurrentPage->NumberOfKeys]) { /*Está na última posição, não há irmãs à direita. Só devemos olhar para a esquerda.*/
Page *LeftSister = getPage(CurrentPage->RRNsArray[Position - 1]);
printf("\nIrmã esquerda:");
PrintKeys(LeftSister);
if (LeftSister->NumberOfKeys > Order) {
printf("É possível redistribuir para a esquerda!!!!!!!!!!\n");
Page*ProblemPage = getPage(CurrentPage->RRNsArray[Position]);
/*Desce o pai*/
char Dad[6];
strcpy(Dad, CurrentPage->ReferencesArray[Position].Reference);
/*Insere o pai na página problemática.*/
InsertKey(ProblemPage, Dad, -1, DataRRN);
/*salva-se a página problemática*/
WritePage(ProblemPage, ProblemPage->RRN);
strcpy(CurrentPage->ReferencesArray[Position].Reference, LeftSister->ReferencesArray[LeftSister->NumberOfKeys - 1].Reference);
Organize(LeftSister, LeftSister->NumberOfKeys - 1);
WritePage(LeftSister, LeftSister->RRN);
printf("Redistribuição concluída.\n");
return TRUE;
} else {
free(LeftSister);
return CONCATENATE;
}
} else {
if (*ProblemRRN != CurrentPage->RRNsArray[0] && *ProblemRRN != CurrentPage->RRNsArray[CurrentPage->NumberOfKeys + 1]) {
/*Olha-se a irmã da direita a fim de se verificar a possibilidade de Redistribuição de chaves.*/
Page *RightSister = getPage(CurrentPage->RRNsArray[Position + 1]);
if (RightSister->NumberOfKeys > Order) {
// printf("É possível redistribuir para a direita!!!!!!!!!!\n");
Page*ProblemPage = getPage(CurrentPage->RRNsArray[Position]);
/*Desce o pai*/
char Dad[6];
strcpy(Dad, CurrentPage->ReferencesArray[Position].Reference);
/*Insere o pai na página problemática.*/
InsertKey(ProblemPage, Dad, -1, DataRRN);
/*salva-se a página problemática*/
WritePage(ProblemPage, ProblemPage->RRN);
strcpy(CurrentPage->ReferencesArray[Position].Reference, RightSister->ReferencesArray[0].Reference);
Organize(RightSister, 0);
WritePage(RightSister, RightSister->RRN);
printf("Redistribuição concluída.\n");
return TRUE;
} else {
printf("Irmã direita:\n");
PrintKeys(RightSister);
free(RightSister);
Page *LeftSister = getPage(CurrentPage->RRNsArray[Position - 1]);
printf("Irmã esquerda:\n");
PrintKeys(LeftSister);
if (LeftSister->NumberOfKeys > Order) {
printf("É possível redistribuir para a esquerda!!!!!!!!!!\n");
Page*ProblemPage = getPage(CurrentPage->RRNsArray[Position]);
/*Desce o pai*/
char Dad[6];
strcpy(Dad, CurrentPage->ReferencesArray[Position - 1].Reference);
/*Insere o pai na página problemática.*/
InsertKey(ProblemPage, Dad, -1, DataRRN);
/*salva-se a página problemática*/
WritePage(ProblemPage, ProblemPage->RRN);
char PromotedSon[6];
strcpy(PromotedSon, LeftSister->ReferencesArray[LeftSister->NumberOfKeys - 1].Reference);
strcpy(CurrentPage->ReferencesArray[Position - 1].Reference, PromotedSon);
Organize(LeftSister, LeftSister->NumberOfKeys - 1);
WritePage(LeftSister, LeftSister->RRN);
printf("Redistribuição concluída.\n");
return TRUE;
} else {
free(LeftSister);
return CONCATENATE;
}
}
}
}
}
int Remove(long CurrentRRN, char *Key, int *Troca, char *ChaveTroca, Page *Dad, int *Trocando, long *ProblemRRN, long DataRRN) {
Page*CurrentPage = getPage(CurrentRRN);
if (CurrentRRN == NIL) {
return ERROR;
}
if (CurrentRRN != NIL) {
strcpy(&(*ChaveTroca), &(*CurrentPage->ReferencesArray[0].Reference));
if (isPageLeaf(CurrentPage) == LEAF && *Trocando == TRUE) {
strcpy(Dad->ReferencesArray[*Troca].Reference, ChaveTroca);
printf("Chave de TROCA: %s\n", ChaveTroca);
printf("last RRN: %li\n", CurrentRRN);
Organize(CurrentPage, 0);
if (CurrentPage->NumberOfKeys < Order) {
printf("UNDERFLOW NA SUA PÁGINA!!!\n");
*Trocando = FALSE;
*ProblemRRN = CurrentRRN;
return UNDERFLOW;
}
*Trocando = FALSE;
WritePage(CurrentPage, CurrentPage->RRN);
return NOT_UNDERFLOW;
}
}
int found = -1;
int Position = BinarySearch(CurrentPage, Key, &found);
if (found == TRUE) {
/*É folha, simplesmente removemos e verificamos se há Underflow na página em questão.*/
if (isPageLeaf(CurrentPage) == LEAF) {
Organize(CurrentPage, Position); /*Remove chave, primeiro caso.*/
// printf("Chave %s removida\n.", Key);
if (CurrentPage->NumberOfKeys < Order) {
WritePage(CurrentPage, CurrentPage->RRN); /*Escreve página alterada*/
printf("UNDERFLOW NA PÁGINA DE RRN %li\n", CurrentRRN);
*ProblemRRN = CurrentRRN;
return UNDERFLOW; /*Retorna que houve Underflow para o nível de cima.*/
}
WritePage(CurrentPage, CurrentPage->RRN); /*Escreve página alterada*/
return TRUE; /*Chave removida.*/
}
/*Se achar em uma página não folha, procuramos seu sucessor direto.*/
if (isPageLeaf(CurrentPage) == NOT_LEAF) {
*Trocando = TRUE;
Dad = &(*CurrentPage); /*Armazena a página pai*/
*Troca = Position; /*Armazena a posição de troca.*/
/*Chama a recursão procurando o sucessor direto da chave.*/
int Return = Remove(CurrentPage->RRNsArray[Position + 1], Key, Troca, ChaveTroca, Dad, Trocando, ProblemRRN, DataRRN);
printf("Resultado: %d.\n", Return);
*Trocando = FALSE;
if (Return == UNDERFLOW) {
/*Tratamento de Underflow. Verificamos se é possível redistribuição*/
if (Redistribution(CurrentPage, ProblemRRN, DataRRN) == CONCATENATE) {
/*Concatenar*/
Concatenate(CurrentPage, ProblemRRN, DataRRN);
} else {
WritePage(CurrentPage, CurrentRRN);
return TRUE; /*Chave removida.*/
}
}
WritePage(CurrentPage, CurrentRRN);
}
} else {
int Return = Remove(CurrentPage->RRNsArray[Position], Key, Troca, ChaveTroca, Dad, Trocando, ProblemRRN, DataRRN);
if (Return == UNDERFLOW) {
/*Tratamento de Underflow. Verificamos se é possível redistribuição*/
if (Redistribution(CurrentPage, ProblemRRN, DataRRN) == CONCATENATE) {
/*Concatenar*/
int ConcatenateResult = Concatenate(CurrentPage, ProblemRRN, DataRRN);
if (ConcatenateResult == UNDERFLOW) {
WritePage(CurrentPage, CurrentRRN);
return UNDERFLOW;
}
}
}
WritePage(CurrentPage, CurrentRRN);
}
return NOT_FOUND;
}
void printtree(long t) {
int i;
if (t != NIL) {
Page *page = getPage(t);
printf("RRN %li|", page->RRN);
printf("Number of Keys %d|", page->NumberOfKeys);
for (i = 0; i < MAXKEYS; i++) {
printf(" %li |", page->RRNsArray[i]);
printf(" %s,%li |", page->ReferencesArray[i].Reference, page->ReferencesArray[i].FileRRN);
if (i == MAXKEYS - 1) {
printf(" %li |", page->RRNsArray[i + 1]);
}
}
puts("");
for (i = 0; i <= MAXKEYS; i++)
printtree(page->RRNsArray[i]);
}
}
int main(int argc, char** argv) {
Driver();
printf("TREE %li CU %li\n", ind->TreeRRN, ind->CurrentRRN);
int j = 0;
int i = 0;
char tudoaux[256];
//variavel para pegar as 3 primeiras posições do vetor
//printf("COPIADA PARA A VERIFICACAO %s \n", tudo);
char IR[3] = "IR\0";
char RR[3] = "RR\0";
char BR[3] = "BR\0";
char IA[3] = "IA\0";
char FM[3] = "FM\0";
char caraux[3] = "NO";
while (strcmp(caraux, FM) != 0) {
j = 0;
scanf("%[^\n]s", tudoaux);
//fgets(tudoaux, 256, stdin);
//printf("%d", strlen(tudoaux));7
for (i = 0; i < 2; i++) {
caraux[j] = tudoaux[i];
j++;
}
if (strcmp(IR, caraux) == 0 && strlen(tudoaux) > 4) {
printf("CHAMEI INSERCAO\n");
char Key[6];
int k = 3;
for (i = 0; i < 5; i++) {
Key[i] = tudoaux[k];
k++;
}
Key[i] = '\0';
DriverRoot(Key, ind->DataRRN);
ind->DataRRN++;
int l = 0;
char Auxiliar[256];
int tamanho = strlen(tudoaux);
for (i = 3; i < tamanho; i++) {
Auxiliar[l] = tudoaux[i];
l++;
}
for (i = l; i < 256; i++) {
Auxiliar[i] = '#';
}
Auxiliar[i] = '\0';
printf("Auxiliar %s\n\n", Auxiliar);
printf("%d\n", strlen(Auxiliar));
fprintf(Data, "%s", Auxiliar);
} else
if (strcmp(RR, caraux) == 0) {
printf("REMOVE REFERENCIA\n");
char Key[6];
int k = 3;
for (i = 0; i < 5; i++) {
Key[i] = tudoaux[k];
k++;
}
Key[i] = '\0';
printf("Key %s\n", Key);
DriverRemove(Key);
} else
if (strcmp(BR, caraux) == 0) {
printf("BUSCA REFERENCIA\n");
char Key[6];
int k = 3;
for (i = 0; i < 5; i++) {
Key[i] = tudoaux[k];
k++;
}
Key[i] = '\0';
long FOUND_RRN = -1;
int FOUND_POS = -1;
if (SearchKey(ind->TreeRRN, Key, &FOUND_RRN, &FOUND_POS) == TRUE) {
printf("Referência encontrada!\n");
Page *Seekpage = getPage(FOUND_RRN);
fseek(Data, Seekpage->ReferencesArray[FOUND_POS].FileRRN * 256 * (sizeof (char)), SEEK_SET);
char BiblioReference[258];
fread(&BiblioReference, 256 * (sizeof (char)), 1, Data);
ParseString(BiblioReference);
} else {
printf("Not found\n");
}
} else
if (strcmp(IA, caraux) == 0) {
printf("ESTADO DO INDICE ATUAL\n");
printtree(ind->TreeRRN);
} else
if (strcmp(FM, caraux) == 0) {
} else {
printf("Opção não existente!\n");
}
getchar();
}
WriteIndex();
free(ind);
fclose(Btree);
fclose(Data);
return (EXIT_SUCCESS);
}
// fprintf(Data, "aoksdskoadkoasoakdkoaskoa", stdin);
// ind = malloc(sizeof (struct Index));
// ind->CurrentRRN = 0;
// Driver();
// ind->TreeRRN = 0;
//
//
// /*
// // Search Test
// long FOUND_RRN = -1;
// int FOUND_POS = -1;
// if (SearchKey(ind->TreeRRN, "CAC80\0", &FOUND_RRN, &FOUND_POS) == TRUE) {
// printf("Found!\n");
// printf("Achado no RRN: %lu\n", FOUND_RRN);
// printf("Posição: %d", FOUND_POS);
// } else {
// printf("Not found\n");
// }
// */
//
// /*
// Remove(ind->TreeRRN, "G\0", NULL);
// if (Remove(ind->TreeRRN, "K\0", NULL) == NOT_FOUND) {
// printf("NÃO ACHEI asdasdasdasdasdaswqWQWQEWASKHGAS\n");
// }
//
// page = getPage(3);
// PrintKeys(page);
// PrintChildren(page);
// free(page);*/
//
// char Key[] = "A\0";
// DriverRoot(Key);
// // DriverRemove("A\0");
// DriverRoot("B\0");
// DriverRoot("C\0");
// DriverRoot("D\0");
// DriverRoot("E\0");
// DriverRoot("F\0");
// DriverRoot("G\0");
// DriverRoot("H\0");
// DriverRoot("I\0");
// DriverRoot("J\0");
// //
// //
// DriverRoot("K\0");
// DriverRoot("L\0");
// DriverRoot("M\0");
// DriverRoot("N\0");
// DriverRoot("O\0");
//
// DriverRoot("P\0");
// DriverRoot("Q\0");
// DriverRoot("R\0");
//
// //
// DriverRoot("CAB80\0");
// DriverRoot("BAC90\0");
// DriverRoot("XAC90\0");
// DriverRoot("XAP90\0");
// DriverRoot("ROG10\0");
// DriverRoot("ZAP90\0");
// DriverRoot("YAP90\0");
// DriverRoot("YEP90\0");
// DriverRoot("YUP90\0");
// DriverRoot("ZEP90\0");
// DriverRoot("ACE90\0");
// DriverRoot("ACA90\0");
// DriverRoot("BEC90\0");
// DriverRoot("XEP90\0");
// DriverRoot("YOP90\0");
// DriverRoot("XOP80\0");
//
//
//
// DriverRemove("P\0");
// DriverRemove("Q\0");
// DriverRemove("CAB80\0");
// DriverRemove("C\0");
// DriverRemove("E\0");
// DriverRemove("B\0");
// DriverRemove("N\0");
// DriverRemove("O\0");
// DriverRemove("F\0");
// DriverRemove("G\0");
// DriverRemove("L\0");
// DriverRemove("K\0");
//
//
//
// /*
// // Search Test
// long FOUND_RRN = -1;
// int FOUND_POS = -1;
// if (SearchKey(ind->TreeRRN, "H\0", &FOUND_RRN, &FOUND_POS) == TRUE) {
// printf("Found!\n");
// printf("Achado no RRN: %lu\n", FOUND_RRN);
// printf("Posição: %d\n", FOUND_POS);
// } else {
// printf("Not found\n");
// }
// */
//
//
// DriverRemove("C\0");
// DriverRemove("I\0");
// DriverRemove("A\0");
// DriverRemove("F\0");
// DriverRemove("E\0");
// DriverRemove("D\0");
// DriverRemove("G\0");
// DriverRemove("H\0");
//
// //
// Page * page = getPage(5);
// PrintKeys(page);
// PrintChildren(page);
// free(page);
// //
// page = getPage(1);
// PrintKeys(page);
// PrintChildren(page);
// free(page);
//
// page = getPage(2);
// PrintKeys(page);
// PrintChildren(page);
// free(page);
//
// page = getPage(3);
// PrintKeys(page);
// PrintChildren(page);
// free(page);
// printf("\n\n\n\nRAIZ: %li\n", ind->TreeRRN);
//
//
//
// printtree(ind->TreeRRN);
// printf("\n\n\n\nRAIZ: %li\n", ind->TreeRRN);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment