#include "speicher.hh"

const int halden_groesse = 32768;

// Struktur der Speicherbloecke in der Freispeicherliste:
// Kopf mit zwei Worten (GROESSE, VERKETTUNG), dann eigentlicher Inhalt

enum {
    GROESSE = 0,		// Groesse in Worten (inkl. Kopf)
    VERKETTUNG = 1,		// Verkettung auf naechsten Kopf
    KOPFGROESSE = 2		// ab hier "Nutzlast" */
};

// Das "NIL" fuer unsere Freispeicherliste

const int verkettungs_ende = -1;

// Die Halde:
// Freispeicherliste initialisiert mit:
//   heap[0+GROESSE] = halden_groesse, heap[0+VERKETTUNG] = verkettungs_ende

Wort heap[halden_groesse] = { halden_groesse, verkettungs_ende };

// Der Index des Kopfes der Freispeicherliste in der Halde

int frei_index = 0;		// Initial: Verweis auf initialen grossen Block


Zeiger anlegen(int groesse) {
    groesse+=KOPFGROESSE;		// Platz fuer Kopf noetig


	int i = frei_index;
	int preferred_index = -1;
	int prev_i = i;

	do {
		//Freispeicher komplett dem User geben weil kein Spalten mehr möglich
		if(heap[i] >= groesse && heap[i] <= groesse+2) {
			heap[prev_i+1] = heap[i+1]; //Speicherbereich aus Liste entfernen
			return &heap[i+KOPFGROESSE];
		}
		//passenden Freispeicher gefunden, aber zu gross -> durchlaufen bis best fit
		else if(heap[i] > groesse+2) {
			//Falls schon ein fit gefunden wurde
			if(preferred_index > -1) {
				//falls ein besserer fit gefunden wurde
				if(heap[preferred_index] > heap[i]) preferred_index = i;
			}
			//falls bisher noch kein fit gefunden wurde
			else preferred_index = i;
		}
		prev_i = i;
		i = heap[i+1];
	}while(i != -1);

	//ungenügender freier speicher
	if(preferred_index == -1) return 0;


	//Split index finden
	int split_index = preferred_index + heap[preferred_index]-groesse;
	//Reservierte groesse vom alten Block abziehen
	heap[preferred_index] -= groesse;
	//groesse des neuen blocks festlegen
	heap[split_index] = groesse;
	return &heap[split_index+KOPFGROESSE];
}

void freigeben(Zeiger speicher_block) {
  /* Aufnehmen von speicher_block in die Freispeicherliste */

	int * verkettungs_index = speicher_block-1;
	int * groesse = speicher_block-2;

	//Freispeicher in verkettete Liste einhängen
	*verkettungs_index = frei_index;
	frei_index = groesse - heap;
}