Aktualisiert: 20210321

Aufgrund der Ressourcenbeschränkung eingebetteter Systeme finden sich in den meisten Projekten Datenstrukturen für kreisförmige Puffer.

Kreisförmige Puffer (auch als Ringpuffer bezeichnet) sind Puffer fester Größe, die so funktionieren, als ob der Speicher zusammenhängend wäre & kreisförmiger Natur. Wenn Speicher generiert und verbraucht wird, müssen die Daten nicht neu gemischt werden, sondern die Head / Tail–Zeiger werden angepasst. Wenn Daten hinzugefügt werden, rückt der Kopfzeiger vor. Wenn Daten verbraucht werden, wird der Endzeiger vorgerückt. Wenn Sie das Ende des Puffers erreichen, werden die Zeiger einfach an den Anfang gewickelt.

Eine detailliertere Zusammenfassung der zirkulären Pufferoperation finden Sie im Wikipedia-Artikel. Der Rest des Artikels setzt voraus, dass Sie wissen, wie zirkuläre Puffer funktionieren.

Inhaltsverzeichnis:

1. Warum einen zirkulären Puffer verwenden?
2. C-Implementierung
   1. Kapselung verwenden
   2. API-Design
   3. Bestimmen, ob ein Puffer voll ist
   4. Typ des kreisförmigen Puffercontainers
   5. Implementierung
   6. Verwendung
   7. Änderungen zum Entfernen des full Flags
3. C++ -Implementierung
   1. Klassendefinition
   2. Implementierung
   3. Verwendung
   4. Updates für C ++ 17
4. Alles zusammenstellen
5. Weiterführende Literatur

Warum einen kreisförmigen Puffer verwenden?

Kreisförmige Puffer werden häufig als Warteschlangen mit fester Größe verwendet. Die feste Größe ist für eingebettete Systeme von Vorteil, da Entwickler häufig versuchen, statische Datenspeichermethoden anstelle dynamischer Zuordnungen zu verwenden.

Zirkuläre Puffer sind auch nützliche Strukturen für Situationen, in denen Datenproduktion und -verbrauch unterschiedlich schnell ablaufen: Die neuesten Daten sind immer verfügbar. Wenn der Verbraucher nicht mit der Produktion Schritt halten kann, werden die veralteten Daten mit neueren Daten überschrieben. Durch die Verwendung eines kreisförmigen Puffers können wir sicherstellen, dass wir immer die neuesten Daten verbrauchen.

Weitere Anwendungsfälle finden Sie unter Ring Buffer Basics auf Embedded.com.

C-Implementierung

Wir werden mit einer C-Implementierung beginnen, da dies uns einigen Designherausforderungen und Kompromissen beim Erstellen einer zirkulären Pufferbibliothek aussetzt.

Kapselung verwenden

Da wir eine zirkuläre Pufferbibliothek erstellen, möchten wir sicherstellen, dass Benutzer mit unseren Bibliotheks-APIs arbeiten, anstatt die Struktur direkt zu ändern. Wir möchten auch, dass die Implementierung in unserer Bibliothek enthalten bleibt, damit wir sie nach Bedarf ändern können, ohne dass Endbenutzer ihren Code aktualisieren müssen. Der Benutzer muss keine Details über unsere Struktur wissen, nur dass sie existiert.

In unserem Bibliotheks-Headerdeklarieren wir dann die Struktur:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

Wir möchten nicht, dass Benutzer direkt mit einem circular_but_t Zeiger arbeiten, da sie den Eindruck haben könnten, dass sie den Wert dereferenzieren können. Wir erstellen einen Handle-Typ, den sie stattdessen verwenden können.

Der einfachste Ansatz für unser Handle ist typedef die cbuf_handle_t als Zeiger auf den kreisförmigen Puffer. Dies verhindert, dass wir den Zeiger innerhalb unserer Funktionsimplementierung umwandeln müssen.

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

