Laburando sobre el borrado con Nico, wish us luck

diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c
index 2bc6eb352cc3e400808c6a06bd89abefc1fe773a..3311353729183a3f085c7a660f59cec27665acee 100644 (file)
--- a/emufs/b_plus_test.c
+++ b/emufs/b_plus_test.c
@@ -26,18 +26,25 @@ emufs_b_plus_insertar(emu->indices,&querydata);
 }
 
 /* NOTA: Deberia devolver el mismo 104 y Exitcode = -1 */
-/*querydata.num_bloque = 104;
+querydata.num_bloque = 104;
 querydata.clave.i_clave = 0;
 exitcode = emufs_b_plus_get_bloque(emu->indices,&querydata,0);
 printf("Numero de bloque donde grabar clave 0: %i\n",(int)(querydata.num_bloque));
-printf("Exit Code del get bloque: %i\n",exitcode);*/
+printf("Exit Code del get bloque: %i\n",exitcode);
 
 /* NOTA: Deberia devolver un numero de bloque X y Exitcode = 0 */
-/*querydata.num_bloque = 104;
+querydata.num_bloque = 104;
 querydata.clave.i_clave = 25;
 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);*/
+printf("Exit Code del get bloque: %i\n",exitcode);
+
+querydata.clave.i_clave = 0;
+querydata.num_bloque = 0; /* al pedo */
+exitcode = b_plus_existe_clave(emu->indices,&querydata,0);
+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);
 
 /*
 querydata.num_bloque = 2;

diff --git a/emufs/indice_bplus.c b/emufs/indice_bplus.c
index 10c7330089fef8d2ea7128e877428a6691ce3c52..23a6f31379919b8895a2164e0c89dc93f291ef6a 100644 (file)
--- a/emufs/indice_bplus.c
+++ b/emufs/indice_bplus.c
@@ -66,12 +66,12 @@ int emufs_b_plus_crear(INDICE *idx) {
  */
 int emufs_b_plus_get_bloque(INDICE *idx, INDEX_DAT *query, int num_node) {
 
+       int i,exitcode = 0;
        NODO_B_PLUS *nodo;
        nodo = b_plus_leer_nodo(idx,num_node);
        if (nodo == NULL) return 1;
-       int i = nodo->cant_claves - 1;
-       int exitcode = 0;
-       
+       i = nodo->cant_claves - 1;
+               
        /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
        if (nodo->nivel == 0) {
         /* Vemos en que bloque deberia ir */
@@ -176,7 +176,7 @@ int b_plus_destruir_nodo(NODO_B_PLUS *nodo)
 int b_plus_split_child(INDICE *idx, int numparent, NODO_B_PLUS *parent, int ithchild, NODO_B_PLUS *fullnode)
 {
        /* locals */
-       int minclaves = ceil(idx->size_hijos/sizeof(int)/2)-1;
+       int minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
        int numbrother,j = 0;
        int es_interno = 1;
        
@@ -288,6 +288,157 @@ int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query)
     return 0;
 }
 
+/** Busca una clave dentro del arbol e indica si existe o no
+ *  Posibilidades: return 1 - Encontro la clave
+ *                 return 0 - No encontro la clave
+ *                 return -1 - Hubo falla de lectura de un nodo, Abortar
+ */
+int b_plus_existe_clave(INDICE *idx, INDEX_DAT *query, int num_node)
+{
+       int i,exitcode = 0;
+       NODO_B_PLUS *nodo;
+       nodo = b_plus_leer_nodo(idx,num_node);
+       if (nodo == NULL) return -1;
+       i = nodo->cant_claves - 1;
+               
+       /* Si es un hoja, busco dentro de la hoja, otherwise, busco la hoja */
+       if (nodo->nivel == 0) {
+        /* Vemos en que bloque deberia ir */
+               while ( i >= 0 && query->clave.i_clave != nodo->claves[i].i_clave ) i--;
+               if (i < 0) return 0; /* No encontre la clave */
+               else return 1; /* Encontre la clave */                  
+       }
+       else {
+               /* Buscamos por donde descender al siguiente nivel */
+               while ( i >= 0 && query->clave.i_clave < nodo->claves[i].i_clave ) i--;
+        i++;
+        num_node = nodo->hijos[i];
+               b_plus_destruir_nodo(nodo);
+               exitcode = b_plus_existe_clave(idx,query,num_node);
+               return exitcode;
+       }
+}
+
+int b_plus_cant_claves_nodo(INDICE *idx, int num_node)
+{
+       NODO_B_PLUS *nodo =     b_plus_leer_nodo(idx,num_node);
+       if (nodo == NULL) return -1;
+       return nodo->cant_claves;
+}
+
+/* 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)
+{
+       int i = 0, j = 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) {
+               while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;
+               /* Busco predecesor en la hoja */       
+               switch (search_type) {
+                       
+                       case 0: if (i < 0) return 0;
+                                       else {
+                                               *prepostkey = nodo->claves[i];
+                                               return 1;
+                                       }
+                                       break;
+                                       
+                       case 1: if (nodo->claves[i].i_clave == key.i_clave) return 0;
+                                       else {
+                                               *prepostkey = nodo->claves[i+1];
+                                               return 1;
+                                       }
+                                       break;
+               }
+                                                                                                       
+               /* Busco sucesor en la hoja */  
+               if ((search_type == 1) && (i < 0)) return 0;
+               else if (i >= 0) {
+                               *prepostkey = nodo->claves[i];
+                               return 1;
+               }                               
+       } else {
+               /* Veo por que rama debo seguir buscando el pre o post */
+               while ( i >= 0 && key.i_clave < nodo->claves[i].i_clave ) --i;          
+               if (search_type == 0) {
+                       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) exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);                                                           
+                       }
+               } else  {
+                       /* Busco un sucesor, y funciona como getbloque... */
+                       exitcode = b_plus_buscar_prepost(idx,key,nodo->hijos[i+1],prepostkey,search_type);
+                       if (exitcode == 0) {
+                               *prepostkey = nodo->claves[i+1];
+                               exitcode = 1;
+                       }
+               }
+                       
+       }
+       
+       return exitcode;
+}
+
+int emufs_b_plus_eliminar(INDICE *idx, CLAVE key, int num_node)
+{
+       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;
+       i = nodo->cant_claves - 1;
+       minclaves = ceil(idx->size_hijos/sizeof(CLAVE)/2)-1;
+
+       /* Si es hoja, borro directamente la clave. No se producira underflow
+       pues lo asegura la recursividad del delete */   
+       if (nodo->nivel == 0) {         
+               while ( i >= 0 && key.i_clave != nodo->claves[i].i_clave ) --i;
+               if (i < 0) return -1;
+               /* Encontre la clave en la pos i, la borro */
+               for (j = i; j < nodo->cant_claves-1; ++j) {
+                       nodo->claves[j] = nodo->claves[j+1];
+                       nodo->hijos[j] = nodo->hijos[j+1];
+               }
+               nodo->hijos[j] = nodo->hijos[j+1];
+        nodo->cant_claves--;
+               
+               /* Grabo el nodo actualizado en disco */
+               b_plus_grabar_nodo(idx,nodo,num_node);
+               b_plus_destruir_nodo(nodo);
+               return 0;
+       } else {
+               /* 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 */      
+               } 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 {                                
+                               cant_claves_child = b_plus_cant_claves_nodo(idx,nodo->hijos[i+1]);
+                               if (cant_claves_child > minclaves) {
+                                       /* Caso 2b */
+                                       
+                               } else {
+                                       /* Caso 2c */
+                               
+                               }
+                       }
+                       
+                       
+               }               
+       }
+       
+       return -1;
+}
+
 int b_plus_get_num_nodo(INDICE *idx)
 {
        FILE *fp;

diff --git a/emufs/indice_bplus.h b/emufs/indice_bplus.h
index 73b3e806b5c0cbb0d7d8f2b60dd93110fdd8ae9d..8aa23802205e7fc89721229d36c60ce0afea0064 100644 (file)
--- a/emufs/indice_bplus.h
+++ b/emufs/indice_bplus.h
@@ -29,6 +29,8 @@ int emufs_b_plus_insertar(INDICE *idx, INDEX_DAT *query);
 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
 \r
 #endif