LinkedListLib

A linked list library provided by Modular-Network for using linked list data structures in your project.

This utility library was forked from https://github.com/o0ragman0o/LibCLL into the Modular-Network ethereum-libraries repo at https://github.com/Modular-Network/ethereum-libraries

It has been updated to add additional functionality and be more compatible with solidity 0.4.18 coding patterns.

• Library Address
• License and Warranty
• Installation and Usage
  • How to install
    • How to link
  • Testing
  • solc Installation
    • With standard JSON input
    • solc without standard JSON input
    • solc documentation
  • solc-js Installation
    • Solc-js Installation via Linking
    • Solc-js documentation
• Overview
  • Basic Usage
  • Mutations to State
• Functions
  • listExists(LinkedListLib.LinkedList storage)
    • Arguments
    • Returns
  • nodeExists(LinkedListLib.LinkedList storage)
    • Arguments
    • Returns
  • sizeOf(LinkedListLib.LinkedList storage)
    • Arguments
    • Returns
  • getNode(LinkedListLib.LinkedList storage, uint256)
    • Arguments
    • Returns
  • getAdjacent(LinkedListLib.LinkedList storage, uint256, bool)
    • Arguments
    • Returns
  • getSortedSpot(LinkedListLib.LinkedList storage, uint256, uint256, bool)
    • Arguments
    • Returns
  • createLink(LinkedListLib.LinkedList storage, uint256, uint256, bool)
    • Arguments
    • Returns
  • insert(LinkedListLib.LinkedList storage, uint256, uint256, bool)
    • Arguments
    • Returns
  • remove(LinkedListLib.LinkedList storage, uint256)
    • Arguments
    • Returns
  • push(LinkedListLib.LinkedList storage, uint256, bool)
    • Arguments
    • Returns
  • pop(LinkedListLib.LinkedList storage, bool)
    • Arguments
    • Returns

Library Address

Main Ethereum Network: 0x95FC85B52cC88AC6926bC55d64B88b2AcF18C59B
Rinkeby Test Network:

License and Warranty

Be advised that while we strive to provide professional grade, tested code we cannot guarantee its fitness for your application. This is released under The MIT License (MIT) and as such we will not be held liable for lost funds, etc. Please use your best judgment and note the following:

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Installation and Usage

How to install

npm install ethereum-libraries-linked-list

How to link

This process will allow you to both link your contract to the current on-chain library as well as deploy it in your local environment for development.

Amend the deployment .js file in your truffle migrations/ directory as follows:

var LinkedListLib = artifacts.require("ethereum-libraries-linked-list/build/contracts/LinkedListLib.json");
var YourOtherContract = artifacts.require("./YourOtherContract.sol");
...

module.exports = function(deployer) {
  deployer.deploy(LinkedListLib, {overwrite: false});
  deployer.link(LinkedListLib, YourOtherContract);
  deployer.deploy(YourOtherContract);
};

Note: If you have not created a second deployment .js file in the migrations/ directory, this needs to be done first. You cannot use the 1_initial_migration.js file for your migrations.

Note: The .link() function should be called before you .deploy(YourOtherContract). Also, be sure to include the {overwrite: false} when writing the deployer i.e. .deploy(Array256Lib, {overwrite: false}). This prevents deploying the library onto the main network or Rinkeby test network at your cost and uses the library already on the blockchain. The function should still be called however because it allows you to use it in your development environment. See below

Testing

Test: npm run test

Test Coverage: npm run test:coverage

solc Installation

version 0.4.21

For direction and instructions on how the Solidity command line compiler works see the documentation.

With standard JSON input

The Standard JSON Input provides an easy interface to include libraries. Include the following as part of your JSON input file:

{
  "language": "Solidity",
  "sources":
  {
    "YourContract.sol": {
      ...
      ...
    },
    "LinkedListLib.sol": {
      "content": "[Contents of LinkedListLib.sol]"
    }
  },
  "settings":
  {
    ...
    "libraries": {
      "YourContract.sol": {
        "LinkedListLib": "0x95FC85B52cC88AC6926bC55d64B88b2AcF18C59B"
      }
    }
  }
}

