/****************************************
 * Sebastien Leriche, Antoine Jacquet   *
 * Module de gestion memoire            *
 * Niveau 4                             *
 ****************************************/

#include <stdlib.h>
#include <string.h>
#include "memoire.h"

int cpt_malloc=0, cpt_free=0;
char politique='f';
FILE *fhistorique=NULL;

struct liste_tas *existe_tas(char ident[], struct liste_tas *bus)
/* Renvoie un pointeur sur le tas de nom ident dans la liste des tas pointee par bus ou NULL sinon */
{
  while (bus!=NULL)
  {
    if (strcmp(bus->tas.ident,ident)==0) return(bus);
    bus=bus->p_suivant;
  }
  return(NULL);
}

int initialiser(int t,struct memoire **pp_memoire)
/* Initialise la memoire
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_libre *p_liste_libre;

  fprintf(fhistorique,"  initialiser %d\n",t);
  *pp_memoire=malloc(sizeof(struct memoire));
  if (*pp_memoire==NULL)
  {
    fprintf(fhistorique,"  initialiser : erreur de malloc !\n");
    return(-1);
  }
  cpt_malloc++;

  (*pp_memoire)->mem=malloc(t);
  if ((*pp_memoire)->mem==NULL)
  {
    fprintf(fhistorique,"  initialiser : erreur de malloc !\n");
    return(-1);
  }
  cpt_malloc++;

  p_liste_libre=malloc(sizeof(struct liste_libre));
  if (p_liste_libre==NULL)
  {
    fprintf(fhistorique,"  initialiser : erreur de malloc !\n");
    return(-1);
  }
  cpt_malloc++;
  (*pp_memoire)->taille_memoire=t;
  p_liste_libre->bloc.adresse=0;
  p_liste_libre->bloc.taille=t;
  p_liste_libre->p_suivant=NULL;
  (*pp_memoire)->p_liste_libre=p_liste_libre;
  (*pp_memoire)->p_liste_tas=NULL;
  (*pp_memoire)->p_liste_programmes=NULL;
  return(0);
}

int terminer(struct memoire **pp_memoire)
/* Libere correctement la memoire
   Retourne -1 en cas de mauvaise gestion de la memoire, 0 sinon */
{
  struct liste_libre *p_liste_libre=(*pp_memoire)->p_liste_libre;
  struct liste_libre *bus_libre=p_liste_libre;
  struct liste_tas *p_liste_tas=(*pp_memoire)->p_liste_tas;
  struct liste_tas *bus_tas=p_liste_tas;
  struct programme *p_liste_programmes=(*pp_memoire)->p_liste_programmes;
  struct programme *bus_prog=p_liste_programmes;

  fprintf(fhistorique,"  terminer\n");
  while (bus_libre!=NULL)
  {
    p_liste_libre=(p_liste_libre)->p_suivant;
    free(bus_libre);
    cpt_free++;
    bus_libre=p_liste_libre;
  }
  while (bus_tas!=NULL)
  {
    p_liste_tas=(p_liste_tas)->p_suivant;
    free(bus_tas);
    cpt_free++;
    bus_tas=p_liste_tas;
  }
  while (bus_prog!=NULL)
  {
    p_liste_programmes=(p_liste_programmes)->p_suivant;
    free(bus_prog);
    cpt_free++;
    bus_prog=p_liste_programmes;
  }
  free((*pp_memoire)->mem);
  cpt_free++;
  free(*pp_memoire);
  cpt_free++;
  *pp_memoire=NULL;
  fprintf(fhistorique,"  terminer : cpt_malloc=%d, cpt_free=%d\n",cpt_malloc,cpt_free);
  if (cpt_malloc==cpt_free)
  {
    fprintf(fhistorique,"  terminer : bonne gestion de la memoire\n");
    return(0);
  }
  else
  {
    fprintf(fhistorique,"  terminer : mauvaise gestion de la memoire !\n");
    return(-1);
  }
}

