Aktualizováno: 20210321

Vzhledem k omezenými přírodními zdroji, povaze embedded systémy, kruhové vyrovnávací paměti datové struktury lze nalézt ve většině projektů.

Kruhové vyrovnávací paměti (také známé jako vyrovnávací paměti ring) jsou pevné velikosti vyrovnávací paměti, které fungují, jako kdyby je paměť souvislé & kruhový charakter. Jak je paměť generována a spotřebována, data nemusí být přeskupena-spíše jsou upraveny ukazatele hlavy/ocasu. Po přidání dat postupuje ukazatel hlavy. Když jsou data spotřebována, ukazatel ocasu postupuje. Pokud se dostanete na konec vyrovnávací paměti, ukazatele se jednoduše zabalí na začátek.

podrobnější shrnutí operace kruhové vyrovnávací paměti naleznete v článku na Wikipedii. Zbytek článku předpokládá, že máte pochopení toho, jak fungují kruhové vyrovnávací paměti.

obsah:

1. Proč používat Kruhový vyrovnávací paměť?
2. C Provádění
   1. Pomocí Zapouzdření
   2. API Design
   3. Určení, pokud Vyrovnávací paměť je Plná
   4. Kruhový Buffer Typ Kontejneru
   5. Realizace
   6. Využití
   7. Modifikace pro Odstranění full vlajky
3. Implementace C++
   1. Definice Třídy
   2. Realizace
   3. Využití
   4. Aktualizace pro C++17
4. Dát To Všechno Dohromady
5. Další Čtení

Proč Používat Kruhový Buffer?

kruhové vyrovnávací paměti se často používají jako fronty s pevnou velikostí. Pevná velikost je výhodná pro vestavěné systémy, protože vývojáři se často snaží používat statické metody ukládání dat spíše než dynamické alokace.

kruhové vyrovnávací paměti jsou také užitečné struktury pro situace, kdy výroba a spotřeba dat probíhá různými rychlostmi: nejnovější data jsou vždy k dispozici. Pokud spotřebitel nemůže držet krok s výrobou, zastaralá data budou přepsána novějšími údaji. Pomocí kruhové vyrovnávací paměti můžeme zajistit, že vždy spotřebováváme nejnovější data.

pro další případy použití, podívejte se na základy Ring Buffer na Embedded.com.

C Provedení

začneme s C provádění, protože to nás vystavuje některé konstrukční problémy a kompromisy při vytváření kruhové vyrovnávací paměti knihovny.

pomocí zapouzdření

protože vytváříme knihovnu kruhové vyrovnávací paměti, chceme zajistit, aby uživatelé pracovali s našimi API knihovny namísto přímé úpravy struktury. Chceme také udržet implementaci obsaženou v naší knihovně, abychom ji mohli podle potřeby změnit, aniž bychom museli koncovým uživatelům aktualizovat svůj kód. Uživatel nemusí znát žádné podrobnosti o naší struktuře, pouze to, že existuje.

V naší knihovně záhlaví, budeme dopředu deklarovat strukturu:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

nechceme uživatelům pracovat s circular_but_t ukazatel přímo, protože by mohli získat dojem, že se může dereference hodnotu. Vytvoříme typ rukojeti, který mohou místo toho použít.

nejjednodušší přístup pro naše rukojeť je typedefcbuf_handle_t jako ukazatel na kruhové vyrovnávací paměti. To nám zabrání v nutnosti obsazení ukazatele v rámci implementace naší funkce.

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

alternativní přístup by bylo, aby se rukojeť uintptr_t nebo void* hodnota. Uvnitř našeho rozhraní bychom zpracovali překlad na příslušný typ ukazatele. Udržujeme Kruhový typ vyrovnávací paměti skrytý před uživateli a jediný způsob interakce s daty je prostřednictvím rukojeti.

budeme se držet jednoduché implementace rukojeti, abychom udrželi náš příkladový kód jednoduchý a přímočarý.

design API

nejprve bychom měli přemýšlet o tom, jak budou uživatelé interagovat s kruhovým bufferem:

• musí inicializovat kruhové vyrovnávací nádoby s vyrovnávací paměti a velikost
• je třeba zničit kruhové vyrovnávací nádoby
• potřebují obnovit kruhové vyrovnávací nádoby
• musí být schopen, aby přidat data do vyrovnávací paměti
• musí být schopen získat další hodnotu z vyrovnávací paměti
• Potřebují vědět, zda je vyrovnávací paměť plná nebo prázdná
• potřebují znát aktuální počet prvků ve vyrovnávací paměti
• potřebují znát max. kapacita vyrovnávací paměti

Pomocí tohoto seznamu, můžeme dát dohromady API pro naši knihovnu. Uživatelé budou komunikovat s knihovnou kruhové vyrovnávací paměti pomocí našeho neprůhledného typu rukojeti, který je vytvořen během inicializace.

jako základní datový typ v této implementaci jsem zvolil uint8_t. Můžete použít jakýkoli konkrétní typ, který se vám líbí – jen buďte opatrní, abyste správně zpracovali základní vyrovnávací paměť a počet bajtů.

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

Určení, pokud Vyrovnávací paměť je Plná

Než budeme pokračovat, měli bychom se na chvíli diskutovat metodu budeme používat k určení, zda je vyrovnávací paměť plná nebo prázdná.

Jak „plný“ a „prázdný“ případy z kruhové vyrovnávací paměti vypadají stejně: headtail ukazatel jsou stejné. Existují dva přístupy k rozlišování mezi plným a prázdným:

1. „Odpad“ slot v paměti:
   • Plné stát je head + 1 == tail
   • Prázdného stavu je head == tail
2. Použití bool vlajky a další logické rozlišovat státy::
   • Plné stát je full
   • Prázdného stavu je (head == tail) && !full

měli Bychom také zvážit bezpečnost podprocesu. Pomocí jediné prázdné buňky detekovat „plné“ případ, můžeme podpořit jednoho výrobce a jednoho spotřebitele, aniž by zámek (stejně dlouho jako putget ne změnit stejné proměnné). Fronta je thread-safe, protože výrobce bude pouze změnit na head index, a spotřebitel bude pouze změnit na tail index. Zatímco jeden index může být v daném kontextu mírně zastaralý, nebude to mít vliv na bezpečnost vlákna fronty. Použití příznaku full však vytváří požadavek na vzájemné vyloučení. Je to proto, že příznak full sdílí jak výrobce, tak spotřebitel.

rozhodnutí má samozřejmě své kompromisy. Pokud má váš vyrovnávací prvek velkou paměťovou stopu (například vyrovnávací paměť, která je dimenzována pro fotoaparát i-frame), plýtvání slotem nemusí být ve vašem systému rozumné. Pokud máte více výrobců/spotřebitelů, kteří interagují s frontou, budete stejně potřebovat zámek, takže plýtvání slotem nedává smysl. Pokud nemáte vzájemné vyloučení k dispozici, (např., protože nepoužíváte OS), ale používáte přerušení, pak budete chtít použít non-full vlajky verze. Paměťový model použitý ve vašem systému může mít také dopad na vaše rozhodnutí jít bez zámku.

níže uvedená implementace používá příznak bool. Použití příznaku vyžaduje další logiku v rutinách get a put pro aktualizaci příznaku. Popíšu také, Jak provést úpravy pro jednoho výrobce/spotřebitele, který nepoužívá příznak full.

Kruhový vyrovnávací kontejner Typ

Nyní, když máme přehled o operacích, které budeme potřebovat k podpoře, můžeme navrhnout náš kruhový vyrovnávací kontejner.

pro správu stavu vyrovnávací paměti používáme strukturu kontejneru. Pro zachování zapouzdření je struktura kontejneru definována uvnitř naší knihovny .c soubor, spíše než v záhlaví.

Budeme muset sledovat:

• základní data vyrovnávací paměti
• maximální velikost vyrovnávací paměti
• aktuální „vedoucí“ pozici (zvýšen, když prvky jsou přidány)
• aktuální „ocas“ (zvýšen, když prvky jsou odstraněny)
• příznak označující, zda buffer je plný, nebo ne

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

Nyní, že náš kontejner je navržen tak, jsme připraveni realizovat knihovna funkcí.

implementace

jedním důležitým detailem je, že každé z našich API vyžaduje inicializovanou rukojeť vyrovnávací paměti. Spíše než vrhat náš kód podmíněnými prohlášeními, použijeme tvrzení k prosazení našich požadavků API ve stylu“ Design by Contract“.

pokud jsou rozhraní nesprávně použita, program selže okamžitě, místo aby vyžadoval, aby uživatel zkontroloval a zpracoval kód chyby.

například:

circular_buf_reset(NULL);

produkuje:

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

Další důležitou poznámkou je, že níže uvedená implementace není bezpečná pro vlákna. Do podkladové knihovny kruhové vyrovnávací paměti nebyly přidány žádné zámky.

inicializujte a resetujte

začněme od začátku: inicializace kruhové vyrovnávací paměti. Naše rozhraní API poskytuje klientům základní velikost vyrovnávací paměti a vyrovnávací paměti a vracíme jim Kruhový popisovač vyrovnávací paměti. Důvodem, proč chceme, aby naši uživatelé poskytovali vyrovnávací paměť, je to, že to umožňuje staticky přidělenou vyrovnávací paměť. Pokud by naše API vytvořilo vyrovnávací paměť pod kapotou, museli bychom využít dynamickou alokaci paměti, která je v programech vestavěných systémů často zakázána.

jsme povinni poskytnout instanci struktury kruhové vyrovnávací paměti v knihovně, abychom mohli uživateli vrátit ukazatel. Pro jednoduchost jsem použil malloc. Systémy, které nelze použít dynamickou paměť, stačí změnit na init funkci použít jinou metodu, jako je přidělení statické bazén z pre-přidělené kruhový buffer struktur.

Další možností by bylo, aby porušit zapouzdření, který umožňuje uživatelům staticky deklarovat kruhové vyrovnávací nádoba struktur mimo knihovnu. V tomto případě je třeba circular_buf_init aktualizovat, aby se ukazatel struktury. Mohli bychom také mít naši funkci init vytvořit strukturu kontejneru na zásobníku a vrátit jej velkoobchodně. Protože je však zapouzdření přerušeno, uživatelé budou moci strukturu upravit bez použití rutin knihovny. Pokud chcete zachovat zapouzdření, musíte pracovat s ukazateli místo instancí konkrétní struktury.

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

vrátíme popisovač struktuře, která je přidělena uvnitř knihovny. Jakmile jsme vytvořili náš kontejner, musíme naplnit hodnoty a zavolat na něj reset. Než se vrátíme z init, zajistíme, že vyrovnávací kontejner byl vytvořen v prázdném stavu.

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

účelem obnovení funkce je dát vyrovnávací paměti do „prázdného“ stavu, který vyžaduje aktualizaci headtailfull:

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

protože máme metodu pro vytvoření kruhové vyrovnávací nádoby, potřebujeme ekvivalentní metodu pro zničení kontejneru. V tomto případě voláme free na našem kontejneru. Nepokoušíme se uvolnit podkladovou vyrovnávací paměť, protože ji nevlastníme.

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

Kontrola stavu

dále implementujeme funkce související se stavem vyrovnávací nádoby.

plná funkce je nejjednodušší implementovat, protože máme příznak představující stav:

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

Protože jsme full vlajky rozlišovat mezi plné nebo prázdné státu, jsme se spojit vlajku s ověřte, že head == tail:

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

kapacita vyrovnávací paměti byl dodán během inicializace, tak jsme se jen vrátit, že hodnotu pro uživatele:

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

Výpočtu počtu prvků v pufru byl složitější problém, než jsem čekal. Mnoho navrhovaných výpočtů velikosti používá modulo, ale při testování jsem narazil na podivné rohové případy. Rozhodl jsem se pro zjednodušený výpočet pomocí podmíněných příkazů.

Pokud je vyrovnávací paměť plná, víme, že naše kapacita je na maximu. Pokud head je větší než nebo rovno-tail, můžeme jednoduše odečíst dvě hodnoty, aby se naše velikost. Pokud tail je větší než head, musíme kompenzovat rozdíl s max jak získat správnou velikost.

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

Přidávání a Odebírání Dat

