solidity-dynamic-array

v0.4.0

Published

a year ago

Resizable in-memory array for Solidity

Downloads

0High
0Medium
0Low

mrkampla

blockchain ethereum library dynamic-array smart-contracts solidity

Solidity dynamic array

Resizable in-memory array for Solidity.

Description

Have you ever wanted to create a resizable, in-memory Solidity array? Or a dynamic in-memory mapping? If you answered “yes”, then this library is for you. In order to create an in-memory Solidity Array, you have to specify its length upfront in order for the compiler to allocate enough memory. With solidity-dynamic-array package, you can use DynamicArray library together with LinkedList struct in order to fully utilize dynamic, resizable arrays. I was aiming to reproduce the JavaScript ES6 array methods, so you can enjoy functions such as map, filter and reduce etc. that we all know and love. Moreover, this package exports another dynamic in-memory data structure that is not available in native Solidity: a fully in-memory mapping object! Map struct uses dynamic arrays under the hood and thanks to that, you can create and edit mappings fully in memory.

Install

npm i solidity-dynamic-array or yarn add solidity-dynamic-array

Usage

Dynamic Array

pragma solidity ^0.8.16;

import { DynamicArray, LinkedList, Node } from 'solidity-dynamic-array/contracts/DynamicArray.sol';

contract MyContract {
  // don't forget about "using" statement!
  using DynamicArray for LinkedList;

  function createDynamicInMemoryArray() public pure {
    // create empty list, you can also create a list based on array values - look up `from`, `fromStorage`
    // and `fromCalldata` methods
    LinkedList memory list = DynamicArray.empty();

    // add as many elements as you want!
    list.push('a');
    list.push('b');
    list.push('c');
    // length will be dynamically calculated
    require(list.length == 3);
    // you can also remove elements
    list.pop();
    require(list.length == 2);
  }

  struct MyStruct {
    uint256 myUint;
    string myString;
  }

  // LinkedList can also store structs!
  function storeStructInDynamicInMemoryArray() public pure {
    LinkedList memory list = DynamicArray.empty();
    // list only accepts bytes values so don't forget to encode your struct before storing it in the list
    list.push(abi.encode(MyStruct(1337, 'example')));

    // when retreiving a struct from list, don't forget to decode the item
    MyStruct memory decodedStruct = abi.decode(list.get(0), (MyStruct));

    require(decodedStruct.myUint == 1337);
    require(keccak256(abi.encodePacked(decodedStruct.myString)) == keccak256('example'));
  }
}

Array Map

pragma solidity ^0.8.16;

import { ArrayMap, Map } from 'solidity-dynamic-array/contracts/ArrayMap.sol';

contract MyContract {
  // don't forget about "using" statement!
  using ArrayMap for Map;

  function createDynamicInMemoryMap() public pure {
    // create empty Map, you can also create a map based on array values - look up methods starting with `from`
    Map memory map = ArrayMap.empty();

    map.set('a', 'b');
    map.set('c', 'd');
    map.set('e', 'f');
    // size will be dynamically calculated
    require(map.size() == 3);
    // you can also remove elements
    map.remove('c');
    require(map.size() == 2);
  }

  struct MyStruct {
    uint256 myUint;
    string myString;
  }

  // Map can also store structs!
  function storeStructInDynamicInMemoryMap() public pure {
    Map memory map = ArrayMap.empty();
    // map only accepts bytes values so don't forget to encode your struct before storing it
    map.set('a', abi.encode(MyStruct(1337, 'example')));

    // when retreiving a struct from list, don't forget to decode the item
    MyStruct memory decodedStruct = abi.decode(map.get('a'), (MyStruct));

    require(decodedStruct.myUint == 1337);
    require(keccak256(abi.encodePacked(decodedStruct.myString)) == keccak256('example'));
  }
}

DynamicArray Library

A library for managing dynamic in-memory arrays of bytes. This can hold any basic type or struct. Due to lack of generics in Solidity, this library uses a workaround to manage dynamic arrays of different types. Under the hood it is storing an arbitrary amount of bytes so in order to store a struct, it has to be encoded before storing (using abi.encode) and decoded after it is retreived from the list (using abi.decode). This library is meant to be used with the LinkedList struct. For brevity, it is recommended to add a 'using' statement to your contract: using DynamicArray for LinkedList;

ArrayMap Library

