helpers::circular_buffer

Module 0xc0ded0c0::circular_buffer

module helpers::circular_buffer

This module serves to provide an efficient data structure for the implementation of the online oracle.

• module helpers::circular_buffer

• Struct CircularBuffer

• Constants

• Function empty

• Function length

• Function borrow_oldest

  • Abort conditions

• Function borrow_newest

• Function push

• Function burn_all

use 0x1::error;
use 0x1::vector;
use 0xc0ded0c0::math;

Struct CircularBuffer

This struct is a wrapper on std::vector, which deals with a circular rather than linear data structure. An online oracle that stores observation is one use case for it.

struct CircularBuffer<T: drop, store> has store

Fields

buffer: vector<T>Circular buffer storagelast_index: u64Index of the last observation/entry that was added to the buffer

Constants

When the buffer is empty and a borrow of the oldest items is requested.

const EEMPTY_BUFFER: u64 = 0;

Function empty

Create an empty circular buffer

public fun empty<T: drop, store>(): circular_buffer::CircularBuffer<T>

Implementation

public fun empty<T: store + drop>(): CircularBuffer<T> {
    // last_index starts with 0 instead of None for convenience; see push
    return CircularBuffer{ buffer: vector::empty<T>(), last_index: 0 }
}

Specification

ensures len(result.buffer) == 0;
ensures result.last_index == 0;

Function length

Returns the length of the buffer

public fun length<T: drop, store>(cbuffer: &circular_buffer::CircularBuffer<T>): u64

Implementation

public fun length<T: store + drop>(cbuffer: &CircularBuffer<T>): u64 {
    vector::length(&cbuffer.buffer)
}

Specification

ensures len(cbuffer.buffer) == result;

fun helper_round_robin(a: u64, b: u64): u64 {
   assert!(b > 0 && a <= b, error::invalid_argument(0));
   if (a < b) {
       a
   }
   else {
       0
   }
}

Function borrow_oldest

Returns the oldest observation in the circular buffer.

Abort conditions

• If the buffer is empty

public fun borrow_oldest<T: drop, store>(cbuffer: &circular_buffer::CircularBuffer<T>): &T

Implementation

public fun borrow_oldest<T: store + drop>(
    cbuffer: &CircularBuffer<T>
): &T {
    let length = vector::length(&cbuffer.buffer);
    assert!(length > 0, error::not_found(EEMPTY_BUFFER));

    let oldest_index = math::round_robin(cbuffer.last_index +1, length);

    vector::borrow(
        &cbuffer.buffer,
        oldest_index,
    )
}

Specification

aborts_if cbuffer.last_index + 1 > len(cbuffer.buffer);
aborts_if len(cbuffer.buffer) == 0;
let oldest_index = helper_round_robin(cbuffer.last_index +1, len(cbuffer.buffer));
ensures result == cbuffer.buffer[oldest_index];

Function borrow_newest

Returns the newest observation in the circular buffer

public fun borrow_newest<T: drop, store>(cbuffer: &circular_buffer::CircularBuffer<T>): &T

Implementation

public fun borrow_newest<T: store + drop>(cbuffer: &CircularBuffer<T>): &T {
    vector::borrow(
        &cbuffer.buffer,
        cbuffer.last_index,
    )
}

Function push

Push value value to the circular buffer cbuffer, assuming that max_length is the size of the buffer.

public fun push<T: drop, store>(cbuffer: &mut circular_buffer::CircularBuffer<T>, value: T, max_length: u64)

Implementation

public fun push<T: store + drop>(
    cbuffer: &mut CircularBuffer<T>,
    value: T,
    max_length: u64, // current buffer capacity
) {
    let current_length = vector::length(&cbuffer.buffer);

    // This if condition ensures that we don't increase last_index,
    // as it was initialized with zero already
    if (current_length == 0) {
        vector::push_back<T>(&mut cbuffer.buffer, value);
        return
    };

    if (current_length < max_length) {
        // Add the new entry
        vector::push_back<T>(&mut cbuffer.buffer, value);

        // Rest of the if statement handles increase in buffer capacity
        let i = cbuffer.last_index;
        if (i < current_length - 1) {
            // We can end up here only if `max_length` has been increased.
            // That implies that we added the new entry at the last
            // position, but it does not belong there.
            while (i + 1 < current_length) {
                vector::swap<T>(&mut cbuffer.buffer, current_length, i + 1);
                i = i + 1;
            }
        };
    } else {
        let oldest_index = math::round_robin(
            cbuffer.last_index + 1,
            current_length
        );
        let oldest_value = vector::borrow_mut<T>(
            &mut cbuffer.buffer,
            oldest_index
        );
        *oldest_value = value;
    };

    // Finally, we set what the next index would be
    cbuffer.last_index = math::round_robin(
        cbuffer.last_index + 1,
        max_length
    );
}

Specification

Function burn_all

Remove all observations from the circular buffer and destroy the buffer itself.

public fun burn_all<T: drop, store>(cbuffer: circular_buffer::CircularBuffer<T>)

Implementation

public fun burn_all<T: store + drop>(cbuffer: CircularBuffer<T>) {
    let CircularBuffer {buffer: buffer, last_index : _a } = cbuffer;
    while (!vector::is_empty(&buffer)) {
        let _observation = vector::pop_back<T>(&mut buffer);
    };
    vector::destroy_empty<T>(buffer);
}