Sigo con el Borrar, de a poco pero seguro, se agrega reemplazo de clave|dato en una...

diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c
index 94242f0d3b50b32b123abce4f07ecdf01faf91f9..c7d70d7a642c9c5e593505de8f658b4d74d87e47 100644 (file)
--- a/emufs/b_plus_test.c
+++ b/emufs/b_plus_test.c
@@ -7,7 +7,7 @@ int main(int argc, char* argv[]) {
 
 /* Locals */
 INDEX_DAT querydata;
 
 /* Locals */
 INDEX_DAT querydata;

-CLAVE postkey, prekey;
+INDEX_DAT postkey, prekey;

 int i = 0;
 int exitcode = 0;
 int tam_nodo = SIZE_B_PLUS_HEADER + sizeof(CLAVE)*5 + sizeof(CLAVE)*6;
 int i = 0;
 int exitcode = 0;
 int tam_nodo = SIZE_B_PLUS_HEADER + sizeof(CLAVE)*5 + sizeof(CLAVE)*6;


@@ -35,27 +35,29 @@ printf("Exit Code del get bloque: %i\n",exitcode);
 
 /* NOTA: Deberia devolver un numero de bloque X y Exitcode = 0 */
 querydata.num_bloque = 104;
 
 /* NOTA: Deberia devolver un numero de bloque X y Exitcode = 0 */
 querydata.num_bloque = 104;

-querydata.clave.i_clave = 25;
+querydata.clave.i_clave = 5;

 exitcode = emufs_b_plus_get_bloque(emu->indices,&querydata,0);
 printf("Numero de bloque donde grabar clave 25: %i\n",(int)(querydata.num_bloque));
 printf("Exit Code del get bloque: %i\n",exitcode);
 
 exitcode = emufs_b_plus_get_bloque(emu->indices,&querydata,0);
 printf("Numero de bloque donde grabar clave 25: %i\n",(int)(querydata.num_bloque));
 printf("Exit Code del get bloque: %i\n",exitcode);
 

-querydata.clave.i_clave = 0;
+querydata.clave.i_clave = 4;

 querydata.num_bloque = 0; /* al pedo */
 exitcode = b_plus_existe_clave(emu->indices,&querydata,0);
 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);
 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);
+/*exitcode = emufs_b_plus_eliminar(emu->indices,querydata.clave,1);
+printf("Exit Code del Borrar Clave: %i\n",exitcode);*/

 
 querydata.clave.i_clave = 4;
 
 querydata.clave.i_clave = 4;

-prekey.i_clave = 555;

 if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&postkey,1)) == -1)
        printf("Busque una clave mayor o igual a la mas grande del arbol\n");
 if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&postkey,1)) == -1)
        printf("Busque una clave mayor o igual a la mas grande del arbol\n");

-printf("El Sucesor de la clave %i es %i\n",querydata.clave.i_clave,postkey.i_clave);
+printf("El Sucesor de la clave %i es %i cuyo hijo es %i\n",querydata.clave.i_clave,postkey.clave.i_clave,postkey.num_bloque);

 
 if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&prekey,0)) == -1)
        printf("Busque una clave menor o igual a la mas chica del arbol\n");
 
 if ((exitcode = b_plus_buscar_prepost(emu->indices,querydata.clave,0,&prekey,0)) == -1)
        printf("Busque una clave menor o igual a la mas chica del arbol\n");

-printf("El Predecesor de la clave %i es %i\n",querydata.clave.i_clave,prekey.i_clave);
+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);

 
 /*
 querydata.num_bloque = 2;
 
 /*
 querydata.num_bloque = 2;

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index 7165daf8a074667da5221d5fa2b02d876a665f69..06d3ee1f07416ee271ccebbd1dc4571fd2de4d9b 100644 (file)
--- a/emufs/indice_bplus.c
+++ b/emufs/indice_bplus.c
@@ -27,7 +27,7 @@ NODO_B_PLUS *b_plus_crearnodo(INDICE *idx) {
        memset(nodo->claves,-1,idx->size_claves);
        memset(nodo->hijos,-1,idx->size_hijos);
        
        memset(nodo->claves,-1,idx->size_claves);
        memset(nodo->hijos,-1,idx->size_hijos);
        

-    return nodo;       
+    return nodo;

 }
 
 /** Crea el archivo indice B+ */
 }
 
 /** Crea el archivo indice B+ */


