* 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 e97109340c0c5097aa5a00d0b60ab658b3892cc2..e43a3a39866559a787a5e93bb822b969bada9291 100644 (file)
--- 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 (file)
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 (file)
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 (file)
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
+