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

#define TOAALBESCHIBAARGEHEUGEN 100

typedef struct element {
   int adres;
   int size;
   struct element *next;
} Element;

typedef enum {
  TRUE = 1,
  FALSE = 0
} bool; /* dit is een boolean */

/* 
 * Public Domain functie die de line buffering uit schakelt,
 * de char pakt, en de terminal weer terug zet
 * (emuleert de domme terminal van windhoos)
 */
int getch (void) {
  struct termios oldt, newt;
  int ch;
  tcgetattr(STDIN_FILENO, &oldt);
  newt = oldt;
  newt.c_lflag &= ~(ICANON | ECHO);
  tcsetattr(STDIN_FILENO, TCSANOW, &newt);
  ch = getchar();
  tcsetattr(STDIN_FILENO, TCSANOW, &oldt);
  return ch;
}

void toonLijst (Element *lijst) {
/* pre : lijst = NULL of wijst naar een lineaire lijst waarvan het laatste
         element de pointer next gelijk is aan NULL
   post: Alle data in de lijst zijn afgdrukt op het scherm
*/
  /**********************************************************/
  /* Maak gebruik van de onderstaande printf om de gegevens */
  /* van een element van de lijst af tedrukken              */
  /*  printf("\n adres = %5d size = %5d",h->adres,h->size)  */
  /**********************************************************/

  Element *h = lijst;

  while (h != NULL) {
    printf("\n adres = %5d size = %5d", h->adres, h->size);
    h = h->next;
  }

} /* toonLijst */


int vrijgevenGeheugen (Element **freeLijst, Element **allocLijst, int adres) {
/* pre:
   post: Als adres voorkomt in het gealloceerd geheugen *allocLijst
         Dan is het geheugen vanaf dit adres met de geregistreerde
             aantalBytes niet meer opgenomen in *allocLijst en is het adres
             met aantalBytes opgenomen in *freeLijst en
             vrijgevenGeheugen(freeLijst,allocLijst,adres) = aantalbytes dat
             bij adres hoort
         Anders vrijgevenGeheugen(freeLijst,allocLijst,adres) = 0.

   Opmerking: Adres MAX+1 is mogelijk met lengte 0 in het vrije geheugen
              Dit is een hack om de som te laten kloppen
*/

  Element *h, *a, *ph, *pa, *tmpa;
  int vrijeBytes = 0;
  bool breakDadelijk; /* Mocht het gealloceerd geheugen tot niets gaan vangt dit het op */

  a = *allocLijst;
  pa = NULL;
  while (a != NULL) {
    breakDadelijk = FALSE;
    h = *freeLijst;
    ph = NULL;
    while (h != NULL) {
      if (ph != NULL) {
        if (ph->adres + ph->size == h->adres && ph->size != 0) {
          /* Het voorgaande blok sluit aan */
          ph->next = h->next;
          ph->size += h->size;
          free(h);
          h = ph;
        }
      }
      if (breakDadelijk)
        break;
      if (h->adres + h->size == a->adres && vrijeBytes == 0 && a->adres == adres) {
        /* Blok sluit achter een bestaand blok aan */
        vrijeBytes = a->size;
        h->size += a->size;
        if (pa != NULL) {
          pa->next = a->next;
          free(a);
          a = pa;
        } else {
          tmpa = a->next;
          free(a);
          a = tmpa;
          *allocLijst = a;
        }
        if (a == NULL)
          breakDadelijk = TRUE;
      } else if (a->adres < h->adres && vrijeBytes == 0 && a->adres == adres) {
        /* Blok komt in het begin van het geheugen of ergens tussenin */
        vrijeBytes = a->size;
        tmpa = a->next;
        a->next = h;
        if (pa != NULL)
          pa->next = tmpa;
        if (ph != NULL)
          ph->next = a;
        h = a;
        if (ph == NULL)
          *freeLijst = h;
        a = tmpa;
        if (pa == NULL)
          *allocLijst = a;
        if (a == NULL)
          breakDadelijk = TRUE;
      } else if (h->next == NULL && vrijeBytes == 0 && a->adres == adres) {
        /* Blok komt aan het einde van het geheugen */
        vrijeBytes = a->size;
        if (pa != NULL) {
          pa->next = a->next;
          h->next = a;
        } else {
          tmpa = a->next;
          h->next = a;
          a = tmpa;
          *allocLijst = a;
        }
        if (a == NULL)
          breakDadelijk = TRUE;
      }
      ph = h;
      h = h->next;
    }
    if (a == NULL)
      break;
    pa = a;
    a = a->next;
  }

  return vrijeBytes;

} /* vrijgevenGeheugen */


