aktualizacja: 20210321

ze względu na ograniczony charakter zasobów systemów wbudowanych, okrągłe struktury danych bufora można znaleźć w większości projektów.

bufory okrągłe (znane również jako bufory pierścieniowe) są buforami o stałej wielkości, które działają tak, jakby pamięć była ciągła& w naturze okrągłe. Ponieważ pamięć jest generowana i zużywana, dane nie muszą być przetasowywane – zamiast tego dostosowywane są wskaźniki head/tail. Po dodaniu danych wskaźnik head postępuje. Gdy dane są zużywane, wskaźnik ogon postępuje. Jeśli dotrzesz do końca bufora, wskaźniki po prostu zawijają się do początku.

aby uzyskać bardziej szczegółowe podsumowanie operacji bufora kołowego, zapoznaj się z artykułem Wikipedii. Reszta artykułu zakłada, że rozumiesz, jak działają bufory okrągłe.

spis treści:

1. po co używać Okrągłego bufora?
2. implementacja C
   1. używanie enkapsulacji
   2. projektowanie API
   3. Określanie, czy bufor jest pełny
   4. Typ kontenera bufora Okrągłego
   5. implementacja
   6. użycie
   7. modyfikacje do usunięciafull flaga
3. implementacja C++
   1. definicja klasy
   2. implementacja
   3. zastosowanie
   4. aktualizacje dla C++17
4. składanie wszystkiego w całość
5. Czytaj dalej

po co używać Okrągłego bufora?

bufory okrągłe są często używane jako kolejki o stałej wielkości. Stały rozmiar jest korzystny dla systemów wbudowanych, ponieważ programiści często próbują używać statycznych metod przechowywania danych zamiast dynamicznych alokacji.

bufory okrągłe są również użytecznymi strukturami w sytuacjach, w których produkcja i zużycie danych odbywa się w różnym tempie: Najnowsze dane są zawsze dostępne. Jeśli konsument nie może nadążyć za produkcją, nieświeże dane zostaną nadpisane nowszymi danymi. Korzystając z okrągłego bufora, możemy zapewnić, że zawsze zużywamy Najnowsze dane.

aby uzyskać dodatkowe przypadki użycia, sprawdź podstawy bufora pierścieniowego na Embedded.com.

implementacja C

zaczniemy od implementacji C, ponieważ naraża nas to na niektóre wyzwania projektowe i kompromisy podczas tworzenia okrągłej biblioteki buforów.

używanie enkapsulacji

ponieważ tworzymy okrągłą bibliotekę buforów, chcemy mieć pewność, że użytkownicy pracują z naszymi interfejsami API bibliotek, zamiast bezpośrednio modyfikować strukturę. Chcemy również utrzymać implementację w naszej bibliotece, abyśmy mogli ją zmieniać w razie potrzeby, bez konieczności aktualizowania kodu przez użytkowników końcowych. Użytkownik nie musi znać żadnych szczegółów na temat naszej struktury, a jedynie to, że istnieje.

w nagłówku naszej biblioteki zadeklarujemy strukturę:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

nie chcemy, aby użytkownicy pracowali bezpośrednio ze wskaźnikiem circular_but_t, ponieważ mogą odnieść wrażenie, że mogą odwołać wartość. Stworzymy typ uchwytu, którego mogą użyć zamiast niego.

najprostszym podejściem do naszego uchwytu jesttypedefcbuf_handle_t jako wskaźnik do bufora kołowego. Dzięki temu nie będziemy musieli rzucać wskaźnika w naszej implementacji funkcji.

// Handle type, the way users interact with the APItypedef circular_buf_t* cbuf_handle_t;

alternatywnym podejściem byłoby nadanie uchwytowi wartościuintptr_t lubvoid*. Wewnątrz naszego interfejsu, będziemy obsługiwać tłumaczenie do odpowiedniego typu wskaźnika. Trzymamy Okrągły Typ bufora ukryty przed użytkownikami, a jedynym sposobem na interakcję z danymi jest uchwyt.

będziemy trzymać się implementacji simple handle, aby nasz przykładowy kod był prosty i prosty.

projektowanie API

najpierw powinniśmy pomyśleć o tym, jak użytkownicy będą współdziałać z kolistym buforem:

