//*******************************************************************************
//tds.c
//*******************************************************************************
//This file is part of the Orb compiler,
//Copyright (C) 2007 Adrian Fraga Fernandez
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//*******************************************************************************

/***********************************************************************/
/* Tabla de simbolos                                                   */
/***********************************************************************/

#include <stdio.h>
#include <string.h>
#include "error.h"
#include "tds.h"

/***********************************************************************/
/* Conversion de identificadores a simbolos			       */
/***********************************************************************/

	/****************/
	/* definiciones */
	/****************/

	/* Tamaño inicial de la tabla hash */
	
#define H_TINICIAL 	65533 		

	/* Tamaño máximo de la tabla hash */

#define H_TMAX		(1024*1024)	

	/* Altura maxima permitida en la tabla hash 
	
	   Una altura superior a H_HMAX provoca la ampliacion de la tabla, excepto 
	   que el tamanho de esta ya supere H_TMAX, en cuyo caso se mostrará (una sola vez) 
	   un aviso de que dicha tabla ha alcanzado su tamaño máximo
	*/

#define H_HMAX		2		

					/*  */
 
	/************************/
	/* estructuras de datos */
	/************************/

typedef struct HNODO{			/* nodo de la tabla hash */
	char *id;
	struct HNODO *sig;
} HNODO;

static HNODO **hash=NULL;		/* tabla hash */
static unsigned int hashN=0;		/* tamanho actual de la tabla hash */

	/************************/
	/* funciones auxiliares */
	/************************/
	
static unsigned int calcularHash(char *s){
unsigned int h;	
	for(h=0;*s!=0;s++)
		h=h*65599+*s;
	return h%hashN;
}

static HNODO *crearEntrada(char *s){
HNODO *l;
	l=(HNODO *)malloc(sizeof(HNODO));
	if (l==NULL)
		e_fatal(NULL,"Sin memoria al construir la tabla de simbolos");
	l->sig=NULL;
	l->id=strdup(s);
	if (l->id==NULL)
		e_fatal(NULL,"Sin memoria al construir la tabla de simbolos");
}

static void ampliarTabla(void){
HNODO **oldp;
unsigned int i,oldN,h;
HNODO *t,*q;

	oldN=hashN;
	oldp=hash;

		/* crear nueva tabla */
	
	hashN*=2;
	if (hashN>=H_TMAX)
		e_warning(NULL,"La tabla de simbolos ha alcanzado su tamanho maximo y no\n"
			       "crecera mas. El proceso de traduccion continuara pero\n"
			       "con un menor rendimiento");
			       
	hash=(HNODO **)malloc(hashN*sizeof(char **));
	if (hash==NULL)
		e_fatal(NULL, "Sin memoria al ampliar la tabla de simbolos");
	for (i=0;i<hashN;i++) hash[i]=NULL;
	
		/* mover nodos */
	
	for(i=0;i<oldN;i++)
		for(t=oldp[i];t!=NULL;t=q){
			q=t->sig;
			
			h=calcularHash(t->id);
			t->sig=hash[h];
			hash[h]=t;
		}
		
		/* eliminar tabla antigua */
		
	free(oldp);
}
	
static void crearTabla(void){
unsigned int i;

	hashN=H_TINICIAL;
	hash=(HNODO **)malloc(hashN*sizeof(char **));
	if (hash==NULL)
		e_fatal(NULL, "Sin memoria al construir la tabla de simbolos");
	for (i=0;i<hashN;i++) hash[i]=NULL;
}

	/* interfaz */

