Ringbuffert

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 november 2018; kontroller kräver 10 redigeringar .

Ringbuffert , eller cyklisk buffert  ( eng.  ring-buffer ) är en datastruktur som använder en enda buffert av en fast storlek på ett sådant sätt att det första elementet omedelbart följer efter det sista elementet igen. Denna struktur ger lätt möjlighet att buffra dataströmmar .

Applikation

Ringbufferten är mycket använd, inklusive vid programmering av mikrokontroller . Dessa strukturer används ofta för att organisera olika meddelandeköer och sända/ta emot buffertar för olika kommunikationsgränssnitt. Populariteten för KB beror på det faktum att detta är ett av de enklaste och mest effektiva sätten att organisera FIFO ( engelska  först in - först ut , "först in - först ut") utan att använda dynamiskt minne. Det finns många typer av KB.

Internt arrangemang

Ringbufferten skapas tom, med en viss fördefinierad längd. Detta är till exempel en buffert med sju element:

Låt oss anta att en "1" skrivs till mitten av bufferten (i en ringbuffert spelar den exakta startcellen ingen roll):

Anta sedan att ytterligare två element lades till efter enheten - "2" och "3":

Om två element sedan måste tas bort från bufferten, väljs de två äldsta elementen. I vårt fall raderas elementen "1" och "2", bara "3" finns kvar i bufferten:

Om det finns 7 element i bufferten är den full:

Om du fortsätter att skriva till bufferten, oavsett dess fullhet, kommer nya data att börja skriva över gamla data. I vårt fall kommer att lägga till element "A" och "B" att skriva över "3" och "4":

I en annan implementering kan rutinerna som underhåller bufferten förhindra att data skrivs över och returnera ett fel eller skapa ett undantag . Överskrivning, eller inte, överlåts till buffertens backends eller applikationen som använder ringbufferten.

Slutligen, om två element nu tas bort från bufferten, kommer inte "3" och "4", utan "5" och "6" att raderas, eftersom "A" och "B" skrev över elementen "3" och " 4"; bufferten kommer att vara i tillståndet:

Ett exempel på implementering i 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 * slut ; flyktigt char * readptr ; flyktigt char * writeptr ; } RingBuffer ; RingBuffer * newRingBuffer ( osignerad long int kapacitet ) { char * mem = malloc ( kapacitet * CHAR_SIZE ); if ( mem == NULL ) { return NULL ;} RingBuffer * rb = malloc ( storlek på ( RingBuffer )); if ( rb == NULL ) { gratis ( mem ); returnera NULL ;} rb -> start = mem ; rb -> slut = mem + kapacitet ; rb -> readptr = mem ; rb -> writeptr = mem ; returnera rb ; } void deleteRingBuffer ( RingBuffer * rb ) { if ( rb == NULL ) returnera ; gratis ( rb -> start ); gratis ( rb ); } int RingBuffer_trywrite ( RingBuffer * rb , char c ) { if ( rb == NULL ) returnera RINGBUFFER_ERR_NULL ; if ( rb -> writeptr + 1 == rb -> readptr ) returnera RINGBUFFER_ERR_FULL ; * ( rb -> writeptr ) = c ; char * tmp = rb -> writeptr + 1 ; if ( tmp >= rb -> slut ) tmp = rb -> start ; rb -> writeptr = tmp ; returnera RINGBUFFER_OK ; } int RingBuffer_tryread ( RingBuffer * rb , char * c ) { if ( rb == NULL ) returnera RINGBUFFER_ERR_NULL ; if ( rb -> readptr == rb -> writeptr ) returnera RINGBUFFER_ERR_EMPTY ; * c = ( rb -> readptr ); char * tmp = rb -> readptr + 1 ; if ( tmp >= rb -> slut ) tmp = rb -> start ; rb -> readptr = tmp ; returnera RINGBUFFER_OK ; }

Länkar

 Data struktur
Listor
Träd
Räknar
Övrig