Mise à jour: 20210321

En raison de la nature limitée en ressources des systèmes embarqués, des structures de données de tampon circulaires peuvent être trouvées dans la plupart des projets.

Les tampons circulaires (également appelés tampons en anneau) sont des tampons de taille fixe qui fonctionnent comme si la mémoire était contiguë & de nature circulaire. Lorsque la mémoire est générée et consommée, les données n’ont pas besoin d’être remaniées – les pointeurs tête / queue sont plutôt ajustés. Lorsque des données sont ajoutées, le pointeur de tête avance. Lorsque les données sont consommées, le pointeur de queue avance. Si vous atteignez la fin du tampon, les pointeurs s’enroulent simplement vers le début.

Pour un résumé plus détaillé du fonctionnement du tampon circulaire, veuillez vous référer à l’article Wikipedia. Le reste de l’article suppose que vous avez une compréhension du fonctionnement des tampons circulaires.

Table des matières :

1. Pourquoi utiliser un tampon circulaire ?
2. Implémentation C
   1. Utilisation de l’Encapsulation
   2. Conception de l’API
   3. Déterminer si un Tampon est plein
   4. Type de Conteneur Tampon Circulaire
   5. Implémentation
   6. Utilisation
   7. Modifications pour Supprimer l’indicateur full
3. Implémentation C++
   1. Définition de Classe
   2. Implémentation
   3. Utilisation
   4. Mises À Jour pour C++17
4. Mettre Tout Cela Ensemble
5. Lecture Ultérieure

Pourquoi Utiliser Un Tampon Circulaire?

Les tampons circulaires sont souvent utilisés comme files d’attente de taille fixe. La taille fixe est bénéfique pour les systèmes embarqués, car les développeurs essaient souvent d’utiliser des méthodes de stockage de données statiques plutôt que des allocations dynamiques.

Les tampons circulaires sont également des structures utiles pour les situations où la production et la consommation de données se produisent à des rythmes différents: les données les plus récentes sont toujours disponibles. Si le consommateur ne peut pas suivre la production, les données périmées seront remplacées par des données plus récentes. En utilisant un tampon circulaire, nous pouvons nous assurer que nous consommons toujours les données les plus récentes.

Pour des cas d’utilisation supplémentaires, consultez les bases du tampon en anneau sur Embedded.com .

Implémentation C

Nous commencerons par une implémentation C, car cela nous expose à certains des défis de conception et des compromis lors de la création d’une bibliothèque de tampons circulaires.

Utilisation de l’encapsulation

Puisque nous créons une bibliothèque tampon circulaire, nous voulons nous assurer que les utilisateurs travaillent avec nos API de bibliothèque au lieu de modifier directement la structure. Nous voulons également conserver l’implémentation contenue dans notre bibliothèque afin de pouvoir la modifier au besoin, sans obliger les utilisateurs finaux à mettre à jour leur code. L’utilisateur n’a pas besoin de connaître de détails sur notre structure, seulement qu’elle existe.

Dans l’en-tête de notre bibliothèque, nous transmettrons la structure:

// Opaque circular buffer structuretypedef struct circular_buf_t circular_buf_t;

Nous ne voulons pas que les utilisateurs travaillent directement avec un pointeur circular_but_t, car ils pourraient avoir l’impression qu’ils peuvent déréférencer la valeur. Nous allons créer un type de poignée qu’ils pourront utiliser à la place.

L’approche la plus simple pour notre poignée consiste à typedefle cbuf_handle_t comme pointeur vers le tampon circulaire. Cela nous évitera d’avoir à lancer le pointeur dans notre implémentation de fonction.

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

Une autre approche consisterait à faire du handle une valeur uintptr_t ou void*. À l’intérieur de notre interface, nous gérerions la traduction vers le type de pointeur approprié. Nous gardons le type de tampon circulaire caché aux utilisateurs, et la seule façon d’interagir avec les données est via le handle.

Nous allons nous en tenir à l’implémentation de la poignée simple pour garder notre exemple de code simple et direct.

Conception de l’API

Tout d’abord, nous devrions réfléchir à la façon dont les utilisateurs interagiront avec un tampon circulaire:

• Ils doivent initialiser le conteneur tampon circulaire avec un tampon et une taille
• Ils doivent détruire un conteneur tampon circulaire
• Ils doivent réinitialiser le conteneur tampon circulaire
• Ils doivent pouvoir ajouter des données au tampon
• Ils doivent pouvoir obtenir la valeur suivante du tampon
• Ils doivent savoir si le tampon est plein ou vide
• Ils doivent connaître le nombre actuel d’éléments dans le buffer
• Ils ont besoin de connaître la capacité maximale du buffer

En utilisant cette liste, nous pouvons créer une API pour notre bibliothèque. Les utilisateurs interagiront avec la bibliothèque de tampons circulaires à l’aide de notre type de poignée opaque, qui est créé lors de l’initialisation.

J’ai choisi uint8_tcomme type de données sous-jacent dans cette implémentation. Vous pouvez utiliser n’importe quel type particulier que vous aimez – veillez simplement à gérer le tampon sous-jacent et le nombre d’octets de manière appropriée.

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

Déterminer si un tampon est plein

Avant de continuer, nous devrions prendre un moment pour discuter de la méthode que nous utiliserons pour déterminer si le tampon est plein ou vide.

Les cas ”plein » et ”vide » du tampon circulaire se ressemblent tous les deux : le pointeur head et tail sont égaux. Il existe deux approches pour différencier le plein du vide:

1. « Déchets” un emplacement dans le tampon:
   • L’état complet est head + 1 == tail
   • L’état vide est head == tail
2. Utilisez un bool drapeau et logique supplémentaire pour différencier les états::
   • L’état complet est full
   • L’état vide est (head == tail) && !full

Nous devrions également considérer la sécurité des threads. En utilisant une seule cellule vide pour détecter le cas « complet », nous pouvons prendre en charge un seul producteur et un seul consommateur sans verrou (tant que put et get ne modifient pas les mêmes variables). La file d’attente est thread-safe car le producteur ne modifiera que l’index head, et le consommateur ne modifiera que l’index tail. Bien que l’un ou l’autre index puisse être légèrement obsolète dans un contexte donné, cela n’affectera pas la sécurité des threads de la file d’attente. L’utilisation de l’indicateur full crée cependant une exigence d’exclusion mutuelle. En effet, l’indicateur full est partagé par le producteur et le consommateur.

Bien sûr, la décision a ses compromis. Si votre élément tampon a une grande empreinte mémoire (telle qu’une mémoire tampon dimensionnée pour une i-frame de caméra), gaspiller un emplacement peut ne pas être raisonnable sur votre système. Si plusieurs producteurs / consommateurs interagissent avec une file d’attente, vous aurez de toute façon besoin d’un verrou, donc gaspiller une fente n’a pas de sens. Si vous n’avez pas d’exclusion mutuelle disponible (par exemple, parce que vous n’utilisez pas de système d’exploitation) mais que vous utilisez des interruptions, vous voudrez utiliser la version de l’indicateur non full. Le modèle de mémoire utilisé sur votre système peut également avoir un impact sur votre décision de vous passer d’un verrou.

L’implémentation ci-dessous utilise l’indicateur bool. L’utilisation de l’indicateur nécessite une logique supplémentaire dans les routines get et put pour mettre à jour l’indicateur. Je décrirai également comment apporter les modifications pour un seul producteur / consommateur qui n’utilise pas l’indicateur full.

Type de conteneur Tampon circulaire

Maintenant que nous maîtrisons les opérations que nous devrons supporter, nous pouvons concevoir notre conteneur tampon circulaire.

Nous utilisons la structure du conteneur pour gérer l’état du tampon. Pour préserver l’encapsulation, la structure du conteneur est définie à l’intérieur du fichier .c de notre bibliothèque, plutôt que dans l’en-tête.

Nous devrons garder une trace de:

• Le tampon de données sous-jacent
• La taille maximale du tampon
• La position actuelle de la « tête” (incrémentée lorsque des éléments sont ajoutés)
• La « queue” actuelle (incrémentée lorsque des éléments sont supprimés)
• Un indicateur indiquant si le tampon est plein ou 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;};

