opdateret: 20210321

på grund af den ressourcebegrænsede karakter af indlejrede systemer kan cirkulære bufferdatastrukturer findes i de fleste projekter.

cirkulære buffere (også kendt som ringbuffere) er buffere i fast størrelse, der fungerer som om hukommelsen er sammenhængende& cirkulær i naturen. Da hukommelsen genereres og forbruges, behøver data ikke at blive omstillet – snarere justeres hoved – /halepegerne. Når data tilføjes, hoved pointer fremskridt. Når data forbruges, fortsætter halepegeren. Hvis du når slutningen af bufferen, vikles pegerne simpelthen rundt til begyndelsen.

for en mere detaljeret oversigt over cirkulær bufferoperation henvises til artiklen. Resten af artiklen antager, at du har en forståelse af, hvordan cirkulære buffere fungerer.

Indholdsfortegnelse:

1. Hvorfor bruge en cirkulær Buffer?
2. C implementering
   1. brug af indkapsling
   2. API Design
   3. bestemmelse af, om en Buffer er fuld
   4. cirkulær Bufferbeholdertype
   5. implementering
   6. anvendelse
   7. ændringer til fjernelse affull flag
3. C++ implementering
   1. klasse definition
   2. implementering
   3. brug
   4. opdateringer til C++17
4. sætte det hele sammen
5. yderligere læsning

hvorfor bruge en cirkulær buffer?

cirkulære buffere bruges ofte som køer i fast størrelse. Den faste størrelse er gavnlig for indlejrede systemer, da udviklere ofte forsøger at bruge statiske datalagringsmetoder snarere end dynamiske tildelinger.

cirkulære buffere er også nyttige strukturer til situationer, hvor dataproduktion og-forbrug sker i forskellige hastigheder: de seneste data er altid tilgængelige. Hvis forbrugeren ikke kan følge med i produktionen, overskrives de uaktuelle data med nyere data. Ved at bruge en cirkulær buffer kan vi sikre, at vi altid bruger de nyeste data.

for yderligere brugssager, tjek Grundlæggende om Ringbuffer på Embedded.com.

C-implementering

Vi starter med en C-implementering, da dette udsætter os for nogle af designudfordringerne og afvejningerne, når vi opretter et cirkulært bufferbibliotek.

brug af indkapsling

da vi opretter et cirkulært bufferbibliotek, vil vi sikre os, at brugerne arbejder med vores Biblioteks-API ‘ er i stedet for at ændre strukturen direkte. Vi ønsker også at beholde implementeringen indeholdt i vores bibliotek, så vi kan ændre den efter behov uden at kræve, at slutbrugerne opdaterer deres kode. Brugeren behøver ikke at vide nogen detaljer om vores struktur, kun at den eksisterer.

i vores biblioteksoverskrift vil vi videresende erklære strukturen:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

Vi ønsker ikke, at brugerne skal arbejde med en circular_but_t pointer direkte, da de måske får indtryk af, at de kan dereference værdien. Vi opretter en håndtagstype, som de kan bruge i stedet.

den enkleste tilgang til vores håndtag er at typedefcbuf_handle_t som en peger til den cirkulære buffer. Dette forhindrer os i at skulle kaste markøren inden for vores funktionsimplementering.

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

en alternativ tilgang ville være at gøre håndtaget til enuintptr_tellervoid* værdi. Inde i vores interface, ville vi håndtere oversættelsen til den relevante pointer type. Vi holder den cirkulære buffertype skjult for brugerne, og den eneste måde at interagere med dataene på er gennem håndtaget.

vi vil holde fast i den enkle håndtagsimplementering for at holde vores eksempelkode enkel og ligetil.

API Design

først skal vi tænke på, hvordan brugerne vil interagere med en cirkulær buffer:

• de skal initialisere den cirkulære bufferbeholder med en buffer og størrelse
• de skal ødelægge en cirkulær bufferbeholder
• de skal nulstille den cirkulære bufferbeholder
• de skal være i stand til at tilføje data til bufferen
• de skal være i stand til at få den næste værdi fra bufferen
• de skal vide, om bufferen er fuld eller Tom
• De har brug for at kende det aktuelle antal bufferbeholdere
• elementer i bufferen
• de har brug for at kende bufferens maksimale kapacitet

Ved hjælp af denne liste kan vi sammensætte en API til vores bibliotek. Brugere vil interagere med det cirkulære bufferbibliotek ved hjælp af vores uigennemsigtige håndtagstype, som oprettes under initialisering.

Jeg har valgt uint8_t som den underliggende datatype i denne implementering. Du kan bruge en bestemt type, du kan lide – bare vær forsigtig med at håndtere den underliggende buffer og antallet af bytes korrekt.

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

bestemmelse af, om en Buffer er fuld

før vi fortsætter, skal vi tage et øjeblik til at diskutere den metode, vi vil bruge til at bestemme, om eller buffer er fuld eller tom.

både de” fulde “og” tomme”tilfælde af den cirkulære buffer ser det samme ud: head og tail pointer er ens. Der er to tilgange til at skelne mellem fuld og Tom:

1. “affald” en slot i bufferen:
   • fuld tilstand er head + 1 == tail
   • tom tilstand er head == tail
2. brug en bool flag og yderligere logik for at differentiere stater::
   • fuld tilstand er full
   • tom tilstand er (head == tail) && !full

Vi bør også overveje trådsikkerhed. Ved at bruge en enkelt tom celle til at registrere den “fulde” sag kan vi understøtte en enkelt producent og en enkelt forbruger uden en lås (så længe put og get ændrer ikke de samme variabler). Køen er trådsikker, fordi producenten kun vil ændre head indekset, og forbrugeren vil kun ændre tail indekset. Mens begge indeks måske er lidt forældede i en given sammenhæng, dette påvirker ikke trådens sikkerhed i køen. Brug af full flag skaber dog et krav om gensidig udelukkelse. Dette skyldes, at full flag deles af både producent og forbruger.

selvfølgelig har beslutningen sine afvejninger. Hvis dit bufferelement har et stort hukommelsesaftryk (såsom en buffer, der er dimensioneret til et kamera i-frame), er det muligvis ikke rimeligt at spilde en slot på dit system. Hvis du har flere producenter/forbrugere, der interagerer med en kø, skal du alligevel have en lås, så spild af en slot giver ikke mening. Hvis du ikke har gensidig udelukkelse tilgængelig (f.eks. fordi du ikke bruger et operativsystem), men du bruger interrupts, så vil du bruge ikke-full flag version. Hukommelsesmodellen, der bruges på dit system, kan også have indflydelse på din beslutning om at gå uden lås.

implementeringen nedenfor brugerbool flag. Brug af flaget kræver yderligere logik iget ogput rutiner for at opdatere flaget. Jeg vil også beskrive, hvordan man foretager ændringerne for en enkelt producent/forbruger, der ikke bruger full flag.

cirkulær Bufferbeholdertype

nu hvor vi har en forståelse for de operationer, vi skal understøtte, kan vi designe vores cirkulære bufferbeholder.

Vi bruger containerstrukturen til styring af bufferens tilstand. For at bevare indkapsling defineres containerstrukturen inde i vores bibliotek .c fil, snarere end i overskriften.

Vi bliver nødt til at holde styr på:

• den underliggende databuffer
• bufferens maksimale størrelse
• den aktuelle “hoved” – position (øges, når elementer tilføjes)
• den aktuelle “hale” (øges, når elementer fjernes)
• et flag, der angiver, om bufferen er fuld eller ej

// 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 hvor vores container er designet, er vi klar til at implementere biblioteksfunktionerne.

implementering

en vigtig detalje at bemærke er, at hver af vores API ‘ er kræver et initialiseret bufferhåndtag. I stedet for at fylde vores kode med betingede udsagn, vil vi bruge påstande til at håndhæve vores API-krav i stilen “Design by Contract”.

hvis grænsefladerne bruges forkert, mislykkes programmet straks i stedet for at kræve, at brugeren kontrollerer og håndterer fejlkoden.

for eksempel:

circular_buf_reset(NULL);

producerer:

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

en anden vigtig note er, at implementeringen vist nedenfor ikke er trådsikker. Der er ikke tilføjet nogen låse til det underliggende cirkulære bufferbibliotek.

Initialiser og Nulstil

lad os starte i begyndelsen: initialisering af en cirkulær buffer. Vores API har klienter, der leverer den underliggende buffer og bufferstørrelse, og vi returnerer et cirkulært bufferhåndtag til dem. Årsagen til, at vi ønsker, at vores brugere skal levere bufferen, er, at dette giver mulighed for en statisk tildelt buffer. Hvis vores API oprettede bufferen under hætten, skulle vi bruge dynamisk hukommelsesallokering, hvilket ofte ikke er tilladt i indlejrede systemprogrammer.

Vi er forpligtet til at give en cirkulær bufferstrukturforekomst i biblioteket, så vi kan returnere en markør til brugeren. Jeg har brugt malloc for enkelhed. Systemer, der ikke kan bruge dynamisk hukommelse, skal blot ændre init-funktionen for at bruge en anden metode, såsom tildeling fra en statisk pulje af forud tildelte cirkulære bufferstrukturer.

en anden tilgang ville være at bryde indkapsling, så brugerne statisk kan erklære cirkulære bufferbeholderstrukturer uden for biblioteket. I dette tilfælde skal circular_buf_init opdateres for at tage en struct pointer. Vi kunne også have vores init funktion Opret en containerstruktur på stakken og returner den engros. Men da indkapsling er brudt, vil brugerne være i stand til at ændre strukturen uden at bruge bibliotekets rutiner. Hvis du vil bevare indkapsling, skal du arbejde med peger 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 returnerer et håndtag til en struktur, der er tildelt inde i biblioteket. Når vi har oprettet vores container, skal vi udfylde værdierne og kalde reset på den. Før vi vender tilbage fra init, sikrer vi, at bufferbeholderen er oprettet 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 nulstillingsfunktionen er at sætte bufferen i en “tom” tilstand, som kræver opdatering headtail og full:

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

da vi har en metode til at oprette en cirkulær bufferbeholder, har vi brug for en tilsvarende metode til at ødelægge beholderen. I dette tilfælde kalder vi free på vores container. Vi forsøger ikke at frigøre den underliggende buffer, da vi ikke ejer den.

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

tilstandskontrol

dernæst implementerer vi funktionerne relateret til bufferbeholderens tilstand.

den fulde funktion er den nemmeste at implementere, da vi har et flag, der repræsenterer staten:

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

da vi har full flag for at skelne mellem fuld eller tom tilstand, kombinerer vi flaget med en kontrol af, at head == tail:

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

kapaciteten af vores buffer blev leveret under initialisering, så vi returnerer bare denne værdi til brugeren:

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

beregning af antallet af elementer i bufferen var et vanskeligere problem end forventet. Mange foreslåede størrelsesberegninger bruger modulo, men jeg løb ind i mærkelige hjørnesager, da jeg testede det. Jeg valgte en forenklet beregning ved hjælp af betingede udsagn.

hvis bufferen er fuld, ved vi, at vores kapacitet er maksimalt. Hvis header større end eller lig med tail, trækker vi simpelthen de to værdier for at få vores størrelse. Hvis tail er større end head, skal vi udligne forskellen med max for at få den korrekte 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;}

Tilføjelse og fjernelse af Data

med bogføringsfunktionerne ude af vejen er det tid til at grave i kødet: Tilføjelse og fjernelse af data fra køen.

Tilføjelse og fjernelse af data fra en cirkulær buffer kræver manipulation af head og tail pointere. Når vi tilføjer data til bufferen, indsætter vi den nye værdi på den nuværende head placering, så går vi videre head. Når vi fjerner data fra bufferen, henter vi værdien af den nuværende tail pointer og derefter frem tail.

tilføjelse af data til bufferen kræver dog lidt mere tanke. Hvis bufferen er full, skal vi fremme vores tail pointer samt head. Vi skal også kontrollere, om indsættelse af en værdi udløser full tilstand.

Vi skal implementere to versioner afput – funktionen, så lad os udtrække vores pointer advancement-logik til en hjælperfunktion. Hvis vores buffer allerede er fuld, går vi videre tail. Vi fremmer altid head af en. Når markøren er blevet avanceret, udfylder vifull flag ved at kontrollere, omhead == tail.

Bemærk brugen af modulo-operatøren (%) nedenfor. Modulo vil medføre, at head og tail værdierne nulstilles til 0, når den maksimale størrelse er nået. Dette sikrer, at headog tail altid er gyldige indekser for den underliggende databuffer.

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 hjælpsomt påpegede, er dette en dyr beregningsoperation. I stedet kan vi bruge betinget logik til at reducere det samlede antal instruktioner. Miros anbefalede tilgang er:

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

nu, advance_pointer vil se sådan ud:

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 lave en lignende hjælperfunktion, der kaldes, når du fjerner en værdi fra bufferen. Når vi fjerner en værdi, er full flagget indstillet til false, og halepekeren er avanceret.

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

Vi opretter to versioner afput funktion. Den første version indsætter en værdi i bufferen og fremmer markøren. Hvis bufferen er fuld, overskrives den ældste værdi. Dette er standardbrugssagen for en cirkulær buffer

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

den anden version af funktionenput returnerer en fejl, hvis bufferen er fuld. Dette leveres til demonstrationsformål, men vi bruger ikke denne variant i vores 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 at fjerne data fra bufferen får vi adgang til værdien vedtailog opdaterer dereftertail pointer. Hvis bufferen er tom, returnerer vi ikke en værdi eller ændrer markøren. I stedet returnerer vi en fejl til brugeren.

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

der fuldender implementeringen af vores cirkulære bufferbibliotek.

brug

når du bruger biblioteket, er klienten ansvarlig for at oprette den underliggende databuffer til circular_buf_init, og a 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åndtag bruges til at interagere med alle resterende biblioteksfunktioner:

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

glem ikke at frigøre både den underliggende databuffer og containeren, når du er færdig:

free(buffer);circular_buf_free(cbuf);

et testprogram, der bruger det cirkulære bufferbibliotek, findes i det indlejrede ressourcelager.

ændringer til fjernelse af det fulde flag

Hvis du ville grøfte full flag, vil du i stedet kontrollere, at head er en position bag halen for at afgøre, om bufferen er fuld:

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, hvis vi ønskede at undgå Modulo-operationen, kan vi i stedet bruge betinget logik:

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 sag er så, 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 halen af buff ‘ en, og vi vil pointer, indpakning om nødvendigt:

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 vi tilføjer data til bufferen, gemmer vi dataene og forskyder hovedpegeren, om nødvendigt indpakning:

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 henvisninger til full kan elimineres.

C++

C++ egner sig til en renere cirkulær bufferimplementering end C.

Klassedefinition

Vi starter med at definere vores c++ klasse. Vi ønsker, at vores C++ – implementering skal understøtte enhver form for data, så vi vil gøre det til en templated klasse.

vores API ‘ er vil svare til C-implementeringen. Vores klasse vil give grænseflader til:

• nulstilling af bufferen til Tom
• tilføjelse af data
• fjernelse af data
• kontrol af fuld/tom tilstand
• kontrol af det aktuelle antal elementer i bufferen
• kontrol af bufferens samlede kapacitet

Vi vil også bruge C++ smart pointers for at sikre, at vi ikke efterlader nogen data, når vores buffer er ødelagt. Det betyder, at vi kan styre bufferen for brugeren.

en anden fordel ved C++ er trivialiteten ved at gøre denne klasse trådsikker: vi kan stole på std::mutex type (forudsat at dette er defineret for din platform).

Her er vores klassedefinition:

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

vores C++ cirkulære buffer efterligner meget af logikken fra C-implementeringen, men resulterer i et meget renere og mere genanvendeligt design. C++ – bufferen bruger også std::mutex for at give en trådsikker implementering.

Bemærk: de samme logiske ændringer kan foretages i C++-implementeringen for at understøtte trådsikkerhed med en enkelt producent og forbruger ved at “spilde” en slot. Se justeringerne i C-implementeringen for at få flere oplysninger.

initialisering

når vi konstruerer vores klasse, tildeler vi dataene til vores underliggende buffer og indstiller bufferstørrelsen. Dette fjerner de omkostninger, der kræves med C-implementeringen.

I modsætning til C-implementeringen kalder C++ – konstruktøren ikkereset. Fordi vi angiver indledende værdier for vores medlemsvariabler, starter vores cirkulære buffer i den rigtige tilstand.

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

vores nulstillingsadfærd sætter bufferen tilbage til en tom tilstand (head == tail && !full_).

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

Tilstandssporing

logikken i empty og full sager er de 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++ cirkulær bufferimplementering rapporterer size og capacity antallet af elementer i køen snarere end størrelsen i bytes. Dette giver os mulighed for at være agnostiske over for de underliggende detaljer af 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;}

tilføjelse af Data

logikken for put matcher C-implementeringen. Denne implementering bruger adfærdsmønsteret” overskriv den ældste værdi”.

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

Bemærk: For nemheds skyld har jeg udeladt den mulighed, der undgår modulo-operationer. Du kan finde den logik i C-sektionen.

henter Data

logikken bag get matcher C-implementeringen. I modsætning til C-implementeringen returneres en tom værdi, 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;}

Bemærk: return T() returnerer en standardkonstrueret værdi for den givne type. Den faktiske værdi produceret afhænger af typen eller konstruktøren. Også for enkelhed har jeg udeladt den mulighed, der undgår modulo-operationer. Du kan finde den logik i C-sektionen.

brug

C++ cirkulær buffer er meget enklere at bruge end C-implementeringen.

for at instantiere en cirkulær buffer erklærer vi bare et objekt og specificerer den templerede type for vores buffer. Her er et eksempel ved hjælp af en buffer på 10 uint32_t poster:

circular_buffer<uint32_t> circle(10);

tilføjelse af data er let:

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

og at få data er lige så let:

x = circle.get()

Husk, at da dette er en templeret klasse, kan du oprette en cirkulær buffer af enhver type, du har brug for.

opdateringer til C++17

i C++17 har vi adgang tilstd::optional, som gør det muligt for os at repræsentere en værdi, der måske eller måske ikke er til stede. Vores getfunktion ville returnere enstd::optional<T>. Vi vil også returnere std::nullopti stedet for en standardkonstrueret T 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;}

Bemærk: for enkelhed har jeg udeladt den mulighed, der undgår modulo-operationer. Du kan finde den logik i C-sektionen.

i opkaldskoden kan du tjekke for en gyldig værdi ved hjælp af den boolske operatør ellerhas_value medlemsfunktion. Hvis en gyldig værdi er til stede, kan den fås ved hjælp af -> eller * operatorer, ur ved hjælp af value() medlemsfunktion.

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

sætte det hele sammen

eksempel implementeringer kan findes iembedded-resources Github repository.

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

Hvis du ønsker at udvide dette bibliotek, er en nyttig øvelse at tilføje yderligere API ‘ er, så brugerne kan tilføje/fjerne flere elementer med en enkelt handling. Du kan også gøre C-implementeringstråden sikker.

Trådsikkerhed med Lookahead-metoden

en tilgang til trådsikkerhed uden muteks er “lookahead”-metoden. Denne metode understøtter en enkelt producent tråd og enkelt forbruger tråd; flere producenter eller forbrugere vil kræve en lås.

i stedet for at bruge det boolske flag til at skelne mellem de fulde og tomme sager, vil vi altid lade en celle være tom. Ved at bruge en enkelt tom celle til at registrere den “fulde” sag kan vi understøtte en enkelt producent og en enkelt forbruger uden en lås (så længe put og get ændrer ikke de samme variabler).

Du kan være bekymret for at spilde en slot, men denne afvejning er ofte meget billigere end omkostningerne ved at bruge en OS-lås primitiv.

yderligere læsning

• C++ Smart Pointers
• Ditch your C-Stye Pointers for Smart Pointers

Her er andre cirkulære bufferimplementeringer:

• Kvantumleaps/lock-free-ring-buffer
• vilemt/BipBuffer

For mere information om cirkulære buffere:

• Embedded.com: ring buffer basics
• cirkulær buffer
• jernholdige systemer: Lås Fri ring Buffer
• Boost cirkulær Buffer
• C++: Udførelse af en cirkulær Buffer vs vektor, Deke og liste
• Lock-Free Single – Producer-single Consumer cirkulær kø

Der er et forslag om at tilføje en cirkulær buffertype til C++ standardbibliotek:

• P0059: Et forslag om at tilføje Ring Span til standardbiblioteket
  • Ring Span
  • Ring Span Lite

Skift Log

• 20210321
  • Fast fejl med max_size_hvorcbuf->maxskulle have været brugt
  • tilføjet afklarende tekst om, hvorfor bufferen sendes ind af brugeren
• 20210301
  • adresseret feedback fra Miro vedrørende undgåelse af Modulo-operationer
• 20210213
  • tilføjet yderligere links
  • tilføjet yderligere diskussion om afvejning mellem fuld flag vs ved hjælp af en “spildt” slot
  • Vis ændringer for trådsikkerhed med en enkelt producent/forbruger
  • Tilføj noter om std::optional brug med C++17
• 20191016
  • opdateret Ændringslogsektionsformatering for konsistens på tværs af siden
  • degraderede overskrifter for konsistens på tværs af siden
  • fast brudt tabel over indhold links
  • fjernet Ændringslog fra indholdsfortegnelsen
• 20190627
  • tilføjet link til Ferro systems’ lock free ring buffer artikel.
• 20190604
  • Rettet en skrivefejl (tak Chris Svec!) og ændret nogle ordlyd relateret til den uigennemsigtige type.
• 20181219
  • tilføjet note om at undgå samtidighedsproblemer med en enkelt producent og enkelt forbruger ved hjælp af en tom slot.
• 20180804
  • artiklen blev omstruktureret og omskrevet.Tak til alle, der gav feedback undervejs. Eksemplerne er opdateret til:
  • Fjern defensiv programmering
  • brug påstande
  • Opret et selvstændigt bibliotek ved hjælp af en uigennemsigtig struktur
  • Udvid API ‘ erne, inklusive en beregning for den aktuelle cirkulære bufferstørrelse
  • Opdater biblioteket, så det ikke spildte en slot