#include <stdio.h>
#include <stdlib.h>

/*** Programme de simulation de l'allocateur mémoire de Zindoz
     
     Par Adrien Reboisson
     adrien-reboisson@astase.com
     
     Ce programme contient sans doute des erreurs et des imperfections,
     il n'est que montré à titre d'exemple :-)
     
     ***/

/** Nos quelques constantes symboliques **/

#define ZIN_NULL 0
#define ZIN_MEMSPACE 10000
#define ZIN_RESERVED 64

#define ERROR_ALLOCDESCRFAILED 1
#define ERROR_SEGFAULT 2
#define ERROR_AV 3

/** Déclaration des types personnalisés **/

typedef unsigned int zin_addr_t;
typedef unsigned int zin_size_t;
typedef unsigned int zin_pid_t;

/** Un descripteur de bloc de mémoire **/

typedef struct _mem_descriptor_t
{
  zin_addr_t addr; /** Adresse du début de bloc en EAS **/
  zin_size_t size; /** Taille du bloc **/
  zin_pid_t pid; /** PID propriétaire **/
  struct _mem_descriptor_t *next; /** Pointeur sur le suivant **/
} mem_descriptor_t;

/** Variable globale contenant la liste des blocs **/

static mem_descriptor_t* memory = NULL;

/** Quelques fonctions utitaires **/

/**************************************************************/

/** Alloue un descripteur en mémoire **/
mem_descriptor_t* alloc_descriptor(zin_addr_t addr, zin_size_t size, zin_pid_t pid,
  mem_descriptor_t *next)
{
   mem_descriptor_t* p = (mem_descriptor_t*) malloc(sizeof(mem_descriptor_t));
   if (p) /** Allocation réussie ?... **/
   {     /** On remplit les propriétés du descripteur : **/
         p->addr = addr;
         p->size = size;
         p->pid = pid;
         p->next = next;
         return p;
   } else exit(ERROR_ALLOCDESCRFAILED); /** Erreur : on arrête tout. **/
}

/**************************************************************/

/** Libère un descripteur en mémoire déjà alloué **/
void free_descriptor(mem_descriptor_t* p)
{
     free(p); /** On libère le bloc en mémoire **/
}

/**************************************************************/

/** Simule le Segmentation Fault **/
void do_segfault(void)
{
  printf("[Simulateur] Segmentation fault\n");
  system("PAUSE");
  exit(ERROR_SEGFAULT);    
}

/**************************************************************/

/** Libère un descripteur en mémoire déjà alloué **/
void do_av(void)
{
  printf("[Simulateur] Access violation\n");
  system("PAUSE");
  exit(ERROR_AV);    
}

/**************************************************************/

/** Alloue un descripteur, le chaine et retourne son adresse de départ en EAS **/
zin_addr_t chain_and_return_addr(zin_addr_t addr, 
  zin_size_t size, zin_pid_t pid, mem_descriptor_t* prev, mem_descriptor_t* next)
{
  /** On crée un nouveau descripteur que l'on initialise. **/
  mem_descriptor_t* descr = alloc_descriptor(addr, size, pid, next);
  /** Si memory est vide, alors ce bloc doit être associé à memory (seul bloc enregistré) **/
  if (!memory)
    memory = descr;
  else
    if (prev) /** On chaine le maillon crée à son prédécesseur, s'il y en a un **/
      prev->next = descr;
  /** On renvoie l'adresse de départ en EAS du descripteur **/
  return addr;
} 

/**************************************************************/

/** Afficher la cartographie de la mémoire (pour tester le programme) **/
void dumpmem(void)
{
   mem_descriptor_t* temp = memory;
   printf("---- Structure mémoire ----\n");
   if (temp)
   {
     while (temp)
     {
        printf("@%d, %d octets réservés pour l'application %d\n", temp->addr, temp->size, temp->pid); 
        temp = temp->next;
      }
      printf("---------------------------\n");
   } else printf("La mémoire est vide.\n");
}

/**************************************************************/
/**************************************************************/
/**************************************************************/

/* Fonctions à coder */

/**************************************************************/
/**************************************************************/
/**************************************************************/

