Prstencový buffer

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. listopadu 2018; kontroly vyžadují 10 úprav .

Kruhová vyrovnávací paměť nebo cyklická vyrovnávací paměť  ( anglicky  ring-buffer ) je datová struktura , která využívá jednu vyrovnávací paměť o pevné velikosti tak, že první prvek bezprostředně následuje znovu za posledním prvkem. Tato struktura snadno poskytuje možnost ukládání datových toků do vyrovnávací paměti .

Aplikace

Kruhová vyrovnávací paměť je velmi široce používána, včetně programování mikrokontrolérů . Tyto struktury se často používají k organizování různých front zpráv a vyrovnávacích pamětí pro vysílání/příjem různých komunikačních rozhraní. Popularita KB je způsobena tím, že jde o jeden z nejjednodušších a nejúčinnějších způsobů, jak organizovat FIFO ( anglicky  first in - first out , "first in - first out") bez použití dynamické paměti. Existuje mnoho typů KB.

Vnitřní uspořádání

Kruhový buffer je vytvořen prázdný, s určitou předdefinovanou délkou. Jedná se například o sedmiprvkovou vyrovnávací paměť:

Předpokládejme, že „1“ je zapsána do středu vyrovnávací paměti (v kruhové vyrovnávací paměti nezáleží na přesné počáteční buňce):

Pak předpokládejme, že za jednotku byly přidány další dva prvky - "2" a "3":

Pokud musí být z vyrovnávací paměti odstraněny dva prvky, vyberou se dva nejstarší prvky. V našem případě se prvky "1" a "2" vymažou, ve vyrovnávací paměti zůstane pouze "3":

Pokud je ve vyrovnávací paměti 7 prvků, je plná:

Pokud budete pokračovat v zápisu do vyrovnávací paměti, bez ohledu na její zaplnění, začnou nová data přepisovat stará data. V našem případě přidání prvků "A" a "B" přepíše "3" a "4":

V jiné implementaci mohou rutiny udržující vyrovnávací paměť zabránit přepsání dat a vrátit chybu nebo vyvolat výjimku . Přepsání, nebo ne, je ponecháno na uvážení backendů bufferu nebo aplikace používající kruhový buffer.

Konečně, pokud jsou nyní z vyrovnávací paměti odstraněny dva prvky, nebudou odstraněny "3" a "4", ale "5" a "6", protože "A" a "B" přepsaly prvky "3" a " 4"; buffer bude ve stavu:

Příklad implementace v C

#include <stdlib.h> #define CHAR_SIZE(sizeof(char)) #define RINGBUFFER_OK (0) #define RINGBUFFER_ERR_NULL (-1) #define RINGBUFFER_ERR_EMPTY (-2) #define RINGBUFFER_ERR_FULL (-3) typedef struct { char * start ; char * konec ; těkavý char * readptr ; těkavý char * writeptr ; } RingBuffer ; RingBuffer * newRingBuffer ( unsigned long int capacity ) { char * mem = malloc ( kapacita * CHAR_SIZE ); if ( mem == NULL ) { return NULL ;} RingBuffer * rb = malloc ( sizeof ( RingBuffer )); if ( rb == NULL ) { zdarma ( mem ); vrátit NULL ;} rb -> start = mem ; rb -> konec = mem + kapacita ; rb -> readptr = mem ; rb -> writeptr = mem ; vrátit rb ; } void deleteRingBuffer ( RingBuffer * rb ) { if ( rb == NULL ) return ; zdarma ( rb -> start ); volný ( rb ); } int RingBuffer_trywrite ( RingBuffer * rb , char c ) { if ( rb == NULL ) return RINGBUFFER_ERR_NULL ; if ( rb -> writeptr + 1 == rb -> readptr ) return RINGBUFFER_ERR_FULL ; * ( rb -> writeptr ) = c ; char * tmp = rb -> writeptr + 1 ; if ( tmp >= rb -> konec ) tmp = rb -> začátek ; rb -> writeptr = tmp ; return RINGBUFFER_OK ; } int RingBuffer_tryread ( RingBuffer * rb , char * c ) { if ( rb == NULL ) return RINGBUFFER_ERR_NULL ; if ( rb -> readptr == rb -> writeptr ) return RINGBUFFER_ERR_EMPTY ; * c = ( rb -> readptr ); char * tmp = rb -> readptr + 1 ; if ( tmp >= rb -> konec ) tmp = rb -> začátek ; rb -> readptr = tmp ; return RINGBUFFER_OK ; }

Odkazy

 Datové struktury
Seznamy
Stromy
Počítání
jiný