solc without standard JSON input

When creating unlinked binary, the compiler currently leaves special substrings in the compiled bytecode in the form of 'LibraryName____' which leaves a 20 byte space for the library's address. In order to include the deployed library in your bytecode add the following flag to your command:

--libraries "LinkedListLib:0x95FC85B52cC88AC6926bC55d64B88b2AcF18C59B"

Additionally, if you have multiple libraries, you can create a file with one library string per line and include this library as follows:

"LinkedListLib:0x95FC85B52cC88AC6926bC55d64B88b2AcF18C59B"

then add the following flag to your command:

--libraries filename

Finally, if you have an unlinked binary already stored with the 'LibraryName____' placeholder, you can run the compiler with the --link flag and also include the following flag:

--libraries "LinkedListLib:0x95FC85B52cC88AC6926bC55d64B88b2AcF18C59B"

solc documentation

See the solc documentation for further information.

solc-js Installation

version 0.4.21

Solc-js provides javascript bindings for the Solidity compiler and can be found here. Please refer to their documentation for detailed use.

This version of Solc-js also uses the standard JSON input to compile a contract. The entry function is compileStandardWrapper() and you can create a standard JSON object explained under the solc section and incorporate it as follows:

var solc = require('solc');
var fs = require('fs');

var file = fs.readFileSync('/path/to/YourContract.sol','utf8');
var LinkedListLib = fs.readFileSync('./path/to/LinkedListLib.sol','utf8');

var input = {
  "language": "Solidity",
  "sources":
  {
    "YourContract.sol": {
      "content": file
    },
    "StringUtilsLib.sol": {
      "content": LinkedListLib
    }
  },
  "settings":
  {
    ...
    "libraries": {
      "YourContract.sol": {
        "LinkedListLib": "0xD620Ce17fC516671F0fA84Ac88e39dCBb0a1615A"
      }
    }
    ...
  }
}

var output = JSON.parse(solc.compileStandardWrapper(JSON.stringify(input)));

//Where the output variable is a standard JSON output object.

Solc-js Installation via Linking

Solc-js also provides a linking method if you have compiled binary code already with the placeholder. To link this library the call would be:

bytecode = solc.linkBytecode(bytecode, { 'Array256Lib': '0xD620Ce17fC516671F0fA84Ac88e39dCBb0a1615A' });

Solc-js documentation

See the Solc-js documentation for further information.

Overview

Basic Usage

The Linked List library provides functionality needed to create and manipulate a Circular Linked List Data structure by allowing a multitude of different functions to be used to interact with the struct. Functions like push() and pop() can be used to create a FILO stack or FIFO ring buffer. getAdjacent() can also be used to iterate over the list. Brief description of functionality:

• Can check if the list exists and find the size.
• Can check if a certain node exists.
• Gets adjacent nodes to a specified node.
• Finds a spot in a sorted list for a new node to be placed.
• Insert nodes and create links between nodes.
• Remove, push, and pop nodes from the list.

LinkedList is a nested mapping with the first key being the node index (uint256) and the second being the bidirectional link (bool) to a neighboring node. Key 0 implies the head so writes to LinkedList.list[0] or manually linking to Linkedlist.list[0] (e.g. list[var1][false] = 0;) are to be avoided by the calling contract.

    struct LinkedList{
        mapping (uint256 => mapping (bool => uint256)) cll;
    }

Mutations to State

The bidirectional links consist of two State slots (2x uint256) which are written to by the function createLink(). insert() calls createLink() twice for a total of 4 state mutations. remove calls createLink() once and deletes two slots.

