Aggiornato: 20210321

A causa della natura vincolata alle risorse dei sistemi embedded, le strutture di dati del buffer circolare possono essere trovate nella maggior parte dei progetti.

I buffer circolari (noti anche come buffer ad anello) sono buffer di dimensioni fisse che funzionano come se la memoria fosse contigua& di natura circolare. Quando la memoria viene generata e consumata, i dati non devono essere rimescolati, piuttosto i puntatori head/tail vengono regolati. Quando i dati vengono aggiunti, il puntatore testa avanza. Quando i dati vengono consumati, il puntatore della coda avanza. Se raggiungi la fine del buffer, i puntatori si avvolgono semplicemente all’inizio.

Per un riepilogo più dettagliato del funzionamento del buffer circolare, fare riferimento all’articolo di Wikipedia. Il resto dell’articolo presuppone che tu abbia una comprensione di come funzionano i buffer circolari.

Sommario:

1. Perché usare un buffer circolare?
2. Implementazione C
   1. Incapsulamento
   2. Progettazione di API
   3. Determinare se un Buffer è Pieno
   4. Buffer Circolare Tipo di Contenitore
   5. Realizzazione
   6. Uso
   7. Modifiche per la Rimozione del full flag
3. Implementazione di C++
   1. Definizione di Classe
   2. Realizzazione
   3. Uso
   4. gli Aggiornamenti per C++17
4. Mettere Tutto Insieme
5. bibliografia

Perché Utilizzare Un Buffer Circolare?

I buffer circolari vengono spesso utilizzati come code di dimensioni fisse. La dimensione fissa è vantaggiosa per i sistemi embedded, poiché gli sviluppatori spesso cercano di utilizzare metodi di archiviazione dati statici piuttosto che allocazioni dinamiche.

I buffer circolari sono anche strutture utili per situazioni in cui la produzione e il consumo di dati avvengono a velocità diverse: i dati più recenti sono sempre disponibili. Se il consumatore non riesce a tenere il passo con la produzione, i dati obsoleti verranno sovrascritti con dati più recenti. Utilizzando un buffer circolare, possiamo assicurarci di consumare sempre i dati più recenti.

Per ulteriori casi d’uso, controlla Ring Buffer Basics su Embedded.com.

Implementazione C

Inizieremo con un’implementazione C, poiché questo ci espone ad alcune delle sfide e dei compromessi di progettazione durante la creazione di una libreria buffer circolare.

Utilizzando l’incapsulamento

Poiché stiamo creando una libreria buffer circolare, vogliamo assicurarci che gli utenti lavorino con le nostre API di libreria invece di modificare direttamente la struttura. Vogliamo anche mantenere l’implementazione contenuta nella nostra libreria in modo da poterla modificare secondo necessità, senza richiedere agli utenti finali di aggiornare il loro codice. L’utente non ha bisogno di conoscere alcun dettaglio sulla nostra struttura, solo che esiste.

Nella nostra intestazione della libreria, inoltreremo dichiarare la struttura:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

Non vogliamo che gli utenti lavorino direttamente con un puntatorecircular_but_t, poiché potrebbero avere l’impressione di poter dereferenziare il valore. Creeremo un tipo di maniglia che possono utilizzare invece.

L’approccio più semplice per il nostro handle è typedef il cbuf_handle_t come puntatore al buffer circolare. Ciò ci impedirà di dover lanciare il puntatore all’interno della nostra implementazione della funzione.

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

Un approccio alternativo sarebbe quello di rendere l’handle un valoreuintptr_tovoid*. All’interno della nostra interfaccia, gestiremmo la traduzione al tipo di puntatore appropriato. Manteniamo il tipo di buffer circolare nascosto agli utenti e l’unico modo per interagire con i dati è attraverso l’handle.

Stiamo andando a bastone con la semplice implementazione maniglia per mantenere il nostro codice di esempio semplice e diretto.

API Design

In primo luogo, dovremmo pensare a come gli utenti interagiranno con un buffer circolare:

• Hanno bisogno di inizializzare il buffer circolare contenitore con un buffer di dimensione
• Hanno bisogno di distruggere un buffer circolare contenitore
• Hanno bisogno di azzerare il buffer circolare contenitore
• di cui Hanno bisogno per essere in grado di aggiungere dati al buffer
• di cui Hanno bisogno per essere in grado di ottenere il valore successivo buffer
• Hanno bisogno di sapere se il buffer è pieno o vuoto
• Hanno bisogno di conoscere l’attuale numero di elementi nel buffer
• Hanno bisogno di sapere la portata massima del buffer

l’Utilizzo di questo elenco, si può mettere insieme un’API per la nostra biblioteca. Gli utenti interagiranno con la libreria buffer circolare utilizzando il nostro tipo di handle opaco, che viene creato durante l’inizializzazione.

Ho scelto uint8_t come tipo di dati sottostante in questa implementazione. È possibile utilizzare qualsiasi tipo particolare che ti piace – basta fare attenzione a gestire il buffer sottostante e il numero di byte in modo appropriato.

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

Determinare se un buffer è pieno

Prima di procedere, dovremmo prendere un momento per discutere il metodo che useremo per determinare se o buffer è pieno o vuoto.

Entrambi i casi “pieno” e “vuoto” del buffer circolare hanno lo stesso aspetto:head etail puntatore sono uguali. Ci sono due approcci per differenziare tra pieno e vuoto:

1. “Spreco” di uno slot nel buffer:
   • Full è stato head + 1 == tail
   • Vuoto è stato head == tail
2. Utilizzare un bool bandiera e logica aggiuntiva per differenziare stati::
   • Lo stato completo è full
   • Lo stato vuoto è (head == tail) && !full

Dovremmo anche considerare la sicurezza del filo. Utilizzando una singola cella vuota per rilevare il caso “completo”, possiamo supportare un singolo produttore e un singolo consumatore senza un blocco (purché put e get non modifichino le stesse variabili). La coda è thread-safe perché il produttore modificherà solo l’indicehead e il consumatore modificherà solo l’indicetail. Mentre entrambi gli indici potrebbero essere leggermente obsoleti in un determinato contesto, ciò non influirà sulla sicurezza del thread della coda. L’utilizzo del flagfull, tuttavia, crea un requisito per l’esclusione reciproca. Questo perché il flagfull è condiviso sia dal produttore che dal consumatore.

Naturalmente, la decisione ha i suoi compromessi. Se il tuo elemento buffer ha un ingombro di memoria elevato (ad esempio un buffer di dimensioni per un i-frame della fotocamera), sprecare uno slot potrebbe non essere ragionevole sul tuo sistema. Se hai più produttori / consumatori che interagiscono con una coda, avrai comunque bisogno di un blocco, quindi sprecare uno slot non ha senso. Se non si dispone di un’esclusione reciproca disponibile (ad esempio, perché non si utilizza un sistema operativo) ma si utilizzano interrupt, si desidera utilizzare la versione di flag nonfull. Il modello di memoria utilizzato sul sistema può anche avere un impatto sulla vostra decisione di andare senza un blocco.

L’implementazione seguente utilizza il flagbool. L’utilizzo del flag richiede una logica aggiuntiva nelle routineget eput per aggiornare il flag. Descriverò anche come apportare le modifiche per un singolo produttore / consumatore che non utilizza il flag full.

Circular Buffer Container Type

Ora che abbiamo una conoscenza delle operazioni che dovremo supportare, possiamo progettare il nostro circular buffer container.

Usiamo la struttura del contenitore per gestire lo stato del buffer. Per preservare l’incapsulamento, la struttura del contenitore è definita all’interno della nostra libreria .c file, piuttosto che nell’intestazione.

Abbiamo bisogno di tenere traccia di:

• I dati sottostanti buffer
• La dimensione massima del buffer
• L’attuale “capo” posizione (incrementato quando gli elementi vengono aggiunti)
• L’attuale “coda” (incrementato quando gli elementi vengono rimossi)
• Un flag che indica se il buffer è pieno o non

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