The ArrayMap library provides a way to store a mapping of keys to values where the keys are dynamic arrays of bytes. Like the DynamicArray library, this library uses the workaround of storing the keys and values as bytes and encoding/decoding them using abi.encode/abi.decode. The library is meant to be used with the Map struct.

The library provides functions to insert, update, remove, and get values from the mapping. It also provides functions to retrieve the keys and values, and get the size of the mapping.

Similar to the DynamicArray library, it is recommended to add a 'using' statement to your contract to make usage of this library more convenient. For example: using ArrayMap for Map;

Because of the fact that keys and values are stored in a dynamic in-memory array, the set and lookup times are O(n) where n is the number of elements in the map. Please note that this implementation is not optimized for big maps. Proceed with caution when using it with large amounts of data and check the gas usage.

Structs

Node

Node is an element stored inside the linked list. Value is stored as bytes, so it can be any basic type or struct, it just has to be encoded before storing and decoded after retrieved from the list. The node also contains references to the previous and next element in the list. Node[] functions as a pointer, if it's empty list, it's null. If it has one element, it's the pointer to the next node.

struct Node {
  bytes value;
  Node[] previous;
  Node[] next;
}

LinkedList

LinkedList is a dynamic array of Nodes. It contains the length of the list and a pointer to the head of the list. If the list is empty, head is an empty array.

struct LinkedList {
  uint256 length;
  Node[] head;
}

Map

