История изменений

Исправление Manhunt, 31.10.14 14:26 (текущая версия) :

Писать начал вчера вечером, но не успел. Пока был занят, всё уже обсудили. Но, тем не менее, опубликую. Код не тестировался и даже не компилировался ни разу. Просто более-менее формальное изложение идеи. Разумеется, глобальные переменные нужно перенести в соответствующие классы, функции превратить в методы этих классов, константы сделать параметрами шаблонов. Но мне было лень.

массив фиксированного размер

#define ITEMS_MAX 100500
item_t items[ITEMS_MAX];

метод добавления элементов не определён(требуется указать в решении)

size_t slot_allocate();

size_t add_item(item_t item)
{
    size_t slot = slot_allocate();
    items[slot] = item;
    return slot;
}

метод извлечения элементов произвольный(то есть любой элемент можно извлечь вне зависимости от других элементов)

void slot_free(size_t slot);

item_t extract_item(size_t slot)
{
    item_t item = items[slot];
    slot_free(slot);
    return item;
}

В случае переполнения массива каждый раз удалять самый старый элемент на данный момент времени и заменять его новым.

#define LIST_HEAD_ALLOCATED (ITEMS_MAX)
#define LIST_HEAD_FREED     (ITEMS_MAX + 1)
#define LIST_SIZE           (ITEMS_MAX + 2)

size_t list_next[LIST_SIZE];
size_t list_prev[LIST_SIZE];

void list_init()
{
    for(size_t i = 0; i < LIST_SIZE; ++i)
    {
        list_next[i] = i;
        list_prev[i] = i;
    }
}

void list_remove(size_t i)
{
    size_t n = list_next[i];
    size_t p = list_prev[i];

    assert(list_next[p] == i);
    assert(list_prev[n] == i);

    list_next[p] = n;
    list_prev[n] = p;

    list_next[i] = i;
    list_prev[i] = i;
}

void list_insert(size_t prev, size_t i)
{
    list_remove(i);

    size_t p = prev;
    size_t n = list_next[prev];

    list_next[p] = i;
    list_prev[i] = p;

    list_next[i] = n;
    list_prev[n] = i;
}

void slot_free(size_t slot)
{
   list_insert(LIST_HEAD_FREED, slot);
}

size_t slot_allocate()
{
    size_t slot = list_prev[LIST_HEAD_FREED];
    if(slot == LIST_HEAD_FREED)
        slot = list_prev[LIST_HEAD_ALLOCATED];
    assert(slot < ITEMS_MAX);
    list_insert(LIST_HEAD_ALLOCATED, slot);
    return slot;
}

size_t slot_allocator_init()
{
    list_init();
    for(size_t i = 0; i < ITEMS_MAX; ++i)
        free_slot(i);
}

Исходная версия Manhunt, 31.10.14 14:26:

Писать начала вчера вечером, но не успел. Пока был занят, всё уже обсудили. Но, тем не менее, опубликую. Код не тестировался и даже не компилировался ни разу. Просто более-менее формальное изложение идеи. Разумеется, глобальные переменные нужно перенести в соответствующие классы, функции превратить в методы этих классов, константы сделать параметрами шаблонов. Но мне было лень.

массив фиксированного размер

#define ITEMS_MAX 100500
item_t items[ITEMS_MAX];

метод добавления элементов не определён(требуется указать в решении)

size_t slot_allocate();

size_t add_item(item_t item)
{
    size_t slot = slot_allocate();
    items[slot] = item;
    return slot;
}

метод извлечения элементов произвольный(то есть любой элемент можно извлечь вне зависимости от других элементов)

void slot_free(size_t slot);

item_t extract_item(size_t slot)
{
    item_t item = items[slot];
    slot_free(slot);
    return item;
}

В случае переполнения массива каждый раз удалять самый старый элемент на данный момент времени и заменять его новым.

#define LIST_HEAD_ALLOCATED (ITEMS_MAX)
#define LIST_HEAD_FREED     (ITEMS_MAX + 1)
#define LIST_SIZE           (ITEMS_MAX + 2)

size_t list_next[LIST_SIZE];
size_t list_prev[LIST_SIZE];

void list_init()
{
    for(size_t i = 0; i < LIST_SIZE; ++i)
    {
        list_next[i] = i;
        list_prev[i] = i;
    }
}

void list_remove(size_t i)
{
    size_t n = list_next[i];
    size_t p = list_prev[i];

    assert(list_next[p] == i);
    assert(list_prev[n] == i);

    list_next[p] = n;
    list_prev[n] = p;

    list_next[i] = i;
    list_prev[i] = i;
}

void list_insert(size_t prev, size_t i)
{
    list_remove(i);

    size_t p = prev;
    size_t n = list_next[prev];

    list_next[p] = i;
    list_prev[i] = p;

    list_next[i] = n;
    list_prev[n] = i;
}

void slot_free(size_t slot)
{
   list_insert(LIST_HEAD_FREED, slot);
}

size_t slot_allocate()
{
    size_t slot = list_prev[LIST_HEAD_FREED];
    if(slot == LIST_HEAD_FREED)
        slot = list_prev[LIST_HEAD_ALLOCATED];
    assert(slot < ITEMS_MAX);
    list_insert(LIST_HEAD_ALLOCATED, slot);
    return slot;
}

size_t slot_allocator_init()
{
    list_init();
    for(size_t i = 0; i < ITEMS_MAX; ++i)
        free_slot(i);
}