Module 0x2::linked_table

Similar to iota::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 ETableIsEmpty: u64 = 1;

const ETableNotEmpty: u64 = 0;

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 iota::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 iota::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 iota::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 iota::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 iota::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 iota::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 iota::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()
}