X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/70181ec30f30250cf0899faf84c6dd24137b2b5c..e71b2f6ba15c4035c6fb10526b4ffd29d44b0ba2:/emufs/indice_b.c?ds=inline diff --git a/emufs/indice_b.c b/emufs/indice_b.c index 2e1615b..228ed2b 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); } @@ -103,13 +105,13 @@ int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato) PERR(idx->nombre); return 0; } - - /* TODO : Implementar carga de valor en clave duplicada! */ - b_insertar_dup_en_pos(idx, claves[i].dato, dato); + + if ((idx->funcion == IND_SELECCION) && (!emufs_indice_es_clave_nula(idx, clave))) + b_insertar_dup_en_pos(idx, claves[i].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 { @@ -131,6 +133,11 @@ int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato) /* Agrego el DATO real al archivo de claves repetiras * y me guardo el ID para poner en el indice */ + if ((idx->funcion == IND_SELECCION) && (emufs_indice_es_clave_nula(idx, clave))) + /* UPS!, la clave que se va a insertar por primera vez es nula + * y soy un indice selectivo!, no lo puedo permitir, ciao!! + */ + return 1; dummy.id = -1; dato.id = b_insertar_dup_en_pos(idx, dummy, dato); } @@ -180,7 +187,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; @@ -216,8 +223,17 @@ 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); + 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); + } + if (encontrado) { + b_borrar_clave(idx, nodo, nodo_id, k); + } } else { PERR("Clave no encontrada"); } @@ -261,8 +277,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; @@ -285,11 +301,11 @@ char *b_leer_nodo(INDICE *idx, int id) } /* Si estoy manejando string tengo que sacar las abreviaturas */ - if (idx->tipo_dato == IDX_STRING) { +/* 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; } @@ -297,15 +313,15 @@ 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) { +/* 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); @@ -455,7 +471,6 @@ static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int n hijo1 = nodo_id; hijo2 = nuevo_id; - fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2); nodo = padre; nodo_id = nodo_header.padre; } else { @@ -480,7 +495,6 @@ static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int n hijo1 = nuevo_id+1; hijo2 = nuevo_id; - fprintf(stderr, "Nodos espliteados = %d %d\n", hijo1, hijo2); /* Limpio al padre */ nuevo = b_leer_nodo(idx, 0); @@ -489,7 +503,6 @@ static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int n nuevo_header.padre = -1; nuevo_header.nivel = nodo_header.nivel+1; nuevo_header.hijo_izquierdo = -1; - fprintf(stderr, "root.nivel=%d\n", nuevo_header.nivel); memset(nuevo, -1, idx->tam_bloque); b_actualizar_header(nuevo, &nuevo_header); b_grabar_nodo(idx, 0, nuevo); @@ -529,7 +542,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); @@ -539,7 +551,6 @@ void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, in char* nuevo = b_leer_nodo(idx, hijo_izq); if (nuevo != NULL) { B_NodoHeader nuevo_header; - fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_izq, nodo_id); b_leer_header(nuevo, &nuevo_header); nuevo_header.padre = nodo_id; b_actualizar_header(nuevo, &nuevo_header); @@ -551,7 +562,6 @@ void b_insertar_en_nodo_con_lugar(INDICE *idx, CLAVE clave, INDICE_DATO dato, in char* nuevo = b_leer_nodo(idx, hijo_der); if (nuevo != NULL) { B_NodoHeader nuevo_header; - fprintf(stderr, "Actualizo padre de %d a %d\n", hijo_der, nodo_id); b_leer_header(nuevo, &nuevo_header); nuevo_header.padre = nodo_id; b_actualizar_header(nuevo, &nuevo_header); @@ -652,12 +662,8 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) while (emufs_indice_es_menor(idx, claves[pos].clave, k)) pos++; /* Es el nodo una hoja? */ - 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,8 +703,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; } @@ -707,10 +712,10 @@ 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); - fprintf(stderr, "ID del padre = %d de nivel %d\n", padre_id, header_padre.nivel); /* TODO Tengo el hijo_izquierdo para revisar!! XXX */ if (header_padre.hijo_izquierdo == actual_id) { PERR("Soy el hijo izquierdo de padre"); @@ -719,6 +724,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,13 +757,11 @@ static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k) PERR("Ta calcule lo que tengo que hacer"); 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); b_pedir_clave_derecha(der, derecha_id, padre, padre_id, actual, actual_id, pos_padre); PERR("listo"); b_leer_header(der, &header_der); b_leer_header(padre, &header_padre); b_leer_header(actual, &header_actual); - fprintf(stderr, "DESPUES DE PEDIR DERECHA TENGO %d claves\n", header_actual.cant); } else if ((izquierda_id != -1) && (header_izq.cant > MIN_HIJOS(idx))) { PERR("Le pido clave a izquierda"); b_pedir_clave_izquierda(izq, izquierda_id, padre, padre_id, actual, actual_id, pos_padre); @@ -797,6 +801,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); @@ -804,13 +809,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! */ @@ -1010,10 +1022,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; @@ -1040,10 +1053,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); @@ -1054,8 +1068,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; +} + +#ifdef NO_TERMINAOD +EMUFS_Estadisticas emufs_indice_b_obtener_estadisticas(INDICE *idx) +{ + EMUFS_Estadisticas stats, st_string, st_multiples; + + stats.tam_archivo = emufs_common_get_file_size(idx->filename); + stats.cant_bloques = stats.tam_archivo/idx->tam_bloque; + +} +#endif + +#include "indice_b_asc.c"