Agrego pseudocódigo bastante detallado de los cambios que hay que hacer para

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

diff --git a/emufs/indice_b.c b/emufs/indice_b.c
index b11978475ddf947719a379e45a036552586d7c39..2e1615b25fe2360d77b8933c126d32db80841107 100644 (file)
--- a/emufs/indice_b.c
+++ b/emufs/indice_b.c
@@ -42,6 +42,8 @@ static void b_pasar_clave_a_derecha(INDICE*, char*, int, char*, int, int, B_Nodo
 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(INDICE *,char *, int, char *, int, char *, int, int);
 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(INDICE *,char *, int, char *, int, char *, int, int);

+/** Crea 3 nodos a partir de 2 llenos */
+static void b_partir_dos_nodos_en_tres(INDICE*, int nodo_izq, int nodo_der, int padre, B_NodoEntry nuevo_entry);

                        
 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo);
 
                        
 static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo);
 


@@ -350,11 +352,52 @@ static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int n
 
                if (nodo_header.cant == CANT_HIJOS(idx)) {
                        int total;
 
                if (nodo_header.cant == CANT_HIJOS(idx)) {
                        int total;

-                       /* TODO: Si es B*, hay que chequear si alguno de los 2
-                        *       nodos hermanos pueden prestarme espacio (y
-                        *       desplazar si es así). Si no pueden, hay que
-                        *       hacer un split de 2 nodos en 3.
-                        *       Si no es B*, hay que hacer lo que sigue:
+                       /*
+                        * TODO FIXME XXX TODO FIXME XXX TODO FIXME XXX
+                        *
+                        *******************************************************
+                        * Pseudocódigo que explica que hay que hacer si es B*
+                        *
+                        * OJO! Si el nodo en el cual estoy insertando es el
+                        * raíz, se maneja exactamente igual que en el B común,
+                        * así que el if sería algo como:
+                        * if (idx->tipo == IND_B_ASC && !es_raiz(nodo_id))
+                        *******************************************************
+                        *
+                        * nuevo_entry = new entry(clave, dato, hijo_der)
+                        * padre = get_padre(nodo)
+                        *
+                        * // Veo si puedo pasar a derecha
+                        * hijo_derecho = get_hijo_derecho(padre)
+                        * if (hijo_derecho != NULL && hijo_derecho.cantidad_entries < MAX_ENTRIES)
+                        *      buffer = new entries[MAX_ENTRIES+1]
+                        *      copiar_entries(buffer, nodo)
+                        *      insertar_ordenado(buffer, nuevo_entry)
+                        *      entry_a_pasar = get_entry_extremo_derecho(buffer)
+                        *      b_pasar_clave_a_derecha(idx, hijo_derecho, hijo_derecho.id, padre, padre.id, padre.posicion, entry_a_pasar)
+                        *      SALIR
+                        *
+                        * // Veo si puedo pasar a izquierda
+                        * hijo_izquierdo = get_hijo_izquierdo(padre)
+                        * if (hijo_izquierdo != NULL && hijo_izquierdo.cantidad_entries < MAX_ENTRIES)
+                        *      buffer = new entries[MAX_ENTRIES+1]
+                        *      copiar_entries(buffer, nodo)
+                        *      insertar_ordenado(buffer, nuevo_entry)
+                        *      entry_a_pasar = get_entry_extremo_izquierdo(buffer)
+                        *      b_pasar_clave_a_izquierda(idx, hijo_izquierdo, hijo_izquierdo.id, padre, padre.id, padre.posicion, entry_a_pasar)
+                        *      SALIR
+                        *
+                        * // Parto 2 nodos en 3.
+                        * if (hijo_izquierdo != NULL)
+                        *      b_partir_dos_nodos_en_tres(idx, hijo_izquierdo, nodo, padre, nuevo_entry)
+                        * else // Siempre alguno tiene que existir.
+                        *      b_partir_dos_nodos_en_tres(idx, nodo, hijo_derecho, padre, nuevo_entry)
+                        *
+                        * SALIR
+                        *
+                        **********************************************************************************
+                        * Fin de pseudocódigo, si no es B* se sigue haciendo lo que dice a continuación. *
+                        **********************************************************************************

                         */
                        nuevo = b_crear_nodo(idx, &nuevo_id);
                        i=0;
                         */
                        nuevo = b_crear_nodo(idx, &nuevo_id);
                        i=0;


@@ -1011,3 +1054,32 @@ static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *he
        free(primera);
 }
 
        free(primera);
 }
 

+static void b_partir_dos_nodos_en_tres(INDICE* idx, int nodo_izq, int nodo_der, int padre, B_NodoEntry nuevo_entry)
+{
+       /*
+        * PSEUDOCODIGO    TODO FIXME XXX TODO FIXME XXX TODO FIXME XXX
+        *
+        * // Creo un buffer con todos los entries (las claves) de ambos nodos, mas el padre y la nueva, ordenadas
+        * buffer_size = 2*MAX_ENTRIES+2
+        * buffer = new entries[buffer_size]
+        * copiar_entries(buffer, nodo_izq)
+        * concatenar_entries(buffer, padre)
+        * concatenar_entries(buffer, nodo_der)
+        * insertar_ordenado(buffer, nuevo_entry)
+        * // Borro los 2 nodos viejos para reutilizarlos y creo el tercero
+        * borrar_entries(nodo_izq)
+        * borrar_entries(nodo_der)
+        * nodo_nuevo = new nodo()
+        * // Copio de a tercios del buffer en los nuevos nodos, excluyendo las 2 claves 'limítrofes' para insertarlas luego en el padre
+        * copiar_algunos_entries(nodo_izq, buffer, 0, (buffer_size/3)-1)
+        * entry_promovido1 = buffer[buffer_size/3]
+        * copiar_algunos_entries(nodo_izq, buffer, (buffer_size/3)+1, 2*(buffer_size/3))
+        * entry_promovido2 = buffer[(2*(buffer_size/3))+1]
+        * copiar_algunos_entries(nodo_nuevo, buffer, (2*(buffer_size/3))+2, buffer_size-1))
+        * // Finalmente inserto (recursivamente, porque esta funcion es llamada desde b_insertar_en_nodo()) las claves promovidas en el padre
+        * b_insertar_en_nodo(idx, entry_promovido.clave, entry_promovido.dato, entry_promovido.id, entry_promovido, nodo_izq.id, nodo_der.id)
+        * b_insertar_en_nodo(idx, entry_promovido.clave, entry_promovido.dato, entry_promovido.id, entry_promovido, nodo_der.id, nodo_nuevo.id)
+        *
+        */
+}
+