Frissítve: 20210321

a beágyazott rendszerek erőforrás-korlátozott jellege miatt a körkörös puffer adatstruktúrák megtalálhatók a legtöbb projektben.

a kör alakú pufferek (más néven gyűrűs pufferek) rögzített méretű pufferek, amelyek úgy működnek, mintha a memória összefüggő lenne & kör alakú jellegű. Mivel a memória generálódik és elfogy, az adatokat nem kell átrendezni – inkább a fej/farok mutatókat kell beállítani. Az adatok hozzáadásakor a fejmutató előre halad. Amikor az adatok elfogynak, a farok mutató előre halad. Ha eléri a puffer végét, a mutatók egyszerűen az elejére tekerednek.

a körkörös puffer működésének részletesebb összefoglalása a Wikipedia cikkében található. A cikk többi része feltételezi, hogy megértette, hogyan működnek a körkörös pufferek.

Tartalomjegyzék:

1. miért használjon körkörös puffert?
2. C implementáció
   1. kapszulázás használata
   2. API tervezés
   3. annak meghatározása, hogy a puffer megtelt-e
   4. körkörös puffer tároló típusa
   5. implementáció
   6. használat
   7. módosítások afull zászló
3. C++ implementáció
   1. class definition
   2. implementation
   3. használat
   4. frissítések a C++17
4. mindent összerakva
5. további olvasmányok

miért használjon körkörös puffert?

a kör alakú puffereket gyakran rögzített méretű sorokként használják. A rögzített méret előnyös a beágyazott rendszerek számára, mivel a fejlesztők gyakran statikus adattárolási módszereket próbálnak használni a dinamikus allokációk helyett.

a kör alakú pufferek szintén hasznos struktúrák olyan helyzetekben, amikor az adattermelés és-fogyasztás eltérő ütemben történik: a legfrissebb adatok mindig rendelkezésre állnak. Ha a fogyasztó nem tud lépést tartani a termeléssel, az elavult adatokat újabb adatokkal írják felül. Körkörös puffer használatával biztosíthatjuk, hogy mindig a legfrissebb adatokat fogyasztjuk.

további használati esetekért nézze meg a gyűrűs puffer alapjait Embedded.com.

C implementáció

egy C implementációval kezdjük, mivel ez kitesz minket néhány tervezési kihívásnak és kompromisszumnak egy kör alakú pufferkönyvtár létrehozásakor.

Encapsulation használata

mivel körkörös pufferkönyvtárat hozunk létre, szeretnénk megbizonyosodni arról, hogy a felhasználók a könyvtár API-jainkkal dolgoznak-e a szerkezet közvetlen módosítása helyett. Azt is szeretnénk, hogy a megvalósítás a könyvtárunkban maradjon, így szükség szerint megváltoztathatjuk, anélkül, hogy a végfelhasználóknak frissíteniük kellene a kódjukat. A felhasználónak nem kell tudnia semmilyen részletet a szerkezetünkről, csak azt, hogy létezik.

a könyvtár fejlécében továbbítjuk a szerkezet deklarálását:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

nem akarjuk, hogy a felhasználók közvetlenül a circular_but_t mutatóval dolgozzanak, mivel az a benyomásuk lehet, hogy törölhetik az értéket. Létrehozunk egy fogantyú típust, amelyet helyette használhatnak.

a fogantyú legegyszerűbb megközelítése atypedef acbuf_handle_t a kör alakú puffer mutatójaként. Ez megakadályozza, hogy a mutatót a funkció megvalósításán belül kell leadnunk.

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

alternatív megközelítés az lenne, ha a fogantyút uintptr_tvagy void* értékre állítanánk. Az interfészünkön belül a fordítást a megfelelő mutatótípusra kezelnénk. A körkörös puffertípust elrejtjük a felhasználók elől, és az adatokkal való interakció egyetlen módja a fogantyú.

ragaszkodunk az egyszerű fogantyú implementációhoz, hogy a példakódunk egyszerű és egyértelmű legyen.

API tervezés

először is meg kell gondolni, hogy a felhasználók kölcsönhatásba lépnek egy körkörös puffer:

