heap.cpp

Jazmyn is a 32-bit, protected mode, multitasking OS which runs on i386 & above CPU`s. Its complete

/*
 * Copyright (C) 2004, Thejesh AP. All rights reserved.
 */

/*
 *A doubly linked list mainains the free space in the heap.
 *Heap uses first fit startegy.
 */

#include <sys\types.h>
#include <null.h>
#include <stdlib.h>
#include <drivers\console.h>
#include <drivers\keyboard.h>
#include <mm\heap.h>

extern keyboard _keyboard_obj;

#define _S(obj)         (sizeof(obj))
#define	HEAP_SIZE	(this->limit-_S(mem_chunk))
#define	BASE(m)		((uint)m+_S(mem_chunk))

heap::heap()
{

}

heap::~heap()
{

}

void heap::init_heap(uint base,uint limit)
{

	this->base = base;
	this->limit = limit;
	head = (mem_chunk*)this->base;
	head->free = TRUE;
	head->size = HEAP_SIZE;
        head->next = NULL;
	head->prev = NULL;
	tail = head;
        if(limit >= 0x800000)
        {
                cout<<"Initializing Kernel Heap                        [OK]"<<endl;
                cout<<"[Heap Start] = "<<this->base<<"  [Heap  Limit] = "<<this->limit<<endl;
        }
}

void* heap::malloc(uint size)
{

	if(size == 0) return NULL;
	if(size > HEAP_SIZE) return NULL;
	mem_chunk *m = head;

	if(m->next == NULL)     //empty heap
	{
		/*size is small enough to create new chunk*/
                if(size + _S(mem_chunk) < HEAP_SIZE)
		{
			/*initialize new chunk*/
			mem_chunk *n = (mem_chunk*)(BASE(m)+size);
			n->size = HEAP_SIZE-(size+_S(mem_chunk));
			n->next = NULL;
			n->prev = m;
			n->free = TRUE;
			tail = n;
			/*update old chunk*/
			m->size = size;
                        m->next = n;
		}
		/*size is too big to create new chunk*/
		m->free = FALSE;
                return (void*)BASE(m);
	}
        while(m!=NULL)
	{
                if((size <= m->size) && m->free)
		{
			/*size is small enough to create new chunk*/
                        if(size + _S(mem_chunk) < m->size)
			{
				/*initialize new chunk*/
				mem_chunk *n = (mem_chunk*)(BASE(m)+size);
				n->size = m->size-(size+_S(mem_chunk));
				n->prev = m;
				n->next = m->next;
				if(n->next == NULL)
				tail = n;
				n->free = TRUE;
				/*update old chunk*/
				m->size = size;
				m->next = n;
			}
			/*size is too big to create new chunk*/
			m->free = FALSE;
			return (void*)BASE(m);
		}
		m = m->next;
	}
}

void heap::free_above(mem_chunk *h)
{
	mem_chunk *m = h;
	m->free = TRUE;
	m = m->next;
	while(m != NULL)
	{
		if(!m->free) break;
		h->next = m->next;
                (m->next!=NULL) ? m->next->prev = h : tail = m->prev;
		h->size += m->size + _S(mem_chunk);
		m = m->next;
	}
}

void heap::free_below(mem_chunk *t)
{
        mem_chunk *m = t;
	t->free = TRUE;
	m = m->prev;
	while(m != NULL)
	{	
		if(!m->free) break;
                if(t == tail)
                {
                        m->next = NULL;
                        tail = m;
                }
                else
                {
                        m->next = t->next;
                        t->next->prev = m;
                }
		m->size += t->size + _S(mem_chunk);
		t = t->prev;
		m = m->prev;
	}
}

void heap::free(void *addr)
{
	if(addr == NULL) return;
        if((uint)addr == BASE(head))
	{
		free_above(head);
	}
        else if((uint)addr == BASE(tail))
	{
                free_below(tail);
	}
	else
	{
		mem_chunk *m = head->next;
                while(m != tail)
		{
			if((uint)addr == BASE(m))
			{
				free_above(m);
                                free_below(m);
				break;
			}
			m = m->next;
		}
	}
}

void* heap::realloc(void *addr,uint newsz)
{
	/*
	 *This is very simple realloc(),it just mallocs new memory, copies the old memory
	 *contents & frees the old memory.
	 */

	if(newsz == 0) return NULL;
	if(newsz > HEAP_SIZE) return NULL;
	void *newaddr = malloc(newsz);
	if(!newaddr) return NULL;
	mem_chunk *m = head;
        while(m!=NULL)
	{
                if(BASE(m) == (uint)addr)
		{
                        memcpy(newaddr,addr,m->size);
			break;
		}
		m = m->next;
	}
	free(addr);
        if(m == NULL) {free(newaddr);return NULL;}
	return newaddr;
}		

heap& heap::operator=(heap &parent)
{
	base = parent.base;
	limit = parent.limit;
	head = parent.head;
	tail = parent.tail;
        return *this;
}

void heap::display()
{
        mem_chunk *m = head;
        while(m!=NULL)
        {
                cout<<"free   :"<<m->free<<" "
                    <<"size   :"<<m->size<<" "
                    <<"next   :"<<(uint)m->next<<" "
                    <<"prev   :"<<(uint)m->prev<<endl;
                m = m->next;
                getch();
        }
}
heap    _heap_obj;