Skrivet av Teknocide:
Nyfiken och kanske dum fråga då jag inte programmerat C på över 15 år: varför väljer du att hålla r som ett värde istället för en pekare till ring_t? Det ser omständigt ut att hämta referensen vid varje anrop till ring_enq/ring_show, men förmodligen missar jag något
Främst två orsaker i detta exempel:
1. minnet hanteras automatiskt.
2. går att låta kompilatorn generera all kod för att initiera en variabel till en tom ring.
I detta fall spelar det ingen större roll hur man gör, är så pass enkelt. Men rent generellt så vill man hålla så mycket som möjligt i automatiska variabler i C, dels är det överlägset snabbaste sättet och kanske ännu viktigare är att sådan kod kan typiskt alltid skrivas så den överhuvudtaget inte kan gå fel -> inga felfall att tänka på -> enklare.
ring_enq() och ring_deq() måste ju ta en pekare för att ändra innehållet i strukturen, ring_show() skulle kunna ta sitt argument "by-value" eller som en const ring_t *, tyckte det var en koherent och ta pekare överallt.
Tycker just denna uppgift kring ring-buffert var lite "elak" då storleken inte är en potens av två. Den absolut vanligaste anledningen till varför man väljer en ring-buffert är för att man måste ha absolut högsta möjliga prestanda. Än viktigare blir det i på dagens multicore-system, en ring-buffert baserad kö men exakt en tråd som producerar och en som konsumerar går att skriva korrekt helt utan lås. En kö med multipla läsare/skrivare går fortfarande att skriva utan traditionella lås (mutex eller liknande), räcker med en s.k. compare-and-swap (CAS) som typiskt är väldigt hårt optimerad i moderna CPUer.
Buggen i mitt program ovan kommer när man köar sitt 2^32:e element, 3 är inte jämt delbart med 2^32 så där kommer det bli fel. Problemet om en ring-buffert inte har en kapacitet som är en potens av två är att en rad optimeringar blir omöjliga, bara en sådan sak som att hålla reda på om kön är helt tom eller helt full blir komplicerat om man kör med ett index för konsumtion och ett index för produktion...
Det "elaka" är att det blir fler specialfall om storleken inte är en potens av två. Slog mig att det är nog orsaken till att man i detta fall föreslår front och length som tillstånd. Pseudokoden för Enqueue blir då i stället
Enqueue(elem)
array[(front + length) mod RING_CAPACITY] = elem ; lagra elementet, index för produktion är index för konsumtion plus nuvarande längd
length++ ; antal element i kön har ökat med ett
och Dequeue blir
Dequeue()
elem = array[front] ; 'front' är index för konsumtion
front = (front + 1) mod RING_CAPACITY ; 'front' är index till nästa position för konsumtion
length-- ; antal element i kön minskar med ett
return elem
En korrekt C implementation där man har restriktionen att kapaciteten måste vara en potens av två, notera total avsaknad av dyra operationer som "mod/%", check för något specialfall vid wrap-around. Många periferienheter använder också ring-bufferts som gränssnitt då det är lätt att designa sådant i maskinvara, nätverkskort är ett exempel som använder ring-bufferts för inkommande och utgående paket.
#include <stdio.h>
#define RING_ORDER 2
/* Convenience macros derived from RING_ORDER */
#define RING_CAP (1U << RING_ORDER)
#define RING_MASK (RING_CAP - 1)
#define RING_INITIALIZER { 0, 0, { [0 ... RING_CAP-1] = '*' } }
typedef char elem_t;
typedef struct {
unsigned prod;
unsigned cons;
elem_t storage[RING_CAP];
} ring_t;
void ring_enq(ring_t *ring, elem_t elem)
{
ring->storage[ring->prod++ & RING_MASK] = elem;
}
elem_t ring_deq(ring_t *ring)
{
return ring->storage[ring->cons++ & RING_MASK];
}
void ring_show(const ring_t *ring)
{
unsigned i;
for (i = 0; i < RING_CAP; i++)
{
printf("%c", ring->storage[i]);
}
printf(" Front = %u, Length = %u\n",
ring->cons & RING_MASK,
ring->prod - ring->cons);
}
int main()
{
ring_t ring_storage = RING_INITIALIZER;
ring_t *r = &ring_storage;
ring_enq(r, 'a');
ring_show(r);
ring_enq(r, 'b');
ring_show(r);
ring_enq(r, 'c');
ring_show(r);
ring_enq(r, 'x');
ring_show(r);
ring_deq(r); /* 'a' */
ring_show(r);
ring_deq(r); /* 'b' */
ring_show(r);
ring_enq(r, 'd');
ring_show(r); /* "dbcx Front = 2, Length = 3" */
}
Dold text
