Circular Buffer

CircularBuffer

Vom Prinzip ein FiFo Buffer (auch Queue oder Stapel genannt), allerdings mit erweiterten Möglichkeiten. Es wird mit einer festen Speichergröße gearbeitet, es werden also immens viel an Speicheroperationen wie Vergrößern / Verkleinern / Kopieren eingespart, außerdem verfügt der Speicher neben dem üblichen Push (Daten auf den Speicher legen) und Pull (Daten aus dem Speicher ziehen) auch über eine Peek Funktion (Daten aus dem Speicher lesen, ohne diese zu entfernen). Das ist sinnvoll für Kommunikationsprotokolle wie TLV um vorweg zu prüfen ob genügend Daten eingegangen sind, ohne den Datenstrom zu beeinträchtigen.

VB.Net

' LICENSE (MIT)
'
' Copyright 2019 Thomas Baumann - tightDev.Net
' 
' Permission is hereby granted, free of charge, to any person obtaining a copy of this
' software and associated documentation files (the "Software"), to deal in the Software
' without restriction, including without limitation the rights to use, copy, modify, merge,
' publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to
' whom the Software is furnished to do so, subject to the following conditions:
'
' The above copyright notice and this permission notice shall be included in all copies or
' substantial portions of the Software.
'
' THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
' EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
' MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
' NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
' HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
' IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
' IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
' SOFTWARE.

Imports System.Runtime.InteropServices
Imports System.IO

''' <summary>
'''     Class represents a circular buffer for storing received data, FIFO principle.
'''     <br/>Other than existing classes this one can be used to validate the data first, because you
'''     can read and validate the data before removing it from the buffer.
''' </summary>
''' <remarks>Uses a fixed size, self overwritten buffer for performance reason.</remarks>
''' <example>
'''     This small code example demonstrates how to use this buffer and it's functions.
'''     <code lang="vb">
'''         ' Create the CircularBuffer with the default size (256 bytes)
'''         Dim Buffer As New Core.CircularBuffer
'''         ' --- or ---
'''         ' Create the CircularBuffer with a size of 1024 bytes)
'''         Dim Buffer As New Core.CircularBuffer(1024)
'''
'''         ' Our data which we want to process
'''         Dim Data As Byte()
'''
'''         ' Push data into the circular buffer
'''         Data = New Byte() {1, 2, 3, 4}
'''         Buffer.Push(Data)
'''         Data = New Byte() {5, 6, 7, 8}
'''         Buffer.Push(Data)
'''
'''         ' Buffer contains values 1, 2, 3, 4, 5, 6, 7, 8
'''
'''         ' Read the data back, removing it from buffer
'''         Data = Buffer.Pull(2) ' Read 2 bytes
'''
'''         ' Data contains values 1, 2
'''         ' Buffer contains values 3, 4, 5, 6, 7, 8
'''
'''         ' Read the data back, without removing it from buffer
'''         Data = Buffer.Peek(2) ' Read 2 bytes
'''
'''         ' Data contains values 3, 4
'''         ' Buffer contains values 3, 4, 5, 6, 7, 8
'''     </code>
'''     <code lang="cs">
'''         // Create the CircularBuffer with the default size (256 bytes)
'''         Core.CircularBuffer Buffer = new Core.CircularBuffer();
'''         // --- or ---
'''         // Create the CircularBuffer with a size of 1024 bytes)
'''         Core.CircularBuffer Buffer = new Core.CircularBuffer(1024);
'''
'''         // Our data which we want to process
'''         byte[] Data;
'''
'''         // Push data into the circular buffer
'''         Data = new byte[] {1, 2, 3, 4};
'''         Buffer.Push(Data);
'''         Data = new byte[] {5, 6, 7, 8};
'''         Buffer.Push(Data);
'''
'''         //  Buffer contains values 1, 2, 3, 4, 5, 6, 7, 8
'''
'''         //  Read the data back, removing it from buffer
'''         Data = Buffer.Pull(2);    // read 2 bytes
'''
'''         //  Data contains values 1, 2
'''         //  Buffer contains values 3, 4, 5, 6, 7, 8
'''
'''         //  Read the data back, without removing it from buffer
'''         Data = Buffer.Peek(2);    // read 2 bytes
'''
'''         //  Data contains values 3, 4
'''         //  Buffer contains values 3, 4, 5, 6, 7, 8
'''     </code>
''' </example>
Friend NotInheritable Class CircularBuffer

#Region "  Private variables  "

	''' <summary>The access timeout in milliseconds. Default 1000 (1 second).</summary>
	Const Timeout As Int32 = 1000

	''' <summary>The internal data store (buffer).</summary>
	Private Buffer As Byte()

	''' <summary>Lock object for the buffer.</summary>
	Private Lock As New Threading.ReaderWriterLock

	''' <summary>The current read position.</summary>
	Private ReadPos As Integer

	''' <summary>The current write position.</summary>
	Private WritePos As Integer

	''' <summary>True if Read and Write position are equal and the data wasn't read yet.</summary>
	''' <remarks></remarks>
	Private IsFull As Boolean

#End Region
#Region "  Public/Friend acessors  "

	''' <summary>Creates a new instance of this class and allocates 256 bytes of buffer memory.</summary>
	''' <remarks>
	'''     Capacity should be at least twice than the size of the maximum received data you expect.
	'''     Without specifying a capacity the buffer size is 256 bytes. Anyway, the capacity should be
	'''     at least twice than the size of the maximum received data you exept.
	''' </remarks>
	Friend Sub New()

		Me.New(255)

	End Sub

	''' <summary>Creates a new instance of this class and allocates the required amount of buffer memory.</summary>
	''' <param name="Capacity">The capacity in bytes for this buffer in bytes.</param>
	''' <exception cref="ArgumentException">Thrown if capacity was set to 3 or below.</exception>
	''' <remarks>
	'''     Capacity should be at least twice than the size of the maximum received data you except.
	'''     <br/>Values below 64 are not recommended!
	''' </remarks>
	Friend Sub New(ByVal Capacity As Integer)

		If Capacity < 3 Then Throw New ArgumentException("Invalid capacity. Must be 3 or larger. Values below 64 are not recommended!", "Capacity")

		Lock.AcquireWriterLock(Timeout)
		ReDim Buffer(Capacity - 1)
		Lock.ReleaseWriterLock()

	End Sub

	''' <summary>Gets / Sets the buffer capacity.</summary>
	''' <remarks>If you set the value the whole buffer gets re-created and thus all data which is inside of it gets lost. Handle with care.</remarks>
	''' <exception cref="ArgumentException">Thrown if a new value below 3 was specified.</exception>
	Friend Property Capacity() As Integer
		Get
			Return Buffer.Length
		End Get
		Set(ByVal value As Integer)
			If value < 3 Then Throw New ArgumentException("New capacity must be 3 or larger.")
			Lock.AcquireWriterLock(Timeout)
			ReDim Buffer(value - 1)
			ReadPos = 0
			WritePos = 0
			Lock.ReleaseWriterLock()
		End Set
	End Property

	''' <summary>Returns the number of bytes the buffer contains.</summary>
	Friend ReadOnly Property Length() As Integer
		Get

			Lock.AcquireReaderLock(Timeout)
			If IsFull Then
				Return Buffer.Length
			Else
				If ReadPos = WritePos Then
					Length = 0
				ElseIf ReadPos < WritePos Then
					Length = WritePos - ReadPos
				Else
					Length = (Buffer.Length - ReadPos) + WritePos
				End If
			End If
			Lock.ReleaseReaderLock()

		End Get
	End Property

	''' <summary>Clears the buffer, thus removing any data which is stored inside of it.</summary>
	Friend Sub Clear()

		Lock.AcquireWriterLock(Timeout)
		ReadPos = 0
		WritePos = 0
		Lock.ReleaseWriterLock()

	End Sub

	''' <summary>Writes data to this buffer.</summary>
	''' <param name="Data">The data to write.</param>
	''' <exception cref="ArgumentException">Thrown if Data is Nothing / null or has a size of 0 bytes.</exception>
	''' <exception cref="InternalBufferOverflowException">Thrown if the data is larger as the the buffer can store (buffer overrun).</exception>
	Friend Sub Push(ByVal Data As Byte())

		If Data Is Nothing OrElse Data.Length = 0 Then Throw New ArgumentException("Are you serious to store nothing? 0.o", "Data")
		If Data.Length > Buffer.Length Then Throw New InternalBufferOverflowException("Received more data than the buffer capacity can store.")

		Lock.AcquireWriterLock(Timeout)
		If (WritePos + Data.Length) <= Buffer.Length Then
			' Data fits into buffer without splitting
			Array.Copy(Data, 0, Buffer, WritePos, Data.Length)
			WritePos += Data.Length
		Else
			' Data needs to be splitted
			Dim i As Integer = (WritePos + Data.Length) - Buffer.Length
			If ReadPos < i Then Throw New InternalBufferOverflowException("Received data would override unreaded data.")
			Array.Copy(Data, 0, Buffer, WritePos, Buffer.Length - WritePos)
			Array.Copy(Data, Data.Length - i, Buffer, 0, i)
			WritePos = i
			Console.WriteLine("CircularBuffer: Splitted data (Push)")
		End If
		If ReadPos = WritePos Then IsFull = True
		Lock.ReleaseWriterLock()

	End Sub

	''' <summary>Reads data from this buffer and removes it.</summary>
	''' <param name="Length">The length of the data to retrive.</param>
	''' <returns>Returns the requested data and releases it from the buffer.</returns>
	''' <exception cref="ArgumentException">Thrown if Length is 0 or less.</exception>
	''' <exception cref="InternalBufferOverflowException">Thrown if the requested data is larger as the data in the buffer (buffer underrun).</exception>
	Friend Function Pull(ByVal Length As Integer) As Byte()
		Return PullPeek(Length, False)
	End Function

	''' <summary>Reads data from this buffer without removing it.</summary>
	''' <param name="Length">The length of the data to retrive.</param>
	''' <exception cref="ArgumentException">Thrown if Length is 0 or less.</exception>
	''' <returns>Returns the requested data without removing it from the buffer.</returns>
	''' <exception cref="InternalBufferOverflowException">Thrown if the requested data is larger as the data in the buffer (buffer underrun).</exception>
	Friend Function Peek(ByVal Length As Integer) As Byte()
		Return PullPeek(Length, True)
	End Function

	''' <summary>Dumps the content of this buffer in hex form, together with read and write positions.</summary>
	''' <returns>The read and write position of this buffer and a hex-view of it's content.</returns>
	Friend Function Dump() As String

		Lock.AcquireReaderLock(Timeout)
		Dump = "ReadPos: " & ReadPos & "    WritePos: " & WritePos & HexView(Buffer)
		Lock.ReleaseReaderLock()

	End Function

	''' <summary>Searches the buffer for the given search byte(s) and returns the index of the first byte if found, -1 otherwise.</summary>
	''' <param name="Search">A Byte array of elements to search for.</param>
	''' <returns>Returns -1 if not found, otherwise the index where the first byte matched.</returns>
	Friend Function IndexOf(ByVal Search As Byte()) As Integer

		IndexOf = -1

		Lock.AcquireReaderLock(Timeout)
		Dim len As Integer = Length	' Buffer
		If len >= Search.Length Then
			For i As Integer = 0 To len - Search.Length
				Dim Found As Integer = 0
				For j As Integer = 0 To Search.Length - 1
					Dim Pos As Integer = (ReadPos + i + j) Mod Buffer.Length
					If Buffer(Pos) = Search(j) Then Found += 1
				Next
				If Found = Search.Length Then
					IndexOf = i
					Exit For
				End If
			Next
		End If
		Lock.ReleaseReaderLock()

	End Function

#End Region
#Region "  Internal helper  "

	''' <summary>Reads bytes from the buffer and returns it.</summary>
	''' <param name="Length">The number of bytes to read.</param>
	''' <param name="PeekOnly">If True the read position will left unchanged, so you can read it again (it remains in buffer).</param>
	''' <returns>The byte array you have requested.</returns>
	''' <exception cref="ArgumentException">Thrown if Length is 0 or less.</exception>
	''' <exception cref="InternalBufferOverflowException">Thrown if the requested data is larger as the data in the buffer (buffer underrun).</exception>
	Private Function PullPeek(ByVal Length As Integer, ByVal PeekOnly As Boolean) As Byte()

		If Length <= 0 Then Throw New ArgumentException("Are you serious to request 0 bytes or less? 0.o", "Length")
		If Length > Buffer.Length Then Throw New InternalBufferOverflowException("Requested more data than the buffer capacity can store.")

		Lock.AcquireReaderLock(Timeout)
		Dim RetVal(Length - 1) As Byte
		If (ReadPos + Length) <= Buffer.Length Then
			' Data is in buffer without being splitted
			Array.Copy(Buffer, ReadPos, RetVal, 0, Length)
			If Not PeekOnly Then ReadPos += Length
		Else
			' Data is splitted
			Dim l As Integer = (ReadPos + Length) - Buffer.Length
			If ReadPos < l Then Throw New InternalBufferOverflowException("Requested data length larger than stored data. Buffer underrun!")
			Array.Copy(Buffer, ReadPos, RetVal, 0, Length - l)
			Array.Copy(Buffer, 0, RetVal, Length - l, l)
			If Not PeekOnly Then ReadPos = l
			Console.WriteLine("CircularBuffer: Splitted data (Pull)")
		End If
		PullPeek = RetVal
		IsFull = False
		Lock.ReleaseReaderLock()

	End Function

#End Region

End Class