Oppdatert: 20210321

på grunn av den ressursbegrensede naturen til innebygde systemer, kan sirkulære bufferdatastrukturer finnes i de fleste prosjekter.

Sirkulære buffere (også kjent som ringbuffere) er buffere med fast størrelse som fungerer som om minnet er sammenhengende & sirkulær i naturen. Som minne genereres og forbrukes, trenger data ikke å bli stokkes – heller, hode/hale pekere er justert. Når data legges til, går hodepekeren videre. Når data forbrukes, går halepekeren videre. Hvis du kommer til slutten av bufferen, pekerne bare vikle rundt til begynnelsen.

For en mer detaljert oppsummering av sirkulær bufferoperasjon, se Wikipedia-artikkelen. Resten av artikkelen forutsetter at du har en forståelse av hvordan sirkulære buffere fungerer.

Innholdsfortegnelse:

1. Hvorfor bruke En Sirkulær Buffer?
2. C Implementering
   1. VED Hjelp Av Innkapsling
   2. API Design
   3. Bestemme om En Buffer Er Full
   4. Sirkulær Bufferbeholder Type
   5. Implementering
   6. Bruk
   7. Modifikasjoner For Å Fjernefull flagg
3. C++ Implementering
   1. class definition
   2. implementering
   3. Bruk
   4. OPPDATERINGER for c++17
4. sette Det Hele Sammen
5. videre Lesing

hvorfor bruke En Sirkulær buffer?

Sirkulære buffere brukes ofte som køer med fast størrelse. Den faste størrelsen er gunstig for innebygde systemer, da utviklere ofte prøver å bruke statiske datalagringsmetoder i stedet for dynamiske tildelinger.

Sirkulære buffere er også nyttige strukturer for situasjoner der dataproduksjon og forbruk skjer i forskjellige hastigheter: de nyeste dataene er alltid tilgjengelige. Hvis forbrukeren ikke kan holde tritt med produksjonen, blir de foreldede dataene overskrevet med nyere data. Ved å bruke en sirkulær buffer kan vi sikre at vi alltid bruker de nyeste dataene.

for ytterligere brukstilfeller, sjekk Ut Ring Buffer Basics på Embedded.com.

C Implementering

Vi starter Med en c implementering, da dette utsetter oss for noen av designutfordringene og avvikene når vi lager et sirkulært bufferbibliotek.

Ved Hjelp Av Innkapsling

Siden vi lager et sirkulært bufferbibliotek, vil vi sørge for at brukerne jobber med bibliotekets Apier i stedet for å endre strukturen direkte. Vi ønsker også å beholde implementeringen i biblioteket vårt, slik at vi kan endre det etter behov, uten at sluttbrukerne må oppdatere koden sin. Brukeren trenger ikke å vite noen detaljer om vår struktur, bare at den eksisterer.

i vår bibliotekoverskrift vil vi videresende deklarere strukturen:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

vi vil ikke at brukere skal jobbe med en circular_but_t peker direkte, da de kan få inntrykk av at de kan dereferere verdien. Vi vil lage en handtakstype som de kan bruke i stedet.

den enkleste tilnærmingen til håndtaket vårt er åtypedefcbuf_handle_t som en peker til den sirkulære bufferen. Dette vil hindre oss fra å måtte kaste pekeren innenfor vår funksjon implementering.

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

en alternativ tilnærming ville være å gjøre håndtaket til enuintptr_t ellervoid* verdi. Inne i grensesnittet vårt vil vi håndtere oversettelsen til riktig pekertype. Vi holder den sirkulære buffertypen skjult for brukere, og den eneste måten å samhandle med dataene på er gjennom håndtaket.

Vi skal holde fast ved den enkle håndtaks implementeringen for å holde vår eksempelkode enkel og grei.

API Design

Først bør vi tenke på hvordan brukerne vil samhandle med en sirkulær buffer:

• De må initialisere den sirkulære bufferbeholderen med en buffer og størrelse
• De må ødelegge en sirkulær bufferbeholder
• de må tilbakestille den sirkulære bufferbeholderen
• De Må kunne legge til data i bufferen
• De Må kunne få neste verdi fra bufferen
• De trenger å vite om bufferen er full eller tom
• De trenger å vite det nåværende antall elementer i bufferen
• De trenger å vite maksimal kapasitet på bufferen

Ved hjelp av denne listen kan Vi sette sammen en api for biblioteket vårt. Brukere vil samhandle med det sirkulære bufferbiblioteket ved hjelp av vår ugjennomsiktige håndtakstype, som opprettes under initialisering.

jeg har valgt uint8_t som den underliggende datatypen i denne implementeringen. Du kan bruke en bestemt type du liker – bare vær forsiktig med å håndtere den underliggende bufferen og antall byte på riktig måte.

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

Bestemme om En Buffer Er Full

før vi fortsetter, bør vi ta et øyeblikk for å diskutere metoden vi skal bruke for å avgjøre om bufferen er full eller tom.

både» fulle «og» tomme»tilfeller av den sirkulære bufferen ser det samme ut: head og tail pekeren er like. Det er to tilnærminger til å skille mellom full og tom:

1. «Avfall» et spor i bufferen:
   • Full tilstand er head + 1 == tail
   • Tom tilstand er head == tail
2. Bruk en bool flagg og ekstra logikk for å skille mellom stater::
   • Full tilstand erfull
3. Tom tilstand er (head == tail) && !full

vi bør også vurdere trådsikkerhet. Ved å bruke en enkelt tom celle for å oppdage» full » saken, kan vi støtte en enkelt produsent og enkelt forbruker uten lås (så lengeput ogget ikke endre de samme variablene). Køen er trådsikker fordi produsenten bare vil endre head – indeksen, og forbrukeren vil bare endretail – indeksen. Selv om en indeks kan være litt utdatert i en gitt kontekst, vil dette ikke påvirke trådsikkerheten i køen. Bruk avfull – flagget skaper imidlertid et krav om gjensidig utelukkelse. Dette skyldes at full – flagget deles av både produsent og forbruker.

selvfølgelig har beslutningen sine avvik. Hvis bufferelementet har et stort minnefotavtrykk (for eksempel en buffer som er dimensjonert for et kamera i-ramme), kan det hende at det ikke er rimelig å kaste bort et spor på systemet. Hvis du har flere produsenter/forbrukere som samhandler med en kø, trenger du en lås uansett, så det er ikke fornuftig å kaste bort et spor. Hvis du ikke har gjensidig utelukkelse tilgjengelig (for eksempel fordi du ikke bruker ET OS), men du bruker avbrudd, vil du bruke ikke – full flaggversjon. Minnemodellen som brukes på systemet ditt, kan også påvirke beslutningen om å gå uten lås.

implementeringen nedenfor brukerbool flagget. Bruk av flagget krever ekstra logikk i get og put rutiner for å oppdatere flagget. Jeg vil også beskrive hvordan du gjør endringene for en enkelt produsent / forbruker som ikke bruker flaggetfull.

Sirkulær Bufferbeholder Type

Nå som vi har en forståelse av operasjonene vi trenger å støtte, kan vi designe vår sirkulære bufferbeholder.

vi bruker beholderstrukturen for å administrere bufferens tilstand. For å bevare innkapsling er beholderstrukturen definert inne i biblioteket vårt .c fil, i stedet for i overskriften.

Vi må holde styr på:

• den underliggende databufferen
• den maksimale størrelsen på bufferen
• den nåværende «head» – posisjonen (økes når elementer legges til)
• den nåværende «tail» (økes når elementer fjernes)
• et flagg som indikerer om bufferen er full eller ikke

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

nå som vår container er designet, er vi klare til å implementere bibliotekets funksjoner.