• muszą zainicjalizować okrągły pojemnik bufora buforem i rozmiarem
• muszą zniszczyć okrągły pojemnik bufora
• muszą zresetować okrągły pojemnik bufora
• muszą być w stanie dodać dane do bufora
• muszą być w stanie uzyskać następną wartość z bufora
• muszą wiedzieć, czy bufor jest pełny, czy pusty
• muszą znać aktualną liczbę elementów w buforze
• muszą znać maksymalną pojemność bufora

używając tej listy, możemy stworzyć API dla naszej biblioteki. Użytkownicy będą wchodzić w interakcje z okrągłą biblioteką buforów przy użyciu naszego nieprzezroczystego typu uchwytu, który jest tworzony podczas inicjalizacji.

wybrałemuint8_t jako podstawowy typ danych w tej implementacji. Możesz użyć dowolnego konkretnego typu, który Ci się podoba – po prostu uważaj, aby odpowiednio obsłużyć bufor bazowy i liczbę bajtów.

/// Pass in a storage buffer and size /// Returns a circular buffer handlecbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size);/// Free a circular buffer structure./// Does not free data buffer; owner is responsible for thatvoid circular_buf_free(cbuf_handle_t cbuf);/// Reset the circular buffer to empty, head == tailvoid circular_buf_reset(cbuf_handle_t cbuf);/// Put version 1 continues to add data if the buffer is full/// Old data is overwrittenvoid circular_buf_put(cbuf_handle_t cbuf, uint8_t data);/// Put Version 2 rejects new data if the buffer is full/// Returns 0 on success, -1 if buffer is fullint circular_buf_put2(cbuf_handle_t cbuf, uint8_t data);/// Retrieve a value from the buffer/// Returns 0 on success, -1 if the buffer is emptyint circular_buf_get(cbuf_handle_t cbuf, uint8_t * data);/// Returns true if the buffer is emptybool circular_buf_empty(cbuf_handle_t cbuf);/// Returns true if the buffer is fullbool circular_buf_full(cbuf_handle_t cbuf);/// Returns the maximum capacity of the buffersize_t circular_buf_capacity(cbuf_handle_t cbuf);/// Returns the current number of elements in the buffersize_t circular_buf_size(cbuf_handle_t cbuf);

Określanie, czy bufor jest pełny

zanim przejdziemy dalej, powinniśmy poświęcić chwilę na omówienie metody, której użyjemy do określenia, czy bufor jest pełny czy pusty.

oba przypadki „pełnego” i „pustego” bufora okrągłego wyglądają tak samo:head Itail wskaźnik są równe. Istnieją dwa podejścia do rozróżnienia pomiędzy pełnym i pustym:

1. „marnuj” slot w buforze:
   • pełny stan to head + 1 == tail
   • pusty stan to head == tail
2. użyj bool flaga i dodatkowa logika do rozróżniania stanów::
   • pełny stan to full
   • pusty stan to (head == tail) && !full

powinniśmy również wziąć pod uwagę bezpieczeństwo wątku. Używając pojedynczej pustej komórki do wykrycia” pełnego ” przypadku, możemy wspierać pojedynczego producenta i pojedynczego konsumenta bez blokady (o ile put I get nie modyfikują tych samych zmiennych). Kolejka jest bezpieczna dla wątków, ponieważ producent modyfikuje tylko indekshead, a konsument modyfikuje tylko indekstail. Chociaż indeks może być nieco Nieaktualny w danym kontekście, nie wpłynie to na bezpieczeństwo wątku kolejki. Użycie znacznikafull stwarza jednak wymóg wzajemnego wykluczenia. Dzieje się tak dlatego, że flaga full jest wspólna zarówno dla producenta, jak i konsumenta.

oczywiście decyzja ma swoje kompromisy. Jeśli element bufora ma duży ślad pamięci (taki jak bufor o rozmiarze odpowiadającym ramce i aparatu), marnowanie gniazda może nie być rozsądne w systemie. Jeśli masz wielu producentów / konsumentów, którzy wchodzą w interakcję z kolejką, i tak będziesz potrzebował blokady, więc marnowanie miejsca nie ma sensu. Jeśli nie masz możliwości wzajemnego wykluczenia (np. ponieważ nie używasz systemu operacyjnego), ale używasz przerwań, wtedy będziesz chciał użyć wersji flagi innej niżfull. Model pamięci zastosowany w systemie może również mieć wpływ na decyzję o przejściu bez blokady.

