From 935438fdd0279afe49eb59bf76cbe0db80be0282 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Sat, 29 May 2004 06:55:07 +0000 Subject: [PATCH 1/1] Borrar al 70 porciento aprox, un toque mas quizas, solo me resta handlear caso 3a 3b. Version libre de printfs --- emufs/b_plus_test.c | 11 +++++++++++ emufs/indice_bplus.c | 42 +++++++++++++++++++++++++----------------- 2 files changed, 36 insertions(+), 17 deletions(-) diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c index cd40916..5742a77 100644 --- a/emufs/b_plus_test.c +++ b/emufs/b_plus_test.c @@ -26,6 +26,11 @@ querydata.clave.i_clave = i; emufs_b_plus_insertar(emu->indices,&querydata); } +/*printf("Insertando clave %i\n",3); +querydata.num_bloque = 10; +querydata.clave.i_clave = 3; +emufs_b_plus_insertar(emu->indices,&querydata);*/ + /* NOTA: Deberia devolver el mismo 104 y Exitcode = -1 */ querydata.num_bloque = 104; querydata.clave.i_clave = 0; @@ -56,6 +61,12 @@ if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&prekey,0)) 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 = emufs_b_plus_reemplazar_clave(emu->indices,querydata.clave,prekey);*/ +/*querydata.clave.i_clave = 32; +exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,2); +printf("Exit Code del Borrar Clave: %i\n",exitcode); +querydata.clave.i_clave = 16; +exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,2); +printf("Exit Code del Borrar Clave: %i\n",exitcode);*/ querydata.clave.i_clave = 4; exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0); printf("Exit Code del Borrar Clave: %i\n",exitcode); diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c index 50e65d3..c192e5d 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -234,9 +234,11 @@ int b_plus_insert_nonfull(INDICE *idx, NODO_B_PLUS *nodo, int num_nodo, INDEX_DA i = nodo->cant_claves-1; if ( nodo->nivel == 0 ){ + /* Muevo siempre el encadenamiento */ + nodo->hijos[i+2] = nodo->hijos[i+1]; + /* Ahora muevo las claves y sus punteros a bloques del dat */ 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->claves[i+1] = nodo->claves[i]; nodo->hijos[i+1] = nodo->hijos[i]; i--; } @@ -361,9 +363,9 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepo 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 { + else { prepostkey->clave = nodo->claves[i+1]; - prepostkey->num_bloque = nodo->hijos[i+i]; + prepostkey->num_bloque = nodo->hijos[i+1]; exitcode = 1; } break; @@ -410,7 +412,7 @@ int emufs_b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query, int n if (b_plus_existe_clave(idx,&auxquery,num_node) == 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); + /*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; @@ -484,8 +486,7 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) if (cant_claves_child > minclaves) { PERR("Entre caso 2b del eliminar"); /* Caso 2b, comienzo buscando la clave sucesor inmediata */ - b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1); - printf("Bloque .dat en prepostkey %i\n",prepostkey.num_bloque); + b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],&prepostkey,1); /* La elimino recursivamente */ emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i+1]); /* CHEAT */ /* Remplazo mi clave key por la encontrada postkey */ @@ -494,6 +495,7 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) /* Remplazo la otra instancia de key en una hoja seguro por postkey */ emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]); } else { + PERR("Entre caso 2c del eliminar"); /* 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]); @@ -515,16 +517,23 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) b_plus_grabar_nodo(idx,nodo,num_node); b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]); b_plus_destruir_nodo(node_y); - b_plus_destruir_nodo(node_z); + b_plus_destruir_nodo(node_z); /* Elimino recursivamente Key de NodeY, entrando por ese subtree */ - emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); - } + emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); + /* Caso muy particular, si hize un merge de la unica clave de una raiz con sus hijos */ + if ((nodo->nivel == 1) && (nodo->cant_claves == 0)) { + /* Debo establecer como nueva raiz, el NodoY */ + node_y = b_plus_leer_nodo(idx,nodo->hijos[i]); + b_plus_grabar_nodo(idx,node_y,0); + truncate(idx->filename,SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); + } } - } - /* Termine caso 2 o 3, libero el nodo */ - b_plus_destruir_nodo(nodo); - return 0; - } + } + } + /* Termine caso 2 o 3, libero el nodo */ + b_plus_destruir_nodo(nodo); + return 0; + } return -1; } @@ -537,8 +546,7 @@ int b_plus_get_num_nodo(INDICE *idx) fp = fopen(idx->filename, "ab"); if (fp == NULL) return -1; - num = ftell(fp)/(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); - printf("Num Nodo Nuevo: %i\n",num); + num = ftell(fp)/(SIZE_B_PLUS_HEADER+idx->size_claves+idx->size_hijos); fclose(fp); return num; } -- 2.43.0