Ora che il nostro contenitore è stato progettato, siamo pronti per implementare le funzioni di libreria.

Implementazione

Un dettaglio importante da notare è che ciascuna delle nostre API richiede un handle di buffer inizializzato. Piuttosto che sporcare il nostro codice con dichiarazioni condizionali, utilizzeremo le asserzioni per far rispettare i nostri requisiti API nello stile “Design by Contract”.

Se le interfacce vengono utilizzate in modo improprio, il programma fallirà immediatamente piuttosto che richiedere all’utente di controllare e gestire il codice di errore.

Ad esempio:

circular_buf_reset(NULL);

Produce:

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

Un’altra nota importante è che l’implementazione mostrata di seguito non è thread-safe. Nessun blocco è stato aggiunto alla libreria buffer circolare sottostante.

Inizializza e ripristina

Iniziamo dall’inizio: inizializzando un buffer circolare. La nostra API ha clienti forniscono il buffer sottostante e la dimensione del buffer, e restituiamo una maniglia buffer circolare a loro. Il motivo per cui vogliamo che i nostri utenti forniscano il buffer è che ciò consente un buffer allocato staticamente. Se la nostra API ha creato il buffer sotto il cofano, avremmo bisogno di fare uso di allocazione dinamica della memoria, che è spesso non consentito nei programmi di sistemi embedded.

Ci viene richiesto di fornire un’istanza di struttura buffer circolare all’interno della libreria in modo da poter restituire un puntatore all’utente. Ho usato malloc per semplicità. I sistemi che non possono utilizzare la memoria dinamica devono semplicemente modificare la funzione init per utilizzare un metodo diverso, come l’allocazione da un pool statico di strutture di buffer circolari preallocate.

Un altro approccio sarebbe quello di interrompere l’incapsulamento, consentendo agli utenti di dichiarare staticamente strutture di contenitori buffer circolari al di fuori della libreria. In questo caso,circular_buf_init deve essere aggiornato per prendere un puntatore struct. Potremmo anche avere la nostra funzioneinit creare una struttura contenitore sullo stack e restituirla all’ingrosso. Tuttavia, poiché l’incapsulamento è rotto, gli utenti saranno in grado di modificare la struttura senza utilizzare le routine di libreria. Se si desidera preservare l’incapsulamento, è necessario lavorare con i puntatori invece di istanze di struttura in calcestruzzo.

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

Restituiremo un handle a una struttura allocata all’interno della libreria. Una volta creato il nostro contenitore, abbiamo bisogno di popolare i valori e chiamare reset su di esso. Prima di tornare da init, ci assicuriamo che il contenitore buffer sia stato creato in uno stato vuoto.

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

Lo scopo della funzione di reset è quello di mettere il buffer in un “vuoto” dello stato, che richiede l’aggiornamento headtail e full:

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

Poiché abbiamo un metodo per creare un contenitore buffer circolare, abbiamo bisogno di un metodo equivalente per distruggere il contenitore. In questo caso, chiamiamo free sul nostro contenitore. Non tentiamo di liberare il buffer sottostante, poiché non lo possediamo.

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

Controlli di stato

Successivamente, implementeremo le funzioni relative allo stato del contenitore buffer.

La funzione completa è la più semplice da implementare, poiché abbiamo un flag che rappresenta lo stato:

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

Dal momento che abbiamo il full bandiera di distinguere tra pieni e vuoti, di stato, uniamo la bandiera con un controllo che il head == tail:

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

La capacità del nostro buffer fornito durante l’inizializzazione, così abbiamo appena di ritorno che il valore per l’utente:

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

Calcolare il numero di elementi nel buffer è un problema più complicato di quanto mi aspettassi. Molti calcoli di dimensione proposti usano modulo, ma mi sono imbattuto in strani casi d’angolo durante il test. Ho optato per un calcolo semplificato utilizzando istruzioni condizionali.

Se il buffer è pieno, sappiamo che la nostra capacità è al massimo. Se headè maggiore o uguale atail, sottraiamo semplicemente i due valori per ottenere la nostra dimensione. Se tailè maggiore dihead, dobbiamo compensare la differenza conmax per ottenere la dimensione corretta.

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

