Ya estaria el algoritmo para rotar a izquierda cuando se inserta en el B*.

diff --git a/emufs/indice_b.c b/emufs/indice_b.c
index d25fec92c11b6730b7c16c9791b7cdb1febb02d3..afb6b8ecdf68ba818eb271806ec547a492f06aaa 100644 (file)
--- a/emufs/indice_b.c
+++ b/emufs/indice_b.c
@@ -35,9 +35,9 @@ static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header);
  * \param hijo1 Id del nodo hijo de la izquierda del insertado.
  * \param hijo2 Id del nodo hijo de la derecha del insertado.
  */
-static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
+static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_izq, int hijo_der);
 /** Inserta en un nodo en el que se sabe positivamente que hay lugar. */
-static void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2);
+static void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_izq, int hijo_der);
 /** Borra una clave del arbol */
 static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k);
 /** Le pide al hermano derecho del nodo una clave cuando se eliminan claves */
@@ -47,7 +47,7 @@ static void b_pedir_clave_izquierda(char *, int, char *, int, char *, int, int);
 /** Le pasa al hermano derecho del nodo una clave cuando se insertan claves */
 static void b_pasar_clave_a_derecha(INDICE*, char*, int, char*, int, int, B_NodoEntry);
 /** Le pasa al hermano izquierdo una clave cuando se insertan claves */
-static void b_pasar_clave_a_izquierda(INDICE*, char*, int, char*, int, int, B_NodoEntry);
+static void b_pasar_clave_a_izquierda(INDICE*, char*, int, char*, int, int, B_NodoEntry, int, int);
 /** Junta 2 nodos y hace uno solo */
 static void b_fundir_nodo(char *, int, char *, int, char *, int, int);
                        
@@ -470,7 +470,7 @@ static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int n
        } while (!salir);
 }
 
-void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2)
+void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_izq, int hijo_der)
 {
        int i = 0;
        B_NodoHeader nodo_header;
@@ -487,11 +487,11 @@ void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, in
        claves[i].clave = clave;
        claves[i].dato = dato;
        if (i==0) {
-               nodo_header.hijo_izquierdo = hijo1;
-               claves[i].hijo_derecho = hijo2;
+               nodo_header.hijo_izquierdo = hijo_izq;
+               claves[i].hijo_derecho = hijo_der;
        } else {
-               claves[i-1].hijo_derecho = hijo1;
-               claves[i].hijo_derecho = hijo2;
+               claves[i-1].hijo_derecho = hijo_izq;
+               claves[i].hijo_derecho = hijo_der;
        }
        /*b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);*/
 
@@ -499,29 +499,64 @@ void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, in
        b_grabar_nodo(idx, nodo_id, nodo);
 
        /* Debo actualizar los punteros al padre de los hijos */
-       if (hijo1 != -1) {
-               char* nuevo = b_leer_nodo(idx, hijo1);
+       if (hijo_izq != -1) {
+               char* nuevo = b_leer_nodo(idx, hijo_izq);
                if (nuevo != NULL) {
                        B_NodoHeader nuevo_header;
-                       fprintf(stderr, "Actualizo padre de %d a %d\n", hijo1, nodo_id);
+                       fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_izq, nodo_id);
                        b_leer_header(nuevo, &nuevo_header);
                        nuevo_header.padre = nodo_id;
                        b_actualizar_header(nuevo, &nuevo_header);
-                       b_grabar_nodo(idx, hijo1, nuevo);
+                       b_grabar_nodo(idx, hijo_izq, nuevo);
                        free(nuevo);
-               } else printf("FUCK! hijo1=%d no existe!\n", hijo1);
+               } else printf("FUCK! hijo_izq=%d no existe!\n", hijo_izq);
        }
-       if (hijo2 != -1) {
-               char* nuevo = b_leer_nodo(idx, hijo2);
+       if (hijo_der != -1) {
+               char* nuevo = b_leer_nodo(idx, hijo_der);
                if (nuevo != NULL) {
                        B_NodoHeader nuevo_header;
-                       fprintf(stderr, "Actualizo padre de %d a %d\n", hijo2, nodo_id);
+                       fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_der, nodo_id);
                        b_leer_header(nuevo, &nuevo_header);
                        nuevo_header.padre = nodo_id;
                        b_actualizar_header(nuevo, &nuevo_header);
-                       b_grabar_nodo(idx, hijo2, nuevo);
+                       b_grabar_nodo(idx, hijo_der, nuevo);
                        free(nuevo);
-               } else printf("FUCK! hijo2=%d no existe!\n", hijo2);
+               } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
+       }
+}
+
+void b_insertar_en_nodo_con_lugar_sin_hijo_izq(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo_der)
+{
+       int i = 0;
+       B_NodoHeader nodo_header;
+       B_NodoEntry* claves;
+       b_leer_header(nodo, &nodo_header);
+       claves = b_leer_claves(nodo, &nodo_header);
+       if (nodo_header.cant > 0) {
+               int j;
+               while ((i < nodo_header.cant) && (emufs_indice_es_menor(idx, claves[i].clave, clave))) i++;
+               for(j=nodo_header.cant; j > i; j--)
+                       claves[j] = claves[j-1];
+       }
+       nodo_header.cant++;
+       claves[i].clave = clave;
+       claves[i].dato = dato;
+       claves[i].hijo_derecho = hijo_der;
+
+       b_actualizar_header(nodo, &nodo_header);
+       b_grabar_nodo(idx, nodo_id, nodo);
+
+       /* Debo actualizar el puntero al padre del hijo */
+       if (hijo_der != -1) {
+               char* nuevo = b_leer_nodo(idx, hijo_der);
+               if (nuevo != NULL) {
+                       B_NodoHeader nuevo_header;
+                       b_leer_header(nuevo, &nuevo_header);
+                       nuevo_header.padre = nodo_id;
+                       b_actualizar_header(nuevo, &nuevo_header);
+                       b_grabar_nodo(idx, hijo_der, nuevo);
+                       free(nuevo);
+               } else printf("FUCK! hijo_der=%d no existe!\n", hijo_der);
        }
 }
 
@@ -735,12 +770,11 @@ static void b_pedir_clave_derecha(char *der, int der_id, char *padre, int padre_
 
 void b_pasar_clave_a_derecha(INDICE *idx, char *der, int der_id, char *padre, int padre_id, int padre_pos, B_NodoEntry entry)
 {
-       B_NodoHeader der_h, padre_h;
-       B_NodoEntry *der_entries, *padre_entries;
+       B_NodoHeader padre_h, der_h;
+       B_NodoEntry* padre_entries;
        /* Leo claves y cabecera del nodo de la derecha y del padre */
-       b_leer_header(der, &der_h);
-       der_entries = b_leer_claves(der, &der_h);
        b_leer_header(padre, &padre_h);
+       b_leer_header(der, &der_h);
        padre_entries = b_leer_claves(padre, &padre_h);
        /* Inserto en el hijo derecho la clave del padre */
        b_insertar_en_nodo_con_lugar(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
@@ -778,33 +812,19 @@ void b_pedir_clave_izquierda(char *izq, int izq_id, char *padre, int padre_id, c
        b_actualizar_header(nodo, &h_nodo);
 }
 
-void b_pasar_clave_a_izquierda(INDICE* idx, char *izq, int izq_id, char *padre, int padre_id, int padre_pos, B_NodoEntry entry)
+void b_pasar_clave_a_izquierda(INDICE* idx, char *izq, int izq_id, char *padre, int padre_id, int padre_pos, B_NodoEntry entry, int id_entry_hijo_izq, int id_entry_nodo)
 {
-/*     int i;
-       B_NodoHeader h_izq, h_padre, h_nodo;
-       B_NodoEntry *c_izq, *c_padre, *c_nodo;
-
-       b_leer_header(nodo, &h_nodo);
-       c_nodo = b_leer_claves(nodo, &h_nodo);
-       b_leer_header(izq, &h_izq);
-       c_izq = b_leer_claves(izq, &h_izq);
-       b_leer_header(padre, &h_padre);
-       c_padre = b_leer_claves(padre, &h_padre);
-
-       for(i=h_nodo.cant; i>0;i++)
-               c_nodo[i] = c_nodo[i-1];
-
-       h_nodo.cant++;
-       c_nodo[0] = c_padre[pos_clave];
-       c_nodo[0].hijo_derecho = -1; / * XXX * /
-       c_padre[pos_clave] = c_izq[h_izq.cant-1];
-       c_padre[pos_clave].hijo_derecho = izq_id;
-       h_izq.cant--;
-
-       b_actualizar_header(izq, &h_izq);
-       b_actualizar_header(padre, &h_padre);
-       b_actualizar_header(nodo, &h_nodo);
-*/
+       B_NodoHeader padre_h;
+       B_NodoEntry* padre_entries;
+       /* Leo claves y cabecera del nodo de la izquierda y del padre */
+       b_leer_header(padre, &padre_h);
+       padre_entries = b_leer_claves(padre, &padre_h);
+       /* Inserto en el hijo izquirdo la clave del padre */
+       b_insertar_en_nodo_con_lugar_sin_hijo_izq(idx, padre_entries[padre_pos].clave, padre_entries[padre_pos].dato,
+                       izq_id, izq, id_entry_hijo_izq);
+       /* Reemplazo clave del padre por clave nueva */
+       entry.hijo_derecho = id_entry_nodo;
+       padre_entries[padre_pos] = entry;
 }
 
 static void b_fundir_nodo(char *izq, int izq_id, char *padre, int padre_id, char *der, int der_id, int pos_clave)