summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ChangeLog14
-rw-r--r--src/BNode.cc206
-rw-r--r--src/BNode.h107
-rw-r--r--src/DHTBucketTree.cc233
-rw-r--r--src/DHTBucketTree.h119
-rw-r--r--src/DHTRoutingTable.cc43
-rw-r--r--src/DHTRoutingTable.h4
-rw-r--r--src/Makefile.am2
-rw-r--r--src/Makefile.in46
-rw-r--r--test/DHTBucketTreeTest.cc (renamed from test/BNodeTest.cc)186
-rw-r--r--test/Makefile.am2
-rw-r--r--test/Makefile.in8
12 files changed, 496 insertions, 474 deletions
diff --git a/ChangeLog b/ChangeLog
index 2b42b9f3..ace54b5e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2010-11-18 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>
+
+ Replaced BNode with DHTBucketTreeNode which is 2 times efficient.
+ * src/BNode.cc: Removed
+ * src/BNode.h: Removed
+ * src/DHTBucketTree.cc
+ * src/DHTBucketTree.h
+ * src/DHTRoutingTable.cc
+ * src/DHTRoutingTable.h
+ * src/Makefile.am
+ * test/BNodeTest.cc: Removed
+ * test/DHTBucketTreeTest.cc
+ * test/Makefile.am
+
2010-11-15 Tatsuhiro Tsujikawa <t-tujikawa@users.sourceforge.net>
Added non-member swap() for SharedHandle.
diff --git a/src/BNode.cc b/src/BNode.cc
deleted file mode 100644
index 71c849ee..00000000
--- a/src/BNode.cc
+++ /dev/null
@@ -1,206 +0,0 @@
-/* <!-- copyright */
-/*
- * aria2 - The high speed download utility
- *
- * Copyright (C) 2006 Tatsuhiro Tsujikawa
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
- *
- * In addition, as a special exception, the copyright holders give
- * permission to link the code of portions of this program with the
- * OpenSSL library under certain conditions as described in each
- * individual source file, and distribute linked combinations
- * including the two.
- * You must obey the GNU General Public License in all respects
- * for all of the code used other than OpenSSL. If you modify
- * file(s) with this exception, you may extend this exception to your
- * version of the file(s), but you are not obligated to do so. If you
- * do not wish to do so, delete this exception statement from your
- * version. If you delete this exception statement from all source
- * files in the program, then also delete it here.
- */
-/* copyright --> */
-#include "BNode.h"
-
-#include <functional>
-#include <algorithm>
-
-#include "DHTBucket.h"
-#include "DHTNode.h"
-
-namespace aria2 {
-
-BNode::BNode(const SharedHandle<DHTBucket>& bucket):
- bucket_(bucket),
- up_(0),
- left_(0),
- right_(0) {}
-
-BNode::~BNode()
-{
- delete left_;
- delete right_;
-}
-
-void BNode::setLeft(BNode* left)
-{
- left_ = left;
- left_->up_ = this;
-}
-
-void BNode::setRight(BNode* right)
-{
- right_ = right;
- right_->up_ = this;
-}
-
-void BNode::setUp(BNode* up)
-{
- up_ = up;
-}
-
-void BNode::setBucket(const SharedHandle<DHTBucket>& bucket)
-{
- bucket_ = bucket;
-}
-
-bool BNode::isInRange(const unsigned char* key) const
-{
- if(!bucket_) {
- return left_->isInRange(key) || right_->isInRange(key);
- } else {
- return bucket_->isInRange(key);
- }
-}
-
-BNode* BNode::findBNodeFor(BNode* b, const unsigned char* key)
-{
- if(!b->isInRange(key)) {
- return 0;
- }
- while(1) {
- if(b->getBucket()) {
- return b;
- }
- // we assume key fits in either left or right bucket range.
- if(b->getLeft()->isInRange(key)) {
- b = b->getLeft();
- } else {
- b = b->getRight();
- }
- }
- // for properly configured BNode tree, here is unreachable.
- return 0;
-}
-
-SharedHandle<DHTBucket> BNode::findBucketFor(BNode* b, const unsigned char* key)
-{
- BNode* bnode = findBNodeFor(b, key);
- if(bnode) {
- return bnode->getBucket();
- } else {
- return SharedHandle<DHTBucket>();
- }
-}
-
-
-void BNode::findClosestKNodes(std::vector<SharedHandle<DHTNode> >& nodes,
- BNode* b, const unsigned char* key)
-{
- BNode* bnode = findBNodeFor(b, key);
- if(!bnode) {
- return;
- }
- {
- SharedHandle<DHTBucket> bucket = bnode->getBucket();
- bucket->getGoodNodes(nodes);
- }
- if(nodes.size() >= DHTBucket::K) {
- return;
- }
- std::vector<const BNode*> visited;
- visited.push_back(bnode);
-
- BNode* up = bnode->getUp();
- if(!up) {
- return;
- }
- bool leftFirst = false;
- if(up->getLeft() == bnode) {
- leftFirst = true;
- }
- bnode = up;
-
- std::const_mem_fun_t<BNode*, BNode> firstfunc = leftFirst?std::mem_fun(&BNode::getLeft):std::mem_fun(&BNode::getRight);
- std::const_mem_fun_t<BNode*, BNode> secondfunc = leftFirst?std::mem_fun(&BNode::getRight):std::mem_fun(&BNode::getLeft);
- while(nodes.size() < DHTBucket::K) {
-
- if(!bnode->getLeft() && !bnode->getRight()) {
- bnode = bnode->getUp();
- } else {
- if(std::find(visited.begin(), visited.end(), firstfunc(bnode)) == visited.end()) {
- bnode = firstfunc(bnode);
- } else if(std::find(visited.begin(), visited.end(), secondfunc(bnode)) == visited.end()) {
- bnode = secondfunc(bnode);
- } else {
- bnode = bnode->getUp();
- }
- }
- if(!bnode) {
- break;
- }
- visited.push_back(bnode);
- {
- SharedHandle<DHTBucket> bucket = bnode->getBucket();
- if(bucket) {
- std::vector<SharedHandle<DHTNode> > goodNodes;
- bucket->getGoodNodes(goodNodes);
- size_t r = DHTBucket::K-nodes.size();
- if(goodNodes.size() <= r) {
- nodes.insert(nodes.end(), goodNodes.begin(), goodNodes.end());
- } else {
- nodes.insert(nodes.end(), goodNodes.begin(), goodNodes.begin()+r);
- }
- }
- }
- }
-}
-
-void BNode::enumerateBucket(std::vector<SharedHandle<DHTBucket> >& buckets,
- const BNode* b)
-{
- std::vector<const BNode*> visited;
- visited.push_back(b);
- while(1) {
- if(!b) {
- break;
- }
- if(b->getBucket()) {
- buckets.push_back(b->getBucket());
- b = b->getUp();
- } else if(std::find(visited.begin(), visited.end(), b->getLeft()) == visited.end()) {
- b = b->getLeft();
- visited.push_back(b);
- } else if(std::find(visited.begin(), visited.end(), b->getRight()) == visited.end()) {
- b = b->getRight();
- visited.push_back(b);
- } else {
- b = b->getUp();
- }
- }
- return;
-}
-
-} // namespace aria2
diff --git a/src/BNode.h b/src/BNode.h
deleted file mode 100644
index f3022ddc..00000000
--- a/src/BNode.h
+++ /dev/null
@@ -1,107 +0,0 @@
-/* <!-- copyright */
-/*
- * aria2 - The high speed download utility
- *
- * Copyright (C) 2006 Tatsuhiro Tsujikawa
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
- *
- * In addition, as a special exception, the copyright holders give
- * permission to link the code of portions of this program with the
- * OpenSSL library under certain conditions as described in each
- * individual source file, and distribute linked combinations
- * including the two.
- * You must obey the GNU General Public License in all respects
- * for all of the code used other than OpenSSL. If you modify
- * file(s) with this exception, you may extend this exception to your
- * version of the file(s), but you are not obligated to do so. If you
- * do not wish to do so, delete this exception statement from your
- * version. If you delete this exception statement from all source
- * files in the program, then also delete it here.
- */
-/* copyright --> */
-#ifndef D_BNODE_H
-#define D_BNODE_H
-
-#include "common.h"
-
-#include <vector>
-
-#include "SharedHandle.h"
-
-namespace aria2 {
-
-class DHTBucket;
-class DHTNode;
-
-class BNode {
-private:
- SharedHandle<DHTBucket> bucket_;
-
- BNode* up_;
-
- BNode* left_;
-
- BNode* right_;
-
-public:
- BNode(const SharedHandle<DHTBucket>& bucket = SharedHandle<DHTBucket>());
-
- ~BNode();
-
- const SharedHandle<DHTBucket>& getBucket() const
- {
- return bucket_;
- }
-
- void setBucket(const SharedHandle<DHTBucket>& bucket);
-
- BNode* getLeft() const
- {
- return left_;
- }
-
- void setLeft(BNode* left);
-
- BNode* getRight() const
- {
- return right_;
- }
-
- void setRight(BNode* right);
-
- BNode* getUp() const
- {
- return up_;
- }
-
- void setUp(BNode* up);
-
- bool isInRange(const unsigned char* key) const;
-
- static BNode* findBNodeFor(BNode* b, const unsigned char* key);
-
- static SharedHandle<DHTBucket> findBucketFor(BNode* b, const unsigned char* key);
-
- static void findClosestKNodes(std::vector<SharedHandle<DHTNode> >& nodes,
- BNode* b, const unsigned char* key);
-
- static void enumerateBucket(std::vector<SharedHandle<DHTBucket> >& buckets,
- const BNode* b);
-};
-
-} // namespace aria2
-
-#endif // D_BNODE_H
diff --git a/src/DHTBucketTree.cc b/src/DHTBucketTree.cc
new file mode 100644
index 00000000..d7f0ae56
--- /dev/null
+++ b/src/DHTBucketTree.cc
@@ -0,0 +1,233 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2010 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you
+ * do not wish to do so, delete this exception statement from your
+ * version. If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#include "DHTBucketTree.h"
+
+#include <cstring>
+#include <algorithm>
+
+#include "DHTBucket.h"
+#include "DHTNode.h"
+
+namespace aria2 {
+
+DHTBucketTreeNode::DHTBucketTreeNode
+(DHTBucketTreeNode* left,
+ DHTBucketTreeNode* right)
+ : parent_(0),
+ left_(left),
+ right_(right)
+{
+ resetRelation();
+}
+
+DHTBucketTreeNode::DHTBucketTreeNode(const SharedHandle<DHTBucket>& bucket)
+ : parent_(0),
+ left_(0),
+ right_(0),
+ bucket_(bucket)
+{
+ memcpy(minId_, bucket_->getMinID(), DHT_ID_LENGTH);
+ memcpy(maxId_, bucket_->getMaxID(), DHT_ID_LENGTH);
+}
+
+DHTBucketTreeNode::~DHTBucketTreeNode()
+{
+ delete left_;
+ delete right_;
+}
+
+void DHTBucketTreeNode::resetRelation()
+{
+ left_->setParent(this);
+ right_->setParent(this);
+ memcpy(minId_, left_->getMinId(), DHT_ID_LENGTH);
+ memcpy(maxId_, right_->getMaxId(), DHT_ID_LENGTH);
+}
+
+DHTBucketTreeNode* DHTBucketTreeNode::dig(const unsigned char* key)
+{
+ if(leaf()) {
+ return 0;
+ }
+ if(left_->isInRange(key)) {
+ return left_;
+ } else {
+ return right_;
+ }
+}
+
+bool DHTBucketTreeNode::isInRange(const unsigned char* key) const
+{
+ return
+ !std::lexicographical_compare(&key[0], &key[DHT_ID_LENGTH],
+ &minId_[0], &minId_[DHT_ID_LENGTH]) &&
+ !std::lexicographical_compare(&maxId_[0], &maxId_[DHT_ID_LENGTH],
+ &key[0], &key[DHT_ID_LENGTH]);
+}
+
+void DHTBucketTreeNode::split()
+{
+ SharedHandle<DHTBucket> leftBucket = bucket_->split();
+ left_ = new DHTBucketTreeNode(leftBucket);
+ right_ = new DHTBucketTreeNode(bucket_);
+ bucket_.reset();
+ resetRelation();
+}
+
+namespace dht {
+
+DHTBucketTreeNode* findTreeNodeFor
+(DHTBucketTreeNode* root, const unsigned char* key)
+{
+ if(root->leaf()) {
+ return root;
+ } else {
+ return findTreeNodeFor(root->dig(key), key);
+ }
+}
+
+SharedHandle<DHTBucket> findBucketFor
+(DHTBucketTreeNode* root, const unsigned char* key)
+{
+ DHTBucketTreeNode* leaf = findTreeNodeFor(root, key);
+ return leaf->getBucket();
+}
+
+namespace {
+void collectNodes
+(std::vector<SharedHandle<DHTNode> >& nodes,
+ const SharedHandle<DHTBucket>& bucket)
+{
+ std::vector<SharedHandle<DHTNode> > goodNodes;
+ bucket->getGoodNodes(goodNodes);
+ nodes.insert(nodes.end(), goodNodes.begin(), goodNodes.end());
+}
+} // namespace
+
+namespace {
+void collectDownwardLeftFirst
+(std::vector<SharedHandle<DHTNode> >& nodes, DHTBucketTreeNode* tnode)
+{
+ if(tnode->leaf()) {
+ collectNodes(nodes, tnode->getBucket());
+ } else {
+ collectDownwardLeftFirst(nodes, tnode->getLeft());
+ if(nodes.size() < DHTBucket::K) {
+ collectDownwardLeftFirst(nodes, tnode->getRight());
+ }
+ }
+}
+} //namespace
+
+namespace {
+void collectDownwardRightFirst
+(std::vector<SharedHandle<DHTNode> >& nodes, DHTBucketTreeNode* tnode)
+{
+ if(tnode->leaf()) {
+ collectNodes(nodes, tnode->getBucket());
+ } else {
+ collectDownwardRightFirst(nodes, tnode->getRight());
+ if(nodes.size() < DHTBucket::K) {
+ collectDownwardRightFirst(nodes, tnode->getLeft());
+ }
+ }
+}
+} //namespace
+
+namespace {
+void collectUpward
+(std::vector<SharedHandle<DHTNode> >& nodes, DHTBucketTreeNode* from)
+{
+ while(1) {
+ DHTBucketTreeNode* parent = from->getParent();
+ if(!parent) {
+ break;
+ }
+ if(parent->getLeft() == from) {
+ collectNodes(nodes, parent->getRight()->getBucket());
+ } else {
+ collectNodes(nodes, parent->getLeft()->getBucket());
+ }
+ from = parent;
+ parent = parent->getParent();
+ if(DHTBucket::K <= nodes.size()) {
+ break;
+ }
+ }
+}
+} // namespace
+
+void findClosestKNodes
+(std::vector<SharedHandle<DHTNode> >& nodes,
+ DHTBucketTreeNode* root,
+ const unsigned char* key)
+{
+ size_t nodesSize = nodes.size();
+ if(DHTBucket::K <= nodesSize) {
+ return;
+ }
+ DHTBucketTreeNode* leaf = findTreeNodeFor(root, key);
+ if(leaf == root) {
+ collectNodes(nodes, leaf->getBucket());
+ } else {
+ DHTBucketTreeNode* parent = leaf->getParent();
+ if(parent->getLeft() == leaf) {
+ collectDownwardLeftFirst(nodes, parent);
+ } else {
+ collectDownwardRightFirst(nodes, parent);
+ }
+ if(nodes.size() < DHTBucket::K) {
+ collectUpward(nodes, parent);
+ }
+ }
+ if(DHTBucket::K < nodes.size()) {
+ nodes.erase(nodes.begin()+DHTBucket::K, nodes.end());
+ }
+}
+
+void enumerateBucket
+(std::vector<SharedHandle<DHTBucket> >& buckets, DHTBucketTreeNode* root)
+{
+ if(root->leaf()) {
+ buckets.push_back(root->getBucket());
+ } else {
+ enumerateBucket(buckets, root->getLeft());
+ enumerateBucket(buckets, root->getRight());
+ }
+}
+
+} // namespace dht
+
+} // namespace aria2
diff --git a/src/DHTBucketTree.h b/src/DHTBucketTree.h
new file mode 100644
index 00000000..48c47a8c
--- /dev/null
+++ b/src/DHTBucketTree.h
@@ -0,0 +1,119 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2010 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you
+ * do not wish to do so, delete this exception statement from your
+ * version. If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#ifndef D_DHT_BUCKET_TREE_H
+#define D_DHT_BUCKET_TREE_H
+
+#include "common.h"
+
+#include <vector>
+
+#include "SharedHandle.h"
+#include "DHTConstants.h"
+
+namespace aria2 {
+
+class DHTBucket;
+class DHTNode;
+
+// This class represents Kademlia DHT routing tree. The leaf nodes
+// have bucket which contains DHT node. The tree is binary tree but
+// highly unbalanced.
+class DHTBucketTreeNode {
+public:
+ // Ctor for internal node
+ DHTBucketTreeNode(DHTBucketTreeNode* left, DHTBucketTreeNode* right);
+ // Ctor for leaf node
+ DHTBucketTreeNode(const SharedHandle<DHTBucket>& bucket);
+ ~DHTBucketTreeNode();
+ // Returns child node, left or right, which contains key. If dig is
+ // called against leaf node, then returns 0.
+ DHTBucketTreeNode* dig(const unsigned char* key);
+ bool isInRange(const unsigned char* key) const;
+ // Returns true iff this is a leaf node.
+ bool leaf() const { return bucket_; }
+ const unsigned char* getMaxId() const { return maxId_; }
+ const unsigned char* getMinId() const { return minId_; }
+ DHTBucketTreeNode* getParent() const { return parent_; }
+ DHTBucketTreeNode* getLeft() const { return left_; }
+ DHTBucketTreeNode* getRight() const { return right_; }
+ const SharedHandle<DHTBucket>& getBucket() const { return bucket_; }
+ // Splits this object's bucket using DHTBucket::split() and create
+ // left and right child node to hold buckets. The bucket of current
+ // node is reseted so this node becomes internal node after this
+ // call.
+ void split();
+private:
+ // Reset relation of children and minId_ and maxId_.
+ void resetRelation();
+ void setParent(DHTBucketTreeNode* parent) { parent_ = parent; }
+ DHTBucketTreeNode* parent_;
+ DHTBucketTreeNode* left_;
+ DHTBucketTreeNode* right_;
+ SharedHandle<DHTBucket> bucket_;
+ unsigned char minId_[DHT_ID_LENGTH];
+ unsigned char maxId_[DHT_ID_LENGTH];
+};
+
+namespace dht {
+
+// Returns leaf node where key fits between node's min and max ID
+// range.
+DHTBucketTreeNode* findTreeNodeFor
+(DHTBucketTreeNode* root, const unsigned char* key);
+
+// Returns bucket where key fits between bucket's min and max ID
+// range. This function first use findTreeNodeFor and returns its
+// bucket_.
+SharedHandle<DHTBucket> findBucketFor
+(DHTBucketTreeNode* root, const unsigned char* key);
+
+// Stores most closest K nodes against key in nodes. K is
+// DHTBucket::K. This function may returns less than K nodes because
+// the routing tree contains less than K nodes. The order of nodes is
+// arbitrary. Caller must pass empty nodes.
+void findClosestKNodes
+(std::vector<SharedHandle<DHTNode> >& nodes,
+ DHTBucketTreeNode* root,
+ const unsigned char* key);
+
+// Stores all buckets in buckets.
+void enumerateBucket
+(std::vector<SharedHandle<DHTBucket> >& buckets, DHTBucketTreeNode* root);
+
+} // namespace dht
+
+} // namespace aria2
+
+#endif // D_DHT_BUCKET_TREE_H
diff --git a/src/DHTRoutingTable.cc b/src/DHTRoutingTable.cc
index 5d4bf18f..bffcad3f 100644
--- a/src/DHTRoutingTable.cc
+++ b/src/DHTRoutingTable.cc
@@ -38,7 +38,7 @@
#include "DHTNode.h"
#include "DHTBucket.h"
-#include "BNode.h"
+#include "DHTBucketTree.h"
#include "DHTTaskQueue.h"
#include "DHTTaskFactory.h"
#include "DHTTask.h"
@@ -48,14 +48,13 @@
namespace aria2 {
-DHTRoutingTable::DHTRoutingTable(const SharedHandle<DHTNode>& localNode):
- localNode_(localNode),
- numBucket_(1),
- logger_(LogFactory::getInstance())
-{
- SharedHandle<DHTBucket> bucket(new DHTBucket(localNode_));
- root_ = new BNode(bucket);
-}
+DHTRoutingTable::DHTRoutingTable(const SharedHandle<DHTNode>& localNode)
+ : localNode_(localNode),
+ root_(new DHTBucketTreeNode
+ (SharedHandle<DHTBucket>(new DHTBucket(localNode_)))),
+ numBucket_(1),
+ logger_(LogFactory::getInstance())
+{}
DHTRoutingTable::~DHTRoutingTable()
{
@@ -84,9 +83,9 @@ bool DHTRoutingTable::addNode(const SharedHandle<DHTNode>& node, bool good)
}
return false;
}
- BNode* bnode = BNode::findBNodeFor(root_, node->getID());
- SharedHandle<DHTBucket> bucket = bnode->getBucket();
+ DHTBucketTreeNode* treeNode = dht::findTreeNodeFor(root_, node->getID());
while(1) {
+ const SharedHandle<DHTBucket>& bucket = treeNode->getBucket();
if(bucket->addNode(node)) {
if(logger_->debug()) {
logger_->debug("Added DHTNode.");
@@ -98,20 +97,12 @@ bool DHTRoutingTable::addNode(const SharedHandle<DHTNode>& node, bool good)
util::toHex(bucket->getMinID(), DHT_ID_LENGTH).c_str(),
util::toHex(bucket->getMaxID(), DHT_ID_LENGTH).c_str());
}
- SharedHandle<DHTBucket> r = bucket->split();
-
- bnode->setBucket(SharedHandle<DHTBucket>());
- BNode* lbnode = new BNode(bucket);
- BNode* rbnode = new BNode(r);
- bnode->setLeft(lbnode);
- bnode->setRight(rbnode);
+ treeNode->split();
++numBucket_;
-
- if(r->isInRange(node)) {
- bucket = r;
- bnode = rbnode;
+ if(treeNode->getLeft()->isInRange(node->getID())) {
+ treeNode = treeNode->getLeft();
} else {
- bnode = lbnode;
+ treeNode = treeNode->getRight();
}
} else {
if(good) {
@@ -130,7 +121,7 @@ void DHTRoutingTable::getClosestKNodes
(std::vector<SharedHandle<DHTNode> >& nodes,
const unsigned char* key) const
{
- BNode::findClosestKNodes(nodes, root_, key);
+ dht::findClosestKNodes(nodes, root_, key);
}
size_t DHTRoutingTable::countBucket() const
@@ -149,7 +140,7 @@ void DHTRoutingTable::showBuckets() const
SharedHandle<DHTBucket> DHTRoutingTable::getBucketFor(const unsigned char* nodeID) const
{
- return BNode::findBucketFor(root_, nodeID);
+ return dht::findBucketFor(root_, nodeID);
}
SharedHandle<DHTBucket> DHTRoutingTable::getBucketFor(const SharedHandle<DHTNode>& node) const
@@ -181,7 +172,7 @@ void DHTRoutingTable::moveBucketTail(const SharedHandle<DHTNode>& node)
void DHTRoutingTable::getBuckets
(std::vector<SharedHandle<DHTBucket> >& buckets) const
{
- BNode::enumerateBucket(buckets, root_);
+ dht::enumerateBucket(buckets, root_);
}
void DHTRoutingTable::setTaskQueue(const SharedHandle<DHTTaskQueue>& taskQueue)
diff --git a/src/DHTRoutingTable.h b/src/DHTRoutingTable.h
index a604d862..3c2c7af8 100644
--- a/src/DHTRoutingTable.h
+++ b/src/DHTRoutingTable.h
@@ -48,14 +48,14 @@ class DHTNode;
class DHTBucket;
class DHTTaskQueue;
class DHTTaskFactory;
-class BNode;
+class DHTBucketTreeNode;
class Logger;
class DHTRoutingTable {
private:
SharedHandle<DHTNode> localNode_;
- BNode* root_;
+ DHTBucketTreeNode* root_;
size_t numBucket_;
diff --git a/src/Makefile.am b/src/Makefile.am
index 7abef93a..84f16a77 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -407,7 +407,7 @@ SRCS += PeerAbstractCommand.cc PeerAbstractCommand.h\
DHTMessageFactoryImpl.cc DHTMessageFactoryImpl.h\
DHTNodeLookupTask.cc DHTNodeLookupTask.h\
DHTNodeLookupEntry.cc DHTNodeLookupEntry.h\
- BNode.cc BNode.h\
+ DHTBucketTree.cc DHTBucketTree.h\
DHTMessageCallback.h\
DHTNodeLookupTaskCallback.cc DHTNodeLookupTaskCallback.h\
DHTPingReplyMessageCallback.h\
diff --git a/src/Makefile.in b/src/Makefile.in
index 206acd7c..3f399dc9 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -199,7 +199,7 @@ bin_PROGRAMS = aria2c$(EXEEXT)
@ENABLE_BITTORRENT_TRUE@ DHTMessageFactoryImpl.cc DHTMessageFactoryImpl.h\
@ENABLE_BITTORRENT_TRUE@ DHTNodeLookupTask.cc DHTNodeLookupTask.h\
@ENABLE_BITTORRENT_TRUE@ DHTNodeLookupEntry.cc DHTNodeLookupEntry.h\
-@ENABLE_BITTORRENT_TRUE@ BNode.cc BNode.h\
+@ENABLE_BITTORRENT_TRUE@ DHTBucketTree.cc DHTBucketTree.h\
@ENABLE_BITTORRENT_TRUE@ DHTMessageCallback.h\
@ENABLE_BITTORRENT_TRUE@ DHTNodeLookupTaskCallback.cc DHTNodeLookupTaskCallback.h\
@ENABLE_BITTORRENT_TRUE@ DHTPingReplyMessageCallback.h\
@@ -584,26 +584,26 @@ am__libaria2c_a_SOURCES_DIST = Socket.h SocketCore.cc SocketCore.h \
DHTUnknownMessage.cc DHTUnknownMessage.h DHTMessageFactory.h \
DHTMessageFactoryImpl.cc DHTMessageFactoryImpl.h \
DHTNodeLookupTask.cc DHTNodeLookupTask.h DHTNodeLookupEntry.cc \
- DHTNodeLookupEntry.h BNode.cc BNode.h DHTMessageCallback.h \
- DHTNodeLookupTaskCallback.cc DHTNodeLookupTaskCallback.h \
- DHTPingReplyMessageCallback.h DHTPeerLookupTaskCallback.cc \
- DHTPeerLookupTaskCallback.h DHTAbstractTask.cc \
- DHTAbstractTask.h DHTTask.h DHTPingTask.cc DHTPingTask.h \
- DHTTaskQueue.h DHTTaskQueueImpl.cc DHTTaskQueueImpl.h \
- DHTTaskExecutor.cc DHTTaskExecutor.h DHTBucketRefreshTask.cc \
- DHTBucketRefreshTask.h DHTAbstractNodeLookupTask.h \
- DHTPeerLookupTask.cc DHTPeerLookupTask.h DHTSetup.cc \
- DHTSetup.h DHTTaskFactory.h DHTTaskFactoryImpl.cc \
- DHTTaskFactoryImpl.h DHTInteractionCommand.cc \
- DHTInteractionCommand.h DHTPeerAnnounceEntry.cc \
- DHTPeerAnnounceEntry.h DHTPeerAnnounceStorage.cc \
- DHTPeerAnnounceStorage.h DHTTokenTracker.cc DHTTokenTracker.h \
- DHTGetPeersCommand.cc DHTGetPeersCommand.h \
- DHTTokenUpdateCommand.cc DHTTokenUpdateCommand.h \
- DHTBucketRefreshCommand.cc DHTBucketRefreshCommand.h \
- DHTPeerAnnounceCommand.cc DHTPeerAnnounceCommand.h \
- DHTReplaceNodeTask.cc DHTReplaceNodeTask.h \
- DHTEntryPointNameResolveCommand.cc \
+ DHTNodeLookupEntry.h DHTBucketTree.cc DHTBucketTree.h \
+ DHTMessageCallback.h DHTNodeLookupTaskCallback.cc \
+ DHTNodeLookupTaskCallback.h DHTPingReplyMessageCallback.h \
+ DHTPeerLookupTaskCallback.cc DHTPeerLookupTaskCallback.h \
+ DHTAbstractTask.cc DHTAbstractTask.h DHTTask.h DHTPingTask.cc \
+ DHTPingTask.h DHTTaskQueue.h DHTTaskQueueImpl.cc \
+ DHTTaskQueueImpl.h DHTTaskExecutor.cc DHTTaskExecutor.h \
+ DHTBucketRefreshTask.cc DHTBucketRefreshTask.h \
+ DHTAbstractNodeLookupTask.h DHTPeerLookupTask.cc \
+ DHTPeerLookupTask.h DHTSetup.cc DHTSetup.h DHTTaskFactory.h \
+ DHTTaskFactoryImpl.cc DHTTaskFactoryImpl.h \
+ DHTInteractionCommand.cc DHTInteractionCommand.h \
+ DHTPeerAnnounceEntry.cc DHTPeerAnnounceEntry.h \
+ DHTPeerAnnounceStorage.cc DHTPeerAnnounceStorage.h \
+ DHTTokenTracker.cc DHTTokenTracker.h DHTGetPeersCommand.cc \
+ DHTGetPeersCommand.h DHTTokenUpdateCommand.cc \
+ DHTTokenUpdateCommand.h DHTBucketRefreshCommand.cc \
+ DHTBucketRefreshCommand.h DHTPeerAnnounceCommand.cc \
+ DHTPeerAnnounceCommand.h DHTReplaceNodeTask.cc \
+ DHTReplaceNodeTask.h DHTEntryPointNameResolveCommand.cc \
DHTEntryPointNameResolveCommand.h DHTRoutingTableSerializer.cc \
DHTRoutingTableSerializer.h DHTRoutingTableDeserializer.cc \
DHTRoutingTableDeserializer.h DHTAutoSaveCommand.cc \
@@ -786,7 +786,7 @@ am__objects_6 =
@ENABLE_BITTORRENT_TRUE@ DHTMessageFactoryImpl.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTNodeLookupTask.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTNodeLookupEntry.$(OBJEXT) \
-@ENABLE_BITTORRENT_TRUE@ BNode.$(OBJEXT) \
+@ENABLE_BITTORRENT_TRUE@ DHTBucketTree.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTNodeLookupTaskCallback.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTPeerLookupTaskCallback.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTAbstractTask.$(OBJEXT) \
@@ -1437,7 +1437,6 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/AuthConfig.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/AuthConfigFactory.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/AutoSaveCommand.Po@am__quote@
-@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/BNode.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Base64.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/BitfieldMan.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/BtAbortOutstandingRequestEvent.Po@am__quote@
@@ -1497,6 +1496,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTBucket.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTBucketRefreshCommand.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTBucketRefreshTask.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTBucketTree.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTConnectionImpl.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTEntryPointNameResolveCommand.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTFindNodeMessage.Po@am__quote@
diff --git a/test/BNodeTest.cc b/test/DHTBucketTreeTest.cc
index 68d9287f..a5458344 100644
--- a/test/BNodeTest.cc
+++ b/test/DHTBucketTreeTest.cc
@@ -1,4 +1,4 @@
-#include "BNode.h"
+#include "DHTBucketTree.h"
#include <cstring>
#include <cppunit/extensions/HelperMacros.h>
@@ -10,29 +10,25 @@
namespace aria2 {
-class BNodeTest:public CppUnit::TestFixture {
+class DHTBucketTreeTest:public CppUnit::TestFixture {
- CPPUNIT_TEST_SUITE(BNodeTest);
- CPPUNIT_TEST(testIsInRange);
+ CPPUNIT_TEST_SUITE(DHTBucketTreeTest);
+ CPPUNIT_TEST(testDig);
CPPUNIT_TEST(testFindBucketFor);
CPPUNIT_TEST(testFindClosestKNodes);
CPPUNIT_TEST(testEnumerateBucket);
CPPUNIT_TEST_SUITE_END();
public:
- void setUp() {}
-
- void tearDown() {}
-
- void testIsInRange();
+ void testDig();
void testFindBucketFor();
void testFindClosestKNodes();
void testEnumerateBucket();
};
-CPPUNIT_TEST_SUITE_REGISTRATION(BNodeTest);
+CPPUNIT_TEST_SUITE_REGISTRATION(DHTBucketTreeTest);
-void BNodeTest::testIsInRange()
+void DHTBucketTreeTest::testDig()
{
unsigned char localNodeID[DHT_ID_LENGTH];
memset(localNodeID, 0xff, DHT_ID_LENGTH);
@@ -42,18 +38,29 @@ void BNodeTest::testIsInRange()
SharedHandle<DHTBucket> bucket1(new DHTBucket(localNode));
SharedHandle<DHTBucket> bucket2 = bucket1->split();
SharedHandle<DHTBucket> bucket3 = bucket1->split();
-
+ // Tree: number is prefix
+ //
+ // +
+ // +------+------+
+ // b2 |
+ // 0 +------+------+
+ // b3 b1
+ // 10 11
+ // |
+ // localNode is here
{
- BNode b(bucket1);
- CPPUNIT_ASSERT(b.isInRange(localNode->getID()));
+ DHTBucketTreeNode b(bucket1);
+ CPPUNIT_ASSERT(!b.dig(localNode->getID()));
}
{
- BNode b(bucket2);
- CPPUNIT_ASSERT(!b.isInRange(localNode->getID()));
+ DHTBucketTreeNode* left = new DHTBucketTreeNode(bucket3);
+ DHTBucketTreeNode* right = new DHTBucketTreeNode(bucket1);
+ DHTBucketTreeNode b(left, right);
+ CPPUNIT_ASSERT(b.dig(localNode->getID()) == right);
}
}
-void BNodeTest::testFindBucketFor()
+void DHTBucketTreeTest::testFindBucketFor()
{
unsigned char localNodeID[DHT_ID_LENGTH];
memset(localNodeID, 0xaa, DHT_ID_LENGTH);
@@ -67,43 +74,40 @@ void BNodeTest::testFindBucketFor()
SharedHandle<DHTBucket> bucket5 = bucket3->split();
{
- BNode b(bucket5);
- CPPUNIT_ASSERT(*bucket5 == *BNode::findBucketFor(&b, localNodeID));
- }
- {
- BNode b(bucket1);
- CPPUNIT_ASSERT(!BNode::findBucketFor(&b, localNodeID));
+ DHTBucketTreeNode b(bucket5);
+ CPPUNIT_ASSERT(*bucket5 == *dht::findBucketFor(&b, localNodeID));
}
{
- BNode* b1 = new BNode(bucket1);
- BNode* b2 = new BNode(bucket2);
- BNode* b3 = new BNode(bucket3);
- BNode* b4 = new BNode(bucket4);
- BNode* b5 = new BNode(bucket5);
-
- BNode* bp1 = new BNode();
- bp1->setLeft(b3);
- bp1->setRight(b5);
-
- BNode* bp2 = new BNode();
- bp2->setLeft(bp1);
- bp2->setRight(b4);
-
- BNode* bp3 = new BNode();
- bp3->setLeft(b1);
- bp3->setRight(bp2);
-
- BNode* bp4 = new BNode();
- bp4->setLeft(bp3);
- bp4->setRight(b2);
-
- CPPUNIT_ASSERT(*bucket5 == *BNode::findBucketFor(bp4, localNode->getID()));
-
- delete bp4;
+ // Tree: number is prefix
+ //
+ // +
+ // +------+------+
+ // b2 |
+ // 0 +------+------+
+ // | b1
+ // +-----+-----+ 11
+ // b4 |
+ // 100 +-----+-----+
+ // b5 b3
+ // 1010 1011
+ // |
+ // localNode is here
+ DHTBucketTreeNode* b1 = new DHTBucketTreeNode(bucket1);
+ DHTBucketTreeNode* b2 = new DHTBucketTreeNode(bucket2);
+ DHTBucketTreeNode* b3 = new DHTBucketTreeNode(bucket3);
+ DHTBucketTreeNode* b4 = new DHTBucketTreeNode(bucket4);
+ DHTBucketTreeNode* b5 = new DHTBucketTreeNode(bucket5);
+
+ DHTBucketTreeNode* bp1 = new DHTBucketTreeNode(b5, b3);
+ DHTBucketTreeNode* bp2 = new DHTBucketTreeNode(b4, bp1);
+ DHTBucketTreeNode* bp3 = new DHTBucketTreeNode(bp2, b1);
+ DHTBucketTreeNode bp4(b2, bp3);
+
+ CPPUNIT_ASSERT(*bucket5 == *dht::findBucketFor(&bp4, localNode->getID()));
}
}
-void BNodeTest::testFindClosestKNodes()
+void DHTBucketTreeTest::testFindClosestKNodes()
{
unsigned char localNodeID[DHT_ID_LENGTH];
memset(localNodeID, 0xaa, DHT_ID_LENGTH);
@@ -118,28 +122,16 @@ void BNodeTest::testFindClosestKNodes()
unsigned char id[DHT_ID_LENGTH];
{
- BNode* b1 = new BNode(bucket1);
- BNode* b2 = new BNode(bucket2);
- BNode* b3 = new BNode(bucket3);
- BNode* b4 = new BNode(bucket4);
- BNode* b5 = new BNode(bucket5);
-
- BNode* bp1 = new BNode();
- bp1->setLeft(b3);
- bp1->setRight(b5);
-
- BNode* bp2 = new BNode();
- bp2->setLeft(bp1);
- bp2->setRight(b4);
-
- BNode* bp3 = new BNode();
- bp3->setLeft(b1);
- bp3->setRight(bp2);
-
- BNode* bp4 = new BNode();
- bp4->setLeft(bp3);
- bp4->setRight(b2);
+ DHTBucketTreeNode* b1 = new DHTBucketTreeNode(bucket1);
+ DHTBucketTreeNode* b2 = new DHTBucketTreeNode(bucket2);
+ DHTBucketTreeNode* b3 = new DHTBucketTreeNode(bucket3);
+ DHTBucketTreeNode* b4 = new DHTBucketTreeNode(bucket4);
+ DHTBucketTreeNode* b5 = new DHTBucketTreeNode(bucket5);
+ DHTBucketTreeNode* bp1 = new DHTBucketTreeNode(b5, b3);
+ DHTBucketTreeNode* bp2 = new DHTBucketTreeNode(b4, bp1);
+ DHTBucketTreeNode* bp3 = new DHTBucketTreeNode(bp2, b1);
+ DHTBucketTreeNode bp4(b2, bp3);
for(size_t i = 0; i < 2; ++i) {
bucket1->getRandomNodeID(id);
@@ -157,7 +149,7 @@ void BNodeTest::testFindClosestKNodes()
unsigned char targetID[DHT_ID_LENGTH];
memset(targetID, 0x80, DHT_ID_LENGTH);
std::vector<SharedHandle<DHTNode> > nodes;
- BNode::findClosestKNodes(nodes, bp4, targetID);
+ dht::findClosestKNodes(nodes, &bp4, targetID);
CPPUNIT_ASSERT_EQUAL((size_t)8, nodes.size());
CPPUNIT_ASSERT(bucket4->isInRange(nodes[0]));
CPPUNIT_ASSERT(bucket4->isInRange(nodes[1]));
@@ -172,7 +164,7 @@ void BNodeTest::testFindClosestKNodes()
unsigned char targetID[DHT_ID_LENGTH];
memset(targetID, 0xf0, DHT_ID_LENGTH);
std::vector<SharedHandle<DHTNode> > nodes;
- BNode::findClosestKNodes(nodes, bp4, targetID);
+ dht::findClosestKNodes(nodes, &bp4, targetID);
CPPUNIT_ASSERT_EQUAL((size_t)8, nodes.size());
CPPUNIT_ASSERT(bucket1->isInRange(nodes[0]));
CPPUNIT_ASSERT(bucket1->isInRange(nodes[1]));
@@ -191,18 +183,17 @@ void BNodeTest::testFindClosestKNodes()
unsigned char targetID[DHT_ID_LENGTH];
memset(targetID, 0x80, DHT_ID_LENGTH);
std::vector<SharedHandle<DHTNode> > nodes;
- BNode::findClosestKNodes(nodes, bp4, targetID);
+ dht::findClosestKNodes(nodes, &bp4, targetID);
CPPUNIT_ASSERT_EQUAL((size_t)8, nodes.size());
for(size_t i = 0; i < DHTBucket::K; ++i) {
CPPUNIT_ASSERT(bucket4->isInRange(nodes[i]));
}
}
- delete bp4;
}
}
-void BNodeTest::testEnumerateBucket()
+void DHTBucketTreeTest::testEnumerateBucket()
{
unsigned char localNodeID[DHT_ID_LENGTH];
memset(localNodeID, 0xaa, DHT_ID_LENGTH);
@@ -216,45 +207,32 @@ void BNodeTest::testEnumerateBucket()
SharedHandle<DHTBucket> bucket5 = bucket3->split();
{
- BNode b(bucket1);
+ DHTBucketTreeNode b(bucket1);
std::vector<SharedHandle<DHTBucket> > buckets;
- BNode::enumerateBucket(buckets, &b);
+ dht::enumerateBucket(buckets, &b);
CPPUNIT_ASSERT_EQUAL((size_t)1, buckets.size());
CPPUNIT_ASSERT(*bucket1 == *buckets[0]);
}
{
- BNode* b1 = new BNode(bucket1);
- BNode* b2 = new BNode(bucket2);
- BNode* b3 = new BNode(bucket3);
- BNode* b4 = new BNode(bucket4);
- BNode* b5 = new BNode(bucket5);
+ DHTBucketTreeNode* b1 = new DHTBucketTreeNode(bucket1);
+ DHTBucketTreeNode* b2 = new DHTBucketTreeNode(bucket2);
+ DHTBucketTreeNode* b3 = new DHTBucketTreeNode(bucket3);
+ DHTBucketTreeNode* b4 = new DHTBucketTreeNode(bucket4);
+ DHTBucketTreeNode* b5 = new DHTBucketTreeNode(bucket5);
- BNode* bp1 = new BNode();
- bp1->setLeft(b3);
- bp1->setRight(b5);
-
- BNode* bp2 = new BNode();
- bp2->setLeft(bp1);
- bp2->setRight(b4);
-
- BNode* bp3 = new BNode();
- bp3->setLeft(b1);
- bp3->setRight(bp2);
-
- BNode* bp4 = new BNode();
- bp4->setLeft(bp3);
- bp4->setRight(b2);
+ DHTBucketTreeNode* bp1 = new DHTBucketTreeNode(b5, b3);
+ DHTBucketTreeNode* bp2 = new DHTBucketTreeNode(b4, bp1);
+ DHTBucketTreeNode* bp3 = new DHTBucketTreeNode(bp2, b1);
+ DHTBucketTreeNode bp4(b2, bp3);
std::vector<SharedHandle<DHTBucket> > buckets;
- BNode::enumerateBucket(buckets, bp4);
+ dht::enumerateBucket(buckets, &bp4);
CPPUNIT_ASSERT_EQUAL((size_t)5, buckets.size());
- CPPUNIT_ASSERT(*bucket1 == *buckets[0]);
- CPPUNIT_ASSERT(*bucket3 == *buckets[1]);
+ CPPUNIT_ASSERT(*bucket2 == *buckets[0]);
+ CPPUNIT_ASSERT(*bucket4 == *buckets[1]);
CPPUNIT_ASSERT(*bucket5 == *buckets[2]);
- CPPUNIT_ASSERT(*bucket4 == *buckets[3]);
- CPPUNIT_ASSERT(*bucket2 == *buckets[4]);
-
- delete bp4;
+ CPPUNIT_ASSERT(*bucket3 == *buckets[3]);
+ CPPUNIT_ASSERT(*bucket1 == *buckets[4]);
}
}
diff --git a/test/Makefile.am b/test/Makefile.am
index e29602e9..68a065ee 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -168,7 +168,7 @@ aria2c_SOURCES += BtAllowedFastMessageTest.cc\
DHTAnnouncePeerReplyMessageTest.cc\
DHTUnknownMessageTest.cc\
DHTMessageFactoryImplTest.cc\
- BNodeTest.cc\
+ DHTBucketTreeTest.cc\
DHTPeerAnnounceEntryTest.cc\
DHTPeerAnnounceStorageTest.cc\
DHTTokenTrackerTest.cc\
diff --git a/test/Makefile.in b/test/Makefile.in
index 2907ac30..8e6d862f 100644
--- a/test/Makefile.in
+++ b/test/Makefile.in
@@ -114,7 +114,7 @@ check_PROGRAMS = $(am__EXEEXT_1)
@ENABLE_BITTORRENT_TRUE@ DHTAnnouncePeerReplyMessageTest.cc\
@ENABLE_BITTORRENT_TRUE@ DHTUnknownMessageTest.cc\
@ENABLE_BITTORRENT_TRUE@ DHTMessageFactoryImplTest.cc\
-@ENABLE_BITTORRENT_TRUE@ BNodeTest.cc\
+@ENABLE_BITTORRENT_TRUE@ DHTBucketTreeTest.cc\
@ENABLE_BITTORRENT_TRUE@ DHTPeerAnnounceEntryTest.cc\
@ENABLE_BITTORRENT_TRUE@ DHTPeerAnnounceStorageTest.cc\
@ENABLE_BITTORRENT_TRUE@ DHTTokenTrackerTest.cc\
@@ -258,7 +258,7 @@ am__aria2c_SOURCES_DIST = AllTest.cc TestUtil.cc TestUtil.h \
DHTFindNodeReplyMessageTest.cc DHTGetPeersMessageTest.cc \
DHTGetPeersReplyMessageTest.cc DHTAnnouncePeerMessageTest.cc \
DHTAnnouncePeerReplyMessageTest.cc DHTUnknownMessageTest.cc \
- DHTMessageFactoryImplTest.cc BNodeTest.cc \
+ DHTMessageFactoryImplTest.cc DHTBucketTreeTest.cc \
DHTPeerAnnounceEntryTest.cc DHTPeerAnnounceStorageTest.cc \
DHTTokenTrackerTest.cc XORCloserTest.cc DHTIDCloserTest.cc \
DHTRoutingTableSerializerTest.cc \
@@ -350,7 +350,7 @@ am__aria2c_SOURCES_DIST = AllTest.cc TestUtil.cc TestUtil.h \
@ENABLE_BITTORRENT_TRUE@ DHTAnnouncePeerReplyMessageTest.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTUnknownMessageTest.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTMessageFactoryImplTest.$(OBJEXT) \
-@ENABLE_BITTORRENT_TRUE@ BNodeTest.$(OBJEXT) \
+@ENABLE_BITTORRENT_TRUE@ DHTBucketTreeTest.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTPeerAnnounceEntryTest.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTPeerAnnounceStorageTest.$(OBJEXT) \
@ENABLE_BITTORRENT_TRUE@ DHTTokenTrackerTest.$(OBJEXT) \
@@ -756,7 +756,6 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/AlphaNumberDecoratorTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/AnnounceListTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/AuthConfigFactoryTest.Po@am__quote@
-@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/BNodeTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Base32Test.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Base64Test.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Bencode2Test.Po@am__quote@
@@ -792,6 +791,7 @@ distclean-compile:
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTAnnouncePeerMessageTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTAnnouncePeerReplyMessageTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTBucketTest.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTBucketTreeTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTConnectionImplTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTFindNodeMessageTest.Po@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/DHTFindNodeReplyMessageTest.Po@am__quote@
generated by cgit (git 2.46.0) at 2026-10-12 03:08:35 +0000