Simple and appropriate data organization can challenge Solidity newcomers. It wants us to organize everything in ways many of us aren’t accustomed to.

Are there well-solved general patterns for routine on-chain data organization?

  • which kind of storage? I note there's not yet a sorted storage in the examples. – Paul S Mar 16 '17 at 22:59
up vote 121 down vote accepted

Here are some simple and useful patterns in increasing order of utility.

Event logs are omitted for brevity. In practice, it's desirable to emit events for every important state change.

Simple List Using Array

Strengths

  • Reliably chronological order
  • Provides a count
  • Random access by Row Number (not Id)

Weaknesses

  • No random access by Id
  • No assurance of uniqueness
  • No check for duplicates
  • Uncontrolled growth of the list

Example:

pragma solidity ^0.4.6;

contract simpleList {

  struct EntityStruct {
    address entityAddress;
    uint entityData;
    // more fields
  }

  EntityStruct[] public entityStructs;

  function newEntity(address entityAddress, uint entityData) public returns(uint rowNumber) {
    EntityStruct memory newEntity;
    newEntity.entityAddress = entityAddress;
    newEntity.entityData    = entityData;
    return entityStructs.push(newEntity)-1;
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityStructs.length;
  }
}

Mapping with Struct

Strengths

  • Random access by unique Id
  • Assurance of Id Uniqueness
  • Enclose arrays, mappings, structs within each "record"

Weaknesses

  • Unable to enumerate the keys
  • Unable to count the keys
  • Needs a manual check to distinguish a default from an explicitly "all 0" record

Example:

contract mappingWithStruct {

  struct EntityStruct {
    uint entityData;
    bool isEntity;
  }

  mapping (address => EntityStruct) public entityStructs;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
    return entityStructs[entityAddress].isEntity;
  }

  function newEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(isEntity(entityAddress)) throw; 
    entityStructs[entityAddress].entityData = entityData;
    entityStructs[entityAddress].isEntity = true;
    return true;
  }

  function deleteEntity(address entityAddress) public returns(bool success) {
    if(!isEntity(entityAddress)) throw;
    entityStructs[entityAddress].isEntity = false;
    return true;
  }

  function updateEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) throw;
    entityStructs[entityAddress].entityData = entityData;
    return true;
  }
}

Array of Structs with Unique Ids

Strengths

  • Random access by Row number
  • Assurance of Id uniqueness
  • Enclose arrays, mappings and structs with each "record"

Weaknesses

  • No random access by Id
  • Uncontrolled growth of the list

Example:

contract arrayWithUniqueIds {

  struct EntityStruct {
    address entityAddress;
    uint entityData;
  }

  EntityStruct[] public entityStructs;
  mapping(address => bool) knownEntity;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
    return knownEntity[entityAddress];
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityStructs.length;
  }

  function newEntity(address entityAddress, uint entityData) public returns(uint rowNumber) {
    if(isEntity(entityAddress)) throw;
    EntityStruct memory newEntity;
    newEntity.entityAddress = entityAddress;
    newEntity.entityData = entityData;
    knownEntity[entityAddress] = true;
    return entityStructs.push(newEntity) - 1;
  }

  function updateEntity(uint rowNumber, address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) throw;
    if(entityStructs[rowNumber].entityAddress != entityAddress) throw;
    entityStructs[rowNumber].entityData    = entityData;
    return true;
  }
}

Mapped Structs with Index

Strengths

  • Random access by unique Id or row number
  • Assurance of Id uniqueness
  • Enclose arrays, mappings and structs within each "record"
  • List maintains order of declaration
  • Count the records
  • Enumerate the Ids
  • "Soft" delete an item by setting a boolean

Weaknesses

  • Uncontrolled growth of the list

Example:

contract MappedStructsWithIndex {

  struct EntityStruct {
    uint entityData;
    bool isEntity;
  }

  mapping(address => EntityStruct) public entityStructs;
  address[] public entityList;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
      return entityStructs[entityAddress].isEntity;
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityList.length;
  }

  function newEntity(address entityAddress, uint entityData) public returns(uint rowNumber) {
    if(isEntity(entityAddress)) throw;
    entityStructs[entityAddress].entityData = entityData;
    entityStructs[entityAddress].isEntity = true;
    return entityList.push(entityAddress) - 1;
  }

  function updateEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) throw;
    entityStructs[entityAddress].entityData    = entityData;
    return true;
  }
}

Mapped Structs with Delete-enabled Index

Strengths

  • Random access by unique Id or row number
  • Assurance of Id uniqueness
  • Enclose arrays, mapping and structs within each "record"
  • Count the records
  • Enumerate the ids
  • Logically control the size of the active list with delete function

