@chainsafe/persistent-merkle-tree - npm Package Compare versions

Comparing version 0.3.6 to 0.3.7

CHANGELOG.md

 # Changelog
 
-## [v0.3.6](https://github.com/ChainSafe/persistent-merkle-tree/tree/v0.3.6) (2021-08-24)
+## [v0.3.7](https://github.com/ChainSafe/persistent-merkle-tree/tree/v0.3.7) (2021-08-26)
 
-[Full Changelog](https://github.com/ChainSafe/persistent-merkle-tree/compare/v0.3.5...v0.3.6)
+[Full Changelog](https://github.com/ChainSafe/persistent-merkle-tree/compare/v0.3.6...v0.3.7)
 
 
 

lib/tree.d.ts

@@ -6,2 +6,3 @@ import { Gindex, GindexBitstring } from "./gindex";
 export declare type Hook = (v: Tree) => void;
+export declare type HashObjectFn = (hashObject: HashObject) => HashObject;
 export declare class Tree {
@@ -21,3 +22,9 @@ private _node;
     setHashObject(index: Gindex | GindexBitstring, hashObject: HashObject, expand?: boolean): void;
-    getSubtree(index: Gindex): Tree;
+    /**
+     * Traverse from root node to node, get hash object, then apply the function to get new node
+     * and set the new node. This is a convenient method to avoid traversing the tree 2 times to
+     * get and set.
+     */
+    setHashObjectFn(gindex: Gindex | GindexBitstring, hashObjectFn: HashObjectFn, expand?: boolean): void;
+    getSubtree(index: Gindex | GindexBitstring): Tree;
     setSubtree(index: Gindex | GindexBitstring, v: Tree, expand?: boolean): void;
@@ -41,2 +48,12 @@ clone(): Tree;
     getProof(input: ProofInput): Proof;
+    /**
+     * Traverse the tree from root node, ignore the last bit to get all parent nodes
+     * of the specified bitstring.
+     */
+    private getParentNodes;
+    /**
+     * Build a new tree structure from bitstring, parentNodes and a new node.
+     * Note: keep the same Tree, just mutate the root node.
+     */
+    private rebindNodeToRoot;
 }

lib/tree.js

@@ -72,3 +72,2 @@ "use strict";
     setNode(gindex, n, expand = false) {
-        let node = this.rootNode;
         // Pre-compute entire bitstring instead of using an iterator (25% faster)
@@ -85,38 +84,4 @@ let bitstring;
         }
-        // Keep a list of all parent nodes of node at gindex `index`. Then walk the list
-        // backwards to rebind them "recursively" with the new nodes without using functions
-        const parentNodes = [this.rootNode];
-        // Ignore the first bit, left right directions are at bits [1,..]
-        // Ignore the last bit, no need to push the target node to the parentNodes array
-        for (let i = 1; i < bitstring.length - 1; i++) {
-            if (node.isLeaf()) {
-                if (!expand) {
-                    throw new Error(ERR_INVALID_TREE);
-                }
-                else {
-                    node = zeroNode_1.zeroNode(bitstring.length - i);
-                }
-            }
-            // Compare to string directly to prevent unnecessary type conversions
-            if (bitstring[i] === "1") {
-                node = node.right;
-            }
-            else {
-                node = node.left;
-            }
-            parentNodes.push(node);
-        }
-        node = n;
-        // Ignore the first bit, left right directions are at bits [1,..]
-        // Iterate the list backwards including the last bit, but offset the parentNodes array
-        // by one since the first bit in bitstring was ignored in the previous loop
-        for (let i = bitstring.length - 1; i >= 1; i--) {
-            if (bitstring[i] === "1") {
-                node = parentNodes[i - 1].rebindRight(node);
-            }
-            else {
-                node = parentNodes[i - 1].rebindLeft(node);
-            }
-        }
-        this.rootNode = node;
+        const parentNodes = this.getParentNodes(bitstring, expand);
+        this.rebindNodeToRoot(bitstring, parentNodes, n);
     }
@@ -135,2 +100,26 @@ getRoot(index) {
     }
+    /**
+     * Traverse from root node to node, get hash object, then apply the function to get new node
+     * and set the new node. This is a convenient method to avoid traversing the tree 2 times to
+     * get and set.
+     */
+    setHashObjectFn(gindex, hashObjectFn, expand = false) {
+        // Pre-compute entire bitstring instead of using an iterator (25% faster)
+        let bitstring;
+        if (typeof gindex === "string") {
+            bitstring = gindex;
+        }
+        else {
+            if (gindex < 1) {
+                throw new Error("Invalid gindex < 1");
+            }
+            bitstring = gindex.toString(2);
+        }
+        const parentNodes = this.getParentNodes(bitstring, expand);
+        const lastParentNode = parentNodes[parentNodes.length - 1];
+        const lastBit = bitstring[bitstring.length - 1];
+        const oldNode = lastBit === "1" ? lastParentNode.right : lastParentNode.left;
+        const newNode = new node_1.LeafNode(hashObjectFn(oldNode));
+        this.rebindNodeToRoot(bitstring, parentNodes, newNode);
+    }
     getSubtree(index) {
@@ -306,3 +295,53 @@ return new Tree(this.getNode(index), (v) => this.setNode(index, v.rootNode));
     }
+    /**
+     * Traverse the tree from root node, ignore the last bit to get all parent nodes
+     * of the specified bitstring.
+     */
+    getParentNodes(bitstring, expand = false) {
+        let node = this.rootNode;
+        // Keep a list of all parent nodes of node at gindex `index`. Then walk the list
+        // backwards to rebind them "recursively" with the new nodes without using functions
+        const parentNodes = [this.rootNode];
+        // Ignore the first bit, left right directions are at bits [1,..]
+        // Ignore the last bit, no need to push the target node to the parentNodes array
+        for (let i = 1; i < bitstring.length - 1; i++) {
+            if (node.isLeaf()) {
+                if (!expand) {
+                    throw new Error(ERR_INVALID_TREE);
+                }
+                else {
+                    node = zeroNode_1.zeroNode(bitstring.length - i);
+                }
+            }
+            // Compare to string directly to prevent unnecessary type conversions
+            if (bitstring[i] === "1") {
+                node = node.right;
+            }
+            else {
+                node = node.left;
+            }
+            parentNodes.push(node);
+        }
+        return parentNodes;
+    }
+    /**
+     * Build a new tree structure from bitstring, parentNodes and a new node.
+     * Note: keep the same Tree, just mutate the root node.
+     */
+    rebindNodeToRoot(bitstring, parentNodes, newNode) {
+        let node = newNode;
+        // Ignore the first bit, left right directions are at bits [1,..]
+        // Iterate the list backwards including the last bit, but offset the parentNodes array
+        // by one since the first bit in bitstring was ignored in the previous loop
+        for (let i = bitstring.length - 1; i >= 1; i--) {
+            if (bitstring[i] === "1") {
+                node = parentNodes[i - 1].rebindRight(node);
+            }
+            else {
+                node = parentNodes[i - 1].rebindLeft(node);
+            }
+        }
+        this.rootNode = node;
+    }
 }
 exports.Tree = Tree;

package.json

 {
   "name": "@chainsafe/persistent-merkle-tree",
-  "version": "0.3.6",
+  "version": "0.3.7",
   "description": "Merkle tree implemented as a persistent datastructure",
@@ -5,0 +5,0 @@ "main": "lib/index.js",

No alert changes

Improved metrics

Total package byte prevSize

68052

increased by3.67%

Lines of code

1377

increased by4.24%

No dependency changes