DISCLAIMER: As always, please ensure you review this code thoroughly for your team's use. We strive to make our code as solid, clean, and well documented as possible but will not accept liability for unforeseen circumstances in which value is lost or stolen. This includes but not limited to any inability to meet signature requirements to move funds, loss of private keys, transactions you deem unauthorized from an owner's account, etc. The library code has been thoroughly tested by our team and believe it to be suitable enough to be posted in our open source repository, however, you are still responsible for its implementation and security in your smart contract. Please use your best judgment. Please [let us know immediately](https://modular.network "Modular-Network website") if you have discovered any issues or vulnerabilities with this library.

Functions

The following is the list of functions available to use in your smart contract.

listExists(LinkedListLib.LinkedList storage)

(LinkedListLib.sol, line 46)

Checks to see if the list exists. If there is only a head node, it does not exist.

Arguments

LinkedListLib.LinkedList self

Returns

bool

nodeExists(LinkedListLib.LinkedList storage)

(LinkedListLib.sol, line 51)

Checks to see if a specific node exists.

Arguments

LinkedListLib.LinkedList self uint256 _node index of the node to look for

Returns

bool

sizeOf(LinkedListLib.LinkedList storage)

(LinkedListLib.sol, line 78)

Finds the size of the linked list. Head node does not count toward size.

Arguments

LinkedListLib.LinkedList self

Returns

uint256

getNode(LinkedListLib.LinkedList storage, uint256)

(LinkedListLib.sol, line 92)

Returns the links of a node as a tuple.

Arguments

LinkedListLib.LinkedList self
uint256 _node index of the node to look for

Returns

(bool,uint256,uint256) bool indicating if the node exists or not, then the PREV and NEXT node, in that order, both 0 if the node doesn't exist.

getAdjacent(LinkedListLib.LinkedList storage, uint256, bool)

(LinkedListLib.sol, line 106)

Returns the link of a node _node in direction _direction.

Arguments

LinkedListLib.LinkedList self
uint256 _node an existing node to search from
bool _direction a direction to search in

Returns

(bool,uint256) bool indicating if the node exists, then the adjacent node

getSortedSpot(LinkedListLib.LinkedList storage, uint256, uint256, bool)

(LinkedListLib.sol, line 122)

Finds the spot in a sorted list where 'value' can be inserted. Used before insert to build a sorted list.

Arguments

LinkedListLib.LinkedList self
uint256 _node an existing node to search from
uint256 _value node nubmer to find a place for
bool _direction a direction to search in. if NEXT, returns the node after the found spot, if BEFORE, returns the node before.

Returns

uint256

createLink(LinkedListLib.LinkedList storage, uint256, uint256, bool)

(LinkedListLib.sol, line 138)

Creates a bidirectional link between two nodes in direction _direction.

Arguments

LinkedListLib.LinkedList self
uint256 _node first node to link.
uint256 _link node to link to
bool _direction a direction to link in (from the first node)

Returns

insert(LinkedListLib.LinkedList storage, uint256, uint256, bool)

(LinkedListLib.sol, line 148)

Insert node _new beside existing node _node in direction _direction.

Arguments

LinkedListLib.LinkedList self
uint256 _node an existing node to insert next to.
uint256 _new a new node to insert in the list.
bool _direction a direction to insert in

Returns

remove(LinkedListLib.LinkedList storage, uint256)

(LinkedListLib.sol, line 162)

Removes node _node from the list.

Arguments

LinkedListLib.LinkedList self
uint256 _node an existing node to remove.

Returns

uint256

push(LinkedListLib.LinkedList storage, uint256, bool)

(LinkedListLib.sol, line 174)

pushes a new node to one end of the list.

Arguments

LinkedListLib.LinkedList self
uint256 _node an existing node to push to the list.
bool _direction direction to push the node. NEXT for head. PREV for tail.

Returns

pop(LinkedListLib.LinkedList storage, bool)

(LinkedListLib.sol, line 181)

Pops a node of an end of the list.

Arguments

LinkedListLib.LinkedList self
bool _direction a direction to pop the node from. NEXT for head. PREV for tail.

Returns

uint256