/* Macro qui affecte a bus un pointeur qui contient la zone de memoire libre qui convient
   en fonction de la politique, NULL sinon, ainsi que la cellule precedente dans cel_precedente */
#define ALLOUER_TROUVE_BLOC \
{ \
  struct liste_libre *meilleur=NULL, *meilleur_cel_precedente=NULL; \
\
  cel_precedente=NULL; \
  bus=*pp_liste_libre; \
  switch (politique) \
  { \
    case 'f': \
      while ((bus!=NULL) && (bus->bloc.taille<t)) \
      { \
        cel_precedente=bus; \
        bus=bus->p_suivant; \
      } \
      break; \
    case 'b': \
      while (bus!=NULL) \
      { \
        if (bus->bloc.taille>=t) \
          if ((meilleur==NULL) || (bus->bloc.taille<meilleur->bloc.taille)) \
          { \
            meilleur_cel_precedente=cel_precedente; \
            meilleur=bus; \
          } \
        cel_precedente=bus; \
        bus=bus->p_suivant; \
      } \
      cel_precedente=meilleur_cel_precedente; \
      bus=meilleur; \
      break; \
    case 'w': \
      while (bus!=NULL) \
      { \
        if (bus->bloc.taille>=t) \
          if ((meilleur==NULL) || (bus->bloc.taille>meilleur->bloc.taille)) \
          { \
            meilleur_cel_precedente=cel_precedente; \
            meilleur=bus; \
          } \
        cel_precedente=bus; \
        bus=bus->p_suivant; \
      } \
      cel_precedente=meilleur_cel_precedente; \
      bus=meilleur; \
      break; \
  } \
}

/* Macro qui affiche le message d'erreur et quitte */
#define ALLOUER_ERREUR \
{ \
  fprintf(fhistorique,"    allouer : pas de bloc assez grand !\n"); \
  return(-1); \
}

int allouer(int t, struct memoire *p_memoire)
/* Alloue une zone memoire de taille t
   Retourne son adresse, -1 sinon */
{
  struct liste_libre **pp_liste_libre=&(p_memoire->p_liste_libre);
  struct liste_libre *bus,*cel_precedente;
  int adresse;

  fprintf(fhistorique,"    allouer %d\n",t);

  /* On essaie de trouver un bloc, en appelant les differents ramasse-miettes si necessaire */
  ALLOUER_TROUVE_BLOC
  if (bus==NULL)
  {
    if (ramasse_miettes_compteurs(p_memoire)==-1)
    {
      if (ramasse_miettes_marquage_balayage(p_memoire)==-1) ALLOUER_ERREUR
      else
      {
        ALLOUER_TROUVE_BLOC
        if (bus==NULL) ALLOUER_ERREUR
      }
    }
    else
    {
      ALLOUER_TROUVE_BLOC
      if (bus==NULL)
      {
        if (ramasse_miettes_marquage_balayage(p_memoire)==-1) ALLOUER_ERREUR
        else
        {
          ALLOUER_TROUVE_BLOC
          if (bus==NULL) ALLOUER_ERREUR
        }
      }
    }
  }

  /* Allocation de la zone */
  adresse=bus->bloc.adresse;
  if (bus->bloc.taille==t)
  {
    if (cel_precedente==NULL) *pp_liste_libre=bus->p_suivant;
    else cel_precedente->p_suivant=bus->p_suivant;
    free(bus);
    cpt_free++;
  }
  else
  {
    bus->bloc.taille-=t;
    bus->bloc.adresse+=t;
  }
  fprintf(fhistorique,"    allouer : adresse=%d\n",adresse);
  return(adresse);
}

