bijgewerkt: 20210321

vanwege de beperkte middelen van ingebedde systemen, kunnen cirkelbuffergegevensstructuren in de meeste projecten worden gevonden.

Cirkelbuffers (ook bekend als ringbuffers) zijn buffers van vaste grootte die werken alsof het geheugen aaneengesloten is & cirkelbuffers. Aangezien het geheugen wordt gegenereerd en verbruikt, hoeven de gegevens niet opnieuw te worden geschud – in plaats daarvan worden de kop/staart pointers aangepast. Wanneer gegevens worden toegevoegd, gaat de head pointer vooruit. Wanneer gegevens worden verbruikt, gaat de staartaanwijzer vooruit. Als je het einde van de buffer bereikt, wikkelen de pointers gewoon rond naar het begin.

voor een meer gedetailleerde samenvatting van circulaire buffer operatie, verwijzen wij u naar het Wikipedia artikel. De rest van het artikel gaat ervan uit dat je een goed begrip hebt van hoe circulaire buffers werken.

inhoudsopgave:

1. waarom een Cirkelbuffer gebruiken?
2. C Uitvoering
   1. met Behulp van de Inkapseling
   2. API Design
   3. het Bepalen of een Buffer is Vol
   4. Circulaire Buffer Container, Type
   5. Implementatie
   6. Gebruik
   7. Aanpassingen voor het Verwijderen van de full vlag
3. C++ Implementatie
   1. Klasse-Definitie
   2. Implementatie
   3. Gebruik
   4. Updates voor C++17
4. Het Allemaal Samen te brengen
5. Verder Lezen

Waarom Gebruik maken van Een Circulaire Buffer?

ronde buffers worden vaak gebruikt als wachtrijen van vaste grootte. De vaste grootte is gunstig voor embedded systemen, omdat ontwikkelaars vaak proberen om statische data opslag methoden te gebruiken in plaats van dynamische toewijzingen.

circulaire buffers zijn ook nuttige structuren voor situaties waarin de productie en het verbruik van gegevens in verschillende snelheden plaatsvinden: de meest recente gegevens zijn altijd beschikbaar. Indien de consument de productie niet kan bijhouden, worden de verouderde gegevens overschreven door recentere gegevens. Door gebruik te maken van een circulaire buffer kunnen we ervoor zorgen dat we altijd de meest recente gegevens gebruiken.

voor extra use cases, check out ring Buffer Basics op Embedded.com.

C implementatie

we beginnen met een C implementatie, omdat dit ons blootstelt aan enkele van de ontwerpuitdagingen en afwegingen bij het maken van een circulaire bufferbibliotheek.

met behulp van Encapsulation

omdat we een circulaire bufferbibliotheek maken, willen we ervoor zorgen dat gebruikers met onze bibliotheek API ‘ s werken in plaats van de structuur direct te wijzigen. We willen ook de implementatie binnen onze bibliotheek houden, zodat we deze naar behoefte kunnen wijzigen, zonder dat eindgebruikers hun code hoeven bij te werken. De gebruiker hoeft geen details over onze structuur te weten, alleen dat het bestaat.

In onze bibliotheekheader zullen we de structuur doorsturen declareren:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

we willen niet dat gebruikers direct met een circular_but_t pointer werken, omdat ze de indruk kunnen krijgen dat ze de waarde kunnen derefereren. We zullen een soort handle maken die ze in plaats daarvan kunnen gebruiken.

de eenvoudigste benadering voor onze handle is om typedef de cbuf_handle_t als een pointer naar de circulaire buffer. Dit zal voorkomen dat we de pointer binnen onze functie-implementatie moeten plaatsen.

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

een alternatieve benadering zou zijn om de handle een uintptr_t of void* waarde te geven. Binnen onze interface, zouden wij de vertaling naar het aangewezen wijzertype behandelen. We houden het circulaire buffertype verborgen voor gebruikers, en de enige manier om met de gegevens te communiceren is via het handvat.

We houden het bij de simple handle implementatie om onze voorbeeldcode eenvoudig en duidelijk te houden.

API ontwerp

eerst moeten we nadenken over hoe gebruikers zullen interageren met een circulaire buffer:

• ze moeten de circulaire buffercontainer initialiseren met een buffer en grootte
• ze moeten een circulaire buffercontainer vernietigen
• ze moeten de circulaire buffercontainer
• resetten ze moeten gegevens aan de buffer kunnen toevoegen
• ze moeten de volgende waarde uit de buffer kunnen halen
• ze moeten weten of de buffer vol of leeg is
• ze moeten het huidige aantal van elementen in de buffer
• ze moeten de maximale capaciteit van de buffer

kennen met behulp van deze lijst kunnen we een API samenstellen voor onze bibliotheek. Gebruikers zullen interageren met de circular buffer library met behulp van onze ondoorzichtige handle type, die wordt gemaakt tijdens initialisatie.

Ik heb uint8_t gekozen als het onderliggende gegevenstype in deze implementatie. Je kunt elk type gebruiken dat je leuk vindt-wees voorzichtig met de onderliggende buffer en het aantal bytes op de juiste manier.

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

bepalen of een Buffer vol is

voordat we verder gaan, moeten we een moment nemen om de methode te bespreken die we zullen gebruiken om te bepalen of de buffer vol of leeg is.

zowel de” volledige “als” lege “gevallen van de cirkelbuffer zien er hetzelfde uit: head en tail pointer zijn gelijk. Er zijn twee benaderingen om onderscheid te maken tussen VOL en leeg:

1. “Waste” een slot in de buffer:
   • volledige toestand is head + 1 == tail
   • lege toestand is head == tail
2. gebruik een boolvlag en aanvullende logica om staten te onderscheiden::
   • volledige status is full
   • lege status is (head == tail) && !full

We moeten ook threadveiligheid overwegen. Door een enkele lege cel te gebruiken om het “volledige” geval te detecteren, kunnen we een enkele producent en enkele consument ondersteunen zonder vergrendeling (zolang put en get niet dezelfde variabelen wijzigen). De wachtrij is thread-safe omdat de producent alleen de head index zal wijzigen, en de consument alleen de tail index zal wijzigen. Hoewel beide index in een bepaalde context enigszins verouderd is, heeft dit geen invloed op de veiligheid van de discussie in de wachtrij. Het gebruik van de full vlag creëert echter een vereiste voor wederzijdse uitsluiting. Dit komt omdat defull vlag wordt gedeeld door zowel de producent als de consument.

natuurlijk heeft het besluit zijn afwegingen. Als uw buffer element een grote geheugen footprint heeft (zoals een buffer die geschikt is voor een camera I-frame), kan het verspillen van een slot niet redelijk zijn op uw systeem. Als u meerdere producenten/consumenten interactie met een wachtrij, moet u een slot toch, dus het verspillen van een slot heeft geen zin. Als u geen wederzijdse uitsluiting beschikbaar heeft (bijvoorbeeld omdat u geen besturingssysteem gebruikt) maar u interrupts gebruikt, dan wilt u de niet-full vlagversie gebruiken. Het geheugenmodel dat op uw systeem wordt gebruikt, kan ook van invloed zijn op uw beslissing om zonder slot te gaan.

de implementatie hieronder gebruikt debool vlag. Het gebruik van de vlag vereist extra logica in de get en put routines om de vlag bij te werken. Ik zal ook beschrijven hoe de wijzigingen aan te brengen voor een enkele Producent / Consument die defull vlag niet gebruikt.

Circular Buffer Container Type

nu we inzicht hebben in de operaties die we moeten ondersteunen, kunnen we onze circular buffer container ontwerpen.

we gebruiken de container structuur voor het beheren van de status van de buffer. Om de inkapseling te behouden, wordt de containerstructuur gedefinieerd in onze bibliotheek .c bestand, in plaats van in de header.

we moeten bijhouden:

• de onderliggende gegevensbuffer
• de maximale grootte van de buffer
• de huidige “Head” – positie (verhoogd wanneer elementen worden toegevoegd)
• de huidige “tail” (verhoogd wanneer elementen worden verwijderd)
• een vlag die aangeeft of de buffer vol is of niet

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

nu onze container is ontworpen, zijn we klaar om de bibliotheekfuncties te implementeren.

implementatie

een belangrijk detail om op te merken is dat elk van onze API ‘ s een geïnitialiseerde bufferhandle vereist. In plaats van onze code te vervuilen met voorwaardelijke verklaringen, zullen we beweringen gebruiken om onze API-vereisten af te dwingen in de “Design by Contract” – stijl.

als de interfaces niet correct worden gebruikt, zal het programma onmiddellijk falen in plaats van dat de gebruiker de foutcode moet controleren en afhandelen.

bijvoorbeeld:

circular_buf_reset(NULL);

produceert:

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

een andere belangrijke opmerking is dat de implementatie hieronder niet thread-safe is. Er zijn geen sloten toegevoegd aan de onderliggende circulaire bufferbibliotheek.

initialiseren en resetten

laten we bij het begin beginnen: initialiseren van een circulaire buffer. Onze API heeft klanten bieden de onderliggende buffer en buffergrootte, en we retourneren een circulaire buffer handle aan hen. De reden dat we willen dat onze gebruikers de buffer leveren is dat dit zorgt voor een statisch toegewezen buffer. Als onze API de buffer onder de motorkap heeft gemaakt, moeten we gebruik maken van dynamische geheugentoewijzing, wat vaak niet is toegestaan in embedded systeemprogramma ‘ s.

we zijn verplicht om een circulaire bufferstructuur instantie binnen de bibliotheek aan te bieden, zodat we een pointer naar de gebruiker kunnen retourneren. Ik heb malloc voor de eenvoud gebruikt. Systemen die geen dynamisch geheugen kunnen gebruiken, hoeven alleen maar de functie init te wijzigen om een andere methode te gebruiken, zoals toewijzing uit een statische pool van vooraf toegewezen circulaire bufferstructuren.

een andere aanpak zou zijn om inkapseling te breken, waardoor gebruikers statisch circulaire buffercontainerstructuren buiten de bibliotheek kunnen declareren. In dit geval moet circular_buf_init worden bijgewerkt om een struct pointer te nemen. We kunnen ook onze init functie een containerstructuur op de stack aanmaken en deze in het groot retourneren. Echter, omdat de encapsulatie is verbroken, zullen gebruikers in staat zijn om de structuur te wijzigen zonder gebruik te maken van de bibliotheek routines. Als u encapsulation wilt behouden, moet u werken met pointers in plaats van concrete structuur instanties.

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

We zullen een handle retourneren naar een structuur die binnen de bibliotheek is toegewezen. Zodra we onze container hebben gemaakt, moeten we de waarden invullen en reset erop aanroepen. Voordat we terugkeren van init, zorgen we ervoor dat de buffer container in een lege staat is aangemaakt.

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

Het doel van de resetfunctie is om de buffer in een “lege” toestand te zetten, die een update vereist headtail, en full:

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

omdat we een methode hebben om een ronde buffer container aan te maken, hebben we een gelijkwaardige methode nodig om de container te vernietigen. In dit geval noemen we free op onze container. We proberen de onderliggende buffer niet vrij te maken, omdat we hem niet bezitten.

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

statuscontroles

vervolgens zullen we de functies implementeren die gerelateerd zijn aan de status van de buffercontainer.

de volledige functie is het makkelijkst te implementeren, omdat we een vlag hebben die de staat vertegenwoordigt:

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

Aangezien we de full vlag om onderscheid te maken tussen vol of leeg staat, combineren we de vlag met een cheque die head == tail:

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

De capaciteit van onze buffer werd geleverd tijdens de initialisatie, zo we zijn net terug die waarde voor de gebruiker:

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

de Berekening van het aantal elementen in de buffer is een lastiger probleem dan ik had verwacht. Veel voorgestelde grootte berekeningen gebruiken modulo, maar ik liep in vreemde hoek gevallen bij het testen van dat uit. Ik heb gekozen voor een vereenvoudigde berekening met behulp van voorwaardelijke verklaringen.

als de buffer vol is, weten we dat onze capaciteit op het maximum is. Als head groter-dan-of-gelijk is aan de tail, trekken we gewoon de twee waarden af om onze grootte te krijgen. Als tail groter is dan head, moeten we het verschil compenseren met max om de juiste grootte te krijgen.

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