• meg kell inicializálni a kör alakú puffer konténer egy puffer és mérete
• meg kell semmisíteni egy kör alakú puffer konténer
• vissza kell állítani a kör alakú puffer konténer
• képesnek kell lenniük arra, hogy adjunk adatokat a puffer
• képesnek kell lenniük arra, hogy a következő értéket a puffer
• tudniuk kell, hogy a puffer tele van-e vagy üres
• tudniuk kell, hogy az aktuális elemek száma a pufferben
• tudniuk kell a puffer maximális kapacitását

ezzel a listával összeállíthatunk egy API-t a könyvtárunkhoz. A felhasználók kölcsönhatásba lépnek a körkörös pufferkönyvtárral az átlátszatlan fogantyú típusunk segítségével, amelyet az inicializálás során hoznak létre.

a uint8_t – et választottam a megvalósítás alapjául szolgáló adattípusként. Bármilyen típust használhat, ami tetszik – csak vigyázzon, hogy megfelelően kezelje az alapul szolgáló puffert és a bájtok számát.

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

annak meghatározása, hogy a puffer megtelt-e

mielőtt folytatnánk, szánjunk egy percet arra, hogy megvitassuk azt a módszert, amelyet annak meghatározására használunk, hogy a puffer tele vagy üres-e.

mind a kör alakú puffer” teljes”, mind”üres”esetei azonosak: head és tail mutató egyenlő. Két megközelítés különböztethető meg a teljes és az üres között:

1. “hulladék” egy rés a pufferben:
   • a teljes állapot head + 1 == tail
   • az üres állapot head == tail
2. használjon bool zászló és további logika az állapotok megkülönböztetésére::
   • a teljes állapot full
   • az üres állapot (head == tail) && !full

a menetbiztonságot is figyelembe kell vennünk. Ha egyetlen üres cellát használunk a “teljes” eset észlelésére, támogathatunk egyetlen gyártót és egyetlen fogyasztót zárolás nélkül (mindaddig, amíg put és get nem módosítjuk ugyanazokat a változókat). A sor szálbiztonságos, mert a gyártó csak a head indexet, a fogyasztó pedig csak a tail indexet módosítja. Bár bármelyik index kissé elavult lehet egy adott kontextusban, ez nem befolyásolja a sor szálbiztonságát. A full jelző használata azonban megköveteli a kölcsönös kizárást. Ez azért van, mert a full jelzőt mind a gyártó, mind a fogyasztó megosztja.

természetesen a döntésnek vannak kompromisszumai. Ha a pufferelem nagy memóriaterülettel rendelkezik (például egy kamera i-frame méretű pufferrel), előfordulhat, hogy egy nyílás pazarlása nem ésszerű a rendszeren. Ha több gyártó/fogyasztó lép kapcsolatba egy sorral, akkor mindenképpen zárra lesz szüksége, így a rés pazarlásának nincs értelme. Ha nem áll rendelkezésre kölcsönös kizárás (például azért, mert nem operációs rendszert használ), de megszakításokat használ, akkor a nemfull zászló verziót kell használnia. A rendszeren használt memóriamodell szintén hatással lehet arra a döntésre, hogy zár nélkül megy.

az alábbi megvalósítás a bool jelzőt használja. A zászló használata további logikát igényel a get és put rutinokban a zászló frissítéséhez. Azt is leírom, hogyan lehet a módosításokat egyetlen gyártó/fogyasztó számára elvégezni, amely nem használja a full zászlót.

körkörös puffer konténer típusa

most, hogy megértettük a támogatandó műveleteket, megtervezhetjük körkörös puffertartályunkat.

a tárolószerkezetet használjuk a puffer állapotának kezelésére. A kapszulázás megőrzése érdekében a tárolószerkezet a könyvtárunk .c fájljában van meghatározva, nem pedig a fejlécben.

nyomon kell követnünk a következőket:

• az alapul szolgáló adatpuffer
• a puffer maximális mérete
• az aktuális “fej” pozíció (az elemek hozzáadásakor növekszik)
• az aktuális “farok” (az elemek eltávolításakor növekszik)
• egy zászló, amely jelzi, hogy a puffer megtelt-e vagy sem

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

most, hogy elkészült a tárolónk, készen állunk a könyvtári funkciók megvalósítására.

implementáció

fontos megjegyezni, hogy minden API-nak inicializált pufferkezelőre van szüksége. Ahelyett, hogy a kódunkat feltételes utasításokkal alomoznánk, az állításokat felhasználjuk az API-követelmények érvényesítésére a “Szerződés szerinti tervezés” stílusban.

Ha az interfészeket nem megfelelően használják, a program azonnal meghibásodik, ahelyett, hogy a felhasználónak ellenőriznie és kezelnie kellene a hibakódot.

például:

circular_buf_reset(NULL);

termel:

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

egy másik fontos megjegyzés, hogy az alábbiakban bemutatott megvalósítás nem biztonságos. Az alapul szolgáló körkörös pufferkönyvtárhoz nem adtak zárakat.

inicializálás és visszaállítás

kezdjük az elején: kör alakú puffer inicializálása. API-nk kliensei biztosítják az alapul szolgáló puffert és pufferméretet, és egy kör alakú pufferfogantyút adunk vissza nekik. Az ok, amiért azt akarjuk, hogy felhasználóink biztosítsák a puffert, az az, hogy ez lehetővé teszi a statikusan kiosztott puffert. Ha API – nk létrehozta a puffert a motorháztető alatt, akkor ki kell használnunk a dinamikus memória-allokációt, amelyet a beágyazott rendszerek programjaiban gyakran nem engedélyeznek.

kör alakú pufferstruktúra-példányt kell biztosítanunk a könyvtáron belül, hogy visszaadhassunk egy mutatót a felhasználónak. Használtam malloc az egyszerűség kedvéért. A dinamikus memóriát nem használó rendszereknek egyszerűen módosítaniuk kell a init függvényt, hogy más módszert használjanak, például az előre kiosztott körkörös pufferszerkezetek statikus készletéből történő allokációt.

egy másik megközelítés a kapszulázás megszakítása lenne, lehetővé téve a felhasználók számára, hogy statikusan deklarálják a kör alakú puffer konténer struktúrákat a könyvtáron kívül. Ebben az esetben acircular_buf_init frissíteni kell a struct mutató felvételéhez. Mi is volna a init függvény hozzon létre egy konténer struktúrát a verem, és vissza nagykereskedelemben. Mivel azonban a kapszulázás megszakadt, a felhasználók a könyvtár rutinok használata nélkül módosíthatják a struktúrát. Ha meg akarja őrizni a kapszulázást, akkor konkrét szerkezeti példányok helyett mutatókkal kell dolgoznia.

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

visszaadunk egy fogantyút a könyvtár belsejében kiosztott struktúrához. Miután létrehoztuk a konténerünket, fel kell töltenünk az értékeket, és hívnunk kell reset rajta. Mielőtt visszatérnénk a init – ből, biztosítjuk, hogy a puffertároló üres állapotban jött létre.

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

a visszaállítási funkció célja, hogy a puffert “üres” állapotba helyezze, ami frissítést igényel headtail, és full:

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

mivel van módszerünk egy kör alakú puffertartály létrehozására, egyenértékű módszerre van szükségünk a tartály megsemmisítésére. Ebben az esetben hívjukfree a tárolónkon. Nem kíséreljük meg felszabadítani az alapul szolgáló puffert, mivel nem a miénk.

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

Állapotellenőrzések

ezután végrehajtjuk a puffertároló állapotával kapcsolatos funkciókat.

a teljes funkció a legkönnyebben megvalósítható, mivel van egy zászló, amely az államot képviseli:

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

mivel megvan a full zászló a teljes vagy az üres állapot megkülönböztetéséhez, kombináljuk a zászlót egy ellenőrzéssel, hogy head == tail:

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

a kapacitás a pufferünket az inicializálás során szállítottuk, ezért csak ezt az értéket adjuk vissza a felhasználónak:

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

a pufferben lévő elemek számának kiszámítása bonyolultabb probléma volt, mint vártam. Sok javasolt méretszámítás modulo-t használ, de furcsa sarokesetekbe ütköztem, amikor ezt teszteltem. Egyszerűsített számítást választottam feltételes állítások felhasználásával.

Ha a puffer tele van, tudjuk, hogy a kapacitás a maximális. Ha head nagyobb, mint-vagy-egyenlő-a tail, egyszerűen kivonjuk a két értéket, hogy megkapjuk a méretünket. Ha a tailnagyobb, mint a head, akkor a különbséget a max értékkel kell ellensúlyozni a megfelelő méret eléréséhez.

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

