Skip to main content

Module 0x2::linked_table

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

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