Ein alternativer Ansatz wäre, das Handle zu einem uintptr_t oder void* Wert zu machen. Innerhalb unserer Schnittstelle würden wir die Übersetzung in den entsprechenden Zeigertyp übernehmen. Wir halten den kreisförmigen Puffertyp für Benutzer verborgen, und die einzige Möglichkeit, mit den Daten zu interagieren, ist über das Handle.

Wir bleiben bei der simple Handle-Implementierung, um unseren Beispielcode einfach und unkompliziert zu halten.

API-Design

Zunächst sollten wir darüber nachdenken, wie Benutzer mit einem kreisförmigen Puffer interagieren:

• Sie müssen den kreisförmigen Puffercontainer mit einem Puffer und einer Größe initialisieren
• Sie müssen einen kreisförmigen Puffercontainer zerstören
• Sie müssen den kreisförmigen Puffercontainer zurücksetzen
• Sie müssen in der Lage sein, dem Puffer Daten hinzuzufügen
• Sie müssen in der Lage sein, den nächsten Wert aus dem Puffer abzurufen
• Sie müssen wissen, ob der Puffer voll oder leer ist
• Sie müssen die aktuelle Anzahl der Elemente im Puffer
• müssen sie die maximale Kapazität des Puffers kennen

Anhand dieser Liste können wir eine API für unsere Bibliothek zusammenstellen. Benutzer interagieren mit der zirkulären Pufferbibliothek mithilfe unseres undurchsichtigen Handle-Typs, der während der Initialisierung erstellt wird.

Ich habe uint8_t als zugrunde liegenden Datentyp in dieser Implementierung ausgewählt. Sie können einen bestimmten Typ verwenden, den Sie mögen – achten Sie nur darauf, den zugrunde liegenden Puffer und die Anzahl der Bytes entsprechend zu behandeln.

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

Bestimmen, ob ein Puffer voll ist

Bevor wir fortfahren, sollten wir uns einen Moment Zeit nehmen, um die Methode zu besprechen, mit der wir feststellen, ob ein Puffer voll oder leer ist.

Sowohl die „vollen“ als auch die „leeren“ Fälle des kreisförmigen Puffers sehen gleich aus: head und tail Zeiger sind gleich. Es gibt zwei Ansätze, um zwischen voll und leer zu unterscheiden:

1. „Verschwenden“ Sie einen Steckplatz im Puffer:
   • Voller Zustand ist head + 1 == tail
   • Leerer Zustand ist head == tail
2. Verwenden Sie eine bool flag und zusätzliche Logik zur Unterscheidung von Zuständen::
   • Vollständiger Zustand ist full
   • Leerer Zustand ist (head == tail) && !full

Wir sollten auch die Thread-Sicherheit berücksichtigen. Indem wir eine einzelne leere Zelle verwenden, um den „vollen“ Fall zu erkennen, können wir einen einzelnen Produzenten und einen einzelnen Verbraucher ohne Sperre unterstützen (solange put und get nicht die gleichen Variablen ändern). Die Warteschlange ist threadsicher, da der Producer nur den head Index ändert und der Consumer nur den tail Index . Obwohl jeder Index in einem bestimmten Kontext möglicherweise etwas veraltet ist, wirkt sich dies nicht auf die Thread-Sicherheit der Warteschlange aus. Die Verwendung des full Flags führt jedoch zu einer Anforderung für den gegenseitigen Ausschluss. Dies liegt daran, dass das Flag full sowohl vom Produzenten als auch vom Konsumenten gemeinsam genutzt wird.

Natürlich hat die Entscheidung ihre Nachteile. Wenn Ihr Pufferelement einen großen Speicherbedarf hat (z. B. einen Puffer mit der Größe eines Kamera-I-Frames), ist die Verschwendung eines Steckplatzes auf Ihrem System möglicherweise nicht sinnvoll. Wenn mehrere Produzenten / Konsumenten mit einer Warteschlange interagieren, benötigen Sie sowieso eine Sperre, sodass es keinen Sinn macht, einen Slot zu verschwenden. Wenn Sie keinen gegenseitigen Ausschluss zur Verfügung haben (z. B. weil Sie kein Betriebssystem verwenden), aber Interrupts verwenden, sollten Sie die Nicht-full Flag-Version verwenden. Das auf Ihrem System verwendete Speichermodell kann sich auch auf Ihre Entscheidung auswirken, auf eine Sperre zu verzichten.

