päivitetty: 20210321

sulautettujen järjestelmien resurssirajoitteisuuden vuoksi ympyränmuotoisia puskuritietorakenteita löytyy useimmista projekteista.

Ympyräpuskurit (tunnetaan myös nimellä rengaspuskurit) ovat kiinteänkokoisia puskureita, jotka toimivat ikään kuin muisti olisi yhteneväinen & ympyränmuotoinen. Kun muistia syntyy ja kuluu, tietoja ei tarvitse sekoittaa uudelleen – pikemminkin pään ja hännän osoittimia säädetään. Kun tietoja lisätään, pään osoitin etenee. Kun dataa kulutetaan, häntäosoitin etenee. Jos pääset loppuun puskuri, osoittimet yksinkertaisesti kietoutua alkuun.

tarkempi Yhteenveto ympyräpuskurioperaatiosta löytyy Wikipedian artikkelista. Artikkelin loppuosassa oletetaan, että sinulla on käsitys siitä, miten pyöreät Puskurit toimivat.

Sisällysluettelo:

1. Miksi käyttää pyöreää puskuria?
2. C-toteutus
3. kapseloinnin avulla
4. API-suunnittelu
5. määrittämällä, onko Puskuri täysi

Pyöreä Puskurisäiliötyyppi

6. toteutus
7. käyttö
8. muutokset fulllippu
9. C++ – toteutus
   1. luokkamääritys
   2. toteutus

   äyttö

10. päivitykset c++17: ään

kaiken yhteen laittaminen

lisätietoja

miksi käyttää ympyränmuotoista puskuria?

Ympyräpuskureita käytetään usein kiinteän kokoisina jonoina. Kiinteä koko on hyödyllinen sulautetuille järjestelmille, sillä kehittäjät pyrkivät usein käyttämään staattisen tiedon tallennusmenetelmiä dynaamisten allokaatioiden sijaan.

pyöreät puskurit ovat myös käyttökelpoisia rakenteita tilanteissa, joissa tiedon tuottaminen ja kuluttaminen tapahtuu eri tahtiin: tuorein tieto on aina saatavilla. Jos kuluttaja ei pysy tuotannon perässä, vanhentuneet tiedot korvataan tuoreemmilla tiedoilla. Käyttämällä pyöreää puskuria voimme varmistaa, että kulutamme aina tuoreimmat tiedot.

lisäkäyttötapauksissa tutustu Rengaspuskurin perusasioihin osoitteessa Embedded.com.

C-toteutus

aloitamme C-toteutuksella, koska tämä altistaa meidät joillekin suunnitteluhaasteille ja tradeoffeille kehäpuskurikirjastoa luotaessa.

kapselointi

koska olemme luomassa ympyränmuotoista puskurikirjastoa, haluamme varmistaa, että käyttäjät toimivat kirjastorajapintojemme kanssa sen sijaan, että muuttaisivat rakennetta suoraan. Haluamme myös pitää toteutuksen sisällämme kirjastossamme, jotta voimme muuttaa sitä tarpeen mukaan ilman, että loppukäyttäjiltä vaaditaan koodin päivittämistä. Käyttäjän ei tarvitse tietää mitään yksityiskohtia rakenteestamme, vain että se on olemassa.

kirjastomme otsikossa ilmoitamme rakenteen eteenpäin:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

emme halua käyttäjien käyttävän circular_but_t osoitinta suoraan, koska he saattavat saada vaikutelman, että he voivat viitata arvoon. Luomme kahvatyypin, jota he voivat käyttää sen sijaan.

yksinkertaisin lähestymistapa kahvallemme on typedefcbuf_handle_t osoitin ympyräpuskuriin. Tämä estää meitä tarvitsemasta heittää osoitinta toimintomme toteuttamiseen.

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

vaihtoehtoinen lähestymistapa olisi tehdä kahvasta uintptr_t tai void* arvo. Sisällä meidän käyttöliittymä, käsittelemme käännös sopiva osoitintyyppi. Pidämme pyöreän puskurityypin piilossa käyttäjiltä, ja ainoa tapa olla vuorovaikutuksessa datan kanssa on kahvan kautta.

aiomme pitää kiinni yksinkertaisesta kahvan toteutuksesta, jotta esimerkkikoodimme pysyy yksinkertaisena ja suoraviivaisena.

API-suunnittelu

ensin pitäisi miettiä, miten käyttäjät toimivat ympyräpuskurin kanssa:

• heidän täytyy alustaa Pyöreä puskurisäiliö puskurilla ja koko
• heidän täytyy tuhota Pyöreä puskurisäiliö
• heidän täytyy nollata Pyöreä puskurisäiliö
• heidän täytyy pystyä lisäämään tietoa puskuriin
• heidän täytyy saada seuraava arvo puskurista
• heidän täytyy tietää, onko puskuri täynnä vai tyhjä
• heidän täytyy tietää nykyinen alkuaineiden määrä puskurissa
• heidän täytyy tietää puskurin maksimikapasiteetti

käyttämällä tätä listaa voimme koota API: n kirjastollemme. Käyttäjät ovat vuorovaikutuksessa pyöreän puskurikirjaston kanssa käyttäen läpinäkymätöntä kahvatyyppiä, joka luodaan alustuksen aikana.

olen valinnut uint8_t pohjatietotyypiksi tässä toteutuksessa. Voit käyttää mitä tahansa tiettyä tyyppiä, josta pidät – ole vain varovainen käsittelemään taustalla olevaa puskuria ja tavujen määrää asianmukaisesti.

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

määritettäessä, onko Puskuri täynnä

ennen kuin etenemme, meidän tulisi hetki keskustella menetelmästä, jolla määritämme, onko puskuri täynnä vai tyhjä.

sekä ympyräpuskurin ”täysi” että ”tyhjä” tapaus näyttävät samalta: head ja tail osoitin on yhtä suuri. Täyden ja tyhjän erottamiseen on kaksi tapaa:

1. ”jätteen” paikka puskurissa:
   • täysi tila on head + 1 == tail
   • tyhjä tila on head == tail
2. käytä bool lippu ja lisälogiikka valtioiden erottamiseksi::
   • täysi tila on full
   • tyhjä tila on (head == tail) && !full

on syytä harkita myös kierteen turvallisuutta. Käyttämällä yhtä tyhjää solua ”täyden” tapauksen havaitsemiseen voimme tukea yhtä tuottajaa ja yksittäistä kuluttajaa ilman lukkoa (kunhan put ja get eivät muokkaa samoja muuttujia). Jono on kierreturvallinen, koska tuottaja muokkaa vain head – indeksiä, ja kuluttaja muuttaa vain tail – indeksiä. Vaikka jompikumpi indeksi saattaa olla tietyssä kontekstissa hieman vanhentunut, tämä ei vaikuta jonon kierreturvallisuuteen. full lipun käyttäminen luo kuitenkin vaatimuksen molemminpuolisesta poissulkemisesta. Tämä johtuu siitä, että

lippu on sekä tuottajan että kuluttajan yhteinen.

tietenkin päätöksellä on traditionsa. Jos puskurielementti on suuri muisti jalanjälki (kuten puskuri, joka on mitoitettu kameran I-frame), tuhlaa korttipaikka ei ehkä ole kohtuullista järjestelmässäsi. Jos sinulla on useita tuottajia / kuluttajia vuorovaikutuksessa jonon kanssa, tarvitset lukon joka tapauksessa, joten kolikkopelin tuhlaaminen ei ole järkevää. Jos käytössä ei ole molemminpuolista poissulkemista (esim.koska et käytä käyttöjärjestelmää), mutta käytät keskeytyksiä, haluat käyttää ei-full lippuversiota. Järjestelmässäsi käytetty muistimalli voi myös vaikuttaa päätökseesi lähteä ilman lukkoa.

alla olevassa toteutuksessa käytetään bool – lippua. Lipun käyttäminen vaatii lisälogiikkaa get ja put rutiineissa lipun päivittämiseksi. Kerron myös, miten muutokset tehdään yksittäiselle tuottajalle/kuluttajalle, joka ei käytä full – lippua.

Pyöreä puskurisäiliö tyyppi

nyt kun meillä on käsitys tuettavista operaatioista, voimme suunnitella pyöreän puskurisäiliömme.

käytämme säiliörakennetta puskurin tilan hallintaan. Kapseloinnin säilyttämiseksi säiliöiden rakenne on määritelty kirjastomme sisällä .c tiedosto, eikä otsikossa.

meidän on pidettävä kirjaa:

• pohjatietopuskurin
• puskurin enimmäiskoko
• nykyinen ”pään” sijainti (kasvoi, kun elementtejä lisätään)
• nykyinen ”hännän” sijainti (kasvoi, kun elementtejä poistetaan)
• lippu, joka ilmaisee, onko puskuri täynnä vai ei

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

