Compiling version para Nico aunque la anterior deberia haber estado functional

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

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index d0fdf58d5f184c446f3f8ab0a8903c5ab567fccd..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);                     
                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 {
                        return -1;
                }
                else {


@@ -399,15 +399,15 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepo
        return(exitcode);               
 }
 
        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;
 {
        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 */
                
        /* 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);
                
                /* 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 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 *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;
 
        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) {
                        /* 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 */
                                /* 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;
                                /* 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 */
                                /* 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) {
                        } 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);
                                        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 */
                                        /* 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;
                                        /* 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 */
                                        /* 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 */
                                } 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];
                                        }
                                        /* 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;
 }
        
        return -1;
 }