From 3cdaf72a1a9cb3adc65b441f56751b2e4eb90f1d Mon Sep 17 00:00:00 2001 From: =?utf8?q?Nicol=C3=A1s=20Dimov?= Date: Sat, 22 May 2004 06:25:17 +0000 Subject: [PATCH] Libero bien la memoria. Una clave que entra en un nodo sin problemas se inserta ordenada dentro del nodo. --- emufs/b_plus.c | 143 ++++++++++++++++++++++++++++++++----------------- emufs/b_plus.h | 6 --- 2 files changed, 94 insertions(+), 55 deletions(-) diff --git a/emufs/b_plus.c b/emufs/b_plus.c index 1aa1664..1c1c083 100644 --- a/emufs/b_plus.c +++ b/emufs/b_plus.c @@ -1,20 +1,15 @@ /** Arbol B+ */ #include "b_plus.h" -/* Private prototypes */ +/**#*#*#*#*#**#*#*#*#*#* Private prototypes*#*#*#*#*#**#*#*#*#*#**#*#*#*/ /* numerando los bloques */ -static int nuevo_bloque = -1; -int get_new_block_number(); int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node); NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node); NODO_B_PLUS *b_plus_crearnodo(INDEXSPECS *idx); +int b_plus_destruir_nodo(NODO_B_PLUS *nodo); +int b_plus_insertar_clave(INDEXSPECS *idx, INDEX_DAT *query); -/** Me devuelve un numero de bloque nuevo */ -int get_new_block_number() -{ - nuevo_bloque++; - return nuevo_bloque; -} +/**#*#*#*#*#**#*#*#*#*#*FIN PROTOTYPES*#*#*#*#*#**#*#*#*#*#**#*#*#*#*#*/ /** Crea un nuevo nodo y lo inicializa */ NODO_B_PLUS *b_plus_crearnodo(INDEXSPECS *idx) { @@ -61,13 +56,74 @@ int emufs_b_plus_crear(INDEXSPECS *idx) { return error; } -/* Inserta un nuevo nodo y reestructura el arbol para que quede como debe */ -int b_plus_actualizar(NODO_B_PLUS *padre, NODO_B_PLUS *new_nodo) +/* Inserta una nueva clave y reestructura el arbol para que quede como debe */ +int b_plus_insertar_clave(INDEXSPECS *idx, INDEX_DAT *query) { + NODO_B_PLUS *curnode, *padre, *new_nodo; + int i,j, prox_nodo; + /* Comienzo leyendo la raiz, entry point de toda funcion */ + curnode = b_plus_leer_nodo(idx,0); + if (curnode == NULL) return -1; + padre = curnode; + while ( curnode->nivel > 0 && curnode ) { + for(i=0; icant_claves; i++){ + /* me fijo que si es mayor */ + if ( (query->clave.i_clave > curnode->claves[i])) { + if ( curnode->cant_claves != i ) /* si no es la ultima clave del nodo */ + continue; /*paso a la siguiente*/ + else { /* si era la ultima, la clave deberia ir ahi */ + /*cargo el proximo nodo*/ + prox_nodo = curnode->hijos[i+1]; + break; /*salgo del for*/ + } + } else { /*si no es mayor o igual es menor*/ + prox_nodo = curnode->hijos[i]; + break; + } + } + padre = curnode; + curnode = b_plus_leer_nodo(idx, prox_nodo); + } + /* aca tengo el nodo donde deberia ir la clave, y su padre */ + + if ( curnode->cant_claves < idx->size_claves ){ + int *claves_aux = (int*)malloc(idx->size_claves); + int *hijos_aux = (int*)malloc(idx->size_hijos); + i = 0; + while ( (curnode->claves[i] < query->clave.i_clave) && (i < curnode->cant_claves)){ + claves_aux[i] = curnode->claves[i]; + hijos_aux[i] = curnode->hijos[i]; + i++; + } + curnode->cant_claves++; + claves_aux[i] = query->clave.i_clave; + hijos_aux[i] = query->num_bloque; + for (j=i+1; jcant_claves; j++){ + claves_aux[j] = curnode->claves[j-1]; + hijos_aux[j] = curnode->hijos[j-1]; + } + free(curnode->claves); + free(curnode->hijos); + curnode->claves = claves_aux; + curnode->hijos = hijos_aux; + b_plus_grabar_nodo(idx, curnode, prox_nodo); + b_plus_destruir_nodo(curnode); + } + + + + /* si el nodo esta lleno tengo que splitear */ + if ( curnode->cant_claves == idx->size_claves ) + { + /**FIXME**/ + } return 0; } /** Busca el nro de bloque donde se debe guardar un reg con clave X */ +/** Si la clave entra en la raiz, la guarda, si no, busca el nodo hoja + donde debe ir y devuelve el bloque (en query) pero no graba la clave */ +/** Devuelve -1 si no hay un bloque donde insertar la nueva clave */ int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) { NODO_B_PLUS *curnode; @@ -83,24 +139,21 @@ int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) { curnode->cant_claves++; /* inserto la clave en el nodo, como es la primera no hace falta ordenar nada*/ *(curnode->claves) = query->clave.i_clave; - /* Debo obtener un numero de bloque para devolverle al query!!! */ - /* por ahora el nuevo bloque se va incrementando, sin recuperacion de vacios FIX*/ - query->num_bloque = get_new_block_number(); - /* Le asigno al nodo del arbol el mismo numero que devolvi */ + /* En query->num_bloque viene un numero de bloque nuevo valido..*/ + /* Le asigno al nodo del arbol el mismo numero que venia en query*/ *(curnode->hijos) = query->num_bloque; - /* Cargado el query salgo de la func, luego habra que actualizar el .dat - y luego volver a grabar el nodo en el arbol*/ + /* Cargado el query salgo de la func, luego habra que actualizar el .dat */ /*grabo el nodo en el archivo*/ b_plus_grabar_nodo(idx, curnode, 0); /* librero el nodo */ - free(curnode); + b_plus_destruir_nodo(curnode); return 0; } /* Mientras no encontre la hoja con la clave, busco.. */ /* RECORDAR QUE LAS CLAVES DEBEN ESTAR ORDENADAS PARA QUE ESTO FUNCIONE !! */ - while (curnode->nivel > 0 && curnode) - { /*recorro las claves hasta encontrar la primera mayor a la que quiero insertar*/ + while (curnode->nivel > 0 && curnode){ + /*recorro las claves hasta encontrar la primera mayor a la que quiero insertar*/ for(i=0; icant_claves; i++){ /* me fijo que si es mayor */ if ( (query->clave.i_clave > curnode->claves[i])) { @@ -116,7 +169,7 @@ int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) { break; } } - free(curnode); + b_plus_destruir_nodo(curnode); curnode = b_plus_leer_nodo(idx, prox_nodo); } @@ -126,42 +179,31 @@ int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) { if ( curnode->cant_claves != i ) /* si no es la ultima clave */ continue; else { /* si era la ultima */ - /* cargo en query el numero del bloque donde deberia ir la nueva clave */ + /* Cargo en query el numero del bloque donde deberia ir la nueva clave */ query->num_bloque = curnode->hijos[i]; - free(curnode); + b_plus_destruir_nodo(curnode); return 0; } } else { /* si no era mayor, era menor */ - /* guardo el bloque anterior porque me pase.. */ if ( i == 0 ){ - /*CREAR UN NODO NUEVO PARA METER UNA CLAVE MENOR A TODAS */ - /* EL NUEVO NODO VA A SER UNA HOJA */ - NODO_B_PLUS *new_nodo = b_plus_crearnodo(idx); - if (new_nodo == NULL){ - PERR("NO SE PUDO CREAR EL NUEVO NODO"); - return -1; - } - /* aumento la cantidad de claves */ - new_nodo->cant_claves++; - /* inserto la clave en el nuevo nodo (es la primera)*/ - new_nodo->claves[0] = query->clave.i_clave; - /* inserto la referencia al nuevo bloque, con un n */ - new_nodo->hijos[0] = query->num_nuevo_bloque; - /* no le cambio el nivel porque es hoja ( por default == 0)*/ - /* Aca viene la papota.. hay que hacer una funcion que meta un nodo - * en el arbol y lo reestructure correctamente. - * Ademas hay que grabar el registro en el .dat*/ - b_plus_actualizar(curnode, new_nodo); /* le mando el padre.. seguro que lo voy a necesitar */ - return 0; + + /* ACA PODRIAMOS RETORNAR -1 COMO CODIGO DE ERROR QUE INFORMARIA QUE NO EXISTE + UN NODO DONDE QUEPA LA CLAVE, ENTONCES HABRIA QUE LLAMAR A LA FUNCION QUE + ACTUALIZA EL ARBOL Y SE ENCARGA DE ARGREGAR LA CLAVE Y HACER EL SPLIT DE SER + NECESARIO */ + /* Llamo a la funcion que mete una clave nueva en el arbol y le paso el bloque a donde + tiene que apuntar */ + b_plus_insertar_clave(idx, query); + return 1; /* SE INSERTO NODO NUEVO */ } else { query->num_bloque = curnode->hijos[i-1]; - free(curnode); + b_plus_destruir_nodo(curnode); return 0; } } } - if (curnode) free(curnode); + if (curnode) b_plus_destruir_nodo(curnode); return 0; } @@ -178,15 +220,15 @@ NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node) { /* Open up file */ fp = fopen(idx->filename, "r+"); if (fp == NULL) { - free(disknode); - free(memnode); + free(disknode); + b_plus_destruir_nodo(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); + free(disknode); fclose(fp); return NULL; } @@ -226,7 +268,10 @@ int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node) return 0; } -int emufs_b_plus_insertar_clave(INDEX_DAT *dataset) +int b_plus_destruir_nodo(NODO_B_PLUS *nodo) { + free(nodo->claves); + free(nodo->hijos); + free(nodo); return 0; } diff --git a/emufs/b_plus.h b/emufs/b_plus.h index 838fd97..51041e0 100644 --- a/emufs/b_plus.h +++ b/emufs/b_plus.h @@ -35,12 +35,6 @@ typedef struct nodo_b_plus { 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); - -/** inserta una clave en el arbol y devuelve en dataset->num_bloque el - bloque donde se insertara en el .dat*/ -int emufs_b_plus_insertar_clave(INDEX_DAT *dataset); - - int emufs_b_plus_buscar(); int emufs_b_plus_destuir(); -- 2.43.0