A circular / ring buffer for embedded

[robert rozee]

You confuse the theory of a ringbuffer with its possible implementation as a linked list with a fixed size

now i'm really confused! my understanding of a linked list is an arbitrary number of records, usually each allocated (from the heap) individually, where each record contains one or more pointers to 'adjacent' records. a linked list is 'anchored' by an initial pointer to the first record, which then has a link (pointer) to the next record, which itself has a pointer to the next, and so on. the final record has its pointer set to nil. a doubly linked list will have two pointers, one pointing to the next record and the other pointing to the previous record. the key point of a linked list is the ability to add records into the 'middle' of the list without needing to shuffle things around - as you would have to do if your data was stored in an array. a doubly-linked list can be traversed in either direction and is slightly more convenient when linking in new records.

the example i posted is just an array of data elements. there are two indexes into this array - one is 'owned' by the process storing data, the other is 'owned' by the process retrieving the data. if these indexes are not guaranteed to be atomic, then some level of locking is necessary to ensure there is no corruption of the indexes.

could it be that the meanings of these terms have changed? when i learnt about these things at university we were using mainframes with 64k of ram - perhaps times have moved on!


cheers,
rob   :-)

[Thaddy]

You confuse the theory of a ringbuffer with its possible implementation as a linked list with a fixed size

now i'm really confused! my understanding of a linked list is an arbitrary number of records, usually each allocated (from the heap) individually, where each record contains one or more pointers to 'adjacent' records. a linked list is 'anchored' by an initial pointer to the first record, which then has a link (pointer) to the next record, which itself has a pointer to the next, and so on. the final record has its pointer set to nil. a doubly linked list will have two pointers, one pointing to the next record and the other pointing to the previous record. the key point of a linked list is the ability to add records into the 'middle' of the list without needing to shuffle things around - as you would have to do if your data was stored in an array. a doubly-linked list can be traversed in either direction and is slightly more convenient when linking in new records.

the example i posted is just an array of data elements. there are two indexes into this array - one is 'owned' by the process storing data, the other is 'owned' by the process retrieving the data. if these indexes are not guaranteed to be atomic, then some level of locking is necessary to ensure there is no corruption of the indexes.

could it be that the meanings of these terms have changed? when i learnt about these things at university we were using mainframes with 64k of ram - perhaps times have moved on!


cheers,
rob   :-)

How can you be confused? You are the one that mistakenly stated a ringbuffer is a linked list, which it can be used to implement as such but isn't.
Why so much text to prove yourself - partially - wrong, again?
Is it so hard to admit you are wrong?
We used the same trick on DEC VAX in 1978.

[ccrause]

an interesting thread - largely because i always understood that the concept of a ringbuffer was that it had a head and a tail.

If we refer to the wikipedia article on circular buffers, which in my world is synonymous with ring buffer. The point is (as per the article) that a ring buffer is useful as a FIFO buffer, so one needs to keep track (in the general sense) of the start and end of the buffer.

In short, Robert I agree with your comment.  Your example logic is spot on in terms of the logic required for shared read/write access to a ring buffer.

Thaddy's example is for a ring buffer that is first populated, then read. No shared asynchronous access.  Thus it is not a general implementation for shared read/write FIFO access to a ring buffer.

[duralast]

Robert,

You confuse the theory of a ringbuffer with its possible implementation as a linked list with a fixed size, which can be a ringbuffer, but is implementation detail.
A ringbuffer is theoretically any implementation of fixed length that resets itself to its start after a given linear number of probes, a.k.a. a ladder run.

But a ringbuffer need not be a linked list. A linked list is certainly not the most efficient implementation of a ringbuffer. That is the way I demonstrated: no need to maintain any pointers, hence it is so popular for real-time applications like video and audio: It is demonstrably the fastest way.

Reading the Linux Lockless Ring Buffer Design doc on kernel.org seems to refute this.
https://docs.kernel.org/trace/ring-buffer-design.html

The ring buffer is made up of a list of pages held together by a linked list.

Also, a ring buffer does use pointers.

Your code looks very amateurish. No overwrite and producer/consumer modes, no nested pages. It does not really resemble a real ring buffer.

[robert rozee]

You are the one that mistakenly stated a ringbuffer is a linked list

where did i state that a ringbuffer is a linked list???

i said a ringbuffer has a head and a tail, but from my example code you can see that these are just indexes. and i also stated a ringbuffer consists of an array of data elements (in my example, an array of char). in my example code i bundle up these constituent parts into a Pascal record simply for convenience, so that the parts can be referred to by 'dot' notation: RxBuffer.head, RxBuffer.tail, RxBuffer.data[n] and for controlling access RxBuffer.skip.

btw, the article "Linux Lockless Ring Buffer Design" postdates my university days by some quarter of a century. in that article, concepts of 'ringbuffer' and 'linked list' appear to be brought together into a complex data structure design that the authors decided to name a "Lockless Ring Buffer", an unfortunate choice of name as what they have built is much more than a simple ringbuffer; their section titled "Generic Ring Buffer" is mis-titled as what they described is (in my opinion) not generic.


cheers,
rob   :-)

[Thaddy]

i said a ringbuffer has a head and a tail,

Wrong.
Your head/tail use implies linked list as implementation.
These are really separate things. In your case you need a tail instead of natural overflow like I propose.
It is a bit strange that you keep arguing.

Note I have nothing against using a fixed length linked list for this, but don't pretend it is the ringbuffer. It is a ringbuffer implemented as a linked list. Period.

[robert rozee]

i said a ringbuffer has a head and a tail

Wrong.
Your head/tail use implies linked list as implementation. [...]

NO, the terms head/tail do not in ANY way imply a linked list. furthermore, the code example i gave does not contain any implementation of a linked list - did you look at the code?

Code: Pascal  [Select][+][-]

1. const RxBuffer:record                                    // serial input (ring) buffer
2.                  data:array [0..$3FFFF] of char;         // 256k
3.                  head:integer;
4.                  tail:integer;
5.                  skip:boolean
6.                end=(data:''; head:0; tail:0; skip:false);

does the fact that a cat (of the feline variety) has a head and a tail imply it is implemented (under the fur) as a linked list?!


cheers,
rob   :-(

[dbannon]

does the fact that a cat (of the feline variety) has a head and a tail imply it is implemented (under the fur) as a linked list?!

Oh, I do so like that !

Davo

[Thaddy]

It just shows Rob doesn't have a clue about theory. Period.

[silvercoder70]

A linked list can use a head and a tail.

So CAN (or does) a circular buffer or ring buffer and whatever names you want to use for the structure as a hole.

And depending on the content (/items) in the "buffer" can use pointers. And my only comment will be the text below (in italics) from https://www.kernel.org/doc/Documentation/circular-buffers.txt

You're Welcome (exiting room silently and leave the door open)... but how you choose to name things, and how much or what parts of the buffer you implement is a design / programming decision.

What is a circular buffer?
==========================

First of all, what is a circular buffer?  A circular buffer is a buffer of
fixed, finite size into which there are two indices:

 (1) A 'head' index - the point at which the producer inserts items into the
     buffer.

 (2) A 'tail' index - the point at which the consumer finds the next item in
     the buffer.

Typically when the tail pointer is equal to the head pointer, the buffer is
empty; and the buffer is full when the head pointer is one less than the tail
pointer.

The head index is incremented when items are added, and the tail index when
items are removed.  The tail index should never jump the head index, and both
indices should be wrapped to 0 when they reach the end of the buffer, thus
allowing an infinite amount of data to flow through the buffer.

Typically, items will all be of the same unit size, but this isn't strictly
required to use the techniques below.  The indices can be increased by more
than 1 if multiple items or variable-sized items are to be included in the
buffer, provided that neither index overtakes the other.  The implementer must
be careful, however, as a region more than one unit in size may wrap the end of
the buffer and be broken into two segments.


edited: added text re naming things.

[cdbc]

Hi
Here's another example of a circular buffer / queue:

Code: Pascal  [Select][+][-]

1. unit cirqueue;
2. {$mode ObjFPC}{$H+}
3. {$Interfaces COM}
4. {-$define dbg}
5. interface
6. uses classes, sysutils;
7. const
8.   cqVersion = '1.04.01.2025';
9.   cqGrowFactor = 1.618; { the golden ratio :o) }
10. type
11.   { callback proc to dispose of data in the 'Clear'ing methods when freeing the container
12.     sig: procedure FreePtr(aPtr: pointer); }
13.   TDisposeProc = procedure(aPtr: pointer);
14.   {$if fpc_fullversion <= 30202} RTLString = ansistring; {$endif} { introduced in trunk }
15.   { TCirQueue ~ enqueues on tail & dequeues on head }
16.   TCirQueue = class(TInterfacedObject{,ICirQueue})
17.   private
18.     fCount,fHead,fTail: ptrint;
19.     fDispose: TDisposeProc; { for use in Clear }
20.     fQue: TFPList;
21.     procedure Grow;
22.   public
23.     constructor Create(aCapacity: ptrint;aDisposeProc: TDisposeProc = nil);
24.     destructor Destroy;override;
25.     function Capacity: ptrint;
26.     procedure Clear;
27.     function Count: ptrint;
28.     function Dequeue: pointer;
29.     procedure Enqueue(aData: pointer);
30.     function IsEmpty: boolean;
31.     function Peek: pointer;
32.     function ToString: RTLString; override;
33.   end;
34.  
35. implementation
36.  
37. procedure DummyDisp(aPtr: pointer); // null-proc
38. begin
39.   if aPtr = nil then ; { do absolutely nothing }
40. end;
41.  
42. {$Region 'TCirQueue'}
43. { TCirQueue }
44. procedure TCirQueue.Grow;
45. var li,lt: ptrint;
46. begin { we'll expand with the golden ratio items added ~ 61,8 % }
47.   li:= trunc(fQue.Count * cqGrowFactor);
48.   fQue.Count:= li;
49.   if (fHead = 0) then fTail:= fCount { only enqueueing has been done, no dequeueing }
50.   else begin { tail caught up, make room in between tail and head again, }
51.     lt:= fQue.Count; { afterall we're growing due to lack of space }
52.     for li:= fCount-1 downto fHead do begin
53.       dec(lt);
54.       fQue[lt]:= fQue[li];
55.     end;
56.     fHead:= lt;
57.   end;
58. end;
59.  
60. constructor TCirQueue.Create(aCapacity: ptrint;aDisposeProc: TDisposeProc);
61. begin
62.   inherited Create;
63.   { assign our disposeproc, if nil then we'll just use a dummy 'null' proc }
64.   if aDisposeProc <> nil then fDispose:= aDisposeProc else fDispose:= @DummyDisp;
65.   fQue:= TFPList.Create;
66.   if (aCapacity <= 1) then aCapacity:= 32;
67.   fQue.Count:= aCapacity;
68.   fHead:= 0; fTail:= fHead; fCount:= 0;
69. end;
70.  
71. destructor TCirQueue.Destroy;
72. begin
73.   Clear;
74.   fQue.Free;
75.   {$ifdef dbg}writeln('TCirQueue Destroyed');{$endif}
76.   inherited Destroy;
77. end;
78.  
79. function TCirQueue.Capacity: ptrint;
80. begin
81.   Result:= fQue.Capacity;
82. end;
83.  
84. procedure TCirQueue.Clear;
85. begin { we only clear the residue active items left in the queue }
86.   while not IsEmpty do fDispose(Dequeue);
87.   fHead:= 0; fTail:= fHead; fCount:= 0; { here fTail:= fHead; means empty }
88. end;
89.  
90. function TCirQueue.Count: ptrint;
91. begin
92.   Result:= fCount;
93. end;
94.  
95. function TCirQueue.Dequeue: pointer;
96. begin
97.   if fCount = 0 then exit(nil);
98.   Result:= fQue[fHead];
99.   fHead:= (fHead + 1) mod fQue.Count; { inc but make sure it's still valid }
100.   dec(fCount);
101. end;
102.  
103. procedure TCirQueue.Enqueue(aData: pointer);
104. begin
105.   fQue[fTail]:= aData;
106.   fTail:= (fTail + 1) mod fQue.Count;
107.   inc(fCount);
108.   if (fTail = fHead) then Grow; { here this means full, so we'll grow it a bit }
109. end;
110.  
111. function TCirQueue.IsEmpty: boolean;
112. begin
113.   Result:= (fCount = 0);
114. end;
115.  
116. function TCirQueue.Peek: pointer;
117. begin { a small test-case, to see if direct access is snappier }
118.   if fCount > 0 then Result:= fQue[fHead] else Result:= nil;
119. end;
120.  
121. function TCirQueue.ToString: RTLString;
122. begin
123.   Result:= 'I/TCirQueue v '+cqVersion+', a circular self-growing queue '+LineEnding+
124.            '(c) 2025 Copyright Benny Christensen a.k.a. cdbc, All rights reserved';
125. end;
126. {$EndRegion 'TCirQueue'}
127.  
128. end.
129.  

It would have to have some 'item-size-mechanics' implemented, to be of real use as a general buffer...
I dunno if it's suitable for embedded though?!?
Just my 2 cent's worth
Regards Benny