dfinity-radix-tree - npm Package Compare versions

Comparing version 0.0.6 to 0.0.7

index.js

 const Graph = require('ipld-graph-builder')
-const cbor = require('borc')
 const Uint1Array = require('uint1array')
@@ -26,46 +25,28 @@ const TextEncoder = require('text-encoding').TextEncoder
     this._setting = Promise.resolve()
+    this.appendKeyToRoot = opts.appendKeyToRoot
   }
 
-  async _mutationLockWait () {
-    let setting
-    while (this._setting !== setting) {
-      setting = this._setting
-      await setting
-    }
-  }
-
-  _mutationLock (func) {
-    const setting = this._setting
-    this._setting = new Promise((resolve, reject) => {
-      return setting.then(() => {
-        return func().then(resolve).catch(reject)
-      })
-    })
-    return this._setting
-  }
-
   /**
-   * returns the state of an empty tree
+   * creates a new instance of RadixTree that is the subTree of the given key
+   * @param {*} key
+   * @return {Promise} resolve to the new instance of RadixTree
    */
-  static get emptyTreeState () {
-    return [null, null, null]
+  async getSubTree (key, decode) {
+    const {root} = await this.get(key, decode)
+    return new RadixTree({dag: this.dag, root: root, appendKeyToRoot: true})
   }
 
   /**
-   * returns an Uint1Array constructir which is used to repersent keys
-   * @returns {object}
+   * gets a value given a key. The promise resolves with an object containing
+   * `node` the node in the merkle tree and `value` the value of the that the
+   * node contains
+   * @param {*} key
+   * @return {Promise}
    */
-  static get ArrayConstructor () {
-    return Uint1Array
+  async get (key, decode) {
+    key = this.formatKey(key)
+    await this.done()
+    return this._get(key)
   }
 
-  /**
-   * returns a merkle link for some given data
-   * @param {Buffer} data - the data which you would like to hash
-   * @returns {Buffer}
-   */
-  static getMerkleLink (data) {
-    return DataStore.getMerkleLink(data)
-  }
-
   async _get (key) {
@@ -87,6 +68,6 @@ let index = 0
           return {
-            index: index,
-            root: root,
-            extension: extension,
-            extensionIndex: extensionIndex
+            index,
+            root,
+            extension,
+            extensionIndex
           }
@@ -121,6 +102,6 @@ }
     return {
-      value: value,
-      root: root,
-      parent: parent,
-      index: index
+      value,
+      root,
+      parent,
+      index
     }
@@ -130,20 +111,2 @@ }
   /**
-   * gets a value given a key. The promise resolves with an object containing
-   * `node` the node in the merkle tree and `value` the value of the that the
-   * node contains
-   * @param {*} key
-   * @return {Promise}
-   */
-  async get (key, decode) {
-    await this._mutationLockWait()
-    key = RadixTree.formatKey(key)
-    let {root, value} = await this._get(key)
-    if (decode && Buffer.isBuffer(value)) {
-      value = cbor.decode(value)
-      treeNode.setValue(root, value)
-    }
-    return {node: root, value}
-  }
-
-  /**
    * stores a value at a given key
@@ -154,2 +117,3 @@ * @param {*} key
   set (key, value) {
+    key = this.formatKey(key)
     return this._mutationLock(this._set.bind(this, key, value))
@@ -159,4 +123,2 @@ }
   async _set (key, value) {
-    key = RadixTree.formatKey(key)
-
     if (treeNode.isEmpty(this.root)) {
@@ -205,2 +167,3 @@ this.root['/'] = createNode(key, [null, null], value)['/']
   delete (key) {
+    key = this.formatKey(key)
     return this._mutationLock(this._delete.bind(this, key))
@@ -210,3 +173,2 @@ }
   async _delete (key) {
-    key = RadixTree.formatKey(key)
     const results = await this._get(key)
@@ -265,2 +227,24 @@ if (results.value !== undefined) {
   /**
+   * returns a promise that resolve when the tree is done with all of its writes
+   * @returns {Promise}
+   */
+  async done () {
+    let setting
+    while (this._setting !== setting) {
+      setting = this._setting
+      await setting
+    }
+  }
+
+  _mutationLock (func) {
+    const setting = this._setting
+    this._setting = new Promise((resolve, reject) => {
+      return setting.then(() => {
+        return func().then(resolve).catch(reject)
+      })
+    })
+    return this._setting
+  }
+
+  /**
    * creates a merkle root for the current tree and stores the data perstantly
@@ -270,6 +254,15 @@ * @returns {Promise}
   async flush () {
-    await this._mutationLockWait()
+    await this.done()
     return this.graph.flush(this.root)
   }
 
+  formatKey (key) {
+    key = RadixTree.formatKey(key)
+    if (this.appendKeyToRoot) {
+      key = treeNode.getExtension(this.root).toJSON().concat(key.toJSON())
+      key = new RadixTree.ArrayConstructor(key)
+    }
+    return key
+  }
+
   static formatKey (key) {
@@ -290,2 +283,26 @@ if (typeof key === 'string') {
   }
+
+  /**
+   * returns the state of an empty tree
+   */
+  static get emptyTreeState () {
+    return [null, null, null]
+  }
+
+  /**
+   * returns an Uint1Array constructir which is used to repersent keys
+   * @returns {object}
+   */
+  static get ArrayConstructor () {
+    return Uint1Array
+  }
+
+  /**
+   * returns a merkle link for some given data
+   * @param {Buffer} data - the data which you would like to hash
+   * @returns {Buffer}
+   */
+  static getMerkleLink (data) {
+    return DataStore.getMerkleLink(data)
+  }
 }