int liberer(int adresse_libre, int taille_libre, struct memoire *p_memoire)
/* Libere la zone memoire de taille taille_libre a l'adresse adresse_libre
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_libre **pp_liste_libre=&(p_memoire->p_liste_libre);
  struct liste_libre *cel_precedente=NULL, *cel_suivante=NULL, *bus=*pp_liste_libre, *aux;

  fprintf(fhistorique,"    liberer %d %d\n",adresse_libre,taille_libre);
  if ((adresse_libre<0) || (adresse_libre+taille_libre>p_memoire->taille_memoire))
  {
    fprintf(fhistorique,"    liberer : intervalle invalide ?!\n");
    return(-1);
  }

  /* Recherche des cellules entourant la zone a liberer */
  while ((bus!=NULL) && (bus->bloc.adresse<adresse_libre))
  {
    cel_precedente=bus;
    bus=bus->p_suivant;
  }
  cel_suivante=bus;

  if ((cel_precedente!=NULL) && (adresse_libre<cel_precedente->bloc.adresse+cel_precedente->bloc.taille))
  {
    fprintf(fhistorique,"    liberer : zone deja libre ?!\n");
    return(-1);
  }
  if ((cel_suivante!=NULL) && (adresse_libre+taille_libre>cel_suivante->bloc.adresse))
  {
    fprintf(fhistorique,"    liberer : zone deja libre ?!\n");
    return(-1);
  }

  if ((cel_precedente!=NULL) && (cel_suivante!=NULL) && (cel_suivante->bloc.adresse==cel_precedente->bloc.adresse+cel_precedente->bloc.taille+taille_libre))
  {
    cel_precedente->p_suivant=cel_suivante->p_suivant;
    cel_precedente->bloc.taille+=taille_libre+cel_suivante->bloc.taille;
    free(cel_suivante);
    cpt_free++;
    fprintf(fhistorique,"    liberer : fusion de 3 zones\n");
    return(0);
  }

  if ((cel_precedente!=NULL) && (adresse_libre==cel_precedente->bloc.adresse+cel_precedente->bloc.taille))
  {
    cel_precedente->bloc.taille+=taille_libre;
    fprintf(fhistorique,"    liberer : fusion avec la cellule precedente\n");
    return(0);
  }

  if ((cel_suivante!=NULL) && (cel_suivante->bloc.adresse==adresse_libre+taille_libre))
  {
    cel_suivante->bloc.adresse-=taille_libre;
    cel_suivante->bloc.taille+=taille_libre;
    fprintf(fhistorique,"    liberer : fusion avec la cellule suivante\n");
    return(0);
  }

  aux=malloc(sizeof(struct liste_libre));
  if (aux==NULL)
  {
    fprintf(fhistorique,"    liberer : erreur de malloc !\n");
    return(-1);
  }
  cpt_malloc++;
  aux->bloc.adresse=adresse_libre;
  aux->bloc.taille=taille_libre;
  aux->p_suivant=cel_suivante;
  if (cel_precedente==NULL) *pp_liste_libre=aux;
  else cel_precedente->p_suivant=aux;
  fprintf(fhistorique,"    liberer : nouvelle cellule inseree\n");
  return(0);
}

