Форум arduino.ua

p-a-h-a

Учасник

Зареєстрований: 2023-07-02

Повідомлень: 4

Циклічний (коловий) масив

Доброго дня, хочу поділитися напрацюваннями для ESP 8266, ESP 32-S3 бібліотекою з прикладом реалізаціїї циклічного масиву. Фішки: має швидкий зсув всього масиву, швидко додає на початок або кінець масиву нові данні з сувом масиву. Фактично міняється вказівник на початок масиву без перенесення всіх комірок. Працювати можна як з vector, так само має ітератори, дані зберігаються на кучі. Спробував зробити якомога більшу сумісність з STL. Наприклад працює сортування

CyclicArray<int> arr{-1,1,-3,3,-2,2,-5,5,-4,4};
std::sort(arr.begin(), arr.end(), std::greater<int>()); //5 4 3 2 1 -1 -2 -3 -4 -5
arr >> 2; //зсув вправо -4 -5 5 4 3 2 1 -1 -2 -3
arr.push_back(100); //-5 5 4 3 2 1 -1 -2 -3 100

Бібліотека може мати помилки. З радістю почитаю про зауваження та варіанти оптимізації.
Один з варіантів використання: зберігати в масив покази датчику.

Посиланя на приклад для Platformio: https://github.com/androidpasha/QuickShiftArray

dimich

Учасник

Зареєстрований: 2023-12-01

Повідомлень: 236

Re: Циклічний (коловий) масив

Якщо цікаво, примітивний варіант реалізації ring buffer фіксованого розміру з моєї відповіді на StackOverflow:

template <typename T>
class ring
{
    T *data;
    std::size_t size;
    std::size_t front { 0 };
    std::size_t back  { 0 };
    bool full { false };
public:
    ring(std::size_t _size) : data{new T[_size]}, size{ _size } {}

    ~ring() {
        delete [](data);
    }

    bool enqueue(T value) {
        if (full) {
            return false;
        }
        data[back] = value;
        back = (back + 1) % size;
        if (back == front) {
            full = true;
        }
        return true;
    }

    T dequeue() {
        if ((front == back) && !full) {
            return {};
        }
        full = false;
        std::size_t old_front = front;
        front = (front + 1) % size;
        return data[old_front];
    }
};

Ініціалізацію з initializer_list та інший синтаксичний цукор за бажанням прикрутити не складе труднощів.

Honey

Учасник

З Київ

Зареєстрований: 2020-09-26

Повідомлень: 439

Re: Циклічний (коловий) масив

Основною фішкою рінгбуфера (якщо не псувати "оптимізаціями" стандартну реалізацію) є можливість виконувати запис і читання в двох окремих потоках без будь-яких синхронізацій між ними.

dimich

Учасник

Зареєстрований: 2023-12-01

Повідомлень: 236

Re: Циклічний (коловий) масив

Основною фішкою рінгбуфера (якщо не псувати "оптимізаціями" стандартну реалізацію) є можливість виконувати запис і читання в двох окремих потоках без будь-яких синхронізацій між ними.

Здається, спосіб організації контейнера та властивість lock-free — ортогональні поняття. Хіба що в рінгбуфері lock-free досягається відносно просто за рахунок правильного порядку операцій. А синхронізація присутня в будь-якому разі, просто в lock-free вона без блокувань, за рахунок атомарності деяких операцій і впорядкування доступу до памʼяті, що в більшості архітектур реалізовано апаратно.