Malditos Arboles B

[NeCRoMaNCeR]

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

[NeCRoMaNCeR]

2/2 :D

Código [Seleccionar] Expand


/****************************************
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;

}


[ghware]

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.