Adatok hozzáadása és eltávolítása

mivel a könyvelési funkciók nincsenek útban, itt az ideje, hogy belemerüljön a húsba: adatok hozzáadása és eltávolítása a sorból.

adatok hozzáadása és eltávolítása körkörös pufferből a headés tail mutatók manipulálását igényli. Amikor adatokat adunk a pufferhez, az új értéket az aktuális head helyre helyezzük, majd előre haladunk head. Amikor adatokat távolítunk el a pufferből, lekérjük az aktuális tail mutató értékét, majd előre tail.

adatok hozzáadása a pufferhez azonban egy kicsit több gondolkodást igényel. Ha a puffer full, elő kell mozdítanunk a tailmutatót, valamint a head értéket. Azt is ellenőriznünk kell, hogy egy érték beillesztése kiváltja-e a full feltételt.

a put függvény két változatát fogjuk megvalósítani, tehát bontsuk ki a mutató előrehaladási logikáját egy segítő funkcióba. Ha a pufferünk már megtelt, előre lépünk tail. Mindig előre head egy. Miután a mutató előrehaladt, feltöltjük a full jelzőt annak ellenőrzésével, hogy head == tail.

vegye figyelembe az alábbi modulo operátor használatát (%). A Modulo hatására ahead éstail értékek visszaállnak 0-ra a maximális méret elérésekor. Ez biztosítja, hogy a head és tail mindig az alapul szolgáló adatpuffer érvényes indexei legyenek.

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

mint Miro Samek segítőkészen rámutatott, ez egy drága számítási művelet. Ehelyett feltételes logikát használhatunk az utasítások teljes számának csökkentésére. Miro ajánlott megközelítése:

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

most, advance_pointer így fog kinézni:

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

készíthetünk egy hasonló segítő funkciót, amelyet akkor hívunk meg, amikor egy értéket eltávolítunk a pufferből. Amikor eltávolítunk egy értéket ,afull jelzőfalse értékre van állítva, és a tail mutató haladó.

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

a put függvény két változatát hozzuk létre. Az első verzió beszúr egy értéket a pufferbe, és előreviszi a mutatót. Ha a puffer megtelt, a legrégebbi érték felülíródik. Ez a szokásos felhasználási eset egy kör alakú pufferhez

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

a put függvény második verziója hibát ad vissza, ha a puffer megtelt. Ez demonstrációs célokra szolgál, de ezt a változatot nem használjuk rendszereinkben.

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

az adatok eltávolításához a pufferből a tail értékhez férünk hozzá, majd frissítjük a tail mutatót. Ha a puffer üres, nem adunk vissza értéket vagy módosítjuk a mutatót. Ehelyett hibát küldünk vissza a felhasználónak.

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

Ez befejezi a körkörös pufferkönyvtárunk megvalósítását.

használat

a könyvtár használatakor az ügyfél felelős az alapul szolgáló adatpuffer létrehozásáért a circular_buf_init, és a cbuf_handle_t visszatér:

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

Ez a fogantyú az összes fennmaradó könyvtárfunkcióval való interakcióra szolgál:

p>

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

ne felejtse el felszabadítani mind az alapul szolgáló adatpuffert, mind a tárolót, ha végzett:

free(buffer);circular_buf_free(cbuf);

a körkörös pufferkönyvtárat használó tesztprogram megtalálható az embedded-resources repository-ban.

A teljes zászló eltávolításának módosításai

Ha a full zászlót el akarja dobni, akkor ehelyett ellenőrizze, hogy a head egy pozíció van-e a farok mögött annak megállapításához, hogy a puffer tele van-e:

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

most, ha el akarjuk kerülni a Modulo műveletet, használhatunk feltételes logikát:

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

az üres eset az, hogy a head és tail ugyanazok:

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

amikor adatokat kapunk a pufferből, akkor a pointer, körbetekerve, ha szükséges:

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

amikor adatokat adunk a pufferhez, tároljuk az adatokat és továbbítjuk a fejmutatót, ha szükséges:

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

a full egyéb hivatkozások a full ki lehet küszöbölni.

C++

C++ alkalmas arra, hogy egy tisztább körkörös puffer végrehajtása, mint a C.

osztály meghatározása

