From 5b7414e56edebd004eee0a746ed7e64c64c52d0c Mon Sep 17 00:00:00 2001 From: Ricardo Markiewicz Date: Sat, 29 May 2004 19:58:41 +0000 Subject: [PATCH] Empiezo a implementar el B*, por ahora en un archivo aparte para poder trabajar tranquilo. (OJO, PONER indice_b_asc.c EN MAKEFILE!) --- emufs/Makefile | 2 + emufs/indice_b.c | 2 + emufs/indice_b_asc.c | 275 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 279 insertions(+) create mode 100644 emufs/indice_b_asc.c diff --git a/emufs/Makefile b/emufs/Makefile index e1c92c9..8b7307a 100644 --- a/emufs/Makefile +++ b/emufs/Makefile @@ -9,6 +9,8 @@ TARGETS=libemufs.a tipo1_main tipo2_main tipo3_main b_plus_test tipo1_bplus_main all: $(TARGETS) +indice_b.o: indice_b.c indice_b_asc.c + tipo1_main: tipo1_main.o $(EMUFS_COMMON) tipo2_main: tipo2_main.o $(EMUFS_COMMON) diff --git a/emufs/indice_b.c b/emufs/indice_b.c index 82fa466..7338622 100644 --- a/emufs/indice_b.c +++ b/emufs/indice_b.c @@ -1313,3 +1313,5 @@ int b_borrar_dup_clave(INDICE *idx, INDICE_DATO k_dato, INDICE_DATO dato) return cant; } +#include "indice_b_asc.c" + diff --git a/emufs/indice_b_asc.c b/emufs/indice_b_asc.c new file mode 100644 index 0000000..fa688f4 --- /dev/null +++ b/emufs/indice_b_asc.c @@ -0,0 +1,275 @@ + + +static void b_asc_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2); + +int emufs_indice_b_asc_insertar(INDICE *idx, CLAVE clave, INDICE_DATO dato) +{ + int i, nodo_id, padre_id; + B_NodoHeader header; + B_NodoEntry *claves; + char *nodo, *padre; + INDICE_DATO dummy; + + /* Leo la raiz */ + nodo = b_leer_nodo(idx, 0); + padre_id = nodo_id = 0; + padre = NULL; + while (nodo) { + if (padre) free(padre); + padre = nodo; + padre_id = nodo_id; + b_leer_header(nodo, &header); + claves = b_leer_claves(nodo, &header); + i=0; + while ((ifuncion == IND_PRIMARIO) { + PERR("Indice primario no puede contener claves duplicadas!"); + PERR(idx->nombre); + return 0; + } + + 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, dummy); + } + return 1; + } else { + if (i == 0) { + nodo = b_leer_nodo(idx, header.hijo_izquierdo); + nodo_id = header.hijo_izquierdo; + } else { + nodo = b_leer_nodo(idx, claves[i-1].hijo_derecho); + nodo_id = claves[i-1].hijo_derecho; + } + } + } + + if (nodo) free(nodo); + nodo = padre; + nodo_id = padre_id; + + if (idx->funcion != IND_PRIMARIO) { + /* Agrego el DATO real al archivo de claves repetiras + * y me guardo el ID para poner en el indice + */ + dummy.id = -1; + dato.id = b_insertar_dup_en_pos(idx, dummy, dato); + } + + b_asc_insertar_en_nodo(idx, clave, dato, nodo_id, nodo, -1, -1); + return 1; /* Agregar OK! */ +} + + +static void b_asc_insertar_en_nodo(INDICE *idx, CLAVE clave, INDICE_DATO dato, int nodo_id, char *nodo, int hijo1, int hijo2) +{ + char *padre, *nuevo; + int nuevo_id; + int i, j; + static int rompi=0; + char salir = 0; + char *izq, *der; + B_NodoHeader nodo_header, nuevo_header; + B_NodoEntry *claves, *tmp_claves, *claves_nuevo; + + do { + if (!nodo) { + /* CREAR NODO? */ + nodo = b_crear_nodo(idx, &nodo_id); + } + b_leer_header(nodo, &nodo_header); + claves = b_leer_claves(nodo, &nodo_header); + + padre = b_leer_nodo(idx, nodo_header.padre); + + if (nodo_header.cant == CANT_HIJOS(idx)) { + int total; + if (nodo_id != 0) { + int izq_id, der_id, pos_padre, i; + B_NodoHeader padre_header, header_der, header_izq; + B_NodoEntry *padre_claves; + B_NodoEntry a_pasar, *buffer; + + b_leer_header(padre, &padre_header); + padre_claves = b_leer_claves(padre, &padre_header); + + /* nuevo_entry = new entry(clave, dato, hijo_der) */ + PERR("Buscando que hijo soy"); + for(pos_padre=0; (padre_claves[pos_padre].hijo_derecho != nodo_id); pos_padre++) { } + + if (pos_padre == padre_header.cant) { + PERR("ERROR GRAVE. Padre no me contiene :-("); + } + + /* Busco mis hermanos a derecha e izquierda, si es que existen */ + PERR("Ya me encontre, busco a mis hermanos"); + if (pos_padre >= 0) { + if (pos_padre == 0) + izq_id = padre_header.hijo_izquierdo; + else + izq_id = padre_claves[pos_padre-1].hijo_derecho; + izq = b_leer_nodo(idx, izq_id); + b_leer_header(izq, &header_izq); + } else { + izq_id = -1; + } + if (pos_padre < padre_header.cant) { + der_id = padre_claves[pos_padre+1].hijo_derecho; + der = b_leer_nodo(idx, der_id); + b_leer_header(der, &header_der); + } else { + der_id = -1; + } + PERR("Hermanos encontrados"); + + buffer = malloc((nodo_header.cant+1)*sizeof(B_NodoEntry)); + + /* Inserto ordenado */ + for(i=0; (itam_bloque-sizeof(B_NodoHeader)); + for(j=0; jtam_bloque-sizeof(B_NodoHeader)); + for(j=0; jtam_bloque); + free(nodo); + nodo = tmp_nuevo; + + clave = tmp_claves[total/2].clave; + dato = tmp_claves[total/2].dato; + + b_grabar_nodo(idx, nuevo_id+1, nodo); + b_grabar_nodo(idx, nuevo_id, nuevo); + + free(nodo); + free(nuevo); + free(tmp_claves); + + 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); + + b_leer_header(nuevo, &nuevo_header); + nuevo_header.cant = 0; + 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); + + nodo_id = 0; + nodo = nuevo; + rompi = 1; + } + } else { + /* La clave entra en este nodo!! */ + b_insertar_en_nodo_con_lugar(idx, clave, dato, nodo_id, nodo, hijo1, hijo2); + salir = 1; + } + } while (!salir); +} + -- 2.43.0