k-bucket - npm Package Compare versions
Comparing version 4.0.1 to 5.0.0
602
index.js
@@ -6,3 +6,3 @@ /* | ||
| Copyright (c) 2013-2016 Tristan Slominski | ||
| Copyright (c) 2013-2018 Tristan Slominski | ||
@@ -32,11 +32,10 @@ Permission is hereby granted, free of charge, to any person | ||
| var randomBytes = require('randombytes') | ||
| var EventEmitter = require('events').EventEmitter | ||
| var inherits = require('inherits') | ||
| const randomBytes = require('randombytes') | ||
| const { EventEmitter } = require('events') | ||
| module.exports = KBucket | ||
| // array1: Uint8Array | ||
| // array2: Uint8Array | ||
| // Return: boolean | ||
| /** | ||
| * @param {Uint8Array} array1 | ||
| * @param {Uint8Array} array2 | ||
| * @return {Boolean} | ||
| */ | ||
| function arrayEquals (array1, array2) { | ||
@@ -49,3 +48,3 @@ if (array1 === array2) { | ||
| } | ||
| for (var i = 0, length = array1.length; i < length; ++i) { | ||
| for (let i = 0, length = array1.length; i < length; ++i) { | ||
| if (array1[i] !== array2[i]) { | ||
@@ -62,295 +61,380 @@ return false | ||
| /* | ||
| * `options`: | ||
| * `distance`: _Function_ | ||
| `function (firstId, secondId) { return distance }` An optional | ||
| `distance` function that gets two `id` Uint8Arrays | ||
| and return distance (as number) between them. | ||
| * `arbiter`: _Function_ _(Default: vectorClock arbiter)_ | ||
| `function (incumbent, candidate) { return contact; }` An optional | ||
| `arbiter` function that givent two `contact` objects with the same `id` | ||
| returns the desired object to be used for updating the k-bucket. For | ||
| more details, see [arbiter function](#arbiter-function). | ||
| * `localNodeId`: _Uint8Array_ An optional Uint8Array representing the local node id. | ||
| If not provided, a local node id will be created via `randomBytes(20)`. | ||
| * `metadata`: _Object_ _(Default: {})_ Optional satellite data to include | ||
| with the k-bucket. `metadata` property is guaranteed not be altered by, | ||
| it is provided as an explicit container for users of k-bucket to store | ||
| implementation-specific data. | ||
| * `numberOfNodesPerKBucket`: _Integer_ _(Default: 20)_ The number of nodes | ||
| that a k-bucket can contain before being full or split. | ||
| * `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. | ||
| */ | ||
| function KBucket (options) { | ||
| EventEmitter.call(this) | ||
| options = options || {} | ||
| this.localNodeId = options.localNodeId || randomBytes(20) | ||
| if (!(this.localNodeId instanceof Uint8Array)) throw new TypeError('localNodeId is not a Uint8Array') | ||
| this.numberOfNodesPerKBucket = options.numberOfNodesPerKBucket || 20 | ||
| this.numberOfNodesToPing = options.numberOfNodesToPing || 3 | ||
| this.distance = options.distance || KBucket.distance | ||
| // use an arbiter from options or vectorClock arbiter by default | ||
| this.arbiter = options.arbiter || KBucket.arbiter | ||
| this.root = createNode() | ||
| this.metadata = Object.assign({}, options.metadata) | ||
| function ensureInt8 (name, val) { | ||
| if (!(val instanceof Uint8Array)) { | ||
| throw new TypeError(name + ' is not a Uint8Array') | ||
| } | ||
| } | ||
| inherits(KBucket, EventEmitter) | ||
| /** | ||
| * Implementation of a Kademlia DHT k-bucket used for storing | ||
| * contact (peer node) information. | ||
| * | ||
| * @extends EventEmitter | ||
| */ | ||
| class KBucket extends EventEmitter { | ||
| /** | ||
| * `options`: | ||
| * `distance`: _Function_ | ||
| * `function (firstId, secondId) { return distance }` An optional | ||
| * `distance` function that gets two `id` Uint8Arrays | ||
| * and return distance (as number) between them. | ||
| * `arbiter`: _Function_ _(Default: vectorClock arbiter)_ | ||
| * `function (incumbent, candidate) { return contact; }` An optional | ||
| * `arbiter` function that givent two `contact` objects with the same `id` | ||
| * returns the desired object to be used for updating the k-bucket. For | ||
| * more details, see [arbiter function](#arbiter-function). | ||
| * `localNodeId`: _Uint8Array_ An optional Uint8Array representing the local node id. | ||
| * If not provided, a local node id will be created via `randomBytes(20)`. | ||
| * `metadata`: _Object_ _(Default: {})_ Optional satellite data to include | ||
| * with the k-bucket. `metadata` property is guaranteed not be altered by, | ||
| * it is provided as an explicit container for users of k-bucket to store | ||
| * implementation-specific data. | ||
| * `numberOfNodesPerKBucket`: _Integer_ _(Default: 20)_ The number of nodes | ||
| * that a k-bucket can contain before being full or split. | ||
| * `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. | ||
| * | ||
| * @param {Object=} options optional | ||
| */ | ||
| constructor (options = {}) { | ||
| super() | ||
| KBucket.arbiter = function (incumbent, candidate) { | ||
| return incumbent.vectorClock > candidate.vectorClock ? incumbent : candidate | ||
| } | ||
| this.localNodeId = options.localNodeId || randomBytes(20) | ||
| this.numberOfNodesPerKBucket = options.numberOfNodesPerKBucket || 20 | ||
| this.numberOfNodesToPing = options.numberOfNodesToPing || 3 | ||
| this.distance = options.distance || KBucket.distance | ||
| // use an arbiter from options or vectorClock arbiter by default | ||
| this.arbiter = options.arbiter || KBucket.arbiter | ||
| this.metadata = Object.assign({}, options.metadata) | ||
| KBucket.distance = function (firstId, secondId) { | ||
| var distance = 0 | ||
| var min = Math.min(firstId.length, secondId.length) | ||
| var max = Math.max(firstId.length, secondId.length) | ||
| for (var i = 0; i < min; ++i) distance = distance * 256 + (firstId[i] ^ secondId[i]) | ||
| for (; i < max; ++i) distance = distance * 256 + 255 | ||
| return distance | ||
| } | ||
| ensureInt8('option.localNodeId as parameter 1', this.localNodeId) | ||
| // contact: *required* the contact object to add | ||
| KBucket.prototype.add = function (contact) { | ||
| if (!contact || !(contact.id instanceof Uint8Array)) throw new TypeError('contact.id is not a Uint8Array') | ||
| 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 | ||
| node = this._determineNode(node, contact.id, bitIndex++) | ||
| this.root = createNode() | ||
| } | ||
| // check if the contact already exists | ||
| var index = this._indexOf(node, contact.id) | ||
| if (index >= 0) { | ||
| this._update(node, index, contact) | ||
| return this | ||
| /** | ||
| * Default arbiter function for contacts with the same id. Uses | ||
| * contact.vectorClock to select which contact to update the k-bucket with. | ||
| * Contact with larger vectorClock field will be selected. If vectorClock is | ||
| * the same, candidat will be selected. | ||
| * | ||
| * @param {Object} incumbent Contact currently stored in the k-bucket. | ||
| * @param {Object} candidate Contact being added to the k-bucket. | ||
| * @return {Object} Contact to updated the k-bucket with. | ||
| */ | ||
| static arbiter (incumbent, candidate) { | ||
| return incumbent.vectorClock > candidate.vectorClock ? incumbent : candidate | ||
| } | ||
| if (node.contacts.length < this.numberOfNodesPerKBucket) { | ||
| node.contacts.push(contact) | ||
| this.emit('added', contact) | ||
| return this | ||
| /** | ||
| * Default distance function. Finds the XOR | ||
| * distance between firstId and secondId. | ||
| * | ||
| * @param {Uint8Array} firstId Uint8Array containing first id. | ||
| * @param {Uint8Array} secondId Uint8Array containing second id. | ||
| * @return {Number} Integer The XOR distance between firstId | ||
| * and secondId. | ||
| */ | ||
| static distance (firstId, secondId) { | ||
| let distance = 0 | ||
| let i = 0 | ||
| const min = Math.min(firstId.length, secondId.length) | ||
| const max = Math.max(firstId.length, secondId.length) | ||
| for (; i < min; ++i) { | ||
| distance = distance * 256 + (firstId[i] ^ secondId[i]) | ||
| } | ||
| for (; i < max; ++i) distance = distance * 256 + 255 | ||
| return distance | ||
| } | ||
| // the bucket is full | ||
| if (node.dontSplit) { | ||
| // we are not allowed to split the bucket | ||
| // we need to ping the first this.numberOfNodesToPing | ||
| // in order to determine if they are alive | ||
| // only if one of the pinged nodes does not respond, can the new contact | ||
| // be added (this prevents DoS flodding with new invalid contacts) | ||
| this.emit('ping', node.contacts.slice(0, this.numberOfNodesToPing), contact) | ||
| return this | ||
| } | ||
| /** | ||
| * Adds a contact to the k-bucket. | ||
| * | ||
| * @param {Object} contact the contact object to add | ||
| */ | ||
| add (contact) { | ||
| ensureInt8('contact.id', (contact || {}).id) | ||
| this._split(node, bitIndex) | ||
| return this.add(contact) | ||
| } | ||
| let bitIndex = 0 | ||
| let node = this.root | ||
| // id: Uint8Array *required* node id | ||
| // n: Integer (Default: Infinity) 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 (!(id instanceof Uint8Array)) throw new TypeError('id is not a Uint8Array') | ||
| if (n === undefined) n = Infinity | ||
| if (typeof n !== 'number' || isNaN(n) || n <= 0) throw new TypeError('n is not positive number') | ||
| var contacts = [] | ||
| 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 | ||
| node = this._determineNode(node, contact.id, bitIndex++) | ||
| } | ||
| 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 = contacts.concat(node.contacts) | ||
| // check if the contact already exists | ||
| const index = this._indexOf(node, contact.id) | ||
| if (index >= 0) { | ||
| this._update(node, index, contact) | ||
| return this | ||
| } | ||
| } | ||
| var self = this | ||
| return contacts | ||
| .map(function (a) { | ||
| return [self.distance(a.id, id), a] | ||
| }) | ||
| .sort(function (a, b) { | ||
| return a[0] - b[0] | ||
| }) | ||
| .slice(0, n) | ||
| .map(function (a) { | ||
| return a[1] | ||
| }) | ||
| } | ||
| if (node.contacts.length < this.numberOfNodesPerKBucket) { | ||
| node.contacts.push(contact) | ||
| this.emit('added', contact) | ||
| return this | ||
| } | ||
| // Counts the number of contacts recursively. | ||
| // If this is a leaf, just return the number of contacts contained. Otherwise, | ||
| // return the length of the high and low branches combined. | ||
| 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 | ||
| // the bucket is full | ||
| if (node.dontSplit) { | ||
| // we are not allowed to split the bucket | ||
| // we need to ping the first this.numberOfNodesToPing | ||
| // in order to determine if they are alive | ||
| // only if one of the pinged nodes does not respond, can the new contact | ||
| // be added (this prevents DoS flodding with new invalid contacts) | ||
| this.emit('ping', node.contacts.slice(0, this.numberOfNodesToPing), contact) | ||
| return this | ||
| } | ||
| this._split(node, bitIndex) | ||
| return this.add(contact) | ||
| } | ||
| return count | ||
| } | ||
| // 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 Uint8Array to compare localNodeId with | ||
| // bitIndex: the bitIndex to which bit to check in the id Uint8Array | ||
| KBucket.prototype._determineNode = function (node, id, bitIndex) { | ||
| // **NOTE** remember that id is a Uint8Array and has granularity of | ||
| // bytes (8 bits), whereas the bitIndex is the _bit_ index (not byte) | ||
| /** | ||
| * Get the n closest contacts to the provided node id. "Closest" here means: | ||
| * closest according to the XOR metric of the contact node id. | ||
| * | ||
| * @param {Uint8Array} id Contact node id | ||
| * @param {Number=} n Integer (Default: Infinity) The maximum number of | ||
| * closest contacts to return | ||
| * @return {Array} Array Maximum of n closest contacts to the node id | ||
| */ | ||
| closest (id, n = Infinity) { | ||
| ensureInt8('id', id) | ||
| // id's that are too short are put in low bucket (1 byte = 8 bits) | ||
| // ~~(bitIndex / 8) finds how many bytes the bitIndex describes, "~~" is | ||
| // equivalent to "parseInt" | ||
| // bitIndex % 8 checks if we have extra bits beyond byte multiples | ||
| // if number of bytes is <= no. of bytes described by bitIndex and there | ||
| // are extra bits to consider, this means id has less bits than what | ||
| // bitIndex describes, id therefore is too short, and will be put in low | ||
| // bucket | ||
| var bytesDescribedByBitIndex = ~~(bitIndex / 8) | ||
| var bitIndexWithinByte = bitIndex % 8 | ||
| if ((id.length <= bytesDescribedByBitIndex) && (bitIndexWithinByte !== 0)) return node.left | ||
| if ((!Number.isInteger(n) && n !== Infinity) || n <= 0) { | ||
| throw new TypeError('n is not positive number') | ||
| } | ||
| var byteUnderConsideration = id[bytesDescribedByBitIndex] | ||
| let contacts = [] | ||
| // byteUnderConsideration is an integer from 0 to 255 represented by 8 bits | ||
| // where 255 is 11111111 and 0 is 00000000 | ||
| // in order to find out whether the bit at bitIndexWithinByte is set | ||
| // we construct Math.pow(2, (7 - bitIndexWithinByte)) which will consist | ||
| // of all bits being 0, with only one bit set to 1 | ||
| // for example, if bitIndexWithinByte is 3, we will construct 00010000 by | ||
| // Math.pow(2, (7 - 3)) -> Math.pow(2, 4) -> 16 | ||
| if (byteUnderConsideration & Math.pow(2, (7 - bitIndexWithinByte))) return node.right | ||
| for (let nodes = [ this.root ], bitIndex = 0; nodes.length > 0 && contacts.length < n;) { | ||
| const node = nodes.pop() | ||
| if (node.contacts === null) { | ||
| const detNode = this._determineNode(node, id, bitIndex++) | ||
| nodes.push(node.left === detNode ? node.right : node.left) | ||
| nodes.push(detNode) | ||
| } else { | ||
| contacts = contacts.concat(node.contacts) | ||
| } | ||
| } | ||
| return node.left | ||
| } | ||
| return contacts | ||
| .map(a => [this.distance(a.id, id), a]) | ||
| .sort((a, b) => a[0] - b[0]) | ||
| .slice(0, n) | ||
| .map(a => a[1]) | ||
| } | ||
| // 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: Uint8Array *required* The ID of the contact to fetch. | ||
| KBucket.prototype.get = function (id) { | ||
| if (!(id instanceof Uint8Array)) throw new TypeError('id is not a Uint8Array') | ||
| var bitIndex = 0 | ||
| var node = this.root | ||
| while (node.contacts === null) { | ||
| node = this._determineNode(node, id, bitIndex++) | ||
| /** | ||
| * Counts the total number of contacts in the tree. | ||
| * | ||
| * @return {Number} The number of contacts held in the tree | ||
| */ | ||
| count () { | ||
| // return this.toArray().length | ||
| let count = 0 | ||
| for (const nodes = [ this.root ]; nodes.length > 0;) { | ||
| const node = nodes.pop() | ||
| if (node.contacts === null) nodes.push(node.right, node.left) | ||
| else count += node.contacts.length | ||
| } | ||
| return count | ||
| } | ||
| var index = this._indexOf(node, id) // index of uses contact id for matching | ||
| return index >= 0 ? node.contacts[index] : null | ||
| } | ||
| /** | ||
| * Determines whether the id at the bitIndex is 0 or 1. | ||
| * Return left leaf if `id` at `bitIndex` is 0, right leaf otherwise | ||
| * | ||
| * @param {Object} node internal object that has 2 leafs: left and right | ||
| * @param {Uint8Array} id Id to compare localNodeId with. | ||
| * @param {Number} bitIndex Integer (Default: 0) The bit index to which bit | ||
| * to check in the id Uint8Array. | ||
| * @return {Object} left leaf if id at bitIndex is 0, right leaf otherwise. | ||
| */ | ||
| _determineNode (node, id, bitIndex) { | ||
| // **NOTE** remember that id is a Uint8Array and has granularity of | ||
| // bytes (8 bits), whereas the bitIndex is the _bit_ index (not byte) | ||
| // node: internal object that has 2 leafs: left and right | ||
| // id: Uint8Array Contact node id. | ||
| // Returns the index of the contact with the given id if it exists | ||
| KBucket.prototype._indexOf = function (node, id) { | ||
| for (var i = 0; i < node.contacts.length; ++i) { | ||
| if (arrayEquals(node.contacts[i].id, id)) return i | ||
| // id's that are too short are put in low bucket (1 byte = 8 bits) | ||
| // (bitIndex >> 3) finds how many bytes the bitIndex describes | ||
| // bitIndex % 8 checks if we have extra bits beyond byte multiples | ||
| // if number of bytes is <= no. of bytes described by bitIndex and there | ||
| // are extra bits to consider, this means id has less bits than what | ||
| // bitIndex describes, id therefore is too short, and will be put in low | ||
| // bucket | ||
| const bytesDescribedByBitIndex = bitIndex >> 3 | ||
| const bitIndexWithinByte = bitIndex % 8 | ||
| if ((id.length <= bytesDescribedByBitIndex) && (bitIndexWithinByte !== 0)) { | ||
| return node.left | ||
| } | ||
| const byteUnderConsideration = id[bytesDescribedByBitIndex] | ||
| // byteUnderConsideration is an integer from 0 to 255 represented by 8 bits | ||
| // where 255 is 11111111 and 0 is 00000000 | ||
| // in order to find out whether the bit at bitIndexWithinByte is set | ||
| // we construct (1 << (7 - bitIndexWithinByte)) which will consist | ||
| // of all bits being 0, with only one bit set to 1 | ||
| // for example, if bitIndexWithinByte is 3, we will construct 00010000 by | ||
| // (1 << (7 - 3)) -> (1 << 4) -> 16 | ||
| if (byteUnderConsideration & (1 << (7 - bitIndexWithinByte))) { | ||
| return node.right | ||
| } | ||
| return node.left | ||
| } | ||
| return -1 | ||
| } | ||
| /** | ||
| * 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. | ||
| * | ||
| * @param {Uint8Array} id The ID of the contact to fetch. | ||
| * @return {Object|Null} The contact if available, otherwise null | ||
| */ | ||
| get (id) { | ||
| ensureInt8('id', id) | ||
| // id: Uint8Array *required* The ID of the contact to remove. | ||
| KBucket.prototype.remove = function (id) { | ||
| if (!(id instanceof Uint8Array)) throw new TypeError('id is not a Uint8Array') | ||
| var bitIndex = 0 | ||
| let bitIndex = 0 | ||
| var node = this.root | ||
| while (node.contacts === null) { | ||
| node = this._determineNode(node, id, bitIndex++) | ||
| let node = this.root | ||
| while (node.contacts === null) { | ||
| node = this._determineNode(node, id, bitIndex++) | ||
| } | ||
| // index of uses contact id for matching | ||
| const index = this._indexOf(node, id) | ||
| return index >= 0 ? node.contacts[index] : null | ||
| } | ||
| var index = this._indexOf(node, id) | ||
| if (index >= 0) { | ||
| var contact = node.contacts.splice(index, 1)[0] | ||
| this.emit('removed', contact) | ||
| /** | ||
| * Returns the index of the contact with provided | ||
| * id if it exists, returns -1 otherwise. | ||
| * | ||
| * @param {Object} node internal object that has 2 leafs: left and right | ||
| * @param {Uint8Array} id Contact node id. | ||
| * @return {Number} Integer Index of contact with provided id if it | ||
| * exists, -1 otherwise. | ||
| */ | ||
| _indexOf (node, id) { | ||
| for (let i = 0; i < node.contacts.length; ++i) { | ||
| if (arrayEquals(node.contacts[i].id, id)) return i | ||
| } | ||
| return -1 | ||
| } | ||
| return this | ||
| } | ||
| /** | ||
| * Removes contact with the provided id. | ||
| * | ||
| * @param {Uint8Array} id The ID of the contact to remove. | ||
| * @return {Object} The k-bucket itself. | ||
| */ | ||
| remove (id) { | ||
| ensureInt8('the id as parameter 1', id) | ||
| // 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 Uint8Array | ||
| // for navigating the binary tree | ||
| KBucket.prototype._split = function (node, bitIndex) { | ||
| node.left = createNode() | ||
| node.right = createNode() | ||
| let bitIndex = 0 | ||
| let node = 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) | ||
| while (node.contacts === null) { | ||
| node = this._determineNode(node, id, bitIndex++) | ||
| } | ||
| const index = this._indexOf(node, id) | ||
| if (index >= 0) { | ||
| const contact = node.contacts.splice(index, 1)[0] | ||
| this.emit('removed', contact) | ||
| } | ||
| return this | ||
| } | ||
| node.contacts = null // mark as inner tree node | ||
| // 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") | ||
| var detNode = this._determineNode(node, this.localNodeId, bitIndex) | ||
| var otherNode = node.left === detNode ? node.right : node.left | ||
| otherNode.dontSplit = true | ||
| } | ||
| /** | ||
| * 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 | ||
| * | ||
| * @param {Object} node node for splitting | ||
| * @param {Number} bitIndex the bitIndex to which byte to check in the | ||
| * Uint8Array for navigating the binary tree | ||
| */ | ||
| _split (node, bitIndex) { | ||
| node.left = createNode() | ||
| node.right = createNode() | ||
| // Returns all the contacts contained in the tree as an array. | ||
| // If this is a leaf, return a copy of the bucket. `slice` is used so that we | ||
| // don't accidentally leak an internal reference out that might be accidentally | ||
| // misused. If this is not a leaf, return the union of the low and high | ||
| // branches (themselves also as arrays). | ||
| KBucket.prototype.toArray = function () { | ||
| 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) | ||
| // redistribute existing contacts amongst the two newly created nodes | ||
| for (const contact of node.contacts) { | ||
| this._determineNode(node, contact.id, bitIndex).contacts.push(contact) | ||
| } | ||
| node.contacts = null // mark as inner tree node | ||
| // 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") | ||
| const detNode = this._determineNode(node, this.localNodeId, bitIndex) | ||
| const otherNode = node.left === detNode ? node.right : node.left | ||
| otherNode.dontSplit = true | ||
| } | ||
| return result | ||
| } | ||
| // Updates the contact selected by the arbiter. | ||
| // If the selection is our old contact and the candidate is some new contact | ||
| // then the new contact is abandoned (not added). | ||
| // If the selection is our old contact and the candidate is our old contact | ||
| // then we are refreshing the contact and it is marked as most recently | ||
| // contacted (by being moved to the right/end of the bucket array). | ||
| // If the selection is our new contact, the old contact is removed and the new | ||
| // 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 (node, index, contact) { | ||
| // sanity check | ||
| if (!arrayEquals(node.contacts[index].id, contact.id)) throw new Error('wrong index for _update') | ||
| /** | ||
| * Returns all the contacts contained in the tree as an array. | ||
| * If this is a leaf, return a copy of the bucket. `slice` is used so that we | ||
| * don't accidentally leak an internal reference out that might be | ||
| * accidentally misused. If this is not a leaf, return the union of the low | ||
| * and high branches (themselves also as arrays). | ||
| * | ||
| * @return {Array} All of the contacts in the tree, as an array | ||
| */ | ||
| toArray () { | ||
| let result = [] | ||
| for (const nodes = [ this.root ]; nodes.length > 0;) { | ||
| const node = nodes.pop() | ||
| if (node.contacts === null) nodes.push(node.right, node.left) | ||
| else result = result.concat(node.contacts) | ||
| } | ||
| return result | ||
| } | ||
| var incumbent = node.contacts[index] | ||
| var selection = this.arbiter(incumbent, contact) | ||
| // if the selection is our old contact and the candidate is some new | ||
| // contact, then there is nothing to do | ||
| if (selection === incumbent && incumbent !== contact) return | ||
| /** | ||
| * Updates the contact selected by the arbiter. | ||
| * If the selection is our old contact and the candidate is some new contact | ||
| * then the new contact is abandoned (not added). | ||
| * If the selection is our old contact and the candidate is our old contact | ||
| * then we are refreshing the contact and it is marked as most recently | ||
| * contacted (by being moved to the right/end of the bucket array). | ||
| * If the selection is our new contact, the old contact is removed and the new | ||
| * contact is marked as most recently contacted. | ||
| * | ||
| * @param {Object} node internal object that has 2 leafs: left and right | ||
| * @param {Number} index the index in the bucket where contact exists | ||
| * (index has already been computed in a previous | ||
| * calculation) | ||
| * @param {Object} contact The contact object to update. | ||
| */ | ||
| _update (node, index, contact) { | ||
| // sanity check | ||
| if (!arrayEquals(node.contacts[index].id, contact.id)) { | ||
| throw new Error('wrong index for _update') | ||
| } | ||
| node.contacts.splice(index, 1) // remove old contact | ||
| node.contacts.push(selection) // add more recent contact version | ||
| this.emit('updated', incumbent, selection) | ||
| const incumbent = node.contacts[index] | ||
| const selection = this.arbiter(incumbent, contact) | ||
| // if the selection is our old contact and the candidate is some new | ||
| // contact, then there is nothing to do | ||
| if (selection === incumbent && incumbent !== contact) return | ||
| node.contacts.splice(index, 1) // remove old contact | ||
| node.contacts.push(selection) // add more recent contact version | ||
| this.emit('updated', incumbent, selection) | ||
| } | ||
| } | ||
| module.exports = KBucket |
| { | ||
| "name": "k-bucket", | ||
| "version": "4.0.1", | ||
| "version": "5.0.0", | ||
| "description": "Kademlia DHT K-bucket implementation as a binary tree", | ||
@@ -23,3 +23,4 @@ "keywords": [ | ||
| "Robert Kowalski <rok@kowalski.gd>", | ||
| "Nazar Mokrynskyi <nazar@mokrynskyi.com>" | ||
| "Nazar Mokrynskyi <nazar@mokrynskyi.com>", | ||
| "Jimmy Wärting <jimmy@warting.se>" | ||
| ], | ||
@@ -41,3 +42,2 @@ "main": "./index.js", | ||
| "dependencies": { | ||
| "inherits": "^2.0.1", | ||
| "randombytes": "^2.0.3" | ||
@@ -44,0 +44,0 @@ }, |
@@ -11,3 +11,3 @@ # k-bucket | ||
| [@tristanls](https://github.com/tristanls), [@mikedeboer](https://github.com/mikedeboer), [@deoxxa](https://github.com/deoxxa), [@feross](https://github.com/feross), [@nathanph](https://github.com/nathanph), [@allouis](https://github.com/allouis), [@fanatid](https://github.com/fanatid), [@robertkowalski](https://github.com/robertkowalski), [@nazar-pc](https://github.com/nazar-pc) | ||
| [@tristanls](https://github.com/tristanls), [@mikedeboer](https://github.com/mikedeboer), [@deoxxa](https://github.com/deoxxa), [@feross](https://github.com/feross), [@nathanph](https://github.com/nathanph), [@allouis](https://github.com/allouis), [@fanatid](https://github.com/fanatid), [@robertkowalski](https://github.com/robertkowalski), [@nazar-pc](https://github.com/nazar-pc), [@jimmywarting](https://github.com/jimmywarting) | ||
@@ -25,16 +25,15 @@ ## Installation | ||
| ```javascript | ||
| var KBucket = require('k-bucket'); | ||
| const KBucket = require('k-bucket') | ||
| var kBucket1 = new KBucket({ | ||
| localNodeId: Buffer.from("my node id") // default: random data | ||
| const kBucket1 = new KBucket({ | ||
| localNodeId: Buffer.from('my node id') // default: random data | ||
| }) | ||
| // or without using Buffer (for example, in the browser) | ||
| var id = "my node id"; | ||
| var nodeId = new Uint8Array(id.length); | ||
| for (var i = 0, len = nodeId.length; i < len; ++i) | ||
| { | ||
| nodeId[i] = id.charCodeAt(i); | ||
| const id = 'my node id' | ||
| const nodeId = new Uint8Array(id.length) | ||
| for (let i = 0, len = nodeId.length; i < len; ++i) { | ||
| nodeId[i] = id.charCodeAt(i) | ||
| } | ||
| var kBucket2 = new KBucket({ | ||
| localNodeId: nodeId // default: random data | ||
| const kBucket2 = new KBucket({ | ||
| localNodeId: nodeId // default: random data | ||
| }) | ||
@@ -76,3 +75,3 @@ ``` | ||
| // contact example | ||
| var contact = { | ||
| const contact = { | ||
| id: Buffer.from('workerService'), | ||
@@ -88,12 +87,12 @@ workerNodes: { | ||
| // the incumbent | ||
| var merged = { | ||
| const merged = { | ||
| id: incumbent.id, // incumbent.id === candidate.id within an arbiter | ||
| workerNodes: incumbent.workerNodes | ||
| }; | ||
| } | ||
| Object.keys(candidate.workerNodes).forEach(function (workerNodeId) { | ||
| Object.keys(candidate.workerNodes).forEach(workerNodeId => { | ||
| merged.workerNodes[workerNodeId] = candidate.workerNodes[workerNodeId]; | ||
| }); | ||
| }) | ||
| return merged; | ||
| return merged | ||
| } | ||
@@ -301,2 +300,1 @@ ``` | ||
| - [Distributed Hash Tables (part 2)](https://web.archive.org/web/20140217064545/http://offthelip.org/?p=157) | ||
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by3.73%
57151
- Dependency count
- decreased by-50%
1
- Lines of code
- increased by8.24%
1025
Worsened metrics
- Number of lines in readme file
- decreased by-0.67%
296
Dependency changes
- Removedinherits@^2.0.1
- Removedinherits@2.0.4(transitive)