dynamic21

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <array>
#include <random>
#include <functional>
#include <time.h>

// Мини логгер

template <typename T>
void log(T&& val) {
    std::cout << val;
}

template <typename T, typename... Ts>
void log(T&& arg, Ts&&... args) {
    log(arg);
    log(args...);
}


// Ассерт
void assert_impl(bool cond, const char* msg, const char* file, const char* func, int line) {
    if (!cond) {
        std::cerr << "Fatal error:\n" << file << ":" << line << " " << func << "(): ";
        std::cerr << "\t" << msg << std::endl;
        exit(1);
    }
}

#define ASSERT(condition, message) assert_impl(condition, message, __FILE__, __FUNCTION__, __LINE__)




// Класс для просмотра строк. (Не владеет ресурсом, только предоставляет к нему доступ)
class StringViewer {
    friend class CircularQueue;

public:
    // Методы взятия одного символа по индексу
    virtual       char& at(unsigned pos)       { return ptr[pos]; }
    virtual const char& at(unsigned pos) const { return ptr[pos]; }

    // Метод получения размера строки
    virtual unsigned length() const { return size; }

    // Метод вывода на экран
    virtual void print(std::ostream& os = std::cout) const { os << ptr; }

    // Оператор << ostream
    friend std::ostream& operator<<(std::ostream& os, const StringViewer& sv) { sv.print(os); }

protected:
    // Конструктор объявлен защищенным, т.к. объект может быть создан только в friend классе CircularQueue
    StringViewer(char* iPtr, unsigned iSize): ptr(iPtr), size(iSize) {}

    char*    ptr;  // Начало строки
    unsigned size; // Размер строки
};

// Класс для просмотра разорванных в памяти строк. Наследник StringViewer
class StringViewerDivide : public StringViewer {
    friend class CircularQueue;

public:
    // Методы взятия одного символа по индексу
    virtual char& at(unsigned pos) {
        return pos < size ? ptr[pos] : ptr2[pos - size];
    }
    virtual const char& at(unsigned pos) const {
        return pos < size ? ptr[pos] : ptr2[pos - size];
    }

    // Метод получения размера строки
    virtual unsigned length() const { return size + size2; }

    // Метод вывода на экран
    virtual void print(std::ostream& os = std::cout) const {
        os << ptr << ptr2;
    }

protected:
    // Конструктор объявлен защищенным, т.к. объект может быть создан только в friend классе CircularQueue
    StringViewerDivide(char* ptr1, unsigned size1, char* iptr2, unsigned isize2):
            StringViewer(ptr1, size1), ptr2(iptr2), size2(isize2) {}

    char*    ptr2;  // Начало второй части строки
    unsigned size2; // Размер второй части
};


// Кольцевая очередь
class CircularQueue {
private:
    struct Node {
        Node(char* iPtr, unsigned iSize): ptr(iPtr), size(iSize) {}

        Node*    next = nullptr;
        Node*    prev = nullptr;

        char*    ptr;
        unsigned size;
    };

    unsigned max_size;     // Размер выделенного блока памяти
    char*    mem;          // Начало блока
    char*    mem_end;      // Конец блока
    char*    space_start;  // Начало свободного пространства
    char*    space_end;    // Конец свободного пространства
    unsigned space_size;   // Размер свободного пространства в байтах

    Node*    head = nullptr;    // Голова очереди
    Node*    tail = nullptr;    // Хвост очереди
    unsigned missed_nodes = 0;  // Количество потерянный узлов


    // Уменьшает свободное пространство на заданную величину
    void incrSpaceStart(unsigned value) {
        space_start += value;
        if (space_start >= mem_end)
            space_start = mem + (space_start - mem_end);
        space_size -= value;
    }

    // Увеличивает свободное пространство на заданную величину
    void incrSpaceEnd(unsigned value) {
        space_end += value;
        if (space_end > mem_end)
            space_end = mem + (space_end - mem_end);
        space_size += value;
    }

    // Возвращает объект StringViewer или StringViewerDivide в зависимости от того, разорвана ли строка
    StringViewer unpack_node(Node* node) {
        if (node) {
            if (node->ptr + node->size > mem_end)
                return StringViewerDivide(node->ptr, mem_end - node->ptr, mem, node->size - (mem_end - node->ptr));
            else
                return StringViewer(node->ptr, node->size);
        } else
            return StringViewer(nullptr, 0);
    }

public:
    CircularQueue(unsigned bytes_size):
            max_size   (bytes_size),
            mem        (new char[max_size + 1]), // +1 for null-terminator
            mem_end    (mem + max_size),
            space_start(mem),
            space_end  (mem_end),
            space_size (max_size)
    {
        ASSERT(max_size != 0, "Попытка задания нулевого размера.");
        mem[max_size] = '\0';
    }


    ~CircularQueue() {
        clear();
        delete [] mem;
    }


    // Добавляет элемент в конец очереди
    void push(const char* str) {
        unsigned strSize = strlen(str) + 1; // null terminator

        ASSERT(strSize <= max_size, "Попытка добавления элемента большего, чем выделенный участок памяти");

        // Удаляем элементы, пока не хватит памяти
        while (space_size < strSize) {
            log("[[FORCE]]");
            ++missed_nodes;
            pop();
        }

        Node* node = nullptr;

        if (space_start + strSize > mem_end) {
            log("[push divided element]: ", "strsize = ", strSize, " freeMemory = ", space_size, "\n");
            unsigned  backSize = mem_end - space_start;
            unsigned frontSize = strSize - backSize;

            memcpy(space_start, str, backSize);
            node = new Node(space_start, strSize);
            incrSpaceStart(backSize);

            memcpy(space_start, str + backSize, frontSize);
            incrSpaceStart(frontSize);

        } else {
            log("[push element]:         ", "strsize = ", strSize, " freeMemory = ", space_size, "\n");
            memcpy(space_start, str, strSize);
            node = new Node(space_start, strSize);
            incrSpaceStart(strSize);
        }

        node->next = tail;
        if (tail)
            tail->prev = node;
        tail = node;

        if (head == nullptr)
            head = tail;
    }

    // Удаляет первый элемент очереди
    void pop() {
        if (head) {
            log("[pop element]:          ", "strsize = ", head->size, " freeMemory = ", space_size, "\n");
            incrSpaceEnd(head->size);

            Node* prev = head->prev;

            if (prev)
                prev->next = nullptr;

            delete head;
            head = prev;

            if (!head)
                tail = nullptr;
        }
    }

    // Очистит очередь
    void clear() { while(head) pop(); }

    // Вернет первый элемент в очереди
    StringViewer front() { return unpack_node(head); }

    // Вернет последний элемент в очереди
    StringViewer back () { return unpack_node(tail); }

    // Вернет количество элементов в очереди
    unsigned size() {
        unsigned res = 0;
        Node* node   = head;

        while (node) {
            ++res;
            node = node->prev;
        }

        return res;
    }

    // Вернет кол-во потерянных элементов
    unsigned missed() { return missed_nodes; }


    // Выведет на экран представление строк в памяти
    // # - это space_start
    // $ - это space_end
    // @ - когда вся память свободна и они совпадают
    // . - терминирующий ноль у строк
    void memdump() {
        char* memstr = new char[max_size + 2];
        memset(memstr, '_', max_size + 1);
        memstr[max_size + 1] = '\0';

        Node* node = head;

        while (node) {
            if (node->ptr + node->size > mem_end) {
                memcpy(memstr + (node->ptr - mem), node->ptr, mem_end - node->ptr);
                memcpy(memstr, mem, node->size - (mem_end - node->ptr));
            } else {
                memcpy(memstr + (node->ptr - mem), node->ptr, node->size);
            }
            node = node->prev;
        }

        if (space_start == space_end)
            memstr[space_start - mem] = '@';
        else {
            memstr[space_start - mem] = '#';
            memstr[space_end - mem] = '$';
        }

        for (int i = 0; i < max_size; ++i)
            if (memstr[i] == '\0')
                memstr[i] = '.';

        std::cout << memstr << std::endl;
        delete [] memstr;
    }
};




// Random Strings

std::array<const char*, 11> strings = {
    "AAAAAAAAAAAAAA",
    "BBBBBBBBBBBB",
    "CCCCCCCCC",
    "DDDDDDDDDDDDDDDDDDDDDD",
    "EEEEEEEEEEEEEEEEEE",
    "FFFFFFFFFFFFFFFF",
    "GGGGGGGGGGGG",
    "HHHHHHHHHHHHHHHHH",
    "IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII",
    "JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ",
    "KKK"
};


std::mt19937 mt(clock());
std::uniform_int_distribution<unsigned> uid(0, 10); // Кол-во строк
auto gen = std::bind(uid, mt);

const char* random_string() {
    return strings[gen()];
}




int main() {
    CircularQueue queue(1024);
    unsigned test_iter = 200;


    for (int i = 0; i < test_iter; ++i) {
        queue.push(random_string());
        queue.memdump();
        queue.pop();
    }

    for (int i = 0; i < test_iter; ++i) {
        queue.memdump();
        queue.push(random_string());
    }

    for (int i = 0; i < test_iter; ++i)
        queue.pop();

    queue.memdump();

    return 0;
}