Die folgende Implementierung verwendet das bool Flag. Die Verwendung des Flags erfordert zusätzliche Logik in den Routinen get und put, um das Flag zu aktualisieren. Ich werde auch beschreiben, wie die Änderungen für einen einzelnen Produzenten / Konsumenten vorgenommen werden, der das full Flag nicht verwendet.

Typ des kreisförmigen Puffercontainers

Nachdem wir nun die Operationen verstanden haben, die wir unterstützen müssen, können wir unseren kreisförmigen Puffercontainer entwerfen.

Wir verwenden die Containerstruktur, um den Zustand des Puffers zu verwalten. Um die Kapselung zu erhalten, wird die Containerstruktur in unserer Bibliotheksdatei .c und nicht im Header definiert.

Wir müssen Folgendes im Auge behalten:

• Der zugrunde liegende Datenpuffer
• Die maximale Größe des Puffers
• Die aktuelle „Kopf“ -Position (erhöht, wenn Elemente hinzugefügt werden)
• Der aktuelle „Schwanz“ (erhöht, wenn Elemente entfernt werden)
• Ein Flag, das angibt, ob der Puffer voll ist oder nicht

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

Nachdem unser Container entworfen wurde, können wir die Bibliotheksfunktionen implementieren.

Implementierung

Ein wichtiges Detail ist, dass jede unserer APIs ein initialisiertes Puffer-Handle benötigt. Anstatt unseren Code mit bedingten Anweisungen zu verunreinigen, werden wir Assertions verwenden, um unsere API-Anforderungen im Stil „Design by Contract“ durchzusetzen.

Wenn die Schnittstellen nicht ordnungsgemäß verwendet werden, schlägt das Programm sofort fehl, anstatt dass der Benutzer den Fehlercode überprüfen und behandeln muss.

Zum Beispiel:

circular_buf_reset(NULL);

Erzeugt:

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

Ein weiterer wichtiger Hinweis ist, dass die unten gezeigte Implementierung nicht threadsicher ist. Der zugrunde liegenden zirkulären Pufferbibliothek wurden keine Sperren hinzugefügt.

Initialisieren und Zurücksetzen

Beginnen wir am Anfang: Initialisieren eines kreisförmigen Puffers. In unserer API stellen Clients den zugrunde liegenden Puffer und die Puffergröße bereit, und wir geben ihnen ein kreisförmiges Pufferhandle zurück. Der Grund, warum wir möchten, dass unsere Benutzer den Puffer bereitstellen, ist, dass dies einen statisch zugewiesenen Puffer ermöglicht. Wenn unsere API den Puffer unter der Haube erstellen würde, müssten wir die dynamische Speicherzuweisung verwenden, die in Programmen für eingebettete Systeme häufig nicht zulässig ist.

Wir müssen eine zirkuläre Pufferstrukturinstanz innerhalb der Bibliothek bereitstellen, damit wir einen Zeiger an den Benutzer zurückgeben können. Ich habe der Einfachheit halber malloc verwendet. Systeme, die keinen dynamischen Speicher verwenden können, müssen lediglich die Funktion init ändern, um eine andere Methode zu verwenden, z. B. die Zuweisung aus einem statischen Pool vorab zugewiesener zirkulärer Pufferstrukturen.

Ein anderer Ansatz wäre, die Kapselung zu unterbrechen, sodass Benutzer kreisförmige Puffercontainerstrukturen außerhalb der Bibliothek statisch deklarieren können. In diesem Fall muss circular_buf_init aktualisiert werden, um einen Strukturzeiger zu erhalten. Wir könnten auch unsere init -Funktion eine Containerstruktur auf dem Stapel erstellen und zurückgeben. Da die Kapselung jedoch unterbrochen ist, können Benutzer die Struktur ändern, ohne die Bibliotheksroutinen zu verwenden. Wenn Sie die Kapselung beibehalten möchten, müssen Sie mit Zeigern anstelle von konkreten Strukturinstanzen arbeiten.

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

