first fit algorithmus

malloc.c

#include "memory.h"
#include <stdio.h>
#include <errno.h>

/* Do not change !! */
static char mem[4096];

static size_t MEMSIZE = 4096;
// BLOCKGROESSE: 1 byte

// Referenz:
// http://www.memorymanagement.org/articles/alloc.html

#ifdef BUDDY
void *bs_malloc(size_t size)
{


   // makro dass den zum betriebssystem passenden error code 
   // fuer "error no memory" zurueckgibt
   errno=ENOMEM; 
   return NULL;
}

void bs_free(void *ptr)
{
}
#endif 

#ifdef FIRST

/*
In the first fit algorithm, the allocator keeps a list of free blocks (known as the free list) and, on receiving a request for memory, scans along the list for the first block that is large enough to satisfy the request. If the chosen block is significantly larger than that requested, then it is usually split, and the remainder added to the list as another free block.

The first fit algorithm performs reasonably well, as it ensures that allocations are quick. When recycling free blocks, there is a choice as to where to add the blocks to the free list -- effectively in what order the free list is kept. 
*/

// free list element
typedef struct memblock memblock;
struct memblock {
	unsigned int blocksize; // => unsigned int
	char* start;
	memblock* next;
	char used;
};

memblock* freelist; 

void *bs_malloc(size_t size)
{
	// erstmaliger aufruf: freelist initialisieren
	if (freelist == NULL)
	{
		
		memblock first = {4096, &mem[0], NULL, 0};
		freelist = &first;
		printf("initialized. free list saved at %p\n", freelist);
	}

	// ersten freien block finden
	memblock* m = freelist;

	do
	{
		printf(" block: [%d, %d] \n", m->blocksize, m->used);
		if (m->used == 0 && m->blocksize >= size)
		{
			// block teilen, in liste einsetzen, pointer zurueckgeben
			memblock n = {(m->blocksize - size), (m->start + size), m->next, 0};
			m->used = 1;
			m->blocksize = size;
			memblock x;
			printf("yeeeah I allocated! %p %p %p\n", &n, m, &x);
			m->next = &n;
			return m->start;
		}
		if (m->next == m ) {printf("wtf.\n"); break;}

	}
	while( (m = m->next) && (m != NULL)); // gucken ob naechstes element existiert und ggf. reinwechselt

	// wenn kein block gefunden, error code setzen und nullpointer returnen
   errno=ENOMEM;
   return NULL;
}

void bs_free(void *ptr)
{
}
#endif