#1 4. November 2014 Hey Leute, bin totaler Neuling in C. Und muss demnächst eine Aufgabe abgeben, leider komme ich dabit noch nicht so ganz zurecht und hoffe auf eure Hilfe. Ich muss eine Freispeicherliste implementieren. Dabei soll der Heap durch ein ausreichend großes Byte-Array "memPool" simuliert werden: PHP: char memPool [ MEM_POOL_SIZE ]; Die freien Blöcke sollen über eine einfach verlinkte Liste verwaltet werden. Dazu enthält jeder Block im simulierten Heap am Anfang eine Verwaltungsstruktur, die die nutzbare Länge des Blocks (d.h. Gesamtlänge des Blockes minus Länge der Verwaltungsstruktur; in Bytes) und einen Zeiger auf den Anfang des nächsten freien Blocks enhält: PHP: typedef struct MemBlock { size_t size ; struct MemBlock * next ; } MemBlockT ; Der next-Pointer des letzten Blocks ist ein Null-Pointer. Der Pointer freeMem (Typ: MemBlockT*) zeigt auf den Anfang der Freispeicherliste. Belegte Blöcke sollen nicht in der Freispeicherliste verwaltet werden, sie behalten aber ihre Verwaltungsstruktur am Anfang des Blockes. Um belegte Blöcke extra kenntlich zu machen, soll der next-Pointer belegter Blöcke den „magischen“ Integerwert 0xacdcacdc enthalten. Nun habe ich bis jetzt folgendes zustande gebracht und weiß einfach nicht was ich als nächstes tun soll, wenn ich die Malloc hinbekommen würde wäre ich schon ein Stückchen weiter. Vielleicht sehe ich den Wald vor lauter Bäumen nicht ... Fehler erhalte ich nicht, jedoch erhalte ich auch nicht das richtige Ergebnis PHP: extern char memPool [ MEM_POOL_SIZE ]; extern struct MemBlock * freeMem = 0 ; unsigned int heap_size ; void initHeap ( void ) { freeMem =( struct MemBlock *) memPool ; freeMem -> size = sizeof ( memPool ); freeMem -> next = 0 ; return; } void * myMalloc ( size_t size ) { heap_size = MEM_POOL_SIZE ; static int heap_inited = 0 ; if(! heap_inited ) { heap_inited = 1 ; initHeap (); } int malloc_size = sizeof ( size ) + sizeof ( freeMem ); struct MemBlock * curr = freeMem ; struct MemBlock * next = NULL ; while( curr ) { if( curr -> size >= malloc_size ) { curr -> size = malloc_size ; curr -> next = curr + malloc_size ; // INIT NEXT BLOCK next = curr -> next ; heap_size -= malloc_size ; next -> next = NULL ; next -> size = heap_size ; free ( next ); curr = curr + sizeof ( struct MemBlock ); print_heap_allocations (); return curr ; } curr = curr -> next ; } return NULL ; } + Multi-Zitat Zitieren
#2 8. November 2014 AW: C Heap mit Char simulieren Ich bin noch halb im Autopilot, von daher kann ich total falsch liegen, allerdings scheint es mir offensichtlich, dass Du mit den Größen ein wenig herumgeschludert hast. Aktuell sieht es so aus das Du den Blöcken jeweils immer exakt 8 Bytes an Speicher zuteilst. malloc_size gibt momentan nur die Größe der Verwaltungsstruktur für jeden Block an (btw.: sizeof(struct MemBlock) ist da etwas eleganter). Das ist eigentlich auch ausreichend da Du ja mit size (dem Funktionsargument von myMalloc) schon die Blockgröße hast, überarbeite also diese Teile und Du solltest deine erwarteten Ergebnisse bekommen. Etwas anderes: Sicherheit- und Algorithmenchecks und dergleichen. 1. Am Anfang solltest Du ganz simpel überprüfen ob es überhaupt noch genug Speicher gibt das Du zurückgeben könntest oder nicht. 2. Entweder rufe immer initHeap() auf und mach dort die static-checks ob alles initiiert wurde und lasse myMalloc() frei davon oder schreibe eine Macro und deklariere eine globale Variable und regel das so, was sogar noch besser wäre da andere Funktionen so die Möglichkeit besäßen zu gucken ob alles i.O. ist oder nicht und bei etwas so essentiellem wie einem Heap machen globale Variablen auch nichts aus. Hoffe die Antwort kam rechtzeitig genug damit. Viel Erfolg und so + Multi-Zitat Zitieren