actualizat: 20210321

datorită naturii limitate a resurselor sistemelor încorporate, structurile de date tampon circulare pot fi găsite în majoritatea proiectelor.

tampoanele circulare (cunoscute și sub numele de tampoane inelare) sunt tampoane de dimensiuni fixe care funcționează ca și cum memoria este contiguă& circulară în natură. Pe măsură ce memoria este generată și consumată, datele nu trebuie remaniate – mai degrabă, indicatoarele cap/coadă sunt ajustate. Când se adaugă date, indicatorul capului avansează. Când datele sunt consumate, indicatorul de coadă avansează. Dacă ajungeți la sfârșitul tamponului, indicii se înfășoară pur și simplu la început.

pentru un rezumat mai detaliat al funcționării tamponului circular, vă rugăm să consultați articolul Wikipedia. Restul articolului presupune că aveți o înțelegere a modului în care funcționează tampoanele circulare.

cuprins:

1. De ce să folosiți un tampon Circular?
2. implementare C
   1. folosind încapsulare
   2. API Design
   3. determinarea dacă un tampon este plin
   4. tampon circular tip Container
   5. implementare
   6. utilizare
   7. modificări pentru eliminareafull Pavilion
3. implementare c++
   1. definiție clasă
   2. punerea în aplicare
   3. utilizare
   4. actualizări pentru C++17
4. punerea totul împreună
5. lectură suplimentară

de ce să folosiți un tampon circular?

tampoanele circulare sunt adesea folosite ca cozi de dimensiuni fixe. Dimensiunea fixă este benefică pentru sistemele încorporate, deoarece dezvoltatorii încearcă adesea să utilizeze metode statice de stocare a datelor, mai degrabă decât alocări dinamice.tampoanele circulare sunt, de asemenea, structuri utile pentru situațiile în care producția și consumul de date au loc la rate diferite: cele mai recente date sunt întotdeauna disponibile. Dacă consumatorul nu poate ține pasul cu producția, datele învechite vor fi suprascrise cu date mai recente. Folosind un tampon circular, ne putem asigura că consumăm întotdeauna cele mai recente date.

pentru cazuri suplimentare de utilizare, verificați elementele de bază ale tamponului de inel pe Embedded.com.

implementare C

vom începe cu o implementare C, deoarece aceasta ne expune la unele dintre provocările de proiectare și compromisuri atunci când creăm o bibliotecă tampon circulară.

folosind încapsularea

deoarece creăm o bibliotecă tampon circulară, vrem să ne asigurăm că utilizatorii lucrează cu API-urile bibliotecii noastre în loc să modifice structura direct. De asemenea, dorim să păstrăm implementarea conținută în biblioteca noastră, astfel încât să o putem schimba după cum este necesar, fără a solicita utilizatorilor finali să își actualizeze codul. Utilizatorul nu trebuie să cunoască detalii despre structura noastră, ci doar că există.

în antetul bibliotecii noastre, vom transmite declararea structurii:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

nu dorim ca utilizatorii să lucreze cu un circular_but_t pointer direct, deoarece ar putea avea impresia că pot dereferența valoarea. Vom crea un tip de mâner pe care îl pot folosi în schimb.

cea mai simplă abordare pentru mânerul nostru este de atypedefcbuf_handle_t ca un pointer la tamponul circular. Acest lucru ne va împiedica să avem nevoie să aruncăm indicatorul în implementarea funcției noastre.

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

o abordare alternativă ar fi ca mânerul să fie uintptr_t sau void* valoare. În interiorul interfeței noastre, ne-am ocupa de traducerea la tipul de pointer corespunzător. Păstrăm tipul de tampon circular ascuns de utilizatori, iar singura modalitate de a interacționa cu datele este prin mâner.

vom rămâne cu implementarea simplă a mânerului pentru a păstra codul nostru de exemplu simplu și direct.

API Design

În primul rând ,ar trebui să ne gândim la modul în care utilizatorii vor interacționa cu un tampon circular:

• trebuie să inițializeze containerul tampon circular cu un tampon și dimensiunea
• trebuie să distrugă un container tampon circular
• trebuie să reseteze containerul tampon circular
• trebuie să poată adăuga date la tampon
• trebuie să poată obține următoarea valoare din tampon
• trebuie să știe dacă tamponul este plin sau gol
• trebuie să cunoască numărul curent de elemente în buffer
• ei trebuie să cunoască capacitatea maximă a buffer

folosind această listă, putem pune împreună un API pentru biblioteca noastră. Utilizatorii vor interacționa cu Biblioteca tampon circular folosind tipul nostru mâner opac, care este creat în timpul inițializării.

am alesuint8_t ca tip de date de bază în această implementare. Puteți utiliza orice tip particular care vă place-trebuie doar să aveți grijă să gestionați tamponul de bază și numărul de octeți în mod corespunzător.

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

determinarea dacă un tampon este plin

înainte de a continua, ar trebui să luăm un moment pentru a discuta metoda vom folosi pentru a determina dacă sau tampon este plin sau gol.

atât cazurile „complete”, cât și „goale” ale tamponului circular arată la fel:head șitail pointer sunt egale. Există două abordări pentru diferențierea între plin și gol:

1. „deșeuri” un slot în tampon:
   • starea completă estehead + 1 == tail
   • starea goală estehead == tail
2. utilizați unbool Flag și logică suplimentară pentru diferențierea stărilor::
   • starea completă estefull
   • starea goală este(head == tail) && !full

ar trebui să luăm în considerare și siguranța firului. Folosind o singură celulă goală pentru a detecta cazul „complet”, putem sprijini un singur producător și un singur consumator fără blocare (atâta timp cât put și get nu modificați aceleași variabile). Coada este thread-safe, deoarece producătorul va modifica doar head index, iar consumatorul va modifica doartail index. În timp ce oricare index ar putea fi ușor depășit într-un context dat, acest lucru nu va afecta siguranța firului cozii. Cu toate acestea, utilizarea steaguluifull creează o cerință pentru excluderea reciprocă. Acest lucru se datorează faptului că full este partajat atât de producător, cât și de consumator.

desigur, decizia are compromisurile sale. Dacă elementul tampon are o amprentă de memorie mare (cum ar fi un tampon care este dimensionat pentru un cadru i al camerei), este posibil ca pierderea unui slot să nu fie rezonabilă pe sistemul dvs. Dacă aveți mai mulți producători/consumatori care interacționează cu o coadă, veți avea nevoie oricum de o blocare, astfel încât irosirea unui slot nu are sens. Dacă nu aveți excludere reciprocă disponibilă (de exemplu, pentru că nu utilizați un sistem de operare), dar utilizați întreruperi, atunci veți dori să utilizați non-full versiune de pavilion. Modelul de memorie utilizat pe sistemul dvs. poate avea, de asemenea, un impact asupra deciziei dvs. de a merge fără blocare.

implementarea de mai jos folosește steagulbool. Utilizarea steagului necesită logică suplimentară înget șiput rutine pentru actualizarea steagului. Voi descrie, de asemenea, modul de a face modificările pentru un singur producător/consumator care nu utilizează full Pavilion.

tip container tampon Circular

acum, că avem o înțelegere asupra operațiunilor pe care va trebui să le susținem, putem proiecta containerul tampon circular.

folosim structura containerului pentru gestionarea stării tamponului. Pentru a păstra încapsularea, structura containerului este definită în interiorul bibliotecii noastre .c, mai degrabă decât în antet.

va trebui să urmărim:

• tamponul de date subiacent
• dimensiunea maximă a tamponului
• poziția curentă „cap” (incrementată atunci când sunt adăugate elemente)
• „coada” curentă (incrementată atunci când elementele sunt eliminate)
• un steag care indică dacă tamponul este plin sau nu

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

acum că containerul nostru este proiectat, suntem gata să implementăm funcțiile bibliotecii.

implementare

un detaliu important de reținut este că fiecare dintre API-urile noastre necesită un mâner tampon inițializat. Mai degrabă decât gunoi codul nostru cu declarații condiționale, vom utiliza afirmații pentru a pune în aplicare cerințele noastre API în „Design de Contract” stil.

dacă interfețele sunt utilizate în mod necorespunzător, programul va eșua imediat, mai degrabă decât să solicite utilizatorului să verifice și să gestioneze codul de eroare.

de exemplu:

circular_buf_reset(NULL);

produce:

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

o altă notă importantă este că implementarea prezentată mai jos nu este sigură pentru fir. Nu s-au adăugat încuietori la Biblioteca tampon circulară subiacentă.

inițializați și resetați

să începem de la început: inițializarea unui tampon circular. API-ul nostru are clienții care furnizează tamponul de bază și dimensiunea tamponului și le returnăm un mâner tampon circular. Motivul pentru care dorim ca utilizatorii noștri să furnizeze tamponul este că acest lucru permite un tampon alocat static. Dacă API-ul nostru a creat tamponul sub capotă, ar trebui să folosim alocarea dinamică a memoriei, care este adesea interzisă în programele de sisteme încorporate.

suntem obligați să furnizăm o instanță de structură tampon circulară în bibliotecă, astfel încât să putem returna un pointer utilizatorului. Am folosit malloc pentru simplitate. Sistemele care nu pot utiliza memoria dinamică trebuie pur și simplu să modifice funcția init pentru a utiliza o metodă diferită, cum ar fi alocarea dintr-un bazin static de structuri tampon circulare pre-alocate.

o altă abordare ar fi ruperea încapsulării, permițând utilizatorilor să declare static structuri circulare de containere tampon în afara bibliotecii. În acest caz,circular_buf_init trebuie actualizat pentru a lua un pointer struct. De asemenea, am putea avea funcția init creați o structură de container pe stivă și returnați-o cu ridicata. Cu toate acestea, deoarece încapsularea este întreruptă, utilizatorii vor putea modifica structura fără a utiliza rutinele bibliotecii. Dacă doriți să păstrați încapsularea, trebuie să lucrați cu indicii în loc de instanțe de structură din beton.

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

vom returna un mâner unei structuri care este alocată în interiorul bibliotecii. Odată ce am creat containerul nostru, avem nevoie popula valorile și apel reset pe ea. Înainte de a reveni de la init, ne asigurăm că containerul tampon a fost creat într-o stare goală.

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

Scopul funcției de resetare este de a pune tamponul într-o stare” goală”, care necesită actualizarea headtail șifull:

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

deoarece avem o metodă de a crea un container tampon circular, avem nevoie de o metodă echivalentă pentru distrugerea containerului. În acest caz, numim free pe containerul nostru. Nu încercăm să eliberăm tamponul de bază, deoarece nu îl deținem.

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

verificări de stare

în continuare, vom implementa funcțiile legate de starea containerului tampon.

funcția completă este cea mai ușor de implementat, deoarece avem un steag care reprezintă statul:

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

deoarece avem full pentru a diferenția între starea completă sau goală, combinăm steagul cu o verificare că head == tail:

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

capacitatea bufferului nostru a fost furnizată în timpul inițializării, așa că returnăm această valoare utilizatorului:

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

calcularea numărului de elemente din Buffer a fost o problemă mai complicată decât mă așteptam. Multe calcule de dimensiuni propuse folosesc modulo, dar am dat peste cazuri de colț ciudate când am testat asta. Am optat pentru un calcul simplificat folosind declarații condiționale.

dacă tamponul este plin, știm că capacitatea noastră este la maxim. Dacă head este mai mare decât sau egal cu tail, pur și simplu scădem cele două valori pentru a obține dimensiunea noastră. Dacă tail este mai mare decât head, trebuie să compensăm diferența cu max pentru a obține dimensiunea corectă.

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

Adăugarea și eliminarea datelor

cu funcțiile de contabilitate din drum, este timpul să săpați în carne: adăugarea și eliminarea datelor din coadă.

Adăugarea și eliminarea datelor dintr-un tampon circular necesită manipularea indicatoarelorhead șitail. Când adăugăm date la tampon, introducem noua valoare la locația curentă head, apoi avansăm head. Când eliminăm datele din tampon, recuperăm valoarea curentătail pointer și apoi avansămtail.

adăugarea de date la tampon necesită totuși un pic mai multă gândire. Dacă tamponul estefull, trebuie să avansămtail pointer precum șihead. De asemenea, trebuie să verificăm dacă introducerea unei valori declanșează condiția full.

vom implementa două versiuni ale funcțieiput, deci să extragem logica noastră de avansare a indicatorului într-o funcție de ajutor. Dacă bufferul nostru este deja plin, avansăm tail. Întotdeauna avansăm head cu unul. După ce indicatorul a fost avansat, vom popula fullPavilion verificând dacăhead == tail.

notați utilizarea operatorului modulo (%) de mai jos. Modulo va face ca valorilehead șitail să se reseteze la 0 când se atinge dimensiunea maximă. Acest lucru asigură căhead șitail sunt întotdeauna indici valabili ai tamponului de date subiacent.

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

după cum a subliniat util Miro Samek, aceasta este o operație de calcul costisitoare. În schimb, putem folosi logica condiționată pentru a reduce numărul total de instrucțiuni. Abordarea recomandată de Miro este:

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

acum, advance_pointer va arăta astfel:

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

putem face o funcție de ajutor similară care este apelată la eliminarea unei valori din tampon. Când eliminăm o valoare, full steagul este setat la false, iar indicatorul de coadă este avansat.

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

vom crea două versiuni ale funcțieiput. Prima versiune introduce o valoare în tampon și avansează indicatorul. Dacă tamponul este plin, cea mai veche valoare va fi suprascrisă. Acesta este cazul de utilizare standard pentru un tampon circular

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

a doua versiune a funcțieiput returnează o eroare dacă tamponul este plin. Acest lucru este oferit în scopuri demonstrative, dar nu folosim această variantă în sistemele noastre.

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

pentru a elimina datele din tampon, accesăm valoarea la tail și apoi actualizăm tail pointer. Dacă tamponul este gol, nu returnăm o valoare sau nu modificăm indicatorul. În schimb, returnăm o eroare utilizatorului.

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

care completează implementarea bibliotecii noastre tampon circulare.

utilizare

când utilizați biblioteca, clientul este responsabil pentru crearea tamponului de date subiacent la circular_buf_init și un cbuf_handle_t este returnat:

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

acest mâner este utilizat pentru a interacționa cu toate funcțiile rămase ale bibliotecii:

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

nu uitați să eliberați atât tamponul de date subiacent, cât și containerul când ați terminat:

free(buffer);circular_buf_free(cbuf);

un program de testare care utilizează biblioteca tampon circulară poate fi găsit în depozitul embedded-resources.

modificări pentru eliminarea steagului complet

Dacă doriți să renunțați la full, verificați în schimb dacă head este o poziție în spatele cozii pentru a determina dacă tamponul este plin:

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

acum, dacă am vrut să evităm operația Modulo, putem folosi logica condiționată în schimb:

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

cazul gol este atunci că head și tail sunt aceleași:

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

când obținem date din tampon, vom avansa coada pointer, înfășurându-se dacă este necesar:

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

când adăugăm date la tampon, vom stoca datele și vom avansa indicatorul capului, înfășurându-ne dacă este necesar:

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

alte referințe la full pot fi eliminate.

C++

C++ se pretează la o implementare mai curată a tamponului circular decât C.