Implementering

en viktig detalj å merke seg er at hver Av Våre Apier krever et initialisert bufferhåndtak. I stedet for å kaste koden vår med betingede uttalelser, vil vi bruke påstander for å håndheve VÅRE API-krav i» Design by Contract » – stilen.

hvis grensesnittene er feil brukt, vil programmet mislykkes umiddelbart i stedet for at brukeren må sjekke og håndtere feilkoden.

For eksempel:

circular_buf_reset(NULL);

Produserer:

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

Et annet viktig notat er at implementeringen vist nedenfor ikke er trådsikker. Ingen låser er lagt til det underliggende sirkulære bufferbiblioteket.

Initialiser og Tilbakestill

La oss starte i begynnelsen: initialisere en sirkulær buffer. VÅR API har kunder som gir den underliggende bufferen og bufferstørrelsen, og vi returnerer et sirkulært bufferhåndtak til dem. Grunnen til at vi vil at brukerne skal gi bufferen, er at dette gir mulighet for en statisk tildelt buffer. Hvis VÅR API opprettet bufferen under hetten, måtte vi gjøre bruk av dynamisk minneallokering, som ofte ikke er tillatt i innebygde systemprogrammer.

Vi er pålagt å gi en sirkulær bufferstruktur forekomst i biblioteket slik at vi kan returnere en peker til brukeren. Jeg har brukt malloc for enkelhet. Systemer som ikke kan bruke dynamisk minne, trenger bare å endre init -funksjonen for å bruke en annen metode, for eksempel tildeling fra et statisk utvalg av forhåndstildelte sirkulære bufferstrukturer.

En annen tilnærming ville være å bryte innkapsling, slik at brukerne statisk deklarerer sirkulære bufferbeholderstrukturer utenfor biblioteket. I dette tilfellet må circular_buf_init oppdateres for å ta en struct-peker. Vi kunne også ha vår init funksjon lag en beholderstruktur på stakken og returner den engros. Men siden innkapsling er ødelagt, vil brukerne kunne endre strukturen uten å bruke bibliotekrutinene. Hvis du vil bevare innkapsling, må du jobbe med pekere i stedet for konkrete strukturforekomster.

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

vi vil returnere et håndtak til en struktur som er tildelt inne i biblioteket. Når vi har opprettet vår container, må vi fylle verdiene og ringe reset på den. Før vi kommer tilbake fra init, sikrer vi at bufferbeholderen er opprettet i tom tilstand.

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

formålet med tilbakestillingsfunksjonen er å sette bufferen i en» tom»tilstand, som krever oppdatering headtail og full:

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

Siden vi har en metode for å lage en sirkulær bufferbeholder, trenger vi en tilsvarende metode for å ødelegge beholderen. I dette tilfellet kaller vi free på vår container. Vi forsøker ikke å frigjøre den underliggende bufferen, siden vi ikke eier den.

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

Statskontroller

deretter implementerer vi funksjonene knyttet til tilstanden til bufferbeholderen.

den fulle funksjonen er den enkleste å implementere, siden vi har et flagg som representerer staten:

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

siden vi har full flagget for å skille mellom full eller tom tilstand, kombinerer vi flagget med en sjekk at head == tail:

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

kapasiteten til bufferen ble levert under initialisering, så vi returnerer bare den verdien til brukeren:

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

beregning av antall elementer i bufferen var et vanskeligere problem enn jeg forventet. Mange foreslåtte størrelsesberegninger bruker modulo, men jeg løp inn i merkelige hjørnesaker når jeg testet det ut. Jeg valgte en forenklet beregning ved hjelp av betingede uttalelser.

hvis bufferen er full, vet vi at kapasiteten vår er maksimal. Hvis head er større enn eller lik til tail, trekker vi bare de to verdiene for å få størrelsen vår. Hvis tail er større enn head, må vi kompensere forskjellen med max for å få riktig størrelse.

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

