Rengaspuskuri

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. marraskuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Ring-puskuri eli syklinen puskuri  ( eng.  ring-buffer ) on tietorakenne , joka käyttää yhtä kiinteän kokoista puskuria siten, että ensimmäinen elementti seuraa välittömästi viimeistä elementtiä. Tämä rakenne tarjoaa helposti mahdollisuuden puskuroida tietovirtoja .

Sovellus

Rengaspuskuria käytetään erittäin laajasti, myös mikro -ohjainten ohjelmoinnissa . Näitä rakenteita käytetään usein erilaisten viestijonojen järjestämiseen ja eri tiedonsiirtorajapintojen lähetys/vastaanottopuskureihin. KB:n suosio johtuu siitä, että tämä on yksi yksinkertaisimmista ja tehokkaimmista tavoista järjestää FIFO ( englanniksi  first in - first out , "first in - first out") ilman dynaamista muistia. KB-tyyppejä on monenlaisia.

Sisäinen järjestely

Soittopuskuri luodaan tyhjäksi, jolla on ennalta määrätty pituus. Tämä on esimerkiksi seitsemän elementin puskuri:

Oletetaan, että puskurin keskelle kirjoitetaan "1" (rengaspuskurissa tarkalla aloitussolulla ei ole väliä):

Oletetaan sitten, että yksikön jälkeen lisättiin vielä kaksi elementtiä - "2" ja "3":

Jos kaksi elementtiä on tämän jälkeen poistettava puskurista, valitaan kaksi vanhinta elementtiä. Tässä tapauksessa elementit "1" ja "2" poistetaan, puskuriin jää vain "3":

Jos puskurissa on 7 elementtiä, se on täynnä:

Jos jatkat puskuriin kirjoittamista sen täyteydestä riippumatta, uudet tiedot alkavat korvata vanhat tiedot. Tässä tapauksessa elementtien "A" ja "B" lisääminen korvaa "3" ja "4":

Toisessa toteutuksessa puskuria ylläpitävät rutiinit voivat estää tietojen päällekirjoittamisen ja palauttaa virheen tai heittää poikkeuksen . Korvaaminen vai ei, on jätetty puskurin taustaohjelmien tai rengaspuskuria käyttävän sovelluksen harkintaan.

Lopuksi, jos kaksi elementtiä poistetaan puskurista, ei "3" ja "4", vaan "5" ja "6" poistetaan, koska "A" ja "B" ylikirjoittivat elementit "3" ja " 4"; puskuri on tilassa:

Esimerkkitoteutus C :ssä

#include <stdlib.h> #define CHAR_SIZE(koko(merkki)) #define RINGBUFFER_OK (0) #define RINGBUFFER_ERR_NULL (-1) #define RINGBUFFER_ERR_EMPTY (-2) #define RINGBUFFER_ERR_FULL (-3) typedef struct { merkki * aloitus ; merkki * loppu ; haihtuva char * readptr ; volatile char * writeptr ; } RingBuffer ; RingBuffer * newRingBuffer ( allekirjoittamaton pitkä int kapasiteetti ) { char * mem = malloc ( kapasiteetti * CHAR_SIZE ); if ( mem == NULL ) { return NULL ;} RingBuffer * rb = malloc ( koko ( RingBuffer )); if ( rb == NULL ) { vapaa ( mem ); palauta NULL ;} rb -> aloitus = mem ; rb -> loppu = muisti + kapasiteetti ; rb -> readptr = mem ; rb -> writeptr = mem ; paluu rb ; } void deleteRingBuffer ( RingBuffer * rb ) { if ( rb == NULL ) return ; vapaa ( rb -> aloitus ); ilmainen ( rb ); } int RingBuffer_trywrite ( RingBuffer * rb , char c ) { if ( rb == NULL ) palauttaa RINGBUFFER_ERR_NULL ; if ( rb -> writeptr + 1 == rb -> readptr ) return RINGBUFFER_ERR_FULL ; * ( rb -> writeptr ) = c ; char * tmp = rb -> writeptr + 1 ; if ( tmp >= rb -> loppu ) tmp = rb -> alku ; rb -> writeptr = tmp ; palauttaa RINGBUFFER_OK ; } int RingBuffer_tryread ( RingBuffer * rb , char * c ) { if ( rb == NULL ) palauttaa RINGBUFFER_ERR_NULL ; if ( rb -> readptr == rb -> writeptr ) return RINGBUFFER_ERR_EMPTY ; * c = ( rb -> readptr ); char * tmp = rb -> readptr + 1 ; if ( tmp >= rb -> loppu ) tmp = rb -> alku ; rb -> readptr = tmp ; palauttaa RINGBUFFER_OK ; }

Linkit

 Tietorakenteet
Luettelot
puut
Laskee
Muut