Module 0x2::linked_table

Similar to sui::table but the values are linked together, allowing for ordered insertion and removal

• Resource LinkedTable
• Struct Node
• Constants
• Function new
• Function front
• Function back
• Function push_front
• Function push_back
• Function borrow
• Function borrow_mut
• Function prev
• Function next
• Function remove
• Function pop_front
• Function pop_back
• Function contains
• Function length
• Function is_empty
• Function destroy_empty
• Function drop

use 0x1::option;
use 0x2::dynamic_field;
use 0x2::object;
use 0x2::tx_context;

Resource LinkedTable

struct LinkedTable<K: copy, drop, store, V: store> has store, key

Fields

id: object::UID

the ID of this table

size: u64

the number of key-value pairs in the table

head: option::Option<K>

the front of the table, i.e. the key of the first entry

tail: option::Option<K>

the back of the table, i.e. the key of the last entry

Struct Node

struct Node<K: copy, drop, store, V: store> has store

Fields

prev: option::Option<K>

the previous key

next: option::Option<K>

the next key

value: V

the value being stored

Constants

const ETableNotEmpty: u64 = 0;

const ETableIsEmpty: u64 = 1;

Function new

Creates a new, empty table

public fun new<K: copy, drop, store, V: store>(ctx: &mut tx_context::TxContext): linked_table::LinkedTable<K, V>

Implementation

public fun new<K: copy + drop + store, V: store>(ctx: &mut TxContext): LinkedTable<K, V> {
    LinkedTable {
        id: object::new(ctx),
        size: 0,
        head: option::none(),
        tail: option::none(),
    }
}

Function front

Returns the key for the first element in the table, or None if the table is empty

public fun front<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>): &option::Option<K>

Implementation

public fun front<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>): &Option<K> {
    &table.head
}

Function back

Returns the key for the last element in the table, or None if the table is empty

public fun back<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>): &option::Option<K>

Implementation

public fun back<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>): &Option<K> {
    &table.tail
}

Function push_front

Inserts a key-value pair at the front of the table, i.e. the newly inserted pair will be the first element in the table Aborts with sui::dynamic_field::EFieldAlreadyExists if the table already has an entry with that key k: K.

public fun push_front<K: copy, drop, store, V: store>(table: &mut linked_table::LinkedTable<K, V>, k: K, value: V)

Implementation

public fun push_front<K: copy + drop + store, V: store>(
    table: &mut LinkedTable<K, V>,
    k: K,
    value: V,
) {
    let old_head = table.head.swap_or_fill(k);
    if (table.tail.is_none()) table.tail.fill(k);
    let prev = option::none();
    let next = if (old_head.is_some()) {
        let old_head_k = old_head.destroy_some();
        field::borrow_mut<K, Node<K, V>>(&mut table.id, old_head_k).prev = option::some(k);
        option::some(old_head_k)
    } else {
        option::none()
    };
    field::add(&mut table.id, k, Node { prev, next, value });
    table.size = table.size + 1;
}

Function push_back

Inserts a key-value pair at the back of the table, i.e. the newly inserted pair will be the last element in the table Aborts with sui::dynamic_field::EFieldAlreadyExists if the table already has an entry with that key k: K.

public fun push_back<K: copy, drop, store, V: store>(table: &mut linked_table::LinkedTable<K, V>, k: K, value: V)

Implementation

public fun push_back<K: copy + drop + store, V: store>(
    table: &mut LinkedTable<K, V>,
    k: K,
    value: V,
) {
    if (table.head.is_none()) table.head.fill(k);
    let old_tail = table.tail.swap_or_fill(k);
    let prev = if (old_tail.is_some()) {
        let old_tail_k = old_tail.destroy_some();
        field::borrow_mut<K, Node<K, V>>(&mut table.id, old_tail_k).next = option::some(k);
        option::some(old_tail_k)
    } else {
        option::none()
    };
    let next = option::none();
    field::add(&mut table.id, k, Node { prev, next, value });
    table.size = table.size + 1;
}

Function borrow

Immutable borrows the value associated with the key in the table table: &LinkedTable<K, V>. Aborts with sui::dynamic_field::EFieldDoesNotExist if the table does not have an entry with that key k: K.

public fun borrow<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>, k: K): &V

Implementation

public fun borrow<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>, k: K): &V {
    &field::borrow<K, Node<K, V>>(&table.id, k).value
}

Function borrow_mut

Mutably borrows the value associated with the key in the table table: &mut LinkedTable<K, V>. Aborts with sui::dynamic_field::EFieldDoesNotExist if the table does not have an entry with that key k: K.

public fun borrow_mut<K: copy, drop, store, V: store>(table: &mut linked_table::LinkedTable<K, V>, k: K): &mut V

Implementation

