X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/84522123b3e93279cdb2bebd54a134dce2cacd1f..140c0b9274254d1e18c27ff2678613fd42d550f0:/emufs/indice_bplus.c?ds=inline diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index a30058b..d0fdf58 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -1,19 +1,20 @@ /** Arbol B+ */ -#include "b_plus.h" +#include "indices.h" +#include "indice_bplus.h" /**#*#*#*#*#**#*#*#*#*#* Private prototypes*#*#*#*#*#**#*#*#*#*#**#*#*#*/ -int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node); -NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node); -NODO_B_PLUS *b_plus_crearnodo(INDEXSPECS *idx); +int b_plus_grabar_nodo(INDICE *idx, NODO_B_PLUS *nodo, int num_node); +NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num_node); +NODO_B_PLUS *b_plus_crearnodo(INDICE *idx); int b_plus_destruir_nodo(NODO_B_PLUS *nodo); -int b_plus_split_child(INDEXSPECS *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode); -int b_plus_insert_nonfull(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query); -int b_plus_insertar(INDEXSPECS *idx, INDEX_DAT *query); -int b_plus_get_num_nodo(INDEXSPECS *idx); +int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode); +int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query); +int b_plus_insertar(INDICE *idx, INDEX_DAT *query); +int b_plus_get_num_nodo(INDICE *idx); /**#*#*#*#*#**#*#*#*#*#*FIN PROTOTYPES*#*#*#*#*#**#*#*#*#*#**#*#*#*#*#*/ /** Crea un nuevo nodo y lo inicializa */ -NODO_B_PLUS *b_plus_crearnodo(INDEX *idx) { +NODO_B_PLUS *b_plus_crearnodo(INDICE *idx) { NODO_B_PLUS *nodo = (NODO_B_PLUS*)malloc(sizeof(NODO_B_PLUS)); if (nodo == NULL) return NULL; @@ -21,16 +22,16 @@ NODO_B_PLUS *b_plus_crearnodo(INDEX *idx) { nodo->cant_claves = 0; /* Calculamos lo que ocupan las cadenas de bytes claves + hijos */ - nodo->claves = (int*)malloc(idx->size_claves); + nodo->claves = (CLAVE*)malloc(idx->size_claves); nodo->hijos = (int*)malloc(idx->size_hijos); memset(nodo->claves,-1,idx->size_claves); memset(nodo->hijos,-1,idx->size_hijos); - return nodo; + return nodo; } /** Crea el archivo indice B+ */ -int emufs_b_plus_crear(INDEXSPECS *idx) { +int emufs_b_plus_crear(INDICE *idx) { FILE *fp; NODO_B_PLUS *raiz; @@ -63,22 +64,22 @@ int emufs_b_plus_crear(INDEXSPECS *idx) { * return -1 - No hay clave, inserto clave de nuevo bloques * return 1 - Hubo falla de lectura de un nodo, Abortar */ -int emufs_b_plus_get_bloque(INDEX *idx, INDEX_DAT *query, int num_node) { +int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) { + int i,exitcode = 0; NODO_B_PLUS *nodo; nodo = b_plus_leer_nodo(idx,num_node); if (nodo == NULL) return 1; - int i = nodo->cant_claves - 1; - int exitcode = 0; - + i = nodo->cant_claves - 1; + /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */ if (nodo->nivel == 0) { /* Vemos en que bloque deberia ir */ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i] ) i--; + while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; if (i < 0) { /* La clave es menor que todas, debo insertarla */ b_plus_destruir_nodo(nodo); - emufs_b_plus_insertar(idx,query); + /*emufs_b_plus_insertar(idx,query);*/ return -1; } else { @@ -90,7 +91,7 @@ int emufs_b_plus_get_bloque(INDEX *idx, INDEX_DAT *query, int num_node) { } else { /* Buscamos por donde descender al siguiente nivel */ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i] ) i--; + while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; i++; num_node = nodo->hijos[i]; b_plus_destruir_nodo(nodo); @@ -99,7 +100,7 @@ int emufs_b_plus_get_bloque(INDEX *idx, INDEX_DAT *query, int num_node) { } } -NODO_B_PLUS *b_plus_leer_nodo(INDEX *idx, int num_node) { +NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num_node) { /*int i = 0;*/ FILE *fp; @@ -139,7 +140,7 @@ NODO_B_PLUS *b_plus_leer_nodo(INDEX *idx, int num_node) { /*printf("Dumping Node_%i\n",num_node); printf("Nivel: %i Cant Claves: %i\n",memnode->nivel,memnode->cant_claves); printf("Claves:"); - for (i = 0; i < idx->size_claves/sizeof(int); ++i) printf(" %i",memnode->claves[i]); + for (i = 0; i < idx->size_claves/sizeof(CLAVE); ++i) printf(" %i",memnode->claves[i].i_clave); printf("\nHijos:"); for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]); printf("\nEnd Dump\n"); */ @@ -148,7 +149,7 @@ NODO_B_PLUS *b_plus_leer_nodo(INDEX *idx, int num_node) { } -int b_plus_grabar_nodo(INDEX *idx, NODO_B_PLUS *nodo, int num_node) +int b_plus_grabar_nodo(INDICE *idx, NODO_B_PLUS *nodo, int num_node) { FILE *fp; @@ -172,10 +173,10 @@ int b_plus_destruir_nodo(NODO_B_PLUS *nodo) return 0; } -int b_plus_split_child(INDEX *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode) +int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode) { /* locals */ - int minclaves = ceil(idx->size_hijos/sizeof(int)/2)-1; + int minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1; int numbrother,j = 0; int es_interno = 1; @@ -226,32 +227,32 @@ int b_plus_split_child(INDEX *idx, int numparent, NODO_B_PLUS *parent, int ithch } -int b_plus_insert_nonfull(INDEX *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query) +int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT *query) { int i, num_nodo_hijo; NODO_B_PLUS *hijo; i = nodo->cant_claves-1; if ( nodo->nivel == 0 ){ - while ( i >= 0 && query->clave.i_clave < nodo->claves[i] ){ + while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ){ nodo->claves[i+1] = nodo->claves[i]; nodo->hijos[i+2] = nodo->hijos[i+1]; nodo->hijos[i+1] = nodo->hijos[i]; i--; } - nodo->claves[i+1] = query->clave.i_clave; + nodo->claves[i+1] = query->clave; nodo->hijos[i+1] = query->num_bloque; nodo->cant_claves++; b_plus_grabar_nodo(idx, nodo, num_nodo); } else { - while ( i >= 0 && query->clave.i_clave < nodo->claves[i] ) + while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; i++; num_nodo_hijo = nodo->hijos[i]; hijo = b_plus_leer_nodo(idx, num_nodo_hijo); - if ( hijo->cant_claves == idx->size_claves/sizeof(int) ) { + if ( hijo->cant_claves == idx->size_claves/sizeof(CLAVE) ) { b_plus_split_child(idx, num_nodo, nodo, i, hijo); - if ( query->clave.i_clave > nodo->claves[i] ) + if ( query->clave.i_clave > nodo->claves[i].i_clave ) i++; } if (hijo) b_plus_destruir_nodo(hijo); @@ -263,12 +264,12 @@ int b_plus_insert_nonfull(INDEX *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DAT return 0; } -int emufs_b_plus_insertar(INDEX *idx, INDEX_DAT *query) +int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query) { NODO_B_PLUS *raiz; raiz = b_plus_leer_nodo(idx, 0); - if ( raiz->cant_claves == idx->size_claves/sizeof(int) ) { + if ( raiz->cant_claves == idx->size_claves/sizeof(CLAVE) ) { NODO_B_PLUS *new_root = b_plus_crearnodo(idx); new_root->nivel = raiz->nivel + 1; new_root->hijos[0] = b_plus_get_num_nodo(idx); @@ -287,7 +288,230 @@ int emufs_b_plus_insertar(INDEX *idx, INDEX_DAT *query) return 0; } -int b_plus_get_num_nodo(INDEX *idx) +/** Busca una clave dentro del arbol e indica si existe o no + * Posibilidades: return 1 - Encontro la clave + * return 0 - No encontro la clave + * return -1 - Hubo falla de lectura de un nodo, Abortar + */ +int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node) +{ + int i,exitcode = 0; + NODO_B_PLUS *nodo; + nodo = b_plus_leer_nodo(idx,num_node); + if (nodo == NULL) return -1; + i = nodo->cant_claves - 1; + + /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */ + if (nodo->nivel == 0) { + /* Vemos si esta la clave */ + while ( i >= 0 && query->clave.i_clave != nodo->claves[i].i_clave ) i--; + if (i < 0) + { + b_plus_destruir_nodo(nodo); + return 0; /* No encontre la clave */ + } else { + /* Encontre la clave, guardo el nodo donde esta! */ + query->num_bloque = num_node; + b_plus_destruir_nodo(nodo); + return 1; + } + } + else { + /* Buscamos por donde descender al siguiente nivel */ + while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--; + i++; + num_node = nodo->hijos[i]; + b_plus_destruir_nodo(nodo); + exitcode = b_plus_existe_clave(idx,query,num_node); + return exitcode; + } +} + +int b_plus_cant_claves_nodo(INDICE *idx, int num_node) +{ + NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node); + if (nodo == NULL) return -1; + return nodo->cant_claves; +} + +/* Search_Type: 0 - Predecesor, 1 - Sucesor + Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre, -1 Error */ +int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepostkey, int search_type) +{ + int i = 0, exitcode = 0; + NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node); + if (nodo == NULL) return -1; + i = nodo->cant_claves - 1; + + if (nodo->nivel == 0) { + while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i; + switch (search_type) { + /* Busco predecesor en la hoja */ + case 0: if (i <= 0) exitcode = 0; + else { + if (nodo->claves[i].i_clave == key.i_clave) { + prepostkey->clave = nodo->claves[i-1]; + prepostkey->num_bloque = nodo->hijos[i-1]; + } else { + prepostkey->clave = nodo->claves[i]; + prepostkey->num_bloque = nodo->hijos[i]; + } + exitcode = 1; + } + break; + /* Busco sucesor en la hoja */ + case 1: if ((nodo->claves[i].i_clave == key.i_clave) && (i == nodo->cant_claves-1)) exitcode = 0; + else { + prepostkey->clave = nodo->claves[i+1]; + prepostkey->num_bloque = nodo->hijos[i+i]; + exitcode = 1; + } + break; + } + } else { + /* Veo por que rama debo seguir buscando el pre o post */ + while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i; + if (search_type == 0) { + if (i < 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type); + else { + /* Busco primero por la rama derecha, sino por la izquierda */ + exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type); + if (exitcode == 0) + exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i],prepostkey,search_type); + } + /* Handleo busqueda de clave menor o igual que todas */ + if (exitcode == 0) exitcode = -1; + } else { + /* Busco un sucesor, y funciona como getbloque... */ + exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type); + /* Veo si tengo que devolver la clave izquierda del padre del que acabo de buscar */ + if (exitcode == 0) { + if (i < nodo->cant_claves-1) { + prepostkey->clave = nodo->claves[i+1]; + exitcode = 1; + } else exitcode = -1; + } + } + } + + /* Libero y devuelvo exitcode */ + b_plus_destruir_nodo(nodo); + return(exitcode); +} + +int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query) +{ + NODO_B_PLUS *nodo; + int i; + INDEX_DAT auxquery; + auxquery.clave = key; + + /* Comienzo buscando la clave y obteniendo el nodo en donde esta */ + if (b_plus_existe_clave(idx,&auxquery,0) == 1) { + + /* Levanto el nodo y busco donde esta la clave */ + printf("El reemplazar encontro la clave %i y en el nodo %i\n",auxquery.clave.i_clave,(int)auxquery.num_bloque); + nodo = b_plus_leer_nodo(idx,auxquery.num_bloque); + if (nodo == NULL) return -1; + i = nodo->cant_claves - 1; + + /* Busco la clave y reemplazo */ + while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; + if (i < 0) return -1; /* Error, no esta la clave */ + + /* Cheque por las dudas si es hoja o interno, aunque deberia ser hoja */ + if (nodo->nivel > 0) { + nodo->claves[i] = query.clave; + } else { + nodo->claves[i] = query.clave; + nodo->hijos[i] = query.num_bloque; + } + b_plus_grabar_nodo(idx,nodo,auxquery.num_bloque); + b_plus_destruir_nodo(nodo); + return 0; + } + else return -1; +} + +int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) +{ + INDEX_DAT prepostkey; + int i = 0,j = 0,minclaves = 0, cant_claves_child = 0; + NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node); + NODO_B_PLUS *hijoder,*hijoizq; + if (nodo == NULL) return -1; + i = nodo->cant_claves - 1; + minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1; + + /* Si es hoja, borro directamente la clave. No se producira underflow + pues lo asegura la recursividad del delete */ + if (nodo->nivel == 0) { + while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; + if (i < 0) return -1; + /* Encontre la clave en la pos i, la borro */ + for (j = i; j < nodo->cant_claves-1; ++j) { + nodo->claves[j] = nodo->claves[j+1]; + nodo->hijos[j] = nodo->hijos[j+1]; + } + nodo->hijos[j] = nodo->hijos[j+1]; + nodo->cant_claves--; + + /* Grabo el nodo actualizado en disco */ + b_plus_grabar_nodo(idx,nodo,num_node); + b_plus_destruir_nodo(nodo); + return 0; + } else { + /* Me debo fijar si esta la clave en este nodo interno, sino busco */ + while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i; + if (i < 0) { + /* No esta en este nodo interno, caso 3 */ + } else { + /* Esta en el nodo interno, caso 2 */ + cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]); + if (cant_claves_child > minclaves) { + /* Caso 2a, comienzo buscando la clave previa inmediata */ + b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prepostkey,0); + /* La elimino recursivamente */ + emufs_b_plus_eliminar(idx,prepostkey.clave,0); + /* Remplazo mi clave key por la encontrada prekey */ + nodo->claves[i] = prepostkey.clave; + /* Remplazo la otra instancia de key en una hoja seguro por prekey */ + emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave); + } else { + cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]); + if (cant_claves_child > minclaves) { + /* Caso 2b, comienzo buscando la clave previa inmediata */ + b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1); + /* La elimino recursivamente */ + emufs_b_plus_eliminar(idx,prepostkey.clave,0); + /* Remplazo mi clave key por la encontrada postkey */ + nodo->claves[i] = prepostkey.clave; + /* Remplazo la otra instancia de key en una hoja seguro por postkey */ + emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave); + } else { + /* Caso 2c debo hacer un merge de la clave con hijo izq y der */ + node_y = b_plus_leer_nodo(idx,nodo->hijos[i]); + node_z = b_plus_leer_nodo(idx,nodo->hijos[i+1]); + /* Bajo la clave Key a NodoY y muevo todo lo de NodoZ a NodoY */ + node_y->claves[minclaves] = nodo->claves[i]; + for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+1] = node_z->claves[j]; + for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+1] = node_z->hijos[j]; + b_plus_destruir_nodo(z); + /* Shifteo en el nodo padre NODO, para quitar la que bajo */ + for (j = i; j < nodo->cant_claves-1; ++j) { + nodo->claves[j] = nodo->claves[j+1]; + nodo->hijos[j+1] = nodo->hijos[j+2]; + } + } + } + } + } + } + + return -1; +} + +int b_plus_get_num_nodo(INDICE *idx) { FILE *fp; int num;