@@ -303,11 +303,18 @@ int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node)
                
        /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
        if (nodo->nivel == 0) {
                
        /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
        if (nodo->nivel == 0) {

-        /* Vemos en que bloque deberia ir */
+        /* Vemos si esta la clave */

                while ( i >= 0 && query->clave.i_clave != nodo->claves[i].i_clave ) i--;
                while ( i >= 0 && query->clave.i_clave != nodo->claves[i].i_clave ) i--;

-               b_plus_destruir_nodo(nodo);
-               if (i < 0) return 0; /* No encontre la clave */
-               else return 1; /* Encontre la clave */                  
+               if (i < 0)
+               {
+                       b_plus_destruir_nodo(nodo);
+                       return 0; /* No encontre la clave */
+               } else  {
+                       /* Encontre la clave, guardo el nodo donde esta! */
+                       query->num_bloque = num_node;
+                       b_plus_destruir_nodo(nodo);
+                       return 1;
+               }

        }
        else {
                /* Buscamos por donde descender al siguiente nivel */
        }
        else {
                /* Buscamos por donde descender al siguiente nivel */


@@ -329,31 +336,34 @@ int b_plus_cant_claves_nodo(INDICE *idx, int num_node)
 
 /* Search_Type: 0 - Predecesor, 1 - Sucesor
    Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre, -1 Error */
 
 /* Search_Type: 0 - Predecesor, 1 - Sucesor
    Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre, -1 Error */

-int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostkey, int search_type)
+int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepostkey, int search_type)

 {
        int i = 0, exitcode = 0;
        NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);             
        if (nodo == NULL) return -1;
        i = nodo->cant_claves - 1;
        
 {
        int i = 0, exitcode = 0;
        NODO_B_PLUS *nodo = b_plus_leer_nodo(idx,num_node);             
        if (nodo == NULL) return -1;
        i = nodo->cant_claves - 1;
        

-       if (nodo->nivel == 0) {
-               printf ("Entre en hoja nro %i\n",num_node);
+       if (nodo->nivel == 0) {         

                while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          
                while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          

-               switch (search_type) {
-                       
+               switch (search_type) {                  

                        /* Busco predecesor en la hoja */                       
                        case 0: if (i <= 0) exitcode = 0;
                                        else {                                          
                        /* Busco predecesor en la hoja */                       
                        case 0: if (i <= 0) exitcode = 0;
                                        else {                                          

-                                               if (nodo->claves[i].i_clave == key.i_clave)     *prepostkey = nodo->claves[i-1];
-                                               else *prepostkey = nodo->claves[i];                                             
+                                               if (nodo->claves[i].i_clave == key.i_clave)     {
+                                                       prepostkey->clave = nodo->claves[i-1];
+                                                       prepostkey->num_bloque = nodo->hijos[i-1];
+                                               } else {
+                                                       prepostkey->clave = nodo->claves[i];
+                                                       prepostkey->num_bloque = nodo->hijos[i];
+                                               }

                                                exitcode = 1;
                                        }
                                                exitcode = 1;
                                        }

-                                       break;
-
+                                       break;                                  

                        /* Busco sucesor en la hoja */                                                          
                        case 1: if ((nodo->claves[i].i_clave == key.i_clave) && (i == nodo->cant_claves-1)) exitcode = 0;
                        /* Busco sucesor en la hoja */                                                          
                        case 1: if ((nodo->claves[i].i_clave == key.i_clave) && (i == nodo->cant_claves-1)) exitcode = 0;

-                                       else {
-                                               *prepostkey = nodo->claves[i+1];
+                                       else {                                          
+                                               prepostkey->clave = nodo->claves[i+1];
+                                               prepostkey->num_bloque = nodo->hijos[i+i];

                                                exitcode = 1;
                                        }
                                        break;
                                                exitcode = 1;
                                        }
                                        break;


@@ -372,15 +382,15 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke
                        /* Handleo busqueda de clave menor o igual que todas */
                        if (exitcode == 0) exitcode = -1;
                } else  {
                        /* Handleo busqueda de clave menor o igual que todas */
                        if (exitcode == 0) exitcode = -1;
                } else  {

-                       /* Busco un sucesor, y funciona como getbloque... */
-                       printf("Voy a buscar en hijo nro: %i\n",nodo->hijos[i+1]);
+                       /* Busco un sucesor, y funciona como getbloque... */                    

                        exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
                        /* Veo si tengo que devolver la clave izquierda del padre del que acabo de buscar */
                        exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
                        /* Veo si tengo que devolver la clave izquierda del padre del que acabo de buscar */

-                       if (exitcode == 0)
+                       if (exitcode == 0) {

                                if (i < nodo->cant_claves-1) {
                                if (i < nodo->cant_claves-1) {

-                                       *prepostkey = nodo->claves[i+1];
+                                       prepostkey->clave = nodo->claves[i+1];

                                        exitcode = 1;
                                } else  exitcode = -1;
                                        exitcode = 1;
                                } else  exitcode = -1;

+                       }

                }               
        }
        
                }               
        }
        


@@ -389,8 +399,43 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke
        return(exitcode);               
 }
 
        return(exitcode);               
 }
 

