Comparing version 0.1.1 to 0.2.0
38
index.js
@@ -51,3 +51,3 @@ /* | ||
if (!(self.localNodeId instanceof Buffer)) { | ||
self.localNodeId = new Buffer(self.localNodeId); | ||
self.localNodeId = new Buffer(self.localNodeId, 'base64'); | ||
} | ||
@@ -64,2 +64,18 @@ self.root = options.root || self; | ||
KBucket.distance = function distance (firstId, secondId) { | ||
var max = Math.max(firstId.length, secondId.length); | ||
var accumulator = ''; | ||
for (var i = 0; i < max; i++) { | ||
var maxDistance = false; | ||
if (firstId[i] === undefined) maxDistance = true; | ||
if (secondId[i] === undefined) maxDistance = true; | ||
if (maxDistance) { | ||
accumulator += (255).toString(16); | ||
} else { | ||
accumulator += (firstId[i] ^ secondId[i]).toString(16); | ||
} | ||
} | ||
return parseInt(accumulator, 16); | ||
}; | ||
// contact: *required* the contact object to add | ||
@@ -137,3 +153,3 @@ // bitIndex: the bitIndex to which bit to check in the Buffer for navigating | ||
contacts.forEach(function (storedContact) { | ||
storedContact.distance = self.distance(storedContact.id, contact.id); | ||
storedContact.distance = KBucket.distance(storedContact.id, contact.id); | ||
}); | ||
@@ -185,20 +201,2 @@ | ||
KBucket.prototype.distance = function distance (firstId, secondId) { | ||
var self = this; | ||
var max = Math.max(firstId.length, secondId.length); | ||
var accumulator = ''; | ||
for (var i = 0; i < max; i++) { | ||
var maxDistance = false; | ||
if (firstId[i] === undefined) maxDistance = true; | ||
if (secondId[i] === undefined) maxDistance = true; | ||
if (maxDistance) { | ||
accumulator += (255).toString(16); | ||
} else { | ||
accumulator += (firstId[i] ^ secondId[i]).toString(16); | ||
} | ||
} | ||
return parseInt(accumulator, 16); | ||
}; | ||
// Returns the index of the contact if it exists | ||
@@ -205,0 +203,0 @@ // **NOTE**: indexOf() does not compare vectorClock |
{ | ||
"name": "k-bucket", | ||
"version": "0.1.1", | ||
"description": "Kademlia DHT K-bucket implementation as a binary tree", | ||
"scripts": { | ||
"test": "node scripts/test.js" | ||
}, | ||
"main": "index.js", | ||
"dependencies": { | ||
"buffertools": "1.1.1" | ||
}, | ||
"devDependencies": { | ||
"nodeunit": "0.8.1" | ||
}, | ||
"repository": { | ||
"type": "git", | ||
"url": "git@github.com:tristanls/node-k-bucket.git" | ||
}, | ||
"keywords": [ | ||
"k-bucket", | ||
"kademlia", | ||
"dht" | ||
], | ||
"author": "Tristan Slominski <tristan.slominski@gmail.com>", | ||
"license": "MIT" | ||
"name": "k-bucket", | ||
"version": "0.2.0", | ||
"description": "Kademlia DHT K-bucket implementation as a binary tree", | ||
"scripts": { | ||
"test": "node scripts/test.js" | ||
}, | ||
"main": "index.js", | ||
"dependencies": { | ||
"buffertools": "1.1.1" | ||
}, | ||
"devDependencies": { | ||
"nodeunit": "0.8.1" | ||
}, | ||
"repository": { | ||
"type": "git", | ||
"url": "git@github.com:tristanls/node-k-bucket.git" | ||
}, | ||
"keywords": [ | ||
"k-bucket", | ||
"kademlia", | ||
"dht" | ||
], | ||
"author": "Tristan Slominski <tristan.slominski@gmail.com>", | ||
"license": "MIT" | ||
} |
@@ -21,4 +21,3 @@ # k-bucket | ||
var kBucket = new KBucket({ | ||
localNodeId: "my node id", /* default: random SHA-1 */ | ||
root: kBucket /* default: self (for internal implementation use) */ | ||
localNodeId: new Buffer("my node id") // default: random SHA-1 | ||
}); | ||
@@ -49,77 +48,93 @@ ``` | ||
#### KBucket.distance(firstId, secondId) | ||
* `firstId`: _Buffer_ | ||
* `secondId`: _Buffer_ | ||
* Return: _Integer_ | ||
Finds the XOR distance between firstId and secondId. | ||
#### new KBucket(options) | ||
Creates a new KBucket. The `options` are: | ||
* `options`: | ||
* `localNodeId`: _String (base64)_ or _Buffer_ An optional String or a Buffer representing the local node id. If not provided, a local node id will be created via `crypto.createHash('sha1').digest()`. If a String is provided, it will be assumed to be base64 encoded and will be converted into a Buffer. | ||
* `root`: _Object_ _(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 | ||
* `localNodeId`: An optional string or a Buffer representing the local node id. If not provided, a local node id will be created via `crypto.createHash('sha1').digest()`. If a string is provided, it will be converted into a Buffer. | ||
* `root`: _(reserved for internal use)_ provides a reference for to the root of the tree data structure as the k-bucket splits as new contacts are added | ||
Creates a new KBucket. | ||
#### kBucket.add(contact, [bitIndex]) | ||
* `contact` Object | ||
* `bitIndex` Integer, Optional, Default: 0 | ||
* Return: Object | ||
* `contact`: _Object_ | ||
* `id`: _Buffer_ contact node id | ||
* Any satellite data can be part of the `contact` object, only `id` is used | ||
* `bitIndex`: _Integer_ _(Default: 0)_ | ||
* Return: _Object_ | ||
Adds a contact to the k-bucket. | ||
Adds a `contact` to the k-bucket. | ||
#### kBucket.closest(contact, n, [bitIndex]) | ||
* `contact` Object | ||
* `n` Integer | ||
* `bitIndex` Integer, Optional, Default: 0 | ||
* Return: Array | ||
* `contact`: _Object_ | ||
* `id`: _Buffer_ contact node id | ||
* Any satellite data can be part of the `contact` object, only `id` is used | ||
* `n`: _Integer_ | ||
* `bitIndex`: _Integer_ _(Default: 0)_ | ||
* Return: _Array_ | ||
Get the n closest contacts to the provided contact. "Closest" here means: closest according to the XOR metric of the contact node id. | ||
Get the `n` closest contacts to the provided `contact`. "Closest" here means: closest according to the XOR metric of the `contact` node id. | ||
#### kBucket.determineBucket(id, [bitIndex]) | ||
* `id` Buffer | ||
* `bitIndex` Integer | ||
* Return: Integer | ||
* `id`: _Buffer_ | ||
* `bitIndex`: _Integer_ _(Default: 0)_ | ||
* Return: _Integer_ | ||
_reserved for internal use_ Determines whether the id at the bitIndex is 0 or 1. If 0, returns -1, else 1. Id is a Buffer. | ||
_reserved for internal use_ | ||
#### kBucket.distance(firstId, secondId) | ||
Determines whether the `id` at the `bitIndex` is 0 or 1. If 0, returns -1, else 1. | ||
* `firstId` Buffer | ||
* `secondId` Buffer | ||
* Return: Integer | ||
Finds the XOR distance between firstId and secondId. | ||
#### kBucket.indexOf(contact) | ||
* `contact` Object | ||
* Return: Integer | ||
* `contact`: _Object_ | ||
* Return: _Integer_ | ||
Returns the index of the contact if it exists, returns -1 otherwise. | ||
Returns the index of the `contact` if it exists, returns -1 otherwise. | ||
#### kBucket.remove(contact, [bitIndex]) | ||
* `contact` Object | ||
* `bitIndex` Integer, Optional, Default: 0 | ||
* Return: Object | ||
* `contact`: _Object_ | ||
* `id`: _Buffer_ contact node id | ||
* Any satellite data can be part of the `contact` object, only `id` is used | ||
* `bitIndex`: _Integer_ _(Default: 0)_ | ||
* Return: _Object_ | ||
Removes the contact. | ||
Removes the `contact`. | ||
#### kBucket.splitAndAdd(contact, [bitIndex]) | ||
* `contact` Object | ||
* `bitIndex` Integer, Optional, Default: 0 | ||
* Return: Object | ||
* `contact`: _Object_ | ||
* `id`: _Buffer_ contact node id | ||
* Any satellite data can be part of the `contact` object, only `id` is used | ||
* `bitIndex`: _Integer_ _(Default: 0)_ | ||
* Return: _Object_ | ||
_reserved for internal use_ 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`. | ||
_reserved for internal use_ | ||
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`. | ||
#### kBucket.update(contact, index) | ||
* `contact` Object | ||
* `index` Integer | ||
* Return: void | ||
* `contact`: _Object_ | ||
* `id`: _Buffer_ contact node id | ||
* Any satellite data can be part of the `contact` object, only `id` is used | ||
* `index`: _Integer_ | ||
_reserved for internal use_ Updates the contact and compares the vector clocks if provided. If new contact vector clock is deprecated, contact is abandoned (not added). If new contact vector clock is the same, contact is marked as moste recently contacted (by being moved to the right/end of the bucket array). If new contact vector clock is more recent, the old contact is removed and the new contact is marked as most recently contacted. | ||
_reserved for internal use_ | ||
Updates the `contact` and compares the vector clocks if provided. If new `contact` vector clock is deprecated, `contact` is abandoned (not added). If new `contact` vector clock is the same, `contact` is marked as moste recently contacted (by being moved to the right/end of the bucket array). If new `contact` vector clock is more recent, the old `contact` is removed and the new contact is marked as most recently contacted. | ||
#### Event: 'ping' | ||
* `oldContacts` _Array_ The array of contacts to ping | ||
* `newContact` _Object_ The new contact to be added if one of old contacts does not respond | ||
* `oldContacts`: _Array_ The array of contacts to ping | ||
* `newContact`: _Object_ The new contact to be added if one of old contacts does not respond | ||
@@ -126,0 +141,0 @@ Emitted every time a contact is added that would exceed the capacity of a _don't split_ k-bucket it belongs to. |
@@ -37,2 +37,31 @@ "use strict"; | ||
test['closest nodes are returned (including exact match)'] = function (test) { | ||
test.expect(3); | ||
var kBucket = new KBucket(); | ||
kBucket.add({id: new Buffer('00', 'hex')}); // 00000000 | ||
kBucket.add({id: new Buffer('01', 'hex')}); // 00000001 | ||
kBucket.add({id: new Buffer('02', 'hex')}); // 00000010 | ||
kBucket.add({id: new Buffer('03', 'hex')}); // 00000011 | ||
kBucket.add({id: new Buffer('04', 'hex')}); // 00000100 | ||
kBucket.add({id: new Buffer('05', 'hex')}); // 00000101 | ||
kBucket.add({id: new Buffer('06', 'hex')}); // 00000110 | ||
kBucket.add({id: new Buffer('07', 'hex')}); // 00000111 | ||
kBucket.add({id: new Buffer('08', 'hex')}); // 00001000 | ||
kBucket.add({id: new Buffer('09', 'hex')}); // 00001001 | ||
kBucket.add({id: new Buffer('0a', 'hex')}); // 00001010 | ||
kBucket.add({id: new Buffer('0b', 'hex')}); // 00001011 | ||
kBucket.add({id: new Buffer('0c', 'hex')}); // 00001100 | ||
kBucket.add({id: new Buffer('0d', 'hex')}); // 00001101 | ||
kBucket.add({id: new Buffer('0e', 'hex')}); // 00001110 | ||
kBucket.add({id: new Buffer('0f', 'hex')}); // 00001111 | ||
kBucket.add({id: new Buffer('10', 'hex')}); // 00010000 | ||
kBucket.add({id: new Buffer('11', 'hex')}); // 00010001 | ||
var contact = {id: new Buffer('11', 'hex')};// 00010001 | ||
var contacts = kBucket.closest(contact, 3); | ||
test.deepEqual(contacts[0].id, new Buffer('11', 'hex')); // distance: 00000000 | ||
test.deepEqual(contacts[1].id, new Buffer('10', 'hex')); // distance: 00000001 | ||
test.deepEqual(contacts[2].id, new Buffer('01', 'hex')); // distance: 00010000 | ||
test.done(); | ||
}; | ||
test['closest nodes are returned even if there isn\'t enough in one bucket'] = function (test) { | ||
@@ -39,0 +68,0 @@ test.expect(22); |
@@ -29,3 +29,3 @@ "use strict"; | ||
test.ok(kBucket.localNodeId instanceof Buffer); | ||
test.deepEqual(kBucket.localNodeId, new Buffer("some identifier")); | ||
test.deepEqual(kBucket.localNodeId, new Buffer("some identifier", 'base64')); | ||
test.done(); | ||
@@ -32,0 +32,0 @@ }; |
@@ -10,5 +10,4 @@ "use strict"; | ||
test.expect(1); | ||
var kBucket = new KBucket(); | ||
test.equal( | ||
kBucket.distance(new Buffer('00', 'hex'), new Buffer('00', 'hex')), | ||
KBucket.distance(new Buffer('00', 'hex'), new Buffer('00', 'hex')), | ||
0); | ||
@@ -20,5 +19,4 @@ test.done(); | ||
test.expect(1); | ||
var kBucket = new KBucket(); | ||
test.equal( | ||
kBucket.distance(new Buffer('00', 'hex'), new Buffer('01', 'hex')), | ||
KBucket.distance(new Buffer('00', 'hex'), new Buffer('01', 'hex')), | ||
1); | ||
@@ -30,5 +28,4 @@ test.done(); | ||
test.expect(1); | ||
var kBucket = new KBucket(); | ||
test.equal( | ||
kBucket.distance(new Buffer('02', 'hex'), new Buffer('01', 'hex')), | ||
KBucket.distance(new Buffer('02', 'hex'), new Buffer('01', 'hex')), | ||
3); | ||
@@ -40,5 +37,4 @@ test.done(); | ||
test.expect(1); | ||
var kBucket = new KBucket(); | ||
test.equal( | ||
kBucket.distance(new Buffer('00', 'hex'), new Buffer('0000', 'hex')), | ||
KBucket.distance(new Buffer('00', 'hex'), new Buffer('0000', 'hex')), | ||
255); | ||
@@ -50,7 +46,6 @@ test.done(); | ||
test.expect(1); | ||
var kBucket = new KBucket(); | ||
test.equal( | ||
kBucket.distance(new Buffer('0124', 'hex'), new Buffer('4024', 'hex')), | ||
KBucket.distance(new Buffer('0124', 'hex'), new Buffer('4024', 'hex')), | ||
1040); | ||
test.done(); | ||
}; |
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
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
39890
709
146