Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

merkle-patricia-tree

Package Overview
Dependencies
Maintainers
1
Versions
62
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

merkle-patricia-tree - npm Package Compare versions

Comparing version 0.1.1 to 0.1.2-p

benchmark.js
sha3.js

1088

index.js

@@ -1,8 +0,12 @@

var assert = require('assert'),
async = require('async'),
rlp = require('rlp'),
levelup = require('levelup'),
TrieNode = require('./trieNode'),
ReadStream = require('./readStream');
const assert = require('assert'),
levelup = require('levelup'),
memdown = require('memdown'),
async = require('async'),
rlp = require('rlp'),
TrieNode = require('./trieNode'),
ReadStream = require('./readStream');
const EMPTY_RLP_HASH_ST = '56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421';
const EMPTY_RLP_HASH = new Buffer(EMPTY_RLP_HASH_ST, 'hex');
var internals = {};

@@ -12,48 +16,53 @@

assert(this.constructor === internals.Trie, 'Trie must be instantiated using new');
this.EMPTY_TRIE_ROOT = EMPTY_RLP_HASH;
this.sem = require('semaphore')(1);
assert(this.constructor === internals.Trie, 'Trie must be instantiated using new');
if (db && db.isImmutable !== undefined) {
this.isImmutable = db.isImmutable;
db = db.db;
} else {
this.isImmutable = true;
}
this.sem = require('semaphore')(1);
if (!db) {
db = levelup('', {
db: require('memdown')
});
}
this.db = db;
this.isCheckpoint = false;
if (db instanceof internals.Trie) {
db = db.db;
}
if (typeof root === 'string') {
root = new Buffer(root, 'hex');
}
if (!db) {
db = levelup('', {
db: memdown
});
}
Object.defineProperty(this, 'root', {
set: function (v) {
if (v) {
if (!Buffer.isBuffer(v)) {
if (typeof v === 'string') {
v = new Buffer(v, 'hex');
}
}
assert(v.length === 32, 'Invalid root length. Roots are 32 bytes');
} else {
v = null;
}
this._root = v;
},
get: function () {
return this._root;
this.db = db;
this._cache = levelup('', {
db: memdown
});
this.isCheckpoint = false;
this._checkpoints = [];
if (typeof root === 'string') {
root = new Buffer(root, 'hex');
}
Object.defineProperty(this, 'root', {
set: function (v) {
if (v) {
if (!Buffer.isBuffer(v)) {
if (typeof v === 'string') {
v = new Buffer(v, 'hex');
}
}
});
assert(v.length === 32, 'Invalid root length. Roots are 32 bytes');
} else {
v = EMPTY_RLP_HASH;
}
this._root = v;
},
get: function () {
return this._root;
}
});
this.root = root;
this.root = root;
};
/*
/**
* Gets a value given a key

@@ -64,14 +73,11 @@ * @method get

internals.Trie.prototype.get = function (key, cb) {
var self = this;
var self = this;
self.sem.take(function () {
self._findNode(key, self.root, [], function (err, node, remainder, stack) {
var value = null;
if (node && remainder.length === 0) {
value = node.value;
}
self.sem.leave();
cb(err, value);
});
});
self._findNode(key, self.root, [], function (err, node, remainder, stack) {
var value = null;
if (node && remainder.length === 0) {
value = node.value;
}
cb(err, value);
});
};

@@ -86,26 +92,27 @@

internals.Trie.prototype.put = function (key, value, cb) {
var self = this;
if (value === '') {
self.del(key, cb);
} else {
self.sem.take(function () {
cb = internals.together(cb, self.sem.leave);
var self = this;
if (self.root) {
//first try to find the give key or its nearst node
self._findNode(key, self.root, [], function (err, foundValue, keyRemainder, stack) {
if (err) {
cb(err);
} else {
//then update
self._updateNode(key, value, keyRemainder, stack, cb);
}
});
} else {
//if no root initialize this trie
self._createNewNode(key, value, cb);
}
if (!value || value === '') {
self.del(key, cb);
} else {
cb = internals.together(cb, self.sem.leave);
self.sem.take(function () {
if (self.root.toString('hex') !== EMPTY_RLP_HASH_ST) {
//first try to find the give key or its nearst node
self._findNode(key, self.root, [], function (err, foundValue, keyRemainder, stack) {
if (err) {
cb(err);
} else {
//then update
self._updateNode(key, value, keyRemainder, stack, cb);
}
});
}
} else {
//if no root initialize this trie
self._createNewNode(key, value, cb);
}
});
}
};

@@ -115,19 +122,19 @@

internals.Trie.prototype.del = function (key, cb) {
var self = this;
var self = this;
cb = internals.together(cb, self.sem.leave);
self.sem.take(function () {
cb = internals.together(cb, self.sem.leave);
self._findNode(key, self.root, [], function (err, foundValue, keyRemainder, stack) {
if (err) {
cb(err);
} else if (foundValue) {
self._deleteNode(key, stack, cb);
} else {
cb();
}
});
self.sem.take(function () {
self._findNode(key, self.root, [], function (err, foundValue, keyRemainder, stack) {
if (err) {
cb(err);
} else if (foundValue) {
self._deleteNode(key, stack, cb);
} else {
cb();
}
});
});
};
/*
/**
* Trys to find a node, given a key it will find the closest node to that key

@@ -146,70 +153,70 @@ * and return to the callback a `stack` of nodes to the closet node

internals.Trie.prototype._findNode = function (key, root, stack, cb) {
var self = this;
var self = this;
//parse the node and gets the next node if any to parse
function processNode(node) {
if (!node) {
cb(null, null, key, stack);
return;
//parse the node and gets the next node if any to parse
function processNode(node) {
if (!node) {
cb(null, null, key, stack);
return;
}
stack.push(node);
if (node.type === 'branch') {
//branch
if (key.length === 0) {
cb(null, node, [], stack, cb);
} else {
var branchNode = node.getValue(key[0]);
if (!branchNode) {
//there is no more nodes to find and we didn't find the key
cb(null, null, key, stack);
} else {
key.shift();
self._findNode(key, branchNode, stack, cb);
}
}
} else {
var nodeKey = node.key,
matchingLen = internals.matchingNibbleLength(nodeKey, key),
keyRemainder = key.slice(matchingLen);
stack.push(node);
if (node.type === 'branch') {
//branch
if (key.length === 0) {
cb(null, node, [], stack, cb);
} else {
var branchNode = node.getValue(key[0]);
if (!branchNode) {
//there is no more nodes to find and we didn't find the key
cb(null, null, key, stack);
} else {
key.shift();
self._findNode(key, branchNode, stack, cb);
}
}
if (node.type === 'leaf') {
if (keyRemainder.length !== 0 || key.length !== nodeKey.length) {
//we did not find the key
node = null;
} else {
var nodeKey = node.key,
matchingLen = internals.matchingNibbleLength(nodeKey, key),
keyRemainder = key.slice(matchingLen);
key = [];
}
cb(null, node, key, stack);
if (node.type === 'leaf') {
if (keyRemainder.length !== 0 || key.length !== nodeKey.length) {
//we did not find the key
node = null;
} else {
key = [];
}
cb(null, node, key, stack);
} else if (node.type === 'extention') {
if (matchingLen !== nodeKey.length) {
//we did not find the key
cb(null, null, key, stack);
} else {
self._findNode(keyRemainder, node.value, stack, cb);
}
}
} else if (node.type === 'extention') {
if (matchingLen !== nodeKey.length) {
//we did not find the key
cb(null, null, key, stack);
} else {
self._findNode(keyRemainder, node.value, stack, cb);
}
}
}
}
if (!root) {
cb(null, null, key, []);
return;
}
if (!root) {
cb(null, null, key, []);
return;
}
if (!Array.isArray(key)) {
//convert key to nibbles
key = TrieNode.stringToNibbles(key);
}
if (!Array.isArray(key)) {
//convert key to nibbles
key = TrieNode.stringToNibbles(key);
}
if (!Array.isArray(stack)) {
stack = [];
}
if (!Array.isArray(stack)) {
stack = [];
}
if (!Array.isArray(root) && !Buffer.isBuffer(root)) {
root = new Buffer(root, 'hex');
}
if (!Array.isArray(root) && !Buffer.isBuffer(root)) {
root = new Buffer(root, 'hex');
}
this._lookupNode(root, processNode);
this._lookupNode(root, processNode);
};

@@ -221,46 +228,46 @@

internals.Trie.prototype._findAll = function (root, key, onFound, onDone) {
var self = this;
var self = this;
function processNode(node) {
if (node.type === 'leaf') {
key = key.concat(node.key);
onFound(node, key, onDone);
} else if (node.type === 'extention') {
key = key.concat(node.key);
self._findAll(node.value, key, onFound, onDone);
} else {
var count = 0;
async.whilst(
function () {
return count < 15;
},
function (callback) {
var val = node.getValue(count);
var tempKey = key.slice(0);
tempKey.push(count);
count++;
if (val) {
self._findAll(val, tempKey, onFound, callback);
} else {
callback();
}
},
function (err) {
var lastVal = node.value;
if (lastVal) {
onFound(lastVal, key, onDone);
} else {
onDone();
}
}
);
function processNode(node) {
if (node.type === 'leaf') {
key = key.concat(node.key);
onFound(node, key, onDone);
} else if (node.type === 'extention') {
key = key.concat(node.key);
self._findAll(node.value, key, onFound, onDone);
} else {
var count = 0;
async.whilst(
function () {
return count < 16;
},
function (callback) {
var val = node.getValue(count);
var tempKey = key.slice(0);
tempKey.push(count);
count++;
if (val) {
self._findAll(val, tempKey, onFound, callback);
} else {
callback();
}
},
function (err) {
var lastVal = node.value;
if (lastVal) {
onFound(lastVal, key, onDone);
} else {
onDone();
}
}
);
}
}
if (!root) {
onDone();
return;
}
if (!root || root.toString('hex') === EMPTY_RLP_HASH_ST) {
onDone();
return;
}
this._lookupNode(root, processNode);
this._lookupNode(root, processNode);
};

@@ -270,22 +277,28 @@

internals.Trie.prototype.deleteState = function (root, cb) {
var self = this;
var self = this;
var thisRoot = false;
if (arguments.length === 1) {
this.revert();
cb = root;
root = this.root;
}
if (arguments.length === 1) {
cb = root;
root = this.root;
thisRoot = true;
}
if (root) {
self.sem.take(function () {
cb = internals.together(cb, self.sem.leave);
self._deleteState(root, [], function (err, opStack) {
self.db.batch(opStack, {
encoding: 'binary'
}, cb);
});
});
} else {
cb();
}
if (root.toString('hex') !== EMPTY_RLP_HASH_ST) {
cb = internals.together(cb, self.sem.leave);
self.sem.take(function() {
var opStack = [];
self._deleteState(root, opStack, function() {
if (thisRoot) {
self.root = EMPTY_RLP_HASH;
}
self.db.batch(opStack, {
encoding: 'binary'
}, cb);
});
});
} else {
cb();
}
};

@@ -297,33 +310,33 @@

internals.Trie.prototype._deleteState = function (root, delNodes, cb) {
var self = this;
var self = this;
function processNode(node) {
self._formatNode(node, false, true, delNodes);
if (node.type === 'leaf') {
cb();
} else if (node.type === 'extention') {
self._deleteState(node.value, delNodes, cb);
} else {
var count = 0;
async.whilst(
function () {
return count < 15;
},
function (callback) {
count++;
var val = node.getValue(count);
if (val) {
self._deleteState(val, callback);
} else {
callback();
}
},
function (err) {
cb(err);
}
);
function processNode(node) {
self._formatNode(node, false, true, delNodes);
if (node.type === 'leaf') {
cb();
} else if (node.type === 'extention') {
self._deleteState(node.value, delNodes, cb);
} else {
var count = 0;
async.whilst(
function() {
return count < 16;
},
function(callback) {
count++;
var val = node.getValue(count);
if (val) {
self._deleteState(val, delNodes, callback);
} else {
callback();
}
},
function(err) {
cb(err);
}
);
}
}
this._lookupNode(root, processNode);
this._lookupNode(root, processNode);
};

@@ -343,66 +356,66 @@

var toSave = [],
lastNode = stack.pop();
var toSave = [],
lastNode = stack.pop();
//add the new nodes
key = TrieNode.stringToNibbles(key);
if (lastNode.type === 'branch') {
stack.push(lastNode);
if (keyRemainder !== 0) {
//add an extention to a branch node
keyRemainder.shift();
//create a new leaf
var newLeaf = new TrieNode('leaf', keyRemainder, value);
stack.push(newLeaf);
} else {
lastNode.value = value;
}
} else if (lastNode.type === 'leaf' && keyRemainder.length === 0) {
//just updating a found value
lastNode.value = value;
stack.push(lastNode);
//add the new nodes
key = TrieNode.stringToNibbles(key);
if (lastNode.type === 'branch') {
stack.push(lastNode);
if (keyRemainder !== 0) {
//add an extention to a branch node
keyRemainder.shift();
//create a new leaf
var newLeaf = new TrieNode('leaf', keyRemainder, value);
stack.push(newLeaf);
} else {
//if extension; create a branch node
var lastKey = lastNode.key,
matchingLength = internals.matchingNibbleLength(lastKey, keyRemainder),
newBranchNode = new TrieNode('branch');
lastNode.value = value;
}
} else if (lastNode.type === 'leaf' && keyRemainder.length === 0) {
//just updating a found value
lastNode.value = value;
stack.push(lastNode);
} else {
//if extension; create a branch node
var lastKey = lastNode.key,
matchingLength = internals.matchingNibbleLength(lastKey, keyRemainder),
newBranchNode = new TrieNode('branch');
//create a new extention node
if (matchingLength !== 0) {
var newKey = lastNode.key.slice(0, matchingLength),
newExtNode = new TrieNode('extention', newKey, value);
stack.push(newExtNode);
lastKey.splice(0, matchingLength);
keyRemainder.splice(0, matchingLength);
}
//create a new extention node
if (matchingLength !== 0) {
var newKey = lastNode.key.slice(0, matchingLength),
newExtNode = new TrieNode('extention', newKey, value);
stack.push(newExtNode);
lastKey.splice(0, matchingLength);
keyRemainder.splice(0, matchingLength);
}
stack.push(newBranchNode);
stack.push(newBranchNode);
if (lastKey.length !== 0) {
var branchKey = lastKey.shift();
if (lastKey.length !== 0 || lastNode.type === 'leaf') {
//shriking extention or leaf
lastNode.key = lastKey;
var formatedNode = this._formatNode(lastNode, false, toSave);
newBranchNode.setValue(branchKey, formatedNode);
} else {
//remove extention or attaching
this._formatNode(lastNode, false, true, toSave);
newBranchNode.setValue(branchKey, lastNode.value);
}
} else {
newBranchNode.value = lastNode.value;
}
if (lastKey.length !== 0) {
var branchKey = lastKey.shift();
if (lastKey.length !== 0 || lastNode.type === 'leaf') {
//shriking extention or leaf
lastNode.key = lastKey;
var formatedNode = this._formatNode(lastNode, false, toSave);
newBranchNode.setValue(branchKey, formatedNode);
} else {
//remove extention or attaching
this._formatNode(lastNode, false, true, toSave);
newBranchNode.setValue(branchKey, lastNode.value);
}
} else {
newBranchNode.value = lastNode.value;
}
if (keyRemainder.length !== 0) {
keyRemainder.shift();
//add a leaf node to the new branch node
var newLeafNode = new TrieNode('leaf', keyRemainder, value);
stack.push(newLeafNode);
} else {
newBranchNode.value = value;
}
if (keyRemainder.length !== 0) {
keyRemainder.shift();
//add a leaf node to the new branch node
var newLeafNode = new TrieNode('leaf', keyRemainder, value);
stack.push(newLeafNode);
} else {
newBranchNode.value = value;
}
}
this._saveStack(key, stack, toSave, cb);
this._saveStack(key, stack, toSave, cb);
};

@@ -419,145 +432,151 @@

internals.Trie.prototype._saveStack = function (key, stack, opStack, cb) {
var lastRoot;
//update nodes
while (stack.length) {
var node = stack.pop();
//remove old values
this._formatNode(node, stack.length === 0, true, opStack);
if (node.type === 'leaf') {
key.splice(key.length - node.key.length);
} else if (node.type === 'extention') {
key.splice(key.length - node.key.length);
if (lastRoot) {
node.value = lastRoot;
}
} else if (node.type === 'branch') {
if (lastRoot) {
var branchKey = key.pop();
node.setValue(branchKey, lastRoot);
}
}
lastRoot = this._formatNode(node, stack.length === 0, opStack);
var lastRoot;
//update nodes
while (stack.length) {
var node = stack.pop();
//remove old values
this._formatNode(node, stack.length === 0, true, opStack);
if (node.type === 'leaf') {
key.splice(key.length - node.key.length);
} else if (node.type === 'extention') {
key.splice(key.length - node.key.length);
if (lastRoot) {
node.value = lastRoot;
}
} else if (node.type === 'branch') {
if (lastRoot) {
var branchKey = key.pop();
node.setValue(branchKey, lastRoot);
}
}
lastRoot = this._formatNode(node, stack.length === 0, opStack);
}
assert(key.length === 0, 'key length should be 0 after we are done processing the stack');
//assert(key.length === 0, 'key length should be 0 after we are done processing the stack');
if (lastRoot) {
this.root = lastRoot;
}
if (this.isCheckpoint) {
this._cache.db.batch(opStack, {
encoding: 'binary'
}, cb);
} else {
this.db.batch(opStack, {
encoding: 'binary'
}, cb);
}
if (lastRoot) {
this.root = lastRoot;
}
if (this.isCheckpoint) {
this._cache.batch(opStack, {
encoding: 'binary'
}, cb);
} else {
this.db.batch(opStack, {
encoding: 'binary'
}, cb);
}
};
internals.Trie.prototype._deleteNode = function (key, stack, cb) {
function processBranchNode(key, branchKey, branchNode, parentNode, stack) {
//branchNode is the node ON the branch node not THE branch node
var branchNodeKey = branchNode.key;
if (!parentNode || parentNode.type === 'branch') {
//branch->?
if (parentNode) stack.push(parentNode);
function processBranchNode(key, branchKey, branchNode, parentNode, stack) {
//branchNode is the node ON the branch node not THE branch node
var branchNodeKey = branchNode.key;
if (!parentNode || parentNode.type === 'branch') {
//branch->?
if (parentNode) stack.push(parentNode);
if (branchNode.type === 'branch') {
//create an extention node
//branch->extention->branch
var extentionNode = new TrieNode('extention', [branchKey], null);
stack.push(extentionNode);
key.push(branchKey);
} else {
//branch key is an extention or a leaf
//branch->(leaf or extention)
branchNodeKey.unshift(branchKey);
branchNode.key = branchNodeKey;
if (branchNode.type === 'branch') {
//create an extention node
//branch->extention->branch
var extentionNode = new TrieNode('extention', [branchKey], null);
stack.push(extentionNode);
key.push(branchKey);
} else {
//branch key is an extention or a leaf
//branch->(leaf or extention)
branchNodeKey.unshift(branchKey);
branchNode.key = branchNodeKey;
//hackery. This is equvilant to array.concat; except we need keep the
//rerfance to the `key` that was passed in.
branchNodeKey.unshift(0);
branchNodeKey.unshift(key.length);
key.splice.apply(key, branchNodeKey);
//hackery. This is equvilant to array.concat; except we need keep the
//rerfance to the `key` that was passed in.
branchNodeKey.unshift(0);
branchNodeKey.unshift(key.length);
key.splice.apply(key, branchNodeKey);
}
stack.push(branchNode);
} else {
//parent is a extention
var parentKey = parentNode.key;
if (branchNode.type === 'branch') {
//ext->branch
parentKey.push(branchKey);
key.push(branchKey);
parentNode.key = parentKey;
stack.push(parentNode);
} else {
//branch node is an leaf or extention and parent node is an exstention
//add two keys together
//dont push the parent node
branchNodeKey.unshift(branchKey);
parentKey = parentKey.concat(branchNodeKey);
branchNode.key = parentKey;
}
stack.push(branchNode);
}
}
stack.push(branchNode);
} else {
//parent is a extention
var parentKey = parentNode.key;
if (branchNode.type === 'branch') {
//ext->branch
parentKey.push(branchKey);
key.push(branchKey);
parentNode.key = parentKey;
stack.push(parentNode);
} else {
//branch node is an leaf or extention and parent node is an exstention
//add two keys together
//dont push the parent node
branchNodeKey.unshift(branchKey);
parentKey = parentKey.concat(branchNodeKey);
branchNode.key = parentKey;
}
stack.push(branchNode);
}
}
var lastNode = stack.pop(),
parentNode = stack.pop(),
opStack = [],
self = this;
var lastNode = stack.pop(),
parentNode = stack.pop(),
opStack = [],
self = this;
if (!Array.isArray(key)) {
//convert key to nibbles
key = TrieNode.stringToNibbles(key);
if (!Array.isArray(key)) {
//convert key to nibbles
key = TrieNode.stringToNibbles(key);
}
if (!parentNode) {
//the root here has to be a leaf.
this.root = EMPTY_RLP_HASH;
if (!this.isCheckpoint){
this.db.del(this.root, cb);
} else{
cb();
}
if (!parentNode) {
//the root here has to be a leaf.
if (!this.isCheckpoint) this.db.del(this.root, cb);
this.root = null;
} else {
if (lastNode.type === 'branch') {
lastNode.value = null;
} else {
if (lastNode.type === 'branch') {
lastNode.value = null;
} else {
//the lastNode has to be a leaf if its not a branch. And a leaf's parent
//if it has one must be a branch.
var lastNodeKey = lastNode.key;
key.splice(key.length - lastNodeKey.length);
//delete the value
this._formatNode(lastNode, false, true, opStack);
parentNode.setValue(key.pop(), null);
lastNode = parentNode;
parentNode = stack.pop();
}
//the lastNode has to be a leaf if its not a branch. And a leaf's parent
//if it has one must be a branch.
var lastNodeKey = lastNode.key;
key.splice(key.length - lastNodeKey.length);
//delete the value
this._formatNode(lastNode, false, true, opStack);
parentNode.setValue(key.pop(), null);
lastNode = parentNode;
parentNode = stack.pop();
}
//nodes on the branch
var branchNodes = [];
//count the number of nodes on the branch
lastNode.raw.forEach(function (node, i) {
var val = lastNode.getValue(i);
if (val) branchNodes.push([i, val]);
});
//nodes on the branch
var branchNodes = [];
//count the number of nodes on the branch
lastNode.raw.forEach(function (node, i) {
var val = lastNode.getValue(i);
if (val) branchNodes.push([i, val]);
});
//if there is only one branch node left, collapse the branch node
if (branchNodes.length === 1) {
//add the one remaing branch node to node above it
var branchNode = branchNodes[0][1],
branchNodeKey = branchNodes[0][0];
//if there is only one branch node left, collapse the branch node
if (branchNodes.length === 1) {
//add the one remaing branch node to node above it
var branchNode = branchNodes[0][1],
branchNodeKey = branchNodes[0][0];
//look up node
this._lookupNode(branchNode, function (foundNode) {
processBranchNode(key, branchNodeKey, foundNode, parentNode, stack, opStack);
self._saveStack(key, stack, opStack, cb);
});
//look up node
this._lookupNode(branchNode, function (foundNode) {
processBranchNode(key, branchNodeKey, foundNode, parentNode, stack, opStack);
self._saveStack(key, stack, opStack, cb);
});
} else {
//simple removing a leaf and recaluclation the stack
stack.push(parentNode);
stack.push(lastNode);
self._saveStack(key, stack, opStack, cb);
}
} else {
//simple removing a leaf and recaluclation the stack
if(parentNode){
stack.push(parentNode);
}
stack.push(lastNode);
self._saveStack(key, stack, opStack, cb);
}
}
};

@@ -567,127 +586,151 @@

internals.Trie.prototype._createNewNode = function (key, value, cb) {
var newNode = new TrieNode('leaf', key, value);
this.root = newNode.hash();
//save
if (this.isCheckpoint) {
this._cache.put(key, value, cb);
} else {
this.db.put(this.root, newNode.serialize(), {
encoding: 'binary'
}, cb);
}
var newNode = new TrieNode('leaf', key, value);
this.root = newNode.hash();
//save
var db;
if (this.isCheckpoint) {
db = this._cache;
} else {
db = this.db;
}
db.put(this.root, newNode.serialize(), {
encoding: 'binary'
}, cb);
};
//formats node to be saved by levelup.batch.
//returns either the hash that will be used key or the rawNode
internals.Trie.prototype._formatNode = function (node, topLevel, remove, opStack) {
if (arguments.length === 3) {
opStack = remove;
remove = false;
if (arguments.length === 3) {
opStack = remove;
remove = false;
}
var rlpNode = node.serialize();
if (rlpNode.length >= 32 || topLevel) {
var hashRoot = node.hash();
if (remove && !this.isCheckpoint) {
opStack.push({
type: 'del',
key: hashRoot
});
} else {
opStack.push({
type: 'put',
key: hashRoot,
value: rlpNode
});
}
var rlpNode = node.serialize();
if (rlpNode.length >= 32 || topLevel) {
var hashRoot = node.hash();
if (remove) {
if (!this.isImmutable) {
opStack.push({
type: 'del',
key: hashRoot
});
}
} else {
opStack.push({
type: 'put',
key: hashRoot,
value: rlpNode
});
}
return hashRoot;
}
return node.raw;
return hashRoot;
}
return node.raw;
};
internals.Trie.prototype._lookupNode = function (node, cb) {
var self = this;
function dbLookup() {
self.db.get(node, {
encoding: 'binary'
}, function (err, foundNode) {
if (err || !foundNode) {
cb(null);
} else {
foundNode = rlp.decode(foundNode);
cb(new TrieNode(foundNode));
}
});
}
var self = this;
if (Buffer.isBuffer(node) && node.length === 32) {
//resovle hash to node
if (this.isCheckpoint) {
this._cache.db.get(node, {
encoding: 'binary'
}, function (err, foundNode) {
if (err || !foundNode) {
dbLookup();
} else {
foundNode = rlp.decode(foundNode);
cb(new TrieNode(foundNode));
}
});
function dbLookup(db, cb2) {
db.get(node, {
encoding: 'binary'
}, function (err, foundNode) {
if (err || !foundNode) {
cb2(null);
} else {
foundNode = rlp.decode(foundNode);
cb2(new TrieNode(foundNode));
}
});
}
if (Buffer.isBuffer(node) && node.length === 32) {
//resovle hash to node
if (this.isCheckpoint) {
dbLookup(this._cache, function(foundNode){
if (!foundNode) {
dbLookup(self.db, cb);
} else {
dbLookup();
cb(foundNode);
}
});
} else {
cb(new TrieNode(node));
dbLookup(this.db, cb);
}
} else {
cb(new TrieNode(node));
}
};
//creates a readstream
internals.Trie.prototype.createReadStream = function () {
return new ReadStream(this);
return new ReadStream(this);
};
//creates a checkout
internals.Trie.prototype.checkpoint = function () {
var self = this;
self.sem.take(function () {
self._cache = new internals.Trie({
isImmutable: false
});
if (!self.isCheckpoint) {
self._checkpointRoot = self.root;
}
self.isCheckpoint = true;
self.sem.leave();
});
//creates a checkpoint
internals.Trie.prototype.checkpoint = function() {
var self = this;
self._checkpoints.push(self.root);
self.isCheckpoint = true;
};
//commits a checkpoint.
internals.Trie.prototype.commit = function (cb) {
var self = this;
var self = this;
cb = internals.together(cb, self.sem.leave);
self.sem.take(function () {
cb = internals.together(cb, self.sem.leave);
if (self.isCheckpoint) {
self.isCheckpoint = false;
self._cache.db.createReadStream().pipe(self.db.createWriteStream()).on('close', cb);
} else {
cb();
}
});
self.sem.take(function () {
self._checkpoints.pop();
if (!self._checkpoints.length && self.isCheckpoint) {
self.isCheckpoint = false;
self._cache.createReadStream().pipe(self.db.createWriteStream()).on('close', cb);
} else {
cb();
}
});
};
internals.Trie.prototype.revert = function () {
var self = this;
//reverts a checkpoint
internals.Trie.prototype.revert = function (cb) {
var self = this;
cb = internals.together(cb, self.sem.leave);
self.sem.take(function () {
delete self._cache;
self.root = self._checkpointRoot;
self.isCheckpoint = false;
self.sem.leave();
});
self.sem.take(function () {
if(self._checkpoints.length){
self.root = self._checkpoints.pop();
}
if(!self._checkpoints.length){
self.isCheckpoint = false;
}
cb();
});
};
//creates a new trie with a shared cache
internals.Trie.prototype.copy = function () {
var trie = new internals.Trie(this.db);
trie.isCheckpoint = this.isCheckpoint;
trie._cache = this._cache;
return trie;
};
/**
* runs a `hash` of command
* @method batch
* @param {Object} ops
* @param {Function} cb
*/
internals.Trie.prototype.batch = function(ops, cb){
var self = this;
var keys = Object.keys(ops);
async.eachSeries(keys, function(key, cb2){
var op = ops[key];
self.put(op[0], op[1], cb2);
}, cb);
};
/**
* Returns the number of in order matching nibbles of two give nibble arrayes

@@ -699,7 +742,7 @@ * @method matchingNibbleLength

internals.matchingNibbleLength = function (nib1, nib2) {
var i = 0;
while (nib1[i] === nib2[i] && nib1.length > i) {
i++;
}
return i;
var i = 0;
while (nib1[i] === nib2[i] && nib1.length > i) {
i++;
}
return i;
};

@@ -712,18 +755,21 @@

internals.together = function () {
var funcs = arguments,
length = funcs.length,
index = length;
var funcs = arguments,
length = funcs.length,
index = length;
if (!length) {
return function () {};
}
if (!length) {
return function () {};
}
return function () {
length = index;
return function () {
length = index;
while (length--) {
var result = funcs[length].apply(this, arguments);
}
return result;
};
while (length--) {
var fn = funcs[length];
if (typeof fn === 'function') {
var result = funcs[length].apply(this, arguments);
}
}
return result;
};
};

34

package.json
{
"name": "merkle-patricia-tree",
"version": "0.1.1",
"version": "0.1.2p",
"description": "This is an implementation of the modified merkle patricia tree as speficed in the Ethereum's yellow paper.",

@@ -28,14 +28,30 @@ "main": "index.js",

"dependencies": {
"async": "~0.8.0",
"leveldown": "^0.10.2",
"memdown": "^0.10.1",
"rlp": "0.0.4",
"semaphore": "^1.0.1",
"async": ">=0.8.0",
"crypto-js": "^3.1.2-5",
"levelup": "*",
"memdown": "^1.0.0",
"rlp": "0.0.11",
"semaphore": ">=1.0.1",
"sha3": "~1.0.0"
},
"devDependencies": {
"levelup": "~0.18.3",
"leveldown": "~0.10.2",
"mocha": "~1.18.2"
"mocha": "~1.18.2",
"ethrereum-tests": "git+https://github.com/ethereum/tests.git#develop"
},
"browser": {
"sha3": "./sha3.js"
},
"testling": {
"files": "test/*.js",
"harness": "mocha-bdd",
"browsers": [
"chrome/22..latest",
"firefox/16..latest",
"safari/latest",
"opera/11.0..latest",
"iphone/6",
"ipad/6",
"android-browser/latest"
]
}
}

28

README.md

@@ -27,9 +27,6 @@ #modified merkle patricia tree [![Build Status](https://travis-ci.org/wanderer/merkle-patricia-tree.svg?branch=master)](https://travis-ci.org/wanderer/merkle-patricia-tree)

### `new new Trie([db], [root])`
### `new new Trie([options], [root])`
### `new Trie([root])`
Creates a new Trie object
- `db` - A instance of [levelup](https://github.com/rvagg/node-levelup/) or compatiable API. If no db is `null` or left undefined then the the trie will be stored in memory vai [memdown](https://github.com/rvagg/memdown)
- `root` - A hex `String` or `Buffer` for the root of a prevously stored trie.
- `options` - hash with the following
- `immutable` - A `Boolean` determing if the Trie will be immutable or not. This property can be changed later.
- `db` - the db

@@ -40,4 +37,4 @@ --------------------------------------------------------

- `root` - The root of the `trie` as a `Buffer`
- `isCheckpoint` - A `Boolean` determining if you are saving to a checkpoint or directly to the db
- `isImmutable` - A `Boolean` flag determing if the Trie is immutable or not
- `isCheckpoint` - A `Boolean` determining if you are saving to a checkpoint or directly to the db
- `EMPTY_TRIE_ROOT` - A `buffer` that is a the Root for an empty trie.

@@ -70,3 +67,3 @@ --------------------------------------------------------

#### `trie.checkpoint()`
Creates a checkpoint that can later be reverted to or commited. After this is called, no changes to the trie will be permanently saved until `commitCheckpoint` is called.
Creates a checkpoint that can later be reverted to or commited. After this is called, no changes to the trie will be permanently saved until `commit` is called.

@@ -82,8 +79,21 @@ --------------------------------------------------------

#### `trie.revert()`
revets the trie to the state it was at when `createCheckpoint` was first called
revets the trie to the state it was at when `checkpoint` was first called
--------------------------------------------------------
#### `trie.batch(operations)`
Give an hash of operation adds them to the DB
- `operations` a hash of `key`/`values` to add to the trie.
example
```javascript
var ops = {
'dog': 'dogecoin',
'cat': 'meow',
'bird': '' //delete bird
}
```
--------------------------------------------------------
#### `trie.deleteState([stateRoot], cb)`
Deletes a the nodes of a given stateroot. If no stateroot is given then it will delete the current state.
Deletes all the nodes of a given stateroot. If no stateroot is given then it will delete the current state.
- `cb` - a callback `Function`

@@ -90,0 +100,0 @@

48

readStream.js
var Readable = require('stream').Readable,
TrieNode = require('./trieNode'),
util = require('util');
TrieNode = require('./trieNode'),
util = require('util');

@@ -8,7 +8,7 @@ var internals = {};

exports = module.exports = internals.ReadStream = function (trie) {
this.trie = trie;
this.next = null;
Readable.call(this, {
objectMode: true
});
this.trie = trie;
this.next = null;
Readable.call(this, {
objectMode: true
});
};

@@ -19,20 +19,20 @@

internals.ReadStream.prototype._read = function () {
var self = this;
if (this.next) {
this.next();
} else if (!this.started) {
this.started = true;
this.trie._findAll(this.trie.root, [], function (val, key, onDone) {
key = TrieNode.nibblesToBuffer(key);
self.next = onDone;
if (val) {
self.push({
key: key,
value: val.value
});
}
}, function () {
self.push(null);
var self = this;
if (this.next) {
this.next();
} else if (!this.started) {
this.started = true;
this.trie._findAll(this.trie.root, [], function (val, key, onDone) {
key = TrieNode.nibblesToBuffer(key);
self.next = onDone;
if (val) {
self.push({
key: key,
value: val.value
});
}
}
}, function () {
self.push(null);
});
}
};

621

test/index.js
var Trie = require('../index.js'),
async = require('async'),
fs = require('fs'),
rlp = require('rlp'),
levelup = require('levelup'),
Sha3 = require('sha3'),
assert = require('assert');
async = require('async'),
rlp = require('rlp'),
Sha3 = require('sha3'),
assert = require('assert'),
jsonTests = require('ethereum-tests').trieTests;
var dbLoc = './test/testdb',
internals = {};
describe('simple save and retrive', function () {
var trie = new Trie();
var trie = new Trie();
it('should not crash if given a non-existant root', function (done) {
var root = new Buffer('3f4399b08efe68945c1cf90ffe85bbe3ce978959da753f9e649f034015b8817d', 'hex');
var trie11 = new Trie(null, root);
it('should not crash if given a non-existant root', function (done) {
var root = new Buffer('3f4399b08efe68945c1cf90ffe85bbe3ce978959da753f9e649f034015b8817d', 'hex');
var trie11 = new Trie(null, root);
trie11.get('test', function (err, value) {
assert.equal(value, null);
done();
});
trie11.get('test', function (err, value) {
assert.equal(value, null);
done();
});
});
it('save a value', function (done) {
trie.put('test', 'one', function () {
done();
});
it('save a value', function (done) {
trie.put('test', 'one', function () {
done();
});
});
it('should get a value', function (done) {
trie.get('test', function (err, value) {
assert.equal(value.toString(), 'one');
done();
});
it('should get a value', function (done) {
trie.get('test', function (err, value) {
assert.equal(value.toString(), 'one');
done();
});
});
it('should update a value', function (done) {
trie.put('test', 'two', function () {
trie.get('test', function (err, value) {
assert.equal(value.toString(), 'two');
done();
});
});
it('should update a value', function (done) {
trie.put('test', 'two', function () {
trie.get('test', function (err, value) {
assert.equal(value.toString(), 'two');
done();
});
});
});
it('should delete a value', function (done) {
trie.del('test', function (stack) {
trie.get('test', function (err, value) {
console.log(value);
done();
});
});
it('should delete a value', function (done) {
trie.del('test', function (stack) {
trie.get('test', function (err, value) {
console.log(value);
done();
});
});
});
it('should recreate a value', function (done) {
trie.put('test', 'one', function () {
done();
});
it('should recreate a value', function (done) {
trie.put('test', 'one', function () {
done();
});
});
it('should get updated a value', function (done) {
trie.get('test', function (err, value) {
assert.equal(value.toString(), 'one');
done();
});
it('should get updated a value', function (done) {
trie.get('test', function (err, value) {
assert.equal(value.toString(), 'one');
done();
});
});
it('should create a branch here', function (done) {
trie.put('doge', 'coin', function () {
assert.equal('de8a34a8c1d558682eae1528b47523a483dd8685d6db14b291451a66066bf0fc', trie.root.toString('hex'));
done();
});
it('should create a branch here', function (done) {
trie.put('doge', 'coin', function () {
assert.equal('de8a34a8c1d558682eae1528b47523a483dd8685d6db14b291451a66066bf0fc', trie.root.toString('hex'));
done();
});
});
it('should get a value that is in a branch', function (done) {
trie.get('doge', function (err, value) {
assert.equal(value.toString(), 'coin');
done();
});
it('should get a value that is in a branch', function (done) {
trie.get('doge', function (err, value) {
assert.equal(value.toString(), 'coin');
done();
});
});
it('should delete from a branch', function (done) {
trie.del('doge', function (err, stack) {
trie.get('doge', function (err, value) {
assert.equal(value, null);
done();
});
});
it('should delete from a branch', function (done) {
trie.del('doge', function (err, stack) {
trie.get('doge', function (err, value) {
assert.equal(value, null);
done();
});
});
});
it('it should totally delete a state', function (done) {
trie.deleteState(done);
});
it('it should totally delete a state', function (done) {
trie.deleteState(done);
});

@@ -101,72 +96,71 @@ });

describe('storing longer values', function () {
var db2 = levelup('./test/testdb2');
var trie2 = new Trie();
var trie2 = new Trie();
var longString = 'this will be a really really really long value';
var longStringRoot = 'b173e2db29e79c78963cff5196f8a983fbe0171388972106b114ef7f5c24dfa3';
var longString = 'this will be a really really really long value';
var longStringRoot = 'b173e2db29e79c78963cff5196f8a983fbe0171388972106b114ef7f5c24dfa3';
it('should store a longer string', function (done) {
trie2.put('done', longString, function (err, value) {
trie2.put('doge', 'coin', function (err, value) {
assert.equal(longStringRoot, trie2.root.toString('hex'));
done();
});
});
it('should store a longer string', function (done) {
trie2.put('done', longString, function (err, value) {
trie2.put('doge', 'coin', function (err, value) {
assert.equal(longStringRoot, trie2.root.toString('hex'));
done();
});
});
});
it('should retreive a longer value', function (done) {
trie2.get('done', function (err, value) {
assert.equal(value.toString(), longString);
done();
});
it('should retreive a longer value', function (done) {
trie2.get('done', function (err, value) {
assert.equal(value.toString(), longString);
done();
});
});
it('should when being modiefied delete the old value', function (done) {
trie2.put('done', 'test', function () {
done();
});
it('should when being modiefied delete the old value', function (done) {
trie2.put('done', 'test', function () {
done();
});
});
it('it should totally delete a state', function (done) {
trie2.deleteState(done);
});
it('it should totally delete a state', function (done) {
trie2.deleteState(done);
});
it('it should totally delete a state', function (done) {
trie2.deleteState(done);
it('it should totally delete a state', function (done) {
trie2.deleteState(done);
});
it('should be an empty trie now', function (done) {
var stream = trie2.createReadStream();
stream.on('data', function (val) {
assert(false, 'got data');
});
it('should be an empty trie now', function (done) {
var stream = trie2.createReadStream();
stream.on('data', function (val) {
assert(false);
});
stream.on('end', function (val) {
done();
});
stream.on('end', function (val) {
done();
});
});
});
describe('testing Extentions and branches', function () {
var trie3 = new Trie();
var trie3 = new Trie();
it('should store a value', function (done) {
trie3.put('doge', 'coin', function () {
done();
});
it('should store a value', function (done) {
trie3.put('doge', 'coin', function () {
done();
});
});
it('should create extention to store this value', function (done) {
trie3.put('do', 'verb', function () {
assert.equal('f803dfcb7e8f1afd45e88eedb4699a7138d6c07b71243d9ae9bff720c99925f9', trie3.root.toString('hex'));
done();
});
it('should create extention to store this value', function (done) {
trie3.put('do', 'verb', function () {
assert.equal('f803dfcb7e8f1afd45e88eedb4699a7138d6c07b71243d9ae9bff720c99925f9', trie3.root.toString('hex'));
done();
});
});
it('should store this value under the extention ', function (done) {
trie3.put('done', 'finished', function () {
assert.equal('409cff4d820b394ed3fb1cd4497bdd19ffa68d30ae34157337a7043c94a3e8cb', trie3.root.toString('hex'));
done();
});
it('should store this value under the extention ', function (done) {
trie3.put('done', 'finished', function () {
assert.equal('409cff4d820b394ed3fb1cd4497bdd19ffa68d30ae34157337a7043c94a3e8cb', trie3.root.toString('hex'));
done();
});
});

@@ -176,23 +170,23 @@ });

describe('testing Extentions and branches - reverse', function () {
var trie3 = new Trie();
var trie3 = new Trie();
it('should create extention to store this value', function (done) {
trie3.put('do', 'verb', function () {
done();
});
it('should create extention to store this value', function (done) {
trie3.put('do', 'verb', function () {
done();
});
});
it('should store a value', function (done) {
trie3.put('doge', 'coin', function () {
done();
});
it('should store a value', function (done) {
trie3.put('doge', 'coin', function () {
done();
});
});
it('should store this value under the extention ', function (done) {
trie3.put('done', 'finished', function () {
assert.equal('409cff4d820b394ed3fb1cd4497bdd19ffa68d30ae34157337a7043c94a3e8cb', trie3.root.toString('hex'));
done();
});
it('should store this value under the extention ', function (done) {
trie3.put('done', 'finished', function () {
assert.equal('409cff4d820b394ed3fb1cd4497bdd19ffa68d30ae34157337a7043c94a3e8cb', trie3.root.toString('hex'));
done();
});
});

@@ -202,82 +196,76 @@ });

describe('testing deletions cases', function () {
var db6 = levelup('./test/testdb6');
var trie3 = new Trie();
var trie3 = new Trie();
it('should delete from a branch->branch-branch', function (done) {
async.parallel([
async.apply(trie3.put.bind(trie3), new Buffer([11, 11, 11]), 'first'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 22, 22]), 'create the first branch'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 34, 44]), 'create the last branch')
], function () {
trie3.del(new Buffer([12, 22, 22]), function () {
trie3.get(new Buffer([12, 22, 22]), function (err, val) {
assert.equal(null, val);
it('should delete from a branch->branch-branch', function (done) {
async.parallel([
async.apply(trie3.put.bind(trie3), new Buffer([11, 11, 11]), 'first'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 22, 22]), 'create the first branch'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 34, 44]), 'create the last branch')
], function () {
trie3.del(new Buffer([12, 22, 22]), function () {
trie3.get(new Buffer([12, 22, 22]), function (err, val) {
assert.equal(null, val);
db6 = levelup('./test/testdb6.1');
trie3 = new Trie(db6);
done();
});
});
trie3 = new Trie();
done();
});
});
});
});
it('should delete from a branch->branch-extention', function (done) {
trie3.put(new Buffer([11, 11, 11]), 'first', function () {
//create the top branch
trie3.put(new Buffer([12, 22, 22]), 'create the first branch', function () {
//crete the middle branch
trie3.put(new Buffer([12, 33, 33]), 'create the middle branch', function () {
trie3.put(new Buffer([12, 33, 44]), 'create the last branch', function () {
//delete the middle branch
trie3.del(new Buffer([12, 22, 22]), function () {
trie3.get(new Buffer([12, 22, 22]), function (err, val) {
assert.equal(null, val);
done();
});
});
});
});
});
it('should delete from a branch->branch-extention', function (done) {
async.parallel([
async.apply(trie3.put.bind(trie3), new Buffer([11, 11, 11]), 'first'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 22, 22]), 'create the first branch'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 33, 33]), 'create the middle branch'),
async.apply(trie3.put.bind(trie3), new Buffer([12, 33, 44]), 'create the last branch')
], function () {
trie3.del(new Buffer([12, 22, 22]), function () {
trie3.get(new Buffer([12, 22, 22]), function (err, val) {
assert.equal(null, val);
done();
});
});
});
});
it('should delete from a extention->branch-extention', function (done) {
trie3.put(new Buffer([11, 11, 11]), 'first', function () {
//create the top branch
trie3.put(new Buffer([12, 22, 22]), 'create the first branch', function () {
//crete the middle branch
trie3.put(new Buffer([12, 33, 33]), 'create the middle branch', function () {
trie3.put(new Buffer([12, 33, 44]), 'create the last branch', function () {
//delete the middle branch
trie3.del(new Buffer([11, 11, 11]), function () {
trie3.get(new Buffer([11, 11, 11]), function (err, val) {
assert.equal(null, val);
done();
});
});
});
});
it('should delete from a extention->branch-extention', function (done) {
trie3.put(new Buffer([11, 11, 11]), 'first', function () {
//create the top branch
trie3.put(new Buffer([12, 22, 22]), 'create the first branch', function () {
//crete the middle branch
trie3.put(new Buffer([12, 33, 33]), 'create the middle branch', function () {
trie3.put(new Buffer([12, 33, 44]), 'create the last branch', function () {
//delete the middle branch
trie3.del(new Buffer([11, 11, 11]), function () {
trie3.get(new Buffer([11, 11, 11]), function (err, val) {
assert.equal(null, val);
done();
});
});
});
});
});
});
});
it('should delete from a extention->branch-branch', function (done) {
trie3.put(new Buffer([11, 11, 11]), 'first', function () {
//create the top branch
trie3.put(new Buffer([12, 22, 22]), 'create the first branch', function () {
//crete the middle branch
trie3.put(new Buffer([12, 33, 33]), 'create the middle branch', function () {
trie3.put(new Buffer([12, 34, 44]), 'create the last branch', function () {
//delete the middle branch
trie3.del(new Buffer([11, 11, 11]), function () {
trie3.get(new Buffer([11, 11, 11]), function (err, val) {
assert.equal(null, val);
done();
});
});
});
});
it('should delete from a extention->branch-branch', function (done) {
trie3.put(new Buffer([11, 11, 11]), 'first', function () {
//create the top branch
trie3.put(new Buffer([12, 22, 22]), 'create the first branch', function () {
//crete the middle branch
trie3.put(new Buffer([12, 33, 33]), 'create the middle branch', function () {
trie3.put(new Buffer([12, 34, 44]), 'create the last branch', function () {
//delete the middle branch
trie3.del(new Buffer([11, 11, 11]), function () {
trie3.get(new Buffer([11, 11, 11]), function (err, val) {
assert.equal(null, val);
done();
});
});
});
});
});
});
});
});

@@ -287,50 +275,68 @@

var trie,
preRoot,
postRoot;
var trie,
preRoot,
postRoot;
before(function (done) {
trie = new Trie();
trie.put('do', 'verb', function () {
trie.put('doge', 'coin', function () {
preRoot = trie.root.toString('hex');
done();
});
});
before(function (done) {
trie = new Trie();
trie.put('do', 'verb', function () {
trie.put('doge', 'coin', function () {
preRoot = trie.root.toString('hex');
done();
});
});
});
it('should create a checkpoint', function (done) {
trie.checkpoint();
it('should create a checkpoint', function (done) {
trie.checkpoint();
done();
});
it('should save to the cache', function (done) {
trie.put('test', 'something', function () {
trie.put('love', 'emotion', function () {
postRoot = trie.root.toString('hex');
done();
});
});
});
it('should save to the cache', function (done) {
trie.put('test', 'something', function () {
trie.put('love', 'emotion', function () {
postRoot = trie.root.toString('hex');
done();
});
it('should revert to the orginal root', function (done) {
assert(trie.isCheckpoint === true);
trie.revert(function(){
assert(trie.root.toString('hex') === preRoot);
assert(trie.isCheckpoint === false);
done();
});
});
it('should commit a checkpoint', function (done) {
trie.checkpoint();
trie.put('test', 'something', function () {
trie.put('love', 'emotion', function () {
trie.commit(function () {
assert(trie.isCheckpoint === false);
assert(trie.root.toString('hex') === postRoot);
done();
});
});
});
});
it('should revert to the orginal root', function (done) {
assert(trie.isCheckpoint === true);
it('should commit a nested checkpoint', function (done) {
trie.checkpoint();
var root;
trie.put('test', 'something else', function () {
root = trie.root;
trie.checkpoint();
trie.put('the feels', 'emotion', function () {
trie.revert();
assert(trie.root.toString('hex') === preRoot);
assert(trie.isCheckpoint === false);
done();
});
it('should commit a checkpoint', function (done) {
trie.checkpoint();
trie.put('test', 'something', function () {
trie.put('love', 'emotion', function () {
trie.commit(function () {
assert(trie.isCheckpoint === false);
assert(trie.root.toString('hex') === postRoot);
done();
});
});
trie.commit(function () {
assert(trie.isCheckpoint === false);
assert(trie.root.toString('hex') === root.toString('hex'));
done();
});
});
});
});
});

@@ -340,70 +346,115 @@

var trie4 = new Trie(),
g = new Buffer('8a40bfaa73256b60764c1bf40675a99083efb075', 'hex'),
j = new Buffer('e6716f9544a56c530d868e4bfbacb172315bdead', 'hex'),
v = new Buffer('1e12515ce3e0f817a4ddef9ca55788a1d66bd2df', 'hex'),
a = new Buffer('1a26338f0d905e295fccb71fa9ea849ffa12aaf4', 'hex'),
hash = new Sha3.SHA3Hash(256),
stateRoot = new Buffer(32);
var trie4 = new Trie(),
g = new Buffer('8a40bfaa73256b60764c1bf40675a99083efb075', 'hex'),
j = new Buffer('e6716f9544a56c530d868e4bfbacb172315bdead', 'hex'),
v = new Buffer('1e12515ce3e0f817a4ddef9ca55788a1d66bd2df', 'hex'),
a = new Buffer('1a26338f0d905e295fccb71fa9ea849ffa12aaf4', 'hex'),
hash = new Sha3.SHA3Hash(256),
stateRoot = new Buffer(32);
stateRoot.fill(0);
var startAmount = new Buffer(26);
startAmount.fill(0);
startAmount[0] = 1;
var account = [startAmount, 0, stateRoot, new Buffer(hash.digest('hex'), 'hex')];
var rlpAccount = rlp.encode(account);
cppRlp = 'f85e9a010000000000000000000000000000000000000000000000000080a00000000000000000000000000000000000000000000000000000000000000000a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470';
stateRoot.fill(0);
var startAmount = new Buffer(26);
startAmount.fill(0);
startAmount[0] = 1;
var account = [startAmount, 0, stateRoot, new Buffer(hash.digest('hex'), 'hex')];
var rlpAccount = rlp.encode(account);
cppRlp = 'f85e9a010000000000000000000000000000000000000000000000000080a00000000000000000000000000000000000000000000000000000000000000000a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470';
var genesisStateRoot = '2f4399b08efe68945c1cf90ffe85bbe3ce978959da753f9e649f034015b8817d';
assert.equal(cppRlp, rlpAccount.toString('hex'));
//console.log(rlpAccount.toString('hex'));
var genesisStateRoot = '2f4399b08efe68945c1cf90ffe85bbe3ce978959da753f9e649f034015b8817d';
assert.equal(cppRlp, rlpAccount.toString('hex'));
//console.log(rlpAccount.toString('hex'));
it('shall match the root given unto us by the Master Coder Gav', function (done) {
trie4.put(g, rlpAccount, function () {
trie4.put(j, rlpAccount, function () {
trie4.put(v, rlpAccount, function () {
trie4.put(a, rlpAccount, function () {
assert.equal(trie4.root.toString('hex'), genesisStateRoot);
done();
});
});
});
it('shall match the root given unto us by the Master Coder Gav', function (done) {
trie4.put(g, rlpAccount, function () {
trie4.put(j, rlpAccount, function () {
trie4.put(v, rlpAccount, function () {
trie4.put(a, rlpAccount, function () {
assert.equal(trie4.root.toString('hex'), genesisStateRoot);
done();
});
});
});
});
});
});
describe('offical tests', function () {
var jsonTests;
var testNames;
var trie;
var testNames,
trie;
before(function () {
var data = fs.readFileSync('./test/jsonTests/trietest.json');
jsonTests = JSON.parse(data),
testNames = Object.keys(jsonTests),
db7 = levelup('./test/testdb9'),
before(function () {
testNames = Object.keys(jsonTests.trietest);
trie = new Trie();
});
it('pass all tests', function (done) {
async.eachSeries(testNames, function (i, done) {
console.log(i);
var inputs = jsonTests.trietest[i].in;
var expect = jsonTests.trietest[i].root;
async.eachSeries(inputs, function (input, done) {
for(i = 0; i < 2; i++){
if(input[i] && input[i].slice(0,2) === '0x'){
input[i] = new Buffer(input[i].slice(2), 'hex');
}
}
trie.put(input[0], input[1], function () {
done();
});
}, function () {
assert.equal('0x' + trie.root.toString('hex'), expect);
trie = new Trie();
done();
});
}, function () {
done();
});
});
});
it('pass all tests', function (done) {
async.eachSeries(testNames, function (i, done) {
console.log(i);
var inputs = jsonTests[i].inputs;
var expect = jsonTests[i].expectation;
describe('offical tests any order', function () {
var testNames,
trie;
async.eachSeries(inputs, function (input, done) {
trie.put(input[0], input[1], function () {
done();
});
}, function () {
before(function () {
testNames = Object.keys(jsonTests.trieanyorder);
trie = new Trie();
});
assert.equal(trie.root.toString('hex'), expect);
trie = new Trie();
done();
});
it('pass all tests', function (done) {
async.eachSeries(testNames, function (i, done) {
console.log(i);
var test = jsonTests.trieanyorder[i];
var keys = Object.keys(test.in);
}, function () {
done();
async.eachSeries(keys, function (key, done) {
var val = test.in[key];
if(key.slice(0,2) === '0x'){
key = new Buffer(key.slice(2), 'hex');
}
if(val && val.slice(0,2) === '0x'){
val = new Buffer(val.slice(2), 'hex');
}
trie.put(key, val, function () {
done();
});
}, function () {
assert.equal('0x' + trie.root.toString('hex'), test.root);
trie = new Trie();
done();
});
}, function () {
done();
});
});
});

255

trieNode.js
var rlp = require('rlp'),
Sha3 = require('sha3');
Sha3 = require('sha3');

@@ -7,39 +7,39 @@ var internals = {};

exports = module.exports = internals.TrieNode = function (type, key, value) {
if (Array.isArray(type)) {
//parse raw node
this.parseNode(type);
if (Array.isArray(type)) {
//parse raw node
this.parseNode(type);
} else {
this.type = type;
if (type === 'branch') {
var values = key;
this.raw = Array.apply(null, Array(17));
if (values) {
values.forEach(function (keyVal) {
this.set.apply(this, keyVal);
});
}
} else {
this.type = type;
if (type === 'branch') {
var values = key;
this.raw = Array.apply(null, Array(17));
if (values) {
values.forEach(function (keyVal) {
this.set.apply(this, keyVal);
});
}
} else {
this.raw = Array(2);
this.setValue(value);
this.setKey(key);
}
this.raw = Array(2);
this.setValue(value);
this.setKey(key);
}
}
};
Object.defineProperty(internals.TrieNode.prototype, 'value', {
get: function () {
return this.getValue();
},
set: function (v) {
this.setValue(v);
}
get: function () {
return this.getValue();
},
set: function (v) {
this.setValue(v);
}
});
Object.defineProperty(internals.TrieNode.prototype, 'key', {
get: function () {
return this.getKey();
},
set: function (k) {
this.setKey(k);
}
get: function () {
return this.getKey();
},
set: function (k) {
this.setKey(k);
}
});

@@ -49,4 +49,4 @@

internals.TrieNode.prototype.parseNode = function (rawNode) {
this.raw = rawNode;
this.type = internals.getNodeType(rawNode);
this.raw = rawNode;
this.type = internals.getNodeType(rawNode);
};

@@ -56,37 +56,37 @@

internals.TrieNode.prototype.setValue = function (key, value) {
if (this.type !== 'branch') {
this.raw[1] = key;
} else {
if (arguments.length === 1) {
value = key;
key = 16;
}
this.raw[key] = value;
if (this.type !== 'branch') {
this.raw[1] = key;
} else {
if (arguments.length === 1) {
value = key;
key = 16;
}
this.raw[key] = value;
}
};
internals.TrieNode.prototype.getValue = function (key) {
if (this.type === 'branch') {
if (arguments.length === 0) {
key = 16;
}
var val = this.raw[key];
if (val !== null && val !== undefined && !(val.length === 1 && val[0] === 0)) {
return val;
}
} else {
return this.raw[1];
if (this.type === 'branch') {
if (arguments.length === 0) {
key = 16;
}
var val = this.raw[key];
if (val !== null && val !== undefined && !(val.length === 0)) {
return val;
}
} else {
return this.raw[1];
}
};
internals.TrieNode.prototype.setKey = function (key) {
if (this.type !== 'branch') {
if (Buffer.isBuffer(key) || typeof key === 'string') {
key = internals.stringToNibbles(key);
} else {
key = key.slice(0); //copy the key
}
key = internals.addHexPrefix(key, this.type === 'leaf');
this.raw[0] = internals.nibblesToBuffer(key);
if (this.type !== 'branch') {
if (Buffer.isBuffer(key) || typeof key === 'string') {
key = internals.stringToNibbles(key);
} else {
key = key.slice(0); //copy the key
}
key = internals.addHexPrefix(key, this.type === 'leaf');
this.raw[0] = internals.nibblesToBuffer(key);
}
};

@@ -96,36 +96,37 @@

internals.TrieNode.prototype.getKey = function () {
if (this.type != 'branch') {
var key = this.raw[0];
key = internals.removeHexPrefix(internals.stringToNibbles(key));
return (key);
}
if (this.type != 'branch') {
var key = this.raw[0];
key = internals.removeHexPrefix(internals.stringToNibbles(key));
return (key);
}
};
internals.TrieNode.prototype.serialize = function () {
return rlp.encode(this.raw);
return rlp.encode(this.raw);
};
internals.TrieNode.prototype.hash = function () {
var hash = new Sha3.SHA3Hash(256);
hash.update(this.serialize());
//no way to get a buffer directly from the hash :(
var key = hash.digest('hex');
return new Buffer(key, 'hex');
var hash = new Sha3.SHA3Hash(256);
hash.update(this.serialize());
//no way to get a buffer directly from the hash :(
var key = hash.digest('hex');
return new Buffer(key, 'hex');
};
internals.TrieNode.prototype.toString = function () {
var out = this.type;
out += ': [';
this.raw.forEach(function(el){
if(Buffer.isBuffer(el)){
out += el.toString('hex') + ', ';
}else if(el){
out += 'object, ';
}else{
out += 'empty, ';
}
});
out = out.slice(0, -2);
out += ']';
return out;
var out = this.type;
out += ': [';
this.raw.forEach(function (el) {
if (Buffer.isBuffer(el)) {
out += el.toString('hex') + ', ';
} else if (el) {
out += 'object, ';
} else {
out += 'empty, ';
}
});
out = out.slice(0, -2);
out += ']';
return out;
};

@@ -139,24 +140,24 @@

internals.addHexPrefix = internals.TrieNode.addHexPrefix = function (key, terminator) {
//odd
if (key.length % 2) {
key.unshift(1);
//even
} else {
key.unshift(0);
key.unshift(0);
}
//odd
if (key.length % 2) {
key.unshift(1);
//even
} else {
key.unshift(0);
key.unshift(0);
}
if (terminator) {
key[0] += 2;
}
return key;
if (terminator) {
key[0] += 2;
}
return key;
};
internals.removeHexPrefix = internals.TrieNode.removeHexPrefix = function (val) {
if (val[0] % 2) {
val = val.slice(1);
} else {
val = val.slice(2);
}
return val;
if (val[0] % 2) {
val = val.slice(1);
} else {
val = val.slice(2);
}
return val;
};

@@ -170,3 +171,3 @@

internals.isTerminator = internals.TrieNode.isTerminator = function (key) {
return key[0] > 1;
return key[0] > 1;
};

@@ -180,12 +181,12 @@

internals.stringToNibbles = internals.TrieNode.stringToNibbles = function (key) {
var bkey = new Buffer(key);
var nibbles = [];
var bkey = new Buffer(key);
var nibbles = [];
for (var i = 0; i < bkey.length; i++) {
var q = i * 2;
nibbles[q] = bkey[i] >> 4;
++q;
nibbles[q] = bkey[i] % 16;
}
return nibbles;
for (var i = 0; i < bkey.length; i++) {
var q = i * 2;
nibbles[q] = bkey[i] >> 4;
++q;
nibbles[q] = bkey[i] % 16;
}
return nibbles;
};

@@ -199,8 +200,8 @@

internals.nibblesToBuffer = internals.TrieNode.nibblesToBuffer = function (arr) {
var buf = new Buffer(arr.length / 2);
for (var i = 0; i < buf.length; i++) {
var q = i * 2;
buf[i] = (arr[q] << 4) + arr[++q];
}
return buf;
var buf = new Buffer(arr.length / 2);
for (var i = 0; i < buf.length; i++) {
var q = i * 2;
buf[i] = (arr[q] << 4) + arr[++q];
}
return buf;
};

@@ -217,13 +218,13 @@

internals.getNodeType = internals.TrieNode.getNodeType = function (node) {
if (Buffer.isBuffer(node) || typeof node === 'string' || node instanceof String) {
return 'unkown';
} else if (node.length === 17) {
return 'branch';
} else if (node.length === 2) {
var key = internals.stringToNibbles(node[0]);
if (internals.isTerminator(key)) {
return 'leaf';
}
return 'extention';
if (Buffer.isBuffer(node) || typeof node === 'string' || node instanceof String) {
return 'unkown';
} else if (node.length === 17) {
return 'branch';
} else if (node.length === 2) {
var key = internals.stringToNibbles(node[0]);
if (internals.isTerminator(key)) {
return 'leaf';
}
return 'extention';
}
};
test/jsonTests/blockgenesistest.json
test/jsonTests/genesishashestest.json
test/jsonTests/hexencodetest.json
test/jsonTests/keyaddrtest.json
test/jsonTests/README.md
test/jsonTests/rlptest.json
test/jsonTests/TODO
test/jsonTests/trietest.json
test/jsonTests/txtest.json
test/jsonTests/vmtests.json
test/testdb2/000067.log
test/testdb2/CURRENT
test/testdb2/LOCK
test/testdb2/LOG
test/testdb2/LOG.old
test/testdb2/MANIFEST-000066
test/testdb6.1/000081.ldb
test/testdb6.1/000083.ldb
test/testdb6.1/000086.ldb
test/testdb6.1/000089.ldb
test/testdb6.1/000090.log
test/testdb6.1/CURRENT
test/testdb6.1/LOCK
test/testdb6.1/LOG
test/testdb6.1/LOG.old
test/testdb6.1/MANIFEST-000088
test/testdb6/000067.log
test/testdb6/CURRENT
test/testdb6/LOCK
test/testdb6/LOG
test/testdb6/LOG.old
test/testdb6/MANIFEST-000066
test/testdb9/000059.log
test/testdb9/CURRENT
test/testdb9/LOCK
test/testdb9/LOG
test/testdb9/LOG.old
test/testdb9/MANIFEST-000058
testSream.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc