uppdaterad: 20210321

på grund av den resursbegränsade naturen hos inbäddade system kan cirkulära buffertdatastrukturer hittas i de flesta projekt.

cirkulära buffertar (även kända som ringbuffertar) är buffertar med fast storlek som fungerar som om minnet är sammanhängande & cirkulär i naturen. Eftersom minne genereras och konsumeras behöver data inte blandas om – snarare justeras Huvud – /svanspekarna. När data läggs till går huvudpekaren framåt. När data konsumeras går svanspekaren framåt. Om du når slutet av bufferten, slingrar pekarna helt enkelt till början.

för en mer detaljerad sammanfattning av cirkulär buffertoperation, se Wikipedia-artikeln. Resten av artikeln förutsätter att du har en förståelse för hur cirkulära buffertar fungerar.

Innehållsförteckning:

1. Varför använda en cirkulär buffert?
2. C implementering
   1. använda inkapsling
   2. API Design
   3. bestämma om en buffert är Full
   4. cirkulär Buffertbehållare Typ
   5. implementering
   6. användning
   7. ändringar för att ta bortfull flagga
3. C++ implementering
   1. klassdefinition
   2. implementering
   3. användning
   4. uppdateringar för C++17
4. att sätta ihop allt
5. Vidare läsning

varför använda en cirkulär buffert?

cirkulära buffertar används ofta som fasta köer. Den fasta storleken är fördelaktig för inbyggda system, eftersom utvecklare ofta försöker använda statiska datalagringsmetoder snarare än dynamiska allokeringar.

cirkulära buffertar är också användbara strukturer för situationer där dataproduktion och konsumtion sker i olika takt: de senaste uppgifterna är alltid tillgängliga. Om konsumenten inte kan hålla jämna steg med produktionen kommer de inaktuella uppgifterna att skrivas över med nyare data. Genom att använda en cirkulär buffert kan vi se till att vi alltid konsumerar de senaste uppgifterna.

För ytterligare användningsfall, kolla in grunderna för Ringbuffert på Embedded.com.

C-implementering

vi börjar med en C-implementering, eftersom detta utsätter oss för några av designutmaningarna och avvägningarna när vi skapar ett cirkulärt buffertbibliotek.

använda inkapsling

eftersom vi skapar ett cirkulärt buffertbibliotek vill vi se till att användare arbetar med våra Biblioteks-API: er istället för att ändra strukturen direkt. Vi vill också behålla implementeringen i vårt bibliotek så att vi kan ändra det efter behov, utan att kräva att slutanvändarna uppdaterar sin kod. Användaren behöver inte veta några detaljer om vår struktur, bara att den finns.

i vårt biblioteksrubrik kommer vi att vidarebefordra förklara strukturen:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

vi vill inte att användarna ska arbeta med en circular_but_t pekare direkt, eftersom de kan få intrycket att de kan avreferera värdet. Vi kommer att skapa en handtagstyp som de kan använda istället.

det enklaste sättet för vårt handtag är att typedefcbuf_handle_t som en pekare till den cirkulära bufferten. Detta kommer att hindra oss från att behöva kasta pekaren i vår funktionsimplementering.

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

ett alternativt tillvägagångssätt skulle vara att göra handtaget till ett uintptr_t eller void* värde. Inuti vårt gränssnitt skulle vi hantera översättningen till lämplig pekartyp. Vi håller den cirkulära bufferttypen dold för användare, och det enda sättet att interagera med data är genom handtaget.

Vi kommer att hålla fast vid det enkla handtaget för att hålla vår exempelkod enkel och okomplicerad.

API Design

först bör vi tänka på hur användarna kommer att interagera med en cirkulär buffert:

• de måste initiera den cirkulära buffertbehållaren med en buffert och storlek
• de måste förstöra en cirkulär buffertbehållare
• de måste återställa den cirkulära buffertbehållaren
• de måste kunna lägga till data i bufferten
• de måste kunna få nästa värde från bufferten
• de behöver veta om bufferten är full eller tom
• de behöver veta det aktuella antalet element i bufferten
• behöver de veta buffertens maximala kapacitet

med den här listan kan vi sätta ihop ett API för vårt bibliotek. Användare kommer att interagera med det cirkulära buffertbiblioteket med vår opaka handtagstyp, som skapas under initialiseringen.

Jag har valt uint8_t som underliggande datatyp i denna implementering. Du kan använda vilken typ du vill – var noga med att hantera den underliggande bufferten och antalet byte på lämpligt sätt.

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

bestämma om en buffert är Full

innan vi fortsätter bör vi ta en stund för att diskutera metoden vi ska använda för att avgöra om bufferten är full eller tom.

både de” fulla ”och” tomma”fallen av den cirkulära bufferten ser likadana ut: head och tail pekaren är lika. Det finns två metoder för att skilja mellan full och tom:

1. ”avfall” en lucka i bufferten:
   • fullt tillstånd ärhead + 1 == tail
   • tomt tillstånd ärhead == tail
2. använd enbool flagga och ytterligare logik för att skilja stater::
   • fullt tillstånd är full
   • tomt tillstånd är (head == tail) && !full

vi bör också överväga trådsäkerhet. Genom att använda en enda tom cell för att upptäcka det” fulla ” fallet kan vi stödja en enda producent och en enda konsument utan lås (så länge som put och get ändrar inte samma variabler). Kön är trådsäker eftersom producenten bara kommer att ändra headindex, och konsumenten kommer bara att ändratail index. Medan antingen index kan vara något out-of-date i ett givet sammanhang, detta kommer inte att påverka trådsäkerheten i kön. Att använda flaggan full skapar dock ett krav på ömsesidig uteslutning. Detta beror på att flaggan full delas av både producenten och konsumenten.

naturligtvis har beslutet sina kompromisser. Om ditt buffertelement har ett stort minnesfotavtryck (till exempel en buffert som är dimensionerad för en kamera i-frame) kan det hända att det inte är rimligt att slösa bort en plats på ditt system. Om du har flera producenter/konsumenter som interagerar med en kö, behöver du ändå ett lås, så det är inte meningsfullt att slösa bort en plats. Om du inte har ömsesidig uteslutning tillgänglig (t.ex. eftersom du inte använder ett operativsystem) men du använder avbrott, vill du använda flaggversionen som inte ärfull. Minnesmodellen som används på ditt system kan också påverka ditt beslut att gå utan lås.

implementeringen nedan använder flagganbool. Att använda flaggan kräver ytterligare logik i rutinerna get och put för att uppdatera flaggan. Jag kommer också att beskriva hur man gör ändringarna för en enda producent/konsument som inte använder flaggan full.

cirkulär Buffertbehållare Typ

Nu när vi har ett grepp om de operationer vi behöver stödja kan vi designa vår cirkulära buffertbehållare.

vi använder behållarstrukturen för att hantera buffertens tillstånd. För att bevara inkapsling definieras behållarstrukturen inuti vårt bibliotek.c – fil, snarare än i rubriken.

Vi måste hålla reda på:

• den underliggande databufferten
• den maximala storleken på bufferten
• den nuvarande ”head” – positionen (inkrementerad när element läggs till)
• den nuvarande ”tail” (inkrementerad när element tas bort)
• en flagga som anger om bufferten är full eller inte

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

nu när vår behållare är utformad är vi redo att implementera biblioteksfunktionerna.

implementering

en viktig detalj att notera är att var och en av våra API: er kräver ett initialiserat bufferthandtag. I stället för att kasta vår kod med villkorliga uttalanden, kommer vi att använda påståenden för att genomdriva våra API-krav i ”Design by Contract” – stilen.

om gränssnitten används felaktigt kommer programmet att misslyckas omedelbart snarare än att kräva att användaren kontrollerar och hanterar felkoden.

till exempel:

circular_buf_reset(NULL);

producerar:

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

en annan viktig anmärkning är att implementeringen som visas nedan inte är trådsäker. Inga lås har lagts till i det underliggande cirkulära buffertbiblioteket.

initiera och återställ

Låt oss börja från början: initiera en cirkulär buffert. Vårt API har kunder som tillhandahåller den underliggande bufferten och buffertstorleken, och vi returnerar ett cirkulärt bufferthandtag till dem. Anledningen till att vi vill att våra användare ska tillhandahålla bufferten är att detta möjliggör en statiskt tilldelad buffert. Om vårt API skapade bufferten under huven, skulle vi behöva använda dynamisk minnesallokering, vilket ofta inte tillåts i inbyggda systemprogram.

Vi måste tillhandahålla en cirkulär buffertstrukturinstans i biblioteket så att vi kan returnera en pekare till användaren. Jag har använt malloc för enkelhet. System som inte kan använda dynamiskt minne behöver helt enkelt ändra funktionen init för att använda en annan metod, till exempel allokering från en statisk pool av fördelad cirkulär buffertstrukturer.