int allouer_tas(char identite_tas[], int taille_tas, struct memoire *p_memoire)
/* Ajoute un tas de nom identite_tas et de taille taille_tas
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_tas **pp_liste_tas=&(p_memoire->p_liste_tas);
  struct liste_tas *aux;
  int i;

  fprintf(fhistorique,"  allouer_tas %s %d\n",identite_tas,taille_tas);
  if (existe_tas(identite_tas,*pp_liste_tas)!=NULL)
  {
    fprintf(fhistorique,"  allouer_tas : tas deja existant !\n");
    return(-1);
  }
  aux=malloc(sizeof(struct liste_tas));
  if (aux==NULL)
  {
    fprintf(fhistorique,"  allouer_tas : erreur de malloc !\n");
    return(-1);
  }
  cpt_malloc++;
  aux->tas.taille=taille_tas;
  strcpy(aux->tas.ident,identite_tas);
  aux->tas.compteur_references=0;
  for (i=0;i<MAX_REF;i++) aux->tas.liste_ident[i][0]='\0';
  aux->tas.drapeau='B';
  if ((aux->tas.adresse=allouer(taille_tas,p_memoire))==-1)
  {
    free(aux);
    cpt_free++;
    fprintf(fhistorique,"  allouer_tas : erreur de allouer !\n");
    return(-1);
  }
  aux->p_suivant=*pp_liste_tas;
  *pp_liste_tas=aux;
  return(aux->tas.adresse);
}

int liberer_tas(char identite_tas[], struct memoire *p_memoire)
/* Libere le tas de nom identite_tas
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_tas **pp_liste_tas=&(p_memoire->p_liste_tas);
  struct liste_tas *bus=*pp_liste_tas,*reference,*precedent=NULL;
  int i;

  fprintf(fhistorique,"  liberer_tas %s\n",identite_tas);
  while ((bus!=NULL) && (strcmp(identite_tas,bus->tas.ident)!=0))
  {
    precedent=bus;
    bus=bus->p_suivant;
  }
  if (bus==NULL)
  {
    fprintf(fhistorique,"  liberer_tas : tas inexistant !\n");
    return(-1);
  }
  if (bus->tas.compteur_references>0)
  {
    fprintf(fhistorique,"  liberer_tas : tas reference !\n");
    return(-1);
  }
  if (liberer(bus->tas.adresse,bus->tas.taille,p_memoire)!=0)
  {
    fprintf(fhistorique,"  liberer_tas : erreur de liberer\n");
    return(-1);
  }

  for (i=0;i<MAX_REF;i++)
    if (bus->tas.liste_ident[i][0]!='\0')
    {
      reference=existe_tas(bus->tas.liste_ident[i],*pp_liste_tas);
      if (reference==NULL)
        fprintf(fhistorique,"  liberer_tas : tas reference a disparu ?!\n");
      else reference->tas.compteur_references--;
    }

  if (precedent==NULL) *pp_liste_tas=bus->p_suivant;
  else precedent->p_suivant=bus->p_suivant;
  free(bus);
  cpt_free++;
  return(0);
}

int ajouter_programme(char ident[], struct memoire *p_memoire)
/* Ajoute le programme de nom ident
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_tas *p_liste_tas=p_memoire->p_liste_tas;
  struct programme **pp_liste_programmes=&(p_memoire->p_liste_programmes);
  struct programme *aux,*bus_prog=*pp_liste_programmes;
  struct liste_tas *p_tas;

  fprintf(fhistorique,"  ajouter_programme %s\n",ident);
  p_tas=existe_tas(ident,p_liste_tas);
  if (p_tas==NULL)
  {
    fprintf(fhistorique,"  ajouter_programme : tas inexistant !\n");
    return(-1);
  }
  while (bus_prog!=NULL)
  {
    if (strcmp(ident,bus_prog->ident)==0)
    {
      fprintf(fhistorique,"  ajouter_programme : programme deja existant !\n");
      return(-1);
    }
    bus_prog=bus_prog->p_suivant;
  }
  aux=malloc(sizeof(struct programme));
  if (aux==NULL)
  {
    fprintf(fhistorique,"  ajouter_programme : erreur de malloc !\n");
    return(-1);
  }
  cpt_malloc++;
  strcpy(aux->ident,ident);
  aux->p_suivant=*pp_liste_programmes;
  p_tas->tas.compteur_references++;
  *pp_liste_programmes=aux;
  return(0);
}

int supprimer_programme(char ident[], struct memoire *p_memoire)
/* Supprime le programme de nom ident
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_tas *p_liste_tas=p_memoire->p_liste_tas;
  struct programme **pp_liste_programmes=&(p_memoire->p_liste_programmes);
  struct programme *precedent=NULL,*bus_prog=*pp_liste_programmes;
  struct liste_tas *p_tas;

  fprintf(fhistorique,"  supprimer_programme %s\n",ident);
  while ((bus_prog!=NULL) && (strcmp(ident,bus_prog->ident)!=0))
  {
    precedent=bus_prog;
    bus_prog=bus_prog->p_suivant;
  }
  if (bus_prog==NULL)
  {
    fprintf(fhistorique,"  supprimer_programme : programme inexistant !\n");
    return(-1);
  }
  if (precedent==NULL) *pp_liste_programmes=bus_prog->p_suivant;
  else precedent->p_suivant=bus_prog->p_suivant;
  free(bus_prog);
  cpt_free++;

  p_tas=existe_tas(ident,p_liste_tas);
  if (p_tas==NULL)
  {
    fprintf(fhistorique,"  supprimer_programme : le tas a disparu !?\n");
    return(-1);
  }
  p_tas->tas.compteur_references--;
  return(0);
}

int ajouter_lien(char tas_referencant[], char tas_reference[], struct memoire *p_memoire)
/* Ajoute un lien de tas_referencant vers tas_reference
   Retourne -1 en cas d'echec, 0 sinon */
{
  struct liste_tas *p_liste_tas=p_memoire->p_liste_tas;
  struct liste_tas *referencant,*reference;
  int i=0;

  fprintf(fhistorique,"  ajouter_lien %s %s\n",tas_referencant,tas_reference);
  referencant=existe_tas(tas_referencant,p_liste_tas);
  if (referencant==NULL)
  {
    fprintf(fhistorique,"  ajouter_lien : tas_referencant inexistant !\n");
    return(-1);
  }
  reference=existe_tas(tas_reference,p_liste_tas);
  if (reference==NULL)
  {
    fprintf(fhistorique,"  ajouter_lien : tas_reference inexistant !\n");
    return(-1);
  }

  while ((i<MAX_REF) && (referencant->tas.liste_ident[i][0]!='\0')) i++;
  if (i==MAX_REF)
  {
    fprintf(fhistorique,"  ajouter_lien : maximum de liens atteint !\n");
    return(-1);
  }
  strcpy(referencant->tas.liste_ident[i],tas_reference);
  reference->tas.compteur_references++;
  return(0);
}

