From: Alan Kennedy Date: Sat, 29 May 2004 05:27:51 +0000 (+0000) Subject: Compiling version para Nico aunque la anterior deberia haber estado functional X-Git-Tag: svn_import_r684~125 X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/648154e669d8796deef811a41dca154e253ac0d2?ds=inline Compiling version para Nico aunque la anterior deberia haber estado functional --- diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c index c7d70d7..cd40916 100644 --- a/emufs/b_plus_test.c +++ b/emufs/b_plus_test.c @@ -45,8 +45,6 @@ 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);*/ querydata.clave.i_clave = 4; if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&postkey,1)) == -1) @@ -57,7 +55,10 @@ if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&prekey,0)) printf("Busque una clave menor o igual a la mas chica del arbol\n"); 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); +/*exitcode = emufs_b_plus_reemplazar_clave(emu->indices,querydata.clave,prekey);*/ +querydata.clave.i_clave = 4; +exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0); +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 274fe79..50e65d3 100644 --- a/emufs/indice_bplus.c +++ b/emufs/indice_bplus.c @@ -399,15 +399,15 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepo return(exitcode); } -int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query) +int emufs_b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query, int num_node) { NODO_B_PLUS *nodo; int i; INDEX_DAT auxquery; - auxquery.clave = key; + auxquery.clave = key; /* Comienzo buscando la clave y obteniendo el nodo en donde esta */ - if (b_plus_existe_clave(idx,&auxquery,0) == 1) { + 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); @@ -436,10 +436,10 @@ int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query) 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; + int i = 0,j = 0,minclaves = 0, nivel_mayor1 = 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; + NODO_B_PLUS *node_y,*node_z; + if (nodo == NULL) { PERR("No leyo nodo bien"); return -1; } i = nodo->cant_claves - 1; minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1; @@ -469,44 +469,62 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node) /* Esta en el nodo interno, caso 2 */ cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]); if (cant_claves_child > minclaves) { + PERR("Entre caso 2a del eliminar"); /* 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); + emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i]); /* CHEAT */ /* Remplazo mi clave key por la encontrada prekey */ nodo->claves[i] = prepostkey.clave; + b_plus_grabar_nodo(idx,nodo,num_node); /* Remplazo la otra instancia de key en una hoja seguro por prekey */ - emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave); + emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]); } 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 */ + 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); /* La elimino recursivamente */ - emufs_b_plus_eliminar(idx,prepostkey.clave,0); + emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i+1]); /* CHEAT */ /* Remplazo mi clave key por la encontrada postkey */ nodo->claves[i] = prepostkey.clave; + b_plus_grabar_nodo(idx,nodo,num_node); /* Remplazo la otra instancia de key en una hoja seguro por postkey */ - emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave); + emufs_b_plus_reemplazar_clave(idx,key,prepostkey,nodo->hijos[i+1]); } 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); + /* Si es nivel mayor a 1, bajo clave pues no esta en NodoZ, otherwise no bajo */ + if (nodo->nivel > 1) { + nivel_mayor1 = 1; + node_y->claves[minclaves] = key; + } + for (j = 0; j < minclaves; ++j) node_y->claves[j+minclaves+nivel_mayor1] = node_z->claves[j]; + for (j = 0; j < minclaves+1; ++j) node_y->hijos[j+minclaves+nivel_mayor1] = node_z->hijos[j]; + node_y->cant_claves = minclaves*2+nivel_mayor1; /* 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]; } + nodo->cant_claves--; + 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); + /* Elimino recursivamente Key de NodeY, entrando por ese subtree */ + emufs_b_plus_eliminar(idx,key,nodo->hijos[i]); } } } - } - } + /* Termine caso 2 o 3, libero el nodo */ + b_plus_destruir_nodo(nodo); + return 0; + } return -1; } diff --git a/emufs/indice_bplus.h b/emufs/indice_bplus.h index ef6dc69..6f40dad 100644 --- a/emufs/indice_bplus.h +++ b/emufs/indice_bplus.h @@ -30,6 +30,6 @@ 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, INDEX_DAT *prepostkey, int search_type); -int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT replacement); +int emufs_b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query, int num_node); #endif