zin_addr_t zin_malloc(zin_size_t size, zin_pid_t pid)
{
  mem_descriptor_t* temp;
  if (memory != NULL) /** La mémoire est elle vide ?... **/
  { /** Si on rentre ici, non ! **/
    temp = memory;
    while (temp->next) /** Tant que le bloc a un successeur...*/
    {
      if (temp->next->addr - temp->addr - temp->size >= size) /** Assez de place entre les deux blocs ?... **/
        /** OK: On créé le nouveau descripteur. 
            Le bloc est alloué sur le début du "trou" entre les deux blocs
            examinés, c'est à dire à p->addr + p->size. **/
        return chain_and_return_addr(temp->addr + temp->size, size, pid, temp, temp->next);  
      temp = temp->next; /** On se décale pour examiner le prochain bloc. **/
    }
    /** Arrivé ici, il ne nous reste qu'une chance: il reste assez de place entre le dernier
        bloc et la fin de l'EAS pour insérer notre bloc. **/
    if (ZIN_MEMSPACE - temp->addr - temp->size >= size)
      /** OK: idem que précédemment **/
      return chain_and_return_addr(temp->addr + temp->size, size, pid, temp, temp->next); 
  /** Si on arrive ici, c'est que aucun bloc vide ne peut contenir le notre: on retourne une erreur...**/
    return ZIN_NULL; 
  } else /** Mémoire entièrement libre à ce stade **/
    if (size <= ZIN_MEMSPACE - ZIN_RESERVED) /** Tout l'espace est suffisant pour contenir le bloc ? **/
      /** OK: on créé le nouveau descripteur.
          Le bloc est alloué sur la première adresse disponible, c'est à dire la
          dernière réservée, contenue dans ZIN_RESERVED. **/
      return chain_and_return_addr(ZIN_RESERVED, size, pid, NULL, NULL);
    else
      return ZIN_NULL; /** Pas assez de place en mémoire simulée... **/
}

void zin_free(zin_addr_t addr, zin_pid_t pid)
{
  mem_descriptor_t* temp = memory;
  mem_descriptor_t* last = NULL;
  if (addr == ZIN_NULL) return; /** On doit ignorer le cas ou addr == ZIN_NULL. **/
  if (addr < ZIN_RESERVED) do_av(); /** Par contre, si on tombe dans la plage d'adresse réservées => violation d'accès **/  
  /** Sinon, on explore la liste à la recherche du bloc recherché. **/
  while (temp)
  {
    if (temp->addr == addr && temp->pid == pid) /** Notre bloc cournt est-il le bon ? **/
    {
      /** "last" pointe toujours sur le prédécesseur de temp.
          Si à ce stade temp a un précédesseur, le champ pointant vers son suivant
          est modifié de manière à ce qu'il pointe vers le suivant de temp
          afin d'éliminer temp de la chaîne. **/
      if (last) 
        last->next = temp->next;
      /** Suppression du descripteur... **/
      free_descriptor(temp);
      /** On a fini, on sors ! **/
      return;
    }
    last = temp;
    temp = temp->next;
  }
  /** Si on est arrivé ici, alors le bloc n'existe pas ! **/
  do_segfault();
}

void zin_checkaddr(zin_addr_t addr, zin_pid_t pid)
{
  mem_descriptor_t* temp = memory;
  if (addr < ZIN_RESERVED) do_av(); /** Les adresses en dessous de ZIN_RESERVED ne sont forcément pas valides. **/  
  /** Sinon, on explore la liste à la recherche du bloc recherché. **/
  while (temp)
  {
    /** Le bloc courant contient t-il l'adresse ? **/    
    if (addr >= temp->addr && addr < (temp->addr + temp->size) && pid == temp->pid) 
      return; /** OK !**/
    temp = temp->next;
  }
  /** Si on est arrivé ici, alors le bloc contenant l'adresse n'existe pas ! **/
  do_segfault();  
}

/**************************************************************/
/**************************************************************/
/**************************************************************/


/** Quelques tests **/

int main(int argc, char *argv[])
{
  zin_addr_t q, p = ZIN_NULL;
  dumpmem();
  p = zin_malloc(1024, 0);
  q = zin_malloc(2048, 0);
  p = zin_malloc(10, 0);
  p = zin_malloc(50, 0);
  zin_free(q, 0);
  p = zin_malloc(500, 0);
  p = zin_malloc(50000, 0);
  dumpmem();
  zin_checkaddr(80, 0);
  system("PAUSE");	
  return 0;
}