poniższa implementacja używa znacznikabool. Użycie flagi wymaga dodatkowej logiki w funkcjachget Iput, aby zaktualizować flagę. Opiszę również, jak dokonać modyfikacji dla pojedynczego producenta/konsumenta, który nie używa flagi full.

Okrągły kontener buforowy Typ

teraz, gdy mamy już pojęcie o operacjach, które musimy wspierać, możemy zaprojektować nasz okrągły kontener buforowy.

używamy struktury kontenera do zarządzania stanem bufora. Aby zachować hermetyzację, struktura kontenera jest zdefiniowana wewnątrz pliku .c, a nie w nagłówku.

będziemy musieli śledzić:

• bazowy bufor danych
• maksymalny rozmiar bufora
• bieżąca pozycja „head” (zwiększana, gdy elementy są dodawane)
• bieżący „tail” (zwiększany, gdy elementy są usuwane)
• znacznik wskazujący, czy bufor jest pełny, czy nie

// The hidden definition of our circular buffer structurestruct circular_buf_t {uint8_t * buffer;size_t head;size_t tail;size_t max; //of the bufferbool full;};

teraz, gdy nasz kontener został zaprojektowany, jesteśmy gotowi do implementacji funkcji bibliotecznych.

implementacja

jednym z ważnych szczegółów jest to, że każdy z naszych interfejsów API wymaga zainicjowanego uchwytu bufora. Zamiast zaśmiecać nasz kod instrukcjami warunkowymi, użyjemy asercji do egzekwowania naszych wymagań API w stylu „Design by Contract”.

Jeśli interfejsy są niewłaściwie używane, program natychmiast zawiedzie, zamiast wymagać od użytkownika sprawdzenia i obsługi kodu błędu.

na przykład:

circular_buf_reset(NULL);

:

=== C Circular Buffer Check ===Assertion failed: (cbuf), function circular_buf_reset, file ../../circular_buffer.c, line 35.Abort trap: 6

kolejną ważną uwagą jest to, że implementacja pokazana poniżej nie jest bezpieczna dla wątków. Do bazowej biblioteki buforów okrągłych nie dodano żadnych blokad.

Inicjalizuj i Resetuj

zacznijmy od początku: inicjalizacja okrągłego bufora. Nasz interfejs API zapewnia klientom bufor bazowy i rozmiar bufora, a my zwracamy im okrągły uchwyt bufora. Powodem, dla którego chcemy, aby nasi użytkownicy dostarczali bufor jest to, że pozwala to na statycznie alokowany bufor. Jeśli nasze API stworzyło bufor pod maską, musielibyśmy skorzystać z dynamicznej alokacji pamięci, co często jest niedozwolone w programach systemów wbudowanych.

jesteśmy zobowiązani do zapewnienia okrągłej instancji struktury bufora w bibliotece, abyśmy mogli zwrócić wskaźnik do użytkownika. Użyłem malloc dla uproszczenia. Systemy, które nie mogą korzystać z pamięci dynamicznej, muszą po prostu zmodyfikować funkcję init, aby użyć innej metody, takiej jak alokacja ze statycznej puli wstępnie przydzielonych okrągłych struktur bufora.

innym podejściem byłoby przerwanie enkapsulacji, pozwalając użytkownikom statycznie deklarować okrągłe struktury kontenerów bufora poza biblioteką. W tym przypadku circular_buf_init musi zostać zaktualizowany, aby przyjąć wskaźnik struct. Możemy również mieć naszą funkcjęinit, która utworzy strukturę kontenera na stosie i zwróci ją hurtowo. Jednakże, ponieważ enkapsulacja jest zepsuta, użytkownicy będą mogli modyfikować strukturę bez użycia funkcji bibliotecznych. Jeśli chcesz zachować hermetyzację, musisz pracować ze wskaźnikami zamiast wystąpień struktury betonowej.

// User provides structvoid circular_buf_init(circular_buf_t* cbuf, uint8_t* buffer, size_t size);// Return a concrete structcircular_buf_t circular_buf_init(uint8_t* buffer, size_t size);// Return a pointer to a struct instance - preferred approachcbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size);

zwracamy uchwyt do struktury przydzielonej wewnątrz biblioteki. Po utworzeniu naszego kontenera, musimy wypełnić wartości i wywołać reset na nim. Zanim wrócimy z init, upewniamy się, że kontener bufora został utworzony w stanie pustym.

cbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size){assert(buffer && size);cbuf_handle_t cbuf = malloc(sizeof(circular_buf_t));assert(cbuf);cbuf->buffer = buffer;cbuf->max = size;circular_buf_reset(cbuf);assert(circular_buf_empty(cbuf));return cbuf;}

celem funkcji resetowania jest umieszczenie bufora w stanie „pustym”, co wymaga aktualizacjiheadtail I full:

void circular_buf_reset(cbuf_handle_t cbuf){ assert(cbuf); cbuf->head = 0; cbuf->tail = 0; cbuf->full = false;}

ponieważ mamy metodę tworzenia okrągłego pojemnika bufora, potrzebujemy równoważnej metody do jego zniszczenia. W tym przypadku wywołujemy free na naszym kontenerze. Nie próbujemy uwolnić bazowego bufora, ponieważ nie jesteśmy jego właścicielami.

void circular_buf_free(cbuf_handle_t cbuf){assert(cbuf);free(cbuf);}

kontrola stanu

następnie zaimplementujemy funkcje związane ze stanem kontenera bufora.

pełna funkcja jest najłatwiejsza do zaimplementowania, ponieważ mamy flagę reprezentującą Państwo:

bool circular_buf_full(cbuf_handle_t cbuf){assert(cbuf); return cbuf->full;}

ponieważ mamy full flaga aby odróżnić stan pełny lub pusty, łączymy flagę z sprawdzeniem, że head == tail:

bool circular_buf_empty(cbuf_handle_t cbuf){assert(cbuf); return (!cbuf->full && (cbuf->head == cbuf->tail));}

pojemność naszego bufora została dostarczona podczas inicjalizacji, więc po prostu zwracamy tę wartość użytkownikowi:

size_t circular_buf_capacity(cbuf_handle_t cbuf){assert(cbuf);return cbuf->max;}

obliczenie liczby elementów w buforze było trudniejszym problemem niż się spodziewałem. Wiele proponowanych obliczeń rozmiaru używa modulo, ale podczas testowania natknąłem się na dziwne przypadki narożne. Zdecydowałem się na uproszczoną kalkulację za pomocą instrukcji warunkowych.

jeśli bufor jest pełny, wiemy, że nasza pojemność jest na maksimum. Jeśli head jest większa niż lub równa tail, po prostu odejmujemy te dwie wartości, aby uzyskać Nasz rozmiar. Jeśli tail jest większa niż head, musimy zrównoważyć różnicę za pomocą max, aby uzyskać prawidłowy rozmiar.

size_t circular_buf_size(cbuf_handle_t cbuf){assert(cbuf);size_t size = cbuf->max;if(!cbuf->full){if(cbuf->head >= cbuf->tail){size = (cbuf->head - cbuf->tail);}else{size = (cbuf->max + cbuf->head - cbuf->tail);}}return size;}

dodawanie i usuwanie danych

po wyeliminowaniu funkcji księgowości, nadszedł czas, aby zagłębić się w mięso: dodawanie i usuwanie danych z kolejki.

dodawanie i usuwanie danych z okrągłego bufora wymaga manipulacji wskaźnikamihead Itail. Podczas dodawania danych do bufora wstawiamy nową wartość w bieżącej lokalizacji head, następnie przesuwamy head. Kiedy usuniemy dane z bufora, pobieramy wartość bieżącego wskaźnikatail, a następnie przesuwamytail.

dodanie danych do bufora wymaga jednak nieco więcej przemyśleń. Jeśli bufor jest full, musimy przyspieszyć nasz tail wskaźnik, jak również head. Musimy również sprawdzić, czy wstawianie wartości powoduje wyzwalanie warunkufull.

zamierzamy zaimplementować dwie wersje funkcjiput, więc wyciągnijmy naszą logikę zaawansowania wskaźnika do funkcji pomocniczej. Jeśli nasz bufor jest już pełny, przechodzimy do tail. Zawsze wyprzedzamy head o jeden. Po zaawansowaniu wskaźnika wypełniamy znacznik full, sprawdzając, czy head == tail.