gegevens toevoegen en verwijderen

met de boekhoudkundige functies uit de weg, is het tijd om in het vlees te graven: gegevens toevoegen en verwijderen uit de wachtrij.

het toevoegen en verwijderen van gegevens uit een circulaire buffer vereist manipulatie van de head en tail pointers. Bij het toevoegen van gegevens aan de buffer, voegen we de nieuwe waarde in op de huidige head locatie, dan gaan we verder met head. Wanneer we gegevens uit de buffer verwijderen, halen we de waarde van de huidige tail pointer op en gaan dan verder tail.

het toevoegen van gegevens aan de buffer vereist echter iets meer aandacht. Als de buffer full is, moeten we onze tail pointer verder zetten en ook head. We moeten ook controleren of het invoegen van een waarde de voorwaarde full triggert.

We gaan twee versies van de put functie implementeren, dus laten we onze pointer vooruitgang logica in een helper functie extraheren. Als onze buffer al vol is, gaan we verder met tail. We zetten altijd head door één. Nadat de pointer is gevorderd, vullen we de full vlag door te controleren of head == tail.

zie hieronder het gebruik van de Modulo-operator (%). Modulo zorgt ervoor dat de head en tail waarden worden gereset naar 0 wanneer de maximale grootte is bereikt. Dit zorgt ervoor dat head en tail altijd geldige indices van de onderliggende gegevensbuffer zijn.

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

zoals Miro Samek behulpzaam opmerkte, is dit een dure computationele operatie. In plaats daarvan kunnen we voorwaardelijke logica gebruiken om het totale aantal instructies te verminderen. Miro ‘ s aanbevolen aanpak is:

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

nu zal advance_pointer er zo uitzien:

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

We kunnen een soortgelijke helper functie maken die wordt aangeroepen wanneer een waarde uit de buffer wordt verwijderd. Wanneer we een waarde verwijderen, wordt de vlag full ingesteld op false, en de staartaanwijzer is geavanceerd.

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

We maken twee versies van de put functie. De eerste versie voegt een waarde in de buffer en de pointer vooruit. Als de buffer vol is, wordt de oudste waarde overschreven. Dit is de standaard use case voor een circulaire buffer

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

de tweede versie van de put functie geeft een fout terug als de buffer vol is. Dit is bedoeld voor demonstratiedoeleinden, maar we gebruiken deze variant niet in onze systemen.

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

om gegevens uit de buffer te verwijderen, benaderen we de waarde op de tail en werken vervolgens de tail bij. Als de buffer leeg is, geven we geen waarde terug of wijzigen we de pointer niet. In plaats daarvan geven we een fout terug aan de gebruiker.

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

dat de implementatie van onze circulaire bufferbibliotheek voltooit.

Gebruik

Bij het gebruik van de bibliotheek, de klant is verantwoordelijk voor het maken van de onderliggende data buffer circular_buf_init en een cbuf_handle_t terug:

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

Deze ingang wordt gebruikt om te communiceren met alle resterende bibliotheek functies:

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

vergeet niet de gratis zowel de onderliggende data buffer en de container wanneer u klaar bent:

free(buffer);circular_buf_free(cbuf);

een testprogramma dat gebruik maakt van de circulaire bufferbibliotheek kan worden gevonden in de embedded-resources repository.

wijzigingen voor het verwijderen van de volledige vlag

Als u defull wilt dumpen, zou u in plaats daarvan controleren of dehead één positie achter de staart is om te bepalen of de buffer vol is:

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

nu, als we willen vermijden de modulo-verrichting, kunnen wij voorwaardelijke logica in plaats daarvan gebruiken:

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

De lege geval is dan is dat head en tail hetzelfde:

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

Bij het ophalen van gegevens uit de buffer, zullen we vooraf de staart aanwijzer te wikkelen rond als nodig:

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

Bij het toevoegen van gegevens aan de buffer, bewaren wij de gegevens en vooraf de head pointer, wikkelen rond als nodig:

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

Andere verwijzingen naar full kunnen worden geëlimineerd.

C++

C++ leent zich voor een schonere circulaire bufferimplementatie dan C.

Klassendefinitie

we beginnen met het definiëren van onze C++ klasse. We willen dat onze C++ implementatie elk type data ondersteunt, dus we gaan er een templated class van maken.

onze API ‘ s zullen vergelijkbaar zijn met de C-implementatie. Onze klasse zal interfaces voor:

• de buffer resetten naar leeg
• gegevens toevoegen
• gegevens verwijderen
• volledige/lege status controleren
• het huidige aantal elementen in de buffer controleren
• de totale capaciteit van de buffer

We zullen ook C++ smart pointers gebruiken om ervoor te zorgen dat we geen gegevens achterlaten zodra onze buffer is vernietigd. Dit betekent dat we de buffer voor de gebruiker kunnen beheren.

een ander voordeel van C++ is de trivialiteit van het veilig maken van deze class thread: we kunnen vertrouwen op het std::mutex type (aangenomen dat dit is gedefinieerd voor uw platform).

Hier is onze klasse definitie:

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

C++ implementatie

onze C++ circulaire buffer bootst veel van de logica van de C implementatie, maar resulteert in een veel schoner en meer herbruikbaar ontwerp. Ook gebruikt de C++ – buffer std::mutex om een thread-veilige implementatie te bieden.

opmerking: dezelfde logische wijzigingen kunnen worden aangebracht in de C++-implementatie om thread-veiligheid te ondersteunen bij een enkele producent en consument door een slot te “verspillen”. Zie de aanpassingen in de C implementatie voor meer informatie.

initialisatie

bij het construeren van onze klasse wijzen we de gegevens toe voor onze onderliggende buffer en stellen we de buffergrootte in. Dit verwijdert de overhead die nodig is met de C-implementatie.

In tegenstelling tot de C-implementatie roept de C++ – constructor resetniet aan. Omdat we initiële waarden specificeren voor onze lidvariabelen, begint onze circulaire buffer in de juiste staat.

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

ons resetgedrag zet de buffer terug naar een lege toestand (head == tail && !full_).

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

Status Volgen

De logica van de empty en full gevallen is het dezelfde als de C-voorbeeld:

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

In de C++ – circulaire buffer uitvoering, size en capacity rapport het aantal elementen in de rij in de plaats van de grootte in bytes. Dit stelt ons in staat om agnostisch te zijn voor de onderliggende details van het type.

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

gegevens toevoegen

de logica voor put komt overeen met de C-implementatie. Deze implementatie maakt gebruik van het gedragspatroon” overschrijf de oudste waarde”.

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

opmerking: voor de eenvoud heb ik de optie weggelaten die modulo-operaties vermijdt. Je kunt die logica vinden in de C sectie.

Gegevens ophalen

de logica achter get komt overeen met de C-implementatie. In tegenstelling tot de C implementatie, wordt een lege waarde geretourneerd als de buffer leeg is.

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

opmerking: return T() retourneert een standaard geconstrueerde waarde voor ra bepaald type. De werkelijk geproduceerde waarde hangt af van het type of de constructeur. Ook, voor de eenvoud, heb ik de optie die modulo operaties vermijdt weggelaten. Je kunt die logica vinden in de C sectie.

gebruik

De C++ circulaire buffer is veel eenvoudiger te gebruiken dan de C implementatie.

om een cirkelbuffer te installeren, declareren we gewoon een object en specificeren we het templated type voor onze buffer. Hier is een voorbeeld met behulp van een buffer van 10 uint32_t entries:

circular_buffer<uint32_t> circle(10);

gegevens toevoegen is eenvoudig:

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

en gegevens ophalen is even eenvoudig:

x = circle.get()

onthoud dat aangezien dit een templated klasse is, u een cirkelbuffer kunt maken van elk type dat u nodig hebt.

Updates voor C++17

In C++17 hebben we toegang totstd::optional, waardoor we een waarde kunnen vertegenwoordigen die al dan niet aanwezig is. Onze getfunctie geeft een std::optional<T> terug. We zouden ook std::nullopt teruggeven in plaats van een standaard geconstrueerde T als de wachtrij leeg is.

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

