From 70181ec30f30250cf0899faf84c6dd24137b2b5c Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Wed, 26 May 2004 20:34:29 +0000 Subject: [PATCH 1/1] =?utf8?q?Agrego=20pseudoc=C3=B3digo=20bastante=20deta?= =?utf8?q?llado=20de=20los=20cambios=20que=20hay=20que=20hacer=20para=20co?= =?utf8?q?nvertir=20el=20B=20en=20B*=20cuando=20est=C3=A9=20terminado.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- emufs/indice_b.c | 82 +++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 77 insertions(+), 5 deletions(-) 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) + * + */ +} + -- 2.43.0