kezdjük azzal, hogy meghatározzuk a C++ osztály. Azt akarjuk, hogy a C++ implementáció bármilyen típusú adatot támogasson, ezért sablonos osztályt fogunk készíteni.

API-k hasonlóak lesznek a C implementációhoz. Osztályunk interfészeket biztosít a:

• a puffer visszaállítása üresre
• Adatok hozzáadása
• Adatok eltávolítása
• teljes/üres állapot ellenőrzése
• a pufferben lévő elemek aktuális számának ellenőrzése
• a puffer teljes kapacitásának ellenőrzése

A C++ intelligens mutatókat is felhasználjuk annak biztosítására, hogy ne hagyjunk semmilyen adatot a puffer megsemmisülése után. Ez azt jelenti, hogy kezelhetjük a puffert a felhasználó számára.

A C++ másik előnye, hogy triviálissá teszi ezt az osztályt szálbiztonságossá: támaszkodhatunk a std::mutex típusra (feltételezve, hogy ez a platformra van meghatározva).

itt van az osztály definíciónk:

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++ implementáció

A C++ körkörös pufferünk a C implementáció logikájának nagy részét utánozza, de sokkal tisztább és újrafelhasználhatóbb kialakítást eredményez. Ezenkívül a C++ puffer a std::mutex programot használja a szálbiztonságos megvalósítás biztosításához.

Megjegyzés: ugyanezek a logikai változások végezhetők el a C++ implementációban, hogy támogassák a szálbiztonságot egyetlen gyártóval és fogyasztóval egy rés “pazarlásával”. További információkért lásd a C megvalósítás kiigazításait.

inicializálás

osztályunk felépítésekor kiosztjuk az adatokat a mögöttes pufferhez, és beállítjuk a puffer méretét. Ez eltávolítja a C megvalósításhoz szükséges költségeket.

A C implementációval ellentétben a C++ konstruktor nem hívja reset. Mivel a tagváltozóink kezdeti értékeit adjuk meg, a körkörös pufferünk a megfelelő állapotban indul.

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

a visszaállítási viselkedésünk visszaállítja a puffert egy üres állapotba (head == tail && !full_).

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

Állapotkövetés

a empty és full esetek logikája megegyezik a C példával:

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

A C++ körkörös puffer implementációban size és capacity a sorban lévő elemek számát jelenti, nem pedig a bájtban megadott méretet. Ez lehetővé teszi számunkra, hogy agnosztikusak legyünk a típus mögöttes részleteivel szemben.

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

Adatok hozzáadása

a put logikája megegyezik a C implementációval. Ez a megvalósítás a “legrégebbi érték felülírása” viselkedési mintát használja.

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

Megjegyzés: Az egyszerűség kedvéért kihagytam azt a lehetőséget, amely elkerüli a modulo műveleteket. Ezt a logikát a C Részben találhatja meg.

Adatok lekérése

a get mögött álló logika megfelel a C implementációnak. A C implementációval ellentétben üres értéket ad vissza, ha a puffer üres.

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

Megjegyzés: return T() egy adott típushoz tartozó alapértelmezett konstruált értéket ad vissza. Az előállított tényleges érték a típustól vagy a kivitelezőtől függ. Az egyszerűség kedvéért kihagytam azt a lehetőséget is, amely elkerüli a modulo műveleteket. Ezt a logikát a C Részben találhatja meg.

használat

A C++ körkörös puffer használata sokkal egyszerűbb, mint a C implementáció.

egy kör alakú puffer példányosításához egyszerűen deklarálunk egy objektumot, és megadjuk a pufferünk sablontípusát. Íme egy példa a 10 uint32_t bejegyzések pufferelésére:

circular_buffer<uint32_t> circle(10);

az adatok hozzáadása egyszerű:

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

és az adatok megszerzése ugyanolyan egyszerű:

x = circle.get()

ne feledje, hogy mivel ez egy sablonos osztály, létrehozhat egy kör alakú puffert bármilyen típusú, amire szüksége van.

frissítések A C++17-hez

A C++17-ben hozzáférhetünk a std::optional – hez, amely lehetővé teszi számunkra, hogy olyan értéket képviseljünk, amely jelen lehet vagy nem. A get függvényünk std::optional<T>értéket ad vissza. Azt is vissza std::nullopt helyett egy alapértelmezett felépített T ha a sor üres.

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

