A circular buffer implementation

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
badidea
Posts: 1570
Joined: May 24, 2007 22:10
Location: The Netherlands

A circular buffer implementation

Postby badidea » Nov 05, 2019 21:57

A circular (or ring) buffer (https://en.wikipedia.org/wiki/Circular_buffer) that allows overwrite (when full, new data overwrites the 'oldest' data). Data is never removed / popped from buffer, only added and contents read. But 'popping' can probably be added; I don't need that.
I plan to this for a 'rolling oscilloscope' function in my power logger/plotter program (for the TPlink HS110 device).

Code: Select all

'-------------------------- Example data type ----------------------------------

type data_type
   dim as double absTime
   dim as integer sample
   declare constructor()
   declare constructor(absTime as double, sample as integer)
   declare operator cast() as string
end type

constructor data_type()
   this.absTime = 0.0 : this.sample = 0
end constructor

constructor data_type(absTime as double, sample as integer)
   this.absTime = absTime : this.sample = sample
end constructor

operator data_type.cast() as string
  return str(absTime) & "," & str(sample)
end operator

'---------------------------- Circular buffer ----------------------------------

type rolling_buffer_type
   private:
   dim as data_type myData(any)
   dim as integer first, reader, numRead, numData, bufferSize
   public:
   declare constructor(dataSize as integer)
   declare destructor()
   declare function add(newData as data_type) as integer
   declare sub readerReset()
   declare function getValue(byref readData as data_type) as integer
   declare sub show()
end type

constructor rolling_buffer_type(bufferSize as integer)
   redim myData(bufferSize - 1)
   this.bufferSize = bufferSize
end constructor

destructor rolling_buffer_type()
   erase myData
   bufferSize = 0
end destructor

function rolling_buffer_type.add(newData as data_type) as integer
   dim as integer index
   if numData < bufferSize then
      'add data
      index = first + numData
      if index >= bufferSize then index -= bufferSize
      numData += 1
      myData(index) = newData
   else
      'replace data
      myData(first) = newData
      first += 1 'move first pointer
      if first >= bufferSize then first -= bufferSize
   end if
   return 0 'always zero for now
end function

'normally not needed
sub rolling_buffer_type.readerReset()
   numRead = 0
end sub

'returns -1 when last item is reached
function rolling_buffer_type.getValue(byref readData as data_type) as integer
   if numData > numRead then
      reader = first + numRead
      if reader >= bufferSize then reader -= bufferSize
      readData = myData(reader)
      numRead += 1
      return 0
   else
      numRead = 0
      return -1
   end if
end function

'for debugging
sub rolling_buffer_type.show()
   print "bufferSize: " & bufferSize
   print "numData: " & numData
   print "numRead: " & numRead
   print "first: " & first
   print "reader: " & reader
   for i as integer = 0 to bufferSize - 1
      print myData(i)
   next
end sub

'----------------------------- Main program ------------------------------------

'create a buffer for 4 items
dim as rolling_buffer_type buffer = rolling_buffer_type(4)
dim as data_type readData

'add 3 items
for i as integer = 1 to 3
   buffer.add(data_type(i, i))
next

'read and print buffer contents
print "Buffer:"
while buffer.getValue(readData) = 0
   print readData
wend

'add 2 more items, last one overwrites the first
for i as integer = 4 to 5
   buffer.add(data_type(i, i))
next

'read and print buffer contents
print "Buffer:"
while buffer.getValue(readData) = 0
   print readData
wend
badidea
Posts: 1570
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: A circular buffer implementation

Postby badidea » Nov 05, 2019 22:39

Popping added:

Code: Select all

'-------------------------- Example data type ----------------------------------

type data_type
   dim as double absTime
   dim as integer sample
   declare constructor()
   declare constructor(absTime as double, sample as integer)
   declare operator cast() as string
end type

constructor data_type()
   this.absTime = 0.0 : this.sample = 0
end constructor

constructor data_type(absTime as double, sample as integer)
   this.absTime = absTime : this.sample = sample
end constructor

operator data_type.cast() as string
  return str(absTime) & "," & str(sample)
end operator

'---------------------------- Circular buffer ----------------------------------

type rolling_buffer_type
   private:
   dim as data_type myData(any)
   dim as integer first, reader, numRead, numData, bufferSize
   public:
   declare constructor(dataSize as integer)
   declare destructor()
   declare function add(newData as data_type) as integer
   declare function pop(byref readData as data_type) as integer
   declare sub readerReset()
   declare function getValue(byref readData as data_type) as integer
   declare function getNumData() as integer
   declare sub show()
end type

constructor rolling_buffer_type(bufferSize as integer)
   redim myData(bufferSize - 1)
   this.bufferSize = bufferSize
end constructor

destructor rolling_buffer_type()
   erase myData
   bufferSize = 0
end destructor

function rolling_buffer_type.add(newData as data_type) as integer
   dim as integer index
   if numData < bufferSize then
      'add data
      index = first + numData
      if index >= bufferSize then index -= bufferSize
      numData += 1
      myData(index) = newData
   else
      'replace data
      myData(first) = newData
      first += 1 'move first pointer
      if first >= bufferSize then first -= bufferSize
   end if
   return 0 'always zero for now
end function

'Get and remove first / oldest item from list
'don't mix / interleave with getValue calls
function rolling_buffer_type.pop(byref readData as data_type) as integer
   if numData > 0 then
      readData = myData(first)
      first += 1
      if first >= bufferSize then first -= bufferSize
      numData -= 1
   else
      return -1
   end if
end function

'normally not needed
sub rolling_buffer_type.readerReset()
   numRead = 0
end sub

'returns -1 when last item is reached
function rolling_buffer_type.getValue(byref readData as data_type) as integer
   if numData > numRead then
      reader = first + numRead
      if reader >= bufferSize then reader -= bufferSize
      readData = myData(reader)
      numRead += 1
      return 0
   else
      numRead = 0
      return -1
   end if
end function

function rolling_buffer_type.getNumData() as integer
   return numData
end function

'for debugging
sub rolling_buffer_type.show()
   print "bufferSize: " & bufferSize
   print "numData: " & numData
   print "numRead: " & numRead
   print "first: " & first
   print "reader: " & reader
   for i as integer = 0 to bufferSize - 1
      print myData(i)
   next
end sub

'----------------------------- Main program ------------------------------------

'create a buffer for 4 items
dim as rolling_buffer_type buffer = rolling_buffer_type(4)
dim as data_type readData

'add 3 items
for i as integer = 1 to 3
   buffer.add(data_type(i, i))
next

'read and print buffer contents
print "Buffer (after 3 items added):"
while buffer.getValue(readData) = 0
   print readData
wend

'add 2 more items, last one overwrites the first
for i as integer = 4 to 5
   buffer.add(data_type(i, i))
next

'read and print buffer contents
print "Buffer (after 2 more added):"
while buffer.getValue(readData) = 0
   print readData
wend

'pop first item from list
print "Removed item:"
if buffer.pop(readData) = 0 then
   print readData
end if

'read and print buffer contents
print "Buffer (after 1 item removed):"
while buffer.getValue(readData) = 0
   print readData
wend

'pop all remaing items from list
print "Removed items:"
while buffer.pop(readData) = 0
   print readData
wend

print "Number of items in buffer: " & buffer.getNumData()
sero
Posts: 25
Joined: Mar 06, 2018 13:26
Location: USA

Re: A circular buffer implementation

Postby sero » Nov 07, 2019 2:49

I really like this idea. I can imagine using this for my own project. I need to replace off screen data with incoming data to replace it. I have a similar method in place already for map data but when it gets more complex I'll want something more robust. This makes me think of how the early side scroller games worked by replacing off screen data with the new screen data. I think I remember that being a new thing when Carmack worked on a Mario brothers clone for the PC. It turned into the Commander Keen series after Nintendo told him no thanks.
badidea
Posts: 1570
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: A circular buffer implementation

Postby badidea » Nov 07, 2019 20:36

sero wrote:I really like this idea. I can imagine using this for my own project. I need to replace off screen data with incoming data to replace it. I have a similar method in place already for map data but when it gets more complex I'll want something more robust. This makes me think of how the early side scroller games worked by replacing off screen data with the new screen data. I think I remember that being a new thing when Carmack worked on a Mario brothers clone for the PC. It turned into the Commander Keen series after Nintendo told him no thanks.

If a map (of tiles indexes) is not too big, you can keep the whole map in memory. And in addition an array of the tiles images. During the game you only draw the tiles that are visible. No need to copy maps during drawing. I have posted some demo's in the past, lets if I can find them...
* One with hexagon tiles: viewtopic.php?f=7&t=21153
* Oblique view and square tiles: viewtopic.php?f=15&t=24464
(not tested with new compiler versions)
For a large or infinite map, the method often used is to load (and unload) 'chunks' of map sections.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 1 guest