X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/22f4aa739f33817a7c47f08154b4742fce0c5c31..746823c78bfbf3337992105d6271460d70de3082:/emufs/indice_b.c

diff --git a/emufs/indice_b.c b/emufs/indice_b.c
index b119784..2e1615b 100644
--- 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);
+/** 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);
 
@@ -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;
-			/* 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;
@@ -1011,3 +1054,32 @@ static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *he
 	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)
+	 *
+	 */
+}
+