S účetnictví funkce z cesty, je čas kopat do masa: přidání a odebrání dat z fronty.

Přidávání a odebírání dat z kruhové vyrovnávací paměti vyžaduje manipulaci headtail ukazatelů. Při přidávání dat do vyrovnávací paměti vložíme novou hodnotu na aktuální head místo, pak postupujeme head. Když odstraníme data z vyrovnávací paměti, načteme hodnotu aktuálního tail ukazatel a poté postoupíme tail.

Přidání dat do vyrovnávací paměti však vyžaduje trochu více přemýšlení. Pokud vyrovnávací paměti je full, musíme předem naše tail ukazatel, stejně jako head. Musíme také zkontrolovat, zda vložení hodnoty spouští podmínku full.

chystáme se implementovat dvě verze funkce put, takže extrahujme naši logiku postupu ukazatele do pomocné funkce. Pokud je naše vyrovnávací paměť již plná, postupujeme tail. Vždy postupujeme head jedním. Po ukazatel byl pokročilý, jsme naplnit full vlajky kontrolou, zda head == tail.

Všimněte si použití operátora modulo (%) níže. Modulo způsobí, že hodnoty head a tail se po dosažení maximální velikosti resetují na 0. Tím je zajištěno, že head a tail jsou vždy platné indexy podkladové datové vyrovnávací paměti.

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

jak ochotně podotkl Miro Samek, jedná se o nákladnou výpočetní operaci. Místo toho můžeme použít podmíněnou logiku ke snížení celkového počtu instrukcí. Miro doporučený přístup je:

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

nyní advance_pointer bude vypadat takto:

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

můžeme vytvořit podobnou pomocnou funkci, která se nazývá při odstraňování hodnoty z vyrovnávací paměti. Když odstraníme hodnotu, příznak full je nastaven na false a ukazatel ocasu je pokročilý.

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

vytvoříme dvě verze funkce put. První verze vloží hodnotu do vyrovnávací paměti a posune ukazatel. Pokud je vyrovnávací paměť plná, nejstarší hodnota bude přepsána. To je standardní případ použití pro kruhové vyrovnávací paměti

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

druhá verze put funkce vrátí chybu, pokud vyrovnávací paměť je plná. Toto je poskytováno pro demonstrační účely, ale tuto variantu v našich systémech nepoužíváme.

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

odstranit data z vyrovnávací paměti, máme přístup k hodnotu na tail a pak aktualizovat tail ukazatel. Pokud je vyrovnávací paměť prázdná, nevrátíme hodnotu ani nezměníme ukazatel. Místo toho vrátíme uživateli chybu.

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

, který dokončí implementaci naší knihovny kruhové vyrovnávací paměti.

Použití

Při používání knihovny, je klient zodpovědný za vytvoření podkladových dat buffer circular_buf_initcbuf_handle_t je vrácen

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

Tento ovladač se používá k interakci s všechny ostatní funkce knihovny:

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

nezapomeňte, aby se zdarma a to jak podkladové vyrovnávací paměť dat a nádoby, když jste hotovi:

free(buffer);circular_buf_free(cbuf);

testovací program, který používá knihovnu kruhové vyrovnávací paměti, lze nalézt v úložišti embedded-resources.

Modifikace pro Odstranění plné vlajka

Pokud jste chtěli zbavit full vlajky, měli byste místo toho zkontrolujte, zda head je o jednu pozici za ocas k určení, pokud vyrovnávací paměť je plná:

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

Nyní, pokud bychom chtěli, aby se zabránilo operaci modulo, můžeme použít podmíněné logiky místo:

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

prázdné případě je pak to, že headtail jsou stejné,

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

Při získání dat z vyrovnávací paměti, budeme postupovat ocas ukazatel, obtékání kolem pokud je to nutné:

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

Při přidávání dat do vyrovnávací paměti, budeme ukládat data a zálohy hlava ukazatel, obtékání kolem pokud je to nezbytné:

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

Další odkazy full mohou být odstraněny.

C++

c++ se hodí k čistší implementaci kruhové vyrovnávací paměti než C.

definice třídy