zwróć uwagę na użycie operatora modulo (%) poniżej. Modulo spowoduje, że wartości head I tail zostaną zresetowane do 0 po osiągnięciu maksymalnego rozmiaru. Zapewnia to, że head I tail są zawsze poprawnymi indeksami bazowego bufora danych.

static void advance_pointer(cbuf_handle_t cbuf){assert(cbuf);if(cbuf->full) {cbuf->tail = (cbuf->tail + 1) % cbuf->max;}cbuf->head = (cbuf->head + 1) % cbuf->max;cbuf->full = (cbuf->head == cbuf->tail);}

jak zauważył Miro Samek, jest to kosztowna operacja obliczeniowa. Zamiast tego możemy użyć logiki warunkowej, aby zmniejszyć całkowitą liczbę instrukcji. Zalecane podejście Miro to:

if (++(cbuf->head) == cbuf->max) { cbuf->head = 0;}

terazadvance_pointer będzie wyglądać tak:

static void advance_pointer(cbuf_handle_t cbuf){assert(cbuf);if(cbuf->full) {if (++(cbuf->tail) == cbuf->max) { cbuf->tail = 0;}}if (++(cbuf->head) == cbuf->max) { cbuf->head = 0;}cbuf->full = (cbuf->head == cbuf->tail);}

możemy stworzyć podobną funkcję pomocniczą, która jest wywoływana podczas usuwania wartości z bufora. Gdy usuniemy wartość, znacznikfull jest ustawiony nafalse, a wskaźnik tail jest zaawansowany.

static void retreat_pointer(cbuf_handle_t cbuf){assert(cbuf);cbuf->full = false;if (++(cbuf->tail) == cbuf->max) { cbuf->tail = 0;}}

utworzymy dwie wersje funkcjiput. Pierwsza wersja wstawia wartość do bufora i przesuwa wskaźnik. Jeśli bufor jest pełny, najstarsza wartość zostanie nadpisana. Jest to standardowy przypadek użycia dla okrągłego bufora

void circular_buf_put(cbuf_handle_t cbuf, uint8_t data){assert(cbuf && cbuf->buffer); cbuf->buffer = data; advance_pointer(cbuf);}

druga wersjaput funkcja zwraca błąd, jeśli bufor jest pełny. Jest to przewidziane w celach demonstracyjnych, ale nie używamy tego wariantu w naszych systemach.

int circular_buf_put2(cbuf_handle_t cbuf, uint8_t data){ int r = -1; assert(cbuf && cbuf->buffer); if(!circular_buf_full(cbuf)) { cbuf->buffer = data; advance_pointer(cbuf); r = 0; } return r;}

aby usunąć dane z bufora, uzyskujemy dostęp do wartości przy wskaźnikutail, a następnie aktualizujemy wskaźniktail. Jeśli bufor jest pusty, nie zwracamy wartości ani nie modyfikujemy wskaźnika. Zamiast tego zwracamy użytkownikowi błąd.

int circular_buf_get(cbuf_handle_t cbuf, uint8_t * data){ assert(cbuf && data && cbuf->buffer); int r = -1; if(!circular_buf_empty(cbuf)) { *data = cbuf->buffer; retreat_pointer(cbuf); r = 0; } return r;}

, który kończy implementację naszej okrągłej biblioteki buforów.

użycie

podczas korzystania z biblioteki klient jest odpowiedzialny za utworzenie bazowego bufora danych do circular_buf_init, a zwracany jest cbuf_handle_t:

uint8_t * buffer = malloc(EXAMPLE_BUFFER_SIZE * sizeof(uint8_t));cbuf_handle_t cbuf = circular_buf_init(buffer, EXAMPLE_BUFFER_SIZE);

Ten uchwyt służy do interakcji ze wszystkimi pozostałymi funkcjami biblioteki:

