preparo para debuguear tipo3

[z.facultad/75.06/emufs.git] / emufs / indice_bplus.c

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index 06d3ee1f07416ee271ccebbd1dc4571fd2de4d9b..50e65d33d3f5ce477395b64f827f0ced34cea45c 100644 (file)
--- a/emufs/indice_bplus.c
+++ b/emufs/indice_bplus.c
@@ -79,7 +79,7 @@ int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) {
                if (i < 0) {
                        /* La clave es menor que todas, debo insertarla */
                        b_plus_destruir_nodo(nodo);                     
-                       emufs_b_plus_insertar(idx,query);                       
+                       /*emufs_b_plus_insertar(idx,query);     */
                        return -1;
                }
                else {
@@ -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);
@@ -435,10 +435,11 @@ 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 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;
+       INDEX_DAT prepostkey;
+       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 *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;
 
@@ -468,26 +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],&prekey,0);
+                               b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prepostkey,0);
                                /* La elimino recursivamente */
-                               emufs_b_plus_eliminar(idx,prekey.clave,0);
+                               emufs_b_plus_eliminar(idx,prepostkey.clave,nodo->hijos[i]); /* CHEAT */
                                /* Remplazo mi clave key por la encontrada prekey */
-                               nodo->claves[i] = prekey.clave;
+                               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,prekey.clave);*/
-                       } else {                                
+                               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 */
-                                       
+                                       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,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,nodo->hijos[i+1]);                                     
                                } else {
-                                       /* Caso 2c */
-                               
+                                       /* 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 */
+                                       /* 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;
 }