From: Ricardo Markiewicz <gazer.arg@gmail.com>
Date: Sun, 9 May 2004 06:06:45 +0000 (+0000)
Subject:  * Agrego arboles B sobre archivos (TEST MODE, no se integra con indice aun).
X-Git-Tag: svn_import_r684~262
X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/db30ec34669e71266f038fcf7cb2386fa210d531

 * Agrego arboles B sobre archivos (TEST MODE, no se integra con indice aun).
    - BUSCAR Done
		- INSERTAR Donecon algun BUGS
		- BORRAR No Implementado
---

diff --git a/emufs/Makefile b/emufs/Makefile
index e971093..e43a3a3 100644
--- a/emufs/Makefile
+++ b/emufs/Makefile
@@ -3,7 +3,7 @@ LDFLAGS=-lm
 
 EMUFS_COMMON=emufs.o tipo1.o tipo2.o tipo3.o idx.o did.o fsc.o common.o indices.o
 
-all: libemufs.a tipo1_main tipo2_main tipo3_main
+all: libemufs.a tipo1_main tipo2_main tipo3_main b_test
 
 tipo1_main: tipo1_main.o $(EMUFS_COMMON)
 
@@ -11,6 +11,8 @@ tipo2_main: tipo2_main.o $(EMUFS_COMMON)
 
 tipo3_main: tipo3_main.o $(EMUFS_COMMON)
 
+b_test: b_test.o indice_b.o
+
 libemufs.a: $(EMUFS_COMMON)
 	$(AR) cru libemufs.a $(EMUFS_COMMON)
 