definiția clasei

vom începe prin definirea clasei noastre c++. Vrem ca implementarea noastră C++ să susțină orice tip de date, așa că o vom face o clasă templată.API-urile noastre vor fi similare cu implementarea C. Clasa noastră va oferi interfețe pentru:

• resetarea tamponului la gol
• adăugarea de date
• eliminarea datelor
• Verificarea stării complete/goale
• verificarea numărului curent de elemente din buffer
• verificarea capacității totale a buffer-ului

vom utiliza, de asemenea, indicatoare inteligente C++ pentru a ne asigura că nu lăsăm date în jur odată ce buffer-ul nostru este distrus. Aceasta înseamnă că putem gestiona tamponul pentru utilizator.

un alt beneficiu al C++ este trivialitatea de a face această clasă thread-safe: ne putem baza pestd::mutex tip (presupunând că acest lucru este definit pentru platforma dvs.).

iată definiția clasei noastre:

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

implementarea C++

tamponul nostru circular c++ imită o mare parte din logica implementării C, dar are ca rezultat un design mult mai curat și mai reutilizabil. De asemenea, tamponul c++ utilizează std::mutex pentru a oferi o implementare sigură a firului.

notă: aceleași modificări logice pot fi făcute în implementarea C++ pentru a sprijini siguranța firului cu un singur producător și consumator prin „irosirea” unui slot. Consultați ajustările din implementarea C pentru mai multe informații.

inițializare

când construim clasa noastră, alocăm datele pentru tamponul nostru de bază și setăm dimensiunea bufferului. Aceasta elimină cheltuielile generale necesare cu implementarea C.

spre deosebire de implementarea C, constructorul C++ nu apeleazăreset. Deoarece specificăm valorile inițiale pentru variabilele noastre membre, tamponul nostru circular începe în starea corectă.

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

comportamentul nostru de resetare readuce tamponul la o stare goală (head == tail && !full_).

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

urmărirea stării

logica empty și full cazuri este aceeași cu exemplul 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_;}

în implementarea tamponului circular c++, size și capacity raportează numărul de elemente din coadă mai degrabă decât dimensiunea în octeți. Acest lucru ne permite să fim agnostici la detaliile subiacente ale tipului.

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

adăugarea de date

logica pentruput se potrivește cu implementarea C. Această implementare folosește modelul comportamental” suprascrie cea mai veche valoare”.

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

notă: pentru simplitate, am omis opțiunea care evită operațiile modulo. Puteți găsi această logică în secțiunea C.

preluarea datelor

logica din spateleget se potrivește cu implementarea C. Spre deosebire de implementarea C, o valoare goală este returnată dacă tamponul este gol.

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

notă: return T() va returna o valoare construită implicit pentru tipul dat. Valoarea reală produsă depinde de tipul sau constructorul. De asemenea, pentru simplitate, am omis opțiunea care evită operațiunile modulo. Puteți găsi această logică în secțiunea C.

utilizare

tamponul circular C++ este mult mai simplu de utilizat decât implementarea C.

pentru a instantia un buffer circular, declaram doar un obiect si specificam tipul templated pentru buffer-ul nostru. Iată un exemplu folosind un tampon de 10uint32_t intrări:

circular_buffer<uint32_t> circle(10);

adăugarea datelor este ușoară:

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

și obținerea datelor este la fel de ușoară:

x = circle.get()

amintiți-vă că, deoarece aceasta este o clasă templată, puteți crea un tampon circular de orice tip de care aveți nevoie.

actualizări pentru C++17

în C++17, avem acces lastd::optional, ceea ce ne permite să reprezentăm o valoare care poate fi sau nu prezentă. Funcția noastră get ar returna un std::optional<T>. De asemenea, am reveni std::nullopt în loc de un ID div construit implicitT dacă coada este goală.

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

notă: pentru simplitate, am omis opțiunea care evită operațiile modulo. Puteți găsi această logică în secțiunea C.

