super test, cargando 10000 registros con claves random y el arbol se arma, al parecer...

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

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index 59b31ac0831282e621638275a210f75cd253e18f..274fe798b99900c97af467d93c5b91117ac6cda6 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+ */


@@ -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 {


@@ -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 */


@@ -328,39 +335,39 @@ int b_plus_cant_claves_nodo(INDICE *idx, int num_node)
 }
 
 /* Search_Type: 0 - Predecesor, 1 - Sucesor
 }
 
 /* Search_Type: 0 - Predecesor, 1 - Sucesor

-   Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre */
-int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostkey, int search_type)
+   Exitcode: 1 - Encontre lo buscado, 0 - No lo encontre, -1 Error */
+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) {
-               PERR ("Entre en hoja");
+       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 */                       
                        /* Busco predecesor en la hoja */                       

-                       case 0: if (i < 0) exitcode = 0;
-                                       else {
-                                               *prepostkey = nodo->claves[i];
+                       case 0: if (i <= 0) exitcode = 0;
+                                       else {                                          
+                                               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;

-               }                                                                                                               
-               /* Libero y devuelvo exitcode */
-               b_plus_destruir_nodo(nodo);
-               return(exitcode);               
-               
+               }                                                                                                                               

        } else {
                /* Veo por que rama debo seguir buscando el pre o post */
                while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          
        } else {
                /* Veo por que rama debo seguir buscando el pre o post */
                while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          


@@ -368,32 +375,70 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke
                        if (i < 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
                        else {
                                /* Busco primero por la rama derecha, sino por la izquierda */
                        if (i < 0) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
                        else {
                                /* Busco primero por la rama derecha, sino por la izquierda */

-                               exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+2],prepostkey,search_type);
-                               if (exitcode == 0) 
-                               {
-                                       PERR("Volvi de rama derecha");
-                                       exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);                                                              
-                               }
+                               exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
+                               if (exitcode == 0)                      
+                                       exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i],prepostkey,search_type);

                        }
                        }

+                       /* Handleo busqueda de clave menor o igual que todas */
+                       if (exitcode == 0) exitcode = -1;

                } else  {
                } else  {

-                       /* Busco un sucesor, y funciona como getbloque... */
-                       PERR("Busco sucesor..., llamo recursivo..");
-                       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);
                        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) {

-                               *prepostkey = nodo->claves[i+1];
-                               exitcode = 1;
+                               if (i < nodo->cant_claves-1) {
+                                       prepostkey->clave = nodo->claves[i+1];
+                                       exitcode = 1;
+                               } else  exitcode = -1;

                        }
                }               
        }
        
                        }
                }               
        }
        

-       return exitcode;
+       /* Libero y devuelvo exitcode */
+       b_plus_destruir_nodo(nodo);
+       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 prepostkey;

        int i = 0,j = 0,minclaves = 0, cant_claves_child = 0;
        int i = 0,j = 0,minclaves = 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;
        i = nodo->cant_claves - 1;
        minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
        if (nodo == NULL) return -1;
        i = nodo->cant_claves - 1;
        minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;


@@ -419,25 +464,47 @@ 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 */
-                                                               
-                       } else {                                
+                               /* 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);
+                               /* Remplazo mi clave key por la encontrada prekey */
+                               nodo->claves[i] = prepostkey.clave;
+                               /* Remplazo la otra instancia de key en una hoja seguro por prekey */
+                               emufs_b_plus_reemplazar_clave(idx,key,prepostkey.clave);
+                       } else { 

                                cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
                                if (cant_claves_child > minclaves) {
                                cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
                                if (cant_claves_child > minclaves) {

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

                                } else {
                                } 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 */
+                                       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);                                                                                
+                                       /* 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];
+                                       }
+                                       }

                                }
                                }

-                       }
-                       
-                       
+                       }                       

                }               
        }
        
                }               
        }