//----------------------------------------------------------------------------
// Работа с кучей. Заголовочный файл.
//
// Структура кучи:
// |t_dynamem_descr| memory part |t_dynamem_descr| memory part |...|t_dynamem_descr| memory part |
// где
// t_dynamem_descr - описатель элемента памяти (см. ниже)
// memory part - элемент памяти, который описывается соответствующим описателем
//
// Поле next_dynamem_descr описателя последнего элемента памяти всегда указывает
// на описатель первого элемента (циклическая структура структура).
// Поле prev_dynamem_descr описателя первого элемента памяти указывает
// на первый элемент (сам на себя).
//----------------------------------------------------------------------------
#include <mm/heap.h>
//----------------------------------------------------------------------------
// Для отладки модуля должен быть определен символ :
// #define MALLOC_DEBUG 1
// или в командной строке должен быть задан ключ
// -DMALLOC_DEBUG=1
//----------------------------------------------------------------------------
// Если отладочная версия, то определим макросы запрещения и разрешения
// прерываний (если они не определены ранее)
//----------------------------------------------------------------------------
#ifdef MALLOC_DEBUG
// Марос ATOMIC_BEGIN() - определяет начало фрагмента,
// который не может быть прерван
#ifndef ATOMIC_BEGIN
#define ATOMIC_BEGIN()
#endif /* ATOMIC_BEGIN */
// Марос ATOMIC_END() - определяет конец фрагмента,
// который не может быть прерван
#ifndef ATOMIC_END
#define ATOMIC_END()
#endif /* ATOMIC_END */
//
#else
// Если версяя рабочая, то включаем определения макросы
// запрещения и разрешения прерываний
#include <atomic/atomic.h>
#endif /* MALLOC_DEBUG */
//----------------------------------------------------------------------------
// Определяем функции печати для отладки
//----------------------------------------------------------------------------
#ifdef MALLOC_DEBUG
//--------------------------------------------------------------------------
// Для использования своей функции печати, отличной от dbg_printf()
// Должен быть определен макрос NOSTD_DBG_PRINTF
// Например, для использования функции printf() для отладки, должен быть
// определен макрос
// #define NOSTD_DBG_PRINTF printf
// или в командной строке должен быть задан ключ
// -DNOSTD_DBG_PRINTF=printf
//--------------------------------------------------------------------------
#ifndef NOSTD_DBG_PRINTF
#define NOSTD_DBG_PRINTF dbg_printf
#endif /* PRINTF_HAVING */
// Print memory block
void prmembl(t_heap_el* mblk)
{NOSTD_DBG_PRINTF("void* next_dynamem_descr 0x%x\n",mblk->next_dynamem_descr);
NOSTD_DBG_PRINTF("void* prev_dynamem_descr 0x%x\n",mblk->prev_dynamem_descr);
NOSTD_DBG_PRINTF("void* this_memory_part 0x%x\n",mblk->this_memory_part);
NOSTD_DBG_PRINTF("unsigned int this_memory_size 0x%x\n",mblk->this_memory_size);
NOSTD_DBG_PRINTF("unsigned int flags 0x%x\n",mblk->flags);
}
// Print memory block of pointer
void prmemptr(void* mptr)
{prmembl( (t_heap_el*) ( ((unsigned int)(mptr)) - sizeof(t_heap_el)) );
}
#endif /* MALLOC_DEBUG */
//----------------------------------------------------------------------------
// Инициализирует кучу 'heap'.
// heap_begin - адрес начала кучи
// heap_size - размер кучи (включая все описатели)
// Куча занимает в памяти адресное пространство
// от heap_begin до (heap_begin+heap_size-1)
//----------------------------------------------------------------------------
void l_heapinit(t_heap* heap, void* heap_begin, int heap_size)
{t_heap_el* tdd;
// Первый элемент, текущий элемент
tdd = heap->curel = heap->firstel = heap_begin;
// Циклическая структура
tdd->next_dynamem_descr=tdd;
// Предыдущий за первым элементом - он же (указатель на самого себя)
tdd->prev_dynamem_descr=tdd;
// Указатель на элемент памяти
tdd->this_memory_part = (void*)(((int)(tdd))+sizeof(t_heap_el));
// Размер элемента памяти
tdd->this_memory_size = heap_size - sizeof(t_heap_el);
// Элемент памяти свободен
tdd->flags = 0x00000000;
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("Memory after init:\n");
prmembl(heap_begin);
NOSTD_DBG_PRINTF("\n");
#endif /* MALLOC_DEBUG */
// После инициализации куча представляет собой список из одного элемента,
// который имеет размер кучи минус размер описателя элемента.
// Т.е. вся куча - это один свобоный элемент памяти
}
//----------------------------------------------------------------------------
// Резервирует память в куче 'heap', для размещения массива из 'nmemb' элементов,
// каждый из которых имеет размер 'size'
// Возвращает указатель на зарезервированную память
// Если в куче не достаточно памяти, то возвращает NULL
//----------------------------------------------------------------------------
void* l_calloc(t_heap* heap,int nmemb,int size){return(l_malloc(heap,nmemb*size));}
//----------------------------------------------------------------------------
// Резервирует память в куче 'heap', размером 'size' байт.
// Возвращает указатель на зарезервированную память
// Если в куче не достаточно памяти, то возвращает NULL
//----------------------------------------------------------------------------
void* l_malloc(t_heap* heap, unsigned int size)
{// Запрещаем прерывания
ATOMIC_BEGIN();
// Временные переменные
t_heap_el* tptr=heap->curel; // Поиск начинается с текущего элемента
t_heap_el* tptrn;
// Возвращаемый указатель
void* retptr;
// Когда exit==1, заканчиваем цикл поиска
int exit=0;
// Выравнивание по заданной границе
#ifdef HEAP_ALIGN
if(size & (HEAP_ALIGN-1))
{size = size + (HEAP_ALIGN - (size & (HEAP_ALIGN-1)));
}
#endif
// Основной цикл поиска
while(!exit)
{// Если найден свободный элемент...
if(!(tptr->flags & DM_BUSY))
{// Проверяем размер
if(tptr->this_memory_size == size)
{// Требуемый и найденный размеры памяти равны
tptr->flags |= DM_BUSY; // Резервируем блок
retptr = tptr->this_memory_part; // Возвращаем указатель на текущий эл-т
heap->curel = tptr->next_dynamem_descr; // Текущий указатель переставляем
// на следующий эл-т
exit=1; // Выходим
}
else if((tptr->this_memory_size) >= (size+sizeof(t_heap_el)) )
{// Найденный размер достаточен для размещения нового эл-та и его описателя
// tptrn - адрес описателя нового эл-та
tptrn=(t_heap_el*)( ((unsigned int)(tptr->this_memory_part)) + size);
// Установим поля описателя нового элемента
tptrn->next_dynamem_descr= tptr->next_dynamem_descr;
tptrn->prev_dynamem_descr= tptr;
tptrn->this_memory_part = (void*)(((unsigned int)(tptrn))+sizeof(t_heap_el));
tptrn->this_memory_size = (tptr->this_memory_size - size - sizeof(t_heap_el));
tptrn->flags = 0x00000000;
// Установим поля найденного элемента
tptr->next_dynamem_descr=tptrn;
//tptr->prev_dynamem_descr
//tptr->this_memory_part
tptr->this_memory_size = size;
tptr->flags |= DM_BUSY;// Block busy
// Если элемент ptr не был последним, то поле следующего за ним эл-та
// должно теперь указывать не на prt, а на ptrn
if((tptrn->next_dynamem_descr)!=heap->firstel)
{((t_heap_el*)(tptrn->next_dynamem_descr))->prev_dynamem_descr=tptrn;
}
//
heap->curel = tptr->next_dynamem_descr; // Текущий указатель переставляем
// на следующий эл-т
retptr = tptr->this_memory_part; // Возвращаем указатель на текущий эл-т
exit=1; // Выходим
}
}
// Переходим к следующему элементу
tptr = tptr->next_dynamem_descr;
// Если не выход
if(!exit)
{// Проверка на полный проход кучи
if(tptr==heap->curel)
{// Элементов заданного размера не найдено,
retptr = NULL; // Возвращаем NULL
exit=1; // Выходим
}
}
}
//
ATOMIC_END(); // Разрешаем прерывания
// Отладочная байда
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("Allocate :\n");
if(retptr){prmemptr(retptr);NOSTD_DBG_PRINTF("\n");}
else{NOSTD_DBG_PRINTF("Nothing !\n");}
#endif /* MALLOC_DEBUG */
// Выход
return(retptr);
}
//----------------------------------------------------------------------------
// Освобождает зарезервированную память, на которую указывает 'ptr' в куче 'heap'.
// Если указатель указывает на память, которая не была выделена ранее
// функциями l_malloc() или l_calloc() или указатель 'ptr' равен 0, то ничего не
// происходит
//----------------------------------------------------------------------------
void l_free(t_heap* heap, void* ptr)
{// Запрещаем прерывания
ATOMIC_BEGIN();
// Временные переменные
t_heap_el* tptr=heap->curel; // Поиск начинается с текущего элемента
t_heap_el* tptrn;
// Отладочная байда
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("Free :\n");
if(ptr){prmemptr(ptr);}
else{NOSTD_DBG_PRINTF("Nothing ! (NULL)\n");}
#endif /* MALLOC_DEBUG */
// Основной цикл поиска, пока ptr!=0
while(ptr)
{// Удаляемый эл-т найден ?
if(tptr->this_memory_part==ptr)
{// Найден. Удаляем его на хрен
// Отладочная байда
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("MBL found\n");
#endif /* MALLOC_DEBUG */
// Устанавливаем признак "блок свободен"
tptr->flags &= ~DM_BUSY;
// Проверяем следующий элемент
tptrn = tptr->next_dynamem_descr; // Указатель на следующий элемент
// Если следующий эл-т свободен и не первый в куче,
// то объединяем его с текущим
if ((!(tptrn->flags & DM_BUSY)) && (tptrn!=heap->firstel))
{// Отладочная байда
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("Join with next\n");
#endif /* MALLOC_DEBUG */
// Объединяем текущий (tptr) и следующий (tptrn) элементы
tptr->this_memory_size = tptr->this_memory_size + tptrn->this_memory_size + sizeof(t_heap_el);
tptr->next_dynamem_descr=tptrn->next_dynamem_descr;
// Если текущий элемент кучи - уничтожаемый при объедтинении
// элемент tptrn, то изменяем его (чтобы он не указывал куда попало)
if(tptrn==heap->curel){heap->curel=tptr;}
// Если эл-т tptrn не последний, то меняем указатель prev_dynamem_descr
// описателя, следующего за ptrn элемента
if( (tptrn->next_dynamem_descr) != heap->firstel)
{tptrn = tptrn->next_dynamem_descr;
tptrn -> prev_dynamem_descr = tptr;
}
//
}
// Если предыдущий эл-т свободен и не первый в куче,
// то объединяем его с текущим
tptrn = tptr->prev_dynamem_descr; // Указатель на предыдущий элемент
if ((!(tptrn->flags & DM_BUSY)) && (tptr!=heap->firstel))
{// Отладочная байда
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("Join with prev\n");
#endif /* MALLOC_DEBUG */
// Объединяем текущий (tptr) и предыдущий (tptrn) элементы
tptrn->this_memory_size = tptr->this_memory_size + tptrn->this_memory_size + sizeof(t_heap_el);
tptrn->next_dynamem_descr=tptr->next_dynamem_descr;
// Если текущий элемент кучи - уничтожаемый при объедтинении
// элемент tptr, то изменяем его (чтобы он не указывал куда попало)
if(tptr==heap->curel){heap->curel=tptrn;}
// Если эл-т tptr не последний, то меняем указатель prev_dynamem_descr
// описателя, следующего за ptr элемента
if( (tptr->next_dynamem_descr) != heap->firstel)
{tptr = tptr->next_dynamem_descr;
tptr -> prev_dynamem_descr = tptrn;
}
//
}
//
ptr=NULL; // Выходим
}
// Проверка, всю ли кучу просмотрели
if(ptr)
{tptr = tptr->next_dynamem_descr;
// Всю кучу просмотрели, элемента не нашли
if(tptr==heap->curel)
{ptr=NULL; // Выходим
}
}
}
// Отладочная байда
#ifdef MALLOC_DEBUG
NOSTD_DBG_PRINTF("\n");
#endif /* MALLOC_DEBUG */
//
ATOMIC_END(); // Разрешаем прерывания
//
}
//----------------------------------------------------------------------------
