#include "bibliotheque.h"

/*
La fonction preallocate() initialise le tas avec une taille specifiée en argument.
L'initialisation correspond à la demande de mémoire (sbrk), à la définition du super-bloc
de type en_tete correspondant au tas lui-même, et a la création du bloc libre 'premier' qui
est correspond au contenu du tas. 
*/
int preallocate(unsigned  size) {
	if ( (size<=MAX_SIZE) && (size>EN_TETE) ) {
		
		// On crée un bloc de 'size' octets correspondant au tas et on l'initialise.
		tas=sbrk(size);
		tas->taille= (size/EN_TETE)-1 ;
		tas->suivant=tas+1;
		
		// puis on initialise le premier bloc libre.
		en_tete *premier;
		premier=tas->suivant;
		premier->taille=tas->taille-1;
		premier->suivant=NULL;
		
		#ifdef DEBUG
			affichage();
		#endif
		
		return 0;
	} else
		return -1;	
}

/* 
La fonction myMalloc() est notre fonction d'allocation malloc() personnelle. Elle
utilise l'algorithme First-Fit, c'est-a-dire que l'on recherche le premier bloc suffisamment
grand, en le scindant en deux, s'il est trop grand, pour pouvoir récupérer le reste de l'espace
qui ne sera pas utilisé.On renvoie un pointeur sur le bloc que l'on a déterminé, ou 0 s'il n'y a
plus de place, ou que le tas n'a pas été initialisé. 
*/
void * myMalloc(unsigned  size) {
	// Si le tas n'a pas été initialisé, on sort ..
	if ( tas == 0) {
		#ifdef DEBUG
			puts("Impossible <-- le tas n'a pas été initialisé ...");
		#endif
		errno=ENOMEM;
		return 0;
	}
	
	en_tete *a,*b,*precedent;
	
	// On convertit la taille en octets, donnée en argument, en une taille compatible avec les adresses
	size = (size/EN_TETE)+1;
	
	// Soit 'a' le premier bloc vide du tas. On cherche un bloc dont la taille est suffisante tant 
	// que 'a' est non NULL, c'est à dire que le tas a été parcouru en entier.
	for ( precedent=tas,a=tas->suivant ; a!=NULL ; precedent=a ,a=a->suivant ) {
		// Bloc suffisamment grand
		if ( a->taille >= size ) {
			// Juste assez
			if ( a->taille == size ) {
				// Redéfinition correct du chaînage des blocs libre du tas
				precedent->suivant=a->suivant;
				#ifdef DEBUG
					puts("Bloc juste assez grand.");
					printf("-> A : %d -- %d \n",a,a->taille);
				#endif
			} 
			// Bloc plus grand que nécessaire, il faut créer un nouveau bloc vide contenant 
			// le reste du bloc actuel non utilisé
			else {
				// Définition du nouveau bloc 'b'
				b=a+size+1;
				b->taille=(a->taille)-size-1;
				b->suivant=a->suivant;
				
				// Redéfinition de la taille du bloc 'a'
				a->taille=size;
				
				// Redéfinition correct du chaînage des blocs libre du tas
				precedent->suivant=b;
				
				#ifdef DEBUG
					puts("Bloc plus grand");
					printf("-> A : %d -- %d \n",a,a->taille);
					printf("-> B : %d -- %d \n\n",b,b->taille);
				#endif
			}
			return (void *)(a+1);
		}
		
		
		// Bloc trop petit
		#ifdef DEBUG
			puts("Bloc trop petit\n\n");
		#endif
	}
	
	// On doit juste retourner un pointeur sur le début du tas (sans l'en_tete_) , mais il n'y a plus de place
	// donc on retourne '0' et on calibre aussi la variable 'errno' comme le veux le standard Unix98 .
	errno=ENOMEM;
	return 0;
	
}
/*
Le but de la fonction myFree() est de libérer le bloc en mémoire dont l'adresse est celle 
pointée par 'ptr' avec l'améloriation à First-Fit qui consiste à regrouper les blocs libres adjacents 
pour réduire fortement la fragmentation. Il ne faut pas oublier de remettre à jour la liste chaînée
des blocs libres.
*/
int myFree(void *ptr) {
	
	// Si le tas n'a pas été initialisé, ou bien, que le pointeur 'ptr' est en-dehors du tas, on sort ..
	if ( (tas == NULL) || (ptr<(void *)tas) || (ptr >(void *)(tas+tas->taille)) ) {
		#ifdef DEBUG
			puts("le tas n'a pas été initialisé ... Ou bien, le pointeur 'ptr' est en-dehors du tas.");
		#endif
		return -1;
	}
	
	en_tete *a,*b;
	
	// Un pointeur sur l'en_tete du bloc :
	b=(en_tete *)ptr-1;

	// On doit retrouver le bloc libre précédant 'b' , s'il éxiste ..
	for (a=tas ; a!=NULL ; a=a->suivant)  {
		// Si le suivant de 'a' est après 'b', ou qu'il n'y a aucun bloc libre après 'a',
		// alors c'est bon, il suffit d'arreter la recherche.
		if ( a->suivant > b || a->suivant == NULL) {
			#ifdef DEBUG
				printf("Bloc retrouvé : %d\n",a);
			#endif
			break;
		}
	}
	
	// Jointure avec le bloc suivant si nécessaire (= s'ils sont collés)
	if ( b->taille+b+1 == a->suivant ) {
		#ifdef DEBUG
			puts("Jointure à droite");
		#endif
		// Redéfinition du bloc 'b' qui englobe maintenant le bloc 'c'
		b->taille +=  a->suivant->taille+1;
		b->suivant =  a->suivant->suivant;
	} else {
		b->suivant =  a->suivant ;
	}
	
	// Jointure avec le bloc précédent si nécessaire (= s'ils sont collés)
	if ( a->taille+a+1 == b ) {
		#ifdef DEBUG
			puts("Jointure à gauche");
		#endif
		// Redéfinition du bloc 'a' qui englobe maintenant le bloc 'b'
		a->taille += b->taille+1;
		a->suivant = b->suivant;
	} else {
		a->suivant = b;
	}
	
	return 0;
}




/*
La fonction affichage() affiche l'état du tas. On affiche la taille (en octets) de 
chaque bloc, séparé par le caractère '-', en parcourant le tas du début jusqu'a
la fin.
*/
void affichage() {
	
	// 'temp' pointe sur le premier bloc du tas.
	en_tete *temp;
	temp=tas+1;
	
	// Si le tas n'a pas été initialisé, on sort ..
	if ( tas == 0) {
		#ifdef DEBUG
			puts("Affichage impossible <-- le tas n'a pas été initialisé ...");
		#endif
		return;
	}
	
	
	// Pour afficher le contenu du tas :
	// - nbr_blocs - nbr_blocs - ....
	while ( temp < (tas->taille+tas+1) ) {
		printf("- %d ",temp->taille*EN_TETE);
		temp += temp->taille +1;
	}
	
	puts("");
}