部分代码来自于GitHub，词典文件为盗版，仅用于学习，禁止传播
Chord网络的模拟（90分）
（1）问题描述
Chord是一种非常经典的P2P结构化网络，可以在Chord上进行分布式P2P文件共享等应用。Chord网络的基本结构如图6-59所示，它是以分布式散列表为基础构建的一种逻辑网络。
分布式散列表（DHT）实际上是一个由大量结点分布式的共同维护的巨大散列表。散列表被分割成不连续的块，每个结点被分配给一个属于自己的散列块（一个散列值范围），并成为这个散列块的管理者，负责存储散列结果位于该散列块内的信息。DHT中使用的散列函数通常是加密散列函数（如MD5，SHA-1等），通过这些函数，一个对象的名字（如节点的ID或其IP地址）或关键词（如文件名）被映射为128位或160位的散列，如SHA-1（“202.38.64.1”）=24b92cb1d2b81a47472a93d06af3d85a42e463ea。一个采用DHT的系统内，所有计算结点、数据对象等被映射到一个空间内。对于图6-59中的Chord结构，每个计算节点根据其IP可以计算出其ID，如图中的N14。
每个文件根据其关键词可以计算出每个信息的ID，就是图中的K，如图中的K=hash（key）=54，这些K被放在Chord环中机器节点ID大于K且最近的K的节点，如图中将K=54的信息放在ID=56的节点N56上，将K=30和K=24的信息放在ID=32的节点N32上。
Chord结构主要支持如下操作：①Insert（key,V），即将关键词key对应的信息V对存放到节点ID大于K=hash（key）且离K最近的节点上，这样的ID可用Successor（K）表示，其中Successor（K）是从K开始顺时针方向距离K最近的节点。②Lookup（K），根据K查询相应的V，主要表现为根据Chord中节点的连接（上图中的节点间连线）路由到存放K的节点上，即节点ID=Successor（K）的节点，在该节点上可以找到K对应的V。③Update（K,new_V）：根据K更新相应的V。④Join（NID）：加入一个新节点，NID是节点的标识，如节点的IP地址，在Chord中加入一个节点需要建立相应的连接，需要移动信息数据，如上图中新加入一个节点N26，则需要将K=24移动到该节点。⑤Leave（）：某个节点主动离开Chord，在Chord中推出一个节点需要修改相应的连接，也需要移动某些信息数据，如上图中退出一个节点N14，则需要将K=10移动到节点N21。
Chord结构的一个非常重要的特点是如果每个节点仅维护其后继节点ID、IP地址等信息，则查询消息通过后继节点指针在圆环上传递，直到查询消息中包含的K落在某节点ID和它的后继节点ID之间，这样的查询速度太慢O（N），N为网络中节点数，如图6-60（a）所示。因此在基本Chord上，引入了一些能加快查询的finger表，finger表的结构如图6-60（b）表示，节点为ID的finger表中存放的是所有的（ID+2i）modN?ID的i从1开始且逐个增1的ID=Successor（ID+2i）的那些节点，每个i对应了finger表中的1项。有了finger表后，可以加速查询过程，对于路由中的任何一个节点ID，该节点选择的路由下一跳是finger表中满足（ID+2i）modN小于等于K且最接近K的那个i对应的表项，从这个表项中可以找到查询的下一跳，如图6-60（c）所示。
仔细分析可以发现，引入finger表后，查询K的路由跳数为O（logN），相比O（N）而言有很大的提高。
（2）课程设计目的
建立对Chord结构的认识，能用数据结构知识完成Chord结构的模拟。
（3）基本要求
①用数据结构知识设计和实现Chord网络结构。
②实现Chord结构上的Insert、Lookup、Update、Leave、Join五个操作。
③构建一个Chord的单机模拟应用，其中的数据信息可以自己定义，如可以定义key为一个一个的英语单词，而其对应的数据为该单词的英文解释。
④应模拟出各个操作的结果，尤其是模拟出Lookup的路由过程，模拟过程应该是可视的，即可以看到节点的连接，路由一跳一跳的过程，鼓励使用VC实现。
⑤用实验结果分析验证引入finger表后，查询K的路由跳数为O（logN）的理论结果。
（4）实现提示
可以查阅P2P中关于Chord的资料，其中用到的散列函数可以直接使用现有的散列函数，如SHA-1，可以直接下载使用散列函数的源代码。
代码：
头文件：
Chord.h
#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <vector>
using namespace std;
class Node;
class FingerTable {
public:
vector<Node*> fingerTable;
Node* local_node;
int nodeId;
FingerTable(int id, Node* node) {
this->nodeId = id;
this->local_node = node;
}
~FingerTable() {
this->nodeId = -99;
this->fingerTable.clear();
}
void printFingerTable();
};
class Node {
public:
uint64_t id;
Node* predecessor;
std::map<int, int> local_keys;
FingerTable *fingertable;
Node(int id) {
this->id = (int) id;
this->predecessor = NULL;
this->fingertable = new FingerTable(this->id, this);
}
~Node() {
this->id = INT64_MIN;
(this->local_keys).clear();
}
// Move keys (if any) to the newly added node
void moveKeys(Node* succ, int new_node_id) {
map<int, int> m;
map<int, int>::iterator iter;
for (map<int, int>::iterator iter = succ->local_keys.begin();
iter != succ->local_keys.end(); iter++) {
if (iter->first <= new_node_id
&& iter->first > succ->predecessor->id) {
insert_key_local(iter->first, iter->second);
} else {
m.insert(pair<int, int>(iter->first, iter->second));
}
}
succ->local_keys.clear();
succ->local_keys = m;
}
// Node join operation
void Join(Node* node) {
if (node == NULL) { // First node to join
for (int i = 0; i < 8; i++) {
fingertable->fingerTable.push_back(this);
}
predecessor = this;
} else {
for (int i = 0; i < 8; i++) {
fingertable->fingerTable.push_back(this);
}
// Find successor to attach to
Node* succ = node->find_successor(id);
// Update node's successor to point to the successor
fingertable->fingerTable[0] = succ;
// Update predecessor's successor to self
succ->predecessor->fingertable->fingerTable[0] = this;
// Update predecessor to successor's old predecessor
predecessor = succ->predecessor;
// move keys on the successor before changing predecessor
moveKeys(succ, id);
// Update successor's predecssor to self
succ->predecessor = this;
// update finger table
// fingerTable[0] is always the successor
createFingerTable();
}
}
// creates the finger table
void createFingerTable() {
for (int i = 1; i < fingertable->fingerTable.size(); i++) {
Node* ptr = this;
int flag = 0;
for (int j = 0; j < pow(2, i); j++) {
ptr = ptr->fingertable->fingerTable[0];
if (ptr == this) {
flag = 1;
break;
}
}
if (flag == 0) {
fingertable->fingerTable[i] = ptr;
}
}
}
// stabilize the finger tables
void stabilize() {
for (int i = 1; i < fingertable->fingerTable.size(); i++) {
fingertable->fingerTable[i]->createFingerTable();
}
}
// Find Successor
Node* find_successor(int id) {
if (this->id == id) {
return this;
}
else if (this->id > id) {
return this;
}
else if(this->id < id && this->fingertable->fingerTable[0]->id <= this->id) {
return this->fingertable->fingerTable[0];
}
else {
return fingertable->fingerTable[0]->find_successor(id);
}
}
// Search a key value pair
string LookUp(int key) {
int node_id = 0;
string ret_val;
cout << "\n Searching Key " << key << " on node " << id << endl;
node_id = local_key_lookup(key);
if (node_id >= 0) {
ret_val = " Found value - " + to_string(node_id) + " on Node - "
+ to_string(id) + "\n";
} else {
for (int i = 0; i < fingertable->fingerTable.size(); i++) {
node_id = fingertable->fingerTable[i]->local_key_lookup(key);
if (node_id >= 0) {
ret_val = " Found value - " + to_string(node_id) + " on Node - "
+ to_string(fingertable->fingerTable[i]->id) + "\n";
break;
}
else {
cout << "Found None" << endl;
}
}
}
return ret_val;
}
// Insert key
void Insert(int key, int value) {
if (key < 0) {
cerr << "\n *** Error Key is less than 0 *** \n";
return;
}
Node* succ = this->fingertable->fingerTable[0];
if (succ->id <= id && id <= key) {
succ->insert_key_local(key, value);
}
else if (predecessor->id > id && key > predecessor->id) {
insert_key_local(key, value);
}
else {
while (succ->id < key) {
succ = succ->fingertable->fingerTable[0];
}
succ->insert_key_local(key, value);
}
}
// Insert a key on this node
void insert_key_local(int key, int value) {
if (!key) {
cout << "No key provided to insert_key!" << endl;
}
local_keys.insert(pair<int, int>(key, value));
}
// Search a key locally
int local_key_lookup(int key) {
cout << " Node " << this->id << " searched" << endl;
int node = -1;
for (int i = 0; i < local_keys.size(); i++) {
if (local_keys.find(key)->first == key) {
node = local_keys.find(key)->second;
}
}
return node;
}
// Leave the chord ring and automatically move the info on it
void Leave() {
Node* succ = this->fingertable->fingerTable[0];
Node* pred = this->predecessor;
// Connect the predecessor's successor to this's successor
pred->fingertable->fingerTable[0] = succ;
// Connect the successor's predecessor to this's predecessor
succ->predecessor = pred;
// Rest of the nodes recreating the Finger Table
succ->createFingerTable();
pred->createFingerTable();
// // Insert the value to the rest nodes
for (map<int, int>::iterator iter = this->local_keys.begin(); iter != this->local_keys.end(); iter++) {
succ->Insert(iter->first, iter->second);
}
}
};
// Print Finger Table
void FingerTable::printFingerTable() {
cout << "\n**** Node ID : " << this->nodeId << " ****";
cout << "\nFingerTable\n";
for (int i = 0; i < fingerTable.size(); i++) {
if (i == 0 || (nodeId != fingerTable[i]->fingertable->nodeId)) {
cout << i + 1 << " : " << fingerTable[i]->fingertable->nodeId
<< "\n";
}
}
cout << "\nKeys : ";
for (map<int, int>::iterator iter = local_node->local_keys.begin();
iter != local_node->local_keys.end(); iter++) {
cout << iter->second << " ";
}
cout << "\n**********************\n";
}
Chord_sha1.h
#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <vector>
using namespace std;
class Node;
class FingerTable {
public:
vector<Node*> fingerTable;
Node* local_node;
string nodeId;
FingerTable(string id, Node* node) {
this->nodeId = id;
this->local_node = node;
}
~FingerTable() {
this->nodeId = "NULL";
this->fingerTable.clear();
}
void printFingerTable();
void printFingerTableWithoutKey();
};
class Node {
public:
string id;
Node* predecessor;
std::map<string, string> local_keys;
FingerTable *fingertable;
Node(string id) {
this->id = id;
this->predecessor = NULL;
this->fingertable = new FingerTable(this->id, this);
}
~Node() {
this->id = "NULL";
(this->local_keys).clear();
}
// Move keys (if any) to the newly added node
void moveKeys(Node* succ, string new_node_id) {
map<string, string> m;
map<string, string>::iterator iter;
for (map<string, string>::iterator iter = succ->local_keys.begin(); iter != succ->local_keys.end(); iter++) {
if (iter->first <= new_node_id && iter->first > succ->predecessor->id) {
insert_key_local(iter->first, iter->second);
} else {
m.insert(pair<string, string>(iter->first, iter->second));
}
}
succ->local_keys.clear();
succ->local_keys = m;
}
// Node join operation
void Join(Node* node) {
if (node == NULL) { // First node to join
for (int i = 0; i < 8; i++) {
fingertable->fingerTable.push_back(this);
}
predecessor = this;
} else {
for (int i = 0; i < 8; i++) {
fingertable->fingerTable.push_back(this);
}
// Find successor to attach to
Node* succ = node->find_successor(id);
// Update node's successor to point to the successor
fingertable->fingerTable[0] = succ;
// Update predecessor's successor to self
succ->predecessor->fingertable->fingerTable[0] = this;
// Update predecessor to successor's old predecessor
predecessor = succ->predecessor;
// move keys on the successor before changing predecessor
moveKeys(succ, id);
// Update successor's predecssor to self
succ->predecessor = this;
// update finger table
// fingerTable[0] is always the successor
createFingerTable();
}
}
// creates the finger table
void createFingerTable() {
for (int i = 1; i < fingertable->fingerTable.size(); i++) {
Node* ptr = this;
int flag = 0;
for (int j = 0; j < pow(2, i); j++) {
ptr = ptr->fingertable->fingerTable[0];
if (ptr == this) {
flag = 1;
break;
}
}
if (flag == 0) {
fingertable->fingerTable[i] = ptr;
}
}
}
// stabilize the finger tables
void stabilize() {
for (int i = 1; i < fingertable->fingerTable.size(); i++) {
fingertable->fingerTable[i]->createFingerTable();
}
}
// Find Successor
Node* find_successor(string id) {
if (this->id == id) {
return this;
}
else if (this->id > id) {
return this;
}
else if(this->id < id && this->fingertable->fingerTable[0]->id <= this->id) {
return this->fingertable->fingerTable[0];
}
else {
return fingertable->fingerTable[0]->find_successor(id);
}
}
// Search a key value pair
string LookUp(string key) {
string value = "NULL";
string ret_val;
cout << "Searching Key " << key << " on node " << id << endl;
value = local_key_lookup(key);
if (value != "NULL") {
ret_val = "Found value: " + value + " on Node: " + id + "\n";
}
else {
Node *t = this;
bool b = false;
for (int i = 0; i < 100; i++) {
b = false;
int j;
for(j = 0; j < t->fingertable->fingerTable.size(); j++) {
if(t->fingertable->fingerTable[j]->id > key) {
t = t->fingertable->fingerTable[j - 1];
b = true;
break;
}
}
if(!b) {
t = t->fingertable->fingerTable[j - 2];
}
// t->fingertable->printFingerTableWithoutKey();
value = t->fingertable->fingerTable[0]->local_key_lookup(key);
if (value != "NULL") {
ret_val = "Found value: " + value + " on Node: " + t->id + "\n";
break;
}
else {
cout << "Found None" << endl;
// t = t->fingertable->fingerTable[0];
if(t->fingertable->fingerTable[0]->id > key) {
ret_val = "Can't Find\n";
break;
}
}
}
}
return ret_val;
}
// Insert key
void Insert(string key, string value) {
Node* succ = this->fingertable->fingerTable[0];
if (succ->id <= id && id <= key) {
succ->insert_key_local(key, value);
}
else if (predecessor->id > id && key > predecessor->id) {
insert_key_local(key, value);
}
else {
while (succ->id < key) {
succ = succ->fingertable->fingerTable[0];
}
succ->insert_key_local(key, value);
}
}
// Insert a key on this node
void insert_key_local(string key, string value) {
if (key == "NULL") {
cout << "No key provided to insert_key!" << endl;
}
local_keys.insert(pair<string, string>(key, value));
}
// Search a key locally
string local_key_lookup(string key) {
cout << "Node " << this->id << " searched" << endl;
string value = "NULL";
for (int i = 0; i < local_keys.size(); i++) {
if(local_keys.find(key)->first == key) {
value = local_keys.find(key)->second;
}
}
return value;
}
void Leave(string id) {
find_successor(id)->_Leave();
stabilize();
}
// Leave the chord ring and automatically move the info on it
void _Leave() {
Node* succ = this->fingertable->fingerTable[0];
Node* pred = this->predecessor;
// Connect the predecessor's successor to this's successor
pred->fingertable->fingerTable[0] = succ;
// Connect the successor's predecessor to this's predecessor
succ->predecessor = pred;
// Rest of the nodes recreating the Finger Table
succ->createFingerTable();
pred->createFingerTable();
// // Insert the value to the rest nodes
for (map<string, string>::iterator iter = this->local_keys.begin(); iter != this->local_keys.end(); iter++) {
succ->Insert(iter->first, iter->second);
}
}
};
// Print Finger Table
void FingerTable::printFingerTable() {
cout << "**** Node ID : " << this->nodeId << " ****" << endl;
cout << "FingerTable" << endl;
for (int i = 0; i < fingerTable.size(); i++) {
if (i == 0 || (nodeId != fingerTable[i]->fingertable->nodeId)) {
cout << i + 1 << " : " << fingerTable[i]->fingertable->nodeId << endl;
}
}
cout << "Keys: " << endl;
for (map<string, string>::iterator iter = local_node->local_keys.begin(); iter != local_node->local_keys.end(); iter++) {
cout << iter->first << endl;
}
cout << "**********************" << endl;
}
void FingerTable::printFingerTableWithoutKey() {
cout << "**** Node ID : " << this->nodeId << " ****" << endl;
cout << "FingerTable" << endl;
for (int i = 0; i < fingerTable.size(); i++) {
if (i == 0 || (nodeId != fingerTable[i]->fingertable->nodeId)) {
cout << i + 1 << " : " << fingerTable[i]->fingertable->nodeId << endl;
}
}
cout << "**********************" << endl;
}
sha1.hpp
/*
sha1.hpp - source code of
============
SHA-1 in C++
============
100% Public Domain.
Original C Code
-- Steve Reid <steve@edmweb.com>
Small changes to fit into bglibs
-- Bruce Guenter <bruce@untroubled.org>
Translation to simpler C++ Code
-- Volker Diels-Grabsch <v@njh.eu>
Safety fixes
-- Eugene Hopkinson <slowriot at voxelstorm dot com>
Header-only library
-- Zlatko Michailov <zlatko@michailov.org>
*/
#ifndef SHA1_HPP
#define SHA1_HPP
#include <cstdint>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
class SHA1
{
public:
SHA1();
void update(const std::string &s);
void update(std::istream &is);
std::string final();
static std::string from_file(const std::string &filename);
private:
uint32_t digest[5];
std::string buffer;
uint64_t transforms;
};
static const size_t BLOCK_INTS = 16; /* number of 32bit integers per SHA1 block */
static const size_t BLOCK_BYTES = BLOCK_INTS * 4;
inline static void reset(uint32_t digest[], std::string &buffer, uint64_t &transforms)
{
/* SHA1 initialization constants */
digest[0] = 0x67452301;
digest[1] = 0xefcdab89;
digest[2] = 0x98badcfe;
digest[3] = 0x10325476;
digest[4] = 0xc3d2e1f0;
/* Reset counters */
buffer = "";
transforms = 0;
}
inline static uint32_t rol(const uint32_t value, const size_t bits)
{
return (value << bits) | (value >> (32 - bits));
}
inline static uint32_t blk(const uint32_t block[BLOCK_INTS], const size_t i)
{
return rol(block[(i+13)&15] ^ block[(i+8)&15] ^ block[(i+2)&15] ^ block[i], 1);
}
/*
* (R0+R1), R2, R3, R4 are the different operations used in SHA1
*/
inline static void R0(const uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
z += ((w&(x^y))^y) + block[i] + 0x5a827999 + rol(v, 5);
w = rol(w, 30);
}
inline static void R1(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
block[i] = blk(block, i);
z += ((w&(x^y))^y) + block[i] + 0x5a827999 + rol(v, 5);
w = rol(w, 30);
}
inline static void R2(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
block[i] = blk(block, i);
z += (w^x^y) + block[i] + 0x6ed9eba1 + rol(v, 5);
w = rol(w, 30);
}
inline static void R3(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
block[i] = blk(block, i);
z += (((w|x)&y)|(w&x)) + block[i] + 0x8f1bbcdc + rol(v, 5);
w = rol(w, 30);
}
inline static void R4(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i)
{
block[i] = blk(block, i);
z += (w^x^y) + block[i] + 0xca62c1d6 + rol(v, 5);
w = rol(w, 30);
}
/*
* Hash a single 512-bit block. This is the core of the algorithm.
*/
inline static void transform(uint32_t digest[], uint32_t block[BLOCK_INTS], uint64_t &transforms)
{
/* Copy digest[] to working vars */
uint32_t a = digest[0];
uint32_t b = digest[1];
uint32_t c = digest[2];
uint32_t d = digest[3];
uint32_t e = digest[4];
/* 4 rounds of 20 operations each. Loop unrolled. */
R0(block, a, b, c, d, e, 0);
R0(block, e, a, b, c, d, 1);
R0(block, d, e, a, b, c, 2);
R0(block, c, d, e, a, b, 3);
R0(block, b, c, d, e, a, 4);
R0(block, a, b, c, d, e, 5);
R0(block, e, a, b, c, d, 6);
R0(block, d, e, a, b, c, 7);
R0(block, c, d, e, a, b, 8);
R0(block, b, c, d, e, a, 9);
R0(block, a, b, c, d, e, 10);
R0(block, e, a, b, c, d, 11);
R0(block, d, e, a, b, c, 12);
R0(block, c, d, e, a, b, 13);
R0(block, b, c, d, e, a, 14);
R0(block, a, b, c, d, e, 15);
R1(block, e, a, b, c, d, 0);
R1(block, d, e, a, b, c, 1);
R1(block, c, d, e, a, b, 2);
R1(block, b, c, d, e, a, 3);
R2(block, a, b, c, d, e, 4);
R2(block, e, a, b, c, d, 5);
R2(block, d, e, a, b, c, 6);
R2(block, c, d, e, a, b, 7);
R2(block, b, c, d, e, a, 8);
R2(block, a, b, c, d, e, 9);
R2(block, e, a, b, c, d, 10);
R2(block, d, e, a, b, c, 11);
R2(block, c, d, e, a, b, 12);
R2(block, b, c, d, e, a, 13);
R2(block, a, b, c, d, e, 14);
R2(block, e, a, b, c, d, 15);
R2(block, d, e, a, b, c, 0);
R2(block, c, d, e, a, b, 1);
R2(block, b, c, d, e, a, 2);
R2(block, a, b, c, d, e, 3);
R2(block, e, a, b, c, d, 4);
R2(block, d, e, a, b, c, 5);
R2(block, c, d, e, a, b, 6);
R2(block, b, c, d, e, a, 7);
R3(block, a, b, c, d, e, 8);
R3(block, e, a, b, c, d, 9);
R3(block, d, e, a, b, c, 10);
R3(block, c, d, e, a, b, 11);
R3(block, b, c, d, e, a, 12);
R3(block, a, b, c, d, e, 13);
R3(block, e, a, b, c, d, 14);
R3(block, d, e, a, b, c, 15);
R3(block, c, d, e, a, b, 0);
R3(block, b, c, d, e, a, 1);
R3(block, a, b, c, d, e, 2);
R3(block, e, a, b, c, d, 3);
R3(block, d, e, a, b, c, 4);
R3(block, c, d, e, a, b, 5);
R3(block, b, c, d, e, a, 6);
R3(block, a, b, c, d, e, 7);
R3(block, e, a, b, c, d, 8);
R3(block, d, e, a, b, c, 9);
R3(block, c, d, e, a, b, 10);
R3(block, b, c, d, e, a, 11);
R4(block, a, b, c, d, e, 12);
R4(block, e, a, b, c, d, 13);
R4(block, d, e, a, b, c, 14);
R4(block, c, d, e, a, b, 15);
R4(block, b, c, d, e, a, 0);
R4(block, a, b, c, d, e, 1);
R4(block, e, a, b, c, d, 2);
R4(block, d, e, a, b, c, 3);
R4(block, c, d, e, a, b, 4);
R4(block, b, c, d, e, a, 5);
R4(block, a, b, c, d, e, 6);
R4(block, e, a, b, c, d, 7);
R4(block, d, e, a, b, c, 8);
R4(block, c, d, e, a, b, 9);
R4(block, b, c, d, e, a, 10);
R4(block, a, b, c, d, e, 11);
R4(block, e, a, b, c, d, 12);
R4(block, d, e, a, b, c, 13);
R4(block, c, d, e, a, b, 14);
R4(block, b, c, d, e, a, 15);
/* Add the working vars back into digest[] */
digest[0] += a;
digest[1] += b;
digest[2] += c;
digest[3] += d;
digest[4] += e;
/* Count the number of transformations */
transforms++;
}
inline static void buffer_to_block(const std::string &buffer, uint32_t block[BLOCK_INTS])
{
/* Convert the std::string (byte buffer) to a uint32_t array (MSB) */
for (size_t i = 0; i < BLOCK_INTS; i++)
{
block[i] = (buffer[4*i+3] & 0xff)
| (buffer[4*i+2] & 0xff)<<8
| (buffer[4*i+1] & 0xff)<<16
| (buffer[4*i+0] & 0xff)<<24;
}
}
inline SHA1::SHA1()
{
reset(digest, buffer, transforms);
}
inline void SHA1::update(const std::string &s)
{
std::istringstream is(s);
update(is);
}
inline void SHA1::update(std::istream &is)
{
while (true)
{
char sbuf[BLOCK_BYTES];
is.read(sbuf, BLOCK_BYTES - buffer.size());
buffer.append(sbuf, (std::size_t)is.gcount());
if (buffer.size() != BLOCK_BYTES)
{
return;
}
uint32_t block[BLOCK_INTS];
buffer_to_block(buffer, block);
transform(digest, block, transforms);
buffer.clear();
}
}
/*
* Add padding and return the message digest.
*/
inline std::string SHA1::final()
{
/* Total number of hashed bits */
uint64_t total_bits = (transforms*BLOCK_BYTES + buffer.size()) * 8;
/* Padding */
buffer += (char)0x80;
size_t orig_size = buffer.size();
while (buffer.size() < BLOCK_BYTES)
{
buffer += (char)0x00;
}
uint32_t block[BLOCK_INTS];
buffer_to_block(buffer, block);
if (orig_size > BLOCK_BYTES - 8)
{
transform(digest, block, transforms);
for (size_t i = 0; i < BLOCK_INTS - 2; i++)
{
block[i] = 0;
}
}
/* Append total_bits, split this uint64_t into two uint32_t */
block[BLOCK_INTS - 1] = (uint32_t)total_bits;
block[BLOCK_INTS - 2] = (uint32_t)(total_bits >> 32);
transform(digest, block, transforms);
/* Hex std::string */
std::ostringstream result;
for (size_t i = 0; i < sizeof(digest) / sizeof(digest[0]); i++)
{
result << std::hex << std::setfill('0') << std::setw(8);
result << digest[i];
}
/* Reset for next run */
reset(digest, buffer, transforms);
return result.str();
}
inline std::string SHA1::from_file(const std::string &filename)
{
std::ifstream stream(filename.c_str(), std::ios::binary);
SHA1 checksum;
checksum.update(stream);
return checksum.final();
}
#endif /* SHA1_HPP */
dic.h
#include "Chord_sha1.h"
#include "sha1.hpp"
using namespace std;
static int MaxNum = 100;
// 使用字符分割
void Stringsplit(const string& str, const char split, vector<string>& res)
{
// int i = 0;
if (str == ""){
return;
}
//在字符串末尾也加入分隔符，方便截取最后一段
string strs = str + split;
size_t pos = strs.find(split);
// 若找不到内容则字符串搜索函数返回 npos
while (pos != strs.npos)
{
string temp = strs.substr(0, pos);
res.push_back(temp);
//去掉已分割的字符串,在剩下的字符串中进行分割
strs = strs.substr(pos + 1, strs.size());
pos = strs.find(split);
}
}
int Charge(Node *n0) {
SHA1 sha1;
ifstream srcFile("dic.txt", ios::in); //以文本模式打开dic.txt备读
if (!srcFile) { //打开失败
cout << "文件读取失败" << endl;
return -1;
}
cout << "文件打开成功" << endl;
int n;
for(n = 1; n < MaxNum; n++) {
sha1.update(to_string(n));
Node *node = new Node(sha1.final());
node->Join(n0);
}
Node *t = n0;
int i = 0;
for(i = 0; i < MaxNum; i++) {
t->stabilize();
t = t->fingertable->fingerTable[0];
}
cout << "结点加入成功" << endl;
//存储
string s1;
vector<string> s2;
while(getline(srcFile, s1, '\n')) {
Stringsplit(s1, ' ', s2);
sha1.update(s2[0]);
string s = sha1.final();
n0->Insert(s, s2[2]);
// cout << s2[0] << endl;
s2.clear();
}
return 0;
}
CPP文件：
展示用：Chord.cpp
#include "Chord_sha1.h"
#include "sha1.hpp"
int StopFun() {
int i;
while(1) {
std::cout << "是否要退出？（1.退出/0.返回）" << std::endl;
std::cin >> i;
if(i == 1) {
return 1;
}
else if(i == 0) {
return 0;
}
else {
std::cout << "输入错误！" << std::endl;
}
}
}
int main() {
int index;
int TotalNum = 1;
bool tag = true;
SHA1 sha1;
// n0 join
Node* n0 = new Node("0");
n0->Join(NULL);
cout << "N0(0)结点初始化完成" << endl;
while(tag) {
system("CLS");
cout << "********************************" << endl;
cout << "* 1.插入Insert *" << endl;
cout << "* 2.查询Lookup *" << endl;
cout << "* 3.加入新结点Join *" << endl;
cout << "* 4.退出结点Leave *" << endl;
cout << "* 5.更新结点Update *" << endl;
cout << "* 6.打印结点信息 *" << endl;
cout << "* -1.退出 *" << endl;
cout << "********************************" << endl;
cout << "请输入序号：" << endl;
cin >> index;
switch (index)
{
case 1:
system("CLS");
{
cout << "输入插入数据的key：" << endl;
string key;
cin >> key;
sha1.update(key);
cout << "输入插入数据的信息：" << endl;
string value;
cin >> value;
n0->Insert(sha1.final(), value);
cout << "信息已插入" << endl;
}
system("pause");
break;
case 2:
system("CLS");
{
cout << "输入查询数据的key：" << endl;
string key;
cin >> key;
sha1.update(key);
string s = sha1.final();
cout << "对应Sha-1散列值为：" << s << endl;
cout << n0->LookUp(s) << endl;
}
system("pause");
break;
case 3:
system("CLS");
{
cout << "输入加入结点序号：" << endl;
int n;
cin >> n;
sha1.update(to_string(n));
string s = sha1.final();
Node *node = new Node(s);
node->Join(n0);
// node->fingertable->printFingerTable();
// node->stabilize();
// node->fingertable->printFingerTable();
cout << "新结点已加入" << endl;
cout << "对应Sha-1散列值为：" << s << endl;
TotalNum++;
}
system("pause");
break;
case 4:
system("CLS");
{
cout << "输入退出结点序号：" << endl;
int n;
cin >> n;
sha1.update(to_string(n));
string s = sha1.final();
n0->Leave(s);
cout << "结点已退出" << endl;
TotalNum--;
}
system("pause");
break;
case 5:
system("CLS");
{
Node *t = n0;
int i = 0;
for(i = 0; i < TotalNum; i++) {
t->stabilize();
t = t->fingertable->fingerTable[0];
}
}
system("pause");
break;
case 6:
system("CLS");
{
Node *t = n0;
int i = 0;
for(i = 0; i < TotalNum; i++) {
t->fingertable->printFingerTable();
t = t->fingertable->fingerTable[0];
}
}
system("pause");
break;
case -1:
system("CLS");
{
int x = StopFun();
if(x == 1) {
tag = false;
break;
}
else {
break;
}
}
default:
cout << "请选择正确序号！" << endl;
system("pause");
break;
}
}
system("pause");
return 0;
}
英文词典：Dictionary.cpp
#include <bits/stdc++.h>
#include "dic.h"
using namespace std;
int StopFun() {
int i;
while(1) {
std::cout << "是否要退出？（1.退出/0.返回）" << std::endl;
std::cin >> i;
if(i == 1) {
return 1;
}
else if(i == 0) {
return 0;
}
else {
std::cout << "输入错误！" << std::endl;
}
}
}
int main() {
int TotalNum = 100;
int index;
bool tag = true;
SHA1 sha1;
// n0 join
Node* n0 = new Node("0");
n0->Join(NULL);
cout << "N0(0)结点初始化完成" << endl;
int n = Charge(n0);
if(n == -1) {
return 0;
}
system("pause");
while(tag) {
system("CLS");
cout << "*************************" << endl;
cout << "* 1.搜索 *" << endl;
cout << "* 2.打印结点 *" << endl;
cout << "* -1.退出 *" << endl;
cout << "**************************" << endl;
cout << "请输入序号：" << endl;
cin >> index;
switch (index)
{
case 1:
system("CLS");
{
string s;
cout << "输入查询的单词：" << endl;
cin >> s;
sha1.update(s);
cout << n0->LookUp(sha1.final()) << endl;
}
system("pause");
break;
case 2:
system("CLS");
{
Node *t = n0;
int i = 0;
for(i = 0; i < TotalNum; i++) {
cout << i + 1 << endl;
t->fingertable->printFingerTableWithoutKey();
t = t->fingertable->fingerTable[0];
}
}
system("pause");
break;
case -1:
system("CLS");
{
int x = StopFun();
if(x == 1) {
tag = false;
break;
}
else {
break;
}
}
default:
cout << "请选择正确序号！" << endl;
system("pause");
break;
}
}
return 0;
}
词典文件：
链接：/s/12UapWwi2-jVDneO6HSrAtg?
提取码：hell
可能仍有BUG
未实现VC可视化与验证实验结果
|