Venga, a ver si te sirve esto 8) Suerte!
[code]
#define LLENO 3
/****************************************************************
* TIPOS DE DATOS
*************************************************************/
typedef struct tag_clave
{
/* Datos del registro que estamos indexando, el offset que
tiene en la bd original, el tamaño en bytes de la clave
y un puntero a los bytes de dicha clave */
long offset;
int tam_clave;
void *clave;
}CLAVE;
typedef struct tag_pagina
{
/* Datos de una pagina */
int contador_claves; /* Numero de claves que tiene la pagina, max orden-1 */
int numero_pag; /* El numero de la pagina dentro de la bd, no es demasiado util */
long offset; /* el offset de la pagina en la bd */
long padre; /* el offset del padre de esta pagina en la bd, -1 si no hay (raiz) */
long *hijos; /* array de longs que contiene los hijos de esta pagina. Si es una
pagina hija lo sabremos porque hijos[0] sera -1*/
/* Array con los punteros a las claves de la pagina */
CLAVE **claves;
}PAGINA;
/****************************************
Crea_ArbolB
Descripcion:
Crea una base de datos de indices de arbolb con un orden y un tamano
maximo de clave dado (ya que utiliza registros de tamano fijo).
Entradas:
**bdarbol: puntero a una estructura de tipo BDFichero previamente localizada
que contendra la informacion del arbolb
*farbolb: nombre del fichero en el que se guardara la bd
*orden: orden (numero maximo de ramas) del arbolb a usar
tam_clave: tamano maximo de las claves que contendra el arbol
*funcmp: funcion de comparacion a usar
Salidas:
codigo de error
Notas:
****************************************/
int Crea_ArbolB( BDFichero **bdarbol, char *farbolb, int orden, int tam_clave, void *funcmp)
{
BDFichero *arbol=NULL;
int i=0;
PAGINA *pagina_arbol=NULL;
/*
Calculamos el tamano del registro mas grande que crearemos, sumando:
el tamano base de una pagina, el tamano del array con todos los offsets de las claves,
el tamano del array de las claves y el tamano del array con los offsets de los hijos.
y le anadimos 2 bytes del indicador de estado del registro */
int max_tam=sizeof(PAGINA) + ( (orden-1) * sizeof(CLAVE)) + ((orden-1) * tam_clave) + \
( orden * sizeof(long)) + 2;
/* CdE */
if ( bdarbol == NULL || farbolb == NULL )
{
printf("Error en los parametros de Crea_ArbolB\n");
return ERR;
}
/* Creamos una pagina inicial vacia para hacer la raiz */
if ( Crea_Pagina(&pagina_arbol, orden,-1) == ERR )
{
printf("Error creando pagina vacia en Crea_ArbolB\n");
if ( pagina_arbol ) Libera_Pagina(pagina_arbol, orden);
return ERR;
}
arbol=BDCrea(farbolb, BD_FIJO, max_tam);
/* Inicializamos los tamaños de la bd de indices arbolb */
memcpy ((arbol->pCabecera)->sRelleno, &max_tam, 4);
i = arbol->lPosicionActual;
memcpy (&((arbol->pCabecera)->sRelleno[4]), &i, 4);
i = orden;
memcpy (&(arbol->pCabecera->sRelleno[8]), &i, 4);
/* Escribimos la direccion de la funcion de comparacion a usar en la cabecera */
/* Esperemos que esto funcione.......................................... */
memcpy (&(arbol->pCabecera->sRelleno[12]), funcmp, sizeof(void*));
i = 0;
memcpy (&(arbol->pCabecera->sRelleno[16]), &i, sizeof(int));
if ( BDEscribe_Pagina(arbol, pagina_arbol, -1) == ERR )
{
printf("Error insertando pagina vacia en Crea_ArbolB\n");
if ( pagina_arbol != NULL ) free(pagina_arbol);
return ERR;
}
Libera_Pagina(pagina_arbol, orden);
/* marcamos que hemos actualizado el arbol*/
(arbol->pCabecera)->sRelleno[217]='$';
(arbol->pCabecera)->sRelleno[216]='$';
(arbol->pCabecera)->sRelleno[215]='$';
if ( BDCierra(arbol)==ERR )
printf("Error cerrando la bd creada en crea_arbolb\n");
if ( Abrir_BaseD( bdarbol, farbolb)==ERR)
{
printf("Error reabriendo la bd recien creada, debio de haber error creandola\n");
return ERR;
}
return OK;
}
/****************************************
BDEscribe_Pagina
Descripcion:
Escribe una pagina dada en una posicion dada
Entradas:
*bdarbol: base de datos de un indice tipo arbolb a usar
*pag: pagina previamente localizada y rellenada (o actualizada) a insertar (o modificar)
posicion: offset en el archivo en el cual escribir el registro
Salidas:
codigo de error
Notas:
Si la posicion es -1, inserta la pagina en la bd como si fuera nueva
(aprovechando los posibles huecos)
****************************************/
int BDEscribe_Pagina( BDFichero *bdarbol, PAGINA *pag, long posicion)
{
int tamano=0, i=0;
void *aux=NULL;
int orden=0;
unsigned short int no_vacio=1;
if ( bdarbol == NULL || pag == NULL )
{
printf("Error en los parametros de BDEscribe_Pagina\n");
return ERR;
}
if ( bdarbol->pCabecera->iTipoBD != BD_FIJO )
{
printf("Tipo de bd erronea, solo usamos BD_FIJO\n");
return ERR;
}
memcpy( &orden, &(bdarbol->pCabecera->sRelleno[8]), sizeof(int));
/* Comprobamos que el tamanoo de la bd sea adecuado */
memcpy(&tamano, bdarbol->pCabecera->sRelleno, sizeof(int));
if ( tamano < sizeof(PAGINA) )
{
printf("Error, el tamano de los registros de la bd es menor que el de la pagina\n");
return ERR;
}
aux=bdarbol->pRegistroActual;
/* Anadimos dos bytes indicando que el registro NO esta vacio */
memcpy(bdarbol->pRegistroActual, &no_vacio, 2);
bdarbol->pRegistroActual=bdarbol->pRegistroActual+2;
/* Añadimos el numero de claves en la pagina */
memcpy(bdarbol->pRegistroActual, &(pag->contador_claves), sizeof(int));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(int);
/* Añadimos el numero de pagina */
if ( pag->numero_pag == -1 )
{
/* Si se paso una pagina nueva, le ponemos el ultimo numero de pagina disponible */
memcpy( &i, &(bdarbol->pCabecera->sRelleno[16]), sizeof(int));
memcpy( &(pag->numero_pag), &i, sizeof(int));
i++;
memcpy( &(bdarbol->pCabecera->sRelleno[16]), &i, sizeof(int));
}
memcpy(bdarbol->pRegistroActual, &(pag->numero_pag), sizeof(int));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(int);
/* Añadimos la posicion del padre */
memcpy(bdarbol->pRegistroActual, &(pag->padre), sizeof(long));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(long);
/* Anadimos la posicion de la pagina */
if ( posicion > -1 ) memcpy(bdarbol->pRegistroActual, &posicion, sizeof(long));
else memcpy(bdarbol->pRegistroActual, &(pag->offset), sizeof(long));
bdarbol->pRegistroActual+=sizeof(long);
/* Escribimos todos los offsets de los hijos (esten vacios o no ) */
memcpy(bdarbol->pRegistroActual, pag->hijos, sizeof(long)*orden);
bdarbol->pRegistroActual=bdarbol->pRegistroActual+(sizeof(long)*orden);
/* Escribimos las claves contenidas en la pagina */
for( i = 0; i < pag->contador_claves; i++)
{
if ( pag->claves == NULL )
{
printf("Pagina corrupta en BDEscribe_Pagina\n");
return ERR;
}
memcpy(bdarbol->pRegistroActual, &(((CLAVE*)pag->claves[i])->offset), sizeof(long));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(long);
memcpy(bdarbol->pRegistroActual, &(((CLAVE*)pag->claves[i])->tam_clave), sizeof(int));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(int);
memcpy(bdarbol->pRegistroActual, ((CLAVE*)pag->claves[i])->clave, ((CLAVE*)pag->claves[i])->tam_clave);
bdarbol->pRegistroActual=bdarbol->pRegistroActual+((CLAVE*)pag->claves[i])->tam_clave;
}
bdarbol->pRegistroActual=aux;
if ( posicion == -1 )
{
if( BDAniadeRegistro(bdarbol)==ERR )
{
printf("Error al escribir pagina como un nuevo registro en BDEscribe_Pagina\n");
return ERR;
}
/* Tenemos que averiguar el offset en el que se guardo la pagina! */
aux=bdarbol->pRegistroActual;
pag->offset = bdarbol->lPosicionActual-tamano;
bdarbol->lPosicionActual -= tamano;
bdarbol->pRegistroActual = bdarbol->pRegistroActual + ( 2 + (sizeof(int)*2)+sizeof(long));
memcpy(bdarbol->pRegistroActual, &(pag->offset), sizeof(long));
bdarbol->pRegistroActual = aux;
if ( BDPonte(bdarbol, bdarbol->lPosicionActual, 0)==ERR)
{
printf("Error posicionando en BDEscribe_Pagina\n");
return ERR;
}
if( BDEscribeRegistro(bdarbol) == ERR )
{
printf("Error escribiendo registro en la posicion indicada en BDEscribe_Pagina\n");
return ERR;
}
}
else if ( posicion > -1 )
{
bdarbol->lPosicionActual = posicion;
if ( BDPonte(bdarbol, bdarbol->lPosicionActual, 0)==ERR)
{
printf("Error posicionando en BDEscribe_Pagina\n");
return ERR;
}
if( BDEscribeRegistro(bdarbol) == ERR )
{
printf("Error escribiendo registro en la posicion indicada en BDEscribe_Pagina\n");
return ERR;
}
/* Nos quedamos donde hayamos terminado de escribir (el siguiente registro ) */
/* bdarbol->lPosicionActual = aux; */
}
return OK;
}
/****************************************
BDLee_Pagina
Descripcion:
Lee una pagina desde una posicion dada
Entradas:
*bdarbol: base de datos de un indice tipo arbolb a usar
*pag: pagina previamente localizada en la que leer los datos del registro de la bd
posicion: offset en el archivo desde el cual leer la pagina
Salidas:
codigo de error
Notas:
Devuelve vacio si el registro no contenia informacion
****************************************/
int BDLee_Pagina ( BDFichero *bdarbol, PAGINA *pag, long posicion)
{
int estado=ERR, i=0;
void *aux=NULL;
int orden=0;
long pos=0;
if ( bdarbol == NULL || pag == NULL )
{
printf("Error en los parametros de BDLee_Pagina\n");
return ERR;
}
if ( bdarbol->pCabecera->iTipoBD != BD_FIJO )
{
printf("Tipo de bd erronea, solo usamos BD_FIJO\n");
return ERR;
}
if ( posicion < (sizeof(BDCabecera)-1))
{
printf("Error en los parametros de BDLee_Pagina\n");
return ERR;
}
memcpy( &orden, &(bdarbol->pCabecera->sRelleno[8]), sizeof(int));
pos = bdarbol->lPosicionActual;
aux=bdarbol->pRegistroActual;
if ( BDPonte(bdarbol, posicion ,0)==ERR)
{
printf("Error posicionando la bd en BDLee_Pagina\n");
return ERR;
}
estado = BDLeeRegistro( bdarbol );
if ( estado == ERR )
{
printf("No se pudo leer el registro de la pagina en BDLee_Pagina\n");
BDPonte(bdarbol,pos,0);
return ERR;
}
else if ( estado == VACIO )
return VACIO;
/* Saltamos el indicador de registro no vacio */
bdarbol->pRegistroActual+=2;
/* Leemos el numero de claves en la pagina */
memcpy(&(pag->contador_claves),bdarbol->pRegistroActual, sizeof(int));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(int);
/* Leemos el numero de pagina */
memcpy(&(pag->numero_pag), bdarbol->pRegistroActual, sizeof(int));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(int);
/* Leemos la posicion del padre */
memcpy(&(pag->padre), bdarbol->pRegistroActual, sizeof(long));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(long);
/* Leemos la posicion de la pagina */
memcpy(&(pag->offset), bdarbol->pRegistroActual, sizeof(long));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(long);
/* Leemos todos los offsets de los hijos (esten vacios o no ) */
memcpy(pag->hijos, bdarbol->pRegistroActual,sizeof(long)*orden);
bdarbol->pRegistroActual=bdarbol->pRegistroActual+(sizeof(long)*orden);
/* Leemos el array de punteros a clave */
/*
memcpy(pag->claves, bdarbol->pRegistroActual, sizeof(CLAVE*)*(orden-1));
bdarbol->pRegistroActual+=sizeof(CLAVE*)*(orden-1);
*/
/* Leemos las claves contenidas en la pagina */
for( i = 0; i < pag->contador_claves; i++)
{
if ( pag->claves == NULL )
{
printf("Pagina corrupta en BDEscribe_Pagina\n");
return ERR;
}
if ( ( pag->claves[i] = (CLAVE*) calloc( 1, sizeof(CLAVE)))==NULL)
{
printf("Error localizando espacio para la clave en BDLee_Pagina\n");
BDPonte(bdarbol,pos, 0);
return ERR;
}
memcpy(&(((CLAVE*)pag->claves[i])->offset), bdarbol->pRegistroActual,sizeof(long));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(long);
memcpy(&(((CLAVE*)pag->claves[i])->tam_clave), bdarbol->pRegistroActual, sizeof(int));
bdarbol->pRegistroActual=bdarbol->pRegistroActual+sizeof(int);
if ( ( ((CLAVE*)pag->claves[i])->clave = (void*) malloc(((CLAVE*)pag->claves[i])->tam_clave))==NULL)
{
printf("Error reservando memoria para clave en BDLee_Pagina\n");
BDPonte(bdarbol,pos,0);
return ERR;
}
memcpy(((CLAVE*)pag->claves[i])->clave, bdarbol->pRegistroActual, ((CLAVE*)pag->claves[i])->tam_clave);
bdarbol->pRegistroActual=bdarbol->pRegistroActual+((CLAVE*)pag->claves[i])->tam_clave;
}
bdarbol->pRegistroActual=aux;
return OK;
}
/****************************************
BDBorra_Pagina
Descripcion:
Borra una pagina dada de la bd en disco
Entradas:
*bdarbol: puntero a una bd de un arbol binario
posicion: posicion de la pagina en la bd
num_pag: numero de la pagina en la bd
Salidas:
codigo de error
Notas:
Borramos o por posicion o por numero de pagina
****************************************/
int BDBorra_Pagina( BDFichero *bdarbol, long posicion, int num_pag)
{
long pos=0;
/* CdE */
if ( bdarbol == NULL || ( posicion < 0 && num_pag < 0 ))
{
printf("Error en los parametros en BDBorra_Pagina\n");
return ERR;
}
if ( num_pag > -1 ) pos = Busca_Sec_Pagina( bdarbol, num_pag );
else pos = posicion;
if ( pos == -1 )
{
printf("No se pudo hallar la posicion de la pagina a borrar en BDBorra_Pagina\n");
return ERR;
}
if ( BDPonte(bdarbol, pos, 0) == ERR )
{
printf("Error posicionando bd en BDBorra_Pagina\n");
return ERR;
}
if ( BDBorraRegistro(bdarbol)== ERR )
{
printf("Error borrando registro en BDBorra_Pagina\n");
return ERR;
}
return OK;
}
/****************************************
Inserta_Clave
Descripcion:
Inserta una clave dada en el arbol
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*clave: puntero a una clave a insertar previamente creada
Salidas:
codigo de error
Notas:
Siempre que vengamos de una promocion, nodo contiene al padre donde
queremos promocionar al valor medio contenido en nuevo
****************************************/
int Inserta_Clave( BDFichero *bdarbol, CLAVE *clave)
{
int indice_clave=0, indice_posible=0, hecho=0;
int orden=0;
long posicion=0;
PAGINA *nodo=NULL, *nuevo=NULL, *padre=NULL;
/* CdE */
if ( bdarbol == NULL || clave == NULL )
{
printf("Error en los parametros de Inserta_Clave\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]),sizeof(int));
if ( orden < 1 )
{
printf("Error en la bd del indice arboreo\n");
return ERR;
}
/* Buscamos la clave en el arbol, para descartar repeticiones */
if ( Busca_Clave(bdarbol, &nodo, clave->clave, 0, -1, &indice_posible, &indice_clave, 0)== ERR )
{
printf("Error buscando clave en el arbol en Inserta_Clave\n");
return ERR;
}
if ( indice_clave > -1 )
{
printf("Intento de insercion de clave presente\n");
free ( clave->clave);
free( clave );
return ERR;
}
if ( indice_posible == -1 )
{
printf("BD erronea u otro error en Inserta_Clave\n");
return ERR;
}
while ( hecho == 0 )
{
/* Hay hueco en la pagina destino */
if ( nodo->contador_claves < (orden-1) )
{
/* Comprobamos si es una hoja */
if ( nodo->hijos[0] == -1 )
{
if ( Inserta_Clave_No_Lleno(bdarbol, indice_posible, &nodo, clave)==ERR)
{
printf("Error insertando la clave en una pagina no llena\n");
if ( nodo ) Libera_Pagina(nodo, orden);
return ERR;
}
if (nodo) Libera_Pagina(nodo, orden);
nodo = NULL;
return OK;
}
else if ( nuevo )
{
/* Venimos de una promocion, y hay espacio;
unimos la pagina promocionada a la pagina padre
*/
padre = NULL;
if ( Mete_Clave(&nodo,-1, nuevo, 0, NULL, NULL, orden)==ERR)
{
printf("Error insertando promocion en pagina con hueco en Inserta_Clave\n");
return ERR;
}
if ( BDEscribe_Pagina( bdarbol, nodo, nodo->offset)==ERR)
{
printf("Error escribiendo promocion final en Inserta_Clave\n");
return ERR;
}
if ( nodo ) Libera_Pagina(nodo, orden);
hecho = 1;
}
else
{
printf("Insercion fuera de hoja en Inserta_Clave\n");
hecho = 1;
}
}
/* La pagina esta llena, tendremos que redistribuir o promocionar */
else
{
/* Insercion mas alla de la raiz */
if ( nodo->padre == -1 )
{
/* Hemos promocionado hasta la raiz, insertamos y escribimos */
if ( nuevo )
{
/* Insertamos la pagina promocionada antes de partir
la raiz */
if ( Mete_Clave(&nodo,-1, nuevo, 0, NULL, NULL, orden+1)==ERR)
{
printf("Error insertando promocion en pagina sin hueco en Inserta_Clave\n");
return ERR;
}
/* Ya hemos insertado la clave, no la volvemos a insertar */
indice_posible = -1;
orden++;
}
memcpy(&posicion, &(bdarbol->pCabecera->sRelleno[4]), 4);
if ( Partir_Y_Guardar(bdarbol, nodo, &nuevo, indice_posible, orden, clave, posicion, 0)==ERR)
{
printf("No funciono Partir_Y_Guardar en Inserta_Clave\n");
return ERR;
}
if ( BDEscribe_Pagina( bdarbol, nuevo, posicion ) == ERR )
{
printf("Error escribiendo nueva raiz en Inserta_Clave\n");
return ERR;
}
hecho = 1;
}
else
{
/* Obtenemos al padre, para averiguar si hay espacio para redistribuir */
if ( Crea_Pagina(&padre, orden, -1) ==ERR)
{
printf("Error creando pagina nueva para el padre en Inserta_Clave\n");
return ERR;
}
if ( BDLee_Pagina(bdarbol, padre, nodo->padre)==ERR)
{
printf("Error obteniendo al nodo padre en Inserta_Clave\n");
return ERR;
}
/* Estamos en una insercion en nodo hoja, intentamos
redistribuir */
if ( nodo->hijos[0] == -1 )
{
if ( Redistribuir(bdarbol , &padre, &nodo, clave, &indice_posible, &hecho)==OK)
{
continue;
}
/* Si habia que insertar en los extremos, redistribuimos con la clave y ya hemos terminado */
else hecho = 0;
}
/* Venimos de una promocion, y donde promocionamos esta lleno */
if ( nuevo != NULL && nodo->hijos[0] != 1)
{
/* Insertamos el promocionado en una pagina de tam orden*/
orden++;
if ( Mete_Clave(&nodo,-1, nuevo, 0, NULL, NULL, orden)==ERR)
{
printf("Error insertando promocion en pagina sin hueco en Inserta_Clave\n");
return ERR;
}
indice_posible = -1;
}
else if ( nuevo != NULL )
{
printf("Error, no podemos estar promocionando en una hoja\n");
return ERR;
}
if ( Partir_Y_Guardar(bdarbol, nodo, &nuevo, indice_posible, orden,clave, padre->offset,-1) == ERR )
{
printf("No funciono Partir_Y_Guardar en Inserta_Clave\n");
return ERR;
}
/* Recuperamos el valor de orden ya que puede haber cambiado
al hacer un partir sobre una tabla orden+1 */
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]),sizeof(int));
/* Borramos nodo para que nos deje un hueco */
if ( BDBorra_Pagina( bdarbol, nodo->offset, -1)==ERR)
{
printf("Error borrando nodo en Inserta_Clave\n");
return ERR;
}
/* Ahora la pagina destino (nodo) es la actual padre */
if ( nodo ) Libera_Pagina(nodo, orden);
nodo = padre;
/* Volvemos al bucle para continuar con la promocion */
}
}
}
if ( padre ) Libera_Pagina( padre,orden );
padre = NULL;
return OK;
}
/****************************************
Inserta_Clave_No_Lleno
Descripcion:
Inserta una clave dada en una pagina (no llena) dada
Entradas:
*bdarbol: puntero a una bd de un arbol binario
indice_posible: indice en el cual poner la clave
nodo: la pagina en la cual insertar
*clave: puntero a una clave a insertar previamente creada
Salidas:
codigo de error
Notas:
La posicion de la bd debe de ser la misma que desde la lectura de nodo, es decir,
la del registro siguiente a nodo
Libera la memoria de nodo
****************************************/
int Inserta_Clave_No_Lleno(BDFichero *bdarbol, int indice_posible, PAGINA **nodo, CLAVE *clave)
{
int orden=0;
/* CdE */
if ( bdarbol == NULL || clave == NULL )
{
printf("Error en los parametros de Inserta_Clave\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]),sizeof(int));
if ( orden < 1 )
{
printf("Error en la bd del indice arboreo\n");
return ERR;
}
if ( Mete_Clave( nodo, indice_posible, NULL, -1, clave, NULL, orden )==ERR)
{
printf("Error metiendo clave en Inserta_Clave_No_Lleno\n");
return ERR;
}
/* Guardamos la pagina despues de modificarla */
if ( BDEscribe_Pagina(bdarbol, (*nodo), (*nodo)->offset)==ERR)
{
printf("Error escribiendo la pagina a insertar en Inserta_Clave_No_Lleno\n");
return ERR;
}
return OK;
}
/****************************************
Redistribuir
Descripcion:
Funcion de redistribucion. Redistribuye los elementos de
las paginas dst y src segun sea insercion o borrado
en donde vayamos a insertar a paginas (no llenas) adyacentes
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*padre: puntero al padre desde el cual redistribuir
offset: offset de la pagina desde la cual se pide la redistribucion
*clave: Si esta presente, significa que estamos insertando esta clave,
sino es que se trata de una operacion de borrado
Salidas:
codigo de error
Notas:
****************************************/
int Redistribuir(BDFichero *bdarbol , PAGINA **padre, PAGINA **nodo, CLAVE *clave, int *indice_posible, int *hecho)
{
int i=0, orden=0, elegido=0,b=0;
PAGINA *izq=NULL, *der=NULL, *dst=NULL, *src=NULL;
CLAVE *temp=NULL;
int posi_clave_en_padre=0, posi_clave_dst=0, posi_clave_src=0,posi_clave_extremo=0;
/* CdE */
if ( bdarbol == NULL || padre == NULL || nodo == NULL )
{
printf("Parametros erroneos en Redistribuir\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]),4);
if ( Lee_Der_Izq(bdarbol, (*padre), (*nodo)->offset, &der, &izq, &i)==ERR)
{
printf("Error leyendo las paginas hermanas\n");
return ERR;
}
if ( ( temp = calloc(1, sizeof(CLAVE)))==NULL)
{
printf("Error localizando clave temporal en Redistribuir\n");
return ERR;
}
if ( Crea_Pagina( &src, orden, -1 ) == ERR )
{
printf("Error creando pagina inicializada en Redistribuir\n");
return ERR;
}
if ( Crea_Pagina( &dst, orden, -1 ) == ERR )
{
printf("Error creando pagina inicializada en Redistribuir\n");
return ERR;
}
if ( izq )
{
if ( clave && izq->contador_claves < (orden-1) )
{
elegido = 1;
BDLee_Pagina(bdarbol, dst, izq->offset);
Libera_Pagina(izq, orden);
BDLee_Pagina(bdarbol, src, (*nodo)->offset);
posi_clave_dst = dst->contador_claves;
posi_clave_extremo = 0;
posi_clave_en_padre = i-1;
posi_clave_src = 0;
}
else if ( clave == NULL && izq->contador_claves > floor(orden/2) )
{
elegido = 3;
BDLee_Pagina(bdarbol, dst, (*nodo)->offset);
BDLee_Pagina(bdarbol, src, izq->offset);
Libera_Pagina(izq, orden);
posi_clave_src = src->contador_claves-1;
posi_clave_dst = 0;
posi_clave_extremo = -1;
posi_clave_en_padre = i-1;
*indice_posible = -2;
}
}
if ( der && elegido == 0 )
{
if ( clave && der->contador_claves < (orden-1) )
{
elegido = 2;
BDLee_Pagina(bdarbol, dst, der->offset);
BDLee_Pagina(bdarbol, src, (*nodo)->offset);
Libera_Pagina(der, orden);
posi_clave_dst = 0;
posi_clave_extremo = orden-1;
posi_clave_en_padre = i;
posi_clave_src = (*nodo)->contador_claves-1;
}
else if ( !clave && der->contador_claves > floor(orden/2) )
{
elegido = 4;
BDLee_Pagina(bdarbol, dst, (*nodo)->offset);
BDLee_Pagina(bdarbol, src, der->offset);
Libera_Pagina(der, orden);
posi_clave_src = 0;
posi_clave_dst = dst->contador_claves;
posi_clave_extremo = -1;
posi_clave_en_padre = i;
*indice_posible = -2;
}
else return LLENO;
}
if ( elegido == 0 ) return LLENO;
/* Si el indice_posible se tiene que insertar en un extremo, pasamos la clave al padre para redistribuir */
if ( *indice_posible == posi_clave_extremo )
{
if ( Mete_Clave( padre , posi_clave_en_padre, NULL, -1, clave, &temp,orden)==ERR)
{
printf("Error reemplazando clave en Redistribuir\n");
return ERR;
}
*hecho = 1;
}
/* Pasamos el elemento menor de nodo a la posicion de la clave correspondiente en padre */
else
{
if ( Mete_Clave( padre, posi_clave_en_padre, src, posi_clave_src, NULL, &temp,orden)==ERR)
{
printf("Error reemplazando clave en Redistribuir\n");
return ERR;
}
/* Estamos redistribuyendo entre paginas padres, redistribuimos los hijos */
if ( src->hijos[0] != -1 )
{
if ( posi_clave_dst == 0 )
{
/* Movemos los hijos una posicion a la derecha */
b = dst->contador_claves+1;
while ( b>0 )
{
if ( dst->hijos[b]==-1 && dst->hijos[b-1] != -1)
{
dst->hijos[b] = dst->hijos[b-1];
dst->hijos[b-1] = -1;
}
b--;
}
}
if ( posi_clave_dst == 0 )
dst->hijos[posi_clave_dst] = src->hijos[posi_clave_src+1];
else dst->hijos[posi_clave_dst] = src->hijos[posi_clave_src+1];
}
if ( Elimina_Clave( &src, posi_clave_src, orden)==ERR)
{
printf("Error eliminando clave en Redistribuir\n");
return ERR;
}
if ( posi_clave_dst == 0) src->hijos[posi_clave_src+1] = -1;
/* si estamos borrando, guardamos los cambios a la pagina fuente ya */
if ( clave )
{
/* Decrementamos el indice_posible, ya que ahora los elementos se
han movido una posicion hacia abajo */
if ( elegido == 1) *indice_posible = *indice_posible - 1;
if ( Mete_Clave( &src, *indice_posible, NULL, -1, clave, NULL,orden)==ERR)
{
printf("Error insertando clave en Redistribuir\n");
return ERR;
}
*hecho = 1;
}
}
if ( BDEscribe_Pagina(bdarbol, src, src->offset)==ERR)
{
printf("Error escribiendo pagina izquierda en Redistribuir_Insercion\n");
return ERR;
}
if ( Mete_Clave( &dst, posi_clave_dst, NULL, -1, temp, NULL, orden)==ERR)
{
printf("Error insertando clave temporal en pagina destino dentro de Redistribuir_Insercion\n");
return ERR;
}
if ( BDEscribe_Pagina(bdarbol, dst, dst->offset)==ERR)
{
printf("Error escribiendo pagina izquierda en Redistribuir_Insercion\n");
return ERR;
}
if ( BDEscribe_Pagina(bdarbol, (*padre), (*padre)->offset)==ERR)
{
printf("Error escribiendo pagina padre en Redistribuir_Insercion\n");
return ERR;
}
if ( src ) Libera_Pagina(src,orden);
if ( dst ) Libera_Pagina(dst,orden);
if ( temp )
{
if ( temp->clave ) free(temp->clave);
free(temp);
}
return OK;
}
/****************************************
Partir_Y_Guardar
Descripcion:
Realiza la operacion de partir una pagina para promocionar un valor
y guardar en disco los cambios (estableciendo apropiadamente los offsets
de los hijos y los numeros de pagina)
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*clave: cadena de la clave a buscar
nodo: pagina a usar como fuente de la informacion para partir
nuevo: pagina donde se dejara el nuevo elemento a insertar
indice_posible: posicion donde se efectuara la particion
orden: orden del arbolb
clave: clave a insertar (si indice_posible > -1)
offset_padre: offset del padre a pasar a los hijos (izq y der)
num_pag: numero de pagina a asignar a nuevo
Salidas:
codigo de error
Notas:
****************************************/
int Partir_Y_Guardar(BDFichero *bdarbol, PAGINA *nodo, PAGINA **nuevo, int indice_posible, int orden, CLAVE *clave, long offset_padre, int num_pag)
{
PAGINA *izq=NULL, *der=NULL;
int orden2=0;
int mas=0;
/* CdE */
if ( !bdarbol || !nodo || !nuevo || offset_padre < sizeof(BDCabecera)-1 )
{
printf("Error en los parametros de Partir_Y_Guardar\n");
return ERR;
}
if ( indice_posible > -1 && !clave )
{
printf("Error en los parametros de Partir_Y_Guardar\n");
return ERR;
}
memcpy(&orden2, &(bdarbol->pCabecera->sRelleno[8]),4);
if ( orden > orden2 ) mas = 1;
/* Partimos el nodo actual y promocionamos el valor
medio */
if ( Partir( nodo, &der,&izq, nuevo, indice_posible, orden, clave, mas)==ERR)
{
printf("Error partiendo en Partir_Y_Guardar\n");
return ERR;
}
/* der e izq acabaran siendo hijos de nodo al final otra vez */
der->padre = offset_padre;
izq->padre = offset_padre;
/* Tenemos que escribir der e izq para que nos den sus offsets y asignarlos en nuevo */
if ( BDEscribe_Pagina( bdarbol, der, -1 ) == ERR )
{
printf("Error escribiendo nuevo hijo de raiz en Partir_Y_Guardar\n");
return ERR;
}
if ( BDEscribe_Pagina( bdarbol, izq, -1 ) == ERR )
{
printf("Error escribiendo nuevo hijo de raiz en Partir_Y_Guardar\n");
return ERR;
}
/* Actualizamos todos los hijos de izq y der para cambiarles el padre */
if ( Actualiza_Hijos(bdarbol, izq, orden2)==ERR)
{
printf("Error actualizando el campo padre de los hijos de izq\n");
return ERR;
}
if ( Actualiza_Hijos(bdarbol, der, orden2)==ERR)
{
printf("Error actualizando el campo padre de los hijos de der\n");
return ERR;
}
if ( num_pag < 0) (*nuevo)->padre = offset_padre;
else (*nuevo)->numero_pag = num_pag;
(*nuevo)->hijos[0] = izq->offset;
(*nuevo)->hijos[1] = der->offset;
return OK;
}
/****************************************
Partir
Descripcion:
Parte una pagina en dos paginas distintas y crea una nueva donde
mete la clave dada
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*clave: cadena de la clave a buscar
nodo: pagina a usar como fuente de la informacion para partir
der: pagina donde se guardara la parte derecha (menor) de la particion
izq: pagina donde se guardara la parte izquierda (mayor) de la particion
nueva: pagina donde se dejara el nuevo elemento a insertar
indice: posicion donde se efectuara la particion
orden: orden del arbolb
Salidas:
codigo de error
Notas:
****************************************/
int Partir( PAGINA *nodo, PAGINA **der, PAGINA **izq, PAGINA **nueva, int indice, int orden, CLAVE *clave, int masuno)
{
int i=0, b=0,c=0;
/* CdE */
if ( nodo == NULL || der ==NULL || izq== NULL || nueva == NULL )
{
printf("Error en los parametros de Partir\n");
return ERR;
}
if ( Crea_Pagina( izq, orden-masuno, -1 ) == ERR )
{
printf("Error creando pagina inicializada en Partir\n");
if ( der ) Libera_Pagina((*der),orden);
return ERR;
}
/* Copiamos las claves de la izquierda */
while ( i < floor((orden-1)/2) )
{
if ( i == indice )
{
if ( Copia_Clave( &((*izq)->claves[i]), clave)==ERR)
{
printf("Error copiando clave en Partir\n");
return ERR;
}
}
else
{
if ( Copia_Clave( &((*izq)->claves[i]), nodo->claves[b])==ERR)
{
printf("Error copiando clave en Partir\n");
return ERR;
}
b++;
}
(*izq)->hijos[i] = nodo->hijos[i];
(*izq)->contador_claves++;
i++;
}
if ( masuno) (*izq)->hijos[i] = nodo->hijos[i];
/* Creamos la pagina que sera padre */
if ( Crea_Pagina( nueva, orden-masuno, -1 ) == ERR )
{
printf("Error creando pagina nueva en Partir\n");
if ( (*izq) ) Libera_Pagina((*izq), orden);
return ERR;
}
/* Si el valor medio es la clave nueva, la ponemos en la pagina a promocionar */
if ( i == indice )
{
if ( Copia_Clave( &((*nueva)->claves[0]), clave)==ERR)
{
printf("Error copiando clave en Partir\n");
return ERR;
}
}
else
{
if ( Copia_Clave( &((*nueva)->claves[0]), nodo->claves[b])==ERR)
{
printf("Error copiando clave en Partir\n");
return ERR;
}
b++;
}
(*nueva)->contador_claves++;
i++;
if ( Crea_Pagina( der, orden-masuno, -1 ) == ERR )
{
printf("Error creando pagina izquierda en Partir\n");
if ( (*izq) ) Libera_Pagina((*izq), orden);
if ( (*nueva) ) Libera_Pagina((*nueva), orden);
return ERR;
}
c=0;
/* Copiamos las claves de la derecha */
while ( i <= nodo->contador_claves )
{
if ( masuno == 1 && i == nodo->contador_claves ) break;
if ( i == indice )
{
if ( Copia_Clave( &((*der)->claves[c]), clave)==ERR)
{
printf("Error copiando clave en Partir\n");
return ERR;
}
}
else
{
if ( Copia_Clave( &((*der)->claves[c]), nodo->claves[b])==ERR)
{
printf("Error copiando clave en Partir\n");
return ERR;
}
b++;
}
(*der)->hijos[c] = nodo->hijos[i];
(*der)->contador_claves++;
i++;
c++;
}
if ( masuno ) (*der)->hijos[c] = nodo->hijos[i];
return OK;
}
/****************************************
Actualiza_Hijos
Descripcion:
Actualiza el campo padre de los hijos de la pagina dada
Entradas:
*bdarbol: puntero a una bd de un arbol binario
padre: el padre desde el que leer los hijos a actualizar
orden: orden del arbolb
Salidas:
codigo de error
Notas:
****************************************/
int Actualiza_Hijos(BDFichero *bdarbol, PAGINA *padre, int orden)
{
PAGINA *buf=NULL;
int i = 0;
if ( Crea_Pagina(&buf, orden,-1)==ERR)
{
printf("Error localizando pagina buffer en Partir_Y_Guardar\n");
return ERR;
}
for ( i = 0; i < padre->contador_claves+1; i++)
{
if( padre->hijos[i] != -1 )
{
if ( BDLee_Pagina(bdarbol, buf, padre->hijos[i])==ERR)
{
printf("Error leyendo hijo al actualizar padre en Partir_Y_Guardar\n");
if ( buf ) Libera_Pagina(buf, orden);
return ERR;
}
buf->padre = padre->offset;
if ( BDEscribe_Pagina(bdarbol, buf, buf->offset)==ERR)
{
printf("Error reescribiendo hijos en Partir_Y_Guardar\n");
if ( buf ) Libera_Pagina(buf, orden);
return ERR;
}
}
}
if ( buf ) Libera_Pagina(buf, orden);
return OK;
}
/****************************************
Busca_Clave
Descripcion:
Busca una clave dada en el arbol a partir de la pagina dada (generalmente la raiz, 0).
Tambien devuelve la posicion en la que se deberia situar la clave en una pagina para
su insercion.
Entradas:
*bdarbol: puntero a una bd de un arbol binario
**pag: puntero a la pagina previamente localizada en la cual guardar
la pagina en la que esta (o deberia estar) la clave
*clave: cadena de la clave a buscar
pagina: pagina desde la cual empezar a buscar
offset: offset de la pagina desde la cual empezar a buscar
indice_posible: entero en el que guardar la posicion que deberia ocupar la
clave en caso de insercion
indice_clave: indice de la clave dentro de la pagina en caso de haberla encontrado
una_pag: si es 1, significa que limitamos la busqueda a la primera pagina
Salidas:
Escribe en pag el puntero a la estructura de la pagina en la que se encuentre la clave, y modifica
indice_clave para que contenga la posicion de la clave en el indice (-1 si no esta)
Codigo de error
Notas:
Si una_pag es 1 limitamos la busqueda a la primera pagina, en cualquier otro caso
se ignora
****************************************/
int Busca_Clave ( BDFichero *bdarbol, PAGINA **pag, const void *clave, int pagina, long offset, int *indice_posible, int *indice_clave, int una_pag)
{
int i=0, orden=0;
long posicion=0;
int (*funcmp) (const void *a, const void *b);
/* Por defecto indicamos que hubo un error buscando la clave o que no se encontro */
*indice_posible = -1;
*indice_clave = -1;
/* CdE */
if ( bdarbol == NULL || clave == NULL || pagina < 0 || indice_posible == NULL || indice_clave == NULL)
{
printf("Error en los parametros de Busca_Clave\n");
*indice_posible = -1;
*indice_clave = -1;
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]), 4);
/* Leemos la informacion de la pagina desde la cual empezar a buscar, si existe */
/* Obtenemos la posicion de la pagina, leyendo secuencialmente todos los registros
si no es la raiz -> no es muy bueno */
if ( pagina > 0 && offset < 0 )
{
posicion = Busca_Sec_Pagina(bdarbol, pagina);
}
if ( (posicion == -1 || pagina == 0 ) && offset < 0)
{
memcpy(&posicion, &(bdarbol->pCabecera->sRelleno[4]), 4);
if ( posicion < 0 )
{
printf("Error en la posicion de la raiz de la bd del arbol en Busca_Clave\n");
*indice_posible = -1;
*indice_clave = -1;
return ERR;
}
}
else posicion = offset;
/* No funciona */
memcpy(&funcmp, &(bdarbol->pCabecera->sRelleno[12]), sizeof(void*));
/* Empezamos en la pagina de la posicion que hayamos encontrado (raiz u otra) */
while ( posicion != -1 )
{
/* Tenemos que borrar y localizar una pagina en cada pagina que analizamos */
if ( (*pag) ) Libera_Pagina((*pag), orden);
(*pag) = NULL;
if ( Crea_Pagina(pag, orden, -1) ==ERR)
{
printf("Error creando pagina nueva en Busca_Clave\n");
return ERR;
}
if ( BDLee_Pagina( bdarbol, (*pag), posicion ) == ERR )
{
printf("Error leyendo la pagina en Busca_Clave\n");
*indice_posible = -1;
*indice_clave = -1;
return ERR;
}
/* Buscamos la clave en la pagina, o la pagina hija en la que deberia estar */
/* Ponemos condicion de error en la posicion, y indice_posible a 0 por si es un arbol vacio*/
posicion = -1;
*indice_posible = 0;
for ( i = 0;i < (*pag)->contador_claves; i++ )
{
/* Hacemos una comparacion de bytes entre las claves para saber si es igual */
if ( strncmp(((CLAVE*)(*pag)->claves[i])->clave, clave, ((CLAVE*)(*pag)->claves[i])->tam_clave)==0)
{
/* Hemos encontrado la clave, devolvemos la pagina y el indice donde
se encuentra */
*indice_clave = i;
*indice_posible = -1;
return OK;
}
else if ( strcmp(((CLAVE*)(*pag)->claves[i])->clave, clave)>0)
{
/* Nos vamos al hijo izquierdo (menor) de la clave actual */
posicion = (*pag)->hijos[i];
*indice_posible = i;
/* Como la pagina esta ordenada, y es menor, no tiene sentido
seguir buscando en esta pagina, acabamos y vamos a la pagina hija si la
hay */
i = (*pag)->contador_claves;
}
else
{
/* A menos que sea menor,vamos al hijo mayor a la clave dada */
posicion = (*pag)->hijos[i+1];
*indice_posible = i+1;
}
}
if ( una_pag == 1 ) posicion = -1;
}
return OK;
}
/****************************************
Busca_Sec_Pagina
Descripcion:
Busca una pagina dada en el arbol, leyendo secuencialmente todas las paginas
Entradas:
*bdarbol: puntero a una bd de un arbol binario
pagina: pagina a encontrar
Salidas:
La posicion en la bd de la pagina, -1 si no la encuentra
Notas:
****************************************/
long Busca_Sec_Pagina(BDFichero *bdarbol, int pagina)
{
PAGINA *pag=NULL;
int tamano=0, orden=0;
long posicion=-1;
int i=0;
/* CdE */
if ( bdarbol == NULL || pagina < 0 )
{
printf("Error en los parametros de Busca_Sec_Pagina\n");
return ERR;
}
posicion = sizeof ( BDCabecera ) - 1;
/* Buscar secuencialmente la pagina en la bd */
memcpy(&tamano, bdarbol->pCabecera->sRelleno, 4);
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]),4);
while ( i != ERR )
{
if ( Crea_Pagina( &pag, orden, -1) == ERR )
{
printf("Error creando pagina en Busca_Sec_Pagina\n");
return -1;
}
i = BDLee_Pagina( bdarbol, pag, posicion );
if ( i != ERR && i != VACIO )
{
if ( pag->numero_pag == pagina )
i = ERR;
else posicion += tamano;
}
/* La pagina pedida no estaba presente */
else posicion=-1;
if ( pag ) Libera_Pagina(pag, orden);
pag = NULL;
}
return posicion;
}
/****************************************
Borra_Clave
Descripcion:
Borra una clave dada del arbolb y de la bd
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*clave: puntero a una clave a eliminar previamente creada
Salidas:
codigo de error
Notas:
****************************************/
int Borra_Clave( BDFichero *bdarbol, BDFichero *origen, void *clave)
{
int orden=0, indice_posible=0, indice_clave=0;
int estado=0;
long posicion_registro_original=0;
PAGINA *nuevo=NULL, *padre=NULL;
CLAVE *foo=NULL;
/* CdE */
if ( bdarbol == NULL || clave == NULL )
{
printf("Error en los parametros de Borra_Clave\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]),sizeof(int));
if ( orden < 1 )
{
printf("Error en la bd del indice arboreo\n");
return ERR;
}
/* Buscamos la clave en el arbol */
if ( Busca_Clave(bdarbol, &padre, clave, 0, -1, &indice_posible, &indice_clave,0)== ERR )
{
printf("Error buscando clave en el arbol en Borra_Clave\n");
return ERR;
}
else if ( indice_clave == -1 )
{
printf("Clave no encontrada en el arbol en Borra_Clave\n");
if ( padre ) Libera_Pagina(padre, orden);
return ERR;
}
posicion_registro_original = (padre->claves[indice_clave])->offset;
/* La clave esta en un nodo padre, tenemos que buscar su elemento inmediatamente
mayor para intercambiarlo por el y luego borrarlo */
if ( padre->hijos[0] != -1 )
{
if ( Buscar_Clave_Adyacente( bdarbol, padre, &nuevo, indice_clave)==ERR)
{
printf("Error buscando la clave adyacente en Borra_Clave\n");
return ERR;
}
/* Metemos el primer elemento de la pagina con el sucesor en nodo */
if ( Mete_Clave( &padre, indice_clave, nuevo, 0, NULL, &foo, orden)==ERR)
{
printf("Error pasando la clave adyacente a padre en Borra_Clave\n");
return ERR;
}
if ( Elimina_Clave( &nuevo, 0, orden )==ERR)
{
printf("Error borrando clave de la pagina hoja\n");
return ERR;
}
/* Guardamos la modificacion a nuevo */
if ( BDEscribe_Pagina(bdarbol, nuevo, nuevo->offset)==ERR)
{
printf("Error guardando el intercambio en padre en Borra_Clave\n");
return ERR;
}
}
else if ( padre->hijos[0] == -1 )
{
if ( Elimina_Clave( &padre, indice_clave, orden)==ERR)
{
printf("Error borrando clave de la pagina hoja\n");
return ERR;
}
}
else
{
printf("Error, intento de borrar en pagina padre\n");
return ERR;
}
/* Escribimos la eliminacion de la clave antes de averiguar si la pagina ha quedado
valida o no */
if ( BDEscribe_Pagina(bdarbol, padre, padre->offset)==ERR)
{
printf("Error guardando pagina borrada\n");
return ERR;
}
/* Hemos borrado en una pagina hoja, leemos la pagina actual en nuevo
y liberamos padre para leer el padre de nuevo alli */
if ( !nuevo )
{
if ( Crea_Pagina(&nuevo, orden, -1 ) == ERR )
{
printf("Error creando pagina nueva en Borra_Clave\n");
return ERR;
}
if ( BDLee_Pagina(bdarbol, nuevo, padre->offset)==ERR)
{
printf("Error copiando la pagina actual en nuevo\n");
return ERR;
}
}
/* Solo leemos el padre en caso de que no estemos borrando en la raiz */
if ( nuevo->padre != -1)
{
/* Ahora nuevo es el actual padre y padre pasa a ser el padre de nuevo */
if ( BDLee_Pagina(bdarbol, padre, nuevo->padre)==ERR)
{
printf("Error leyendo el padre de la pagina hoja utilizada en Borra_Clave\n");
return ERR;
}
}
/* No hay suficientes elementos restantes en la pagina para satisfacer la
condicion de pagina de arbolb: tenemos que (1) redistribuir o (2) concatenar
lo que quede de la pagina actual y la clave padre de la borrada en una pagina
lateral a la que contenia la clave borrada */
if ( nuevo->contador_claves < floor(orden/2) && nuevo->padre != -1)
{
if ( Fundir( bdarbol, &padre, &nuevo )==ERR)
{
printf("Hubo un error fundiendo paginas\n");
return ERR;
}
}
else if ( padre->padre == -1 && padre->contador_claves == 0)
{
/* Borramos la raiz, ya que esta vacia */
bdarbol->lPosicionActual = padre->offset;
if ( BDBorraRegistro(bdarbol)==ERR)
{
printf("Error borrando la raiz en Borra_Clave\n");
return ERR;
}
/* Cuando se inserte una pagina otra vez, ira a lPosicionBorrado, luego la
raiz estara alli */
estado = bdarbol->pCabecera->lPosicionBorrado;
memcpy(&(bdarbol->pCabecera->sRelleno[4]), &estado, 4);
}
/* No borramos el registro de la bd original hasta que hayamos hecho con exito las operaciones
en el arbolb */
if ( BDPonte(origen, posicion_registro_original, 0)==ERR)
{
printf("Registro inexistente en bd original\n");
return ERR;
}
if ( BDBorraRegistro(origen)==ERR)
{
printf("Error borrando registro en Borra_Clave\n");
return ERR;
}
return OK;
}
/****************************************
Fundir
Descripcion:
Funde dos paginas hijas de un padre y comprueba que el padre
cumpla la condicion de numero de claves. Repite la operacion
si el padre no cumple la condicion (a menos que sea raiz).
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*padre: padre desde el cual empezamos
*nuevo: hijos del padre desde el cual empezamos
Salidas:
codigo
2/2 :D
/****************************************
Buscar_Clave_Adyacente
Descripcion:
Desciende por el arbol b buscando la clave inmediatamente
mayor una dada en una pagina dada
Entradas:
*bdarbol: puntero a una bd de un arbol binario
*nodo: pagina donde esta situada la clave
**nuevo: puntero a la pagina donde esta situada la clave adyacente
indice_clave: indice de la clave en nodo
Salidas:
codigo de error
Notas:
****************************************/
int Buscar_Clave_Adyacente(BDFichero *bdarbol,PAGINA *nodo,PAGINA **nuevo,int indice_clave)
{
int orden = 0;
long posicion = -1;
/* CdE */
if ( !bdarbol || !nodo || !nuevo || indice_clave < 0 )
{
printf("Error en los parametros de Buscar_Clave_Adyacente\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]), 4);
if ( Crea_Pagina( nuevo, orden, -1 )==ERR)
{
printf("Error creando pagina nueva en Buscar_Clave_Adyacente\n");
return ERR;
}
if ( BDLee_Pagina( bdarbol, (*nuevo), nodo->hijos[indice_clave+1])==ERR)
{
printf("Error leyendo pagina hija derecha en Buscar_Clave_Adyacente\n");
return ERR;
}
while ( (*nuevo)->hijos[0] != -1 )
{
posicion = (*nuevo)->hijos[0];
if ( (*nuevo)) Libera_Pagina((*nuevo),orden);
if ( Crea_Pagina( nuevo, orden, -1 )==ERR)
{
printf("Error creando pagina nueva en Buscar_Clave_Adyacente\n");
return ERR;
}
if ( BDLee_Pagina( bdarbol, (*nuevo), posicion)==ERR)
{
printf("Error leyendo pagina hija izq en Buscar_Clave_Adyacente\n");
return ERR;
}
}
return OK;
}
/****************************************
Muestra_Pagina
Descripcion:
Muestra una pagina por su numero o por su offset
Entradas:
*bdarbol: puntero a una bd de un arbol binario
numero_pag: numero de pagina de la pagina a mostrar
posicion: offset de la pagina en la bd
ch: pagina a mostrar, si existe
Salidas:
codigo de error
Notas:
****************************************/
int Muestra_Pagina( BDFichero *bdarbol, int numero_pag, long posicion, PAGINA *ch)
{
PAGINA *pag=NULL;
int i=0, orden=0;
if ( bdarbol == NULL )
{
printf("Error en los parametros de Muestra_Pagina\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]), 4);
if ( ch == NULL )
{
if ( numero_pag < 0 && posicion < 0 )
{
printf("Error en los parametros de Muestra_Pagina\n");
return ERR;
}
if ( Crea_Pagina(&pag, orden, -1) == ERR)
{
printf("Error localizando estructura de pagina en Muestra_Pagina\n");
return ERR;
}
if ( posicion > -1 )
{
if ( BDLee_Pagina(bdarbol, pag, posicion) == ERR )
{
printf("Error leyendo pagina en Muestra_Pagina\n");
if ( pag ) free(pag);
return ERR;
}
}
else if ( numero_pag > -1 )
{
if ( numero_pag == 0 )
{
memcpy(&posicion, &(bdarbol->pCabecera->sRelleno[4]), sizeof(int));
if ( BDLee_Pagina(bdarbol, pag, posicion) == ERR )
{
printf("Error leyendo pagina en Muestra_Pagina\n");
if ( pag ) free(pag);
return ERR;
}
}
else
{
posicion = Busca_Sec_Pagina(bdarbol, numero_pag);
if ( posicion == -1 )
{
printf("Pagina no encontrada en Muestra_Pagina\n");
return ERR;
}
else if ( BDLee_Pagina(bdarbol, pag, posicion) == ERR )
{
printf("Error leyendo pagina en Muestra_Pagina\n");
if ( pag ) free(pag);
return ERR;
}
}
}
}
else pag = ch;
printf("Informacion de la pagina numero %d:\n", pag->numero_pag);
printf("Padre:\t%ld\n", pag->padre);
printf("Offset:\t%ld\n", pag->offset);
printf("Claves e hijos:\n");
for(i = 0; i < pag->contador_claves; i++)
printf("Clave:\t%35s\tOffset:%ld\tHijos:\t%ld\t%ld\t\n", (char*)((CLAVE*)pag->claves[i])->clave, ((CLAVE*)pag->claves[i])->offset, pag->hijos[i], pag->hijos[i+1]);
/* Funcion de liberacion de pagina */
if ( ch == NULL ) if ( pag ) Libera_Pagina(pag, orden);
return OK;
}
/****************************************
Libera_Pagina
Descripcion:
Libera la memoria reservada para una pagina
Entradas:
*pagina: pagina a liberar
Salidas:
codigo de error
Notas:
****************************************/
int Libera_Pagina(PAGINA *pag, int orden)
{
int i=0;
if ( pag == NULL )
return ERR;
if ( pag->contador_claves > orden+1 )
pag->contador_claves = orden-1;
/* Liberamos la memoria de las claves */
if ( pag->claves != NULL )
{
for ( i = 0; i < pag->contador_claves; i++)
{
if ( pag->claves[i] )
{
if ( (pag->claves[i])->clave )
free( ((CLAVE*)pag->claves[i])->clave);
free( pag->claves[i] );
}
}
free ( pag->claves );
}
if ( pag->hijos) free ( pag->hijos );
free ( pag );
return OK;
}
/****************************************
Crea_Pagina
Descripcion:
Crea una pagina vacia con sus valores inicializados
Entradas:
*pagina: pagina a inicializar
orden: orden del arbol
Salidas:
codigo de error
Notas:
Los hijos se inicializa a -1 y el padre igual
****************************************/
int Crea_Pagina(PAGINA **pag, int orden, int num_pag)
{
int i=0;
/* CdE */
if ( pag == NULL || orden < 0)
{
printf("Error en los parametros de Crea_Pagina\n");
return ERR;
}
if( ((*pag)=calloc(1, sizeof(PAGINA)))==NULL ){
printf("Error en la reserva de memoria de pag en Crea_Pagina\n");
return ERR;
}
/* Inicializamos la pagina vacia */
if( ((*pag)->hijos = (long*) calloc( 1, sizeof(long) * orden))==NULL)
{
printf("Error en la reserva de memoria de los offsets de los hijos en Crea_Pagina\n");
if ( (*pag) ) Libera_Pagina((*pag), orden);
return ERR;
}
/* Inicializamos el array de claves */
(*pag)->claves = NULL;
if( ((*pag)->claves = (CLAVE** ) calloc ( 1, sizeof (CLAVE*) * (orden-1)))==NULL)
{
printf("Error en la reserava de memoria del array de claves en Crea_Pagina\n");
if ( (*pag) ) Libera_Pagina((*pag),orden);
return ERR;
}
for ( i = 0 ; i <(orden-1);i++)
{
(*pag)->claves[i] = NULL;
(*pag)->hijos[i] = -1;
}
(*pag)->hijos[i] = -1;
(*pag)->numero_pag = num_pag;
(*pag)->padre = -1;
(*pag)->offset = -1;
(*pag)->contador_claves = 0;
return OK;
}
/****************************************
Lee_Der_Izq
Descripcion:
Lee las paginas derecha e izquierda a una dada
Entradas:
bdarbol:
padre:
nodo:
der:
izq:
Salidas:
codigo de error
Notas:
****************************************/
int Lee_Der_Izq(BDFichero *bdarbol, PAGINA *padre, long offset_nodo, PAGINA **der, PAGINA **izq, int *i)
{
int b=0;
int orden = 0;
if ( !bdarbol || !padre || offset_nodo < 0 || !der || !izq )
{
printf("Parametros erroneos en Lee_Der_Izq\n");
return ERR;
}
/* Buscamos los offsets de las paginas anexas a nodo */
for(b=0; b < (padre->contador_claves)+1; b++)
if ( padre->hijos[b] == offset_nodo ) break;
if ( b > padre->contador_claves )
{
printf("El offset dado no esta en padre en Lee_Der_Izq\n");
return ERR;
}
memcpy(&orden, &(bdarbol->pCabecera->sRelleno[8]), 4);
if ( b > 0 )
{
if ( padre->hijos[b-1] != -1 )
{
if ( Crea_Pagina(izq, orden, -1) ==ERR)
{
printf("Error creando pagina izq en Lee_Der_Izq\n");
return ERR;
}
if ( BDLee_Pagina(bdarbol, (*izq), padre->hijos[b-1])==ERR)
{
printf("Error obteniendo la pagina izquierda en Lee_Der_Izq\n");
return ERR;
}
}
}
if ( padre->hijos[b+1] != -1 && b != (padre->contador_claves))
{
if ( Crea_Pagina(der, orden, -1) ==ERR)
{
printf("Error creando pagina izq en Lee_Der_Izq\n");
return ERR;
}
if ( BDLee_Pagina(bdarbol, (*der), padre->hijos[b+1])==ERR)
{
printf("Error obteniendo la pagina derecha en Lee_Der_Izq\n");
return ERR;
}
}
*i = b;
return OK;
}
/****************************************
Copia_Clave
Descripcion:
Copia la informacion de una clave *src a otra
clave *dst (localizando memoria si es preciso)
Entradas:
*dst: clave destino, si es null se crea
*src: clave fuente
Salidas:
codigo de error
Notas:
****************************************/
int Copia_Clave(CLAVE **dst, const CLAVE *src)
{
if ( src == NULL || dst == NULL)
{
printf("Error en los parametros de Copia_Clave\n");
return ERR;
}
if ( src->clave==NULL || src->offset < 0 || src->tam_clave <1 )
{
printf("Error en los parametros de Copia_Clave\n");
return ERR;
}
if ( !(*dst) )
{
if ( ( (*dst) = calloc(1, sizeof(CLAVE)))==NULL)
{
printf("Error localizando memoria para una clave nueva en Copia_Clave\n");
return ERR;
}
if ( ( (*dst)->clave = calloc(1, src->tam_clave))==NULL)
{
printf("Error localizando memoria para la clave en Copia_Clave\n");
return ERR;
}
}
else
{
if ( ( (*dst)->clave = realloc((*dst)->clave, src->tam_clave))==NULL)
{
printf("Error relocalizando memoria para (*dst) en Copia_Clave\n");
return ERR;
}
}
(*dst)->offset = src->offset;
(*dst)->tam_clave = src->tam_clave;
memcpy((*dst)->clave, src->clave, src->tam_clave);
return OK;
}
/****************************************
Mete_Clave
Descripcion:
Mueve la informacion de una clave a otra
clave ( en una pagina ), guardando la clave destino en *temp
La clave puede estar en una pagina o ser pasada
como parametro.
Entradas:
*dst: pagina destino
indice_posible: posicion en la cual insertar la clave (-1 si tenemos que
buscar en que posicion iria)
*src: pagina fuente de la clave (NULL si es una insercion de clave suelta)
posicion_src: posicion de la clave en la pagina fuente
clave_src: clave fuente en caso de insercion suelta
temp: estructura en la que guardar la clave
orden: orden del arbolb
Salidas:
codigo de error
Notas:
Si la clave esta en una pagina, reajustamos la pagina
Si se nos da una posicion en la que insertar, confiamos en que sea ordenada
****************************************/
int Mete_Clave( PAGINA **dst, int posicion_dst, PAGINA *src, int posicion_src, CLAVE *clave_src, CLAVE **temp, int orden)
{
int i=0, copiar_hijos=0;
CLAVE *clave=NULL;
PAGINA *nuevo=NULL;
long hijo_izq=-1, hijo_der=-1;
if ( !dst || ( !src && !clave_src ) || ( src && posicion_src <0) || !(*dst) )
{
printf("Error en los parametros de Mete_Clave\n");
return ERR;
}
if ( !clave_src )
{
if ( Copia_Clave( &clave, src->claves[posicion_src])==ERR)
{
printf("Error copiando src->clave en clave\n");
return ERR;
}
if ( src->hijos[posicion_src] != -1 )
{
copiar_hijos = 1;
hijo_izq = src->hijos[posicion_src];
}
if ( src->hijos[posicion_src+1] != -1 )
{
copiar_hijos = 1;
hijo_der = src->hijos[posicion_src+1];
}
}
else
{
if ( Copia_Clave( &clave, clave_src)==ERR)
{
printf("Error copiando clave_src en clave\n");
return ERR;
}
}
/* Solo reemplazamos la clave */
if ( temp )
{
if ( Copia_Clave( temp, (*dst)->claves[posicion_dst])==ERR)
{
printf("Error salvando clave reemplazada en Mete_Clave\n");
return ERR;
}
if ( Copia_Clave( &((*dst)->claves[posicion_dst]), clave)==ERR)
{
printf("Error escribiendo sobre la clave a reemplazar en Mete_Clave\n");
}
return OK;
}
/* Si la insercion es en el ultimo lugar, la hacemos de inmediato */
if ( posicion_dst == (*dst)->contador_claves )
{
if ( Copia_Clave( &((*dst)->claves[posicion_dst]), clave)==ERR)
{
printf("Error escribiendo clave en ultima posicion en Mete_Clave\n");
return ERR;
}
if ( copiar_hijos)
{
if ( hijo_izq > -1 ) (*dst)->hijos[posicion_dst] = hijo_izq;
if ( hijo_der > -1 ) (*dst)->hijos[posicion_dst+1] = hijo_der;
}
(*dst)->contador_claves++;
return OK;
}
if ( Crea_Pagina(&nuevo, orden, -1)==ERR)
{
printf("Error creando pagina nueva en Mete_Clave\n");
return ERR;
}
/* Insertamos la clave en la posicion dada */
if ( posicion_dst > -1 )
{
while (i < posicion_dst )
{
if ( Copia_Clave( &(nuevo->claves[i]), (*dst)->claves[i])==ERR)
{
printf("Error copiando clave en Inserta_Clave_No_Lleno\n");
return ERR;
}
nuevo->hijos[i] = (*dst)->hijos[i];
i++;
}
if ( Copia_Clave( &(nuevo->claves[i]), clave)==ERR)
{
printf("Error copiando clave en Inserta_Clave_No_Lleno\n");
return ERR;
}
if ( copiar_hijos)
{
if ( hijo_izq > -1 ) (*dst)->hijos[posicion_dst] = hijo_izq;
if ( hijo_der > -1 ) (*dst)->hijos[posicion_dst+1] = hijo_der;
}
else
nuevo->hijos[posicion_dst] = (*dst)->hijos[i];
i++;
while (i <= (*dst)->contador_claves)
{
if ( Copia_Clave( &(nuevo->claves[i]), (*dst)->claves[i-1])==ERR)
{
printf("Error copiando clave en Inserta_Clave_No_Lleno\n");
return ERR;
}
nuevo->hijos[i] = (*dst)->hijos[i];
i++;
}
}
/* Tenemos que averiguar en que indice colocamos esta clave en esta pagina */
if ( posicion_dst == -1 )
{
i = 0;
while ( i < (*dst)->contador_claves )
{
/* Hacemos una comparacion de bytes entre las claves para saber si es igual */
if ( strncmp(((CLAVE*)(*dst)->claves[i])->clave, clave->clave, ((CLAVE*)(*dst)->claves[i])->tam_clave)==0)
{
/* Hemos encontrado la clave, devolvemos la pagina y el indice donde
se encuentra */
printf("Error, clave ya presente en Mete_Clave\n");
return ERR;
}
else if ( strcmp(((CLAVE*)(*dst)->claves[i])->clave, clave->clave)>0)
{
/* Hemos encontrado la posicion en la que meter la clave */
if ( Copia_Clave( &(nuevo->claves[i]), clave)==ERR)
{
printf("Error copiando clave en Mete_Clave\n");
return ERR;
}
if ( src )
{
nuevo->hijos[i] = src->hijos[posicion_src];
nuevo->hijos[i+1] = src->hijos[posicion_src+1];
}
else
{
nuevo->hijos[i] = (*dst)->hijos[i];
nuevo->hijos[i+1] = (*dst)->hijos[i+1];
}
break;
}
else
{
/* Copiamos la clave a nuevo, ya que es menor */
if ( Copia_Clave( &(nuevo->claves[i]), (*dst)->claves[i])==ERR)
{
printf("Error copiando clave en Mete_Clave\n");
return ERR;
}
nuevo->hijos[i] = (*dst)->hijos[i];
nuevo->hijos[i+1] = (*dst)->hijos[i+1];
i++;
}
}
if ( i == (*dst)->contador_claves )
{
if ( Copia_Clave( &(nuevo->claves[i]), clave)==ERR)
{
printf("Error copiando clave en Mete_Clave\n");
return ERR;
}
if ( src )
{
nuevo->hijos[i] = src->hijos[posicion_src];
nuevo->hijos[i+1] = src->hijos[posicion_src+1];
}
}
else
{
/* Copiamos a nuevo lo que quede por copiar */
i++;
while ( (i-1) < (*dst)->contador_claves )
{
if ( Copia_Clave( &(nuevo->claves[i]), (*dst)->claves[i-1])==ERR)
{
printf("Error copiando clave en Mete_Clave\n");
return ERR;
}
nuevo->hijos[i+1] = (*dst)->hijos[i];
i++;
}
}
}
nuevo->padre = (*dst)->padre;
nuevo->numero_pag = (*dst)->numero_pag;
nuevo->offset = (*dst)->offset;
nuevo->contador_claves = (*dst)->contador_claves+1;
if ( (*dst) ) Libera_Pagina((*dst),orden);
(*dst) = nuevo;
return OK;
}
/****************************************
Elimina_Clave
Descripcion:
Elimina una clave de una pagina y la reorganiza si es
necesario
Entradas:
**dst: pagina destino
indice_posible: posicion en la cual insertar la clave (-1 si tenemos que
buscar en que posicion iria)
*src: pagina fuente de la clave (NULL si es una insercion de clave suelta)
posicion_src: posicion de la clave en la pagina fuente
clave_src: clave fuente en caso de insercion suelta
temp: estructura en la que guardar la clave
orden: orden del arbolb
Salidas:
codigo de error
Notas:
Si la clave esta en una pagina, reajustamos la pagina
Si se nos da una posicion en la que insertar, confiamos en que sea ordenada
****************************************/
int Elimina_Clave( PAGINA **dst, int posicion_dst, int orden)
{
/* CdE */
if ( dst == NULL || (*dst)==NULL || orden < 1 || posicion_dst < 0 || posicion_dst > (*dst)->contador_claves-1)
{
printf("Parametros erroneos en Elimina_Clave\n");
return ERR;
}
if ( (*dst)->claves[posicion_dst] )
{
if ( ((*dst)->claves[posicion_dst])->clave ) free(((*dst)->claves[posicion_dst])->clave);
free((*dst)->claves[posicion_dst]);
}
(*dst)->claves[posicion_dst] = NULL;
/* (*dst)->hijos[posicion_dst] = -1; */
(*dst)->contador_claves--;
/* Reorganizamos las claves de la pag */
if ( posicion_dst < (*dst)->contador_claves )
{
if ( Reorganiza_Pag( dst, orden )==ERR)
{
printf("Error reorganizando la pagina en Elimina_Clave\n");
Libera_Pagina((*dst),orden);
return ERR;
}
}
return OK;
}
/****************************************
Compara_MarcaModelo
Descripcion:
Compara dos cadenas MarcaModelo dadas
Entradas:
*a: marcamodelo 1
*b: marcamodelo 2
Salidas:
1 si a es mayor, 0 si son iguales, -1 si b es mayor
Notas:
****************************************/
int Compara_MarcaModelo(const void * a, const void * b)
{
return (strcmp( a , b ));
}
/****************************************
Reorganiza_Pag
Descripcion:
Elimina el hueco dejado en una pagina al borrar
o al redistribuir
Entradas:
**pag: puntero a una pagina localizada
orden: orden del arbolb
Salidas:
codigo de error
Notas:
****************************************/
int Reorganiza_Pag(PAGINA **pag, int orden )
{
int i=0;
int count=0;
/* CdE */
if ( pag == NULL || orden < 1 )
{
printf("Parametros erroneos en Reorganiza_Pag\n");
return ERR;
}
while ( i < (orden-2) && count < (orden-2))
{
if ( (*pag)->claves[i] == NULL && (*pag)->claves[i+1] != NULL )
{
if ( Copia_Clave( &((*pag)->claves[i]), (*pag)->claves[i+1])==ERR)
{
printf("Error copiando clave en Reorganiza_Pag\n");
return ERR;
}
if ((*pag)->claves[i+1])
{
if( ((*pag)->claves[i+1])->clave )
free(((*pag)->claves[i+1])->clave);
free((*pag)->claves[i+1]);
}
(*pag)->claves[i+1] = NULL;
count++;
}
if ( (*pag)->hijos[i] == -1 && (*pag)->hijos[i+1] != -1 )
{
(*pag)->hijos[i] = (*pag)->hijos[i+1];
(*pag)->hijos[i+1] = -1;
}
i++;
}
return OK;
}
/****************************************
Rota_Hijoa
Descripcion:
Rota los hijos de una pagina dada a la izquierda
o a la derecha (dejando un -1 en el extremo correspondiente)
Entradas:
**pag: puntero a una pagina localizada
orden: orden del arbolb
direccion: direccion a la que rotar (0) izquierda, (1) derecha
Salidas:
codigo de error
Notas:
****************************************/
int Rota_Hijos( PAGINA **pag, int orden, int direccion)
{
int i=0;
if ( pag == NULL || orden < 1 )
{
printf("Error en los parametros de Rota_Hijos\n");
return ERR;
}
if ( (*pag) == NULL || orden < 1 )
{
printf("Error en los parametros de Rota_Hijos\n");
return ERR;
}
/* Rotamos a la izquierda */
if ( direccion == 0 )
{
while( i <= (*pag)->contador_claves )
{
(*pag)->hijos[i] = (*pag)->hijos[i+1];
i++;
}
(*pag)->hijos[i]=-1;
}
/* Rotamos a la derecha */
else if (direccion == 1)
{
i = (*pag)->contador_claves+1;
while(i > 0 )
{
(*pag)->hijos[i] = (*pag)->hijos[i-1];
i--;
}
(*pag)->hijos[i] = -1;
}
else
{
printf("Error en los parametros de Rota_Hijos\n");
return ERR;
}
return OK;
}
Ayudadme porque me voy a acabar volviendo LOCO!!! :x :x :x Alguien tiene algún código de arboles B para que me pueda guiar?
He visto seudocodigos pero me vendría bien algo ya hecho.
Gracias de antemano.