začneme definováním naší třídy C++. Chceme, aby naše implementace c++ podporovala jakýkoli typ dat, takže z ní uděláme templátovou třídu.

naše API budou podobná implementaci C. Naše třída poskytne rozhraní pro:

• Resetování buffer prázdný
• Přidávání dat
• Odstranění dat
• Kontrola plné/prázdné státu
• Kontrola aktuální počet prvků ve vyrovnávací paměti
• Kontrola celková kapacita vyrovnávací paměti

Budeme také využívat C++ inteligentní ukazatele, aby zajistily, určitě nezůstanou žádné údaje jednou naše vyrovnávací paměť je zničena. To znamená, že můžeme spravovat vyrovnávací paměť pro uživatele.

Další výhodou C++ je trivialita tvorby této třídy thread-safe: můžeme se spolehnout na std::mutex type (za předpokladu, že je definován pro vaši platformu).

Tady je naše definice třídy:

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++ Implementace

Naše C++ kruhové vyrovnávací paměti napodobuje moc logiku z C realizaci, ale výsledky v mnohem čistší a opakovaně design. Také vyrovnávací paměť C++ využívá std::mutex k zajištění implementace bezpečné pro vlákna.

Poznámka: stejnou logiku změny mohou být provedeny v C++ implementace podporovat závit-bezpečnostní s jediným výrobcem a spotřebitelem o „plýtvání“ slot. Další informace naleznete v části úpravy v implementaci C.

inicializace

při konstrukci naší třídy přidělíme data pro náš podkladový vyrovnávací paměť a nastavíme velikost vyrovnávací paměti. Tím se odstraní režijní náklady požadované s implementací C.

Na rozdíl od implementace C Konstruktor c++ nevolá reset. Protože určujeme počáteční hodnoty pro naše členské proměnné, naše kruhová vyrovnávací paměť začíná ve správném stavu.

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

Naše reset chování dává vyrovnávací paměti zpět do prázdného stavu (head == tail && !full_).

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

Sledování

logika emptyfull případech je stejný jako C příklad:

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

V C++ kruhový buffer provádění, sizecapacity zpráva počet prvků ve frontě, spíše než velikost v bajtech. To nám umožňuje být Agnostický k podkladovým detailům typu.

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

Přidávání Dat

logické put odpovídá C provádění. Tato implementace používá vzor chování „přepsat nejstarší hodnotu“.

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

Poznámka: Pro jednoduchost jsem vynechal možnost, která se vyhýbá modulo operací. Tuto logiku najdete v sekci C.

Načítání Dat

logika get odpovídá C provádění. Na rozdíl od implementace C je prázdná hodnota vrácena, pokud je vyrovnávací paměť prázdná.

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

Poznámka: return T() vrátí výchozí konstruovanou hodnotu pro daný typ. Skutečná vytvořená hodnota závisí na typu nebo konstruktoru. Také pro jednoduchost jsem vynechal možnost, která se vyhýbá modulo operacím. Tuto logiku najdete v sekci C.

použití

kruhová vyrovnávací paměť C++ je mnohem jednodušší než implementace C.

Chcete-li vytvořit kruhovou vyrovnávací paměť, stačí deklarovat objekt a určit typ šablony pro naši vyrovnávací paměť. Zde je příklad použití vyrovnávací paměti 10 uint32_t položky:

circular_buffer<uint32_t> circle(10);

Přidávání dat je jednoduché:

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

A získávání dat je stejně jednoduché:

x = circle.get()

Pamatujte si, že protože se jedná o šablonové třídy, můžete vytvořit kruhové vyrovnávací paměti jakéhokoli typu, které potřebujete.

Aktualizace pro C++17

V C++17, máme přístup do std::optional, který nám umožňuje reprezentovat hodnoty, které mohou nebo nemusí být přítomen. Naše get funkce vrátí std::optional<T>. Také bychom vrátili std::nullopt místo výchozího T, pokud je fronta prázdná.

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

Poznámka: Pro jednoduchost jsem vynechal možnost, která se vyhýbá modulo operací. Tuto logiku najdete v sekci C.