+int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT query)
+{
+       NODO_B_PLUS *nodo;
+       int i;
+       INDEX_DAT auxquery;
+       auxquery.clave = key;
+               
+       /* Comienzo buscando la clave y obteniendo el nodo en donde esta */
+       if (b_plus_existe_clave(idx,&auxquery,0) == 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);
+               nodo = b_plus_leer_nodo(idx,auxquery.num_bloque);
+               if (nodo == NULL) return -1;
+               i = nodo->cant_claves - 1;
+               
+               /* Busco la clave y reemplazo */
+               while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i;
+               if (i < 0) return -1; /* Error, no esta la clave */
+               
+               /* Cheque por las dudas si es hoja o interno, aunque deberia ser hoja */
+               if (nodo->nivel > 0) {                  
+                       nodo->claves[i] = query.clave;
+               } else {
+                       nodo->claves[i] = query.clave;
+                       nodo->hijos[i] = query.num_bloque;
+               }
+               b_plus_grabar_nodo(idx,nodo,auxquery.num_bloque);
+               b_plus_destruir_nodo(nodo);
+               return 0;
+       }
+       else return -1;
+}
+

 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 {
 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;
        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;


@@ -418,13 +463,19 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
                /* Me debo fijar si esta la clave en este nodo interno, sino busco */           
                while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i;
                if (i < 0) {
                /* Me debo fijar si esta la clave en este nodo interno, sino busco */           
                while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i;
                if (i < 0) {

-                       /* No esta en este nodo interno, caso 3 */      
+                       /* No esta en este nodo interno, caso 3 */

                } else {
                        /* Esta en el nodo interno, caso 2 */
                        cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
                        if (cant_claves_child > minclaves) {
                } else {
                        /* Esta en el nodo interno, caso 2 */
                        cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i]);
                        if (cant_claves_child > minclaves) {

-                               /* Caso 2a */
-                                                               
+                               /* Caso 2a, comienzo buscando la clave previa inmediata */
+                               b_plus_buscar_prepost(idx,key,nodo->hijos[i],&prekey,0);
+                               /* La elimino recursivamente */
+                               emufs_b_plus_eliminar(idx,prekey.clave,0);
+                               /* Remplazo mi clave key por la encontrada prekey */
+                               nodo->claves[i] = prekey.clave;
+                               /* Remplazo la otra instancia de key en una hoja seguro por prekey */
+                               /*emufs_b_plus_reemplazar_clave(idx,key,prekey.clave);*/

                        } 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) {


@@ -434,9 +485,7 @@ int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
                                        /* Caso 2c */
                                
                                }
                                        /* Caso 2c */
                                
                                }

-                       }
-                       
-                       
+                       }                       

                }               
        }
        
                }               
        }
        

diff --git a/emufs/indice_bplus.h b/emufs/indice_bplus.h
index 81963fcbf47c9c57d75fc7bcd26c919fc68a933a..ef6dc695ef45ce4385de09f7978bcef7d6aa7fb8 100644 (file)
--- a/emufs/indice_bplus.h
+++ b/emufs/indice_bplus.h
@@ -26,12 +26,10 @@ typedef struct nodo_b_plus {
 int emufs_b_plus_crear(INDICE *idx);\r
 int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node);\r
 int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query);\r
 int emufs_b_plus_crear(INDICE *idx);\r
 int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node);\r
 int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query);\r

-int emufs_b_plus_actualizar_nodo(INDEX_DAT *dataset);\r
-int emufs_b_plus_buscar();\r
-int emufs_b_plus_destuir();\r

 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node);\r
 int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node);\r
 NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num);\r
 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node);\r
 int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node);\r
 NODO_B_PLUS *b_plus_leer_nodo(INDICE *idx, int num);\r

-int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostkey, int search_type);\r
+int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, INDEX_DAT *prepostkey, int search_type);\r
+int b_plus_reemplazar_clave(INDICE *idx, CLAVE key, INDEX_DAT replacement);\r

 \r
 #endif
 \r
 #endif