Socket
Socket
Sign inDemoInstall

k-bucket

Package Overview
Dependencies
Maintainers
1
Versions
34
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

k-bucket - npm Package Compare versions

Comparing version 3.0.2 to 3.0.3

benchmarks/add.js
test/determineNode.js

311

index.js

@@ -38,2 +38,10 @@ /*

function defaultArbiter (incumbent, candidate) {
return incumbent.vectorClock > candidate.vectorClock ? incumbent : candidate
}
function createNode () {
return { contacts: [], dontSplit: false, left: null, right: null }
}
/*

@@ -55,5 +63,2 @@ * `options`:

not been contacted the longest.
* `root`: _Object_ _**CAUTION: reserved for internal use**_ Provides a
reference to the root of the tree data structure as the k-bucket splits
when new contacts are added.
*/

@@ -64,10 +69,2 @@ function KBucket (options) {

// use an arbiter from options or vectorClock arbiter by default
this.arbiter = options.arbiter || function arbiter (incumbent, candidate) {
return incumbent.vectorClock > candidate.vectorClock ? incumbent : candidate
}
// the bucket array has least-recently-contacted at the "front/left" side
// and the most-recently-contaced at the "back/right" side
this.bucket = []
this.localNodeId = options.localNodeId || randomBytes(20)

@@ -77,8 +74,6 @@ if (!Buffer.isBuffer(this.localNodeId)) throw new TypeError('localNodeId is not a Buffer')

this.numberOfNodesToPing = options.numberOfNodesToPing || 3
this.root = options.root || this
// use an arbiter from options or vectorClock arbiter by default
this.arbiter = options.arbiter || defaultArbiter
// V8 hints
this.dontSplit = null
this.low = null
this.high = null
this.root = createNode()
}

@@ -98,27 +93,24 @@

// contact: *required* the contact object to add
// bitIndex: the bitIndex to which bit to check in the Buffer for navigating
// the binary tree
KBucket.prototype._add = function (contact, bitIndex) {
// first check whether we are an inner node or a leaf (with bucket contents)
if (this.bucket === null) {
KBucket.prototype.add = function (contact) {
if (!Buffer.isBuffer(contact.id)) throw new TypeError('contact.id is not a Buffer')
var bitIndex = 0
var node = this.root
while (node.contacts === null) {
// this is not a leaf node but an inner node with 'low' and 'high'
// branches; we will check the appropriate bit of the identifier and
// delegate to the appropriate node for further processing
if (this._determineBucket(contact.id, bitIndex++) < 0) {
return this.low._add(contact, bitIndex)
} else {
return this.high._add(contact, bitIndex)
}
node = this._determineNode(node, contact.id, bitIndex++)
}
// check if the contact already exists
var index = this._indexOf(contact.id)
var index = this._indexOf(node, contact.id)
if (index >= 0) {
this._update(contact, index)
this._update(node, index, contact)
return this
}
if (this.bucket.length < this.numberOfNodesPerKBucket) {
this.bucket.push(contact)
this.root.emit('added', contact)
if (node.contacts.length < this.numberOfNodesPerKBucket) {
node.contacts.push(contact)
this.emit('added', contact)
return this

@@ -128,3 +120,3 @@ }

// the bucket is full
if (this.dontSplit) {
if (node.dontSplit) {
// we are not allowed to split the bucket

@@ -135,48 +127,51 @@ // we need to ping the first this.numberOfNodesToPing

// be added (this prevents DoS flodding with new invalid contacts)
this.root.emit('ping', this.bucket.slice(0, this.numberOfNodesToPing), contact)
this.emit('ping', node.contacts.slice(0, this.numberOfNodesToPing), contact)
return this
}
return this._splitAndAdd(contact, bitIndex)
this._split(node, bitIndex)
return this.add(contact)
}
// contact: *required* the contact object to add
KBucket.prototype.add = function (contact) {
if (!Buffer.isBuffer(contact.id)) throw new TypeError('contact.id is not a Buffer')
return this._add(contact, 0)
}
// id: Buffer *required* node id
// n: Integer *required* maximum number of closest contacts to return
// bitIndex: Integer (Default: 0)
// Return: Array of maximum of `n` closest contacts to the node id
KBucket.prototype._closest = function (id, n, bitIndex) {
if (this.bucket === null) {
var contacts
if (this._determineBucket(id, bitIndex++) < 0) {
contacts = this.low._closest(id, n, bitIndex)
if (contacts.length < n) contacts = contacts.concat(this.high._closest(id, n, bitIndex))
KBucket.prototype.closest = function (id, n) {
if (!Buffer.isBuffer(id)) throw new TypeError('id is not a Buffer')
var contacts = []
function sort (contacts) {
return contacts.slice().sort(function (a, b) {
return KBucket.distance(a.id, id) - KBucket.distance(b.id, id)
})
}
for (var nodes = [ this.root ], bitIndex = 0; nodes.length > 0 && contacts.length < n;) {
var node = nodes.pop()
if (node.contacts === null) {
var detNode = this._determineNode(node, id, bitIndex++)
nodes.push(node.left === detNode ? node.right : node.left)
nodes.push(detNode)
} else {
contacts = this.high._closest(id, n, bitIndex)
if (contacts.length < n) contacts = contacts.concat(this.low._closest(id, n, bitIndex))
contacts = contacts.concat(sort(node.contacts)).slice(0, n)
}
return contacts.slice(0, n)
}
return this.bucket
.map(function (storedContact) {
storedContact.distance = KBucket.distance(storedContact.id, id)
return storedContact
return contacts
/*
function sort (contacts) {
return contacts.slice().sort(function (a, b) {
return KBucket.distance(a, id) - KBucket.distance(b, id)
})
.sort(function (a, b) { return a.distance - b.distance })
.slice(0, n)
}
}
// id: Buffer *required* node id
// n: Integer *required* maximum number of closest contacts to return
// Return: Array of maximum of `n` closest contacts to the node id
KBucket.prototype.closest = function (id, n) {
if (!Buffer.isBuffer(id)) throw new TypeError('id is not a Buffer')
return this._closest(id, n, 0)
for (var nodes = [ this.root ]; nodes.length > 0 && contacts.length < n;) {
var node = nodes.pop()
if (node.contacts === null) nodes.push(node.right, node.left)
else contacts = contacts.concat(sort(node.contacts)).slice(0, n)
}
return contacts
*/
}

@@ -187,13 +182,19 @@

// return the length of the high and low branches combined.
KBucket.prototype.count = function count () {
if (this.bucket !== null) return this.bucket.length
return this.high.count() + this.low.count()
KBucket.prototype.count = function () {
// return this.toArray().length
var count = 0
for (var nodes = [ this.root ]; nodes.length > 0;) {
var node = nodes.pop()
if (node.contacts === null) nodes.push(node.right, node.left)
else count += node.contacts.length
}
return count
}
// Determines whether the id at the bitIndex is 0 or 1. If 0, returns -1, else 1
// Determines whether the id at the bitIndex is 0 or 1.
// Return left leaf if `id` at `bitIndex` is 0, right leaf otherwise
// node: internal object that has 2 leafs: left and right
// id: a Buffer to compare localNodeId with
// bitIndex: the bitIndex to which bit to check in the id Buffer
KBucket.prototype._determineBucket = function (id, bitIndex) {
bitIndex = bitIndex || 0
KBucket.prototype._determineNode = function (node, id, bitIndex) {
// **NOTE** remember that id is a Buffer and has granularity of

@@ -209,5 +210,5 @@ // bytes (8 bits), whereas the bitIndex is the _bit_ index (not byte)

// bucket
var bytesDescribedByBitIndex = parseInt(bitIndex / 8, 10)
var bytesDescribedByBitIndex = ~~(bitIndex / 8)
var bitIndexWithinByte = bitIndex % 8
if ((id.length <= bytesDescribedByBitIndex) && (bitIndexWithinByte !== 0)) return -1
if ((id.length <= bytesDescribedByBitIndex) && (bitIndexWithinByte !== 0)) return node.left

@@ -223,5 +224,5 @@ var byteUnderConsideration = id[bytesDescribedByBitIndex]

// Math.pow(2, (7 - 3)) -> Math.pow(2, 4) -> 16
if (byteUnderConsideration & Math.pow(2, (7 - bitIndexWithinByte))) return 1
if (byteUnderConsideration & Math.pow(2, (7 - bitIndexWithinByte))) return node.right
return -1
return node.left
}

@@ -234,34 +235,21 @@

// id: Buffer *required* The ID of the contact to fetch.
// bitIndex: the bitIndex to which bit to check in the Buffer for navigating
// the binary tree
KBucket.prototype._get = function (id, bitIndex) {
if (this.bucket === null) {
if (this._determineBucket(id, bitIndex++) < 0) {
return this.low._get(id, bitIndex)
} else {
return this.high._get(id, bitIndex)
}
KBucket.prototype.get = function (id) {
if (!Buffer.isBuffer(id)) throw new TypeError('id is not a Buffer')
var bitIndex = 0
var node = this.root
while (node.contacts === null) {
node = this._determineNode(node, id, bitIndex++)
}
var index = this._indexOf(id) // index of uses contact id for matching
if (index < 0) return null // contact not found
return this.bucket[index]
var index = this._indexOf(node, id) // index of uses contact id for matching
return index >= 0 ? node.contacts[index] : null
}
// Get a contact by its exact ID.
// If this is a leaf, loop through the bucket contents and return the correct
// contact if we have it or null if not. If this is an inner node, determine
// which branch of the tree to traverse and repeat.
// id: Buffer *required* The ID of the contact to fetch.
KBucket.prototype.get = function get (id) {
if (!Buffer.isBuffer(id)) throw new TypeError('id is not a Buffer')
return this._get(id, 0)
}
// node: internal object that has 2 leafs: left and right
// id: Buffer Contact node id.
// Returns the index of the contact with the given id if it exists
KBucket.prototype._indexOf = function indexOf (id) {
for (var i = 0; i < this.bucket.length; i++) {
if (bufferEquals(this.bucket[i].id, id)) return i
KBucket.prototype._indexOf = function (node, id) {
for (var i = 0; i < node.contacts.length; ++i) {
if (bufferEquals(node.contacts[i].id, id)) return i
}

@@ -272,22 +260,16 @@

// id: Buffer *required* The ID of the contact to remove.
// bitIndex: the bitIndex to which bit to check in the Buffer for navigating
// the binary tree
KBucket.prototype._remove = function (id, bitIndex) {
// first check whether we are an inner node or a leaf (with bucket contents)
if (this.bucket === null) {
// this is not a leaf node but an inner node with 'low' and 'high'
// branches; we will check the appropriate bit of the identifier and
// delegate to the appropriate node for further processing
if (this._determineBucket(id, bitIndex++) < 0) {
return this.low._remove(id, bitIndex)
} else {
return this.high._remove(id, bitIndex)
}
// id: Buffer *required* he ID of the contact to remove.
KBucket.prototype.remove = function (id) {
if (!Buffer.isBuffer(id)) throw new TypeError('id is not a Buffer')
var bitIndex = 0
var node = this.root
while (node.contacts === null) {
node = this._determineNode(node, id, bitIndex++)
}
var index = this._indexOf(id)
var index = this._indexOf(node, id)
if (index >= 0) {
var contact = this.bucket.splice(index, 1)[0]
this.root.emit('removed', contact)
var contact = node.contacts.splice(index, 1)[0]
this.emit('removed', contact)
}

@@ -298,56 +280,25 @@

// id: Buffer *required* he ID of the contact to remove.
KBucket.prototype.remove = function remove (id) {
if (!Buffer.isBuffer(id)) throw new TypeError('id is not a Buffer')
return this._remove(id, 0)
}
// Splits the node, redistributes contacts to the new nodes, and marks the
// node that was split as an inner node of the binary tree of nodes by
// setting this.root.contacts = null
// node: *required* node for splitting
// bitIndex: *required* the bitIndex to which byte to check in the Buffer
// for navigating the binary tree
KBucket.prototype._split = function (node, bitIndex) {
node.left = createNode()
node.right = createNode()
// Splits the bucket, redistributes contacts to the new buckets, and marks the
// bucket that was split as an inner node of the binary tree of buckets by
// setting this.bucket = null
// contact: *required* the contact object to add
// bitIndex: the bitIndex to which byte to check in the Buffer for navigating the
// binary tree
KBucket.prototype._splitAndAdd = function (contact, bitIndex) {
this.low = new KBucket({
arbiter: this.arbiter,
localNodeId: this.localNodeId,
numberOfNodesPerKBucket: this.numberOfNodesPerKBucket,
numberOfNodesToPing: this.numberOfNodesToPing,
root: this.root
})
this.high = new KBucket({
arbiter: this.arbiter,
localNodeId: this.localNodeId,
numberOfNodesPerKBucket: this.numberOfNodesPerKBucket,
numberOfNodesToPing: this.numberOfNodesToPing,
root: this.root
})
// redistribute existing contacts amongst the two newly created nodes
for (var i = 0; i < node.contacts.length; ++i) {
var contact = node.contacts[i]
this._determineNode(node, contact.id, bitIndex).contacts.push(contact)
}
node.contacts = null // mark as inner tree node
bitIndex = bitIndex || 0
// redistribute existing contacts amongst the two newly created buckets
this.bucket.forEach(function (storedContact) {
if (this._determineBucket(storedContact.id, bitIndex) < 0) {
this.low.add(storedContact)
} else {
this.high.add(storedContact)
}
}.bind(this))
this.bucket = null // mark as inner tree node
// don't split the "far away" bucket
// don't split the "far away" node
// we check where the local node would end up and mark the other one as
// "dontSplit" (i.e. "far away")
if (this._determineBucket(this.localNodeId, bitIndex) < 0) {
// local node belongs to "low" bucket, so mark the other one
this.high.dontSplit = true
} else {
this.low.dontSplit = true
}
// add the contact being added
this._add(contact, bitIndex)
return this
var detNode = this._determineNode(node, this.localNodeId, bitIndex)
var otherNode = node.left === detNode ? node.right : node.left
otherNode.dontSplit = true
}

@@ -361,4 +312,9 @@

KBucket.prototype.toArray = function () {
if (this.bucket !== null) return this.bucket.slice(0)
return this.low.toArray().concat(this.high.toArray())
var result = []
for (var nodes = [ this.root ]; nodes.length > 0;) {
var node = nodes.pop()
if (node.contacts === null) nodes.push(node.right, node.left)
else result = result.concat(node.contacts)
}
return result
}

@@ -374,12 +330,11 @@

// contact is marked as most recently contacted.
// node: internal object that has 2 leafs: left and right
// contact: *required* the contact to update
// index: *required* the index in the bucket where contact exists
// (index has already been computed in a previous calculation)
KBucket.prototype._update = function (contact, index) {
KBucket.prototype._update = function (node, index, contact) {
// sanity check
if (!bufferEquals(this.bucket[index].id, contact.id)) {
throw new Error('indexOf() calculation resulted in wrong index')
}
if (!bufferEquals(node.contacts[index].id, contact.id)) throw new Error('wrong index for _update')
var incumbent = this.bucket[index]
var incumbent = node.contacts[index]
var selection = this.arbiter(incumbent, contact)

@@ -390,5 +345,5 @@ // if the selection is our old contact and the candidate is some new

this.bucket.splice(index, 1) // remove old contact
this.bucket.push(selection) // add more recent contact version
this.root.emit('updated', incumbent, selection)
node.contacts.splice(index, 1) // remove old contact
node.contacts.push(selection) // add more recent contact version
this.emit('updated', incumbent, selection)
}

2

package.json
{
"name": "k-bucket",
"version": "3.0.2",
"version": "3.0.3",
"description": "Kademlia DHT K-bucket implementation as a binary tree",

@@ -5,0 +5,0 @@ "keywords": [

26

README.md

@@ -28,3 +28,3 @@ # k-bucket

localNodeId: new Buffer("my node id") // default: random data
});
})
```

@@ -135,3 +135,2 @@

* `numberOfNodesToPing`: _Integer_ _(Default: 3)_ The number of nodes to ping when a bucket that should not be split becomes full. KBucket will emit a `ping` event that contains `numberOfNodesToPing` nodes that have not been contacted the longest.
* `root`: _Object_ _**CAUTION: reserved for internal use**_ Provides a reference to the root of the tree data structure as the k-bucket splits when new contacts are added.

@@ -183,12 +182,11 @@ Creates a new KBucket.

#### kBucket._determineBucket(id, [bitIndex])
#### kBucket._determineNode(node, id, [bitIndex])
_**CAUTION: reserved for internal use**_
* `node`: internal object that has 2 leafs: left and right
* `id`: _Buffer_ Id to compare `localNodeId` with.
* `bitIndex`: _Integer_ _(Default: 0)_ The bit index to which bit to check in the `id` Buffer.
* Return: _Integer_ -1 if `id` at `bitIndex` is 0, 1 otherwise.
* Return: _Object_ left leaf if `id` at `bitIndex` is 0, right leaf otherwise.
Determines whether the `id` at the `bitIndex` is 0 or 1. If 0, returns -1, else 1.
#### kBucket._indexOf(id)

@@ -198,2 +196,3 @@

* `node`: internal object that has 2 leafs: left and right
* `id`: _Buffer_ Contact node id.

@@ -204,22 +203,20 @@ * Return: _Integer_ Index of `contact` with provided `id` if it exists, -1 otherwise.

#### kBucket._splitAndAdd(contact, [bitIndex])
#### kBucket._split(node, [bitIndex])
_**CAUTION: reserved for internal use**_
* `contact`: _Object_ The contact object to add.
* `id`: _Buffer_ Contact node id.
* Any satellite data that is part of the `contact` object will not be altered, only `id` is used.
* `node`: _Object_ node for splitting
* `bitIndex`: _Integer_ _(Default: 0)_ The bit index to which bit to check in the `id` Buffer.
* Return: _Object_ The k-bucket itself.
Splits the bucket, redistributes contacts to the new buckets, and marks the bucket that was split as an inner node of the binary tree of buckets by setting `self.bucket = undefined`. Also, marks the "far away" bucket as `dontSplit`.
Splits the node, redistributes contacts to the new nodes, and marks the node that was split as an inner node of the binary tree of nodes by setting `self.contacts = null`. Also, marks the "far away" node as `dontSplit`.
#### kBucket._update(contact, index)
#### kBucket._update(node, index, contact)
_**CAUTION: reserved for internal use**_
* `node`: internal object that has 2 leafs: left and right
* `index`: _Integer_ The index in the bucket where contact exists (index has already been computed in previous calculation).
* `contact`: _Object_ The contact object to update.
* `id`: _Buffer_ Contact node id
* Any satellite data that is part of the `contact` object will not be altered, only `id` is used.
* `index`: _Integer_ The index in the bucket where contact exists (index has already been computed in previous calculation).

@@ -276,1 +273,2 @@ Updates the `contact` by using the `arbiter` function to compare the incumbent and the candidate. If `arbiter` function selects the old `contact` but the candidate is some new `contact`, then the new `contact` is abandoned. If `arbiter` function selects the old `contact` and the candidate is that same old `contact`, the `contact` is marked as most recently contacted (by being moved to the right/end of the bucket array). If `arbiter` function selects the new `contact`, the old `contact` is removed and the new `contact` is marked as most recently contacted.

- [Distributed Hash Tables (part 2)](https://web.archive.org/web/20140217064545/http://offthelip.org/?p=157)

32

test/add.js

@@ -14,11 +14,11 @@ 'use strict'

test('adding a contact places it in bucket', function (t) {
test('adding a contact places it in root node', function (t) {
var kBucket = new KBucket()
var contact = { id: new Buffer('a') }
kBucket.add(contact)
t.true(kBucket.bucket[0] === contact)
t.same(kBucket.root.contacts, [ contact ])
t.end()
})
test('adding an existing contact does not increase number of contacts in bucket', function (t) {
test('adding an existing contact does not increase number of contacts in root node', function (t) {
var kBucket = new KBucket()

@@ -28,17 +28,17 @@ var contact = { id: new Buffer('a') }

kBucket.add({ id: new Buffer('a') })
t.same(kBucket.bucket.length, 1)
t.same(kBucket.root.contacts.length, 1)
t.end()
})
test('adding same contact moves it to the end of the bucket (most-recently-contacted end)', function (t) {
test('adding same contact moves it to the end of the root node (most-recently-contacted end)', function (t) {
var kBucket = new KBucket()
var contact = { id: new Buffer('a') }
kBucket.add(contact)
t.same(kBucket.bucket.length, 1)
t.same(kBucket.root.contacts.length, 1)
kBucket.add({ id: new Buffer('b') })
t.same(kBucket.bucket.length, 2)
t.true(kBucket.bucket[0] === contact) // least-recently-contacted end
t.same(kBucket.root.contacts.length, 2)
t.true(kBucket.root.contacts[0] === contact) // least-recently-contacted end
kBucket.add(contact)
t.same(kBucket.bucket.length, 2)
t.true(kBucket.bucket[1] === contact) // most-recently-contacted end
t.same(kBucket.root.contacts.length, 2)
t.true(kBucket.root.contacts[1] === contact) // most-recently-contacted end
t.end()

@@ -52,6 +52,6 @@ })

t.same(contacts.length, kBucket.numberOfNodesToPing)
// console.dir(kBucket.high.bucket[0])
// console.dir(kBucket.root.right.contacts[0])
for (var i = 0; i < kBucket.numberOfNodesToPing; ++i) {
// the least recently contacted end of the bucket should be pinged
t.true(contacts[i] === kBucket.high.bucket[i])
// the least recently contacted end of the node should be pinged
t.true(contacts[i] === kBucket.root.right.contacts[i])
}

@@ -62,3 +62,3 @@ t.same(replacement, { id: new Buffer([ 0x80, j ]) })

for (var j = 0; j < kBucket.numberOfNodesPerKBucket + 1; ++j) {
kBucket.add({ id: new Buffer([ 0x80, j ]) }) // make sure all go into "far away" bucket
kBucket.add({ id: new Buffer([ 0x80, j ]) }) // make sure all go into "far away" node
}

@@ -79,3 +79,3 @@ })

test('should generate event "added" when adding to a split bucket', function (t) {
test('should generate event "added" when adding to a split node', function (t) {
t.plan(2)

@@ -88,3 +88,3 @@ var kBucket = new KBucket({

}
t.false(kBucket.bucket)
t.same(kBucket.root.contacts, null)
var contact = { id: new Buffer('a') }

@@ -91,0 +91,0 @@ kBucket.on('added', function (newContact) {

1

test/closest.js

@@ -19,2 +19,3 @@ 'use strict'

var contacts = kBucket.closest(contact.id, 3)
t.same(contacts.length, 3)
t.same(contacts[0].id, new Buffer([ 0x11 ])) // distance: 00000100

@@ -21,0 +22,0 @@ t.same(contacts[1].id, new Buffer([ 0x10 ])) // distance: 00000101

6

test/createKBucket.js

@@ -16,3 +16,3 @@ 'use strict'

var localNodeId = new Buffer('some length')
var kBucket = new KBucket({localNodeId: localNodeId})
var kBucket = new KBucket({ localNodeId: localNodeId })
t.true(kBucket.localNodeId instanceof Buffer)

@@ -30,5 +30,5 @@ t.true(bufferEquals(kBucket.localNodeId, localNodeId))

test('root is \'self\' if not provided', function (t) {
test('check root node', function (t) {
var kBucket = new KBucket()
t.same(kBucket.root, kBucket)
t.same(kBucket.root, { contacts: [], dontSplit: false, left: null, right: null })
t.end()

@@ -35,0 +35,0 @@ })

2

test/get.js

@@ -16,3 +16,3 @@ 'use strict'

var kBucket = new KBucket()
t.same(null, kBucket.get(new Buffer('foo')))
t.same(kBucket.get(new Buffer('foo')), null)
t.end()

@@ -19,0 +19,0 @@ })

4

test/indexOf.js

@@ -8,3 +8,3 @@ 'use strict'

kBucket.add({ id: new Buffer('a') })
t.same(kBucket._indexOf(new Buffer('a')), 0)
t.same(kBucket._indexOf(kBucket.root, new Buffer('a')), 0)
t.end()

@@ -16,4 +16,4 @@ })

kBucket.add({ id: new Buffer('a') })
t.same(kBucket._indexOf(new Buffer('b')), -1)
t.same(kBucket._indexOf(kBucket.root, new Buffer('b')), -1)
t.end()
})

4

test/remove.js

@@ -23,5 +23,5 @@ 'use strict'

var contactToDelete = { id: new Buffer([ 0x80, 0x00 ]) }
t.same(kBucket.high._indexOf(contactToDelete.id), 0)
t.same(kBucket._indexOf(kBucket.root.right, contactToDelete.id), 0)
kBucket.remove(new Buffer([ 0x80, 0x00 ]))
t.same(kBucket.high._indexOf(contactToDelete.id), -1)
t.same(kBucket._indexOf(kBucket.root.right, contactToDelete.id), -1)
t.end()

@@ -28,0 +28,0 @@ })

72

test/split.js

@@ -5,12 +5,12 @@ 'use strict'

test('adding a contact does not split K-bucket', function (t) {
test('adding a contact does not split node', function (t) {
var kBucket = new KBucket()
kBucket.add({ id: new Buffer('a') })
t.false(kBucket.low)
t.false(kBucket.high)
t.true(kBucket.bucket)
t.same(kBucket.root.left, null)
t.same(kBucket.root.right, null)
t.notSame(kBucket.root.contacts, null)
t.end()
})
test('adding maximum number of contacts (per K-bucket) [20] into K-bucket does not split K-bucket', function (t) {
test('adding maximum number of contacts (per node) [20] into node does not split node', function (t) {
var kBucket = new KBucket()

@@ -20,9 +20,9 @@ for (var i = 0; i < kBucket.numberOfNodesPerKBucket; ++i) {

}
t.false(kBucket.low)
t.false(kBucket.high)
t.true(kBucket.bucket)
t.same(kBucket.root.left, null)
t.same(kBucket.root.right, null)
t.notSame(kBucket.root.contacts, null)
t.end()
})
test('adding maximum number of contacts (per K-bucket) + 1 [21] into K-bucket splits the K-bucket', function (t) {
test('adding maximum number of contacts (per node) + 1 [21] into node splits the node', function (t) {
var kBucket = new KBucket()

@@ -32,25 +32,9 @@ for (var i = 0; i < kBucket.numberOfNodesPerKBucket + 1; ++i) {

}
t.true(kBucket.low instanceof KBucket)
t.true(kBucket.high instanceof KBucket)
t.false(kBucket.bucket)
t.notSame(kBucket.root.left, null)
t.notSame(kBucket.root.right, null)
t.same(kBucket.root.contacts, null)
t.end()
})
test('split buckets inherit options from parent bucket', function (t) {
var OPTIONS = ['arbiter', 'localNodeId', 'root', 'numberOfNodesPerKBucket', 'numberOfNodesToPing']
t.plan(OPTIONS.length * 2)
var kBucket = new KBucket()
var _options = {}
OPTIONS.forEach(function (option) { _options[option] = kBucket[option] })
for (var i = 0; i < kBucket.numberOfNodesPerKBucket + 1; ++i) {
kBucket.add({ id: new Buffer('' + i) })
}
OPTIONS.forEach(function (option) {
t.same(kBucket.low[option], _options[option])
t.same(kBucket.high[option], _options[option])
})
t.end()
})
test('split buckets contain all added contacts', function (t) {
test('split nodes contain all added contacts', function (t) {
t.plan(20 /* numberOfNodesPerKBucket */ + 2)

@@ -64,7 +48,7 @@ var kBucket = new KBucket({ localNodeId: new Buffer([ 0x00 ]) })

var traverse = function (node) {
if (!node.bucket) {
traverse(node.low)
traverse(node.high)
if (node.contacts === null) {
traverse(node.left)
traverse(node.right)
} else {
node.bucket.forEach(function (contact) {
node.contacts.forEach(function (contact) {
foundContact[parseInt(contact.id.toString('hex'), 16)] = true

@@ -74,9 +58,9 @@ })

}
traverse(kBucket)
traverse(kBucket.root)
Object.keys(foundContact).forEach(function (key) { t.true(foundContact[key], key) })
t.false(kBucket.bucket)
t.same(kBucket.root.contacts, null)
t.end()
})
test('when splitting buckets the "far away" bucket should be marked to prevent splitting "far away" bucket', function (t) {
test('when splitting nodes the "far away" node should be marked to prevent splitting "far away" node', function (t) {
t.plan(5)

@@ -87,11 +71,11 @@ var kBucket = new KBucket({ localNodeId: new Buffer([ 0x00 ]) })

}
// above algorithm will split low bucket 4 times and put 0x00 through 0x0f
// in the low bucket, and put 0x10 through 0x14 in high bucket
// since localNodeId is 0x00, we expect every high bucket to be "far" and
// above algorithm will split left node 4 times and put 0x00 through 0x0f
// in the left node, and put 0x10 through 0x14 in right node
// since localNodeId is 0x00, we expect every right node to be "far" and
// therefore marked as "dontSplit = true"
// there will be one "low" bucket and four "high" buckets (t.expect(5))
// there will be one "left" node and four "right" nodes (t.expect(5))
var traverse = function (node, dontSplit) {
if (!node.bucket) {
traverse(node.low, false)
traverse(node.high, true)
if (node.contacts === null) {
traverse(node.left, false)
traverse(node.right, true)
} else {

@@ -102,4 +86,4 @@ if (dontSplit) t.true(node.dontSplit)

}
traverse(kBucket)
traverse(kBucket.root)
t.end()
})

20

test/update.js

@@ -20,4 +20,4 @@ 'use strict'

kBucket.add(contact)
kBucket._update({ id: new Buffer('a'), vectorClock: 2 }, 0)
t.same(kBucket.bucket[0].vectorClock, 3)
kBucket._update(kBucket.root, 0, { id: new Buffer('a'), vectorClock: 2 })
t.same(kBucket.root.contacts[0].vectorClock, 3)
t.end()

@@ -31,4 +31,4 @@ })

kBucket.add({ id: new Buffer('b') })
kBucket._update(contact, 0)
t.same(kBucket.bucket[1], contact)
kBucket._update(kBucket.root, 0, contact)
t.same(kBucket.root.contacts[1], contact)
t.end()

@@ -42,7 +42,7 @@ })

kBucket.add({ id: new Buffer('b') })
kBucket._update({ id: new Buffer('a'), newer: 'property', vectorClock: 4 }, 0)
t.true(bufferEquals(kBucket.bucket[1].id, contact.id))
t.same(kBucket.bucket[1].vectorClock, 4)
t.same(kBucket.bucket[1].old, undefined)
t.same(kBucket.bucket[1].newer, 'property')
kBucket._update(kBucket.root, 0, { id: new Buffer('a'), newer: 'property', vectorClock: 4 })
t.true(bufferEquals(kBucket.root.contacts[1].id, contact.id))
t.same(kBucket.root.contacts[1].vectorClock, 4)
t.same(kBucket.root.contacts[1].old, undefined)
t.same(kBucket.root.contacts[1].newer, 'property')
t.end()

@@ -65,3 +65,3 @@ })

test('should generate event "updated" when updating a split bucket', function (t) {
test('should generate event "updated" when updating a split node', function (t) {
t.plan(3)

@@ -68,0 +68,0 @@ var kBucket = new KBucket({

test/determineBucket.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