# 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のデータを持つ事とする。

```dart
class KId {
  List<int> _values = null;
  List<int> get value => new List.from(_values);
  KId(List<int> id) {
    if(id == null || id.length != 20) {
      throw {};
    }
    this._values = new Uint8List.fromList(id);
  }
  int get length => _values.length;
  int operator [](int idx) => _values[idx];
  Iterator<int> get iterator => _values.iterator;
}
```

#### XOR の計算機能を追加する

KIdはXOR距離が計算できる必要があります。数値としては表現する事は諦めましたが、計算した結果はKIDとして返す機能は必要です。バイト配列の各値ごとに xorをとる事で実現できます。

```dart
class KId {
  ...
  ...
  ...
  KId xor(KId b, [KId output = null]) {
    if (output == null) {
      output = new KId.zeroClear();
    }
    for (int i = 0; i < b._values.length; i++) {
      output._values[i] = this._values[i] ^ b._values[i];
    }
    return output;
  }
}
```

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

大小比較の機能を追加します。この機能を追加する事により、ソートが可能になります。 ソートができるようになると、あるKIDに近い値順に一覧を出すとかできるようになります。 まさに、これから作成しようとしている、InfoHashに近い値を持つPeer一覧を返す機能そのものです。

```dart
class KId {
  ...
  ...
  ...
  bool operator >(KId b) {
    for (int i = 0; i < b._values.length; i++) {
      if (this._values[i] == b._values[i]) {
        continue;
      } else if (this._values[i] > b._values[i]) {
        return true;
      } else {
        return false;
      }
    }
    return false;
  }

  bool operator ==(KId b) {
    for (int i = 0; i < b._values.length; i++) {
      if (this._values[i] != b._values[i]) {
        return false;
      }
    }
    return true;
  }

  bool operator >=(KId b) {
    return (this == b ? true : (this > b ? true : false));
  }

  bool operator <(KId b) {
    return (this == b ? false : !(this > b));
  }

  bool operator <=(KId b) {
    return (this == b ? true : (this > b ? false : true));
  }
```

以上でKIDの作成は完了です。事の顛末を知りたい方は、以下を参照してください。 <https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht>

実装作業は、必ずテストを書きながら、動作確認しながら、進めてください。

## kBucketを実装する。

kBucketは、K個のPeetについての情報を格納する入れ物です。これは、値を追加する時に制限をもたせたListとして表現できますね。

今回の実装ではkBucketが満杯になった場合は古いデータから削除するようにしています。 このあたりは、実際に動作させてみて最適な方法を試行錯誤すべきでしょう。

```dart
class KBucket {
  int _k = 8;
  int get k => _k;
  List<KPeerInfo> peerInfos = null;

  KBucket(int kBucketSize) {
    this._k = kBucketSize;
    this.peerInfos = [];
  }

  add(KPeerInfo peerInfo) {
    if (peerInfos.contains(peerInfo) == true) {
      peerInfos.remove(peerInfo);
    }
    peerInfos.add(peerInfo);
    if (peerInfos.length > k) {
      peerInfos.removeAt(0);
    }
  }

  int get length => peerInfos.length;
  KPeerInfo operator [](int idx) => peerInfos[idx];
  Iterator<KPeerInfo> get iterator => peerInfos.iterator;
}
```

以上でkBucketの作成は完了です。事の顛末を知りたい方は、以下を参照してください。 <https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht>

## RootingTableを実装する

前章で説明したとおり、RootingTableは、0〜160までの161個のkBucketを保持する事ができるのでした。 まずは、最初の定義、kBucketを161個保持することができる。

```dart
class KRootingTable {
  List<KBucket> _kBuckets = [];
  int _kBucketSize = 0;

  KRootingTable(int k_bucketSize) {
    this._kBucketSize = k_bucketSize;
    for (int i = 0; i < 161; i++) {
      _kBuckets.add(new KBucket(k_bucketSize));
    }
  }
}
```

#### 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位置が決まる事がわかります。

これをコードに落としましょう。

```dart
class KRootingTable {
  List<KBucket> _kBuckets = [];
  int _kBucketSize = 0;
  KId _ownerKId = null;
  KId get ownerKId => _ownerKId;

  KRootingTable(int k_bucketSize, KId ownerKId) {
    this._kBucketSize = k_bucketSize;
    for (int i = 0; i < 161; i++) {
      _kBuckets.add(new KBucket(k_bucketSize));
    }
    this._ownerKId = ownerKId;
  }

  int getRootingTabkeIndex(KId v) {
    // xor距離を計算する
    v = v.xor(_ownerKId);

    // 対応するkBucketを探す。
    for (int i = 0, ret = 19; i < 20; i++, ret--) {
      if (v[i] != 0) {
        for (int j = 0; j < 9; j++) {
          if (v[i] < (0x1 << j)) {
            return (ret * 8) + j;
          }
        }
        return i;
      }
    }
    return 0;
  }
}
```

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

いままで、作成した機能を合わせる事で、RootingTableを更新できるようになります。

```
class KRootingTable {
  ...
  ...
  ...
  Future update(KPeerInfo info) {
    return new Future(() {
      _kBuckets[getRootingTabkeIndex(info.id)].add(info);
    });
  }
  ...
  ...
}
```

これで、RootingTableの作成は完了です。次の章の説明を得て、findNodeメソッドが追加されます。しかし、今までに解説した内容で実装できるのはここまでとなります。

Kyorohiro work

<http://kyorohiro.strikingly.com>