solidity-dynamic-array

Solidity dynamic array

Resizable in-memory array for Solidity.

Description

Have you ever wanted to create a resizable, in-memory Solidity array? 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.

Install

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

Usage

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'));
  }
}

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;

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;
}

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

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
list	struct LinkedList	The list to retreive the Node from
index	uint256	The index of the Node to retreive

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
list	struct LinkedList	The list to retreive the value from
index	uint256	The index of the value to retreive

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
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

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
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

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
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

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

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
list	struct LinkedList	The list to remove the value from
index	uint256	The index of the value to remove

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

slice

function slice(struct LinkedList list, uint256 _from, uint256 _to) internal pure returns (struct LinkedList)

Creates a new list that only contains the elements between the specified range of the original list

Name	Type	Description
list	struct LinkedList	The list to slice
_from	uint256	The index of the first element to include
_to	uint256	The index of the last element to include

Name	Type	Description
[0]	struct LinkedList	the sliced list

merge

function merge(struct LinkedList list, struct LinkedList _other) internal pure

Merges two lists together by appending the second list at the end of the first. The other list will be deep copied so it can be safely modified after this operation without affecting the result list.

Name	Type	Description
list	struct LinkedList	The list to append to
_other	struct LinkedList	The list to be copied and appended

concat

function concat(struct LinkedList list, struct LinkedList other) internal pure returns (struct LinkedList)

Creates a new list that is a result of concatenation of the lists passed as arguments. Both lists will be deep copied so they can be safely modified after this operation without affecting the result list.

Name	Type	Description
list	struct LinkedList	The first list to concatenate
other	struct LinkedList	The second list to concatenate

Name	Type	Description
[0]	struct LinkedList	newList A new list that is a result of concatenation of the lists passed as arguments

deepCopy

function deepCopy(struct LinkedList list) internal pure returns (struct LinkedList copiedList)

Creates a deep copy of the list

Name	Type	Description
list	struct LinkedList	The list to copy

Name	Type	Description
copiedList	struct LinkedList	A copy of the original list

some

function some(struct LinkedList list, function (bytes,uint256) view returns (bool) callback) internal view returns (bool)

Iterates over the list and calls the callback function for each element in order to check if the condition is met for at least one element. Callbacks are only executed until one of the callback invocations returns true.

Name	Type	Description
list	struct LinkedList	The list to iterate over
callback	function (bytes,uint256) view returns (bool)	The function to call for each element. It accepts the element and the index as parameters.

every

function every(struct LinkedList list, function (bytes,uint256) view returns (bool) callback) internal view returns (bool)

Iterates over the list and calls the callback function for each element in order to check if the condition is met for all elements. Callbacks are only executed until one of the callback invocations returns false.

Name	Type	Description
list	struct LinkedList	The list to iterate over
callback	function (bytes,uint256) view returns (bool)	The function to call for each element. It accepts the element and the index as parameters.

Name	Type	Description
[0]	bool	true If the callback returns true for all elements, false otherwise

forEach

function forEach(struct LinkedList list, function (bytes,uint256) callback) internal

Iterates over the list and calls the callback function for each element

Name	Type	Description
list	struct LinkedList	The list to iterate over
callback	function (bytes,uint256)	The function to call for each element. It accepts the element and the index as parameters

map

function map(struct LinkedList list, function (bytes,uint256) view returns (bytes) callback) internal view returns (struct LinkedList)

Creates a new list with elements that are the result of calling the callback function for each element

Name	Type	Description
list	struct LinkedList	The list to iterate over
callback	function (bytes,uint256) view returns (bytes)	The function to call for each element. It accepts the element and the index as parameters and returns a new item

filter

function filter(struct LinkedList list, function (bytes,uint256) view returns (bool) callback) internal view returns (struct LinkedList)

Filters the list and creates a new list with the elements that match the condition

Name	Type	Description
list	struct LinkedList	The list to filter
callback	function (bytes,uint256) view returns (bool)	The function to check if element matches the condition. It accepts the element and the index as parameters.

Name	Type	Description
[0]	struct LinkedList	filteredList A new list with the elements that match the condition

reduce

function reduce(struct LinkedList list, function (bytes,bytes,uint256) view returns (bytes) callback, bytes initialValue) internal view returns (bytes)

Reduces the list to a single value by calling the callback function for each element

Name	Type	Description
list	struct LinkedList	The list to reduce
callback	function (bytes,bytes,uint256) view returns (bytes)	The function to call for each element. It accepts the accumulator, the current element and the index as parameters.
initialValue	bytes	The initial value of the accumulator

Name	Type	Description
[0]	bytes	accumulator The final value of the accumulator

sort

function sort(struct LinkedList list, function (bytes,bytes) view returns (int256) callback) internal view

Sorts the list using quicksort algorithm

The input list is not copied, so the original list is modified

Name	Type	Description
list	struct LinkedList	The list to sort
callback	function (bytes,bytes) view returns (int256)	The function to compare two elements. It accepts two elements and returns: -1 if the first element is smaller than the second element 0 if the first element is equal to the second element 1 if the first element is greater than the second element

Author

👤 Kamil Planer

• Github: @MrKampla
• LinkedIn: @https://www.linkedin.com/in/kamil-planer/

Contributions, issues and feature requests are welcome!

Give a ⭐️ if this project helped you!