/* 19Jun24: NEGATIV-Beispiel (II) einer Stack Implementierung.
 *
 * Hier wollen wir die Erlauben in beliebiger Reihenfolge Speicher
 * anzufordern und freizugeben.  Hierzu teilen wir den verwalteten
 * Speicher in eine feste Anzahl an Festen Speicherbereichen, welche
 * ganz vergeben werden.  Ob ein Speicherbereich vergeben wurde, wird
 * AUßERHALB mit einem quasi-"Bit-Vektor" verwaltet.  Das
 * unterschiedet sich auch zu der eigentlichen Aufgabe, wo die
 * Verzeichnisstrukturen sich innerhalb von dem verwaltetem
 * Speicherbereich selbst befinden.
 *
 * Vorteile von dem Ansatz sind dass man wie malloc(3) es eigentlich
 * will, Speicher in Beliebiger Reihenfolge Anfragen und Freigeben
 * kann.  Suche von Speicherbereichen benötigt 𝒪(n) viel Zeit, aber
 * Freigabe geht in 𝒪(1).
 *
 * Nachteile sind, sowohl dass man ineffizient Speicher vergibt
 * (interner Verschleiß, ähnlich zu Seiten-Basierten Virtualisierung
 * im Betriebsystem), aber auch dass Speicherbereiche erstmal nicht
 * über einen "Bucket" hinaus vergeben werden können -- das Problem
 * wäre aber mit einem etwas komplexeren Algorithmen in 𝒪(n²) findbar.
 * 
 * Im wesentlichem ist das der schlechteste Ansatz um die
 * Mindestanforderung von malloc(3) zu genügen. */

/* -> Siehe Kommentare in halde-stack.c */
#define _GNU_SOURCE
#include "halde.h"

#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <unistd.h>
#include <assert.h>
#include <sys/mman.h>

/* Wir legen hier fest wie viel Speicher, und wie granular der
 * Speicher geteilt wird.  Spezifisch,  */
#define SIZE (1024*1024*1)
#define BUCKETS (1024)

static char memory[SIZE];
static bool reserved[BUCKETS];

void *malloc(size_t size) {
     /* Wir können leicht überprüfen ob es überhaupt möglich ist genug
      * Speicher zu vergeben, indem wir sicher gehen dass weniger
      * Speicher gefragt wird, als in einem Bucket passt.  Wenn das
      * nicht der Fall ist, dann brechen wir gleich ab mit ENOMEM.  */

     /* Wir setzen `errno' gleich am Anfang, auch wenn wir eine
      * Speicherstelle finden, weil es für den Aufrufer nur dann
      * erlaubt ist `errno' zu prüfen, wenn es einen Fehler gegeben
      * hat. */
     errno = ENOMEM;

     if (size <= SIZE/BUCKETS) {

          /* Um eine freien Bucket zu finden, durchsuchen wir schlicht
           * den Bit-Vektor nach einer freien Stelle. */
          for (unsigned i = 0; i < BUCKETS; i++) {
               if (reserved[i]) {
                    continue;
               }

               /* Haben wir eine frei Stelle gefunden, berechnen wir
                * die Adresse in "memory" die gleich vergeben wird,
                * und markieren den Bucket als vergeben. */
               reserved[i] = true;
               return  memory + (SIZE/BUCKETS) * i;
          }

          /* Terminiert die Schleife, haben wir keinen Speicherbereich
           * gefunden, und geben NULL zurück.  `errno' wurde bereits
           * gesetzt.  */
     }

     return NULL;               /* Fehlerfall */
}


void free(void *vptr) {
     if (vptr == NULL) return;

     char *ptr = vptr;          /* cast void* -> char* */

     /* Hier benutzen wir assert(3) anstatt abort(3), was aber im
      * wesentlichem den gleichen Effekt hat.  Bei dem assert(3) Makro
      * geben wir direkt eine Bedingung an, die aus der Konsistenz
      * eines System folgen sollte.  Ist in diesem Fall
      *
      * - ptr nicht ein Zeiger auf den Anfang von einem Bucket, oder
      * - ptr nicht der Zeiger auf einen vergebenen Speicherbereich,
      *
      * dann brechen wir die Ausführung gleich ab.  Diese Kontrollen
      * kann man aber mit "-DNDEBUG" während der Übersetzung
      * deaktivieren, also handelt es sich NICHT um eine gültige
      * Fehlerbehandlung -- was hier auch gar nicht die Absicht ist. */
     assert(((ptr - memory) % SIZE/BUCKETS) == 0);
     assert(reserved[((ptr - memory) % SIZE/BUCKETS)]);

     /* Die Freigabe eines Speicherbereich heißt nur im Bit-Vektor
      * markieren, dass jetzt ein Bucket wieder vergeben werden
      * kann. */
     reserved[((ptr - memory) % SIZE/BUCKETS)] = false;

     /* Hier eine andere Funktion welche freigegeben Speicher
      * invalidiert, nachdem es benutzt wurde, um leichter Fehler in
      * einer Anwendung zu erkennen.  Das ist natürlich nicht
      * notwendig und macht die Anwendung langsamer, aber ist im
      * erlaubtem Rahmen von free(3). */
     memfrob(vptr, SIZE/BUCKETS);
}

/**********************************************************************/
/* ACHTUNG: Diese Datei enthält keine Implementierung von calloc(3)   */
/* und realloc(3).  Diese Funktionen sind jedoch für die Aufgabe 5 zu */
/* implementieren.  Programme welche man gegen dieses Modul bindet    */
/* könnten sich möglicherweise Falsch verhalten, wenn es unsere               */
/* `malloc' und realloc(3) kombinierend!                              */
/**********************************************************************/