V volající kód, můžete zkontrolovat pro platnou hodnotu pomocí booleovských operátor nebo has_value členské funkce. Pokud platná hodnota je přítomen, to může být přístupné pomocí -> nebo * operátoři, ur pomocí value() členské funkce.

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

Dát to Všechno Dohromady

Příklad implementace lze nalézt v embedded-resources Github úložiště.

• C kruhový buffer testovací program
  • C kruhový buffer knihovna
• C++ kruhové vyrovnávací paměti příklad

Pokud hledáte k rozšíření této knihovny, užitečné cvičení je, aby přidat další rozhraní Api, které umožní uživatelům přidat/odebrat více prvků s jedinou operaci. Můžete také vytvořit vlákno implementace C-bezpečné.

Bezpečnost Podprocesu se Metoda dopředného vyhledávání

Jeden přístup pro thread-bezpečnost bez mutex je „lookahead“ metoda. Tato metoda podporuje jediný výrobní závit a jediný spotřebitelský závit; více výrobců nebo spotřebitelů bude vyžadovat zámek.

Namísto použití boolean flag rozlišovat mezi plné a prázdné případech budeme vždy nechat jednu buňku prázdnou. Pomocí jediné prázdné buňky detekovat „plné“ případ, můžeme podpořit jednoho výrobce a jednoho spotřebitele, aniž by zámek (stejně dlouho jako putget ne změnit stejné proměnné).

můžete mít obavy z plýtvání slotem,ale tento kompromis je často mnohem levnější než náklady na použití primitivního zámku OS.

Další Čtení

• C++ Inteligentní Ukazatelů
• Příkopu C-ječné zrno Ukazatele pro Chytré Ukazatele

Zde jsou další kruhový buffer implementace:

• QuantumLeaps/zámek-zdarma-ring vyrovnávací paměti
• willemt/BipBuffer

Pro více informací o kruhové vyrovnávací paměti:

• Embedded.com: Ring buffer základy
• Wikipedie: Kruhové vyrovnávací paměti
• Železné Systémy: Lock Ring Vyrovnávací paměti
• Zvýšení Kruhové Vyrovnávací paměti
• C++: Výkon Kruhový Buffer vs Vector, Deque a List
• Lock-Free Single-Výrobce – Jednoho Spotřebitele Kruhové Fronty

Tam je návrh na doplnění kruhové vyrovnávací paměti typu C++ standardní knihovny:

• P0059: Návrh na doplnění Prsten Span Standardní Knihovna
  • Kroužek Rozpětí
  • Kroužek Span Lite

Změnit Log

• 20210321
  • Opravena chyba s max_size_cbuf->max by měl být použit
  • Přidán vysvětlující text týkající se, proč vyrovnávací paměti je předán v uživatelem
• 20210301
  • Určeno zpětnou vazbu od Miro týkající se vyhnout modulo operace
• 20210213
  • další odkazy
  • Přidána další diskusi o kompromis mezi plnou vlajka vs pomocí „zbytečný“ slot
  • Zobrazit změny pro bezpečnost podprocesu pomocí jediného výrobce/spotřebitele
  • Přidat poznámky na std::optional použití s C++17
• 20191016
  • Aktualizované Změna Log části formátování pro soudržnost na celém webu
  • Degradován záhlaví konzistence na celém webu
  • Pevná rozbité Obsah odkazy
  • Odstraněno Změna Log z Obsahu
• 20190627
  • Přidán odkaz na Železných Systémů Lock Ring Buffer čl.
• 20190604
  • Opraven překlep (díky Chris Svec!) a změnil některé znění týkající se neprůhledného typu.
• 20181219
  • přidána poznámka o zamezení problémům souběžnosti s jedním výrobcem a jediným spotřebitelem pomocí prázdného slotu.
• 20180804
  • článek byl restrukturalizován a přepsán.Děkujeme všem, kteří na cestě poskytli zpětnou vazbu. Příklady byly aktualizovány na:
  • Odstranit defenzivní programování
  • Použití tvrzení
  • Vytvořit samostatnou knihovnu pomocí neprůhledná struktura
  • Rozšířit Api, včetně výpočtu pro aktuální oběžník velikost vyrovnávací paměti
  • Aktualizovat knihovnu, takže to netrvalo slot