nyt kun kontti on suunniteltu, olemme valmiita toteuttamaan kirjaston toiminnot.

toteutus

yksi tärkeä yksityiskohta on huomata, että jokainen Sovellusliittymämme vaatii alustetun puskurikahvan. Sen sijaan, että roskaamme koodimme ehdollisilla lauseilla, käytämme väitteitä API-vaatimusten täytäntöönpanemiseksi ”Design by Contract” – tyyliin.

Jos rajapintoja käytetään väärin, ohjelma epäonnistuu välittömästi sen sijaan, että käyttäjä joutuisi tarkistamaan ja käsittelemään virhekoodin.

esimerkiksi:

circular_buf_reset(NULL);

tuottaa:

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

toinen tärkeä huomio on, että alla esitetty toteutus ei ole kierreturvallinen. Taustalla olevaan ympyräpuskurikirjastoon ei ole lisätty lukkoja.

alustaa ja nollaa

aloitetaan alusta: alustetaan ympyräpuskuri. API: n asiakkaat tarjoavat taustalla olevan puskurin ja puskurin koon, ja palautamme heille pyöreän puskurikahvan. Syy, miksi haluamme käyttäjiemme tarjoavan puskurin, on se, että tämä mahdollistaa staattisesti kohdennetun puskurin. Jos SOVELLUSLIITTYMÄMME loi puskurin konepellin alle, meidän olisi käytettävä dynaamista muistinjakoa, joka on usein kielletty sulautettujen järjestelmien ohjelmissa.

meidän on tarjottava kirjastossa Pyöreä puskurirakenne-ilmentymä, jotta voimme palauttaa osoittimen käyttäjälle. Olen käyttänytmalloc yksinkertaisuuden vuoksi. Järjestelmät, jotka eivät voi käyttää dynaamista muistia, joutuvat vain muokkaamaan init funktiota käyttääkseen erilaista menetelmää, kuten allokaatiota ennalta varattujen ympyränmuotoisten puskurirakenteiden staattisesta poolista.

toinen lähestymistapa olisi kapseloinnin rikkominen, jolloin käyttäjät voisivat staattisesti julistaa kirjaston ulkopuolella olevia pyöreitä puskurisäiliörakenteita. Tällöin circular_buf_init on päivitettävä strukturoidun osoittimen ottamiseksi. Myös init funktio voisi luoda pinoon konttirakenteen ja palauttaa sen tukkumyyntiin. Koska kapselointi on kuitenkin rikki, käyttäjät voivat muokata rakennetta ilman kirjaston rutiineja. Jos haluat säilyttää kapseloinnin, sinun täytyy työskennellä osoittimilla betonirakenteiden instanssien sijaan.

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

palautamme kahvan kirjaston sisällä olevaan rakennelmaan. Kun olemme luoneet konttimme, meidän on kansoitettava arvot ja kutsuttava reset sille. Ennen kuin palaamme init, varmistamme, että puskurisäiliö on luotu tyhjään tilaan.

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

nollausfunktion tarkoituksena on laittaa puskuri ”tyhjään” tilaan, mikä vaatii päivittämistä headtail ja full:

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

koska meillä on menetelmä luoda pyöreä puskurisäiliö, tarvitsemme vastaavan menetelmän säiliön tuhoamiseen. Tällöin kutsumme free meidän kontista. Emme yritä vapauttaa taustalla olevaa puskuria, koska emme omista sitä.

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

Tilatarkistukset

seuraavaksi toteutamme puskurisäiliön tilaan liittyvät toiminnot.

täysi funktio on helpoin toteuttaa, sillä meillä on valtiota edustava lippu:

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

koska meillä on full lippu, joka erottaa täyden tai tyhjän tilan, yhdistämme lipun tarkistamalla, että head == tail:

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

puskurimme kapasiteetti toimitettiin alustuksen aikana, joten palautamme vain kyseisen arvon käyttäjälle:

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

puskurin elementtien lukumäärän laskeminen oli hankalampi ongelma kuin odotin. Monet ehdotetut kokolaskelmat käyttävät moduloa, mutta törmäsin outoihin kulmatapauksiin testatessani sitä. Valitsin yksinkertaistetun laskelman, jossa käytetään ehdollisia lausekkeita.

Jos puskuri on täynnä, tiedämme, että kapasiteettimme on maksimissaan. Jos head on suurempi-kuin-tai-yhtäsuuri-kuin tail, me yksinkertaisesti vähennämme kaksi arvoa saadaksemme kokoamme. Jos tail on suurempi kuin head, on erotus tasattava max oikean koon saamiseksi.

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

tietojen lisääminen ja poistaminen

kirjanpitotoimintojen ollessa pois tieltä on aika kaivaa lihat: tietojen lisääminen ja poistaminen jonosta.

tietojen lisääminen ja poistaminen ympyräpuskurista edellyttää head ja tail osoittimien käsittelyä. Kun tietoja lisätään puskuriin, lisätään uusi arvo nykyiseen head sijainti, niin edetään head. Kun poistamme tiedot puskurista, noudamme nykyisen tail osoittimen arvon ja etenemme sitten tail.

tietojen lisääminen puskuriin vaatii kuitenkin hieman enemmän miettimistä. Jos puskuri on full, on edettävä tail osoitin sekä head. On myös tarkistettava, laukaiseeko arvon lisääminen full ehdon.

aiomme toteuttaa kaksi versiota put funktiosta, joten puretaan osoittimen etenemislogiikkamme avustajafunktioksi. Jos puskurimme on jo täynnä, etenemme tail. Etenemme aina head yhdellä. Kun osoitin on edennyt, kansoitetaan full lippu tarkistamalla, onko head == tail.

huomaa modulo-operaattorin käyttö (%) alla. Modulo aiheuttaa head ja tail arvojen palautumisen arvoon 0, kun maksimikoko saavutetaan. Näin varmistetaan, että head ja tail ovat aina voimassa olevia pohjatietopuskurin indeksejä.

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

kuten Miro Samek avuliaasti huomautti, kyseessä on kallis laskennallinen operaatio. Sen sijaan ehdollisella logiikalla voidaan vähentää ohjeiden kokonaismäärää. Miron suositus on:

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

nyt, advance_pointer näyttää tältä:

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

voimme tehdä samanlaisen auttajafunktion, jota kutsutaan poistettaessa arvoa puskurista. Kun poistetaan arvo, full lippu asetetaan false, ja pyrstön osoitin on kehittynyt.

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

luodaan kaksi versiota put funktiosta. Ensimmäinen versio lisää puskuriin arvon ja ennakoi osoitinta. Jos puskuri on täynnä, vanhin arvo korvataan. Tämä on standardikäyttötapaus ympyräpuskurille

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

put funktio palauttaa virheen, jos puskuri on täynnä. Tämä on tarkoitettu esittelytarkoituksiin, mutta emme käytä tätä versiota järjestelmissämme.

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

poistaaksemme tiedot puskurista, käytämme arvoa tail ja päivitämme sitten tail osoitin. Jos puskuri on tyhjä, emme palauta arvoa tai muuta osoitinta. Sen sijaan palautamme virheen käyttäjälle.

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

, joka täydentää pyöreän puskurikirjastomme toteutuksen.

käyttö

kirjastoa käytettäessä asiakas vastaa taustalla olevan tietopuskurin luomisesta circular_buf_init, ja cbuf_handle_t palautetaan:

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

tätä kahvaa käytetään vuorovaikutuksessa kaikkien jäljellä olevien kirjastotoimintojen kanssa:

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

älä unohda vapauttaa sekä taustalla olevaa tietopuskuria että säiliötä, kun olet valmis:

free(buffer);circular_buf_free(cbuf);

ympyräpuskurikirjastoa käyttävä testiohjelma löytyy sulautettujen resurssien arkistosta.

muutokset kokonaisen lipun poistamiseksi

Jos haluat jättää full lipun, tarkista sen sijaan, että head on yksi paikka hännän takana, jotta voit määrittää, onko puskuri täynnä:

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

Jos haluamme välttää Modulo-operaation, Voimme käyttää ehdollista logiikkaa.:

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

tyhjä tapaus on sitten se, että head ja tail ovat samat:

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

saadessamme tietoja puskurista etenemme häntää osoitin, kääritään tarvittaessa ympärille:

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

kun lisätään tietoja puskuriin, tallennamme tiedot ja etenemme pään osoitin, kääritään tarvittaessa ympäri:

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

muut viittaukset full voidaan poistaa.

C++

c++ soveltuu puhtaampaan ympyränmuotoiseen puskuritoteutukseen kuin C.

Luokkamääritys

aloitamme määrittelemällä C++ – luokkamme. Haluamme C++ – toteutuksemme tukevan mitä tahansa dataa, joten aiomme tehdä siitä templated-luokan.

Sovellusliittymämme tulevat olemaan samanlaisia kuin C-toteutus. Meidän luokka tarjoaa rajapinnat:

• puskurin nollaaminen tyhjäksi
• lisäämällä tietoa
• poistamalla tietoa
• tarkistamalla puskurin elementtien tämänhetkisen määrän
• tarkistamalla puskurin kokonaiskapasiteetin

käytämme myös C++ – älyosoittimia varmistaaksemme, ettemme jätä tietoja ympärille puskurimme tuhouduttua. Tämä tarkoittaa, että voimme hallita puskuria käyttäjälle.

Toinen C++: n etu on triviaalisuus tehdä tästä luokasta säiettä turvallinen: voimme luottaa std::mutex-tyyppiin (olettaen, että tämä on määritelty alustallesi).

tässä on luokkamäärityksemme:

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

C++ – ympyräpuskurimme jäljittelee paljon C-toteutuksen logiikkaa, mutta johtaa paljon puhtaampaan ja uudelleenkäytettävämpään suunnitteluun. Myös C++ – puskuri hyödyntää std::mutex langatonta toteutusta.

Huom: samat logiikkamuutokset voidaan tehdä C++-toteutuksessa tukemaan säieturvallisuutta yhden tuottajan ja kuluttajan kanssa ”hukkaamalla” korttipaikka. Katso tarkemmat tiedot C-toteutuksen muutoksista.

alustus

rakentaessamme luokkaamme kohdistamme tiedot taustalla olevalle puskurillemme ja asetamme puskurin koon. Tämä poistaa C-toteutuksessa tarvittavat yleiskustannukset.

toisin kuin C-toteutus, C++ – konstruktori ei kutsu reset. Koska määrittelemme jäsenmuuttujiemme lähtöarvot, kehäpuskurimme alkaa oikeassa tilassa.

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

nollauskäyttäytymisemme laittaa puskurin takaisin tyhjään tilaan (head == tail && !full_).

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

Tilanneseuranta

empty ja full tapaukset ovat samat kuin C-esimerkki:

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

c++: n ympyräpuskuritoteutuksessa size ja capacity ilmoittavat jonossa olevien alkioiden lukumäärän koon sijaan tavuina. Näin voimme olla agnostisia tyypin taustalla oleville yksityiskohdille.

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

tietojen lisääminen

put logiikka vastaa C-toteutusta. Tämä toteutus käyttää ”korvaa vanhin arvo” käyttäytymismalli.

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

Huom: yksinkertaisuuden vuoksi olen jättänyt pois modulo-operaatioita välttävän vaihtoehdon. Se logiikka löytyy C-osiosta.

tietojen hakeminen

get logiikka vastaa C-toteutusta. Toisin kuin C-toteutuksessa, tyhjä arvo palautetaan, jos puskuri on tyhjä.

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

Huom.: return T() palauttaa oletusarvoisen konstruoidun arvon fo ra annettua tyyppiä. Tuotettu todellinen arvo riippuu tyypistä tai rakentajasta. Yksinkertaisuuden vuoksi olen myös jättänyt pois vaihtoehdon, jolla vältetään modulo-operaatiot. Se logiikka löytyy C-osiosta.

käyttö

c++: n ympyräpuskuri on paljon yksinkertaisempi käyttää kuin C-toteutus.

asentaaksemme pyöreän puskurin, julistamme vain objektin ja määritämme puskurillemme templated-tyypin. Tässä esimerkki käyttäen puskuria 10 uint32_t merkinnät:

circular_buffer<uint32_t> circle(10);

tietojen lisääminen on helppoa:

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

ja tietojen saaminen on yhtä helppoa:

x = circle.get()

muista, että koska kyseessä on temploitu luokka, voit luoda minkä tahansa tyyppisen pyöreän puskurin.

C++17: n päivitykset

c++17: ssä meillä on käytössämme std::optional, jonka avulla voimme esittää arvon, joka voi olla tai olla olematta. Meidän get funktio palauttaisi std::optional<T>. Myös std::nullopt oletusarvoisen T, jos jono on tyhjä.

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

Huom: yksinkertaisuuden vuoksi olen jättänyt pois modulo-operaatioita välttävän vaihtoehdon. Se logiikka löytyy C-osiosta.

kutsukoodista saattoi tarkistaa kelvollisen arvon käyttämällä Boolen operaattoria tai has_value jäsenfunktiota. Jos voimassa oleva arvo on olemassa, sitä voi käyttää -> tai * operaattorit, ur käyttäen value() jäsenfunktiota.

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

Putting it All Together

Example implementations can found in the embedded-resources Github repository.

• C: n ympyräpuskuritestiohjelma
• C: n ympyräpuskurikirjasto

C++: n ympyräpuskuriesimerkki

Jos haluat laajentaa tätä kirjastoa, hyödyllinen harjoitus on lisätä ylimääräisiä sovellusliittymiä, jotta käyttäjät voivat lisätä / poistaa useita elementtejä yhdellä toiminnolla. Voit myös tehdä C-toteutuksesta kierreturvallisen.

kierteiden turvallisuus Lookahead-menetelmällä

yksi lähestymistapa kierteiden turvallisuuteen ilman mutexia on ”lookahead” – menetelmä. Tämä menetelmä tukee yhden tuottajan lankaa ja yhden kuluttajan lankaa; useat tuottajat tai kuluttajat vaativat lukon.

sen sijaan, että käyttäisimme Boolen lippua erotellaksemme täydet ja tyhjät kotelot, jätämme aina yhden solun tyhjäksi. Käyttämällä yhtä tyhjää solua ”täyden” tapauksen havaitsemiseen voimme tukea yhtä tuottajaa ja yksittäistä kuluttajaa ilman lukkoa (kunhan put ja get eivät muokkaa samoja muuttujia).

voit olla huolissasi pelipaikan tuhlaamisesta, mutta tämä tradeoff on usein paljon halvempi kuin käyttöjärjestelmän lukon alkukantaisen käytön hinta.

lisätietoja

• C++ Älyosoittimet
• dit Your C-Stye Pointers for Smart Pointers

tässä on muita ympyräpuskuritoteutuksia:

QuantumLeaps/lock-free-ring-buffer

lisätietoja ympyräpuskureista:

• Embedded.com: Rengaspuskurin perusteet
• Wikipedia: Ympyräpuskuri
• Ferrosysteemit: lukitsematon Rengaspuskuri
• Boost Ympyräpuskuri
• C++: Pyöreän puskurin suorituskyky vektori, Deque ja lista
• lukitsematon yhden tuottajan ja yhden kuluttajan Ympyräjono

on ehdotus pyöreän puskurityypin lisäämisestä C++: n standardikirjastoon:

• p0059: Ehdotus Rengasspanin lisäämisestä Standardikirjastoon
  • Rengasspan
  • Rengasspan Lite

muutoslokiin

• 20210321
  • Kiinteä virhe max_size_jossacbuf->maxpitäisi on käytetty
  • Lisätty selventävää tekstiä siitä, miksi käyttäjä syöttää puskurin sisään
• 20210301
  • mirolta osoitettu palaute modulo-operaatioiden välttämisestä
• 20210213
  • Lisätty lisälinkkejä
  • lisäsi vielä keskustelua Full Flag vs. ”hukkaan” slot
  • Näytä muutokset säieturvallisuuteen yhdellä tuottajalla/kuluttajalla
  • Lisää huomautuksia std::optional käytä C++17: n kanssa
• 20191016
  • päivitetty Muutoslokiosion muotoilu johdonmukaisuudesta koko sivustolla
  • Alennetut otsikot johdonmukaisuudesta koko sivustolla
  • kiinteä rikkinäinen Sisällysluettelo linkit
  • poistettu Muutosloki sisällysluettelosta
• 20190627
  • Lisätty linkki ferrousjärjestelmien lukitsemattomaan rengaspuskuriartikkeliin.
• 20190604
  • korjasi kirjoitusvirheen (kiitos Chris Svec!) ja muutti joitakin läpinäkymättömään tyyppiin liittyviä sanamuotoja.
• 20181219
  • Lisätty huomautus siitä, että tyhjän luukun käyttävän yksittäisen tuottajan ja yksittäisen kuluttajan on vältettävä samanaikaisia ongelmia.
• 20180804
  • artikkeli uudistettiin ja kirjoitettiin uudelleen.Kiitos kaikille, jotka antoivat palautetta matkan varrella. Esimerkit on päivitetty:
  • Poista puolustava ohjelmointi
  • käytä väitteitä
  • luo itsenäinen kirjasto käyttäen läpinäkymätöntä rakennetta
  • Laajenna sovellusliittymiä, mukaan lukien laskelma nykyisestä ympyränmuotoisesta puskurikoosta
  • Päivitä kirjasto, jotta se ei haaskaisi aukkoa