char *t_simbolo(char *id){
unsigned int h;
HNODO *p;
int altura;

	if (hashN==0) crearTabla();

	h=calcularHash(id);
	if (hash[h]==NULL){
	
			/* crear nueva entrada (slot vacio) */
	
		hash[h]=crearEntrada(id);
		return hash[h]->id;
	}
	else {
			/* buscar la entrada en la tabla */
	
		for (p=hash[h],altura=0;p!=NULL;p=p->sig,altura++)
			if (!strcmp(p->id,id))
				return p->id;
		
			/* crear nueva entrada si la busqueda ha fallado */

		if (altura>=H_HMAX && hashN<H_TMAX){
			ampliarTabla();
			h=calcularHash(id);
		}
							
		p=hash[h];
		hash[h]=crearEntrada(id);
		hash[h]->sig=p;
		return hash[h]->id;
	}
}

/***********************************************************************/
/* Tablas de simbolos                      			       */
/***********************************************************************/

	/*********************************/
	/* Estructura de datos para nodo */
	/*********************************/
	
typedef struct T_NODO{		
	char *simbolo;			/* Simbolo */
	unsigned char parametros;	/* Parametros */
	void *datos;			/* Datos asociados al simbolo */
	int bal;			/* Balanceado del nodo */
	struct T_NODO *iz;		/* Hijo izquierdo del nodo */
	struct T_NODO *der;		/* Hijo derecho del nodo */	
} T_NODO;
	
	/************************/
	/* funciones auxiliares */
	/************************/
	
void *crearNodo(void){
T_NODO *p;
	p=(T_NODO *)malloc(sizeof(T_NODO));
	if (p==NULL)
		e_fatal(NULL,"Sin memoria al construir tabla de simbolos");
	return p;
}

static T_NODO *rotarIzquierda(T_NODO *p){
T_NODO *r;
	r=p->der;
	p->der=r->iz;
	r->iz=p;
	p->bal--;
	if (r->bal>0) p->bal-=r->bal;
	r->bal--;
	if (p->bal<0) r->bal+=p->bal;
	return r;	
}

static T_NODO *rotarDerecha(T_NODO *p){
T_NODO *l;
	l=p->iz;
	p->iz=l->der;
	l->der=p;
	p->bal++;
	if (l->bal<0) p->bal-=l->bal;
	l->bal++;
	if (p->bal>0) l->bal+=p->bal;
	return l;	
}

	/*******************************/
	/* Crear una tabla de simbolos */
	/*******************************/

void *t_crear(void){
	return NULL;
}
	
	/************************************/
	/* Insertar un simbolo en una tabla */
	/************************************/

void *t_insertar(void *tabla, char *simbolo, unsigned char parametros, void *datos){
static int aux;		
T_NODO *p;

	aux=0;
	p=tabla;
	if (p==NULL){
		p=crearNodo();
		p->simbolo=simbolo;
		p->parametros=parametros;
		p->bal=0;
		p->iz=NULL;
		p->der=NULL;
		p->datos=datos;
		aux=1;
	}
	else if (p->simbolo<simbolo || (p->simbolo==simbolo && p->parametros<parametros)){
		p->der=t_insertar(p->der,simbolo,parametros,datos);		
		if (aux){
			p->bal++;
			if (p->bal==1) aux=1;
			else if (p->bal==2){
				if (p->der->bal==-1) p->der=rotarDerecha(p->der);
				p=rotarIzquierda(p);
				aux=0;
			}
			else aux=0;
		}
	}
	else if (p->simbolo>simbolo || (p->simbolo==simbolo && p->parametros>parametros)){
		p->iz=t_insertar(p->iz,simbolo,parametros,datos);
		if (aux){
			p->bal--;
			if (p->bal==-1) aux=1;
			else if (p->bal==-2){
				if (p->iz->bal==1) p->iz=rotarIzquierda(p->iz);
				p=rotarDerecha(p);
				aux=0;
			}
			else aux=0;
		}		
	}
	else
		e_fatal(NULL,"El simbolo \"%s\":%d ya existe en la tabla de simbolos",simbolo,parametros);

	return p;
}
		
	/**********************************/
	/* Buscar un simbolo en una tabla */
	/**********************************/