ett annat tillvägagångssätt skulle vara att bryta inkapsling, så att användarna statiskt kan deklarera cirkulära buffertbehållarstrukturer utanför biblioteket. I det här fallet måste circular_buf_init uppdateras för att ta en struct-pekare. Vi kan också ha vår init funktion skapa en containerstruktur på stacken och returnera den grossist. Eftersom inkapslingen är trasig kan användarna dock ändra strukturen utan att använda biblioteksrutinerna. Om du vill bevara inkapsling måste du arbeta med pekare istället för konkreta strukturinstanser.

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

Vi kommer att returnera ett handtag till en struktur som tilldelas inuti biblioteket. När vi har skapat vår behållare behöver vi fylla i värdena och ringa reset på den. Innan vi återvänder från init, ser vi till att buffertbehållaren har skapats i tomt tillstånd.

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

syftet med återställningsfunktionen är att sätta bufferten i ett ”tomt” tillstånd, vilket kräver uppdatering headtail och full:

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

eftersom vi har en metod för att skapa en cirkulär buffertbehållare behöver vi en motsvarande metod för att förstöra behållaren. I det här fallet kallar vi free på vår Behållare. Vi försöker inte frigöra den underliggande bufferten, eftersom vi inte äger den.

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

Statskontroller

därefter implementerar vi funktionerna relaterade till buffertbehållarens tillstånd.

den fullständiga funktionen är den enklaste att implementera, eftersom vi har en flagga som representerar staten:

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

eftersom vi har flaggan full för att skilja mellan fullständigt eller tomt tillstånd, kombinerar vi flaggan med en kontroll som head == tail:

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

kapaciteten hos vår buffert levererades under initialiseringen, så vi returnerar bara det värdet till användaren:

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

beräkning av antalet element i bufferten var ett svårare problem än jag förväntade mig. Många föreslagna storleksberäkningar använder modulo, men jag stötte på konstiga hörnfall när jag testade det. Jag valde en förenklad beräkning med villkorliga uttalanden.

om bufferten är full vet vi att vår kapacitet är maximal. Om head är större än eller lika med tail, subtraherar vi helt enkelt de två värdena för att få vår storlek. Om tail är större än head, måste vi kompensera skillnaden med max för att få rätt storlek.

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

lägga till och ta bort Data

med bokföringsfunktionerna ur vägen är det dags att gräva i köttet: lägga till och ta bort data från kön.

lägga till och ta bort data från en cirkulär buffert kräver manipulering av head och tail pekare. När vi lägger till data i bufferten sätter vi in det nya värdet på den aktuella head plats, sedan avancerar vi head. När vi tar bort data från bufferten hämtar vi värdet på den aktuella tail pekaren och avancerar sedan tail.

att lägga till data i bufferten kräver dock lite mer eftertanke. Om bufferten ärfull, måste vi avancera vårtail pekare samthead. Vi måste också kontrollera om infoga ett värde utlöserfull villkor.

Vi kommer att implementera två versioner av funktionen put, så låt oss extrahera vår pekareutvecklingslogik till en hjälparfunktion. Om vår buffert redan är full, avancerar vi tail. Vi avancerar alltid head med en. När pekaren har avancerat fyller vi flaggan full genom att kontrollera om head == tail.

notera användningen av Modulo-operatören (%) nedan. Modulo gör att värdenahead ochtail återställs till 0 när maximal storlek uppnås. Detta säkerställer att head och tail alltid är giltiga index för den underliggande databufferten.

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

Som Miro Samek hjälpsamt påpekade är detta en dyr beräkningsoperation. Istället kan vi använda villkorlig logik för att minska det totala antalet instruktioner. Miros rekommenderade tillvägagångssätt är:

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

Nu kommer advance_pointer att se ut så här:

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

Vi kan göra en liknande hjälpfunktion som kallas när du tar bort ett värde från bufferten. När vi tar bort ett värde är full flaggan inställd på false, och svanspekaren är avancerad.

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

Vi skapar två versioner av funktionen put. Den första versionen infogar ett värde i bufferten och förflyttar pekaren. Om bufferten är full skrivs det äldsta värdet över. Detta är standardanvändningsfallet för en cirkulär buffert

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

den andra versionen av funktionenput returnerar ett fel om bufferten är full. Detta tillhandahålls för demonstrationsändamål, men vi använder inte denna variant i våra system.

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

