Code: //---------------------------------------------------------------------------- // Работа с кучей. Заголовочный файл. // // Структура кучи: // |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(); // Разрешаем прерывания // } //----------------------------------------------------------------------------
|