Aggiunta e rimozione di dati

Con le funzioni di contabilità fuori mano, è il momento di scavare nella carne: aggiunta e rimozione di dati dalla coda.

Aggiungere e rimuovere dati da un buffer circolare richiede la manipolazione dei puntatorihead etail. Quando si aggiungono dati al buffer, inseriamo il nuovo valore nella posizione corrente head, quindi avanziamohead. Quando rimuoviamo i dati dal buffer, recuperiamo il valore del puntatore tail corrente e quindi avanziamotail.

L’aggiunta di dati al buffer richiede tuttavia un po ‘ più di riflessione. Se il buffer è full, abbiamo bisogno di avanzare il nostro tailpuntatore così come head. Dobbiamo anche verificare se l’inserimento di un valore attiva la condizione full.

Implementeremo due versioni della funzioneput, quindi estraiamo la nostra logica di avanzamento del puntatore in una funzione di supporto. Se il nostro buffer è già pieno, avanziamo tail. Avanziamo sempre head di uno. Dopo che il puntatore è stato avanzato, popoliamo il flagfull controllando sehead == tail.

Si noti l’uso dell’operatore modulo (%) di seguito. Modulo farà sì che i valori head e tail vengano reimpostati su 0 quando viene raggiunta la dimensione massima. Ciò garantisce che head e tail siano sempre indici validi del buffer di dati sottostante.

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

Come Miro Samek ha utilmente sottolineato, questa è un’operazione computazionale costosa. Invece, possiamo usare la logica condizionale per ridurre il numero totale di istruzioni. L’approccio consigliato da Miro è:

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

Ora, advance_pointer sarà simile a questo:

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

Possiamo creare una funzione di supporto simile che viene chiamata quando si rimuove un valore dal buffer. Quando rimuoviamo un valore, il flagfull è impostato sufalse e il puntatore della coda è avanzato.

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

Creeremo due versioni della funzione put. La prima versione inserisce un valore nel buffer e avanza il puntatore. Se il buffer è pieno, il valore più vecchio verrà sovrascritto. Questo è il caso d’uso standard per un buffer circolare

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

La seconda versione della funzione put restituisce un errore se il buffer è pieno. Questo è fornito a scopo dimostrativo, ma non usiamo questa variante nei nostri sistemi.

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

Per rimuovere i dati dal buffer, accediamo al valore altaile quindi aggiornare iltail puntatore. Se il buffer è vuoto non restituiamo un valore o modifichiamo il puntatore. Invece, restituiamo un errore all’utente.

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

Che completa l’implementazione della nostra libreria buffer circolare.

Utilizzo

Quando si utilizza la libreria, il cliente è responsabile per la creazione di dati sottostanti buffer circular_buf_init e un cbuf_handle_t viene restituito:

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

Questa maniglia è utilizzato per interagire con tutte le restanti funzioni di libreria:

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

non dimenticare di connessione entrambi i dati sottostanti buffer e il contenitore quando si è fatto:

free(buffer);circular_buf_free(cbuf);

Un programma di test che utilizza la libreria buffer circolare può essere trovato nel repository embedded-resources.

le Modifiche per la Rimozione completa bandiera

Se si ha voluto abbandonare il full bandiera, si dovrebbe invece controllare che il head è una posizione dietro la coda per determinare se il buffer è pieno:

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

Ora, se si voleva evitare l’operazione modulo, siamo in grado di utilizzare la logica condizionale invece:

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

La custodia vuota allora head e tail sono le stesse:

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

Quando la ricezione dei dati dal buffer, possiamo avanzare l’indicatore della coda, avvolgendo intorno, se necessario:

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

Quando si aggiungono dati al buffer, siamo in grado di immagazzinare i dati e anticipo la testa puntatore, avvolgendo intorno, se necessario:

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

riferimenti full può essere eliminato.

C++

C++ si presta a un’implementazione del buffer circolare più pulita rispetto a C.

