Buffer circulaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un cercle représentant un buffer circulaire de manière conceptuelle. En réalité, une représentation linéaire est utilisée, et la partie orange est simplement écrasée.

Un buffer circulaire est une structure de données utilisant un buffer de taille fixe et dont le début et la fin sont considérés comme connectés. Les buffers circulaires sont souvent utilisés pour gérer des flux de donnée ou pour implémenter un comportement de type FIFO.

Fonctionnement[modifier | modifier le code]

Un buffer circulaire est vide au départ et a une longueur prédéterminée. Par exemple, un buffer de 7 éléments :

Circular buffer - empty.svg

Supposons que le nombre 1 est écrit à une position, arbitrairement définie comme position initiale :

Circular buffer - XX1XXXX.svg

Deux éléments supplémentaires — 2 & 3 — sont alors ajoutés après le 1:

Circular buffer - XX123XX.svg

Si deux éléments sont alors retirés du buffer il s’agira des deux premiers éléments ajoutés. Ici il s’agit de 1 et 2, le buffer ne contient alors plus que le 3.

Circular buffer - XXXX3XX.svg

Si le buffer a 7 éléments, il est alors complètement rempli :

Circular buffer - 6789345.svg

Une des conséquences de l'utilisation d'un buffer circulaire est que lorsqu'il est plein et qu'un ajout supplémentaire est effectué, les données les plus anciennes sont écrasées. Dans ce cas, deux éléments — A & B — sont ajoutés et écrasent le 3 et le 4:

Circular buffer - 6789AB5.svg

Il est aussi possible que la routine gérant le buffer ne laisse pas l'écrasement se produire et génère une erreur lors de l'ajout de données supplémentaires.

Pour finir, si deux éléments sont alors retirés, les éléments obtenus ne seraient alors pas 3 & 4 mais 5 & 6, car A & B ont écrasés le 3 et le 4; laissant le buffer dans cet état :

Circular buffer - X789ABX.svg