în codul de apelare, puteți verifica o valoare validă folosind operatorul boolean sau funcția de membru has_value. Dacă este prezentă o valoare validă, aceasta poate fi accesată folosind -> sau * operatori, ur folosind value() funcție de membru.

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

punerea totul împreună

exemplu implementările pot fi găsite înembedded-resources GitHub repository.

• C Program de testare tampon circular
  • C bibliotecă tampon circular
• c++ exemplu tampon circular

Dacă sunteți în căutarea de a extinde această bibliotecă, un exercițiu util este de a adăuga API-uri suplimentare pentru a permite utilizatorilor să adauge/elimina mai multe elemente cu o singură operație. De asemenea, puteți face firul de implementare c sigur.

siguranța filetului cu metoda Lookahead

o abordare pentru siguranța filetului fără mutex este metoda „lookahead”. Această metodă acceptă un singur fir de producător și un singur fir de consumator; mai mulți producători sau consumatori vor necesita o blocare.

în loc să folosim steagul boolean pentru a face diferența între cazurile complete și cele goale, vom lăsa întotdeauna o celulă goală. Folosind o singură celulă goală pentru a detecta cazul „complet”, putem sprijini un singur producător și un singur consumator fără blocare (atâta timp cât put și get nu modificați aceleași variabile).

s-ar putea să vă preocupe pierderea unui slot, dar acest compromis este adesea mult mai ieftin decât costul utilizării unui primitiv de blocare a sistemului de operare.

lecturi suplimentare

• c++ indicii inteligente
• șanț c-Stye indicii pentru indicii inteligente

aici sunt alte implementări tampon circulare:

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

Pentru mai multe informații cu privire la tampoane circulare:

• Embedded.com: bazele tampon Inel
• Wikipedia: tampon Circular
• sisteme feroase: blocare tampon Inel liber
• Boost tampon Circular
• C++: Performanța unui tampon Circular vs Vector, Deque, și lista
• Lock-Free Single-Producător – un singur consumator Coadă circulară

există o propunere pentru adăugarea unui tip tampon circular la biblioteca standard C++:

• P0059: O propunere de a adăuga interval de inel la biblioteca Standard
  • interval de inel
  • interval de inel Lite

jurnal de schimbare

• 20210321
  • Eroare fixă cu max_size_ unde cbuf->max au fost utilizate
  • adăugat text clarificator cu privire la motivul pentru care tamponul este transmis de utilizator
• 20210301
  • feedback adresat de la Miro cu privire la evitarea operațiunilor modulo
• 20210213
  • adăugat link-uri suplimentare
  • adăugat discuții suplimentare despre compromis între Flag complet vs folosind slot
  • arată modificările de siguranță fir cu un singur producător/consumator
  • Adăugați note pestd::optional utilizați cu C++17
• 20191016
  • actualizat Schimbare jurnal secțiunea Formatare pentru coerența pe site-ul
  • anteturi retrogradat pentru coerența pe site-ul
  • fix rupt cuprins link-uri
  • a fost eliminat Jurnalul de modificări din Cuprins
• 20190627
  • link adăugat la articolul tampon Inel de blocare fără sisteme feroase.
• 20190604
  • Fixed o greșeală de scriere (Multumesc Chris Svec!) și a schimbat unele formulări legate de tipul opac.
• 20181219
  • adăugat notă despre evitarea problemelor de concurență cu un singur producător și un singur consumator folosind un slot gol.
• 20180804
  • articolul a fost restructurat și rescris.Mulțumesc tuturor celor care au oferit feedback pe parcurs. Exemplele au fost actualizate la:
  • eliminați programarea defensivă
  • utilizați afirmații
  • creați o bibliotecă independentă folosind o structură opacă
  • extindeți API-urile, inclusiv un calcul pentru dimensiunea curentă a tamponului circular
  • actualizați biblioteca astfel încât să nu piardă un slot