メモリ管理

struct memblock {
    int size;
    unsigned char magic;
    unsigned char occupied;
    struct memblock *next;
    struct memblock *prev;
};

#define HEADER_SIZE (sizeof(struct memblock))

#define DELTA 20

#define MEM_MAGIC 0xa5

#define WORDSIZE 4

#define WORD_ALIGN(n) (((n) + WORDSIZE - 1) & -WORDSIZE)

struct memblock block_chain;

#define HEAP_SIZE 10000
char memory_heap[HEAP_SIZE];

void initialize_memory()
{
    struct memblock *h;
    
    h = (struct memblock *)memory_heap;
    block_chain.size = sizeof(block_chain);
    block_chain.magic = MEM_MAGIC;
    block_chain.occupied = 1;
    block_chain.next = block_chain.prev = h;
    
    h->size = HEAP_SIZE;
    h->magic = MEM_MAGIC;
    h->occupied = 0;
    h->next = h->prev = & block_chain;
}

void *allocate_block(int size)
{
    struct memblock *p, *s;
    int nbytes;
    
    nbytes = WORD_ALIGN(size + HEADER_SIZE);
    
    for (p = block_chain.next; p != &block_chain; p = p->next){
        
        if(!p->occupied && p->size >= nbytes){
            if (p->size - nbytes > DELTA){
                s = (struct memblock *)((char *)p + nbytes);
                s->size = p->size - nbytes;
                s->magic = MEM_MAGIC;
                s->occupied = 0;
                
                p->next->prev = s;
                s->next = p->next;
                p->next = s;
                s->prev = p;
                
                p->size = nbytes;
                p->occupied = 1;
            } else
                p->occupied =1;
            
            return (char *)p + HEADER_SIZE;
        }
    }
    return NULL;
}

void free_block(void *block)
{
    struct memblock *mem;
    
    mem = (struct memblock *)((char *)block - HEADER_SIZE);
    
    if(mem->magic != MEM_MAGIC)
        return;
    
    if (! mem->prev->occupied){
        mem->next->prev = mem->prev;
        mem->prev->next = mem->next;
        mem->prev->size += mem->size;
        mem = mem->prev;
    }
    
    if(! mem->next->occupied){
        mem->next->next->prev = mem;
        mem->size += mem->next->size;
        mem->next = mem->next->next;
    }
    mem->occupied = 0;
}