X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/22f4aa739f33817a7c47f08154b4742fce0c5c31..e1b83d7a86a1982cf9936cc354a969d68303d351:/emufs/indice_b.c?ds=sidebyside diff --git a/emufs/indice_b.c b/emufs/indice_b.c index b119784..f032d51 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); @@ -283,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; } @@ -299,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); @@ -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,180 @@ 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) + * + */ +} + +CLAVE emufs_indice_b_obtener_menor_clave(INDICE *idx) +{ + B_NodoHeader header; + B_NodoEntry *claves; + CLAVE k; + char *nodo; + + nodo = b_leer_nodo(idx, 0); + b_leer_header(nodo, &header); + /* Tengo que ir siempre a la izquierda hasta una hora */ + while (header.hijo_izquierdo != -1) { + free(nodo); + nodo = b_leer_nodo(idx, header.hijo_izquierdo); + b_leer_header(nodo, &header); + } + + /* Listo, ahora solo leo la primer clave */ + claves = b_leer_claves(nodo, &header); + k = claves[0].clave; + free(nodo); + return k; +} + +CLAVE emufs_indice_b_obtener_mayor_clave(INDICE *idx) +{ + B_NodoHeader header; + B_NodoEntry *claves; + CLAVE k; + int i; + char *nodo; + + nodo = b_leer_nodo(idx, 0); + b_leer_header(nodo, &header); + claves = b_leer_claves(nodo, &header); + /* Tengo que ir siempre a la izquierda hasta una hora */ + while (claves[header.cant-1].hijo_derecho != -1) { + i = claves[header.cant-1].hijo_derecho; + free(nodo); + nodo = b_leer_nodo(idx, i); + b_leer_header(nodo, &header); + claves = b_leer_claves(nodo, &header); + } + + /* Listo, ahora solo leo la primer clave */ + k = claves[header.cant-1].clave; + free(nodo); + 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