Maintenant que notre conteneur est conçu, nous sommes prêts à implémenter les fonctions de la bibliothèque.

Implémentation

Un détail important à noter est que chacune de nos API nécessite un handle de tampon initialisé. Plutôt que de jeter notre code avec des instructions conditionnelles, nous utiliserons des assertions pour appliquer nos exigences d’API dans le style « Conception par contrat”.

Si les interfaces sont mal utilisées, le programme échouera immédiatement plutôt que d’obliger l’utilisateur à vérifier et à gérer le code d’erreur.

Par exemple :

circular_buf_reset(NULL);

Produit:

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

Une autre note importante est que l’implémentation montrée ci-dessous n’est pas thread-safe. Aucun verrou n’a été ajouté à la bibliothèque de tampons circulaires sous-jacente.

Initialiser et réinitialiser

Commençons par le début: initialiser un tampon circulaire. Notre API demande aux clients de fournir le tampon sous-jacent et la taille du tampon, et nous leur renvoyons un descripteur de tampon circulaire. La raison pour laquelle nous voulons que nos utilisateurs fournissent le tampon est que cela permet un tampon alloué statiquement. Si notre API créait le tampon sous le capot, nous devions utiliser l’allocation de mémoire dynamique, qui est souvent interdite dans les programmes de systèmes embarqués.

Nous devons fournir une instance de structure de tampon circulaire dans la bibliothèque afin que nous puissions renvoyer un pointeur à l’utilisateur. J’ai utilisé malloc pour plus de simplicité. Les systèmes qui ne peuvent pas utiliser de mémoire dynamique doivent simplement modifier la fonction init pour utiliser une méthode différente, telle que l’allocation à partir d’un pool statique de structures tampons circulaires pré-allouées.

Une autre approche consisterait à casser l’encapsulation, permettant aux utilisateurs de déclarer statiquement des structures de conteneurs tampons circulaires en dehors de la bibliothèque. Dans ce cas, circular_buf_init doit être mis à jour pour prendre un pointeur struct. Nous pourrions également avoir notre fonction init pour créer une structure de conteneur sur la pile et la renvoyer en gros. Cependant, l’encapsulation étant interrompue, les utilisateurs pourront modifier la structure sans utiliser les routines de la bibliothèque. Si vous souhaitez préserver l’encapsulation, vous devez travailler avec des pointeurs au lieu d’instances de structure concrète.

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

Nous allons renvoyer un handle à une structure qui est allouée à l’intérieur de la bibliothèque. Une fois que nous avons créé notre conteneur, nous devons remplir les valeurs et appeler reset dessus. Avant de revenir de init, nous nous assurons que le conteneur tampon a été créé dans un état vide.

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

Le but de la fonction de réinitialisation est de mettre le tampon dans un état « vide”, ce qui nécessite la mise à jour headtail, et full:

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

Comme nous avons une méthode pour créer un conteneur tampon circulaire, nous avons besoin d’une méthode équivalente pour détruire le conteneur. Dans ce cas, nous appelons free sur notre conteneur. Nous n’essayons pas de libérer le tampon sous-jacent, car nous ne le possédons pas.

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

Contrôles d’état

Ensuite, nous allons implémenter les fonctions liées à l’état du conteneur tampon.

La fonction complète est la plus facile à implémenter, car nous avons un drapeau représentant l’état:

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

Étant donné que nous avons l’indicateur full pour différencier l’état plein ou vide, nous combinons l’indicateur avec une vérification que head == tail:

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

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

a capacité de notre tampon a été fournie lors de l’initialisation, nous renvoyons donc simplement cette valeur à l’utilisateur:

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

Le calcul du nombre d’éléments dans le tampon était un problème plus délicat que prévu. De nombreux calculs de taille proposés utilisent modulo, mais j’ai rencontré d’étranges cas de coin lors du test. J’ai opté pour un calcul simplifié à l’aide d’instructions conditionnelles.

Si le tampon est plein, nous savons que notre capacité est au maximum. Si head est supérieur ou égal au tail, nous soustrayons simplement les deux valeurs pour obtenir notre taille. Si tail est supérieur à head, nous devons compenser la différence avec max pour obtenir la bonne taille.

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

