From 0213eecd485623b3f5def829c4b16acaf4baad2e Mon Sep 17 00:00:00 2001 From: Ricardo Markiewicz Date: Sat, 15 May 2004 17:13:07 +0000 Subject: [PATCH] * Modificaciones necesarias para Borrar registros usando indices * Implemento Borrar en arboles B, me falta fundir, pero el borrar simple anda. --- emufs/emufs.h | 2 +- emufs/indice_b.c | 106 +++++++++++++++++++++++++++++++++++++++++- emufs/indice_b.h | 9 ++-- emufs/indices.c | 2 +- emufs/tipo1.c | 16 +++++-- emufs/tipo1.h | 2 +- emufs/tipo2.c | 18 ++++--- emufs/tipo2.h | 2 +- emufs/tipo2_main.c | 4 +- emufs/tipo3.c | 18 +++++-- emufs/tipo3.h | 2 +- emufs_gui/articulos.c | 13 ++---- emufs_gui/facturas.c | 4 +- emufs_gui/viewer.c | 2 +- 14 files changed, 158 insertions(+), 42 deletions(-) diff --git a/emufs/emufs.h b/emufs/emufs.h index 790fdea..61004dd 100644 --- a/emufs/emufs.h +++ b/emufs/emufs.h @@ -118,7 +118,7 @@ struct _emu_fs_t { void* (*leer_registro_raw)(struct _emu_fs_t*, EMUFS_REG_ID, EMUFS_REG_SIZE*, int *); /**< Método para leer un registro con todo su bloque asociado */ EMUFS_REG_ID (*grabar_registro)(struct _emu_fs_t*, void*, EMUFS_REG_SIZE, int*); /**< Método para grabar un registro */ EMUFS_REG_ID (*modificar_registro)(struct _emu_fs_t*, EMUFS_REG_ID, void*, EMUFS_REG_SIZE, int*); /**< Método para modificar un registro */ - int (*borrar_registro)(struct _emu_fs_t*, EMUFS_REG_ID); /**< Método para borrar un registro */ + int (*borrar_registro)(struct _emu_fs_t*, CLAVE); /**< Método para borrar un registro */ EMUFS_Estadisticas (*leer_estadisticas)(struct _emu_fs_t *); /**< Método para obtener estádisticas sobre el archivo */ void (*compactar)(struct _emu_fs_t *); /**< Método para compactar el archivo reorganizándolo físicamente */ char *nombre; /**< Nombre del archivo */ diff --git a/emufs/indice_b.c b/emufs/indice_b.c index 5097992..96ada55 100644 --- a/emufs/indice_b.c +++ b/emufs/indice_b.c @@ -16,7 +16,8 @@ static void b_leer_header(char *src, B_NodoHeader *header); static void b_actualizar_header(char *src, B_NodoHeader *header); static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header); static void b_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2); -const int b_elegir_izquierdo(INDICE *idx, int a, int b); +static int b_elegir_izquierdo(INDICE *idx, int a, int b); +static void b_borrar_clave(INDICE *idx, char *nodo, int nodo_id, CLAVE k); void emufs_indice_b_crear(INDICE *idx) { @@ -122,6 +123,50 @@ INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave) return ret; } +int emufs_indice_b_borrar(INDICE *idx, CLAVE k) +{ + /* Busco el nodo que contiene la clave,si es que esta existe */ + char *nodo; + int nodo_id, i; + char encontrado=0; + B_NodoHeader header; + B_NodoEntry *claves; + + nodo_id = 0; /* Tomo la raiz */ + nodo = b_leer_nodo(idx, nodo_id); + PERR("Buscando clave a borrar"); + while (nodo && !encontrado) { + /* Obtengo los datos del nodo */ + b_leer_header(nodo, &header); + claves = b_leer_claves(nodo, &header); + + i=0; + while ((i= MIN_HIJOS(idx)) { + PERR("Borrar completo sin fundir"); + return; + } + + /* Tengo que pasar datos o fundir nodos :-( */ + PERR("TODO : FUNDIR NODOS!!!!\n"); +} + diff --git a/emufs/indice_b.h b/emufs/indice_b.h index 7093de2..266bbe1 100644 --- a/emufs/indice_b.h +++ b/emufs/indice_b.h @@ -22,11 +22,7 @@ typedef struct _b_nodo_header_ { typedef struct _b_nodo_entry_ { CLAVE clave; - /* Si el nivel del nodo == 0, quiere decir que es el - * bloque del archivo de datos donde esta el registro. - * Si el nivel != 0, es el siguiente bloque dentro - * del archivo de indice donde buscar - */ + /* Dato guardado */ INDICE_DATO dato; /* El ID de la hoja de depliega a la derecha */ int hijo_derecho; @@ -38,6 +34,9 @@ void emufs_indice_b_crear(INDICE *idx); /* Inserta un par clave-ubicacion */ int emufs_indice_b_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato); +/* Borra una entrada */ +int emufs_indice_b_borrar(INDICE *idx, CLAVE k); + /* Busca una clave, retorna ubicacion o -1 si no existe */ INDICE_DATO emufs_indice_b_buscar(INDICE *idx, CLAVE clave); diff --git a/emufs/indices.c b/emufs/indices.c index fa99903..8a54d99 100644 --- a/emufs/indices.c +++ b/emufs/indices.c @@ -35,7 +35,7 @@ INDICE *emufs_indice_crear(EMUFS *emu, char *nombre, INDICE_FUNCION funcion, IND PERR("Creando indice con Arbol B"); emufs_indice_b_crear(tmp); tmp->agregar_entrada = emufs_indice_b_insertar; - tmp->borrar_entrada = NULL; + tmp->borrar_entrada = emufs_indice_b_borrar; tmp->existe_entrada = emufs_indice_b_buscar; tmp->buscar_entradas = NULL; break; diff --git a/emufs/tipo1.c b/emufs/tipo1.c index 76b1e9b..d14d756 100644 --- a/emufs/tipo1.c +++ b/emufs/tipo1.c @@ -366,19 +366,27 @@ EMUFS_REG_ID emufs_tipo1_grabar_registro(EMUFS* efs, void* reg, return header.id; } -int emufs_tipo1_borrar_registro(EMUFS* efs, EMUFS_REG_ID reg_id) +int emufs_tipo1_borrar_registro(EMUFS* efs, CLAVE k) { char* block; /* bloque leido (en donde está el registro a leer) */ EMUFS_BLOCK_ID block_id; /* id del bloque en donde esta el registro a leer */ EMUFS_BLOCK_SIZE offset; /* offset del bloque leído */ EMUFS_TIPO1_REG_HEADER curr_reg_header; /* cabecera del registro a leer */ + EMUFS_REG_ID reg_id; + INDICE_DATO dato; int err = 0; /* para almacenar código de error */ - block_id = emufs_idx_buscar_registro(efs, reg_id); + /*block_id = emufs_idx_buscar_registro(efs, reg_id); if (block_id == EMUFS_NOT_FOUND) { PERR("Registro no encontrado"); return EMUFS_NOT_FOUND; - } + }*/ + dato = efs->indices->existe_entrada(efs->indices, k); + block_id = dato.bloque; /*emufs_idx_buscar_registro(emu, ID);*/ + reg_id = dato.id; + + if (reg_id == -1) return EMUFS_NOT_FOUND; + if (!(block = (char*) emufs_tipo1_leer_bloque(efs, block_id, &err))) { PERR("no se pudo reservar memoria"); return err; @@ -685,7 +693,7 @@ EMUFS_BLOCK_ID emufs_tipo1_grabar_bloque_fsc(EMUFS *efs, void *block, EMUFS_REG_ID emufs_tipo1_modificar_registro(EMUFS* efs, EMUFS_REG_ID id, void *data, EMUFS_REG_SIZE size, int* err) { - emufs_tipo1_borrar_registro(efs, id); +/* emufs_tipo1_borrar_registro(efs, id);*/ return emufs_tipo1_grabar_registro(efs, data, size, err); } diff --git a/emufs/tipo1.h b/emufs/tipo1.h index a3c667f..ec74926 100644 --- a/emufs/tipo1.h +++ b/emufs/tipo1.h @@ -54,7 +54,7 @@ void* emufs_tipo1_leer_registro(EMUFS*, CLAVE, EMUFS_REG_SIZE*, int*); EMUFS_REG_ID emufs_tipo1_grabar_registro(EMUFS*, void*, EMUFS_REG_SIZE, int*); /** Borra un registro de del archivo. */ -int emufs_tipo1_borrar_registro(EMUFS*, EMUFS_REG_ID); +int emufs_tipo1_borrar_registro(EMUFS*, CLAVE); /** Método para modificar un registro. */ EMUFS_REG_ID emufs_tipo1_modificar_registro(EMUFS *emu, EMUFS_REG_ID, void*, EMUFS_REG_SIZE, int*); diff --git a/emufs/tipo2.c b/emufs/tipo2.c index fd20bba..f62f650 100644 --- a/emufs/tipo2.c +++ b/emufs/tipo2.c @@ -177,16 +177,22 @@ EMUFS_REG_ID emufs_tipo2_grabar_registro(EMUFS *efs, void *ptr, EMUFS_REG_SIZE r } /* Borra un registro determinado y actualiza los archivos de Posicion Relativa (Indice-Offset) y el de Gaps */ -int emufs_tipo2_borrar_registro(EMUFS *efs, EMUFS_REG_ID id_reg) +int emufs_tipo2_borrar_registro(EMUFS *efs, CLAVE k) { EMUFS_OFFSET reg_offset,reg_size; - + EMUFS_REG_ID id_reg; + INDICE_DATO dato; /* Obtenemos el offset donde arranca el registro */ - if ((reg_offset = emufs_idx_buscar_registro(efs,id_reg)) == EMUFS_NOT_FOUND) { - /* TODO Manejo de errores */ + /*if ((reg_offset = emufs_idx_buscar_registro(efs,id_reg)) == EMUFS_NOT_FOUND) { PERR("Registro no encontrado"); return EMUFS_NOT_FOUND; - } + }*/ + + dato = efs->indices->existe_entrada(efs->indices, k); + id_reg = dato.id; + reg_offset = dato.bloque; + + if (id_reg == -1) return EMUFS_NOT_FOUND; /* Obtenemos el Size del Registro en cuestion y hacemos un dummyfill*/ emufs_tipo2_get_regsize(efs,reg_offset,®_size); @@ -253,7 +259,7 @@ int emufs_tipo2_dummyfill(EMUFS *efs, EMUFS_OFFSET reg_pos, EMUFS_REG_SIZE amoun /* Realiza la actualizacin de un registro ya existente */ EMUFS_REG_ID emufs_tipo2_modificar_registro(EMUFS *efs, EMUFS_REG_ID id, void *data, EMUFS_REG_SIZE size, int *error) { - emufs_tipo2_borrar_registro(efs, id); + /*emufs_tipo2_borrar_registro(efs, id);*/ return emufs_tipo2_grabar_registro(efs, data, size, error); } diff --git a/emufs/tipo2.h b/emufs/tipo2.h index c80ef3b..da79dc4 100644 --- a/emufs/tipo2.h +++ b/emufs/tipo2.h @@ -97,7 +97,7 @@ EMUFS_REG_ID emufs_tipo2_grabar_registro(EMUFS *efs, void *ptr, EMUFS_REG_SIZE r * \param id_reg Id del registro que se quiere eliminar. * \return \b int Indicador de exito de la operacion. */ -int emufs_tipo2_borrar_registro(EMUFS *efs, EMUFS_REG_ID id_reg); +int emufs_tipo2_borrar_registro(EMUFS *efs, CLAVE k); /** Devuelve el \em Size de un registro dado, en base a su \em ID. * diff --git a/emufs/tipo2_main.c b/emufs/tipo2_main.c index f7157dc..1fe3efc 100644 --- a/emufs/tipo2_main.c +++ b/emufs/tipo2_main.c @@ -93,9 +93,9 @@ int main(int argc, char *argv[]) efs->borrar_registro(efs, n4);*/ /* Prueba de recompactacion */ - efs->borrar_registro(efs, n7); + /*efs->borrar_registro(efs, n7); efs->borrar_registro(efs, n4); - efs->borrar_registro(efs, n2); + efs->borrar_registro(efs, n2); */ n9 = efs->grabar_registro(efs, d, 8, &err); diff --git a/emufs/tipo3.c b/emufs/tipo3.c index 5ce17d5..bf93f81 100644 --- a/emufs/tipo3.c +++ b/emufs/tipo3.c @@ -332,13 +332,14 @@ int emufs_tipo3_grabar_bloque(EMUFS *emu, void *ptr, EMUFS_BLOCK_ID num) } /*borra un registro de un bloque y acomoda los registros que quedan*/ -int emufs_tipo3_borrar_registro(EMUFS *emu, EMUFS_REG_ID ID) +int emufs_tipo3_borrar_registro(EMUFS *emu, CLAVE k) { EMUFS_BLOCK_SIZE num_bloque; EMUFS_BLOCK_SIZE ptr_elim; EMUFS_BLOCK_SIZE ptr_mov; - EMUFS_REG_ID ID_aux; + EMUFS_REG_ID ID_aux, ID; EMUFS_FREE fs; + INDICE_DATO dato; char *bloque; int err = 0, i, cant_bloques; @@ -346,14 +347,21 @@ int emufs_tipo3_borrar_registro(EMUFS *emu, EMUFS_REG_ID ID) cant_bloques = emu->tam_reg/(emu->tam_bloque-sizeof(EMUFS_REG_ID))+1; if ( emu->tam_reg+sizeof(EMUFS_REG_ID) == emu->tam_bloque ) cant_bloques = 1; - - num_bloque = emufs_idx_buscar_registro(emu, ID); + + PERR("Buscando datos del registro en el indice"); + dato = emu->indices->existe_entrada(emu->indices, k); + num_bloque = dato.bloque; /*emufs_idx_buscar_registro(emu, ID);*/ + ID = dato.id; + if (!(bloque = emufs_tipo3_leer_bloque(emu, num_bloque, &err))) { /* TODO Manejo de errores */ PERR("no se pudo leer el bloque"); return -1; } + PERR("Borrando clave"); + /* TODO Borrar en todos los indices!! */ + emu->indices->borrar_entrada(emu->indices, k); /*apunto al registro que voy a eliminar*/ ptr_elim = 0; while ( ptr_elim < emu->tam_bloque ){ @@ -466,7 +474,7 @@ EMUFS_Estadisticas emufs_tipo3_leer_estadisticas(EMUFS *emu) EMUFS_REG_ID emufs_tipo3_modificar_registro(EMUFS *emu, EMUFS_REG_ID id, void *data, EMUFS_REG_SIZE size, int *error) { - emufs_tipo3_borrar_registro(emu, id); + /*emufs_tipo3_borrar_registro(emu, id);*/ return emufs_tipo3_grabar_registro(emu, data, size, error); } diff --git a/emufs/tipo3.h b/emufs/tipo3.h index ee19aee..720905b 100644 --- a/emufs/tipo3.h +++ b/emufs/tipo3.h @@ -92,7 +92,7 @@ int emufs_tipo3_grabar_bloque(EMUFS *emu, void *ptr, EMUFS_BLOCK_ID num_bloque); * \param emu Esructura para manejar los archivos. * \param id_reg Id del registro a borrar. */ -int emufs_tipo3_borrar_registro(EMUFS *emu, EMUFS_REG_ID id_reg); +int emufs_tipo3_borrar_registro(EMUFS *emu, CLAVE k); /** Método para modificar un registro * \param emu Esructura para manejar los archivos. diff --git a/emufs_gui/articulos.c b/emufs_gui/articulos.c index 59a3f35..7abf14d 100644 --- a/emufs_gui/articulos.c +++ b/emufs_gui/articulos.c @@ -335,8 +335,8 @@ void art_eliminar(char *s) { WINDOW *win; t_Articulo *articulo; - t_Reg_Articulo *nodo; EMUFS_REG_ID id; + CLAVE k; win = newwin(8, COLS-2, 13, 1); box(win, 0, 0); @@ -351,15 +351,8 @@ void art_eliminar(char *s) wrefresh(win); getch(); } else { - nodo = lst_articulos->primero; - while (nodo) { - if (nodo->numero == articulo->numero) { - lst_articulos->fp->borrar_registro(lst_articulos->fp, nodo->num_reg); - eliminar_nodo_articulo(lst_articulos, nodo); - break; - } - nodo = nodo->sig; - } + k = emufs_indice_generar_clave_desde_valor(lst_articulos->fp->indices, (char *)&(articulo->numero)); + lst_articulos->fp->borrar_registro(lst_articulos->fp, k); free(articulo); } diff --git a/emufs_gui/facturas.c b/emufs_gui/facturas.c index 8e2526a..b713ba6 100644 --- a/emufs_gui/facturas.c +++ b/emufs_gui/facturas.c @@ -402,8 +402,8 @@ void fact_eliminar(char *s) nodo = lst_facturas->primero; while (nodo) { if (nodo->numero == fact->numero) { - lst_facturas->fp->borrar_registro(lst_facturas->fp, nodo->num_reg); - lst_facturas->fp_texto->borrar_registro(lst_facturas->fp_texto, nodo->texto_reg); + /*lst_facturas->fp->borrar_registro(lst_facturas->fp, nodo->num_reg);*/ + /*lst_facturas->fp_texto->borrar_registro(lst_facturas->fp_texto, nodo->texto_reg);*/ eliminar_nodo_factura(lst_facturas, nodo); break; } diff --git a/emufs_gui/viewer.c b/emufs_gui/viewer.c index 10bcff6..1290631 100644 --- a/emufs_gui/viewer.c +++ b/emufs_gui/viewer.c @@ -373,7 +373,7 @@ void ver_registros(WINDOW *padre, int w, int h, int cual) case 'e': case 'E': if (indices_actual != EMUFS_NOT_FOUND) - fp->borrar_registro(fp, indices[indices_actual]); + /*fp->borrar_registro(fp, indices[indices_actual]); XXX*/ free(indices); indices = emufs_idx_get(fp, &indices_total); -- 2.43.0