diff --git a/emufs/b_test.c b/emufs/b_test.c
new file mode 100644
index 0000000..12d3809
--- /dev/null
+++ b/emufs/b_test.c
@@ -0,0 +1,21 @@
+
+#include "indice_b.h"
+
+int main(int argc, char *argv[])
+{
+	int pos;
+	b_crear();
+
+	for(pos = 0; pos < 540; pos++)
+		b_insertar(65+pos, pos);
+
+	pos = b_buscar(70);
+
+	if (pos == -1)
+		printf("No encontrado\n");
+	else
+		printf("Esta en la pos %d\n", pos);
+
+	return 0;
+}
+
diff --git a/emufs/indice_b.c b/emufs/indice_b.c
new file mode 100644
index 0000000..b9cc9c3
--- /dev/null
+++ b/emufs/indice_b.c
@@ -0,0 +1,388 @@
+
+#include "indice_b.h"
+
+#define FILENAME "b.idx"
+#define BLOCK_SIZE 512
+
+/* Cantidad de claves por nodo */
+#define CANT_HIJOS ((BLOCK_SIZE-sizeof(B_NodoHeader))/sizeof(B_NodoEntry))
+#define CANT_NODOS (CANT_HIJOS+1)
+#define MIN_HIJOS (CANT_HIJOS/2)
+
+/* Auxiliares */
+static void b_grabar_nodo(int id, char *data);
+static int b_ultimo_id();
+static char *b_leer_nodo(int id);
+static char *b_crear_nodo();
+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(int clave, int ubicacion, int nodo_id, char *nodo, int hijo1, int hijo2);
+
+void b_crear()
+{
+	FILE *fp;
+	char *bloque;
+	B_NodoHeader header;
+
+	header.cant = 0;
+	header.nivel = 0;
+	header.padre = -1;
+	header.hijo_izquierdo = -1;
+
+	fp = fopen(FILENAME, "w");
+	
+	/* Creo el archivo con el Nodo raiz */
+	bloque = (char *)malloc(BLOCK_SIZE);
+	memset(bloque, -1, BLOCK_SIZE);
+
+	memcpy(bloque, &header, sizeof(B_NodoHeader));
+
+	fwrite(bloque, BLOCK_SIZE, 1, fp);
+	fclose(fp);
+}
+
+int b_insertar(int clave, int ubicacion)
+{
+	int i, nodo_id, padre_id;
+	B_NodoHeader header;
+	B_NodoEntry *claves;
+	char *nodo, *padre;
+	
+	/* Leo la raiz */
+	nodo = b_leer_nodo(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 ((i<header.cant) && (claves[i].clave < clave)) i++;
+		if ((i<header.cant) && (claves[i].clave == clave)) {
+			/* CLAVE DUPLICADA! */
+			return 0;
+		} else {
+			if (i == 0) {
+				if (header.nivel != 0) {
+					nodo = b_leer_nodo(header.hijo_izquierdo);
+					nodo_id = header.hijo_izquierdo;
+				} else {
+					nodo = NULL;
+					nodo_id = -1;
+				}
+			} else {
+				if (header.nivel != 0) {
+					nodo = b_leer_nodo(claves[i-1].ubicacion);
+					nodo_id = claves[i-1].ubicacion;
+				} else {
+					nodo = NULL;
+					nodo_id = -1;
+				}
+			}
+		}
+	}
+
+	if (nodo) free(nodo);
+	nodo = padre;
+	nodo_id = padre_id;
+	b_insertar_en_nodo(clave, ubicacion, nodo_id, nodo, -1, -1);
+	return 1; /* Agregar OK! */
+}
+
+int b_buscar(int clave)
+{
+	int i, ret;
+	B_NodoHeader header;
+	B_NodoEntry *claves;
+	char *nodo, *tmp;
+	
+	/* Leo la raiz */
+	nodo = b_leer_nodo(0);
+	while (nodo) {
+		b_leer_header(nodo, &header);
+		claves = b_leer_claves(nodo, &header);
+		i=0;
+		while ((i<header.cant) && (claves[i].clave < clave)) i++;
+		if (claves[i].clave == clave) {
+				ret = claves[i].ubicacion;
+				free(nodo);
+				return ret;
+		} else {
+			tmp = nodo;
+			if (i == 0) {
+				nodo = b_leer_nodo(header.hijo_izquierdo);
+				printf("Me voy a izquierda = %d\n", header.hijo_izquierdo);
+			} else {
+				nodo = b_leer_nodo(claves[i-1].ubicacion);
+				printf("Me voy a hijo=%li\n", claves[i-1].ubicacion);
+			}
+			free(tmp);
+		}
+	}
+
+	/* Nodo no encontrado */
+	return -1;
+}
+
+static int b_ultimo_id()
+{
+	int i;
+	FILE *fp;
+	fp = fopen(FILENAME, "r");
+	fseek(fp, 0, SEEK_END);
+	i = ftell(fp)/BLOCK_SIZE;
+	fclose(fp);
+
+	return i;
+}
+
+static char *b_crear_nodo(int *id)
+{
+	char *bloque;
+	B_NodoHeader header;
+
+	(*id) = b_ultimo_id();
+
+	printf("Nuevo nodo creado : id = %d\n", *id);
+	header.cant = 0;
+	header.nivel = 0;
+	header.hijo_izquierdo = -1;
+	header.padre = -1;
+
+	bloque = (char *)malloc(BLOCK_SIZE);
+	memset(bloque, -1, BLOCK_SIZE);
+	memcpy(bloque, &header, sizeof(B_NodoHeader));
+
+	b_grabar_nodo(*id, bloque);
+
+	return bloque;
+}
+
+static char *b_leer_nodo(int id)
+{
+	FILE *fp;
+	char *out;
+
+	if (id < 0) return NULL;
+
+	fp = fopen(FILENAME, "r");
+	if (fp == NULL) return NULL;
+
+	fseek(fp, id*BLOCK_SIZE, SEEK_SET);
+
+	out = (char *)malloc(BLOCK_SIZE);
+	if (out == NULL) {
+		fclose(fp);
+		return NULL;
+	}
+
+	if (fread(out, 1, BLOCK_SIZE, fp) != BLOCK_SIZE) {
+		free(out);
+		/* No se puso leer el nodo */
+		fclose(fp);
+		return NULL;
+	}
+
+	fclose(fp);
+	return out;
+}
+
+static void b_grabar_nodo(int id, char *data)
+{
+	FILE *fp;
+
+/*	if (id > b_ultimo_id()) {
+		printf("AGREGANDO AL FINAL\n");
+		fp = fopen(FILENAME, "a");
+		if (fp == NULL) {
+		_("No se pudo abrir archivo\n");
+			return;
+		}
+	} else {
+		fp = fopen(FILENAME, "w");
+		if (fp == NULL) {
+		_("No se pudo abrir archivo\n");
+			return;
+		}
+		fseek(fp, id*BLOCK_SIZE, SEEK_SET);
+		printf("SOLO GUARDO DATA\n");
+	}*/
+
+	fp = fopen(FILENAME, "r+");
+	fseek(fp, id*BLOCK_SIZE, SEEK_SET);
+	fwrite(data, 1, BLOCK_SIZE, fp);
+	fclose(fp);
+}
+
+static void b_leer_header(char *src, B_NodoHeader *header)
+{
+	if (!src) return;
+
+	memcpy(header, src, sizeof(B_NodoHeader));
+}
+
+static void b_actualizar_header(char *src, B_NodoHeader *header)
+{
+	if (!src) return;
+	memcpy(src, header, sizeof(B_NodoHeader));
+}
+
+static B_NodoEntry *b_leer_claves(char *src, B_NodoHeader *header)
+{
+	return (B_NodoEntry *)(src+sizeof(B_NodoHeader));
+}
+
+static void b_insertar_en_nodo(int clave, int ubicacion, 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;
+	B_NodoHeader nodo_header, nuevo_header;
+	B_NodoEntry *claves, *tmp_claves, *claves_nuevo;
+
+	do {
+		if (!nodo) {
+			/* CREAR NODO? */
+			nodo = b_crear_nodo(&nodo_id);
+		}
+		b_leer_header(nodo, &nodo_header);
+		claves = b_leer_claves(nodo, &nodo_header);
+
+		padre = b_leer_nodo(nodo_header.padre);
+
+		if (nodo_header.cant == CANT_HIJOS) {
+			int total;
+			nuevo = b_crear_nodo(&nuevo_id);
+			i=0;
+			/* Creo una lista ordenada de los nodos a partir */
+			tmp_claves = (B_NodoEntry *)malloc(sizeof(B_NodoEntry)*(nodo_header.cant+1));
+			total = nodo_header.cant+1;
+			while ((i<nodo_header.cant) && (claves[i].clave < clave)) {
+				tmp_claves[i] = claves[i];
+				i++;
+			}
+			tmp_claves[i].clave = clave;
+			tmp_claves[i].ubicacion = ubicacion;
+			while (i < nodo_header.cant) {
+				tmp_claves[i+1] = claves[i];
+				i++;
+			}
+			
+			/* Asigno a cada nodo lo que corresponde */
+			b_leer_header(nuevo, &nuevo_header);
+
+			nuevo_header.nivel = nodo_header.nivel;
+			nodo_header.cant = total/2;
+			nuevo_header.cant = total - nodo_header.cant;
+
+			memset(claves, '*', BLOCK_SIZE-sizeof(B_NodoHeader));
+			for(j=0; j<nodo_header.cant; j++)
+				claves[j] = tmp_claves[j];
+
+			claves_nuevo = b_leer_claves(nuevo, &nuevo_header);
+			memset(claves_nuevo, '*', BLOCK_SIZE-sizeof(B_NodoHeader));
+			for(j=0; j<nuevo_header.cant; j++)
+				claves_nuevo[j] = tmp_claves[j+nodo_header.cant];
+
+			b_actualizar_header(nodo, &nodo_header);
+			b_actualizar_header(nuevo, &nuevo_header);
+
+			if (nodo_id != 0) {
+				clave = claves_nuevo[0].clave; /*tmp_claves[total/2].clave;*/
+				ubicacion = nuevo_id;
+
+				b_grabar_nodo(nodo_id, nodo);
+				b_grabar_nodo(nuevo_id, nuevo);
+				free(nodo);
+				free(nuevo);
+				free(tmp_claves);
+
+				hijo1 = nodo_id;
+				hijo2 = nuevo_id;
+
+				nodo = padre;
+				nodo_id = nodo_header.padre;
+			} else {
+				/* Oops, parti el raiz, y este debe quedar en 0, lo paso a otro bloque
+				 * y dejo el padre vacio
+				 */
+				char *tmp_nuevo = b_crear_nodo(&nodo_id);
+				memcpy(tmp_nuevo, nodo, BLOCK_SIZE);
+				free(nodo);
+				nodo = tmp_nuevo;
+	
+				clave = claves_nuevo[0].clave; /*tmp_claves[total/2].clave;*/
+				ubicacion = nodo_id; /*nuevo_id;*/
+
+				b_grabar_nodo(nuevo_id+1, nodo);
+				b_grabar_nodo(nuevo_id, nuevo);
+		
+				free(nodo);
+				free(nuevo);
+				free(tmp_claves);
+
+				hijo1 = nuevo_id+1;
+				hijo2 = nuevo_id;
+
+				/* Limpio al padre */
+				nuevo = b_leer_nodo(0);
+
+				b_leer_header(nuevo, &nuevo_header);
+				nuevo_header.cant = 0;
+				nuevo_header.padre = -1;
+				nuevo_header.nivel = nodo_header.nivel+1;
+				memset(nuevo, -1, BLOCK_SIZE);
+				b_actualizar_header(nuevo, &nuevo_header);
+				b_grabar_nodo(0, nuevo);
+
+				nodo_id = 0;
+				nodo = nuevo;
+				rompi = 1;
+			}
+		} else {
+			/* La clave entra en este nodo!! */
+			i = 0;
+			if (nodo_header.cant > 0) {
+				while ((claves[i].clave < clave) && (i < nodo_header.cant)) i++;
+				for(j=nodo_header.cant; j > i; j--)
+					claves[j] = claves[j-1];
+			}
+			nodo_header.cant++;
+			claves[i].clave = clave;
+			claves[i].ubicacion = ubicacion;
+			nodo_header.hijo_izquierdo = hijo1;
+
+			b_actualizar_header(nodo, &nodo_header);
+			b_grabar_nodo(nodo_id, nodo);
+
+			/* Debo actualizar los punteros al padre de los hijos */
+			if (hijo1 != -1) {
+				nuevo = b_leer_nodo(hijo1);
+				if (nuevo != NULL) {
+					b_leer_header(nuevo, &nuevo_header);
+					nuevo_header.padre = nodo_id;
+					b_actualizar_header(nuevo, &nuevo_header);
+					b_grabar_nodo(hijo1, nuevo);
+					free(nuevo);
+				} else printf("FUCK! hijo1=%d no existe!\n", hijo1);
+			}
+			if (hijo2 != -1) {
+				nuevo = b_leer_nodo(hijo2);
+				if (nuevo != NULL) {
+					b_leer_header(nuevo, &nuevo_header);
+					nuevo_header.padre = nodo_id;
+					b_actualizar_header(nuevo, &nuevo_header);
+					b_grabar_nodo(hijo2, nuevo);
+					free(nuevo);
+				} else printf("FUCK! hijo2=%d no existe!\n", hijo2);
+			}
+			salir = 1;
+		}
+	} while (!salir);
+}
+
diff --git a/emufs/indice_b.h b/emufs/indice_b.h
new file mode 100644
index 0000000..c0a1bf3
--- /dev/null
+++ b/emufs/indice_b.h
@@ -0,0 +1,44 @@
+
+
+#ifndef _ARBOL_B_
+#define _ARBOL_B_ 1
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "indices.h"
+
+typedef struct _b_nodo_header_ {
+	int nivel; /* Numero de nivel. Si es hoja debe ser 0 */
+	int cant; /* Cantidad de items en el nivel */
+	int padre;
+	
+	/* Nodo al que debo ir si la clave a insertar/buscar/borrar
+	 * es menor que la primera del nodo
+	 */
+	int hijo_izquierdo;
+} B_NodoHeader;
+
+typedef struct _b_nodo_entry_ {
+	/* FIXME usar tipo CLAVE */
+	int 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
+	 */
+	long ubicacion;
+} B_NodoEntry;
+
+/* Crea un arbol */
+void b_crear();
+
+/* Inserta un par clave-ubicacion */
+int b_insertar(int clave, int ubicacion);
+
+/* Busca una clave, retorna ubicacion o -1 si no existe */
+int b_buscar(int clave);
+
+
+#endif
+