X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/ce3cea71f571b6f5dcff4857718ae7e22dd93172..74c6776ce0ae5ea218cf0363af040bf260b2c72b:/emufs/indice_b.c diff --git a/emufs/indice_b.c b/emufs/indice_b.c index 4edaca2..dfd4ff3 100644 --- a/emufs/indice_b.c +++ b/emufs/indice_b.c @@ -43,12 +43,13 @@ static void b_pasar_clave_a_izquierda(INDICE*, char*, int, char*, int, int, B_No /** 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 void b_partir_dos_nodos_en_tres(INDICE* idx, int nodo_izq, int nodo_der, B_NodoEntry padre_entry, B_NodoEntry nuevo_entry, int id_padre); static EMUFS_REG_ID b_insertar_dup_en_pos(INDICE *idx, INDICE_DATO pos, INDICE_DATO nuevo); static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header); static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *header); +int b_borrar_dup_clave(INDICE *idx, INDICE_DATO k, INDICE_DATO dato); void emufs_indice_b_crear(INDICE *idx) { @@ -74,6 +75,7 @@ void emufs_indice_b_crear(INDICE *idx) memcpy(bloque, &header, sizeof(B_NodoHeader)); fwrite(bloque, idx->tam_bloque, 1, fp); + free(bloque); fclose(fp); } @@ -108,7 +110,7 @@ int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato) if (idx->tipo_dato == IDX_STRING) { /* Tengo que sacar el texto repetido del archivo de textos */ - idx->emu_string->borrar_registro(idx->emu_string, clave); + idx->emu_string->borrar_registro(idx->emu_string, clave, dummy); } return 1; } else { @@ -179,7 +181,7 @@ INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave) return ret; } -int emufs_indice_b_borrar(INDICE *idx, CLAVE k) +int emufs_indice_b_borrar(INDICE *idx, CLAVE k, INDICE_DATO dato) { /* Busco el nodo que contiene la clave,si es que esta existe */ char *nodo; @@ -215,8 +217,19 @@ int emufs_indice_b_borrar(INDICE *idx, CLAVE k) if (encontrado) { PERR("Clave encontrada, borrando ..."); - fprintf(stderr, "La clave a borrar esta en el nodo %d\n", nodo_id); - b_borrar_clave(idx, nodo, nodo_id, k); + fprintf(stderr, "%s: La clave a borrar esta en el nodo %d\n", idx->nombre, nodo_id); + if (idx->funcion != IND_PRIMARIO) { + /* Debo borrar primero la clave desde el archivo de + * claves repetidas, y si recien ahi me quedo sin claves, + * borrar la clave del arbol + */ + PERR("Vamos a borrar duplicados"); + encontrado = b_borrar_dup_clave(idx, claves[i].dato, dato); + fprintf(stderr, "Listo, encontrado = %d\n", encontrado); + } + if (encontrado) { + b_borrar_clave(idx, nodo, nodo_id, k); + } } else { PERR("Clave no encontrada"); } @@ -260,8 +273,8 @@ char *b_leer_nodo(INDICE *idx, int id) { FILE *fp; char *out; - B_NodoHeader header; - B_NodoEntry *claves; + /*B_NodoHeader header; + B_NodoEntry *claves;*/ if (id < 0) return NULL; @@ -296,8 +309,8 @@ char *b_leer_nodo(INDICE *idx, int id) static void b_grabar_nodo(INDICE *idx, int id, char *data) { FILE *fp; - B_NodoHeader header; - B_NodoEntry *claves; + /*B_NodoHeader header; + B_NodoEntry *claves;*/ /* Si las claves son de tipo string debo abreviar antes de guardar */ /* if (idx->tipo_dato == IDX_STRING) { @@ -528,7 +541,6 @@ void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, in claves[i-1].hijo_derecho = hijo_izq; claves[i].hijo_derecho = hijo_der; } - /*b_elegir_izquierdo(idx, nodo_header.hijo_izquierdo, hijo1);*/ b_actualizar_header(nodo, &nodo_header); b_grabar_nodo(idx, nodo_id, nodo); @@ -654,9 +666,6 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) fprintf(stderr, "La clave esta en la pos = %d\n", pos); if (header.hijo_izquierdo != -1) { PERR("Nodo no es hoja, intercambio"); -/* if (pos == 0) { - actual = b_leer_nodo(idx, nodo_header.hijo_izquierdo); - else*/ actual = b_leer_nodo(idx, claves[pos].hijo_derecho); actual_id = claves[pos].hijo_derecho; p = claves[pos].hijo_derecho; @@ -697,7 +706,7 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) /* Se cumple la condicion de hijos? */ PERR("Dejo todo consistente"); fprintf(stderr, "Condicion : %d >= %d\n", header_actual.cant, MIN_HIJOS(idx)); - if (header_actual.cant >= MIN_HIJOS(idx)) { + if ((header_actual.cant >= MIN_HIJOS(idx)) || (actual_id == 0)) { PERR("Borrar completo sin fundir"); return; } @@ -706,6 +715,7 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) /* Tengo que pasar datos o fundir nodos :-( */ do { padre_id = header.padre; + if (padre_id == -1) continue; padre = b_leer_nodo(idx, padre_id); b_leer_header(padre, &header_padre); claves_padre = b_leer_claves(padre, &header_padre); @@ -718,6 +728,7 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) derecha_id = claves_padre[0].hijo_derecho; der = b_leer_nodo(idx, derecha_id); b_leer_header(der, &header_der); + pos_padre = 0; } else { PERR("Buscando que hijo soy"); for(pos_padre=0; (claves_padre[pos_padre].hijo_derecho != actual_id); pos_padre++) { } @@ -751,6 +762,7 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) if ((derecha_id != -1) && (header_der.cant > MIN_HIJOS(idx))) { PERR("Le pido clave a derecha"); fprintf(stderr, "ANTES DE PEDIR DERECHA TENGO %d claves\n", header_actual.cant); + fprintf(stderr, "PEDIR DERECHA DATOS : yo=%d, padre=%d, der=%d, pos_clave=%d\n", actual_id, padre_id, derecha_id, pos_padre); b_pedir_clave_derecha(der, derecha_id, padre, padre_id, actual, actual_id, pos_padre); PERR("listo"); b_leer_header(der, &header_der); @@ -796,6 +808,7 @@ static void b_pedir_clave_derecha(char *der, int der_id, char *padre, int padre_ B_NodoHeader h_der, h_padre, h_nodo; B_NodoEntry *c_der, *c_padre, *c_nodo; + PERR("Derecha 1"); b_leer_header(nodo, &h_nodo); c_nodo = b_leer_claves(nodo, &h_nodo); b_leer_header(der, &h_der); @@ -803,13 +816,16 @@ static void b_pedir_clave_derecha(char *der, int der_id, char *padre, int padre_ b_leer_header(padre, &h_padre); c_padre = b_leer_claves(padre, &h_padre); + PERR("Derecha 2"); c_nodo[h_nodo.cant] = c_padre[pos_clave+1]; c_nodo[h_nodo.cant].hijo_derecho = -1; /* XXX */ + PERR("Derecha 3"); c_padre[pos_clave+1] = c_der[0]; c_padre[pos_clave+1].hijo_derecho = der_id; /* Muevo las claves de derecho */ + PERR("Derecha 4"); for(i=0; iemu_mult->modificar_registro(idx->emu_mult, k, leido, cant*sizeof(INDICE_DATO)+sizeof(int), - &error + &error, + dummy ); } /* Clean up! */ @@ -1009,10 +1029,11 @@ static void abreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *heade * mas de 2 letras iguales, si no no gano nada y complica las cosas */ if (iguales > 1) { + INDICE_DATO dummy1; sprintf(salvar, "%d|%s", iguales, resto); free(actual); error = 0; - idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error); + idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error, dummy1); } else { free(primera); primera = actual; @@ -1039,10 +1060,11 @@ static void desabreviar_claves(INDICE *idx, B_NodoEntry *array, B_NodoHeader *he } iguales = strtol(actual, &resto, 10); if ((iguales > 0) && (*resto == '|')) { + INDICE_DATO dummy2; strncpy(salvar, primera, iguales); salvar[iguales] = '\0'; strcat(salvar, resto+1); /* +1 para saltar el separador */ - idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error); + idx->emu_string->modificar_registro(idx->emu_string, array[i].clave, salvar, strlen(salvar)+1, &error, dummy2); free(actual); } else { free(primera); @@ -1053,8 +1075,83 @@ 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) +void insertar_ordenado(INDICE *idx, B_NodoEntry *buffer, int cant, B_NodoEntry nuevo_entry) { + int i, pos; + for(i=0; (ipos; i--) + buffer[i] = buffer[i-1]; + + buffer[pos] = nuevo_entry; +} + +static void b_partir_dos_nodos_en_tres(INDICE* idx, int nodo_izq, int nodo_der, B_NodoEntry padre_entry, B_NodoEntry nuevo_entry, int id_padre) +{ + PERR("PARTIR 2 EN 3"); + B_NodoEntry *buffer; + char *izq, *der, *padre, *nuevo; + B_NodoEntry *c_der, *c_izq, *c_nuevo, prom1, prom2; + B_NodoHeader h_der, h_izq, h_nuevo; + int i, j, nodo_nuevo; + int cant_claves; + + /* Leo los nodos y los datos */ + der = b_leer_nodo(idx, nodo_der); + izq = b_leer_nodo(idx, nodo_izq); + + b_leer_header(der, &h_der); + b_leer_header(izq, &h_izq); + + c_der = b_leer_claves(der, &h_der); + c_izq = b_leer_claves(izq, &h_izq); + + cant_claves = 2*CANT_HIJOS(idx)+2; + buffer = malloc(cant_claves*sizeof(B_NodoEntry)); + + for(i=0, j=0; iemu_mult->leer_registro(idx->emu_mult, k, &tam, &error); + + if (leido == NULL) { + PERR("LEI CUALQUIER COSA, BUG?"); + return 1; + } + + cant = *((int *)leido); + + /* Obtengo un nuevo lugar para el dato nuevo */ + array = (INDICE_DATO *)(leido+sizeof(int)); + + /* busco pos de dato en array */ + for(pos=0; posemu_mult->borrar_registro(idx->emu_mult, k, dummy1); + return 0; + } + + /* Quito el elemento */ + leido = realloc(leido, sizeof(int)+cant*sizeof(INDICE_DATO)); + + /* Actualizo la cantidad */ + (*((int *)leido)) = cant; + + error = 0; + idx->emu_mult->modificar_registro(idx->emu_mult, + k, + leido, + cant*sizeof(INDICE_DATO)+sizeof(int), + &error, + dummy1 + ); + + free(leido); + + return cant; +} + +#include "indice_b_asc.c"