Dynamische Speicherverwaltung mit Heap und FIrst-Fit

[Erls]

Wir haben folgende Aufgabe bekommen:
Die Vorgabe geht von einem Array von ,,Worten‘‘ (hier: Datentyp int) namens heap aus.
Aus diesem kann mit der Funktion anlegen(groesse) Speicher angefordert werden.
Dabei wird intern ein Kopf aus zwei zusätzlichen Worten (KOPFGROESSE = 2) mitreserviert,
der später für die Freispeicherliste gebraucht wird. In diese beiden Worte sollen die
Größe des Speicherbereichs inklusive Kopf (Offset GROESSE = 0) und die Verkettungsinformation
für die Freispeicherliste (Offset VERKETTUNG = 1) geschrieben werden.
Das Array heap wird so initialisiert, dass sich ein einzelnes Element mit der maximalen
Größe halden_groesse und der Verkettung verkettungs_ende (,,kein weiteres
Element in der Freispeicherliste‘‘) darin befindet; frei_index verweist auf den Anfang der Freispeicherliste
Die Funktion anlegen(groesse) soll einen Null-Pointer zurückliefern, falls in dem
vorgegebenen Feld heap kein Platz mehr für die Anforderung vorhanden ist. Andernfalls
liefert sie (wenn first_fit der Offset des gefundenen Bereichs in heap ist) dem Nutzer
mittels return &heap[first_fit+KOPFGROESSE] die Speicheradresse des
ersten Wortes hinter dem Kopf zurück.
Entsprechend wird in der Funktion freigeben(p), die wir vorgegeben haben, die
KOPFGROESSE wieder abgezogen, bevor auf den Kopf zugegriffen wird. Der freigegebene
Bereich wird einfach an den Anfang der Liste gestellt
Die Funktion anlegen(groesse) kann, wenn sie ihren ,,First Fit‘‘ gefunden hat, auf
zwei Fälle stoßen:

1. Der Bereich ist groß genug für die Anforderung, aber nicht groß genug, um weiter
   aufgespalten zu werden (dafür müßten noch mindestens zwei Worte für einen neuen
   Kopf und ein weiteres Wort für den Nutzer da sein).
   In diesem Fall soll der Bereich ganz aus der verketteten Freispeicherliste entfernt
   und dann dem Nutzer bereitgestellt werden.
2. Der Bereich ist groß genug für ein Aufspalten. In diesem Fall ist es hier am einfachsten,
   den dem Nutzer bereitzustellenden Bereich hinten vom gefundenen Block
   abzuspalten — dann muss man die Verkettung nicht verändern.

Und ich bräuchte einen Lösungsansatz dazu, da mir garnicht klar ist wie anlegen(groesse) aussehen muss. Hab viel im Netz gesucht aber nichts passendes gefunden.

[SeppJ]

Nun, da steht doch schon so einiges als Lösungsansatz in der Aufgabe. Was willst du konkret noch weiter wissen? Was hast du dir denn schon überlegt? Wenn du das zeigst, kann man darauf ja mal aufbauen.

[Erls]

Also bist jetzt habe ich folgendes

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

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

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

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

    // Hier gehoert Eure Loesung hin.
    // Irgendwo darin sollten diese beiden Zeilen stehen:
    //return &heap[first_fit+KOPFGROESSE];// erfolgreiche Rueckgabe
    // bzw.:
    //return 0;				// Kein Speicher mehr da
    int first_fit;
    for(first_fit = 0; i < halden_groesse; i++){

    }
}

Das Problem ist wohl das ich die Aufgabenstellung nicht verstehe. Ich brauch sowas wie ne Anweisung, wie kann ich prüfen ob ein Block frei ist oder nicht Wie läuft das mit dem verketten, wie kann ich die Liste durchlaufen. Dazu fällt mit nichts ein, ich habe keinen Ansatz. Und aus dem Text kann ich auch keinen lesen.

[SeppJ]

Es geht hier nicht um das verketten fertiger Anweisungen aus der Standardbibliothek. Sonst könntest du auch gleich malloc nehmen. Du musst über das Problem nachdenken und dann eine eigene Lösung ohne Nutzung der Standardbibliothek entwickeln.
Du musst dir irgendwo die Verwaltungsdaten merken, welcher Block belegt ist und dir Algorithmen ausdenken die dem beschriebenen Anforderungsschema entsprechen.