A circular / ring buffer for embedded lazarus / 77-Embedded ---------------------------------------------------------------------- d.ioannidis · 2022-10-10 11:11 Ηι,   if you need a circular / ring buffer, I added the spsc_ringbuffer  in ccrause's fpc-avr github repo. It's very small, fast, lock free and even if it's in an AVR specific repo it's not only for AVR ( i think ... ).   It's a single producer / single consumer ring buffer. That means that there must be only one reader and only one writer. The basis for this came from an article in Jack Ganssle's Embedded Muse: http://www.ganssle.com/tem/tem110.pdf and with hints from this forum thread ( thx Martin ! ) . Have fun ! regards, ---------------------------------------------------------------------- marcov · 2022-10-10 13:19 Shouldn't at least some of those be inline? ---------------------------------------------------------------------- d.ioannidis · 2022-10-10 13:54 Hi, Quote from: marcov on October 10, 2022, 03:19:24 pmShouldn't at least some of those be inline? AFAIU, inline will have numerous copies of the same code at many places and I wanted it to be as small as possible . I'll look again the asm tonight to see if I missed something . regards, ---------------------------------------------------------------------- marcov · 2022-10-10 14:07 Quote from: d.ioannidis on October 10, 2022, 03:54:02 pmAFAIU, inline will have numerous copies of the same code at many places and I wanted it to be as small as possible . But the code might be smaller than the function overhead. QuoteI'll look again the asm tonight to see if I missed something . I don't do much AVR work, mostly dspic. (in C, not Pascal). Dspic-E and -Cs have a 4 cycle branch, so inlining wins back 3 cycles before even anything else is done. ---------------------------------------------------------------------- d.ioannidis · 2022-10-10 21:44 Hi, Quote from: marcov on October 10, 2022, 04:07:33 pm But the code might be smaller than the function overhead. If all the methods are inlined, then if the amount of calls to readbyte and/or writebyte methods is more than > 2 in the project, the project size is increased more than if you didn't inline them. But if the amount of calls to readbyte and/or writebyte methods is <=2, then the project size is smaller than if you didn't inline them.  Now I'm little puzzled on what I should use .... Maybe a define. some ifdef's and inform the user of the buffer library, for the pros and cons of enabling inline or not . Quote from: marcov on October 10, 2022, 04:07:33 pm I don't do much AVR work, mostly dspic. (in C, not Pascal). Dspic-E and -Cs have a 4 cycle branch, so inlining wins back 3 cycles before even anything else is done. If by branch you mean conditional branch, then AFAIK, on AVR is 1 cycle if condition is false and 2 cycles if the condition is true ( instruction pointer needs to be loaded with new target ). No much gain in this regard . If you mean call or rcall then it's 4 cycles ( for the mcu's with 16 bit PC that is ) as the Dspic-E you use . regards, ---------------------------------------------------------------------- AlexTP · 2022-10-10 22:20 Unit code was read by me. Can be changed to have any buffer size, as  i see. but instead of "Inc(nnn)" we will need Inc(nnn); if nnn>=BufferLastOffset then nnn:= BufferStartOffset; It must work with any size. The xxxMask method won't be needed. EDIT. Ops, then getting the buffer size as nWriteOffset-nReadOffset will be broken, sorry. ---------------------------------------------------------------------- marcov · 2022-10-11 07:43 I never really optimize on size, always on speed. Typical firmwares are 20-30kb, while the smallest flash is 128k, and most have 512kb. ---------------------------------------------------------------------- ccrause · 2022-10-11 11:58 Quote from: marcov on October 10, 2022, 04:07:33 pmI don't do much AVR work, mostly dspic. (in C, not Pascal). Quote from: marcov on October 11, 2022, 09:43:06 amI never really optimize on size, always on speed. Typical firmwares are 20-30kb, while the smallest flash is 128k, and most have 512kb. AVR resources are a bit more constrained: Maximum flash = 256 kB (atmega2560/1) Maximum RAM = 16 kB (atmega1284 & AVR128DB) Minimum flash = 512 bytes (attiny4/5) Minimum RAM = 32 bytes RAM (attiny4/5/9/10) No RAM : attiny26/28 Thus the use of inlining would depend on whether a particular application is flash, RAM and/or speed constrained. Quote from: d.ioannidis on October 10, 2022, 11:44:14 pm.... Maybe a define. some ifdef's and inform the user of the buffer library, for the pros and cons of enabling inline or not .A define to control the use of inline seems like an acceptable option so that the user has some choice. ---------------------------------------------------------------------- PascalDragon · 2022-10-12 05:35 We really should adjust {$Inline} so that it works like in Delphi: at the call site. So that the user themselves can control that inlining is off while the code that is called is compiled with inline (and assuming the compiler would indeed inline it). ---------------------------------------------------------------------- ccrause · 2022-10-12 06:09 Quote from: PascalDragon on October 12, 2022, 07:35:16 amWe really should adjust {$Inline} so that it works like in Delphi: at the call site. So that the user themselves can control that inlining is off while the code that is called is compiled with inline (and assuming the compiler would indeed inline it).  This seems like a really good idea! ---------------------------------------------------------------------- marcov · 2022-10-12 07:40 Quote from: ccrause on October 11, 2022, 01:58:52 pmAVR resources are a bit more constrained: Maximum flash = 256 kB (atmega2560/1) Maximum RAM = 16 kB (atmega1284 & AVR128DB) Minimum flash = 512 bytes (attiny4/5) Minimum RAM = 32 bytes RAM (attiny4/5/9/10) No RAM : attiny26/28 How useful is a HLL like Pascal on the tiny ? Quote from: PascalDragon on October 12, 2022, 07:35:16 amWe really should adjust {$Inline} so that it works like in Delphi: at the call site. So that the user themselves can control that inlining is off while the code that is called is compiled with inline (and assuming the compiler would indeed inline it).  Definitely. ---------------------------------------------------------------------- Thaddy · 2022-10-12 08:30 Just let it overflow with {$R-}. Need power of two, of course and the correct bit size. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program ringbuffer;{$R-}var    b:byte = 0;begin  repeat    writeln(b);    inc(b);  until 0=1;// silly, replace with signal hi/lo....end.Audio buffers trick.... That's how I used it in the past... And it is a 256 ringbuffer which is perfect for embedded. ---------------------------------------------------------------------- ccrause · 2022-10-12 08:45 Quote from: marcov on October 12, 2022, 09:40:37 amQuote from: ccrause on October 11, 2022, 01:58:52 pmAVR resources are a bit more constrained: Maximum flash = 256 kB (atmega2560/1) Maximum RAM = 16 kB (atmega1284 & AVR128DB) Minimum flash = 512 bytes (attiny4/5) Minimum RAM = 32 bytes RAM (attiny4/5/9/10) No RAM : attiny26/28 How useful is a HLL like Pascal on the tiny ? I assume with "tiny" you are referring to the bottom of the range little/no RAM controllers, since most of the tiny series is relatively capable.  One can implement some basic ideas in Pascal, especially if the main functionality consists of configuring peripherals. An example is a blinky project with no RAM requirement, all the logic is handled by the timer peripheral.  Other than removing the RTL startup code, I don't think you can reduce the code size (for this example) more by switching to assembler (and I have an idea to add a compiler switch to drop the startup code). But using Pascal would not give the user full control over storing variables just in registers, so to squeeze the very last bit of resources out of the controller would require abandoning the ABI (and Pascal) and only working in low level assembler. ---------------------------------------------------------------------- Thaddy · 2022-10-12 08:47 @ccrause Read my reply. That is usually how it is done and very lightweight. ---------------------------------------------------------------------- d.ioannidis · 2022-10-12 08:57 Hi, Quote from: marcov on October 12, 2022, 09:40:37 amQuote from: ccrause on October 11, 2022, 01:58:52 pmAVR resources are a bit more constrained: Maximum flash = 256 kB (atmega2560/1) Maximum RAM = 16 kB (atmega1284 & AVR128DB) Minimum flash = 512 bytes (attiny4/5) Minimum RAM = 32 bytes RAM (attiny4/5/9/10) No RAM : attiny26/28 How useful is a HLL like Pascal on the tiny ?   well the ATtiny10 has 1024 bytes of flash. With each instruction taking up 16 bits (2 bytes), you have about 512 instruction words available.  Writing in assembly gives you full control over these 512 words , but it also means slightly lesser readability (some people may disagree with me on this). That is why I usually prefer writing using Free pascal .   But FYI I'm not an embedded programmer ( using C# in my day job ), only a hobbyist who loves free pascal and electronics . regards, ---------------------------------------------------------------------- d.ioannidis · 2022-10-12 09:07 Hi, Quote from: Thaddy on October 12, 2022, 10:30:45 amJust let it overflow with {$R-}. Need power of two, of course and the correct bit size. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program ringbuffer;{$R-}var    b:byte = 0;begin  repeat    writeln(b);    inc(b);  until 0=1;// silly, replace with signal hi/lo....end.Audio buffers trick.... That's how I used it in the past... And it is a 256 ringbuffer which is perfect for embedded.  I use the same technique for the ring buffer read/write indices ( i.e. see here for read ) but how the above can be a ring buffer with 256 slots ? Where the values are stored ? What am I missing ?  Could you please elaborate ? regards, ---------------------------------------------------------------------- alpine · 2022-10-12 09:35 Quote from: d.ioannidis on October 12, 2022, 11:07:31 amHi, Quote from: Thaddy on October 12, 2022, 10:30:45 amJust let it overflow with {$R-}. Need power of two, of course and the correct bit size. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program ringbuffer;{$R-}var    b:byte = 0;begin  repeat    writeln(b);    inc(b);  until 0=1;// silly, replace with signal hi/lo....end.Audio buffers trick.... That's how I used it in the past... And it is a 256 ringbuffer which is perfect for embedded.  I use the same technique for the ring buffer read/write indices ( i.e. see here for read ) but how the above can be a ring buffer with 256 slots ? Where the values are stored ? What am I missing ?  Could you please elaborate ? regards, IMO this is just an example how the buffer pointer can be incremented and modulo 256 taken, without actually writing it ( b := (b + 1) % 256 ) by using the byte boundaries. ---------------------------------------------------------------------- Thaddy · 2022-10-12 16:11 No, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation. I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway. ---------------------------------------------------------------------- marcov · 2022-10-12 16:14 Quote from: Thaddy on October 12, 2022, 06:11:38 pmNo, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation. I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway. Well, assuming of course that this won't fail horribly because the compiler chooses a larger register size for the variable. ---------------------------------------------------------------------- Thaddy · 2022-10-12 16:16 which is not the case. ---------------------------------------------------------------------- marcov · 2022-10-12 16:23 Quote from: Thaddy on October 12, 2022, 06:16:23 pmwhich is not the case. Coincidence or by design? ---------------------------------------------------------------------- alpine · 2022-10-12 17:32 Quote from: Thaddy on October 12, 2022, 06:11:38 pmNo, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation. I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway. No? FYI modulo of 2^n is quite a light operation and is actually bit-wise and with 2^n-1. In your example, that you called an overflow, even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register - the carry just drops into the status flags and gets ignored. Regardless of the size of the type/register, unsigned and two's complement integers always naturally form a commutative ring. See also modular arithmetics. ---------------------------------------------------------------------- d.ioannidis · 2022-10-12 17:34 Hi, Quote from: y.ivanov on October 12, 2022, 07:32:35 pmQuote from: Thaddy on October 12, 2022, 06:11:38 pmNo, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation. I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway. No? FYI modulo of 2^n is quite a light operation and is actually bit-wise and with 2^n-1. In your example, that you called an overflow, even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register - the carry just drops into the status flags and gets ignored. Regardless of the size of the type/register, unsigned and two's complement integers always naturally form a commutative ring. See also modular arithmetics. the spsc_ringbuffer code is exactly what you describe . Stripped down is effectively : Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i unit spsc_ringbuffer; {$mode objfpc}{$macro on}{$inline on} interface {$define SPSC_PTRUINT := Byte} type   TSPSCRingBuffer = packed record    FBuffer: pbyte;    FBufferSize, FReadIndex, FWriteIndex: SPSC_PTRUINT;  end; function SPSC_IsEmpty(constref ARingBuffer: TSPSCRingBuffer): boolean;function SPSC_IsFull(constref ARingBuffer: TSPSCRingBuffer): boolean;function SPSC_Size(constref ARingBuffer: TSPSCRingBuffer): SPSC_PTRUINT; function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte); implementation function SPSC_MaskIndex(constref ARingBuffer: TSPSCRingBuffer; const AValue: SPSC_PTRUINT): SPSC_PTRUINT; inline;begin  Result := AValue and (ARingBuffer.FBufferSize - 1);end; function SPSC_IsEmpty(constref ARingBuffer: TSPSCRingBuffer): boolean;begin  Result := ARingBuffer.FReadIndex = ARingBuffer.FWriteIndex;end; function SPSC_IsFull(constref ARingBuffer: TSPSCRingBuffer): boolean;begin  Result := SPSC_Size(ARingBuffer) = ARingBuffer.FBufferSize - 1;end; function SPSC_Size(constref ARingBuffer: TSPSCRingBuffer): SPSC_PTRUINT;begin{$PUSH}{$Q-}{$R-}  Result := SPSC_MaskIndex(ARingBuffer, ARingBuffer.FWriteIndex -  ARingBuffer.FReadIndex);{$POP}end; function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;begin  Result := ARingBuffer.FBuffer[SPSC_MaskIndex(ARingBuffer,  ARingBuffer.FReadIndex)];{$PUSH}{$Q-}  Inc(ARingBuffer.FReadIndex);{$POP}end; procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte);begin  ARingBuffer.FBuffer[SPSC_MaskIndex(ARingBuffer, ARingBuffer.FWriteIndex)] := AValue;{$PUSH}{$Q-}  Inc(ARingBuffer.FWriteIndex);{$POP}end; end.  EDIT: wrong quote .... regards, ---------------------------------------------------------------------- d.ioannidis · 2022-10-12 18:03 Hi, Quote from: y.ivanov on October 12, 2022, 07:32:35 pm... even the bit- wise and isn't needed because it is achieved naturally by the limited length of the register ...  the bit-wise AND is needed in the case the buffer size is smaller of the index type max value.   i.e. If the index are type of byte and the buffer size is 64 instead of 128 the "index AND (size - 1)" clamps the value into the buffer size range .  At least this is how I understand it. regards, ---------------------------------------------------------------------- alpine · 2022-10-12 18:17 Quote from: d.ioannidis on October 12, 2022, 08:03:08 pmHi, Quote from: y.ivanov on October 12, 2022, 07:32:35 pm... even the bit- wise and isn't needed because it is achieved naturally by the limited length of the register ...  the bit-wise AND is needed in the case the buffer size is smaller of the index type max value.   i.e. If the index are type of byte and the buffer size is 64 instead of 128 the "index AND (size - 1)" clamps the value into the buffer size range .  At least this is how I understand it. regards, Right, (x mod 2^n) is same as (x and (2^n-1)). In the case when we're incrementing a BYTE with a value of $FF, the carry from the seventh bit to the eight (which is not present) just vanishes, it is same as to make ($10000 and $FFFF) - the result is zero. ---------------------------------------------------------------------- hakelm · 2025-02-16 14:56 Happened to see this. Here is a little ringbuffer if someone is interested: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i unit ringbuffer; {$mode ObjFPC}{$H+} interface uses  Classes, SysUtils;type  tdata=integer;  tdataarr=array of tdata;  { tringbuffer }   tringbuffer=class  private    fdata:tdataarr;    mask:integer;    indexofzero:integer;    function getdata(age: integer): tdata;    procedure setdata(age: integer; AValue: tdata);  public    constructor create(asize:integer);    property data[age:integer]:tdata read getdata write setdata; //use only to alter data w:o adding new items  procedure put(avalue:tdata);  //inserts a new item updates indexofzero  end; implementation { tringbuffer } function tringbuffer.getdata(age: integer): tdata;begin  age:=(age+indexofzero) and mask;  result:=fdata[age];end; procedure tringbuffer.setdata(age: integer; AValue: tdata);begin  age:=(age+indexofzero) and mask;  fdata[age]:=avalue;end; constructor tringbuffer.create(asize: integer);begin  mask:=1;  while mask application is in the middle of accessing the RxBuffer    repeat       try I:=fpRead(SerialHandle, @Buffer[1], 250) except I:=-1 end;   // adding @ suppresses a compiler note, seems to still work ok        if I>0 then begin                                              // data has been read in from serial port                  SetLength(Buffer, I);                     for J:=1 to length(Buffer) do                    begin                      ch:=Buffer[J];                      K:=(RxBuffer.head+1) mod sizeof(RxBuffer.data);                       if K<>RxBuffer.tail then                      begin                        RxBuffer.data[RxBuffer.head]:=ch;              // insert character into ring buffer                        RxBuffer.head:=K                             // increment head index                      end                  end                  end else      if I<0 then begin                                              // ERROR - disconnect and advise main program                    CONNECTED:=false;                  try fpClose(SerialHandle) except end                  end     until not CONNECTED or (I<=0)                                      // keep reading until disconnected or nothing to read  endend; (SerialHandle, CONNECTED, and ExitThreads defined elsewhere) ... and a regular timer event that processes data from the ring buffer with the aid of a few 'helper' functions: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i // returns how much time has elapsed since GetTickCount64 was assigned to a counter// (placed up here as is used within serial.inc)function timesince(counter:int64):int64;begin  result:=GetTickCount64-counterend;   function ReadSerialQueue(var ch:char; timeout:int64):boolean;          // read (any) single character , with timeoutvar TimeFlag:boolean;        mark:int64;         I:integer;           B:boolean;begin  ch:=#00;                                                           // returns character set to #00 if nothing to read  mark:=GetTickCount64;   RxBuffer.skip:=true;       { lock access }  B:=(RxBuffer.head=RxBuffer.tail);  RxBuffer.skip:=false;        { free access }   if (timeout<>0) and B then  repeat                                                             // may NOT pass through -> TimeFlag MAY be undefined    Application.ProcessMessages;    TimeFlag:=(timesince(mark)>timeout);     RxBuffer.skip:=true;       { lock access }    B:=(RxBuffer.head<>RxBuffer.tail);    RxBuffer.skip:=false       { free access }  until B or TimeFlag;   RxBuffer.skip:=true;         { lock access }  B:=(RxBuffer.head=RxBuffer.tail);  RxBuffer.skip:=false;        { free access }   if B then result:=false else  begin    RxBuffer.skip:=true;       { lock access }    I:=RxBuffer.tail;    RxBuffer.skip:=false;      { free access }     ch:=RxBuffer.data[I];    I:=(I+1) mod sizeof(RxBuffer.data);     RxBuffer.skip:=true;       { lock access }    RxBuffer.tail:=I;    RxBuffer.skip:=false;      { free access }    result:=true  endend; Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure TForm1.Timer1Timer(Sender: TObject); begin  if ReadSerialQueue(ch, 0) then then write(ch)end; the above is all code i just clipped out of a much larger project and purged of superfluous stuff that wasn't relevant here (like a 2nd ring buffer for TxData and handled by the same serial thread). so i might have broken something in the process! cheers, rob   :-) ---------------------------------------------------------------------- Thaddy · 2025-02-17 14:24 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. ---------------------------------------------------------------------- robert rozee · 2025-02-17 15:30 Quote from: Thaddy on February 17, 2025, 03:24:20 pmYou 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 · 2025-02-17 16:20 Quote from: robert rozee on February 17, 2025, 04:30:23 pmQuote from: Thaddy on February 17, 2025, 03:24:20 pmYou 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 · 2025-02-17 17:07 Quote from: robert rozee on February 17, 2025, 03:16:32 pman 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 · 2025-02-17 17:49 Quote from: Thaddy on February 17, 2025, 03:24:20 pmRobert, 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 QuoteThe 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 · 2025-02-17 21:00 Quote from: Thaddy on February 17, 2025, 05:20:00 pmYou 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 · 2025-02-18 07:37 Quote from: robert rozee on February 17, 2025, 10:00:33 pmi 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 · 2025-02-18 08:30 Quote from: Thaddy on February 18, 2025, 08:37:40 amQuote from: robert rozee on February 17, 2025, 10:00:33 pmi said a ringbuffer has a head and a tailWrong. 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i const RxBuffer:record                                    // serial input (ring) buffer                 data:array [0..$3FFFF] of char;         // 256k                 head:integer;                 tail:integer;               skip:boolean               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 · 2025-02-18 10:26 Quote from: robert rozee on February 18, 2025, 09:30:47 amdoes 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 · 2025-02-18 11:30 It just shows Rob doesn't have a clue about theory. Period. ---------------------------------------------------------------------- silvercoder70 · 2025-02-18 21:50 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 · 2025-02-19 07:04 Hi Here's another example of a circular buffer / queue:Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i unit cirqueue;{$mode ObjFPC}{$H+} {$Interfaces COM}{-$define dbg}interfaceuses classes, sysutils;const  cqVersion = '1.04.01.2025';  cqGrowFactor = 1.618; { the golden ratio :o) }type  { callback proc to dispose of data in the 'Clear'ing methods when freeing the container    sig: procedure FreePtr(aPtr: pointer); }  TDisposeProc = procedure(aPtr: pointer);  {$if fpc_fullversion <= 30202} RTLString = ansistring; {$endif} { introduced in trunk }  { TCirQueue ~ enqueues on tail & dequeues on head }  TCirQueue = class(TInterfacedObject{,ICirQueue})  private    fCount,fHead,fTail: ptrint;    fDispose: TDisposeProc; { for use in Clear }    fQue: TFPList;    procedure Grow;  public    constructor Create(aCapacity: ptrint;aDisposeProc: TDisposeProc = nil);    destructor Destroy;override;     function Capacity: ptrint;    procedure Clear;  function Count: ptrint;    function Dequeue: pointer;    procedure Enqueue(aData: pointer);    function IsEmpty: boolean;    function Peek: pointer;    function ToString: RTLString; override;  end;  implementation procedure DummyDisp(aPtr: pointer); // null-procbegin  if aPtr = nil then ; { do absolutely nothing }end; {$Region 'TCirQueue'}{ TCirQueue }procedure TCirQueue.Grow;var li,lt: ptrint;begin { we'll expand with the golden ratio items added ~ 61,8 % }   li:= trunc(fQue.Count * cqGrowFactor);  fQue.Count:= li;  if (fHead = 0) then fTail:= fCount { only enqueueing has been done, no dequeueing }  else begin { tail caught up, make room in between tail and head again, }    lt:= fQue.Count; { afterall we're growing due to lack of space }    for li:= fCount-1 downto fHead do begin      dec(lt);      fQue[lt]:= fQue[li];    end;    fHead:= lt;  end;end; constructor TCirQueue.Create(aCapacity: ptrint;aDisposeProc: TDisposeProc);begin  inherited Create;  { assign our disposeproc, if nil then we'll just use a dummy 'null' proc }  if aDisposeProc <> nil then fDispose:= aDisposeProc else fDispose:= @DummyDisp;  fQue:= TFPList.Create;  if (aCapacity <= 1) then aCapacity:= 32;  fQue.Count:= aCapacity;  fHead:= 0; fTail:= fHead; fCount:= 0;end; destructor TCirQueue.Destroy;begin  Clear;  fQue.Free;  {$ifdef dbg}writeln('TCirQueue Destroyed');{$endif}  inherited Destroy;end; function TCirQueue.Capacity: ptrint;begin  Result:= fQue.Capacity;end; procedure TCirQueue.Clear;begin { we only clear the residue active items left in the queue }  while not IsEmpty do fDispose(Dequeue);  fHead:= 0; fTail:= fHead; fCount:= 0; { here fTail:= fHead; means empty }end; function TCirQueue.Count: ptrint;begin  Result:= fCount;end; function TCirQueue.Dequeue: pointer;begin  if fCount = 0 then exit(nil);  Result:= fQue[fHead];  fHead:= (fHead + 1) mod fQue.Count; { inc but make sure it's still valid }  dec(fCount);end; procedure TCirQueue.Enqueue(aData: pointer);begin  fQue[fTail]:= aData;  fTail:= (fTail + 1) mod fQue.Count;  inc(fCount);  if (fTail = fHead) then Grow; { here this means full, so we'll grow it a bit }end; function TCirQueue.IsEmpty: boolean;begin  Result:= (fCount = 0);end; function TCirQueue.Peek: pointer;begin { a small test-case, to see if direct access is snappier }  if fCount > 0 then Result:= fQue[fHead] else Result:= nil;end; function TCirQueue.ToString: RTLString;begin  Result:= 'I/TCirQueue v '+cqVersion+', a circular self-growing queue '+LineEnding+           '(c) 2025 Copyright Benny Christensen a.k.a. cdbc, All rights reserved';end;{$EndRegion 'TCirQueue'} end. 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