X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/5f476f3fa9229877b70262ae8c3629bbec92ef58..a666806d9361a2876a07941b8d2bb5c973e1557e:/emufs/indice_bplus.c diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index 10c7330..7165daf 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -66,12 +66,12 @@ int emufs_b_plus_crear(INDICE *idx) { */ 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 */ @@ -176,7 +176,7 @@ int b_plus_destruir_nodo(NODO_B_PLUS *nodo) 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; @@ -288,6 +288,161 @@ int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query) return 0; } +/** 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 en que bloque deberia ir */ + while ( i >= 0 && query->clave.i_clave != nodo->claves[i].i_clave ) i--; + b_plus_destruir_nodo(nodo); + if (i < 0) return 0; /* No encontre la clave */ + else return 1; /* Encontre la clave */ + } + 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, CLAVE *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) { + printf ("Entre en hoja nro %i\n",num_node); + 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 = nodo->claves[i-1]; + else *prepostkey = nodo->claves[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 = nodo->claves[i+1]; + 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... */ + printf("Voy a buscar en hijo nro: %i\n",nodo->hijos[i+1]); + 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 = nodo->claves[i+1]; + exitcode = 1; + } else exitcode = -1; + } + } + + /* Libero y devuelvo exitcode */ + b_plus_destruir_nodo(nodo); + return(exitcode); +} + +int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) +{ + int i = 0,j = 0,minclaves = 0, cant_claves_child = 0; + NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node); + 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 */ + + } else { + cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]); + if (cant_claves_child > minclaves) { + /* Caso 2b */ + + } else { + /* Caso 2c */ + + } + } + + + } + } + + return -1; +} + int b_plus_get_num_nodo(INDICE *idx) { FILE *fp;