Ajout et suppression de données

Avec les fonctions de comptabilité à l’écart, il est temps de creuser dans la viande: ajouter et supprimer des données de la file d’attente.

L’ajout et la suppression de données d’un tampon circulaire nécessitent la manipulation des pointeurs head et tail. Lors de l’ajout de données au tampon, nous insérons la nouvelle valeur à l’emplacement head actuel, puis nous avançons head. Lorsque nous supprimons des données du tampon, nous récupérons la valeur du pointeur tail actuel, puis nous avançons tail.

L’ajout de données au tampon nécessite cependant un peu plus de réflexion. Si le tampon est full, nous devons avancer notre pointeur tail ainsi que head. Nous devons également vérifier si l’insertion d’une valeur déclenche la condition full.

Nous allons implémenter deux versions de la fonction put, alors extrayons notre logique d’avancement du pointeur dans une fonction d’assistance. Si notre tampon est déjà plein, nous avançons tail. Nous avançons toujours head par un. Une fois le pointeur avancé, nous remplissons l’indicateur full en vérifiant si head == tail.

Notez l’utilisation de l’opérateur modulo (%) ci-dessous. Modulo entraînera la réinitialisation des valeurs head et tail à 0 lorsque la taille maximale est atteinte. Cela garantit que head et tail sont toujours des indices valides du tampon de données sous-jacent.

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

Comme l’a utilement souligné Miro Samek, il s’agit d’une opération de calcul coûteuse. Au lieu de cela, nous pouvons utiliser la logique conditionnelle pour réduire le nombre total d’instructions. L’approche recommandée par Miro est la suivante :

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

Maintenant, advance_pointer ressemblera à ceci:

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

Nous pouvons créer une fonction d’assistance similaire qui est appelée lors de la suppression d’une valeur du tampon. Lorsque nous supprimons une valeur, l’indicateur full est défini sur false, et le pointeur de queue est avancé.

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

Nous allons créer deux versions de la fonction put. La première version insère une valeur dans le tampon et fait avancer le pointeur. Si le tampon est plein, la valeur la plus ancienne sera écrasée. C’est le cas d’utilisation standard pour un tampon circulaire

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

La deuxième version de la fonction put renvoie une erreur si le tampon est plein. Ceci est fourni à des fins de démonstration, mais nous n’utilisons pas cette variante dans nos systèmes.

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

Pour supprimer des données du tampon, nous accédons à la valeur au pointeur tail puis mettons à jour le pointeur tail. Si le tampon est vide, nous ne renvoyons pas de valeur ni ne modifions le pointeur. Au lieu de cela, nous renvoyons une erreur à l’utilisateur.

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

Qui complète l’implémentation de notre bibliothèque de tampons circulaires.

Utilisation

Lors de l’utilisation de la bibliothèque, le client est responsable de la création du tampon de données sous-jacent à circular_buf_init, et un cbuf_handle_t est renvoyé :

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

Ce handle est utilisé pour interagir avec toutes les fonctions de la bibliothèque restantes :

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

N’oubliez pas de libérer à la fois le tampon de données sous-jacent et le conteneur lorsque vous avez terminé:

free(buffer);circular_buf_free(cbuf);

Un programme de test qui utilise la bibliothèque de tampons circulaires se trouve dans le référentiel embedded-resources.

Modifications pour supprimer le drapeau complet

Si vous vouliez abandonner le drapeau full, vous vérifieriez plutôt que le head est une position derrière la queue pour déterminer si le tampon est plein:

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

Maintenant, si nous voulions éviter l’opération modulo, nous pouvons utiliser la logique conditionnelle à la place:

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

Le cas vide est alors que head et tail sont les mêmes:

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

Lors de l’obtention de données à partir du tampon, nous avancerons le pointeur de queue, enroulant autour si nécessaire:

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

Lors de l’ajout de données au tampon, nous stockerons les données et avancerons le pointeur de tête, enroulant autour si nécessaire:

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

Les autres références à full peuvent être éliminées.

C++

C++ se prête à une implémentation de tampon circulaire plus propre que C.

Définition de classe

Nous commencerons par définir notre classe C++. Nous voulons que notre implémentation C++ prenne en charge tout type de données, nous allons donc en faire une classe modèle.

Nos API vont être similaires à l’implémentation C. Notre classe fournira des interfaces pour:

• Réinitialiser le tampon pour le vider
• Ajout de données
• Suppression de données
• Vérification de l’état plein / vide
• Vérification du nombre actuel d’éléments dans le tampon
• Vérification de la capacité totale du tampon

Nous utiliserons également des pointeurs intelligents C++ pour nous assurer que nous ne laissons aucune donnée une fois notre tampon détruit. Cela signifie que nous pouvons gérer le tampon pour l’utilisateur.

Un autre avantage de C++ est la trivialité de rendre cette classe thread-safe: nous pouvons compter sur le type std::mutex (en supposant que cela soit défini pour votre plate-forme).

Voici notre définition de 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;};

Implémentation C++

Notre tampon circulaire C++ imite une grande partie de la logique de l’implémentation C, mais aboutit à une conception beaucoup plus propre et plus réutilisable. De plus, le tampon C++ utilise std::mutex pour fournir une implémentation thread-safe.

Remarque : Les mêmes modifications logiques peuvent être apportées dans l’implémentation C++ pour prendre en charge la sécurité des threads avec un seul producteur et consommateur en « gaspillant” un slot. Voir les ajustements dans l’implémentation C pour plus d’informations.

Initialisation

Lors de la construction de notre classe, nous allouons les données pour notre tampon sous-jacent et définissons la taille du tampon. Cela supprime les frais généraux requis avec l’implémentation C.

Contrairement à l’implémentation C, le constructeur C++ n’appelle pas reset. Parce que nous spécifions des valeurs initiales pour nos variables membres, notre tampon circulaire commence dans le bon état.

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

Notre comportement de réinitialisation remet le tampon à un état vide (head == tail && !full_).

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

Suivi d’état

La logique des cas empty et full est la même que celle de l’exemple C:

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

Dans l’implémentation du tampon circulaire C++, size et capacity rapportent le nombre d’éléments dans la file d’attente plutôt que la taille en octets. Cela nous permet d’être agnostiques aux détails sous-jacents du type.

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

Ajout de données

La logique de put correspond à l’implémentation C. Cette implémentation utilise le modèle de comportement ”écraser la valeur la plus ancienne ».

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

Remarque: Pour plus de simplicité, j’ai omis l’option qui évite les opérations modulo. Vous pouvez trouver cette logique dans la section C.

Récupération des données

La logique derrière get correspond à l’implémentation C. Contrairement à l’implémentation C, une valeur vide est renvoyée si le tampon est vide.

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

Remarque: return T() renvoie une valeur construite par défaut pour le type donné. La valeur réelle produite dépend du type ou du constructeur. De plus, pour plus de simplicité, j’ai laissé de côté l’option qui évite les opérations modulo. Vous pouvez trouver cette logique dans la section C.

Utilisation

Le tampon circulaire C++ est beaucoup plus simple à utiliser que l’implémentation C.

Pour instancier un tampon circulaire, nous déclarons simplement un objet et spécifions le type de modèle pour notre tampon. Voici un exemple utilisant un tampon de 10 entrées uint32_t:

circular_buffer<uint32_t> circle(10);

Ajouter des données est facile:

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

Et obtenir des données est tout aussi facile:

x = circle.get()

Rappelez-vous que comme il s’agit d’une classe modélisée, vous pouvez créer un tampon circulaire de tout type dont vous avez besoin.

Mises à jour pour C++17

En C++17, nous avons accès à std::optional, ce qui nous permet de représenter une valeur qui peut être présente ou non. Notre fonction get renverrait un std::optional<T>. Nous retournerions également std::nullopt au lieu d’un T construit par défaut si la file d’attente est vide.

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

Remarque: Pour plus de simplicité, j’ai omis l’option qui évite les opérations modulo. Vous pouvez trouver cette logique dans la section C.

Dans le code d’appel, vous pouvez vérifier une valeur valide à l’aide de l’opérateur booléen ou de la fonction membre has_value. Si une valeur valide est présente, elle est accessible à l’aide des opérateurs -> ou *, en utilisant la fonction membre value().

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

Tout mettre ensemble

Des exemples d’implémentations peuvent être trouvés dans le dépôt Github embedded-resources.

• Programme de test de tampon circulaire C
  • Bibliothèque de tampon circulaire C
• Exemple de tampon circulaire C++

Si vous souhaitez étendre cette bibliothèque, un exercice utile consiste à ajouter des API supplémentaires pour permettre aux utilisateurs d’ajouter / supprimer plusieurs éléments en une seule opération. Vous pouvez également sécuriser le thread d’implémentation C.

Sécurité des threads avec la méthode Lookahead

Une approche pour la sécurité des threads sans mutex est la méthode  » lookahead ». Cette méthode prend en charge un seul thread producteur et un seul thread consommateur; plusieurs producteurs ou consommateurs auront besoin d’un verrou.

Au lieu d’utiliser l’indicateur booléen pour différencier les cas pleins et vides, nous laisserons toujours une cellule vide. En utilisant une seule cellule vide pour détecter le cas « complet », nous pouvons prendre en charge un seul producteur et un seul consommateur sans verrou (tant que put et get ne modifient pas les mêmes variables).

Vous risquez peut-être de gaspiller un emplacement, mais ce compromis est souvent beaucoup moins cher que le coût d’utilisation d’une primitive de verrouillage du système d’exploitation.

Pour en savoir plus

• Pointeurs intelligents C++
• Abandonnez vos Pointeurs C-Orgelet pour des Pointeurs intelligents

Voici d’autres implémentations de tampons circulaires :

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

Pour plus d’informations sur les tampons circulaires :

• Embedded.com : Bases du tampon annulaire
• Wikipedia: Tampon circulaire
• Systèmes Ferreux: Tampon Annulaire Sans Verrouillage
• Tampon Circulaire Boost
• C++: Performance d’un Tampon Circulaire vs Vecteur, Deque et Liste
• File d’attente circulaire Mono-Producteur-Consommateur unique sans verrouillage

Il existe une proposition pour ajouter un type de tampon circulaire à la bibliothèque standard C++ :

• P0059: Une proposition visant à ajouter une portée d’anneau à la Bibliothèque standard
  • Portée d’anneau
  • Portée d’anneau Lite

Journal des modifications

• 20210321
  • Erreur corrigée avec max_size_ où cbuf->max devrait avoir utilisé
  • Ajout d’un texte clarifiant sur la raison pour laquelle le tampon est transmis par l’utilisateur
• 20210301
  • Commentaires adressés de Miro concernant l’évitement des opérations modulo
• 20210213
  • Ajout de liens supplémentaires
  • Ajout d’une discussion supplémentaire sur le compromis entre l’indicateur complet et l’utilisation d’un « gaspillé” slot
  • Afficher les modifications pour la sécurité des threads avec un seul producteur / consommateur
  • Ajouter des notes sur std::optionalUtiliser avec C++17
• 20191016
  • Mise à jour du formatage de la section du journal des modifications pour la cohérence sur le site
  • En-têtes rétrogradés pour la cohérence sur le site
  • Liens de table des matières cassés fixes
  • /li>
  • Suppression du Journal des modifications de la Table des matières
• 20190627
  • Ajout d’un lien vers l’article Tampon d’anneau sans verrouillage de Ferrous Systems.
• 20190604
  • Correction d’une faute de frappe (merci Chris Svec!) et a modifié certaines formulations liées au type opaque.
• 20181219
  • Note supplémentaire sur la prévention des problèmes de concurrence avec un seul producteur et un seul consommateur utilisant un emplacement vide.
• 20180804
  • L’article a été restructuré et réécrit.Merci à tous ceux qui ont fourni des commentaires en cours de route. Les exemples ont été mis à jour pour:
  • Supprimer la programmation défensive
  • Utiliser des assertions
  • Créer une bibliothèque autonome à l’aide d’une structure opaque
  • Développer les API, y compris un calcul de la taille de tampon circulaire actuelle
  • Mettre à jour la bibliothèque pour qu’elle ne perde pas de slot