From: Alan Kennedy <kennedya@3dgames.com.ar>
Date: Sat, 29 May 2004 19:04:10 +0000 (+0000)
Subject: Listo Caso 3a Rotacion Derecha, going in for 3b y a probarlo con arboles de nivel > 1
X-Git-Tag: svn_import_r684~116
X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/65ec965b32ea1300412887755a368c2e62a16be8?ds=sidebyside

Listo Caso 3a Rotacion Derecha, going in for 3b y a probarlo con arboles de nivel > 1
---

diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c
index 00f0c6b..4e99c19 100644
--- a/emufs/b_plus_test.c
+++ b/emufs/b_plus_test.c
@@ -26,10 +26,10 @@ querydata.clave.i_clave = i;
 emufs_b_plus_insertar(emu->indices,&querydata);
 }
 
-/*printf("Insertando clave %i\n",3);
+printf("Insertando clave %i\n",3);
 querydata.num_bloque = 10;
 querydata.clave.i_clave = 3;
-emufs_b_plus_insertar(emu->indices,&querydata);*/
+emufs_b_plus_insertar(emu->indices,&querydata);
 
 /* NOTA: Deberia devolver el mismo 104 y Exitcode = -1 */
 querydata.num_bloque = 104;
@@ -67,13 +67,13 @@ 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 = 16;
+querydata.clave.i_clave = 16;
 exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0);
 printf("Exit Code del Borrar Clave: %i\n",exitcode);
 querydata.clave.i_clave = 32;
 exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,0);
-printf("Exit Code del Borrar Clave: %i\n",exitcode);*/
-querydata.clave.i_clave = 2;
+printf("Exit Code del Borrar Clave: %i\n",exitcode);
+querydata.clave.i_clave = 8;
 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 036d4cc..c693803 100644
--- a/emufs/indice_bplus.c
+++ b/emufs/indice_bplus.c
@@ -500,7 +500,7 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 					}
 					node_z->hijos[j] = node_z->hijos[j+1];
         			node_z->cant_claves--;
-					/* Grabo los cambios y listo */					
+					/* Grabo los cambios */					
 					b_plus_grabar_nodo(idx,node_z,nodo->hijos[i+1]);
 					b_plus_grabar_nodo(idx,node_y,nodo->hijos[i]);
 					b_plus_grabar_nodo(idx,nodo,num_node);
@@ -513,7 +513,40 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 						/* el sibling izquierdo me dara una key mediante rotacion Caso 3a */
 						PERR("Entre caso 3a left sibling del eliminar");
 						node_z = b_plus_leer_nodo(idx,nodo->hijos[i]);	
-						node_y = b_plus_leer_nodo(idx,nodo->hijos[i-1]);
+						node_y = b_plus_leer_nodo(idx,nodo->hijos[i-1]);					
+						if (node_z->nivel == 0) es_hoja = 1;
+					    /* Hago lugar en NodoZ para la clave que bajara desde el padre */						
+						/* Muevo el ultimo y restantes claves/punteros */
+						j = node_z->cant_claves - 1;												
+						node_z->hijos[j+2] = node_z->hijos[j+1];
+        				while (j >= 0){
+            				node_z->claves[j+1] = node_z->claves[j];			
+							node_z->hijos[j+1] = node_z->hijos[j];
+            				j--;
+        				}						
+						/* Hago la rotacion final segun sea hoja o no */
+						if (es_hoja) {
+							nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1];
+							node_z->claves[0] = node_y->claves[cant_claves_lsibling-1];
+							node_z->hijos[0] = node_y->hijos[cant_claves_lsibling-1];
+							node_y->hijos[cant_claves_lsibling-1] = node_y->hijos[cant_claves_lsibling]; /* cadena */
+							node_y->cant_claves--;
+							node_z->cant_claves++;
+						} else {
+							node_z->claves[0] = nodo->claves[i-1];
+							node_z->hijos[0] = node_y->hijos[cant_claves_lsibling];
+							nodo->claves[i-1] = node_y->claves[cant_claves_lsibling-1];
+							node_y->cant_claves--;
+							node_z->cant_claves++;
+						}
+						/* Grabo los cambios */						
+						b_plus_grabar_nodo(idx,node_y,nodo->hijos[i-1]);
+						b_plus_grabar_nodo(idx,node_z,nodo->hijos[i]);
+						b_plus_grabar_nodo(idx,nodo,num_node);
+						b_plus_destruir_nodo(node_y);
+						b_plus_destruir_nodo(node_z);					
+						/* Borro recursivamente KEY entrando por Child que ahora tiene minclaves+1 */
+						emufs_b_plus_eliminar(idx,key,nodo->hijos[i]);						
 					} else {
 						/* Caso 3b, debo bajar una clave y unificar con sibling disponible */
 						PERR("Entre caso 3b del eliminar");