Definizione della classe

Inizieremo definendo la nostra classe C++. Vogliamo che la nostra implementazione C++ supporti qualsiasi tipo di dati, quindi la renderemo una classe basata su modelli.

Le nostre API saranno simili all’implementazione C. La nostra classe fornirà interfacce per:

• Il buffer a vuoto
• Aggiunta di dati
• Rimozione di dati
• Controllo pieno/vuoto di stato
• verificare l’attuale numero di elementi nel buffer
• Controllo totale della capacità del buffer

Ci sarà anche utilizzare C++ puntatori intelligenti per garantire sicuri di non lasciare eventuali dati una volta che il buffer è distrutto. Ciò significa che possiamo gestire il buffer per l’utente.

Un altro vantaggio di C++ è la banalità di rendere questa classe thread-safe: possiamo fare affidamento sul tipostd::mutex (supponendo che questo sia definito per la tua piattaforma).

Ecco la nostra definizione di classe:

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

Implementazione C++

Il nostro buffer circolare C++ imita gran parte della logica dell’implementazione C, ma si traduce in un design molto più pulito e riutilizzabile. Inoltre, il buffer C++ utilizza std::mutex per fornire un’implementazione thread-safe.

Nota: le stesse modifiche logiche possono essere apportate nell’implementazione C++ per supportare la sicurezza dei thread con un singolo produttore e consumatore “sprecando” uno slot. Vedere le modifiche nell’implementazione C per ulteriori informazioni.

Inizializzazione

Quando si costruisce la nostra classe, allochiamo i dati per il nostro buffer sottostante e impostiamo la dimensione del buffer. Questo rimuove il sovraccarico richiesto con l’implementazione C.

A differenza dell’implementazione C, il costruttore C++ non chiamareset. Poiché specifichiamo i valori iniziali per le nostre variabili membro, il nostro buffer circolare inizia nello stato corretto.

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

Il nostro comportamento di reset riporta il buffer a uno stato vuoto (head == tail && !full_).

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

Stato Tracking

La logica del empty e full casi è lo stesso come il C esempio:

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

In C++ buffer circolare di attuazione, size e capacity relazione il numero di elementi nella coda, piuttosto che la dimensione in byte. Questo ci permette di essere agnostici ai dettagli sottostanti del tipo.

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

Aggiunta di dati

La logica per put corrisponde all’implementazione C. Questa implementazione utilizza il modello comportamentale “sovrascrivi il valore più vecchio”.

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

Nota: per semplicità, ho lasciato fuori l’opzione che evita le operazioni modulo. Puoi trovare quella logica nella sezione C.

Recupero dei dati

La logica dietro get corrisponde all’implementazione C. A differenza dell’implementazione C, viene restituito un valore vuoto se il buffer è vuoto.

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

Nota: return T() restituirà un valore costruito predefinito per un determinato tipo. Il valore effettivo prodotto dipende dal tipo o dal costruttore. Inoltre, per semplicità, ho lasciato fuori l’opzione che evita le operazioni modulo. Puoi trovare quella logica nella sezione C.

Utilizzo

Il buffer circolare C++ è molto più semplice da usare rispetto all’implementazione C.

Per istanziare un buffer circolare, dichiariamo semplicemente un oggetto e specifichiamo il tipo di modello per il nostro buffer. Ecco un esempio utilizzando un buffer di 10uint32_t voci:

circular_buffer<uint32_t> circle(10);

Aggiungere dati è facile:

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

E ottenere dati è altrettanto facile:

x = circle.get()

Ricorda che poiché questa è una classe basata su modelli, puoi creare un buffer circolare di qualsiasi tipo di cui hai bisogno.

Aggiornamenti per C++17

In C++17, abbiamo accesso astd::optional, che ci consente di rappresentare un valore che può o non può essere presente. La nostra funzione get restituirebbe un std::optional<T>. Restituiremmo anchestd::nullopt invece di unT costruito di default se la coda è vuota.

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

Nota: Per semplicità, ho lasciato fuori l’opzione che evita le operazioni modulo. Puoi trovare quella logica nella sezione C.