för att ta bort data från bufferten kommer vi åt värdet på tail och uppdaterar sedan tail pekaren. Om bufferten är tom returnerar vi inte ett värde eller ändrar pekaren. Istället returnerar vi ett fel till användaren.

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

som slutför implementeringen av vårt cirkulära buffertbibliotek.

användning

När du använder biblioteket är klienten ansvarig för att skapa den underliggande databufferten till circular_buf_init och ett cbuf_handle_t returneras:

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

detta handtag används för att interagera med alla återstående biblioteksfunktioner:

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

glöm inte att frigöra både den underliggande databufferten och behållaren när du är klar:

free(buffer);circular_buf_free(cbuf);

ett testprogram som använder det cirkulära buffertbiblioteket finns i embedded-resources-arkivet.

ändringar för att ta bort hela flaggan

om du vill dike flaggan full, skulle du istället kontrollera att head är en position bakom svansen för att avgöra om bufferten är full:

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

nu, om vi ville undvika Modulo-operationen, kan vi använda villkorlig logik istället:

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

det tomma fallet är då att head och tail är desamma:

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

När vi hämtar data från bufferten kommer vi att avancera svanspekare, linda runt om det behövs:

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

När vi lägger till data i bufferten lagrar vi data och förflyttar huvudpekaren och lindar om det behövs:

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

andra referenser till full kan elimineras.

C++

C++ lämpar sig för en renare cirkulär buffertimplementering än C.

klassdefinition

vi börjar med att definiera vår C++ – klass. Vi vill att vår c++ – implementering ska stödja alla typer av data, så vi kommer att göra det till en mallklass.

våra API: er kommer att likna C-implementeringen. Vår klass kommer att ge gränssnitt för:

• återställa bufferten till Tom
• lägga till data
• ta bort data
• kontrollera fullständigt/tomt tillstånd
• kontrollera det aktuella antalet element i bufferten
• kontrollera buffertens totala kapacitet

Vi kommer också att använda C++ smarta pekare för att säkerställa att vi inte lämnar några data när vår buffert förstörs. Detta innebär att vi kan hantera bufferten för användaren.

en annan fördel med C++ är trivialiteten att göra denna klass trådsäker: vi kan lita på typen std::mutex (förutsatt att detta är definierat för din plattform).

Här är vår klassdefinition:

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

vår c++ – cirkulära buffert efterliknar mycket av logiken från C-implementeringen, men resulterar i en mycket renare och mer återanvändbar design. C++ – bufferten använder också std::mutex för att ge en trådsäker implementering.

Obs: samma logiska ändringar kan göras i C++-implementeringen för att stödja trådsäkerhet med en enda producent och konsument genom att” slösa ” en plats. Se justeringarna i genomförandet C för mer information.

initialisering

När vi konstruerar vår klass fördelar vi data för vår underliggande buffert och ställer in buffertstorleken. Detta tar bort den overhead som krävs med C-implementeringen.

Till skillnad från C-implementeringen kallar C++ – konstruktören inte reset. Eftersom vi anger initialvärden för våra medlemsvariabler börjar vår cirkulära buffert i rätt tillstånd.

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

vårt återställningsbeteende sätter bufferten tillbaka till ett tomt tillstånd (head == tail && !full_).

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

Statsspårning

logiken för empty och full fall är samma som C-exemplet:

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

i C++ cirkulär buffertimplementering rapporterar size och capacity antalet element i kön snarare än storleken i byte. Detta gör att vi kan vara agnostiska för de underliggande detaljerna av typen.

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

lägga till Data

logiken för put matchar C-implementeringen. Denna implementering använder beteendemönstret” Skriv över det äldsta värdet”.

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

Obs: För enkelhetens skull har jag utelämnat alternativet som undviker modulo-operationer. Du kan hitta den logiken i C-sektionen.

hämta Data

logiken bakom get matchar C-implementeringen. Till skillnad från C-implementeringen returneras ett tomt värde om bufferten är tom.

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

notera: return T() returnerar ett standardkonstruerat värde för RA given typ. Det faktiska värdet som produceras beror på typen eller konstruktören. För enkelhetens skull har jag också utelämnat alternativet som undviker modulo-operationer. Du kan hitta den logiken i C-sektionen.

användning

c++ cirkulär buffert är mycket enklare att använda än C-implementeringen.

för att initiera en cirkulär buffert, förklarar vi bara ett objekt och anger den mallade typen för vår buffert. Här är ett exempel med en buffert på 10uint32_t poster:

circular_buffer<uint32_t> circle(10);

att lägga till data är enkelt:

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

och att få data är lika enkelt:

x = circle.get()

Kom ihåg att eftersom det här är en mallad klass kan du skapa en cirkulär buffert av vilken typ du behöver.

uppdateringar för C++17

i C++17 har vi tillgång tillstd::optional, vilket gör att vi kan representera ett värde som kanske eller inte finns. Vår getfunktion skulle returnera enstd::optional<T>. Vi skulle också returnera std::nullopt istället för ett standardkonstruerat T om kön är tom.

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

Obs: För enkelhetens skull har jag utelämnat alternativet som undviker modulo-operationer. Du kan hitta den logiken i C-sektionen.

i anropskoden kan du söka efter ett giltigt värde med den booleska operatören eller has_value medlemsfunktion. Om ett giltigt värde är närvarande kan det nås med -> eller * operatorer, ur med value() medlemsfunktion.

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

att sätta ihop allt

exempel implementeringar kan hittas i embedded-resources Github repository.

• c cirkulärt bufferttestprogram
  • c cirkulärt buffertbibliotek
• c++ cirkulärt buffertexempel

om du vill utöka detta bibliotek är en användbar övning att lägga till ytterligare API: er för att göra det möjligt för användare att lägga till / ta bort flera element med en enda operation. Du kan också göra C-implementeringsgängan säker.

Trådsäkerhet med Lookahead-metoden

ett tillvägagångssätt för trådsäkerhet utan mutex är ”lookahead” – metoden. Denna metod stöder en enda producentgänga och en enda konsumenttråd; flera producenter eller konsumenter kommer att kräva ett lås.

istället för att använda den booleska flaggan för att skilja mellan de fullständiga och tomma Fallen lämnar vi alltid en cell tom. Genom att använda en enda tom cell för att upptäcka det” fulla ” fallet kan vi stödja en enda producent och en enda konsument utan lås (så länge som put och get ändrar inte samma variabler).

Du kan vara orolig för att slösa bort en plats, men denna avvägning är ofta mycket billigare än kostnaden för att använda ett primitivt OS-Lås.

Vidare läsning

• C++ smarta pekare
• dike dina C-Stye pekare för smarta pekare

här är andra cirkulära buffertimplementeringar:

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

För mer information om cirkulära buffertar:

• Embedded.com: grunderna för Ringbuffert
• Wikipedia: cirkulär buffert
• Järnsystem: Lås fri Ringbuffert
• Boost cirkulär buffert
• C++: Prestanda för en cirkulär buffert vs Vector, deque och List
• Lock-Free Single – Producer-Single Consumer Circular Queue

det finns ett förslag om att lägga till en cirkulär bufferttyp till C++ – standardbiblioteket:

• P0059: Ett förslag om att lägga till Ring Span till standardbiblioteket
  • Ring Span
  • Ring Span Lite

Ändra logg

• 20210321
  • fixat fel med max_size_därcbuf->maxbör ha om varför bufferten skickas in av användaren
• 20210301
  • adresserad feedback från Miro angående att undvika modulooperationer
• 20210213
  • lade till ytterligare länkar
  • lade till ytterligare diskussion om avvägning mellan full flagga vs med en ”bortkastad” slot
  • Visa ändringar för trådsäkerhet med en enda producent/konsument
  • Lägg till anteckningar om std::optional använd med C++17
• 20191016
  • uppdaterad Ändringsloggavsnittsformatering för konsistens över webbplatsen
  • degraderade rubriker för konsistens över webbplatsen
  • fast trasig Innehållsförteckning länkar
  • borttagen ändringslogg från Innehållsförteckning
• 20190627
  • tillagd länk till järnsystems låsfri ringbuffertartikel.
• 20190604
  • fixade ett stavfel (tack Chris Svec!) och ändrade någon formulering relaterad till den ogenomskinliga typen.
• 20181219
  • tillagd anteckning om att undvika samtidighetsproblem med en enda producent och en enda konsument som använder en tom plats.
• 20180804
  • artikeln har omstrukturerats och skrivits om.Tack till alla som gav feedback på vägen. Exemplen har uppdaterats till:
  • ta bort defensiv programmering
  • använd påståenden
  • skapa ett fristående bibliotek med en ogenomskinlig struktur
  • expandera API: erna, inklusive en beräkning för den aktuella cirkulära buffertstorleken
  • uppdatera biblioteket så att det inte slösade bort en plats