Legge Til Og Fjerne Data

med bokføringsfunksjonene ute av veien, er det på tide å grave inn i kjøttet: legge til og fjerne data fra køen.

Legge til og fjerne data fra en sirkulær buffer krever manipulering av head og tail pekere. Når du legger til data i bufferen, setter vi inn den nye verdien ved gjeldende head plassering, så går vi videre head. Når vi fjerner data fra bufferen, henter vi verdien av gjeldende tail peker og deretter forhånd tail.

Å Legge til data i bufferen krever imidlertid litt mer tanke. Hvis bufferen er full, må vi fremme vår tail peker samt head. Vi må også sjekke om å sette inn en verdi utløserfull – tilstanden.

Vi skal implementere to versjoner av put – funksjonen, så la oss trekke ut pekeren vår i en hjelperfunksjon. Hvis bufferen vår allerede er full, går vi videre tail. Vi går alltid videre head av en. Etter at pekeren er avansert, fyller vifull flagget ved å sjekke om head == tail.

Merk bruken av modulo-operatøren (%) nedenfor. Modulo vil føre til athead ogtail verdiene tilbakestilles til 0 når maksimal størrelse er nådd. Dette sikrer at head og tail alltid er gyldige indekser for den underliggende databufferen.

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

Som Miro Samek påpekte, er dette en dyr beregningsoperasjon. I stedet kan vi bruke betinget logikk for å redusere totalt antall instruksjoner. Miro anbefalte tilnærming er:

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

Nå,advance_pointer vil se slik ut:

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

Vi kan lage en lignende hjelpefunksjon som kalles når du fjerner en verdi fra bufferen. Når vi fjerner en verdi, er full flagget satt til false, og halepekeren er avansert.

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

vi lager to versjoner avput – funksjonen. Den første versjonen setter inn en verdi i bufferen og flytter pekeren. Hvis bufferen er full, overskrives den eldste verdien. Dette er standard brukstilfellet for en sirkulær buffer

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

den andre versjonen avput – funksjonen returnerer en feil hvis bufferen er full. Dette er gitt for demonstrasjonsformål, men vi bruker ikke denne varianten i våre systemer.

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

for å fjerne data fra bufferen får vi tilgang til verdien påtail og oppdaterertail pekeren. Hvis bufferen er tom, returnerer vi ikke en verdi eller endrer pekeren. I stedet returnerer vi en feil til brukeren.

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

som fullfører implementeringen av vårt sirkulære bufferbibliotek.

Bruk

når du bruker biblioteket, er klienten ansvarlig for å opprette den underliggende databufferen til circular_buf_init, og en cbuf_handle_t returneres:

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

dette håndtaket brukes til å samhandle med alle gjenværende biblioteksfunksjoner:

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

ikke glem å frigjøre både den underliggende databufferen og beholderen når du er ferdig:

free(buffer);circular_buf_free(cbuf);

et testprogram som bruker det sirkulære bufferbiblioteket, finnes i det innebygde ressursregisteret.

Modifikasjoner For Å Fjerne hele flagget

hvis du ønsket å droppe full flagget, ville du i stedet sjekke at head er en posisjon bak halen for å avgjøre om bufferen er full:

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

nå, hvis Vi ønsket å unngå Modulo-operasjonen, kan vi bruke betinget logikk i stedet:

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

den tomme saken er da at head og tail er de samme:

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

når vi får data fra bufferen, vil vi fremme halepeker, innpakning rundt om nødvendig:

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

når du legger til data i bufferen, lagrer vi dataene og fremmer hodepekeren, innpakning om nødvendig:

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

andre referanser til full kan elimineres.

C++

C++ gir seg til en renere sirkulær bufferimplementering enn C.

Klassedefinisjon

Vi starter med å definere Vår c++ – klasse. Vi vil at vår c++ – implementering skal støtte alle typer data, så vi skal gjøre det til en malbasert klasse.

