simple on-array allocator

block_pool.c

// 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;
}