Wir geben ein Handle an eine Struktur zurück, die innerhalb der Bibliothek zugewiesen ist. Sobald wir unseren Container erstellt haben, müssen wir die Werte auffüllen und reset aufrufen. Bevor wir von init , stellen wir sicher, dass der Puffercontainer in einem leeren Zustand erstellt wurde.

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

Der Zweck der Reset-Funktion besteht darin, den Puffer in einen „leeren“ Zustand zu versetzen, der eine Aktualisierung erfordert headtail und full:

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

Da wir eine Methode zum Erstellen eines kreisförmigen Puffercontainers haben, benötigen wir eine äquivalente Methode zum Zerstören des Containers. In diesem Fall rufen wir free in unserem Container auf. Wir versuchen nicht, den zugrunde liegenden Puffer freizugeben, da wir ihn nicht besitzen.

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

Statusüberprüfungen

Als nächstes implementieren wir die Funktionen, die sich auf den Status des Puffercontainers beziehen.

Die vollständige Funktion ist am einfachsten zu implementieren, da wir ein Flag haben, das den Status darstellt:

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

Da wir das full Flag haben, um zwischen vollem oder leerem Zustand zu unterscheiden, kombinieren wir das Flag mit einer Überprüfung, dass head == tail:

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

Die Kapazität unseres Puffers wurde während initialisierung, also geben wir diesen Wert einfach an den Benutzer zurück:

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

Die Berechnung der Anzahl der Elemente im Puffer war ein schwierigeres Problem als erwartet. Viele vorgeschlagene Größenberechnungen verwenden Modulo, aber ich bin beim Testen auf seltsame Eckfälle gestoßen. Ich habe mich für eine vereinfachte Berechnung mit bedingten Anweisungen entschieden.

Wenn der Puffer voll ist, wissen wir, dass unsere Kapazität maximal ist. Wenn head größer oder gleich tail ist, subtrahieren wir einfach die beiden Werte, um unsere Größe zu erhalten. Wenn tail größer als head ist, müssen wir die Differenz mit max , um die richtige Größe zu erhalten.

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

Hinzufügen und Entfernen von Daten

Mit den Buchhaltungsfunktionen aus dem Weg, ist es Zeit, in das Fleisch zu graben: Hinzufügen und Entfernen von Daten aus der Warteschlange.

Das Hinzufügen und Entfernen von Daten aus einem kreisförmigen Puffer erfordert die Manipulation der head und tail Zeiger. Wenn wir Daten zum Puffer hinzufügen, fügen wir den neuen Wert an der aktuellen head Position ein, dann gehen wir vor head. Wenn wir Daten aus dem Puffer entfernen, rufen wir den Wert des aktuellen tail Zeigers ab und fahren dann tail .

Das Hinzufügen von Daten zum Puffer erfordert jedoch etwas mehr Nachdenken. Wenn der Puffer full ist, müssen wir unseren tail Zeiger sowie head . Wir müssen auch überprüfen, ob das Einfügen eines Werts die Bedingung full auslöst.

Wir werden zwei Versionen der put -Funktion implementieren. Wenn unser Puffer bereits voll ist, gehen wir tail . Wir bringen head immer um eins voran. Nachdem der Zeiger fortgeschritten ist, füllen wir das Flag full , indem wir prüfen, ob head == tail .

Beachten Sie die Verwendung des Modulo-Operators (%) unten. Modulo bewirkt, dass die Werte head und tail auf 0 zurückgesetzt werden, wenn die maximale Größe erreicht ist. Dadurch wird sichergestellt, dass head und tail immer gültige Indizes des zugrunde liegenden Datenpuffers sind.

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

Wie Miro Samek hilfreich betonte, ist dies eine teure Rechenoperation. Stattdessen können wir bedingte Logik verwenden, um die Gesamtzahl der Anweisungen zu reduzieren. Miros empfohlener Ansatz ist:

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

Nun wird advance_pointer so aussehen:

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

