Skip to content

Instantly share code, notes, and snippets.

@max-dark
Last active January 21, 2020 00:01
Show Gist options
  • Save max-dark/44f5f77f0555ea3017a9ea8331fbefc4 to your computer and use it in GitHub Desktop.
Save max-dark/44f5f77f0555ea3017a9ea8331fbefc4 to your computer and use it in GitHub Desktop.
simple on-array allocator
// task: create two queues that will be located in one array of a fixed size
// solution: create a pool of blocks in this array.
// http://www.cyberforum.ru/algorithms/thread2569313.html
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <assert.h>
// настройки типов
typedef uint8_t pointer_t; // "указатель" на блок
typedef uint8_t offset_t; // смещение в блоке
typedef uint8_t item_t; // тип элемента
// настройки размеров
enum PoolConstants
{
BLOCK_COUNT = 32, // количество блоков в пуле
BLOCK_SIZE = 32, // размер одного блока(количество item_t в блоке)
DATA_SIZE = BLOCK_SIZE - sizeof(pointer_t), // размер участка данных в блоке
};
// block pool
// представляет собой односвязный список, размещенный в массиве
// элемент пула
// тут можно пофантазировать:
// например, можно сделать его union-ом 2х сструктур
struct mem_block_t
{
pointer_t next; // next block in list
item_t data[DATA_SIZE]; // payload
};
typedef struct mem_block_t mem_block_t;
static const pointer_t null_ptr = 0xff; // для индикации "out of memory". любое число >= BLOCK_COUNT
// собственно пул блоков
static mem_block_t blocks[BLOCK_COUNT];
static pointer_t first_free; // ссылка на первый свободный блок
// конвертация:
// получить указатель по его номеру
mem_block_t* block(pointer_t idx)
{
assert(idx < BLOCK_COUNT);
return &blocks[idx];
}
// начальная настройка пула
// вызвать при старте программы
void pool_init()
{
pointer_t idx;
first_free = 0;
// собрать список из блоков
for(idx = 0; idx < BLOCK_COUNT - 1; ++idx)
{
block(idx)->next = idx + 1;
}
block(idx)->next = null_ptr;
}
// проверка на пустоту пула
bool pool_empty()
{
return first_free == null_ptr;
}
// запросить блок из пула
pointer_t pool_alloc()
{
// проверка на наличие блоков в пуле
// сработает только в debug
// если нужно обработать эту ситуацию(например: поднять лапки, выключив перефирию), то можно вернуть null_ptr
assert(!pool_empty());
pointer_t idx = first_free;
first_free = block(idx)->next;
// "подчистим" указатель
block(idx)->next = null_ptr;
return idx;
}
// вернуть блок в пул
void pool_free(pointer_t idx)
{
assert(idx < BLOCK_COUNT);
block(idx)->next = first_free;
first_free = idx;
}
// FIFO container
// обычный односвязный список
struct queue_t
{
pointer_t head, tail;
offset_t data_start; // смещение начала данных в head
offset_t first_free; // смещение на свободное место в tail
};
typedef struct queue_t queue_t;
// "конструктор" очереди
void queue_init(queue_t* self)
{
// выделить начальный блок
self->head = self->tail = pool_alloc();
// настроить смещения
self->data_start = self->first_free = 0;
}
// "деструктор": уничтожить очередь, освободив все блоки
void queue_destroy(queue_t* self)
{
while(self->head != self->tail)
{
pointer_t old_head = self->head;
self->head = block(self->head)->next;
pool_free(old_head);
}
}
// проверка на пустоту
bool queue_empty(const queue_t* self)
{
return (self->head == self->tail)
&& (self->data_start == self->first_free);
}
// прочитать 1 элемент в начале очереди
item_t queue_top_byte(const queue_t* self)
{
assert(!queue_empty(self));
return block(self->head)->data[self->data_start];
}
// извлечь из очереди один элемент
item_t queue_pop_byte(queue_t* self)
{
assert(!queue_empty(self));
item_t result = queue_top_byte(self);
// на следующий элемент
self->data_start += 1;
// блок полностью считан?
if (self->data_start >= DATA_SIZE)
{
// да, переходим на следующий блок
// это последний блок в очереди?
if (self->head == self->tail)
{
assert(queue_empty(self));
// да, сбросим состояние очереди, оставив его себе
self->data_start = self->first_free = 0;
}
else
{
// нет, перейдем к следующему
pointer_t old_head = self->head;
self->head = block(self->head)->next;
self->data_start = 0;
// освободим память
pool_free(old_head);
}
}
return result;
}
// записать 1 элемент
void queue_put_byte(queue_t* self, item_t data)
{
// есть ли свободное место?
if (self->first_free >= DATA_SIZE)
{
// место в текущем блоке кончилось, выделим новый
block(self->tail)->next = pool_alloc();
// tail = new block
self->tail = block(self->tail)->next;
self->first_free = 0;
}
// store item
block(self->tail)->data[self->first_free] = data;
self->first_free += 1;
}
// message struct
enum MsgConstants
{
MSG_MAX_SIZE = 9, // максимальный размер сообщения
};
struct message_t
{
// длина сообщения
item_t length;
// данные сообщения
item_t data[MSG_MAX_SIZE];
};
typedef struct message_t message_t;
// записать сообщение
void queue_put_msg(queue_t* self, const message_t* msg)
{
// сначала длину
queue_put_byte(self, msg->length);
// затем сообщение
for(offset_t idx = 0; idx < msg->length; ++idx)
{
queue_put_byte(self, msg->data[idx]);
}
}
// извлечь сообщение
void queue_pop_msg(queue_t* self, message_t* msg)
{
// сначала длину
msg->length = queue_pop_byte(self);
// затем сообщение
for(offset_t idx = 0; idx < msg->length; ++idx)
{
msg->data[idx] = queue_pop_byte(self);
}
}
int main(void) {
static queue_t q1, q2;
// init block pool
pool_init();
// init queues
queue_init(&q1);
queue_init(&q2);
item_t num = 101;
// test queue_t::push_back
for(offset_t idx = 0; idx < num; ++idx)
{
queue_put_byte(&q1, idx);
queue_put_byte(&q2, idx * 2);
}
// test queue_t::pop_front
for(offset_t idx = 0; idx < num; ++idx)
{
item_t data = queue_pop_byte(&q1);
assert(data == idx);
}
// test queue_t::pop_front
for(offset_t idx = 0; idx < num; ++idx)
{
item_t data = queue_pop_byte(&q2);
assert(data == idx * 2);
}
// проверим, что данные считаны полностью
assert(queue_empty(&q1));
assert(queue_empty(&q2));
// в этой точке мы будем только если все тесты прошли
puts("OK");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment