Looks good Arlet. Economical and efficient.
For a heap management I've been using a header structure like this (16 bytes on a 32 bit machine):
Code:
// This structure is only known to the memory routines.
typedef struct tagMEM {
int checkstr;
int size;
struct tagMEM *next;
int resv;
} MEM;
checkstr is a four byte ascii string 'MBK' (3 chars plus 0). Checkstr helps in cases of writing too much data to a buffer.
size is the size of the memory allocation including the header.
next is a pointer to the next available block of memory
resv is four bytes padding reserved.
Both the size (which is rounded to size of the header) and a pointer to the next block are maintained. This is a little bit
redundant but may have been done to improve performance.
The memory functions maintain a semaphore for thread safety.
On a free() the operation has to chase down the chain representing the free list as blocks need to be maintained on the list
in memory address order.
Free() combines neighbouring blocks into a larger one.
Code:
// Free a block of memory
void freeMem(void *m)
{
MEM *p;
MEM *prev;
MEM *next;
MEM *mem;
if (m==null)
return;
mem = &((MEM*)m)[-1];
if (mem->next) // is block already free ?
return;
spin_lock(&sfFreeMem);
p = freeMemList;
if (p==null) {
freeMemList = mem;
mem->next = 0;
spin_unlock(&sfFreeMem);
return;
}
for (prev = null; p && p < mem; prev = p, p = p->next);
if (!prev) {
mem->next = freeMemList;
freeMemList = mem;
}
else {
mem->next = prev->next;
prev->next = mem;
}
next = mem->next;
// Can it be combined with next ?
if ((char *)mem + mem->size>=(char *)next) {
mem->size = mem->size + next->size;
mem->next = next->next;
}
// Can it be combined with the previous ?
if ((char*)prev + prev->size>=(char *)mem) {
prev->size = prev->size + mem->size;
prev->next = mem->next;
}
spin_unlock(&sfFreeMem);
}
allocMem() uses a first fit algorithm so I've not shown it. I'll have to re-write it for the challenge.
Login
Register
FAQ
Search