@@ -316,6 +333,6 @@
   return {
-    extensionIndex: extensionIndex,
-    extensionLen: extensionLen,
-    extension: extension
+    extensionIndex,
+    extensionLen,
+    extension
   }
 }

package.json

 {
   "name": "dfinity-radix-tree",
-  "version": "0.0.6",
+  "version": "0.0.7",
   "description": "This implements a binary merkle radix tree",
@@ -30,3 +30,2 @@ "main": "index.js",
   "dependencies": {
-    "borc": "^2.0.2",
     "buffer-pipe": "0.0.0",
@@ -33,0 +32,0 @@ "ipld-graph-builder": "^1.3.5",

tests/index.js

@@ -82,2 +82,33 @@ const tape = require('tape')
 
+tape('sub trees', async t => {
+  const tree = new RadixTree({
+    db: db
+  })
+
+  let key0 = new RadixTree.ArrayConstructor([1, 1, 1, 1, 1])
+  let key1 = new RadixTree.ArrayConstructor([0, 1, 1, 1, 1])
+  let key2 = new RadixTree.ArrayConstructor([1, 1, 1, 0, 1])
+  let key3 = new RadixTree.ArrayConstructor([0, 0, 1, 0, 1])
+
+  tree.set(key0, Buffer.from('cat'))
+  tree.set(key1, Buffer.from('cat2'))
+  tree.set(key2, Buffer.from('dog'))
+  tree.set(key3, Buffer.from('cat3'))
+
+  await tree.done()
+  let key = new RadixTree.ArrayConstructor([1, 1, 1])
+  let subKey1 = new RadixTree.ArrayConstructor([1, 1])
+  let subKey2 = new RadixTree.ArrayConstructor([0, 1])
+
+  const subTree = await tree.getSubTree(key)
+
+  let val = await subTree.get(subKey1)
+  t.equals(val.value.toString(), 'cat')
+
+  val = await subTree.get(subKey2)
+  t.equals(val.value.toString(), 'dog')
+
+  t.end()
+})
+
 tape('delete', async t => {
@@ -122,18 +153,2 @@ const tree = new RadixTree({
 
-tape('encoding / decoding', async t => {
-  // t.plan(3)
-  const tree = new RadixTree({
-    db: db
-  })
-
-  await tree.set('test', {
-    'something': 1
-  })
-  await tree.flush()
-
-  let r = await tree.get('test', true)
-  t.equals(r.value.something, 1, 'should correctly decode value')
-  t.end()
-})
-
 tape('errors', async t => {
@@ -140,0 +155,0 @@ const tree = new RadixTree({

treeNode.js

@@ -1,4 +0,3 @@
-const borc = require('borc')
 const leb128 = require('leb128').unsigned
-const LebStream = require('buffer-pipe')
+const BufferPipe = require('buffer-pipe')
 const Uint1Array = require('uint1array')
@@ -40,3 +39,3 @@ const HASH_LEN = 20
   } else {
-    return []
+    return toTypedArray([])
   }
@@ -95,5 +94,2 @@ }
   if (val !== undefined) {
-    if (!val.buffer) {
-      val = borc.encode(val)
-    }
     encoded.push(val)
@@ -115,7 +111,7 @@ prefix += MASK.VALUE
   const prefix = val[0]
-  const lebStream = new LebStream(val.slice(1))
+  const pipe = new BufferPipe(val.slice(1))
 
   if (prefix & MASK.EXTENSION) {
-    const len = Number(leb128.read(lebStream))
-    const ext = lebStream.read(Math.ceil(len / 8))
+    const len = Number(leb128.read(pipe))
+    const ext = pipe.read(Math.ceil(len / 8))
     node[EXTENSION] = [len, ext]
@@ -126,3 +122,3 @@ }
     node[LBRANCH] = {
-      '/': lebStream.read(HASH_LEN)
+      '/': pipe.read(HASH_LEN)
     }
@@ -133,3 +129,3 @@ }
     node[RBRANCH] = {
-      '/': lebStream.read(HASH_LEN)
+      '/': pipe.read(HASH_LEN)
     }
@@ -139,5 +135,5 @@ }
   if (prefix & MASK.VALUE) {
-    node[VALUE] = lebStream.buffer
+    node[VALUE] = pipe.buffer
   }
   return node
 }

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Native code

Supply chain risk

Contains native code (e.g., compiled binaries or shared libraries). Including native code can obscure malicious behavior.

Found 3 instances in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Native code

Supply chain risk

Contains native code (e.g., compiled binaries or shared libraries). Including native code can obscure malicious behavior.

Found 5 instances in 1 package

Improved metrics

Dependency count

7

decreased by-12.5%

Lines of code

1596

increased by1.4%

Number of medium supply chain risk alerts

3

decreased by-40%

Worsened metrics

Total package byte prevSize

377285

decreased by-7.72%

Number of package files

47

decreased by-4.08%

Dependency changes

• - Removedborc@^2.0.2

• - Removedbignumber.js@9.1.2(transitive)

• - Removedborc@2.1.2(transitive)

• - Removedcommander@2.20.3(transitive)

• - Removeddelimit-stream@0.1.0(transitive)

• - Removedinherits@2.0.4(transitive)

• - Removediso-url@0.4.7(transitive)

• - Removedjson-text-sequence@0.1.1(transitive)

• - Removedreadable-stream@3.6.2(transitive)

• - Removedstring_decoder@1.3.0(transitive)

• - Removedutil-deprecate@1.0.2(transitive)