int supprimer_lien(char tas_referencant[], char tas_reference[], struct memoire *p_memoire)
/* Supprime le lien de tas_referencant vers tas_reference
   Retourne -1 en cas d'echec, 0 sinon */
{
  struct liste_tas *p_liste_tas=p_memoire->p_liste_tas;
  struct liste_tas *referencant,*reference;
  int i=0;

  fprintf(fhistorique,"  supprimer_lien %s %s\n",tas_referencant,tas_reference);
  referencant=existe_tas(tas_referencant,p_liste_tas);
  if (referencant==NULL)
  {
    fprintf(fhistorique,"  supprimer_lien : tas_referencant inexistant !\n");
    return(-1);
  }
  reference=existe_tas(tas_reference,p_liste_tas);
  if (reference==NULL)
  {
    fprintf(fhistorique,"  supprimer_lien : tas_reference inexistant !\n");
    return(-1);
  }

  while ((i<MAX_REF) && (strcmp(referencant->tas.liste_ident[i],tas_reference))) i++;
  if (i==MAX_REF)
  {
    fprintf(fhistorique,"  supprimer_lien : lien inexistant !\n");
    return(-1);
  }
  referencant->tas.liste_ident[i][0]='\0';
  reference->tas.compteur_references--;
  return(0);
}

int ramasse_miettes_compteurs(struct memoire *p_memoire)
/* Libere les tas dont le compteur de reference est a zero
   Retoure -1 si aucun tas n'a ete libere, 0 sinon */
{
  struct liste_tas **pp_liste_tas=&(p_memoire->p_liste_tas);
  struct liste_tas *bus,*aux;
  int n=0,compteur_miettes;

  fprintf(fhistorique,"  ramasse_miettes_compteurs\n");
  do
  {
    compteur_miettes=0;
    bus=*pp_liste_tas;
    while (bus!=NULL)
    {
      aux=bus->p_suivant;
      if (bus->tas.compteur_references==0)
        if (liberer_tas(bus->tas.ident,p_memoire)==0) compteur_miettes++;
      bus=aux;
    }
    n+=compteur_miettes;
  } while (compteur_miettes>0);
  fprintf(fhistorique,"  ramasse_miettes_compteurs : %d tas ramasse(s)\n",n);
  if (n==0) return(-1); else return(0);
}

