A data structures library that does memory management for you
Soon:
This software is in alpha. There are likely bugs. Testing is relatively limited right now. Use at your own risk
Below are some comparisons of Array vs a built in solidity array (uint256[]
). Where possible a 1:1 comparison
is made. Otherwise, it is up to the reader to say what is most applicable to compare.
op | Array | Solidity builtin |
---|---|---|
new(5) | 75 | 147 |
push | 229 | N/A |
unsafe_push | 78 | N/A |
set | 113 | 75 |
unsafe_set | 29 | N/A |
get | 123 | 70 |
unsafe_get | 48 | N/A |
length | 33 | 10 |
import "memmove/Array.sol";
contract ArrayUser {
using ArrayLib for Array;
function instantiateArray() public {
// create the array
//
// note: the `5` here is what is called a `capacityHint`
// basically is just an optimization for when you *know*
// the size of your array or can decently guess.
// You can make it 0, and it will work just fine
Array pa = ArrayLib.newArray(5);
// we can use unsafe_push because we know 5 elements
// can for sure fit
//
// additionally, unsafe_pushes cannot move the array so
// we dont have to do `pa = pa.unsafe_push(..)`
//
// this is actually cheaper than builtin solidity arrays!
pa.unsafe_push(125);
pa.unsafe_push(126);
pa.unsafe_push(127);
pa.unsafe_push(128);
pa.unsafe_push(129);
// after 5 elements, we have to use push, and update `pa`
// we have to update pa because it may be moved when we
// push
//
// for a better ux (but slightly less gas efficient), use `RefArrayLib`
pa = pa.push(130);
pa = pa.push(131);
pa = pa.push(132);
pa = pa.push(133);
pa = pa.push(134);
pa = pa.push(135);
for (uint256 i; i < 11; i++) {
require(pa.get(i) == 125 + i);
}
// performance hack!
// we can read the length once, and then use
// `unsafe_get` for indexing into the array
//
// this is also cheaper than builtin solidity array indexing!
uint256 length = pa.length();
for (uint256 i; i < length; i++) {
require(pa.unsafe_get(i) == 125 + i);
}
}
}
import "memmove/Array.sol";
contract RefArrayUser {
// note using RefArrayLib instead of ArrayLib;
// it has almost the same interface (just dont have to update the pointer) but
// is slightly less gas efficient
using RefArrayLib for Array;
function instantiateRefArray() public {
Array pa = RefArrayLib.newArray(5);
// we can use unsafe_push because we know 5 elements
// can for sure fit
pa.unsafe_push(125);
pa.unsafe_push(126);
pa.unsafe_push(127);
pa.unsafe_push(128);
pa.unsafe_push(129);
// we dont have to update the `pa` because even if the underlying array
// is moved, we basically are holding a reference of the reference to the array
//
// when the reference to the array is updated, this library updates our reference for us
pa.push(130);
pa.push(131);
pa.push(132);
pa.push(133);
pa.push(134);
pa.push(135);
for (uint256 i; i < 11; i++) {
require(pa.get(i) == 125 + i);
}
}
}
import "memmove/LinkedList.sol";
struct U256 {
uint256 value;
uint256 next;
}
// A basic wrapper around an array that returns a pointer to an element in
// the array. Unfortunately without generics, the user has to cast from a pointer to a type
// held in memory manually
//
// is indexable
//
// data structure:
// |-----------------------------| |-------|
// | v | v
// [ptr, ptr2, ptr3, ptr4] {value, other value, next} {value, other value, next}
// | ^
// |-------------------------------------------------------|
//
// where `mload(add(ptr, linkingOffset))` (aka `next`) == ptr2
contract ILLUser {
using IndexableLinkedListLib for LinkedList;
function instantiateIndexableLinkedList() public {
// create a new indexable linked list with a `capacityHint`
// see below how we actually insert 7 elements, not just 5
LinkedList pa = IndexableLinkedListLib.newIndexableLinkedList(5);
// we create a struct in memory. the struct must be designed for the
// linked list for now but this requirement may be lifted later
//
// `next` will be filled by the library, but you need to tell the library
// where in the struct to find the pointer
//
// for this example, `nextParameterOffset` is 32, meaning 32 bytes. this is because from
// the start of our struct, to the `next` parameter there is
// one field before it, so 1*32bytes = 32bytes (32 bytes is the default length in memory)
uint256 nextParameterOffset = 32;
for (uint256 i; i < 7; i++) {
// we create our linked list element in memory
U256 memory b = U256({value: 100 + i, next: 0});
// we push into the linked list, and if there is a preceeding value,
// we will link this to that one
//
// otherwise, its the first element and will start the linked list
//
// note: we have to turn our struct into a bytes32 pointer.
// for a struct you define, all you have to do is replace the `U256`
// in the `pointer` function with the name of your struct
pa = pa.push_and_link(pointer(b), nextParameterOffset);
}
// and we can index into the list and get the resulting values
for (uint256 i; i < 7; i++) {
bytes32 ptr = pa.get(i);
U256 memory k = fromPointer(ptr);
require(k.value == 100 + i);
}
}
function pointer(U256 memory a) internal returns(bytes32 ptr) {
assembly ("memory-safe") {
ptr := a
}
}
function fromPointer(bytes32 ptr) internal returns(U256 memory a) {
assembly ("memory-safe") {
a := ptr
}
}
}
import "memmove/LinkedList.sol";
struct U256 {
uint256 value;
uint256 next;
}
// the only way to traverse is to start at head and iterate via `next`. More memory efficient, better for maps
//
// data structure:
// |-------------------------tail----------------------------|
// |head| |--------|
// | v | v
// head, dataStruct{.., next} } dataStruct{.., next} dataStruct{.., next}
// | ^
// |----------|
//
// `head` is a packed word split as 80, 80, 80 of linking offset, ptr to first element, ptr to last element
// `head` *isn't* stored in memory because it fits in a word
contract LLUser {
// note: this uses `LinkedListLib` *not* `IndexableLinkedListLib`
using LinkedListLib for LinkedList;
function instantiateLinkedList() public {
// unlike indexable linked list, we instantiate a normal linked
// list with just the `nextParameterOffset`
//
// non-indexable linked lists (lls) live on the stack, with elements
// being allocated nonsequentially in memory
//
// what `pa` is in this scenario is, is a packed type that consists of:
// packedLoc0 - uint80: linkingOffset (the `nextParameterOffset` variable)
// packedLoc1 - uint80: head ptr, a pointer to the head of the ll
// packedLoc2 - uint80: tail ptr, a pointer to the tail of the ll
//
// note: there is an extra 16 bits that are unused, but you shouldn't rely
// on being able to store anything in there as they are likely to get wiped out
//
// what this means is you can only access the head or the tail of a linked list
// this have gas efficiencies associated with it, as well as being able to keep it
// on the stack
//
// additionally, we never have to move the underlying data, it can stay wherever
// because each element in our list holds a ptr to it
uint256 nextParameterOffset = 32;
LinkedList pa = LinkedListLib.newLinkedList(nextParameterOffset);
for (uint256 i; i < 7; i++) {
// we create our linked list element in memory
U256 memory b = U256({value: 100 + i, next: 0});
// we push into the linked list, and if there is a preceeding value,
// we will link this to that one
//
// otherwise, its the first element and will start the linked list
//
// note: we have to turn our struct into a bytes32 pointer.
// for a struct you define, all you have to do is replace the `U256`
// in the `pointer` function with the name of your struct
//
// REMEMBER: you *must* update the `pa` value, otherwise you will lose your tail.
pa = pa.push_and_link(pointer(b), nextParameterOffset);
}
// we *cannot* index into the linked list but we can walk it from head to tail:
//
// get the head ptr
bytes32 element = pa.head();
bool success = true;
// while we still have elements to walk:
uint256 ctr = 0;
while (success) {
// convert the ptr to our struct type
U256 memory elem = fromPointer(element);
// check it is what we expected
require(elem.value == 100 + ctr);
++ctr;
// walk to the next element
(success, element) = linkedList.next(element);
}
require(ctr == 7);
}
function pointer(U256 memory a) internal returns(bytes32 ptr) {
assembly ("memory-safe") {
ptr := a
}
}
function fromPointer(bytes32 ptr) internal returns(U256 memory a) {
assembly ("memory-safe") {
a := ptr
}
}
}
import "memmove/LinkedList.sol";
// A mapping with the following structure:
// |---------------------------------------------------|
// |------------| | |------------| |------------| |
// | | | | key | |--> | key | |-> ... |
// | bucket 1 | - holds pointer to > | | value | | | value | | |
// | | | | ptr_to ----|---| | ptr_to ----|---| |
// |------------| | |------------| |------------| |
// | | |---------------------------------------------------|
// | bucket 2 | ...
// | |
// |------------|
// | ... |
// |------------|
// where the number of buckets is determined by the capacity. The number of buckets is
// currently static at initialization, but this limitation could be lifted later
//
// in general, its a memory/lookup speed tradeoff. We use a basic modulo operation for bucketing,
// which isn't ideal
//
// Complexity: best case O(1), worst case O(n)
contract MappingUser {
using MappingLib for Mapping;
function createDynamicMap() internal returns (Mapping map) {
// create a mapping with 5 buckets
Mapping map = MappingLib.newMapping(5);
// insert 7 items, where the key is a bytes32, and the value is a uint256
// if your type doesnt match those, you can cast them into it. eventually will be
// overloaded for you
//
// by default there cannot be duplicate keys. if you `insert` with the same key,
// it will overwrite a previous value
for (uint256 i; i < 7; i++) {
map.insert(bytes32(i), i);
}
// we can get values by key
for (uint256 i; i < 7; i++) {
(bool keyExists, uint256 previouslyInsertedValue) = map.get(bytes32(i));
require(keyExists);
require(previouslyInsertedValue == i);
}
// we can insert values in an unchecked manner. this is slightly more gas efficient
// but may lead you to unnecessarily expanding one of the linked lists that
// are used under the hood, making subsequent gets for values
// added after a faulty unchecked insert cost more
//
// additionally faulty unchecked inserts *wont* update the value for the key
for (uint256 i; i < 7; i++) {
// note we in theory are updating all the values here, but in the subsequent
// `get` calls, the old value will return
map.uncheckedInsert(bytes32(i), i + 1);
}
for (uint256 i; i < 7; i++) {
(bool keyExists, uint256 previouslyInsertedValue) = map.get(bytes32(i));
require(keyExists);
// despite our `uncheckedInsert` for exiting keys, we end up with the old value
require(previouslyInsertedValue == i);
}
// you can also check if a key exists in the set
//
// but in general this should only be used if you never actually want the value
// because its the same time complexity as a normal `get` just strips returning the value
bool keyExists = map.containsKey(bytes(1));
}
}
TODO :)