Våre Apier skal være lik c-implementeringen. Vår klasse vil gi grensesnitt for:

Tilbakestilling av bufferen til tom

Legge til data

Fjerne data

Kontrollere full / tom tilstand

Kontrollere gjeldende antall elementer i bufferen

Kontrollere den totale kapasiteten til bufferen

Vi vil også bruke c++ smarte pekere for å sikre at vi ikke legger igjen data når bufferen er ødelagt. Dette betyr at vi kan administrere bufferen for brukeren.En annen fordel Med C++ er trivialiteten ved å gjøre denne klassen trådsikker: vi kan stole påstd::mutex type (forutsatt at dette er definert for plattformen din).

her er vår klassedefinisjon:

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++ – Implementering

Vår c++ sirkulære buffer etterligner mye av logikken Fra c-implementeringen, men resulterer i en mye renere og mer gjenbrukbar design. C++ – bufferen benytter også std::mutex for å gi en trådsikker implementering.

Merk: de samme logiske endringene kan gjøres I c++-implementeringen for å støtte trådsikkerhet med en enkelt produsent og forbruker ved å «kaste bort» et spor. Se justeringene I c-implementeringen for mer informasjon.

Initialisering

når vi bygger vår klasse, tildeler vi dataene for vår underliggende buffer og angir bufferstørrelsen. Dette fjerner overhead som kreves Med c-implementeringen.

I Motsetning Til c-implementeringen kaller Ikke c++ – konstruktøren reset. Fordi vi angir startverdier for våre medlemsvariabler, starter vår sirkulære buffer i riktig tilstand.

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

vår tilbakestillingsadferd setter bufferen tilbake til en tom tilstand (head == tail && !full_).

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

Tilstandssporing

logikken til empty og full tilfeller er det samme Som c-eksemplet:

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

i c++ sirkulær buffer implementering, size og capacity rapportere antall elementer i køen i stedet for størrelsen i byte. Dette tillater oss å være agnostiker til de underliggende detaljene av typen.

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

Legge Til Data

logikken for put samsvarer Med c-implementeringen. Denne implementeringen bruker atferdsmønsteret «overskrive den eldste verdien».

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

Merk: For enkelhets skyld har jeg utelatt alternativet som unngår modulo-operasjoner. Du kan finne den logikken I C-delen.

Henter Data

logikken bakget samsvarer Med c-implementeringen. I motsetning Til c-implementeringen returneres en tom verdi hvis bufferen er tom.

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

Merk: return T() vil returnere en standard konstruert verdi for gitt type. Den faktiske verdien som produseres, avhenger av typen eller konstruktøren. Også, for enkelhet, har jeg utelatt alternativet som unngår modulo-operasjoner. Du kan finne den logikken I C-delen.

Bruk

c++ sirkulær buffer er mye enklere å bruke enn c-implementeringen.

for å starte en sirkulær buffer, erklærer vi bare et objekt og angir malertypen for bufferen vår. Her er et eksempel ved hjelp av en buffer på 10 uint32_t oppføringer:

circular_buffer<uint32_t> circle(10);

Å Legge til data er enkelt:

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

og å få data er like enkelt:

x = circle.get()

Husk at siden dette er en malbasert klasse, kan du opprette en sirkulær buffer av hvilken som helst type du trenger.

Oppdateringer For C++17

I C++17 har vi tilgang til std::optional, som gjør at vi kan representere en verdi som kanskje eller kanskje ikke er til stede. Vår get – funksjon vil returnere en std::optional<T>. Vi vil også returnere std::nullopt i stedet for en standardkonstruertT hvis køen er tom.

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

Merk: For enkelhets skyld har jeg utelatt alternativet som unngår modulo-operasjoner. Du kan finne den logikken I C-delen.

i anropskoden kan du se etter en gyldig verdi ved hjelp av den boolske operatoren ellerhas_value medlemsfunksjon. Hvis en gyldig verdi er til stede, kan den nås ved hjelp av-> eller* operatorer, ur ved hjelp avvalue() medlemsfunksjon.

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

Sette det Hele sammen

Eksempel implementeringer kan bli funnet iembedded-resources Github repository.

• c sirkulær buffer test program
  • C sirkulær buffer bibliotek
• c++ sirkulær buffer eksempel

Hvis du ønsker å utvide dette biblioteket, er en nyttig øvelse å legge til flere Apier for å gjøre det mulig for brukere å legge til / fjerne flere elementer med en enkelt operasjon. Du kan også gjøre c implementering thread-safe.

Trådsikkerhet med Lookahead-Metoden

en tilnærming for trådsikkerhet uten mutex er «lookahead» – metoden. Denne metoden støtter en enkelt produsent tråd og enkelt forbruker tråd; flere produsenter eller forbrukere vil kreve en lås.I Stedet for å bruke det boolske flagget for å skille mellom de fulle og tomme tilfellene, vil vi alltid forlate en celle tom. Ved å bruke en enkelt tom celle for å oppdage» full » saken, kan vi støtte en enkelt produsent og enkelt forbruker uten lås (så lengeput ogget ikke endre de samme variablene).

Du kan være bekymret for å kaste bort et spor, men denne avviket er ofte mye billigere enn kostnaden ved Å bruke EN os-lås primitiv.

Videre Lesing

• C++ Smarte Pekere
• Grøft Dine C-Stye Pekere For Smarte Pekere

her er andre sirkulære buffer implementeringer:

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

For mer informasjon om sirkulære buffere:

• Embedded.com: Ring buffer grunnleggende
• Wikipedia: Sirkulær buffer
• Jernholdige Systemer: Lås Gratis Ring Buffer
• Boost Sirkulær Buffer
• C++: Ytelse Av En Sirkulær Buffer vs Vektor, Deque og List
• Lock-Free Single-Producer-Single Consumer Circular Queue

det er et forslag til å legge til en sirkulær buffertype I c++ standardbiblioteket:

• P0059: Et Forslag Om Å Legge Ring Span Til Standard Biblioteket
  • Ring Span

Endre Logg

• 20210321
  • Fast feil medmax_size_ dercbuf->max bør ha tekst om hvorfor bufferen Er Sendt inn av brukeren
• 20210301
  • adressert tilbakemelding fra miro om å unngå modulo operasjoner
• 20210213
  • lagt til flere lenker
  • lagt til videre diskusjon om avveining mellom full flagg vs ved hjelp av en «bortkastet» spor
  • Vis modifikasjoner for trådsikkerhet med en enkelt produsent/forbruker
  • Legg til notater påstd::optional bruk Med C++17
• 20191016
  • Oppdatert endringslogg seksjon formatering for konsistens på tvers av området
  • Degraderte overskrifter for konsistens på tvers av området
  • Fast brutt Innholdsfortegnelse lenker
  • fjernet Endringslogg fra innholdsfortegnelsen
• 20190627
  • lagt link til jernholdige systemer’ lås gratis ring buffer Artikkel.
• 20190604
  • Fikset en skrivefeil (Takk Chris Svec!) og endret noen ordlyd relatert til den ugjennomsiktige typen.
• 20181219
  • Lagt til merknad om å unngå samtidighetsproblemer med en enkelt produsent og enkelt forbruker ved hjelp av et tomt spor.
• 20180804
  • artikkelen ble omstrukturert og omskrevet.Takk til alle som ga tilbakemelding underveis. Eksemplene er oppdatert til:Bruk påstander
  • Opprett et frittstående bibliotek ved hjelp av en ugjennomsiktig struktur
  • Utvid Apiene, inkludert en beregning for den nåværende sirkulære bufferstørrelsen
  • Oppdater biblioteket slik at det ikke sløser bort et spor