Map is a key-value store consisting of two linked lists. Each key is stored in the keys list, and its corresponding value is stored in the values list at the same index. This allows for efficient retrieval and deletion of key-value pairs, as well as iteration over the map. Please note that the Map struct may not be suitable for large mappings due to gas usage. Each key-value pair added to the map incurs a certain amount of gas cost, which can become significant for large mappings, as array implementation of a mapping is not optimized for an efficient lookup and insert operations (it's O(n) time complexity).

struct Map {
  LinkedList keys;
  LinkedList values;
}

DynamicArray methods

empty

function empty() internal pure returns (struct LinkedList)

Creates an empty LinkedList

| Name | Type | Description | | ---- | ----------------- | ------------------------- | | [0] | struct LinkedList | list The empty LinkedList |

from

function from(bytes[] values) internal pure returns (struct LinkedList)

Creates a LinkedList from an in-memory array of bytes

| Name | Type | Description | | ------ | ------- | ------------------------------------------------ | | values | bytes[] | The array of bytes to create the LinkedList from |

| Name | Type | Description | | ---- | ----------------- | --------------------------------------------------- | | [0] | struct LinkedList | list The LinkedList created from the array of bytes |

fromStorage

function fromStorage(bytes[] values) internal view returns (struct LinkedList)

Creates a LinkedList from an array of bytes from storage

| Name | Type | Description | | ------ | ------- | ------------------------------------------------ | | values | bytes[] | The array of bytes to create the LinkedList from |

| Name | Type | Description | | ---- | ----------------- | --------------------------------------------------- | | [0] | struct LinkedList | list The LinkedList created from the array of bytes |

fromCalldata

function fromCalldata(bytes[] values) internal pure returns (struct LinkedList)

Creates a LinkedList from an array of bytes from calldata

| Name | Type | Description | | ------ | ------- | ------------------------------------------------ | | values | bytes[] | The array of bytes to create the LinkedList from |

| Name | Type | Description | | ---- | ----------------- | --------------------------------------------------- | | [0] | struct LinkedList | list The LinkedList created from the array of bytes |

fromSequence

function fromSequence(uint256 end) internal pure returns (struct LinkedList newList)

Creates a list of numbers from 0 to end

| Name | Type | Description | | ---- | ------- | ------------------------------ | | end | uint256 | The number to end the sequence |

| Name | Type | Description | | ------- | ----------------- | -------------------------------------- | | newList | struct LinkedList | The new list created from the sequence |

fromSubrange

function fromSubrange(struct LinkedList list, uint256 start, uint256 end) internal pure returns (struct LinkedList)

Creates a new list of numbers witch is a subset of the original list from specified part

| Name | Type | Description | | ----- | ----------------- | -------------------------------- | | list | struct LinkedList | The list to create a subset from | | start | uint256 | The index to start the subset | | end | uint256 | The index to end the subset |

| Name | Type | Description | | ---- | ----------------- | -------------------------------------------- | | [0] | struct LinkedList | newList the new list created from the subset |

push

function push(struct LinkedList list, bytes value) internal pure

Pushes a new value to the end of the list

| Name | Type | Description | | ----- | ----------------- | ----------------------------- | | list | struct LinkedList | The list to push the value to | | value | bytes | The value to push to the list |

pop

function pop(struct LinkedList list) internal pure returns (bytes)

Removes the last value from the list

| Name | Type | Description | | ---- | ----------------- | ------------------------------ | | list | struct LinkedList | The list to pop the value from |

| Name | Type | Description | | ---- | ----- | ------------------------------------ | | [0] | bytes | value The value popped from the list |

tryPop

function tryPop(struct LinkedList list) internal pure returns (bool success, bytes removedItem)

Tries to pop the last value from list. If the list is empty, it returns false and does not revert.

| Name | Type | Description | | ---- | ----------------- | ------------------------------ | | list | struct LinkedList | The list to pop the value from |

| Name | Type | Description | | ----------- | ----- | ------------------------------ | | success | bool | Whether the pop was successful | | removedItem | bytes | The value popped from the list |

getNode

function getNode(struct LinkedList list, uint256 index) internal pure returns (struct Node)

Retreives the Node element at the specified index without removing it

| Name | Type | Description | | ----- | ----------------- | ---------------------------------- | | list | struct LinkedList | The list to retreive the Node from | | index | uint256 | The index of the Node to retreive |

tryGetNode

function tryGetNode(struct LinkedList list, uint256 index) internal pure returns (bool success, struct Node)

Tries to retreive the Node element at the specified index without removing it. If the index is out of bounds, it returns false and does not revert.

| Name | Type | Description | | ------- | ----------- | ------------------------------- | | success | bool | Whether the call was successful | | [1] | struct Node | The Node at the specified index |

get

function get(struct LinkedList list, uint256 index) internal pure returns (bytes)

Retreives the value at the specified index without removing it

| Name | Type | Description | | ----- | ----------------- | ----------------------------------- | | list | struct LinkedList | The list to retreive the value from | | index | uint256 | The index of the value to retreive |

tryGet

function tryGet(struct LinkedList list, uint256 index) internal pure returns (bool success, bytes value)

Tries to retreive the value at the specified index without removing it. If the index is out of bounds, it returns false and does not revert.

| Name | Type | Description | | ------- | ----- | -------------------------------- | | success | bool | Whether the call was successful | | value | bytes | The value at the specified index |

set

function set(struct LinkedList list, uint256 index, bytes value) internal pure

Sets the value at the specified index

| Name | Type | Description | | ----- | ----------------- | ----------------------------- | | list | struct LinkedList | The list to set the value in | | index | uint256 | The index of the value to set | | value | bytes | The value to set |

trySet

function trySet(struct LinkedList list, uint256 index, bytes value) internal pure returns (bool success)

Tries to set the value at the specified index. If the index is out of bounds, it returns false and does not revert.

| Name | Type | Description | | ------- | ---- | ------------------------------- | | success | bool | Whether the call was successful |

insert

function insert(struct LinkedList list, uint256 index, bytes value) internal pure

Inserts a new value at the specified index

| Name | Type | Description | | ----- | ----------------- | -------------------------------- | | list | struct LinkedList | The list to insert the value in | | index | uint256 | The index to insert the value at | | value | bytes | The value to insert |

tryInsert

function tryInsert(struct LinkedList list, uint256 index, bytes value) internal pure returns (bool success)

Tries to insert a new value at the specified index. If the index is out of bounds, it returns false and does not revert.

| Name | Type | Description | | ------- | ---- | ------------------------------- | | success | bool | Whether the call was successful |

insertAll

function insertAll(struct LinkedList list, uint256 index, bytes[] values) internal pure

Inserts an array of values at the specified index

| Name | Type | Description | | ------ | ----------------- | --------------------------------- | | list | struct LinkedList | The list to insert the values in | | index | uint256 | The index to insert the values at | | values | bytes[] | The values to insert |

tryInsertAll

function tryInsertAll(struct LinkedList list, uint256 index, bytes[] values) internal pure returns (bool success)

Tries to insert an array of values at the specified index. If the index is out of bounds, it returns false and does not revert.

| Name | Type | Description | | ------- | ---- | ------------------------------- | | success | bool | Whether the call was successful |

appendAll

function appendAll(struct LinkedList list, bytes[] values) internal pure

Appends an array of values to the end of the list

This is equivalent to insertAll(list, list.length, values)

| Name | Type | Description | | ------ | ----------------- | -------------------------------- | | list | struct LinkedList | The list to append the values to | | values | bytes[] | The values to append |

addFirst

function addFirst(struct LinkedList list, bytes value) internal pure

Adds a value to the beginning of the list

This is equivalent to insert(list, 0, value)

| Name | Type | Description | | ----- | ----------------- | ---------------------------- | | list | struct LinkedList | The list to add the value to | | value | bytes | The value to add |

addLast

function addLast(struct LinkedList list, bytes value) internal pure

Adds a value to the end of the list

This is equivalent to insert(list, list.length, value)

| Name | Type | Description | | ----- | ----------------- | ---------------------------- | | list | struct LinkedList | The list to add the value to | | value | bytes | The value to add |

getFirstElement

function getFirstElement(struct LinkedList list) internal pure returns (bytes)

Gets the first value in the list without removing it

This is equivalent to get(list, 0)

| Name | Type | Description | | ---- | ----------------- | ------------------------------ | | list | struct LinkedList | The list to get the value from |

getLastElement

function getLastElement(struct LinkedList list) internal pure returns (bytes)

Gets the last value in the list without removing it

This is equivalent to get(list, list.length - 1)

| Name | Type | Description | | ---- | ----------------- | ------------------------------ | | list | struct LinkedList | The list to get the value from |

indexOf

function indexOf(struct LinkedList list, bytes value) internal pure returns (int256)

gets the index of the first occurance of the specified value

| Name | Type | Description | | ----- | ----------------- | ----------------------- | | list | struct LinkedList | The list to search | | value | bytes | The value to search for |

| Name | Type | Description | | ---- | ------ | ---------------------------------------------------------------------------------------------- | | [0] | int256 | the index of the first occurance of the specified value, or -1 if the value is not in the list |

lastIndexOf

function lastIndexOf(struct LinkedList list, bytes value) internal pure returns (int256)

Gets the index of the last occurance of the specified value

| Name | Type | Description | | ----- | ----------------- | ----------------------- | | list | struct LinkedList | The list to search | | value | bytes | The value to search for |

| Name | Type | Description | | ---- | ------ | --------------------------------------------------------------------------------------------- | | [0] | int256 | The index of the last occurance of the specified value, or -1 if the value is not in the list |

find

function find(struct LinkedList list, function (bytes,uint256) pure returns (bool) callback) internal pure returns (bytes)

Finds the first occurance of the specified in the list

| Name | Type | Description | | -------- | -------------------------------------------- | ------------------------------------------------- | | list | struct LinkedList | The list to search | | callback | function (bytes,uint256) pure returns (bool) | The callback to call for each element in the list |

| Name | Type | Description | | ---- | ----- | ----------------------------------------------------------------------------------------------------------------------------- | | [0] | bytes | the first value from the list for which the callback returns true, or an empty bytes array if the callback never returns true |

contains

function contains(struct LinkedList list, bytes value) internal pure returns (bool)

Checks if the list contains the specified value

| Name | Type | Description | | ----- | ----------------- | ----------------------- | | list | struct LinkedList | The list to search | | value | bytes | The value to search for |

| Name | Type | Description | | ---- | ---- | -------------------------------------------------------------- | | [0] | bool | true if the list contains the specified value, false otherwise |

remove

function remove(struct LinkedList list, uint256 index) internal pure

Removes the first occurance of the specified value

| Name | Type | Description | | ----- | ----------------- | --------------------------------- | | list | struct LinkedList | The list to remove the value from | | index | uint256 | The index of the value to remove |

tryRemove

function tryRemove(struct LinkedList list, uint256 index) internal pure returns (bool success)

Tries to removes the the element at the specified index. Returns false if the index is out of bounds and does not revert.

| Name | Type | Description | | ------- | ---- | ------------------------------------------------ | | success | bool | true if the element was removed, false otherwise |

toArray

function toArray(struct LinkedList list) internal pure returns (bytes[])

Creates a solidity array from the linked list

| Name | Type | Description | | ---- | ----------------- | ------------------- | | list | struct LinkedList | The list to convert |

asAddressArray

function asAddressArray(struct LinkedList list) internal pure returns (address[] result)

Creates a solidity array of addresses from the linked list

This function should only be called if the list contains addresses