void *t_buscar(void *tabla, char *simbolo, unsigned char parametros){
T_NODO *p;

	p=tabla;
	while(p!=NULL){
		if (p->simbolo<simbolo || (p->simbolo==simbolo && p->parametros<parametros))
			p=p->der;
		else if (p->simbolo>simbolo || (p->simbolo==simbolo && p->parametros>parametros)) 
			p=p->iz;
		else break;
	}
	return p==NULL?NULL:p->datos;
}
	
	/******************************************/
	/* Obtener el primer elemento de la tabla */
	/******************************************/

void *t_primero(void *tabla){
T_NODO *p;

	p=tabla;
	if (p->iz==NULL) return p->datos;
	else return t_primero(p->iz);
}
	
	/************************************************************/
	/* Ejecutar una acción para todos los símbolos de una tabla */
	/************************************************************/

void t_forAll(void *tabla,void (*accion)(char *simbolo,unsigned char parametros,void *datos)){
T_NODO *p;

	p=tabla;
	if (p!=NULL){
		t_forAll(p->iz,accion);
		if (accion!=NULL) accion(p->simbolo,p->parametros,p->datos);
		t_forAll(p->der,accion);
	}	
}

	/****************************************************************/
	/* Borrar un elemento de la tabla de simbolos                   */
	/****************************************************************/

static char *t_borrarAuxSimbolo;
static unsigned char t_borrarAuxParametros;
static void *t_borrarAuxTabla;
static void (*t_borrarAuxAccion)(char *simbolo,unsigned char parametros, void *datos);

static void t_borrarAuxF1(char *simbolo,unsigned char parametros, void *datos){
	if (simbolo==t_borrarAuxSimbolo && parametros==t_borrarAuxParametros){
		if (t_borrarAuxAccion!=NULL)
			t_borrarAuxAccion(simbolo,parametros,datos);
	}
	else
		t_borrarAuxTabla=t_insertar(t_borrarAuxTabla,simbolo,parametros,datos);
}
void *t_borrar(void *tabla, char *simbolo, unsigned char parametros,
               void (*accion)(char *simbolo,unsigned char parametros, void *datos)){

	t_borrarAuxSimbolo=simbolo;
	t_borrarAuxParametros=parametros;
	t_borrarAuxAccion=accion;
	t_borrarAuxTabla=t_crear();
	t_forAll(tabla,&t_borrarAuxF1);
	t_free(tabla,NULL);
	return t_borrarAuxTabla;
}	     
	
	/****************************************************************/
	/* Destruir una tabla de simbolos y liberar la memoria asociada */
	/****************************************************************/

void t_free(void *tabla,void (*accion)(char *simbolo,unsigned char parametros,void *datos)){
T_NODO *p;

	p=tabla;
	if (p!=NULL){
		t_free(p->iz,accion);
		t_free(p->der,accion);
		if (accion!=NULL) accion(p->simbolo,p->parametros,p->datos);
		free(p);
	}	
}

	/******************************************/
	/* Comprobar si una tabla esta vacía      */
	/******************************************/

char t_vacio(void *tabla){
	return tabla==NULL;
}
	
	/******************************************/
	/* Imprimir una tabla de simbolos (debug) */
	/******************************************/

static void imprimir(void *tabla,int altura){
int i;
T_NODO *p;

	p=tabla;
	if (p!=NULL){
		imprimir(p->iz,altura+1);
		for (i=0;i<altura;i++) printf(" ");	
		//printf("%s(%d):%d\n",p->simbolo,p->parametros,p->bal);
		printf("%s(%d)\n",p->simbolo,p->parametros);
		imprimir(p->der,altura+1);
	}
	else{
		//for (i=0;i<altura;i++) printf(" ");	
		//printf("<vacio>\n");
	}
}

void t_imprimir(void *tabla){
	printf("..................................................................\n");
	imprimir(tabla,0);
	printf("..................................................................\n");
}



