Listo busqueda de sucesor, predecesor de 1 clave, tambien conocido como el afamado...

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

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index 59b31ac0831282e621638275a210f75cd253e18f..7165daf8a074667da5221d5fa2b02d876a665f69 100644 (file)
--- a/emufs/indice_bplus.c
+++ b/emufs/indice_bplus.c
@@ -328,7 +328,7 @@ 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 */
+   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 i = 0, exitcode = 0;
 int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostkey, int search_type)
 {
        int i = 0, exitcode = 0;


@@ -337,14 +337,15 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke
        i = nodo->cant_claves - 1;
        
        if (nodo->nivel == 0) {
        i = nodo->cant_claves - 1;
        
        if (nodo->nivel == 0) {

-               PERR ("Entre en hoja");
+               printf ("Entre en hoja nro %i\n",num_node);

                while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          
                switch (search_type) {
                        
                        /* Busco predecesor en la hoja */                       
                while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          
                switch (search_type) {
                        
                        /* 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 = nodo->claves[i-1];
+                                               else *prepostkey = nodo->claves[i];                                             

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


@@ -356,11 +357,7 @@ int b_plus_buscar_prepost(INDICE *idx, CLAVE key, int num_node, CLAVE *prepostke
                                                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,26 +365,28 @@ 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  {
                        /* Busco un sucesor, y funciona como getbloque... */
                } 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]);
                        exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
                        printf("Voy a buscar en hijo nro: %i\n",nodo->hijos[i+1]);
                        exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);

-                       if (exitcode == 0) {
-                               *prepostkey = nodo->claves[i+1];
-                               exitcode = 1;
-                       }
+                       /* Veo si tengo que devolver la clave izquierda del padre del que acabo de buscar */
+                       if (exitcode == 0)
+                               if (i < nodo->cant_claves-1) {
+                                       *prepostkey = nodo->claves[i+1];
+                                       exitcode = 1;
+                               } else  exitcode = -1;

                }               
        }
        
                }               
        }
        

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

 }
 
 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
 }
 
 int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)