opmerking: voor de eenvoud heb ik de optie weggelaten die modulo-operaties vermijdt. Je kunt die logica vinden in de C sectie.

In de aanroepende code kunt u controleren op een geldige waarde met behulp van de Booleaanse operator of de has_value member functie. Als er een geldige waarde aanwezig is, kan deze worden benaderd met behulp van de -> of * operators, ur met behulp van de value() member functie.

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

alles samenvoegen

voorbeelden van implementaties zijn te vinden in de embedded-resources GitHub repository.

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

Als u deze bibliotheek wilt uitbreiden, is het een nuttige oefening om extra API ‘ s toe te voegen om gebruikers in staat te stellen meerdere elementen toe te voegen of te verwijderen met één enkele bewerking. U kunt de C implementatie thread ook veilig maken.

Thread Safety met de Lookahead methode

een benadering voor thread-safety zonder mutex is de “lookahead” methode. Deze methode ondersteunt een enkele producent draad en enkele consument draad; meerdere producenten of consumenten zullen een slot nodig hebben.

in plaats van de Booleaanse vlag te gebruiken om onderscheid te maken tussen de volle en lege gevallen, zullen we altijd één cel leeg laten. Door een enkele lege cel te gebruiken om het “volledige” geval te detecteren, kunnen we een enkele producent en enkele consument ondersteunen zonder vergrendeling (zolang put en get niet dezelfde variabelen wijzigen).

u kunt zich zorgen maken over het verspillen van een slot, maar deze afweging is vaak veel goedkoper dan de kosten van het gebruik van een OS lock primitive.

Verder Lezen

• C++ Smart Pointers
• Greppel Uw C-Stye tips voor Slimme Verwijzingen

Hier zijn een andere circulaire buffer-implementaties:

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

Voor meer informatie over circulaire buffers:

• Embedded.com: Ring buffer-basis
• Wikipedia: Circulaire buffer
• Ferro-Systemen: Slot Gratis Ring Buffer
• Boost Circulaire Buffer
• C++: Performance of a Circular Buffer vs Vector, Deque, and List
• Lock-Free Single – Producer-Single Consumer Circular Queue

Er is een voorstel om een circulair buffertype toe te voegen aan de C++ standard library:

• P0059: Een Voorstel om toe te Voegen Ring Span tot de Standaard Bibliotheek
  • Ring Span
  • Ring Span Lite

Change Log

• 20210321
  • Vaste fout met max_size_ waar cbuf->max zouden zijn gebruikt
  • Toegevoegd verduidelijking van de tekst met betrekking tot de reden waarom de buffer wordt doorgegeven door de gebruiker,
• 20210301
  • Gericht feedback van Miro met betrekking tot het vermijden van modulo-activiteiten
• 20210213
  • extra koppelingen
  • Toegevoegd verdere discussie over de afweging tussen volledige vlag vs met een “verspild” slot
  • Toon wijzigingen voor thread veiligheid met een enkele producent/consument
  • notities Toevoegen aan std::optional gebruiken met C++17
• 20191016
  • Wijziging Log sectie-opmaak voor de consistentie in de website
  • Gedegradeerd headers voor consistentie in de hele site
  • Vast gebroken Inhoudsopgave links
  • Verwijderd Change Log van Inhoudsopgave
• 20190627
  • link Toegevoegd aan Ferro-Systemen’ Lock Vrij Ring Buffer artikel.
• 20190604
  • een typefout opgelost (bedankt Chris Svec!) en veranderde enkele formulering met betrekking tot het ondoorzichtige type.
• 20181219
  • toegevoegd opmerking over het vermijden van concurrentieproblemen met één producent en één consument met behulp van een leeg vak.
• 20180804
  • het artikel is geherstructureerd en herschreven.Dank aan iedereen die onderweg feedback heeft gegeven. De voorbeelden zijn bijgewerkt naar:
  • verwijder defensief programmeren
  • gebruik asserties
  • Maak een standalone bibliotheek met een ondoorzichtige structuur
  • Breid de API ‘ s uit, inclusief een berekening voor de huidige ronde buffergrootte
  • Update de bibliotheek zodat er geen slot