From 1cded9108ca388be764e0ac32118dca6df540e86 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Mon, 17 May 2004 01:57:08 +0000 Subject: [PATCH] Arrancamos, a algun lado llegaremos..Minor test included --- emufs/Makefile | 4 +- emufs/b_plus.c | 113 +++++++++++++++++++++++++++++++++----------- emufs/b_plus.h | 11 ++++- emufs/b_plus_test.c | 19 ++++++-- 4 files changed, 112 insertions(+), 35 deletions(-) diff --git a/emufs/Makefile b/emufs/Makefile index 6721482..2e0dbf5 100644 --- a/emufs/Makefile +++ b/emufs/Makefile @@ -1,7 +1,7 @@ CFLAGS=-Wall -g -ansi -pedantic -DDEBUG LDFLAGS=-lm -EMUFS_COMMON=emufs.o tipo1.o tipo2.o tipo3.o idx.o did.o fsc.o common.o indices.o indice_b.o b_plus.o +EMUFS_COMMON=emufs.o tipo1.o tipo2.o tipo3.o idx.o did.o fsc.o common.o indices.o indice_b.o TARGETS=libemufs.a tipo1_main tipo2_main tipo3_main b_test @@ -13,7 +13,7 @@ tipo2_main: tipo2_main.o $(EMUFS_COMMON) tipo3_main: tipo3_main.o $(EMUFS_COMMON) -b_plus_test: b_plus_test.o $(EMUFS_COMMON) +b_plus_test: b_plus_test.o b_plus.o #b_plus_test: b_plus_test.o b_plus.o indices.o emufs.o #b_test: b_test.o indice_b.o diff --git a/emufs/b_plus.c b/emufs/b_plus.c index 052b112..92ab385 100644 --- a/emufs/b_plus.c +++ b/emufs/b_plus.c @@ -1,37 +1,31 @@ /** Arbol B+ */ #include "b_plus.h" +/* Private prototypes */ +NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node); + /** Crea un nuevo nodo y lo inicializa */ -NODO_B_PLUS emufs_b_plus_crearnodo(INDICE *idx, int es_hoja) { - - NODO_B_PLUS nodo; - int nonheader_bytes = 0; - int size_claves = 0; - int size_hijos = 0; +NODO_B_PLUS *emufs_b_plus_crearnodo(INDEXSPECS *idx, int es_hoja) { - nodo.es_hoja = es_hoja; - nodo.nivel = 0; - nodo.cant_claves = 0; + NODO_B_PLUS *nodo = (NODO_B_PLUS*)malloc(sizeof(NODO_B_PLUS)); + nodo->es_hoja = es_hoja; + nodo->nivel = 0; + nodo->cant_claves = 0; /* Calculamos lo que ocupan las cadenas de bytes claves + hijos */ - nonheader_bytes = idx->tam_bloque - sizeof(int)*3; - size_claves = (nonheader_bytes - sizeof(int))/2; - size_hijos = size_claves + sizeof(int); - nodo.claves = (int*) malloc(size_claves); - nodo.hijos = (int*) malloc(size_hijos); - memset(nodo.claves,'1',size_claves); - memset(nodo.hijos,'9',size_hijos); + nodo->claves = (int*)malloc(idx->size_claves); + nodo->hijos = (int*)malloc(idx->size_hijos); + memset(nodo->claves,-1,idx->size_claves); + memset(nodo->hijos,-1,idx->size_hijos); return nodo; } /** Crea el archivo indice B+ */ -int emufs_b_plus_crear(INDICE *idx) { +int emufs_b_plus_crear(INDEXSPECS *idx) { FILE *fp; - NODO_B_PLUS raiz; - int size_claves = (idx->tam_bloque - SIZE_B_PLUS_HEADER - sizeof(int))/2; - int size_hijos = size_claves + sizeof(int); + NODO_B_PLUS *raiz; /* Creamos el archivo que contendra el indice */ fp = fopen(idx->filename, "w"); @@ -43,15 +37,80 @@ int emufs_b_plus_crear(INDICE *idx) { } /* Creamos el nodo raiz y lo guardamos el en indice */ - raiz = emufs_b_plus_crearnodo(idx,0); - fwrite(&raiz,SIZE_B_PLUS_HEADER,1,fp); - fwrite(raiz.claves,size_claves,1,fp); - fwrite(raiz.hijos,size_hijos,1,fp); + raiz = emufs_b_plus_crearnodo(idx,1); + fwrite(raiz,SIZE_B_PLUS_HEADER,1,fp); + fwrite(raiz->claves,idx->size_claves,1,fp); + fwrite(raiz->hijos,idx->size_hijos,1,fp); fclose(fp); - /* Liberamos areas de memoria reservadas para claves e hijos */ - free(raiz.claves); - free(raiz.hijos); + /* Liberamos areas de memoria reservadas */ + free(raiz->claves); + free(raiz->hijos); + free(raiz); return 0; } + +/** Busca el nro de bloque donde se debe guardar un reg con clave X */ +int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) { + + NODO_B_PLUS *curnode; + + /* Comienzo leyendo la raiz, entry point de toda funcion */ + printf ("Buscando donde insertar clave: %i\n",query->clave.i_clave); + curnode = b_plus_leer_nodo(idx,0); + if (curnode == NULL) return -1; + + /* Mientras no encontre la hoja con la clave, busco.. */ + while ((curnode->es_hoja == 0) && curnode) + { + + } + + return 0; +} + +NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node) { + + int i = 0; + FILE *fp; + NODO_B_PLUS *memnode = (NODO_B_PLUS*)malloc(sizeof(NODO_B_PLUS)); + char *disknode = (char*)malloc(sizeof(idx->tam_bloque)); + + if (disknode == NULL) return NULL; + if (memnode == NULL) return NULL; + + /* Open up file */ + fp = fopen(idx->filename, "r"); + if (fp == NULL) { + free(disknode); + free(memnode); + return NULL; + } + + /* Intentamos leer un nodo, sino podemos error! */ + fseek(fp, num_node*idx->tam_bloque, SEEK_SET); + if (fread(disknode, idx->tam_bloque, 1, fp) != 1) { + free(disknode); + fclose(fp); + return NULL; + } + fclose(fp); + + /* Pudimos leer un nodo de disco, ahora lo transformamos a nodo mem */ + memcpy(memnode,disknode,SIZE_B_PLUS_HEADER); + memcpy(memnode->claves,disknode+SIZE_B_PLUS_HEADER,idx->size_claves); + memcpy(memnode->hijos,disknode+SIZE_B_PLUS_HEADER,idx->size_hijos); + free(disknode); + + printf("Dumping nodo leido...\n"); + printf("Nivel: %i Cant Claves: %i Es Hoja: %i\n",memnode->nivel,memnode->cant_claves,memnode->es_hoja); + printf("Claves:"); + for (i = 0; i < idx->size_claves/sizeof(int); ++i) printf(" %i",memnode->claves[i]); + printf("\nHijos:"); + for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]); + printf("\nEnd Dump\n"); + + return memnode; + +} diff --git a/emufs/b_plus.h b/emufs/b_plus.h index 6c79a6f..7442eba 100644 --- a/emufs/b_plus.h +++ b/emufs/b_plus.h @@ -9,6 +9,13 @@ /** Estructura que define un nodo B+. Para los nodos hojas, el ultimo valor de hijo, será el nro * de nodo con el que se encadena el actual. (Lista de nodos a nivel hoja. Sequence Set). */ + +typedef struct _indexspecs_ { + unsigned int tam_bloque; + unsigned int size_claves; + unsigned int size_hijos; + char *filename; +} INDEXSPECS; typedef struct _index_dat_ { EMUFS_BLOCK_ID num_bloque; @@ -25,8 +32,8 @@ typedef struct nodo_b_plus { /** TODO */ -int emufs_b_plus_crear(INDICE *idx); -int emufs_b_plus_get_bloque(INDEX_DAT *dataset); +int emufs_b_plus_crear(INDEXSPECS *idx); +int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *dataset); int emufs_b_plus_actualizar_nodo(INDEX_DAT *dataset); int emufs_b_plus_buscar(); int emufs_b_plus_destuir(); diff --git a/emufs/b_plus_test.c b/emufs/b_plus_test.c index a06eadd..226e73f 100644 --- a/emufs/b_plus_test.c +++ b/emufs/b_plus_test.c @@ -3,11 +3,22 @@ int main(int argc, char* argv[]) { +/* Locals */ +INDEX_DAT querydata; + /* Creamos un handler EMUFS, luego un Indice B+ y testing... */ -EMUFS *emu = emufs_crear("testbplus",T3,512, 128); -INDICE *indice = emufs_indice_crear(emu,"principal",0,0,0,0,sizeof(int)*12); -emufs_b_plus_crear(indice); -printf ("Yeiiiii\n"); +INDEXSPECS indice; +indice.tam_bloque = 48; +indice.size_claves = (indice.tam_bloque - SIZE_B_PLUS_HEADER - sizeof(int))/2; +indice.size_hijos = indice.size_claves + sizeof(int); +indice.filename = "idxbplus_primary.idx"; +emufs_b_plus_crear(&indice); + +/* Pedimos al arbol el nro de bloque donde guardar la clave 5. Should */ +/* return -1 pues solo esta la raiz.. */ +querydata.num_bloque = -666; +querydata.clave.i_clave = 5; +emufs_b_plus_get_bloque(&indice,&querydata); return 0; -- 2.43.0