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

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

diff --git a/emufs/indice_b.c b/emufs/indice_b.c
index eba1739c90603b4cc67b89f275aede57d43fadc8..f032d51805e834070f7647d46bd74ec9f64bf45a 100644 (file)
--- a/emufs/indice_b.c
+++ b/emufs/indice_b.c
@@ -285,11 +285,11 @@ char *b_leer_nodo(INDICE *idx, int id)
        }
 
        /* Si estoy manejando string tengo que sacar las abreviaturas */
-       if (idx->tipo_dato == IDX_STRING) {
+/*     XXX if (idx->tipo_dato == IDX_STRING) {
                b_leer_header(out, &header);
                claves = b_leer_claves(out, &header);
                desabreviar_claves(idx, claves, &header);
-       }
+       }*/
        fclose(fp);
        return out;
 }
@@ -301,11 +301,11 @@ static void b_grabar_nodo(INDICE *idx, int id, char *data)
        B_NodoEntry *claves;
 
        /* Si las claves son de tipo string debo abreviar antes de guardar */
-       if (idx->tipo_dato == IDX_STRING) {
+/*XXX  if (idx->tipo_dato == IDX_STRING) {
                b_leer_header(data, &header);
                claves = b_leer_claves(data, &header);
                abreviar_claves(idx, claves, &header);
-       }
+       }*/
        fp = fopen(idx->filename, "r+");
        fseek(fp, id*idx->tam_bloque, SEEK_SET);
        fwrite(data, 1, idx->tam_bloque, fp);
@@ -1132,3 +1132,102 @@ CLAVE emufs_indice_b_obtener_mayor_clave(INDICE *idx)
        return k;
 }
 
+CLAVE emufs_indice_b_obtener_sig_clave(INDICE *idx, CLAVE k)
+{
+       int i;
+       B_NodoHeader header;
+       B_NodoEntry *claves;
+       char *nodo, *tmp;
+       int nodo_id;
+       CLAVE salida;
+       
+       /* Primero busco la clave pasada por parametro */
+       nodo = b_leer_nodo(idx, 0);
+       nodo_id = 0;
+       while (nodo) {
+               b_leer_header(nodo, &header);
+               claves = b_leer_claves(nodo, &header);
+               i=0;
+               while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) i++;
+               if ((i<header.cant) && (emufs_indice_es_igual(idx, claves[i].clave, k))) {                              
+                               /* LA ENCONTRE! , ahora busco la siguiente clave!! */           
+                               fprintf(stderr, "Me encontre en pos %d en el padre\n", i);
+                               if ((i+1)<header.cant) {
+                                       PERR("Joya, hay lugar a la derecha");
+                                       if (claves[i].hijo_derecho == -1) {
+                                               PERR("Y soy hoja!!");
+                                               /* Joya!, fue facil, la siguiente va en camino! */
+                                               salida = claves[i+1].clave;
+                                               free(nodo);
+                                               return salida;
+                                       }
+
+                                       PERR("No soy hoja, busco la hoja de menor");
+                                       /* Mmmmm ... la siguiente esta en uno de mis hijo */
+                                       /* Necesito la mas chica de las siguientes, para eso
+                                        * me voy a mi hijo derecho y de ahi bajo siempre
+                                        * hacia la izquierda hacia una hoja */
+                                       i = claves[i].hijo_derecho;
+                                       free(nodo);
+                                       nodo = b_leer_nodo(idx, i);
+                                       b_leer_header(nodo, &header);
+                                       while (header.hijo_izquierdo != -1) {
+                                               free(nodo);
+                                               nodo = b_leer_nodo(idx, header.hijo_izquierdo);
+                                               b_leer_header(nodo, &header);
+                                       }
+                                       claves = b_leer_claves(nodo, &header);
+                                       salida = claves[0].clave;
+                                       free(nodo);
+                                       return salida;
+                               }
+
+                               PERR("Fuck, tengo que ir otro nodo a buscar");
+                               /* Fuck, la siguiente clave la tengo que sacar de padre */
+                               /* Busco al mi padre, perdido en un maremoto hace mucho,muchos
+                                * años
+                                */
+                               free(nodo);
+                               if (header.padre == -1) {
+                                       salida.i_clave = -1;
+                                       return salida;
+                               }
+                               nodo = b_leer_nodo(idx, header.padre);
+                               b_leer_header(nodo, &header);
+                               claves = b_leer_claves(nodo, &header);
+                               i = 0;
+                               PERR("Busco mi siguiente en mi padre");
+                               fprintf(stderr, "Padre tiene %d claves\n", header.cant);
+                               while ((i<header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, k))) {
+                                       i++;
+                                       fprintf(stderr, "Proximo i : %d\n", i);
+                               }
+                               if (i<header.cant) {
+                                       PERR("Siguiente clave encontrada");
+                                       salida = claves[i].clave;
+                               } else {
+                                       /* No hay mas claves! */
+                                       PERR("Busque y busque pero no aparecio");
+                                       salida.i_clave = -1;
+                               }
+                               return salida;
+               } else {
+                       tmp = nodo;
+                       b_grabar_nodo(idx, nodo_id, nodo);
+                       if (i == 0) {
+                               nodo = b_leer_nodo(idx, header.hijo_izquierdo);
+                               nodo_id = header.hijo_izquierdo;
+                       } else {
+                               nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho);
+                               nodo_id = claves[i-1].hijo_derecho;
+                       }
+                       free(tmp);
+               }
+       }
+
+       /* No encontre la clave pasada, no existe */
+       PERR("No encontre la clave pasada!!");
+       salida.i_clave = -1;
+       return salida;
+}
+