Weaknesses

  • Marginally increased code complexity
  • Marginally higher storage costs
  • Key list is inherently unordered

Example:

contract mappedWithUnorderedIndexAndDelete {

  struct EntityStruct {
    uint entityData;
    uint listPointer;
  }

  mapping(address => EntityStruct) public entityStructs;
  address[] public entityList;

  function isEntity(address entityAddress) public constant returns(bool isIndeed) {
    if(entityList.length == 0) return false;
    return (entityList[entityStructs[entityAddress].listPointer] == entityAddress);
  }

  function getEntityCount() public constant returns(uint entityCount) {
    return entityList.length;
  }

  function newEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(isEntity(entityAddress)) throw;
    entityStructs[entityAddress].entityData = entityData;
    entityStructs[entityAddress].listPointer = entityList.push(entityAddress) - 1;
    return true;
  }

  function updateEntity(address entityAddress, uint entityData) public returns(bool success) {
    if(!isEntity(entityAddress)) throw;
    entityStructs[entityAddress].entityData = entityData;
    return true;
  }

  function deleteEntity(address entityAddress) public returns(bool success) {
    if(!isEntity(entityAddress)) throw;
    uint rowToDelete = entityStructs[entityAddress].listPointer;
    address keyToMove   = entityList[entityList.length-1];
    entityList[rowToDelete] = keyToMove;
    entityStructs[keyToMove].listPointer = rowToDelete;
    entityList.length--;
    return true;
  }

}

This last one has an explainer here: https://medium.com/@robhitchens/solidity-crud-part-2-ed8d8b4f74ec#.ekc22r5lf

and here: https://bitbucket.org/rhitchens2/soliditycrud/src/83703dcaf4d0c4b0d6adc0377455c4f257aa29a7/docs/?at=master

Folder Tree Example: How can we organize storage of a folder or object tree in Solidity?

Linked List example shows a way to maintain an ordered list using a library. https://github.com/ethereum/dapp-bin/blob/master/library/linkedList.sol 0

  • 3
    Linked lists are quite useful too: they allow enumeration, random access by ID and by index, are inherently ordered, etc. Only downside is O(n) lookup/insertion/deletion by index – Tjaden Hess Mar 22 '17 at 22:54
  • 2
    This makes me think of renaming the function because it appears the purpose of the function is misunderstood. It doesn't validate the input. It's not necessary to do so since anything successfully passed in will be a valid address. Instead, it's checking if the key is already used/ a;ready exists to ensure unique keys. No duplicate keys are allowed. Possibly I should change the function name to something like function keyExists() to prevent confusion. – Rob Hitchens B9lab May 20 '17 at 12:25
  • 2
    It's only a con in certain cases where the data is transient. Suppose you have a case where 90% or more of the data is to be logically deleted. You would end up with an unpruned list pointing to many obsolete records and this might not be ideal. – Rob Hitchens B9lab Sep 26 '17 at 17:28
  • 2
    Not even close. Have a look at medium.com/@robhitchens/solidity-crud-part-1-824ffa69509a and web3 example. JS will fetch the length, iterate, and fetch the rows one at a time. – Rob Hitchens B9lab Sep 26 '17 at 17:59
  • 2
    Suppose you have a dataset where rows are appended and consumed then routinely set to inactive or usedUp. You could end up with clients that have to iterate over an ever-increasing list of obsolete information. Sometimes (not majority) it makes sense to truly remove something from the list. The delete-enabled pattern solves for that. – Rob Hitchens B9lab Apr 18 at 16:37

Adding to Rob's answer, please use revert() as an alternative of throw.From version 0.4.13 the throw keyword is deprecated and will be phased out in the future. Read here for more information: require, assert and revert in solidity.

So, as an example you should change

if(isEntity(entityAddress)) throw;

to

if(isEntity(entityAddress)) revert();

in above code provided by Rob.

  • 2
    Here's the updated code examples using revert(): ethfiddle.com/PgDM-drAc9 – James Duffy Nov 14 '17 at 6:39
  • 2
    Thanks, James! I'm sure that will help people. One could also use require() but that would mean reversing all the rules ... if(bad) revert() => require(!bad) – Rob Hitchens B9lab Nov 14 '17 at 14:48
  • What is the main difference between throw and revert()? Do they do the same thing, by reverting back all the states? @Abhishek Sinha && @Rob Hitchens – alper Dec 9 '17 at 14:55
  • 2
    Starting solc 0.4.13, revert, require and assert deprecate throw. They differ slightly from the original throw in the details such as gas destruction. Have a look over here: ethereum.stackexchange.com/questions/15166/… – Rob Hitchens B9lab Dec 9 '17 at 16:03

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.