Skip to content

Instantly share code, notes, and snippets.

@v14dislav
Created April 11, 2019 14:26
Show Gist options
  • Save v14dislav/3624e4bb2509888ed76a79f5297b26db to your computer and use it in GitHub Desktop.
Save v14dislav/3624e4bb2509888ed76a79f5297b26db to your computer and use it in GitHub Desktop.
Simple memory allocator
#include <inttypes.h>
#include <stdio.h>
#define FREE 0x6B
#define META 5
#define MIN_block 16
void * buffer= 0;
size_t length=0;
// Эта функция будет вызвана перед тем как вызывать myalloc и myfree
// используйте ее чтобы инициализировать ваш аллокатор перед началом
// работы.
//
// buf - указатель на участок логической памяти, который ваш аллокатор
// должен распределять, все возвращаемые указатели должны быть
// либо равны NULL, либо быть из этого участка памяти
// size - размер участка памяти, на который указывает buf
/* size в этой ф-ии это размер блока, а не размер payload */
void mysetup(void *buf, size_t size)
{
buffer = buf;
length = size;
/* uppet */
*(uint32_t *)buffer = (uint32_t) size; // 20 из 32 бит на размер
*( (char *)buffer + sizeof(uint32_t) ) = FREE; // 8 бит на флаг // итого: верхняя мета 5 байт
/* lower */
*(uint32_t *)((char *)buffer + size-META) = (uint32_t) size; // 20 из 32 бит на размер
*((char *)buffer+size-sizeof(char)) = FREE; // 8 бит на флаг // итого: нижняя мета 5 байт
/* 0x6B - блок свободен */
}
void *myalloc(size_t size){
char * p = (char *)buffer;
if (size >= length) goto exit;
while ( p < (char *)buffer + length ){//проход всего списка
if ( *(p + sizeof(uint32_t)) == FREE && ((int32_t)(*(uint32_t *)p-META*2) == (int32_t)size)){
/* upper */
*(uint32_t *)p = (uint32_t)size + META*2;
*((char *)p + sizeof(uint32_t)) = 0; // busy now
/* lower */
*(uint32_t *)((char *)p + META + size) = (uint32_t)size + META*2;
*((char *)p + META + size + sizeof(uint32_t)) = 0; // busy now
p += META; if ((char*)p + size > (char *)buffer +length) goto exit;
return (void*)p;
}
if (*((p + sizeof(uint32_t))) == FREE && ( (int32_t)*(uint32_t *)p-META*2-MIN_block-META*2 >= (int32_t)size )){
// new free /* upper */
*(uint32_t *)((char *)p + META + size + META) = *(uint32_t *)p - size - META*2;
*((char *)p + META + size + META + sizeof(uint32_t)) = FREE;
/* lower */
*(uint32_t *)((char *)p + *(uint32_t *)p-META) = *(uint32_t *)p - size - META*2;
*((char *)p + *(uint32_t *)p- sizeof(char)) = FREE;
/* upper */
*(uint32_t *)p = (uint32_t)size + META*2;
*((char *)p + sizeof(uint32_t)) = 0; // busy now
/* lower */
*(uint32_t *)((char *)p + META + size) = (uint32_t)size + META*2;
*((char *)p + META + size + sizeof(uint32_t)) = 0; // busy now
p += META; if ((char*)p + size > (char *)buffer +length) goto exit;
return (void*)p;
}
p += *(uint32_t *)p;
}
exit:
return NULL;
}
// Функция освобождения
void myfree(void *p)
{
/* upper */
*((char *)p - sizeof(char)) = FREE; // free now
/* lower */
*((char *)p + *(uint32_t *)((char *)p - META) - META - sizeof(char)) = FREE; // free now
if( (char *)p + *(uint32_t *)((char *)p - META)- META <= (length + (char*)buffer) -META*2 -MIN_block ){ // the end of a heap?
void* next_tag = (void *)((char *)p + *(uint32_t *)((char *)p - META) - META);
if ( *((char *)next_tag + sizeof(uint32_t)) == FREE ){ // free?
/* upper */
*(uint32_t *)((char *)p - META) += *(uint32_t *)next_tag;
/* lower */
*(uint32_t *)((char *)next_tag + *(uint32_t *)next_tag - META ) = *(uint32_t *)((char *)p - META);
}
}
if( (char *)p -META > (char *)buffer ){
void* prev_tag = (void *) ( (char*)p - META*2);
if ( *((char *)prev_tag + sizeof(uint32_t)) == FREE ){ // the start of a heap?
/* lower */
*(uint32_t *)((char*)prev_tag + *(uint32_t *)((char *)p - META) )= *(uint32_t*)prev_tag + *(uint32_t *)((char *)p - META);
/* upper */
*(uint32_t *)((char*)p - META -*(uint32_t*)prev_tag ) += *(uint32_t *)((char *)p - META);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment