This module implements a circular buffer CircularBuffer and a markable circular buffer MarkableCircularBuffer that supports incremental marking.

Overview

CircularBuffer uses a fixed-length array as a storage container, and the two ends of the array are connected together. It does not need to have its elements shuffled around when one is consumed. This lends itself easily to buffering data streams.

At a certain moment, its storage state is similar to:

[   empty   |---data---|   empty  ]

see Circular buffer Wiki
see Circular buffer Wiki 中文

MarkableCircularBuffer inherits from CircularBuffer , and adds the function of incremental marking, allowing the data stored to be marked. Increment means that the next operation will always continue from the previous end position. Incremental marking simplifies some tedious tasks such as scanning, analysis and so on.

Storage methods

The circular buffer provides two storage methods: manual storage and automatic storage.

Manual storage is a low-level operation, which can obtain better performance but is more complicated. You need to directly manipulate the storable space involved in next and pack, and use copyMem, read(file, pointer, size) or other similar methods to directly store data. This is an unsafe method, but there is no additional copy, so you can get better performance.

Automatic storage is a high-level operation, storing data with add. This is a safer and simpler method, but it has additional copy overhead.

Marking

MarkableCircularBuffer allows marking data. marks() iterates the stored data one by one in the form of characters (bytes), and marks the characters (bytes) at the same time. This is especially useful for data analysis, such as searching a CRLF. When you find the desired mark, you can use popMarks to extract the marked data.

Increment

In most IO scenarios, you need to read or write data repeatedly. MarkableCircularBuffer provides incremental support for this environment, incrementally storing data and incrementally marking data, so that you don't have to worry about losing data state in a loop operation.

Thread safety

CircularBuffer and MarkableCircularBuffer does not guarantees thread safety. When you use them in multiple threads, you should be responsible for conditional competition.

Usage

Manual storage

Manual storage can be divided into three steps:

1. Gets the address and the length of a storable space：

var buffer = initMarkableCircularBuffer()
var (regionPtr, regionLen) = buffer.next()

2. Operates the storable space to store data：

var readLen = socket.read(regionPtr, regionLen)

3. Tell the buffer the length of the stored data：

var packLen = buffer.pack(n)

Automatic storage

To store a character:

var n = buffer.add('A')

To store a string:

var str = "ABC"
var n = buffer.add(str.cstring, 3)

Marking

To search a string ending with a newline character:

var buffer = initMarkableCircularBuffer()
var str = "foo\Lbar\L"
assert buffer.add(str.cstring, str.len) == str.len

var lineString = ""

for c in buffer.marks():
  if c == '\L':
    lineString = buffer.popMarks(1)
    break
assert lineString == "foo"

for c in buffer.marks():
  if c == '\L':
    lineString = buffer.popMarks(1)
    break
assert lineString == "bar"

markUntil makes this process easier:

var buffer = initMarkableCircularBuffer()
var str = "foo\Lbar\L"
assert buffer.add(str.cstring, str.len) == str.len

var lineString = ""

assert buffer.markUntil('\L')
assert lineString == "foo"

assert buffer.markUntil('\L')
assert lineString == "bar"

Read data

Copy the stored data to a specified memory and delete the data:

var buffer = initMarkableCircularBuffer()
var str = "foo\Lbar\L"
assert buffer.add(str.cstring, str.len) == str.len
assert buffer.len == str.len

var dest = newString(64)
var getLen = buffer.get(dest, destLen)
var delLen = buffer.del(getLen)
dest.setLen(getLen)

assert dest == "foo\Lbar\L"
assert buffer.len == 0

Copy the stored data to a string and delete the data:

var buffer = initMarkableCircularBuffer()
var str = "foo\Lbar\L"
assert buffer.add(str.cstring, str.len) == str.len
assert buffer.len == str.len

var foo = buffer.get(3)
assert foo == "foo"

Imports

../misc, constants

Types

CircularBuffer = object of RootObj value: array[0 .. BufferSize, byte] startPos: Natural endPos: Natural endMirrorPos: Natural: A circular buffer. Note that the maximum length of its storage space is BufferSize. Source Edit
MarkableCircularBuffer = object of CircularBuffer markedPos: Natural: A markable circular buffer. Source Edit

Procs

proc initCircularBuffer(): CircularBuffer {...}{.raises: [], tags: [].}

Initializes an CircularBuffer. Source Edit

proc capacity(b: CircularBuffer): Natural {...}{.inline, raises: [], tags: [].}

Returns the capacity of this buffer. Source Edit

proc len(b: CircularBuffer): Natural {...}{.inline, raises: [], tags: [].}

Returns the length of the data stored in this buffer. Source Edit

proc next(b: var CircularBuffer): (pointer, Natural) {...}{.raises: [], tags: [].}

Gets the next safe storage space. The return value includes the address and length of the storable space.

Examples:

var source = "Hello World"
var (regionPtr, regionLen) = buffer.next()
var length = min(regionLen, s.len)
copyMem(regionPtr, source.cstring, length)

Source Edit

proc pack(b: var CircularBuffer; size: Natural): Natural {...}{.raises: [], tags: [].}

Tells the buffer that size bytes from the current storage location are promoted to data. Returns the actual length promoted.

When next() is called, data is written to the storage space inside the buffer, but the buffer cannot know how much data was written. pack () tells the buffer the length of the data written.

Whenever next() is called, pack() should be called immediately.

Examples:

var source = "Hello World"
var (regionPtr, regionLen) = buffer.next()
var length = min(regionLen, s.len)
copyMem(regionPtr, source.cstring, length)
var n = buffer.pack(length)

Source Edit

proc add(b: var CircularBuffer; source: pointer; size: Natural): Natural {...}{.raises: [], tags: [].}

Copies up to size lengths of data from source and store the data in the buffer. Returns the actual length copied. This is a simplified version of the next pack combination call. The difference is that an additional copy operation is made instead of writing directly to the buffer.

Examples:

var source = "Hello World"
var n = buffer.add(source.cstring, source.len)

Source Edit

proc add(b: var CircularBuffer; c: char): Natural {...}{.raises: [], tags: [].}

Stores a character c in the buffer and returns the actual stored length. If the storage space is full, it will return 0, otherwise 1. Source Edit

proc get(b: var CircularBuffer; dest: pointer; size: Natural): Natural {...}{.raises: [], tags: [].}

Gets up to size of the stored data, and copy the data to the space dest. Returns the actual number copied. Source Edit

proc get(b: var CircularBuffer; size: Natural): string {...}{.raises: [], tags: [].}

Gets up to size of the stored data and returns as a string. Source Edit

proc get(b: var CircularBuffer): string {...}{.raises: [], tags: [].}

Gets all stored data and returns as a string. Source Edit

proc del(b: var CircularBuffer; size: Natural): Natural {...}{.raises: [], tags: [].}

Deletes up to size of the stored data and returns the actual number deleted. Source Edit

proc initMarkableCircularBuffer(): MarkableCircularBuffer {...}{.raises: [], tags: [].}

Initializes an MarkableCircularBuffer. Source Edit

proc del(b: var MarkableCircularBuffer; size: Natural): Natural {...}{.raises: [], tags: [].}

Deletes up to size of the stored data and returns the actual number deleted. Source Edit

proc mark(b: var MarkableCircularBuffer; size: Natural): Natural {...}{.raises: [], tags: [].}

Marks the stored data in the buffer immediately until it reaches size or reaches the end of the data. Returns the actual number marked.

Note that the marking is performed incrementally, that is, when the marking operation is called next time, it will continue from the position where it last ended.

Source Edit

proc markUntil(b: var MarkableCircularBuffer; c: char): bool {...}{.raises: [], tags: [].}

Marks the stored data one by one until a byte is c. false is returned if no byte is c.

Note that the marking is performed incrementally, that is, when the marking operation is called next time, it will continue from the position where it last ended.

Source Edit

proc markAll(b: var MarkableCircularBuffer) {...}{.raises: [], tags: [].}

Marks all the stored data.

Note that the marking is performed incrementally, that is, when the marking operation is called next time, it will continue from the position where it last ended.

Source Edit

proc lenMarks(b: MarkableCircularBuffer): Natural {...}{.inline, raises: [], tags: [].}

Returns the length of the stored data that has been marked. Source Edit

proc popMarks(b: var MarkableCircularBuffer; n: Natural = 0): string {...}{.raises: [], tags: [].}

Pops the marked data, skip the data from the end forward by n bytes, and return it as a string. At the same time, delete these data. Source Edit

Iterators

iterator items(b: CircularBuffer): char {...}{.raises: [], tags: [].}

Iterates over the stored data. Source Edit

iterator marks(b: var MarkableCircularBuffer): char {...}{.raises: [], tags: [].}

Iterate over the stored data, and marks the data at the same time.

Note that the marking is performed incrementally, that is, when the marking operation is called next time, it will continue from the position where it last ended.

var s = "Hello World\R\L"
var n = b.put(s.cstring, s.len)

for c in b.marks():
  if c == '\L':
    break

Source Edit

netkit/buffer/circular