Wir können eine ähnliche Hilfsfunktion erstellen, die aufgerufen wird, wenn ein Wert aus dem Puffer entfernt wird. Wenn wir einen Wert entfernen, wird das Flag full auf false gesetzt und der Endzeiger wird erweitert.

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

Wir werden zwei Versionen der put Funktion erstellen. Die erste Version fügt einen Wert in den Puffer ein und rückt den Zeiger vor. Wenn der Puffer voll ist, wird der älteste Wert überschrieben. Dies ist der Standard-Anwendungsfall für einen kreisförmigen Puffer

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

Die zweite Version der put Funktion gibt einen Fehler zurück, wenn der Puffer voll ist. Dies wird zu Demonstrationszwecken bereitgestellt, wir verwenden diese Variante jedoch nicht in unseren Systemen.

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

Um Daten aus dem Puffer zu entfernen, greifen wir auf den Wert am tail zu und aktualisieren dann den tail Zeiger. Wenn der Puffer leer ist, geben wir keinen Wert zurück oder ändern den Zeiger. Stattdessen geben wir einen Fehler an den Benutzer zurück.

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

Damit ist die Implementierung unserer zirkulären Pufferbibliothek abgeschlossen.

Verwendung

Bei Verwendung der Bibliothek ist der Client für die Erstellung des zugrunde liegenden Datenpuffers für circular_buf_init verantwortlich, und es wird ein cbuf_handle_t zurückgegeben:

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

Dieses Handle wird verwendet, um mit allen verbleibenden Bibliotheksfunktionen zu interagieren:

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

Vergessen Sie nicht, sowohl den zugrunde liegenden Datenpuffer als auch den Container freizugeben, wenn Sie fertig sind:

free(buffer);circular_buf_free(cbuf);

Ein Testprogramm, das die circular buffer Library verwendet, finden Sie im embedded-resources Repository.

Modifikationen zum Entfernen des vollständigen Flags

Wenn Sie das full Flag entfernen möchten, überprüfen Sie stattdessen, ob das head eine Position hinter dem Schwanz ist, um festzustellen, ob der Puffer voll ist:

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

Wenn wir nun vermeiden Sie die Modulo-Operation, wir können stattdessen bedingte Logik verwenden:

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

Der leere Fall ist dann, dass head und tail gleich sind:

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

Wenn wir Daten aus dem Puffer erhalten, werden wir den Endzeiger voranbringen und ihn bei Bedarf umwickeln:

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

Wenn wir Daten zum Puffer hinzufügen, werden wir die Daten speichern und den Kopfzeiger voranbringen, wenn nötig:

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

Andere Verweise auf full können eliminiert werden.

C++

C++ eignet sich für eine sauberere zirkuläre Pufferimplementierung als C.

Klassendefinition

Wir beginnen mit der Definition unserer C ++ – Klasse. Wir möchten, dass unsere C ++ – Implementierung jede Art von Daten unterstützt, daher werden wir sie zu einer Vorlagenklasse machen.

Unsere APIs werden der C-Implementierung ähnlich sein. Unsere Klasse bietet Schnittstellen für:

• Zurücksetzen des Puffers auf leer
• Hinzufügen von Daten
• Entfernen von Daten
• Überprüfen des vollständigen / leeren Zustands
• Überprüfen der aktuellen Anzahl von Elementen im Puffer
• Überprüfen der Gesamtkapazität des Puffers

Wir werden auch C ++ Smart Pointer verwenden, um sicherzustellen, dass wir keine Daten hinterlassen, sobald unser Puffer zerstört ist. Dies bedeutet, dass wir den Puffer für den Benutzer verwalten können.

Ein weiterer Vorteil von C ++ ist die Trivialität, diese Klasse threadsicher zu machen: Wir können uns auf den std::mutex Typ verlassen (vorausgesetzt, dies ist für Ihre Plattform definiert).

Hier ist unsere Klassendefinition:

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

Unser C ++ – Kreispuffer ahmt einen Großteil der Logik der C-Implementierung nach, führt jedoch zu einem viel saubereren und wiederverwendbareren Design. Außerdem verwendet der C ++ – Puffer std::mutex , um eine threadsichere Implementierung bereitzustellen.

Hinweis: Die gleichen logischen Änderungen können in der C ++ – Implementierung vorgenommen werden, um die Thread-Sicherheit mit einem einzelnen Producer und Consumer zu unterstützen, indem ein Slot „verschwendet“ wird. Weitere Informationen finden Sie in den Anpassungen in der C-Implementierung.

Initialisierung

Beim Erstellen unserer Klasse weisen wir die Daten für unseren zugrunde liegenden Puffer zu und legen die Puffergröße fest. Dadurch entfällt der für die C-Implementierung erforderliche Overhead.

Im Gegensatz zur C-Implementierung ruft der C++ – Konstruktor reset nicht auf. Da wir Anfangswerte für unsere Mitgliedsvariablen angeben, beginnt unser zirkulärer Puffer im richtigen Zustand.

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

Unser Reset-Verhalten versetzt den Puffer wieder in einen leeren Zustand (head == tail && !full_).

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

Statusverfolgung

Die Logik der empty und full Fälle ist die gleiche wie im C-Beispiel:

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

Im C-Beispiel ++ zirkuläre Pufferimplementierung, size und capacity geben die Anzahl der Elemente in der Warteschlange und nicht die Größe in Bytes an. Dies ermöglicht es uns, den zugrunde liegenden Details des Typs gegenüber agnostisch zu sein.

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

Daten hinzufügen

Die Logik für put entspricht der C-Implementierung. Diese Implementierung verwendet das Verhaltensmuster „Ältesten Wert überschreiben“.

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

Hinweis: Der Einfachheit halber habe ich die Option weggelassen, die Modulo-Operationen vermeidet. Sie finden diese Logik im Abschnitt C.

Abrufen von Daten

Die Logik hinter get entspricht der C-Implementierung. Im Gegensatz zur C-Implementierung wird ein leerer Wert zurückgegeben, wenn der Puffer leer ist.

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

Hinweis: return T() gibt einen konstruierten Standardwert für den angegebenen Typ zurück. Der tatsächlich erzeugte Wert hängt vom Typ oder vom Konstruktor ab. Der Einfachheit halber habe ich auch die Option ausgelassen, die Modulo-Operationen vermeidet. Sie finden diese Logik im Abschnitt C.

Verwendung

Der C ++ – Kreispuffer ist viel einfacher zu verwenden als die C-Implementierung.

Um einen zirkulären Puffer zu instanziieren, deklarieren wir einfach ein Objekt und geben den Vorlagentyp für unseren Puffer an. Hier ist ein Beispiel mit einem Puffer von 10 uint32_t Einträgen:

circular_buffer<uint32_t> circle(10);

Das Hinzufügen von Daten ist einfach:

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

Und das Abrufen von Daten ist ebenso einfach:

x = circle.get()

Denken Sie daran, dass Sie, da dies eine Vorlagenklasse ist, einen kreisförmigen Puffer jedes Typs erstellen können, den Sie benötigen.

Updates für C ++ 17

In C++17 haben wir Zugriff auf std::optional , wodurch wir einen Wert darstellen können, der vorhanden sein kann oder nicht. Unsere get Funktion würde eine std::optional<T> . Wir würden auch std::nullopt anstelle eines standardmäßig erstellten T wenn die Warteschlange leer ist.

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

Hinweis: Der Einfachheit halber habe ich die Option weggelassen, die Modulo-Operationen vermeidet. Sie finden diese Logik im Abschnitt C.

Im aufrufenden Code können Sie mit dem Booleschen Operator oder der has_value Memberfunktion nach einem gültigen Wert suchen. Wenn ein gültiger Wert vorhanden ist, kann mit den Operatoren -> oder * oder mit der Memberfunktion value() darauf zugegriffen werden.

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

Alles zusammenfassen

Beispielimplementierungen finden Sie im embedded-resources Github-Repository.

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

Wenn Sie diese Bibliothek erweitern möchten, können Sie zusätzliche APIs hinzufügen, damit Benutzer mehrere Elemente mit einem einzigen Vorgang hinzufügen / entfernen können. Sie können die C-Implementierung auch threadsicher machen.

Thread-Sicherheit mit der Lookahead-Methode

Ein Ansatz für Thread-Sicherheit ohne Mutex ist die „Lookahead“-Methode. Diese Methode unterstützt einen einzelnen Producer-Thread und einen einzelnen Consumer-Thread; mehrere Hersteller oder Verbraucher benötigen eine Sperre.

Anstatt das boolesche Flag zu verwenden, um zwischen den vollen und leeren Fällen zu unterscheiden, lassen wir immer eine Zelle leer. Indem wir eine einzelne leere Zelle verwenden, um den „vollen“ Fall zu erkennen, können wir einen einzelnen Produzenten und einen einzelnen Verbraucher ohne Sperre unterstützen (solange put und get nicht die gleichen Variablen ändern).

Sie könnten besorgt sein, einen Slot zu verschwenden, aber dieser Kompromiss ist oft viel billiger als die Kosten für die Verwendung eines OS-Lock-Primitivs.

Weiterführende Literatur

• C ++ Smart Pointer
• Lassen Sie Ihre C-Stye-Zeiger für Smart Pointer fallen

Hier sind andere Implementierungen von zirkulären Puffern:

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

Weitere Informationen zu zirkulären Puffern:

Embedded.com : Ringpuffer Grundlagen
• Wikipedia: Kreispuffer
• Betriebssysteme: Lock Free Ringpuffer
• Boost-Kreispuffer
• C ++: Leistung eines kreisförmigen Puffers im Vergleich zu Vektor, Deque und Liste
• Lock-Free Single-Producer – Single Consumer Circular Queue

Es gibt einen Vorschlag, der C ++ – Standardbibliothek einen kreisförmigen Puffertyp hinzuzufügen:

• P0059: Ein Vorschlag, Ring Span zur Standardbibliothek hinzuzufügen
  • Ring Span
  • Ring Span Lite

Änderungsprotokoll

• 20210321
  • Fehler behoben mit max_size_ wobei cbuf->max hätte verwendet werden sollen
  • Klärender Text hinzugefügt, warum der Puffer vom Benutzer übergeben wird
• 20210301
  • Adressiertes Feedback von Miro zur Vermeidung von Modulo-Operationen
• 20210213
  • Zusätzliche Links hinzugefügt
  • Weitere Diskussion über den Kompromiss zwischen vollem Flag und der Verwendung eines „verschwendeten“ änderungen für Thread-Sicherheit mit einem einzelnen Produzenten / Verbraucher anzeigen
  • Notizen hinzufügen zu std::optional mit C ++ 17 verwenden
• 20191016
  • Formatierung des Änderungsprotokollabschnitts für Konsistenz auf der gesamten Site aktualisiert
  • Herabgestufte Header für Konsistenz auf der gesamten Site
  • Fehlerhafte Inhaltsverzeichnislinks behoben
  • Änderungsprotokoll aus Inhaltsverzeichnis entfernt
• 20190627
  • Link zum Artikel Lock Free Ring Buffer von Microsoft Systems hinzugefügt.
• 20190604
  • Ein Tippfehler wurde behoben (danke Chris Svec!) und einige Formulierungen in Bezug auf den undurchsichtigen Typ geändert.
• 20181219
  • Hinweis zur Vermeidung von Parallelitätsproblemen mit einem einzelnen Produzenten und einem einzelnen Verbraucher unter Verwendung eines leeren Steckplatzes hinzugefügt.
• 20180804
  • Der Artikel wurde umstrukturiert und neu geschrieben.Vielen Dank an alle, die auf dem Weg Feedback gegeben haben. Die Beispiele wurden aktualisiert, um:
  • Defensive Programmierung entfernen
  • Assertionen verwenden
  • Erstellen Sie eine eigenständige Bibliothek mit einer undurchsichtigen Struktur
  • Erweitern Sie die APIs, einschließlich einer Berechnung für die aktuelle kreisförmige Puffergröße
  • Aktualisieren Sie die Bibliothek, damit sie keinen Steckplatz verschwendet hat