From 568a401891b45d9764b41e5c2091a55178691611 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Fri, 28 May 2004 00:37:33 +0000 Subject: [PATCH] Laburando sobre el borrado con Nico, wish us luck --- emufs/b_plus_test.c | 15 ++-- emufs/indice_bplus.c | 159 +++++++++++++++++++++++++++++++++++++++++-- emufs/indice_bplus.h | 2 + 3 files changed, 168 insertions(+), 8 deletions(-) diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c index 2bc6eb3..3311353 100644 --- a/emufs/b_plus_test.c +++ b/emufs/b_plus_test.c @@ -26,18 +26,25 @@ emufs_b_plus_insertar(emu->indices,&querydata); } /* NOTA: Deberia devolver el mismo 104 y Exitcode = -1 */ -/*querydata.num_bloque = 104; +querydata.num_bloque = 104; querydata.clave.i_clave = 0; exitcode = emufs_b_plus_get_bloque(emu->indices,&querydata,0); printf("Numero de bloque donde grabar clave 0: %i\n",(int)(querydata.num_bloque)); -printf("Exit Code del get bloque: %i\n",exitcode);*/ +printf("Exit Code del get bloque: %i\n",exitcode); /* NOTA: Deberia devolver un numero de bloque X y Exitcode = 0 */ -/*querydata.num_bloque = 104; +querydata.num_bloque = 104; querydata.clave.i_clave = 25; exitcode = emufs_b_plus_get_bloque(emu->indices,&querydata,0); printf("Numero de bloque donde grabar clave 25: %i\n",(int)(querydata.num_bloque)); -printf("Exit Code del get bloque: %i\n",exitcode);*/ +printf("Exit Code del get bloque: %i\n",exitcode); + +querydata.clave.i_clave = 0; +querydata.num_bloque = 0; /* al pedo */ +exitcode = b_plus_existe_clave(emu->indices,&querydata,0); +printf("Exit Code del Buscar Clave: %i\n",exitcode); +exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,1); +printf("Exit Code del Borrar Clave: %i\n",exitcode); /* querydata.num_bloque = 2; diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index 10c7330..23a6f31 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,157 @@ 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--; + 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 */ +int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostkey, int search_type) +{ + int i = 0, j = 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; + /* Busco predecesor en la hoja */ + switch (search_type) { + + case 0: if (i < 0) return 0; + else { + *prepostkey = nodo->claves[i]; + return 1; + } + break; + + case 1: if (nodo->claves[i].i_clave == key.i_clave) return 0; + else { + *prepostkey = nodo->claves[i+1]; + return 1; + } + break; + } + + /* Busco sucesor en la hoja */ + if ((search_type == 1) && (i < 0)) return 0; + else if (i >= 0) { + *prepostkey = nodo->claves[i]; + return 1; + } + } 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+2],prepostkey,search_type); + if (exitcode == 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type); + } + } else { + /* Busco un sucesor, y funciona como getbloque... */ + exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type); + if (exitcode == 0) { + *prepostkey = nodo->claves[i+1]; + exitcode = 1; + } + } + + } + + 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; diff --git a/emufs/indice_bplus.h b/emufs/indice_bplus.h index 73b3e80..8aa2380 100644 --- a/emufs/indice_bplus.h +++ b/emufs/indice_bplus.h @@ -29,6 +29,8 @@ int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query); int emufs_b_plus_actualizar_nodo(INDEX_DAT *dataset); int emufs_b_plus_buscar(); int emufs_b_plus_destuir(); +int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node); +int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node); NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num); #endif -- 2.43.0