From a29c2ba26fc37a7a01e916911f0a77cc9ccd02c5 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Sat, 29 May 2004 01:16:58 +0000 Subject: [PATCH] Sigo con el Borrar, de a poco pero seguro, se agrega reemplazo de clave|dato en una hoja usado en el borrar para rotar and shit --- emufs/b_plus_test.c | 18 ++++---- emufs/indice_bplus.c | 101 ++++++++++++++++++++++++++++++++----------- emufs/indice_bplus.h | 6 +-- 3 files changed, 87 insertions(+), 38 deletions(-) diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c index 94242f0..c7d70d7 100644 --- a/emufs/b_plus_test.c +++ b/emufs/b_plus_test.c @@ -7,7 +7,7 @@ int main(int argc, char* argv[]) { /* Locals */ INDEX_DAT querydata; -CLAVE postkey, prekey; +INDEX_DAT postkey, prekey; int i = 0; int exitcode = 0; int tam_nodo = SIZE_B_PLUS_HEADER + sizeof(CLAVE)*5 + sizeof(CLAVE)*6; @@ -35,27 +35,29 @@ 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.clave.i_clave = 25; +querydata.clave.i_clave = 5; 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); -querydata.clave.i_clave = 0; +querydata.clave.i_clave = 4; querydata.num_bloque = 0; /* al pedo */ exitcode = b_plus_existe_clave(emu->indices,&querydata,0); +if (exitcode == 1) printf("El nodo hoja donde esta la clave %i es %i\n",querydata.clave.i_clave,querydata.num_bloque); 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); +/*exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,1); +printf("Exit Code del Borrar Clave: %i\n",exitcode);*/ querydata.clave.i_clave = 4; -prekey.i_clave = 555; if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&postkey,1)) == -1) printf("Busque una clave mayor o igual a la mas grande del arbol\n"); -printf("El Sucesor de la clave %i es %i\n",querydata.clave.i_clave,postkey.i_clave); +printf("El Sucesor de la clave %i es %i cuyo hijo es %i\n",querydata.clave.i_clave,postkey.clave.i_clave,postkey.num_bloque); if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&prekey,0)) == -1) printf("Busque una clave menor o igual a la mas chica del arbol\n"); -printf("El Predecesor de la clave %i es %i\n",querydata.clave.i_clave,prekey.i_clave); +printf("El Predecesor de la clave %i es %i cuyo hijo es %i\n",querydata.clave.i_clave,prekey.clave.i_clave,prekey.num_bloque); + +exitcode = b_plus_reemplazar_clave(emu->indices,querydata.clave,prekey); /* querydata.num_bloque = 2; diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index 7165daf..06d3ee1 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -27,7 +27,7 @@ NODO_B_PLUS *b_plus_crearnodo(INDICE *idx) { memset(nodo->claves,-1,idx->size_claves); memset(nodo->hijos,-1,idx->size_hijos); - return nodo; + return nodo; } /** Crea el archivo indice B+ */ @@ -303,11 +303,18 @@ int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node) /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */ if (nodo->nivel == 0) { - /* Vemos en que bloque deberia ir */ + /* Vemos si esta la clave */ 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 */ + 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 */ @@ -329,31 +336,34 @@ int b_plus_cant_claves_nodo(INDICE *idx, int num_node) /* 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 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) { - printf ("Entre en hoja nro %i\n",num_node); + if (nodo->nivel == 0) { while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i; - switch (search_type) { - + 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]; + 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; - + 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]; + else { + prepostkey->clave = nodo->claves[i+1]; + prepostkey->num_bloque = nodo->hijos[i+i]; exitcode = 1; } break; @@ -372,15 +382,15 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke /* 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]); + /* 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 (exitcode == 0) { if (i < nodo->cant_claves-1) { - *prepostkey = nodo->claves[i+1]; + prepostkey->clave = nodo->claves[i+1]; exitcode = 1; } else exitcode = -1; + } } } @@ -389,8 +399,43 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke 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 prekey; 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; @@ -418,13 +463,19 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) /* 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 */ + /* 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 */ - + /* Caso 2a, comienzo buscando la clave previa inmediata */ + b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prekey,0); + /* La elimino recursivamente */ + emufs_b_plus_eliminar(idx,prekey.clave,0); + /* Remplazo mi clave key por la encontrada prekey */ + nodo->claves[i] = prekey.clave; + /* Remplazo la otra instancia de key en una hoja seguro por prekey */ + /*emufs_b_plus_reemplazar_clave(idx,key,prekey.clave);*/ } else { cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]); if (cant_claves_child > minclaves) { @@ -434,9 +485,7 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) /* Caso 2c */ } - } - - + } } } diff --git a/emufs/indice_bplus.h b/emufs/indice_bplus.h index 81963fc..ef6dc69 100644 --- a/emufs/indice_bplus.h +++ b/emufs/indice_bplus.h @@ -26,12 +26,10 @@ typedef struct nodo_b_plus { int emufs_b_plus_crear(INDICE *idx); int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node); 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); -int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostkey, int search_type); +int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepostkey, int search_type); +int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT replacement); #endif -- 2.43.0