public fun borrow_mut<K: copy + drop + store, V: store>(
    table: &mut LinkedTable<K, V>,
    k: K,
): &mut V {
    &mut field::borrow_mut<K, Node<K, V>>(&mut table.id, k).value
}

Function prev

Borrows the key for the previous entry of the specified key k: K in the table table: &LinkedTable<K, V>. Returns None if the entry does not have a predecessor. Aborts with sui::dynamic_field::EFieldDoesNotExist if the table does not have an entry with that key k: K

public fun prev<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>, k: K): &option::Option<K>

Implementation

public fun prev<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>, k: K): &Option<K> {
    &field::borrow<K, Node<K, V>>(&table.id, k).prev
}

Function next

Borrows the key for the next entry of the specified key k: K in the table table: &LinkedTable<K, V>. Returns None if the entry does not have a predecessor. Aborts with sui::dynamic_field::EFieldDoesNotExist if the table does not have an entry with that key k: K

public fun next<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>, k: K): &option::Option<K>

Implementation

public fun next<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>, k: K): &Option<K> {
    &field::borrow<K, Node<K, V>>(&table.id, k).next
}

Function remove

Removes the key-value pair in the table table: &mut LinkedTable<K, V> and returns the value. This splices the element out of the ordering. Aborts with sui::dynamic_field::EFieldDoesNotExist if the table does not have an entry with that key k: K. Note: this is also what happens when the table is empty.

public fun remove<K: copy, drop, store, V: store>(table: &mut linked_table::LinkedTable<K, V>, k: K): V

Implementation

public fun remove<K: copy + drop + store, V: store>(table: &mut LinkedTable<K, V>, k: K): V {
    let Node<K, V> { prev, next, value } = field::remove(&mut table.id, k);
    table.size = table.size - 1;
    if (prev.is_some()) {
        field::borrow_mut<K, Node<K, V>>(&mut table.id, *prev.borrow()).next = next
    };
    if (next.is_some()) {
        field::borrow_mut<K, Node<K, V>>(&mut table.id, *next.borrow()).prev = prev
    };
    if (table.head.borrow() == &k) table.head = next;
    if (table.tail.borrow() == &k) table.tail = prev;
    value
}

Function pop_front

Removes the front of the table table: &mut LinkedTable<K, V> and returns the value. Aborts with ETableIsEmpty if the table is empty

public fun pop_front<K: copy, drop, store, V: store>(table: &mut linked_table::LinkedTable<K, V>): (K, V)

Implementation

public fun pop_front<K: copy + drop + store, V: store>(table: &mut LinkedTable<K, V>): (K, V) {
    assert!(table.head.is_some(), ETableIsEmpty);
    let head = *table.head.borrow();
    (head, table.remove(head))
}

Function pop_back

Removes the back of the table table: &mut LinkedTable<K, V> and returns the value. Aborts with ETableIsEmpty if the table is empty

public fun pop_back<K: copy, drop, store, V: store>(table: &mut linked_table::LinkedTable<K, V>): (K, V)

Implementation

public fun pop_back<K: copy + drop + store, V: store>(table: &mut LinkedTable<K, V>): (K, V) {
    assert!(table.tail.is_some(), ETableIsEmpty);
    let tail = *table.tail.borrow();
    (tail, table.remove(tail))
}

Function contains

Returns true iff there is a value associated with the key k: K in table table: &LinkedTable<K, V>

public fun contains<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>, k: K): bool

Implementation

public fun contains<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>, k: K): bool {
    field::exists_with_type<K, Node<K, V>>(&table.id, k)
}

Function length

Returns the size of the table, the number of key-value pairs

public fun length<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>): u64

Implementation

public fun length<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>): u64 {
    table.size
}

Function is_empty

Returns true iff the table is empty (if length returns 0)

public fun is_empty<K: copy, drop, store, V: store>(table: &linked_table::LinkedTable<K, V>): bool

Implementation

public fun is_empty<K: copy + drop + store, V: store>(table: &LinkedTable<K, V>): bool {
    table.size == 0
}

Function destroy_empty

Destroys an empty table Aborts with ETableNotEmpty if the table still contains values

public fun destroy_empty<K: copy, drop, store, V: store>(table: linked_table::LinkedTable<K, V>)

Implementation

public fun destroy_empty<K: copy + drop + store, V: store>(table: LinkedTable<K, V>) {
    let LinkedTable { id, size, head: _, tail: _ } = table;
    assert!(size == 0, ETableNotEmpty);
    id.delete()
}

Function drop

Drop a possibly non-empty table. Usable only if the value type V has the drop ability

public fun drop<K: copy, drop, store, V: drop, store>(table: linked_table::LinkedTable<K, V>)

Implementation

public fun drop<K: copy + drop + store, V: drop + store>(table: LinkedTable<K, V>) {
    let LinkedTable { id, size: _, head: _, tail: _ } = table;
    id.delete()
}