int claimGeheugen (Element **freeLijst, Element **allocLijst, int aantalBytes) {
/* pre : aantalbytes > 0
   post: Als er geen geheugenblok ter grootte hoevelheid meer aanwezig is
         Dan claimGeheugen(freeLijst,allocLijst,aantalBytes)=0
         Anders claimGeheugen(freeLijst,allocLijst,aantalBytes)= het eerst
            voorkomend adres in *freeLijst waar een geheugenblok ter grootte
            aantalbytes aanwezig is (dit geheugen is geallocoord en niet meer
            vrij beschikbaar) en het vrijgegeven adres met aantalbytes is
            opgenomen in *allocLijst.
*/

  Element  *h = *freeLijst, *a = *allocLijst;
  int vrijGeheugen = 0;

  while (h != NULL) {
    if (h->size >= aantalBytes && vrijGeheugen == 0) {
      vrijGeheugen = h->adres;
      h->adres += aantalBytes;
      h->size -= aantalBytes;
      break;
    }
    h = h->next;
  }

  if (vrijGeheugen == 0)
    return 0;

  if (*allocLijst == NULL) {
    *allocLijst = (Element *) malloc(sizeof(Element));
    (*allocLijst)->size = aantalBytes;
    (*allocLijst)->adres = vrijGeheugen;
    (*allocLijst)->next = NULL;
  } else {
    while (a->next != NULL)
      a = a->next;
    a->next = (Element *) malloc(sizeof(Element));
    a->next->size = aantalBytes;
    a->next->adres = vrijGeheugen;
    a->next->next = NULL;
  }

  return vrijGeheugen;

} /* claimGeheugen */


void opruimenLijst (Element **lijst) {
/* pre : *lijst = NULL of lijst wijst naar een lineaire lijst waarvan het laatste
         element de pointer next gelijk aan NULL heeft
   pos : Het geheugen waar *lijst naar wijst is opgeruimd
*/

  if (*lijst != NULL) {
    Element *h = (*lijst)->next, *t;

    free(*lijst);

    while (h != NULL) {
      t = h->next;
      free(h);
      h = t;
    }
  }

} /* opruimenLijst */


int main (int argc, char *argv[]) {

  Element *allocLijst = NULL, *freeLijst = NULL;
  int aantalBytes, adres;
  char antwoord;
  bool stoppen;

  /* initialisate van lijsten dus freelijst bevat alle geheugen en alloc is leeg */
  freeLijst = (Element *) malloc(sizeof(Element));
  freeLijst->size = TOAALBESCHIBAARGEHEUGEN;
  freeLijst->adres = 1;
  freeLijst->next = NULL;
  allocLijst = NULL;

  stoppen = FALSE;
  while (!stoppen) {
    printf("\n\nMENU");
    printf("\n===========================");
    printf("\n[1] Tonen free lijst");
    printf("\n[2] Tonen alloc lijst");
    printf("\n[3] Claimen geheugen");
    printf("\n[4] Vrijgeven geheugen");
    printf("\n[5] Stoppen.");
    printf ("\n\nKeuze : ");
    antwoord = getch();
    printf("\n\n");

    switch (antwoord) {
      case '1':
        printf("\nFreeLijst\n");
        toonLijst(freeLijst);
      break;
      case '2':
        printf("\nAllocLijst\n");
       toonLijst(allocLijst);
      break;
      case '3':
        printf("\nGeef aantal bytes : ");
        scanf("%d", &aantalBytes);
        adres = claimGeheugen(&freeLijst,&allocLijst,aantalBytes);
        if (adres == 0)
          printf("\nEr is geen voldoende vrij geheugen meer aanwezig.");
        else
          printf("\nHet volgende adres is vrijgegeven : %d",adres);
      break;
      case '4':
        printf("\nGeef het vrij te geven adres : ");
        scanf("%d", &adres);
        aantalBytes = vrijgevenGeheugen(&freeLijst,&allocLijst,adres);
        if (aantalBytes==0)
          printf("\nHet opgegeven adres komt niet voor in alloc lijst.");
        else
          printf("\nAdres %5d met ter grootte %d is vrijgegeven.",adres,aantalBytes);
      break;
      case '5':
        stoppen = TRUE;
      break;
    }
    if (antwoord != '5') {
      printf ("\n\nDruk op een toets om terug te keren  naar menu.");
      getch();
    }
  }

  /* opruimen van de lijsten */
  opruimenLijst(&freeLijst);
  opruimenLijst(&allocLijst);

  return 0;
} /* main */