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:
- miért használjon körkörös puffert?
- C implementáció
- kapszulázás használata
- API tervezés
- annak meghatározása, hogy a puffer megtelt-e
- körkörös puffer tároló típusa
- implementáció
- használat
- módosítások a
full
zászló
- C++ implementáció
- class definition
- implementation
- használat
- frissítések a C++17
- mindent összerakva
- 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_t
vagy 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:
- “hulladék” egy rés a pufferben:
- a teljes állapot
head + 1 == tail
- az üres állapot
head == tail
- a teljes állapot
- 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 teljes állapot
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 head
tail
, é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 tail
nagyobb, 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 tail
mutató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
- 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
- 20210321
- javítva a hiba a
max_size_
aholcbuf->max
- hozzáadott tisztázó szöveg arról, hogy miért adja át a puffert a felhasználó
- javítva a hiba a
- 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
van egy javaslat körkörös puffertípus hozzáadására a C++ standard könyvtárhoz: