Circular buffers

Go To Last Post
9 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi Freaks,

Does anybody know of a good tutorial/website that explains how to implement circular buffers?

I am not looking for a code snippet but just the explanation/logic/algorithm for a circular buffer.

I have looked at the wiki site and did not understand their explanation.

Thanks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This wiki? http://en.wikipedia.org/wiki/Cir... I don't think there is something wrong with the explanation.

Stealing Proteus doesn't make you an engineer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What wiki did you look at? I think the Wikipedia article explains it quite well.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes I looked at the same one, but I was looking for some more elaboration on the circular buffer mechanics part. I mean where they show the partially full buffer and the start and end pointers, how did the start and the top pointers get swapped?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You can think about it as an array with two indexes.... one to add chars, one to remove chars. When you add a char at the end, you set the in index to zero. When you get the char at the end, you set the out index to zero. When the indexes ar equal, the buffer is empty, etc

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sometimes the two pointers are called head and tail. The tail chases the head, but does not overtake it. When the head catches the tail, the buffer has filled.

called circular (or "ring") because the pointers increment up to the size of the buffer storage, then wrap around to the beginning again. This is usually done by making the buffer size a power of two, and doing a bitwise AND on the incremented pointers, thus effecting a modulo operation like the "%" operator in C or the "mod" in most BASICs. The AND is simply faster.

if you look at the code for circular buffers, say, in UART interrupt handlers, you'll see that it's important to watch out for exclusive access while pointers are modified by non-interrupt code, if the interrupt code can alter the same pointer.

one example, among many here, is
https://www.avrfreaks.net/index.p...

some implementations use just head and tail pointers; others add a counter to speed up getting buffer content size.

Now, on to another ole fun thing: linked lists.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A very good book for that sort of thing is An Introduction to Algorithms by Cormen, Leiserson and Rivest.

Leon

Leon Heller G1HSM

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This App Note from IAR details a circular buffer for Serial Coms.

http://supp.iar.com/Support/?note=18523&from=search+result

Regards,

-=mike=-

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The Tutorial Forum here contains Dean's tutorial about UART interrupts that inevitably covers ring buffers:

https://www.avrfreaks.net/index.p...