Nel codice chiamante, è possibile verificare un valore valido utilizzando l’operatore booleano o la funzione membrohas_value. Se è presente un valore valido, è possibile accedervi utilizzando gli operatori-> o*, ur utilizzando la funzione membrovalue().

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

Mettere tutto insieme

Le implementazioni di esempio possono essere trovate nel repository Github embedded-resources.

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

Se si sta cercando di estendere questa libreria, un esercizio utile è quello di aggiungere API aggiuntive per consentire agli utenti di aggiungere / rimuovere più elementi con una singola operazione. È inoltre possibile rendere l’implementazione C thread-safe.

Sicurezza dei thread con il metodo Lookahead

Un approccio per la sicurezza dei thread senza un mutex è il metodo “lookahead”. Questo metodo supporta un singolo thread produttore e un singolo thread consumatore; più produttori o consumatori richiederanno un blocco.

Invece di usare il flag booleano per distinguere tra i casi pieni e vuoti, lasceremo sempre una cella vuota. Utilizzando una singola cella vuota per rilevare il caso “completo”, possiamo supportare un singolo produttore e un singolo consumatore senza un blocco (purché put e get non modifichino le stesse variabili).

Potresti essere preoccupato di sprecare uno slot, ma questo compromesso è spesso molto più economico del costo dell’utilizzo di una primitiva di blocco del sistema operativo.

bibliografia

• C++ Puntatori Intelligenti
• Fosso il Vostro C-Porcile Puntatori di Puntatori Intelligenti

Qui ci sono altri buffer circolare implementazioni:

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

Per ulteriori informazioni sul buffer circolare:

• Embedded.com: Ring buffer nozioni di base
• Wikipedia: buffer Circolare
• Ferrosi Sistemi: Lock Free Ring Buffer
• aumenta il Buffer Circolare
• C++: Prestazioni di un buffer circolare rispetto a Vector, Deque e List
• Lock-Free Single-Producer-Single Consumer Circular Queue

Esiste una proposta per aggiungere un tipo di buffer circolare alla libreria standard C++:

• P0059: Una Proposta per Aggiungere il Anello di estensione della Libreria Standard
  • Anello Span
  • Anello Span Lite

Change Log

• 20210321
  • Risolto un errore con il max_size_ dove cbuf->max sarebbe stato usato
  • Aggiunto il chiarimento di testo riguardanti il motivo per cui il buffer è passato dall’utente
• 20210301
  • Rivolto feedback da Miro in materia di evitare le operazioni modulo
• 20210213
  • Aggiunta di ulteriori collegamenti
  • Aggiunto un’ulteriore discussione sulla compromesso tra full flag vs utilizzando un “sprecato” slot
  • Mostra le modifiche per la sicurezza dei thread con un unico produttore/consumatore
  • Aggiungi note std::optional usare con C++17
• 20191016
  • Modifica Aggiornata dei file di Registro di formattazione per la coerenza tra il sito
  • Abbassato le intestazioni per la coerenza tra il sito
  • Fisso rotto Sommario collegamenti
  • Rimosso Cambiare Registro dal Sommario
• 20190627
  • Aggiunto il link di metalli Ferrosi, Sistemi di’ Lock Free Ring Buffer articolo.
• 20190604
  • Risolto un errore di battitura (grazie Chris Svec!) e cambiato alcune parole relative al tipo opaco.
• 20181219
  • Aggiunta nota sull’evitare problemi di concorrenza con un singolo produttore e un singolo consumatore utilizzando uno slot vuoto.
• 20180804
  • L’articolo è stato ristrutturato e riscritto.Grazie a tutti coloro che hanno fornito feedback lungo la strada. Gli esempi sono stati aggiornati a:
  • Rimuovi la programmazione difensiva
  • Usa asserzioni
  • Crea una libreria autonoma usando una struttura opaca
  • Espandi le API, incluso un calcolo per la dimensione del buffer circolare corrente
  • Aggiorna la libreria in modo che non sprechi uno slot