bool full = circular_buf_full(cbuf);bool empty = circular_buf_empty(cbuf);printf("Current buffer size: %zu\n", circular_buf_size(cbuf);

nie zapomnij uwolnić zarówno bazowego bufora danych, jak i kontenera po zakończeniu:

free(buffer);circular_buf_free(cbuf);

w repozytorium embedded-resources znajduje się program testowy, który korzysta z okrągłej biblioteki buforów.

modyfikacje do usuwania pełnej flagi

Jeśli chcesz porzucić flagęfull, zamiast tego sprawdź, czyhead jest jedną pozycją za ogonem, aby określić, czy bufor jest pełny:

bool circular_buf_full(circular_buf_t* cbuf){// We determine "full" case by head being one position behind the tail// Note that this means we are wasting one space in the buffer return ((cbuf->head + 1) % cbuf->size) == cbuf->tail;}

teraz, jeśli chcemy uniknąć operacji Modulo, możemy użyć logiki warunkowej zamiast:

bool circular_buf_full(circular_buf_t* cbuf){// We need to handle the wraparound case size_t head = cbuf->head + 1; if(head == cbuf->max) {head = 0; }return head == cbuf->tail;}

pustym przypadkiem jest to, że head I tail są takie same:

bool circular_buf_empty(circular_buf_t* cbuf){// We define empty as head == tail return (cbuf->head == cbuf->tail);}

podczas pobierania danych z bufora, przesuniemy ogon wskaźnik, owijanie w razie potrzeby:

int circular_buf_get(circular_buf_t * cbuf, uint8_t * data){ int r = -1; if(cbuf && data && !circular_buf_empty(cbuf)) { *data = cbuf->buffer; cbuf->tail = (cbuf->tail + 1) % cbuf->size; r = 0; } return r;}

podczas dodawania danych do bufora, będziemy przechowywać Dane i przesuwać wskaźnik głowy, owijanie w razie potrzeby:

int circular_buf_put(circular_buf_t * cbuf, uint8_t data){ int r = -1; if(cbuf && !circular_nuf_full(cbuf)) { cbuf->buffer = data; cbuf->head = (cbuf->head + 1) % cbuf->size; r = 0; } return r;}

inne odniesienia do full można wyeliminować.

C++

C++ nadaje się do czystszej implementacji bufora kołowego niż C.

definicja klasy

zaczniemy od zdefiniowania naszej klasy C++. Chcemy, aby nasza implementacja c++ obsługiwała każdy rodzaj danych, więc zamierzamy uczynić z niej klasę szablonową.

nasze API będą podobne do implementacji C. Nasza klasa dostarczy interfejsy dla:

• Resetowanie bufora do pustego
• Dodawanie danych
• usuwanie danych
• Sprawdzanie stanu pełnego/pustego
• sprawdzanie bieżącej liczby elementów w buforze
• sprawdzanie całkowitej pojemności bufora

wykorzystamy również inteligentne wskaźniki c++, aby upewnić się, że nie pozostawiamy żadnych danych po zniszczeniu naszego bufora. Oznacza to, że możemy zarządzać buforem dla użytkownika.

Kolejną zaletą C++ jest trywialność uczynienia tej klasy bezpieczną dla wątków: możemy polegać na typie std::mutex (zakładając, że jest to zdefiniowane dla Twojej platformy).

oto definicja naszej klasy:

template <class T>class circular_buffer {public:explicit circular_buffer(size_t size) :buf_(std::unique_ptr<T>(new T)),max_size_(size){ // empty }void put(T item);T get();void reset();bool empty() const;bool full() const;size_t capacity() const;size_t size() const;private:std::mutex mutex_;std::unique_ptr<T> buf_;size_t head_ = 0;size_t tail_ = 0;const size_t max_size_;bool full_ = 0;};

implementacja C++

Nasz okrągły bufor C++ naśladuje wiele logiki z implementacji C, ale skutkuje znacznie czystszym i bardziej wielokrotnego użytku projektem. Ponadto bufor C++ wykorzystuje std::mutex, aby zapewnić implementację bezpieczną dla wątków.

Uwaga: te same zmiany logiczne mogą być wprowadzone w implementacji c++, aby wspierać bezpieczeństwo wątków z jednym producentem i konsumentem poprzez „marnowanie” gniazda. Więcej informacji można znaleźć w dostosowaniach implementacji C.

Inicjalizacja

podczas konstruowania naszej klasy, przydzielamy dane do naszego bazowego bufora i ustawiamy rozmiar bufora. Usuwa to narzut wymagany przy implementacji C.

W przeciwieństwie do implementacji C, konstruktor c++ nie wywołuje reset. Ponieważ określamy wartości początkowe dla naszych zmiennych członkowskich, nasz bufor kołowy zaczyna się w prawidłowym stanie.

explicit circular_buffer(size_t size) :buf_(std::unique_ptr<T>(new T)),max_size_(size){//empty constructor}

nasze zachowanie resetowania powoduje przywrócenie bufora do stanu pustego (head == tail && !full_).

void reset(){std::lock_guard<std::mutex> lock(mutex_);head_ = tail_;full_ = false;}

Śledzenie stanu

logika przypadków empty I full jest taka sama jak w przykładzie C:

bool empty() const{//if head and tail are equal, we are emptyreturn (!full_ && (head_ == tail_));}bool full() const{//If tail is ahead the head by 1, we are fullreturn full_;}

w implementacji bufora okrągłego c++, size I capacity zgłaszają liczbę elementów w kolejce, a nie rozmiar w bajtach. To pozwala nam być agnostykiem do podstawowych szczegółów typu.

size_t capacity() const{return max_size_;}size_t size() const{size_t size = max_size_;if(!full_){if(head_ >= tail_){size = head_ - tail_;}else{size = max_size_ + head_ - tail_;}}return size;}

Dodawanie danych

Logika dlaput pasuje do implementacji C. Ta implementacja używa wzorca behawioralnego „Nadpisz najstarszą wartość”.

void put(T item){std::lock_guard<std::mutex> lock(mutex_);buf_ = item;if(full_){tail_ = (tail_ + 1) % max_size_;}head_ = (head_ + 1) % max_size_;full_ = head_ == tail_;}

uwaga: dla uproszczenia pominąłem opcję, która unika operacji modulo. Możesz znaleźć tę logikę w sekcji C.

pobieranie danych

logikaget pasuje do implementacji C. W przeciwieństwie do implementacji C, wartość pusta jest zwracana, jeśli bufor jest pusty.

T get(){std::lock_guard<std::mutex> lock(mutex_);if(empty()){return T();}//Read data and advance the tail (we now have a free space)auto val = buf_;full_ = false;tail_ = (tail_ + 1) % max_size_;return val;}

Uwaga: return T() zwróci domyślną wartość skonstruowaną dla danego typu ra. Rzeczywista wytworzona wartość zależy od typu lub konstruktora. Ponadto, dla uproszczenia, pominąłem opcję, która unika operacji modulo. Możesz znaleźć tę logikę w sekcji C.

zastosowanie

bufor okrągły C++ jest znacznie prostszy w użyciu niż implementacja C.

aby utworzyć instancję bufora kołowego, po prostu deklarujemy obiekt i określamy typ szablonu dla naszego bufora. Oto przykład z buforem 10uint32_t wpisy:

circular_buffer<uint32_t> circle(10);

Dodawanie danych jest łatwe:

uint32_t x = 100;circle.put(x);

i pobieranie danych jest równie łatwe:

x = circle.get()

pamiętaj, że ponieważ jest to klasa szablonowa, możesz utworzyć okrągły bufor dowolnego typu, którego potrzebujesz.

aktualizacje dla C++17

w C++17 mamy dostęp do std::optional, co pozwala nam reprezentować wartość, która może być obecna lub nie. Nasza funkcjaget zwrócistd::optional<T>. Zwracamy również std::nulloptzamiast domyślnegoT, jeśli kolejka jest pusta.

std::optional<T> get(){std::lock_guard<std::mutex> lock(mutex_);if(empty()){return std::nullopt;}//Read data and advance the tail (we now have a free space)auto val = buf_;full_ = false;tail_ = (tail_ + 1) % max_size_;return val;}

uwaga: dla uproszczenia pominąłem opcję, która unika operacji modulo. Możesz znaleźć tę logikę w sekcji C.

w kodzie wywoławczym można sprawdzić poprawną wartość za pomocą operatora logicznego lub funkcji członkahas_value. Jeśli istnieje prawidłowa wartość, można uzyskać do niej dostęp za pomocą -> lub * operatorów, ur za pomocą value() funkcji członka.

// Returns an optionalauto item = cbuf.get();// Check if the optional is validif(item){process_data(*item); // access the value}

składając to wszystko razem

przykładowe implementacje można znaleźć wembedded-resources repozytorium Github.

• C circular buffer test program
  • C circular buffer library
• C++ circular buffer example

Jeśli chcesz rozszerzyć tę bibliotekę, przydatnym ćwiczeniem jest dodanie dodatkowych interfejsów API, aby umożliwić użytkownikom dodawanie/usuwanie wielu elementów za pomocą jednej operacji. Możesz również uczynić wątek implementacji C bezpiecznym.

zabezpieczenie nici metodą Lookahead

jednym z podejść do zabezpieczenia nici bez mutex jest metoda „lookahead”. Metoda ta obsługuje pojedynczy wątek producenta i pojedynczy wątek konsumenta; wielu producentów lub konsumentów będzie wymagać blokady.

zamiast używać znacznika logicznego do rozróżniania przypadków pełnych i pustych, zawsze zostawimy jedną komórkę pustą. Używając pojedynczej pustej komórki do wykrycia” pełnego ” przypadku, możemy wspierać pojedynczego producenta i pojedynczego konsumenta bez blokady (o ile put I get nie modyfikują tych samych zmiennych).

możesz obawiać się marnowania slotu, ale ten kompromis jest często znacznie tańszy niż koszt użycia prymitywnego zamka OS.

Czytaj dalej

• Inteligentne Wskaźniki C++
• porzuć swoje wskaźniki C-Stye dla inteligentnych wskaźników

oto inne implementacje buforów okrągłych:

• QuantumLeaps/lock-free-ring-buffer
• willemt/BipBuffer

aby uzyskać więcej informacji na temat buforów okrągłych:

• Embedded.com: podstawy bufora pierścieniowego
• Wikipedia: Bufor Okrągły
• Systemy żelazne: Blokada wolnego bufora pierścieniowego
• wzmocnienie bufora Okrągłego
• c++: Wydajność bufora Okrągłego vs Vector, Deque i List
• bez blokad Kolejka okrągła pojedynczego producenta-pojedynczego konsumenta

istnieje propozycja dodania bufora okrągłego do standardowej biblioteki C++:

• P0059: Propozycja dodania zakresu pierścienia do standardowej biblioteki
  • zakresu pierścienia
  • zakresu pierścienia Lite

Change Log

• 20210321
  • Naprawiono błąd z max_size_ gdzie cbuf->max powinien zostały użyte
  • dodano tekst wyjaśniający, dlaczego bufor jest przekazywany przez użytkownika
• 20210301
  • zaadresowano informacje zwrotne od Miro dotyczące unikania operacji modulo
• 20210213
  • dodano dodatkowe linki
  • dodano dalszą dyskusję na temat kompromisu między pełną flagą a użyciem „WASTED” slot
  • Pokaż modyfikacje dla bezpieczeństwa wątku z jednym producentem/konsumentem
  • dodaj uwagi na std::optional użyj Z C++17
• 20191016
  • zaktualizowane formatowanie sekcji dziennika zmian dla spójności w całej witrynie
  • zdegradowane nagłówki dla spójności w całej witrynie
  • Naprawiono uszkodzoną tabelę spis treści linki
  • usunięto dziennik zmian ze spisu treści
• 20190627
  • Dodano link do artykułu bufor pierścieni blokujących.
• 20190604
  • Naprawiono literówkę (dzięki Chris Svec!) oraz zmieniono niektóre sformułowania związane z typem nieprzezroczystym.
• 20181219
  • Dodano notatkę o unikaniu problemów z współbieżnością z pojedynczym producentem i pojedynczym konsumentem przy użyciu pustego gniazda.
• 20180804
  • artykuł został zrestrukturyzowany i przepisany.Dziękujemy wszystkim, którzy przekazali swoją opinię po drodze. Przykłady zostały zaktualizowane do:
  • Usuń programowanie defensywne
  • użyj asercji
  • Utwórz samodzielną bibliotekę przy użyciu nieprzezroczystej struktury
  • rozwiń interfejsy API, w tym obliczenia dla bieżącego okrągłego rozmiaru bufora
  • zaktualizuj bibliotekę, aby nie marnowała gniazda