Megjegyzés: Az egyszerűség kedvéért kihagytam azt a lehetőséget, amely elkerüli a modulo műveleteket. Ezt a logikát a C Részben találhatja meg.

a hívókódban ellenőrizhet egy érvényes értéket a logikai operátorral vagy a has_value tagfunkcióval. Ha van érvényes érték, akkor a -> vagy * operátorok segítségével érhető el, ur a value() tagfüggvény használatával.

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

mindent összerakva

példa implementációk találhatók a embedded-resources Github adattár.

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

ha bővíteni szeretné ezt a könyvtárat, hasznos feladat további API-k hozzáadása, amelyek lehetővé teszik a felhasználók számára több elem hozzáadását/eltávolítását egyetlen művelettel. A C megvalósítási szálat biztonságossá is teheti.

Szálbiztonság a Lookahead módszerrel

a Mutex nélküli szálbiztonság egyik megközelítése a “lookahead” módszer. Ez a módszer egyetlen termelői szálat és egyetlen fogyasztói szálat támogat; több gyártó vagy fogyasztó zárolást igényel.

ahelyett, hogy a logikai jelzőt használnánk a teljes és az üres esetek megkülönböztetésére, mindig egy cellát hagyunk üresen. Ha egyetlen üres cellát használunk a “teljes” eset észlelésére, támogathatunk egyetlen gyártót és egyetlen fogyasztót zárolás nélkül (mindaddig, amíg put és get nem módosítjuk ugyanazokat a változókat).

lehet, hogy aggódik egy rés pazarlása miatt, de ez a kompromisszum gyakran sokkal olcsóbb, mint az operációs rendszer használatának költsége zár primitív.

további olvasmányok

• C++ intelligens mutatók
• Ditch a C-Stye mutatók intelligens mutatók

itt vannak más körkörös puffer implementációk:

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

További információ a körkörös pufferekről:

• Embedded.com: Ring buffer alapjai
• Wikipedia: körkörös puffer
• Vasrendszerek: zár szabad gyűrű puffer
• Boost körkörös puffer
• C++: Körkörös puffer vs Vektor, Deque és List teljesítménye
• Lock-Free Single-Producer-Single Consumer Circular Queue

van egy javaslat körkörös puffertípus hozzáadására a C++ standard könyvtárhoz:

• P0059: Javaslat a gyűrűs tartomány hozzáadására a szabványos könyvtárhoz
  • gyűrűs tartomány
  • gyűrűs tartomány Lite

Változási napló

• 20210321
  • javítva a hiba a max_size_ ahol cbuf->max
  • hozzáadott tisztázó szöveg arról, hogy miért adja át a puffert a felhasználó
• 20210301
  • címzett visszajelzés Miro-tól a modulo műveletek elkerülésével kapcsolatban
• 20210213
  • hozzáadott további linkek
  • hozzáadott további vita a teljes zászló vs közötti kompromisszumról egy “elpazarolt” slot
  • mutasson módosításokat szál biztonsági egyetlen gyártó/fogyasztó
  • Add megjegyzések std::optional használja a C++17
• 20191016
  • frissített Változásnapló szakasz formázás következetesség az egész oldalon
  • lefokozott fejlécek következetesség az egész oldalon
  • Fix törött Tartalomjegyzék linkek
  • eltávolította a változási naplót a tartalomjegyzékből
• 20190627
  • hozzáadott linket a vasrendszerek zár nélküli gyűrűs puffer cikkéhez.
• 20190604
  • Javítva egy elírás (köszönöm Chris Svec!) és megváltoztatott néhány megfogalmazást az átlátszatlan típushoz kapcsolódóan.
• 20181219
  • hozzáadott megjegyzés a párhuzamos problémák elkerüléséről egyetlen termelővel és egyetlen fogyasztóval egy üres hely használatával.
• 20180804
  • a cikket átalakították és átírták.Köszönet mindenkinek, aki visszajelzést adott az út mentén. A példákat frissítettük:
  • távolítsa el a védekező programozást
  • állítások használata
  • hozzon létre egy önálló könyvtárat átlátszatlan struktúrával
  • bontsa ki az API-kat, beleértve az aktuális körkörös pufferméret kiszámítását
  • frissítse a könyvtárat, hogy ne pazarolja el a helyet