int marquage(struct liste_tas *p_liste_tas, struct programme *p_liste_programmes)
/* Marque les tas accessibles depuis les programmes
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct programme *bus_prog=p_liste_programmes;
  struct liste_tas *bus_tas, *aux;
  int compteur_marquage,i;

  fprintf(fhistorique,"    marquage\n");
  if (p_liste_programmes==NULL) return(0);

  while (bus_prog!=NULL)
  {
    aux=existe_tas(bus_prog->ident,p_liste_tas);
    if (aux==NULL)
    {
      fprintf(fhistorique,"    marquage : le tas a disparu !?\n");
      return(-1);
    }
    aux->tas.drapeau='P';
    fprintf(fhistorique,"    marquage : tas %s marque\n",aux->tas.ident);
    bus_prog=bus_prog->p_suivant;
  }

  do
  {
    compteur_marquage=0;
    bus_tas=p_liste_tas;
    while (bus_tas!=NULL)
    {
      if (bus_tas->tas.drapeau=='P')
      {
        for (i=0;i<MAX_REF;i++)
          if (bus_tas->tas.liste_ident[i][0]!='\0')
          {
            aux=existe_tas(bus_tas->tas.liste_ident[i],p_liste_tas);
            if (aux==NULL)
            {
              fprintf(fhistorique,"    marquage : le tas reference a disparu !?\n");
              return(-1);
            }
            if (aux->tas.drapeau!='N')
            {
              aux->tas.drapeau='P';
              fprintf(fhistorique,"    marquage : tas %s marque\n",aux->tas.ident);
              compteur_marquage++;
            }
          }
        bus_tas->tas.drapeau='N';
      }
      bus_tas=bus_tas->p_suivant;
    }
  }
  while (compteur_marquage>0);

  return(0);
}

int balayage(struct memoire *p_memoire)
/* Libere les tas non marques
   Retoure -1 si aucun tas n'a ete libere, 0 sinon */
{
  struct liste_tas **pp_liste_tas=&(p_memoire->p_liste_tas);
  struct liste_tas *bus=*pp_liste_tas, *aux;
  int n=0,i;

  fprintf(fhistorique,"    balayage\n");
  while (bus!=NULL)
  {
    aux=bus->p_suivant;
    if (bus->tas.drapeau=='B')
    {
      bus->tas.compteur_references=0;
      for (i=0;i<MAX_REF;i++) bus->tas.liste_ident[i][0]='\0';
      if (liberer_tas(bus->tas.ident,p_memoire)==0) n++;
    }
    else bus->tas.drapeau='B';
    bus=aux;
  }
  fprintf(fhistorique,"    balayage : %d tas balaye(s)\n",n);
  if (n==0) return(-1); else return(0);
}

int ramasse_miettes_marquage_balayage(struct memoire *p_memoire)
/* Libere les tas non accessibles depuis les programmes
   Retourne -1 en cas d'erreur, 0 sinon */
{
  struct liste_tas *p_liste_tas=p_memoire->p_liste_tas;
  struct programme *p_liste_programmes=p_memoire->p_liste_programmes;

  fprintf(fhistorique,"  ramasse_miettes_marquage_balayage\n");
  if (marquage(p_liste_tas,p_liste_programmes)==-1)
  {
    fprintf(fhistorique,"  ramasse_miettes_marquage_balayage : erreur de marquage ?!\n");
    return(-1);
  }
  if (balayage(p_memoire)==-1)
  {
    fprintf(fhistorique,"  ramasse_miettes_marquage_balayage : aucun tas balaye\n");
    return(-1);
  }
  return(0);
}