Smart Table

The Smart Table is a scalable hash table implementation based on linear hashing. This data structure aims to optimize storage and performance by utilizing linear hashing, which splits one bucket at a time instead of doubling the number of buckets, thus avoiding unexpected gas costs. The Smart Table uses the SipHash function for faster hash computations while tolerating collisions.

The SmartTable struct is designed to handle dynamic data efficiently:

• buckets: A table with a length that stores vectors of entries.
• num_buckets: The current number of buckets.
• level: The number of bits representing num_buckets.
• size: The total number of items in the table.
• split_load_threshold: The load threshold percentage that triggers bucket splits.
• target_bucket_size: The target size of each bucket, which is not strictly enforced.

The following constants define various error codes used within the module:

• ENOT_FOUND: 1
• EZERO_CAPACITY: 2
• ENOT_EMPTY: 3
• EALREADY_EXIST: 4
• EINVALID_LOAD_THRESHOLD_PERCENT: 5
• EINVALID_TARGET_BUCKET_SIZE: 6
• EEXCEED_MAX_BUCKET_SIZE: 7
• EINVALID_BUCKET_INDEX: 8
• EINVALID_VECTOR_INDEX: 9

• new<K: copy + drop + store, V: store>(): SmartTable<K, V>: Creates an empty table with default configurations.
• new_with_config<K: copy + drop + store, V: store>(num_initial_buckets: u64, split_load_threshold: u8, target_bucket_size: u64): SmartTable<K, V>: Creates an empty table with custom configurations.

• destroy_empty<K, V>(table: SmartTable<K, V>): Destroys an empty table.
• destroy<K: drop, V: drop>(table: SmartTable<K, V>): Destroys a table and its elements.
• clear<K: drop, V: drop>(table: &mut SmartTable<K, V>): Clears all elements from the table.

• add<K, V>(table: &mut SmartTable<K, V>, key: K, value: V): Adds a key-value pair to the table.
• add_all<K, V>(table: &mut SmartTable<K, V>, keys: vector<K>, values: vector<V>): Adds multiple key-value pairs to the table.
• remove<K: copy + drop, V>(table: &mut SmartTable<K, V>, key: K): V: Removes and returns the value associated with a key.
• upsert<K: copy + drop, V: drop>(table: &mut SmartTable<K, V>, key: K, value: V): Inserts or updates a key-value pair.

• borrow<K: drop, V>(table: &SmartTable<K, V>, key: K): &V: Returns an immutable reference to the value associated with a key.
• borrow_with_default<K: copy + drop, V>(table: &SmartTable<K, V>, key: K, default: &V): &V: Returns the value associated with a key or a default value if the key is not found.
• borrow_mut<K: drop, V>(table: &mut SmartTable<K, V>, key: K): &mut V: Returns a mutable reference to the value associated with a key.
• borrow_mut_with_default<K: copy + drop, V: drop>(table: &mut SmartTable<K, V>, key: K, default: V): &mut V: Inserts a key-value pair if the key is not found, then returns a mutable reference to the value.

• length<K, V>(table: &SmartTable<K, V>): u64: Returns the number of entries in the table.
• load_factor<K, V>(table: &SmartTable<K, V>): u64: Returns the load factor of the table.
• update_split_load_threshold<K, V>(table: &mut SmartTable<K, V>, split_load_threshold: u8): Updates the split load threshold.
• update_target_bucket_size<K, V>(table: &mut SmartTable<K, V>, target_bucket_size: u64): Updates the target bucket size.
• to_simple_map<K: store + copy + drop, V: store + copy>(table: &SmartTable<K, V>): SimpleMap<K, V>: Converts the smart table to a simple map.

module 0x42::smart_table_usage {
    use aptos_std::smart_table;

    public entry fun main() {
        let table = smart_table::new<u64, u64>();
        smart_table::add(&mut table, 1, 100);
        smart_table::add(&mut table, 2, 200);

        let length = smart_table::length(&table);
        assert!(length == 2, 0);

        let value1 = smart_table::borrow(&table, 1);
        assert!(*value1 == 100, 0);

        let value2 = smart_table::borrow(&table, 2);
        assert!(*value2 == 200, 0);

        let removed_value = smart_table::remove(&mut table, 1);
        assert!(removed_value == 100, 0);

        smart_table::destroy_empty(table);
    }
}

module 0x42::smart_table_usage {
    use aptos_std::smart_table;

    public fun add_multiple_entries() {
        let table = smart_table::new<u64, u64>();
        let keys = vector[1, 2, 3];
        let values = vector[100, 200, 300];

        smart_table::add_all(&mut table, keys, values);

        let length = smart_table::length(&table);
        assert!(length == 3, 0);

        let value1 = smart_table::borrow(&table, 1);
        assert!(*value1 == 100, 0);

        let value2 = smart_table::borrow(&table, 2);
        assert!(*value2 == 200, 0);

        let value3 = smart_table::borrow(&table, 3);
        assert!(*value3 == 300, 0);

        smart_table::destroy_empty(table);
    }
}

module 0x42::smart_table_usage {
    use aptos_std::smart_table;

    public fun update_and_clear_table() {
        let table = smart_table::new<u64, u64>();
        smart_table::add(&mut table, 1, 100);
        smart_table::add(&mut table, 2, 200);

        smart_table::upsert(&mut table, 2, 300);
        let value2 = smart_table::borrow(&table, 2);
        assert!(*value2 == 300, 0);

        smart_table::clear(&mut table);
        let length = smart_table::length(&table);
        assert!(length == 0, 0);

        smart_table::destroy_empty(table);
    }
}

module 0x42::smart_table_usage {
    use aptos_std::smart_table;
    use aptos_std::simple_map;

    public fun convert_to_simple_map() {
        let table = smart_table::new<u64, u64>();
        smart_table::add(&mut table, 1, 100);
        smart_table::add(&mut table, 2, 200);

        let map = smart_table::to_simple_map(&table);
        let length = simple_map::length(&map);
        assert!(length == 2, 0);

        let value1 = simple_map::borrow(&map, &1);
        assert!(*value1 == 100, 0);

        let value2 = simple_map::borrow(&map, &2);
        assert!(*value2 == 200, 0);

        smart_table::destroy(table);
    }
}

• smart_table.move

• Move Spiders Smart Table
• Move Spiders Querying Smart Table via FullNode APIs
• Move Spiders Querying Smart Table via View Function