RootingTableを実装してみよう
    KIdを実装する
    kBucketを実装する
    RootingTableを実装する
RootingTableを実装してみましょう。コードに落とす事で理解も深まります。

KIDを実装する。

InfoHashもPeerIDもKIDとして表せる。

InfoHash と InfoHash、Peer IDとInfoHash Peer ID とPeer ID のXOR距離を計算する必要があるのでした。これらのIDは、すべて20バイトのデータであり同じものとして定義できます。本文ではKIDと呼ぶことにします。
XORでは160bitの値を扱う必要があります。しかし、Dart言語では160bitに対応する 数値を持っていません。53bitまでしか使えません。これは、Dart言語の問題というわけではなく、ほとんどの言語で、160bitの値を扱うことができません。
- XOR距離を数値に直す機能はなくても良い
本書では160bitの数値を定義しないで実装する方法で進めます。 実際に実装してみるとわかるのですが、XOR距離を求める必要はありません。RootingTable上のどの位置に格納されるのかという情報と、大小比較する機能が必要になります。
作成していきましょう。まずは、最初の定義、KID は、20byteのデータを持つ事とする。
1
class KId {
2
List<int> _values = null;
3
List<int> get value => new List.from(_values);
4
KId(List<int> id) {
5
if(id == null || id.length != 20) {
6
throw {};
7
}
8
this._values = new Uint8List.fromList(id);
9
}
10
int get length => _values.length;
11
int operator [](int idx) => _values[idx];
12
Iterator<int> get iterator => _values.iterator;
13
}
Copied!

XOR の計算機能を追加する

KIdはXOR距離が計算できる必要があります。数値としては表現する事は諦めましたが、計算した結果はKIDとして返す機能は必要です。バイト配列の各値ごとに xorをとる事で実現できます。
1
class KId {
2
...
3
...
4
...
5
KId xor(KId b, [KId output = null]) {
6
if (output == null) {
7
output = new KId.zeroClear();
8
}
9
for (int i = 0; i < b._values.length; i++) {
10
output._values[i] = this._values[i] ^ b._values[i];
11
}
12
return output;
13
}
14
}
Copied!

大小比較の機能を追加する

大小比較の機能を追加します。この機能を追加する事により、ソートが可能になります。 ソートができるようになると、あるKIDに近い値順に一覧を出すとかできるようになります。 まさに、これから作成しようとしている、InfoHashに近い値を持つPeer一覧を返す機能そのものです。
1
class KId {
2
...
3
...
4
...
5
bool operator >(KId b) {
6
for (int i = 0; i < b._values.length; i++) {
7
if (this._values[i] == b._values[i]) {
8
continue;
9
} else if (this._values[i] > b._values[i]) {
10
return true;
11
} else {
12
return false;
13
}
14
}
15
return false;
16
}
17
18
bool operator ==(KId b) {
19
for (int i = 0; i < b._values.length; i++) {
20
if (this._values[i] != b._values[i]) {
21
return false;
22
}
23
}
24
return true;
25
}
26
27
bool operator >=(KId b) {
28
return (this == b ? true : (this > b ? true : false));
29
}
30
31
bool operator <(KId b) {
32
return (this == b ? false : !(this > b));
33
}
34
35
bool operator <=(KId b) {
36
return (this == b ? true : (this > b ? false : true));
37
}
Copied!
以上でKIDの作成は完了です。事の顛末を知りたい方は、以下を参照してください。 https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht
実装作業は、必ずテストを書きながら、動作確認しながら、進めてください。

kBucketを実装する。

kBucketは、K個のPeetについての情報を格納する入れ物です。これは、値を追加する時に制限をもたせたListとして表現できますね。
今回の実装ではkBucketが満杯になった場合は古いデータから削除するようにしています。 このあたりは、実際に動作させてみて最適な方法を試行錯誤すべきでしょう。
1
class KBucket {
2
int _k = 8;
3
int get k => _k;
4
List<KPeerInfo> peerInfos = null;
5
6
KBucket(int kBucketSize) {
7
this._k = kBucketSize;
8
this.peerInfos = [];
9
}
10
11
add(KPeerInfo peerInfo) {
12
if (peerInfos.contains(peerInfo) == true) {
13
peerInfos.remove(peerInfo);
14
}
15
peerInfos.add(peerInfo);
16
if (peerInfos.length > k) {
17
peerInfos.removeAt(0);
18
}
19
}
20
21
int get length => peerInfos.length;
22
KPeerInfo operator [](int idx) => peerInfos[idx];
23
Iterator<KPeerInfo> get iterator => peerInfos.iterator;
24
}
Copied!
以上でkBucketの作成は完了です。事の顛末を知りたい方は、以下を参照してください。 https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht

RootingTableを実装する

前章で説明したとおり、RootingTableは、0〜160までの161個のkBucketを保持する事ができるのでした。 まずは、最初の定義、kBucketを161個保持することができる。
1
class KRootingTable {
2
List<KBucket> _kBuckets = [];
3
int _kBucketSize = 0;
4
5
KRootingTable(int k_bucketSize) {
6
this._kBucketSize = k_bucketSize;
7
for (int i = 0; i < 161; i++) {
8
_kBuckets.add(new KBucket(k_bucketSize));
9
}
10
}
11
}
Copied!

KIdに値に応じて、追加するxBucketを決める機能を追加する

RootingTableを所持しているPeerとのXORを計算してもその値をもとに、どのxBucketに追加するかを決めます。
2進
index
0
000
0
1
001
1
2, 3
010, 011
2
4, 5, 6, 7
100, 101, 110, 111
3
実際に表に落としてみると、左から右へ1bitずつ確認していって、最初に1であった場所によって、kBucket位置が決まる事がわかります。
これをコードに落としましょう。
1
class KRootingTable {
2
List<KBucket> _kBuckets = [];
3
int _kBucketSize = 0;
4
KId _ownerKId = null;
5
KId get ownerKId => _ownerKId;
6
7
KRootingTable(int k_bucketSize, KId ownerKId) {
8
this._kBucketSize = k_bucketSize;
9
for (int i = 0; i < 161; i++) {
10
_kBuckets.add(new KBucket(k_bucketSize));
11
}
12
this._ownerKId = ownerKId;
13
}
14
15
int getRootingTabkeIndex(KId v) {
16
// xor距離を計算する
17
v = v.xor(_ownerKId);
18
19
// 対応するkBucketを探す。
20
for (int i = 0, ret = 19; i < 20; i++, ret--) {
21
if (v[i] != 0) {
22
for (int j = 0; j < 9; j++) {
23
if (v[i] < (0x1 << j)) {
24
return (ret * 8) + j;
25
}
26
}
27
return i;
28
}
29
}
30
return 0;
31
}
32
}
Copied!

Peerの情報が渡されたら、対応するkBucketに追加する

いままで、作成した機能を合わせる事で、RootingTableを更新できるようになります。
1
class KRootingTable {
2
...
3
...
4
...
5
Future update(KPeerInfo info) {
6
return new Future(() {
7
_kBuckets[getRootingTabkeIndex(info.id)].add(info);
8
});
9
}
10
...
11
...
12
}
Copied!
これで、RootingTableの作成は完了です。次の章の説明を得て、findNodeメソッドが追加されます。しかし、今までに解説した内容で実装できるのはここまでとなります。
Kyorohiro work
Last modified 3yr ago