Vladislav_Bezruk

distributed hash table (dht)

Dec 3rd, 2021 (edited)
894
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <stdlib.h>
  5. #include <time.h>
  6. #include <conio.h>
  7.  
  8. using namespace std;
  9.  
  10. /*Індетифікатор адреси*/
  11. #define ADDRESS_IND                 '@'
  12.  
  13. /*Розмір хеш таблиці для даних*/
  14. #define HASHTABLE_DATA_SIZE         5
  15.  
  16. /*Розмір хеш таблиці для адрес*/
  17. #define HASHTABLE_CONNECTIONS_SIZE  5
  18.  
  19. /*Кількість серверів*/
  20. #define SERVERS_COUNT               12
  21.  
  22. /*Вхідний файл з даними про лікарські рослини*/
  23. #define INPUT_DATA_FILENAME         "input_data.txt"
  24.  
  25. /*Матриця зв'язків між серверами*/
  26. bool serversConnections[SERVERS_COUNT][SERVERS_COUNT] = {
  27.     {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
  28.     {1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0},
  29.     {1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0},
  30.     {0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0},
  31.     {1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
  32.     {0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
  33.     {0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
  34.     {0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
  35.     {0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
  36.     {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
  37.     {0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1},
  38.     {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}
  39. };
  40.  
  41. template <typename keyT, typename dataT> class Server;
  42.  
  43. /*Структура елементу хеш таблиці*/
  44. template <typename keyT, typename dataT> struct Node {
  45.     keyT key;           //ключ
  46.     dataT data;         //дані
  47.     Node* next = NULL;  //адреса на наступний елемент
  48.  
  49.     Node(keyT _key, dataT _data) : key(_key), data(_data) {}
  50. };
  51.  
  52. /*Клас хеш таблиці*/
  53. template <typename keyT, typename dataT> class HashTable {
  54.     protected:
  55.         Node<keyT, dataT>** table;  //хеш таблиці
  56.         unsigned int records;               //кількість записів
  57.         unsigned int size;                  //розмір таблиці
  58.  
  59.         /*Хеш функція*/
  60.         unsigned int hashFunc(keyT key) {
  61.             int sum = 0;
  62.             for (int i = 0; i < key.length(); i++)
  63.                 sum += key[i];
  64.             return sum % size;
  65.         }
  66.  
  67.     public:
  68.         HashTable(int _size) : size(_size) {
  69.             records = 0;
  70.             table = new Node<keyT, dataT>*[size];
  71.  
  72.             for (int i = 0; i < size; i++)
  73.                 table[i] = NULL;
  74.         }
  75.  
  76.         /*Функція додавання нового елемента*/
  77.         void push(keyT key, dataT data) {
  78.             records++;
  79.             unsigned int hashNumber = hashFunc(key);
  80.  
  81.             Node<keyT, dataT>* newNode = new Node<keyT, dataT>(key, data);
  82.             Node<keyT, dataT>* hashNode = table[hashNumber];
  83.  
  84.             if (hashNode == NULL) {
  85.                 table[hashNumber] = newNode;
  86.             } else {
  87.                 while (hashNode->next)
  88.                     hashNode = hashNode->next;
  89.                 hashNode->next = newNode;
  90.             }
  91.         }
  92.  
  93.         /*Функція знаходження елемента*/
  94.         Node<keyT, dataT>* find(keyT key) {
  95.             unsigned int hashNumber = hashFunc(key);
  96.  
  97.             Node<keyT, dataT>* hashNode = table[hashNumber];
  98.  
  99.             while (hashNode) {
  100.                 if (hashNode->key == key)
  101.                     return hashNode;
  102.                 hashNode = hashNode->next;
  103.             }
  104.             return NULL;
  105.         }
  106.  
  107.         /*Функція видалення елемента*/
  108.         void pop(keyT key) {
  109.             unsigned int hashNumber = hashFunc(key);
  110.  
  111.             Node<keyT, dataT>* hashNode = table[hashNumber];
  112.             Node<keyT, dataT>* preNode;
  113.             preNode->next;
  114.  
  115.             while (hashNode) {
  116.                 if (hashNode->key == key) {
  117.                     records--;
  118.                     if (hashNode->next == NULL) {
  119.                         if (table[hashNumber]->key == key) {
  120.                             table[hashNumber] = NULL;
  121.                         } else {
  122.                             (*preNode).next = NULL;
  123.                         }
  124.                     } else {
  125.                         *hashNode = *hashNode->next;
  126.                     }
  127.                     return;
  128.                 }
  129.                 preNode = hashNode;
  130.                 hashNode = hashNode->next;
  131.             }
  132.         }
  133.  
  134.         /*Функція друкування усіх ключів*/
  135.         void printKeys() {
  136.             keyT* keys = getKeys();
  137.  
  138.             for (int i = 0; i < records; i++)
  139.                 cout << "- " << keys[i] << endl;
  140.  
  141.             if (records == 0)
  142.                 cout << "Noting." << endl;
  143.         }
  144.  
  145.         /*Функція знаходження усіх ключів*/
  146.         keyT* getKeys() {
  147.             keyT* keys = NULL;
  148.             int k = 0;
  149.  
  150.             if (records)
  151.                 keys = new keyT[records];
  152.  
  153.             for (int i = 0; i < size; i++) {
  154.                 Node<keyT, dataT>* hashNode = table[i];
  155.  
  156.                 while (hashNode != NULL) {
  157.                     keys[k++] = hashNode->key;
  158.                     hashNode = hashNode->next;
  159.                 }
  160.             }
  161.             return keys;
  162.         }
  163. };
  164.  
  165. /*Клас інтерфйсу для зв'язку між серврами*/
  166. template <typename keyT, typename dataT> class Interface : public HashTable<keyT, Server<keyT, dataT>*> {
  167.     protected:
  168.         unsigned int nConn; //кількість підключень сервера
  169.  
  170.     public:
  171.         Interface(int _mConn) : HashTable<keyT, Server<keyT, dataT>*>(_mConn) {}
  172.  
  173.         /*Додати нове з'єднання*/
  174.         void addConnection(Server<keyT, dataT>* pAdress) {
  175.             HashTable<keyT, Server<keyT, dataT>*>::push(pAdress->getAdress(), pAdress);
  176.         }
  177.  
  178.         /*Додати з'єднання*/
  179.         void removeConnection(keyT address) {
  180.             HashTable<keyT, Server<keyT, dataT>*>::pop(address);
  181.         }
  182.  
  183.         /*Відправити інформацію про додавання нових даних іншим серверам*/
  184.         void sendAddInfo(keyT key, string address) {
  185.             keyT* keys = HashTable<string, Server<keyT, dataT>*>::getKeys();
  186.  
  187.             for (int i = 0; i < HashTable<keyT, Server<keyT, dataT>*>::records; i++) {
  188.                 Server<keyT, dataT>* pAdress = HashTable<string, Server<keyT, dataT>*>::find(keys[i])->data;
  189.                 pAdress->addData(key, address);
  190.             }
  191.         }
  192.  
  193.         /*Відправити інформацію про отримання даних іншим серверам*/
  194.         Node<keyT, dataT>* sendGetInfo(keyT key, string address) {
  195.             Node<keyT, Server<keyT, dataT>*>* node = HashTable<keyT, Server<keyT, dataT>*>::find(address);
  196.  
  197.             if (node)
  198.                 return node->data->getData(key);
  199.             return NULL;
  200.         }
  201.  
  202.         /*Відправити інформацію про видалення даних іншим серверам*/
  203.         void sendRemoveInfo(keyT key) {
  204.             Node<keyT, Server<keyT, dataT>*>* hashNode;
  205.             for (int i = 0; i < HashTable<keyT, Server<keyT, dataT>*>::size; i++) {
  206.                 hashNode = HashTable<keyT, Server<keyT, dataT>*>::table[i];
  207.  
  208.                 while (hashNode) {
  209.                     hashNode->data->removeData(key);
  210.                     hashNode = hashNode->next;
  211.                 }
  212.             }
  213.         }
  214. };
  215.  
  216. /*Клас сервера*/
  217. template <typename keyT, typename dataT> class Server : public HashTable<keyT, dataT>, public Interface<keyT, dataT> {
  218.     private:
  219.         string adress; //адреса сервера (ip адрес)
  220.  
  221.     public:
  222.         Server(int _size, int _mConn, string _adress) : HashTable<keyT, dataT>(_size), Interface<keyT, dataT>(_mConn), adress(_adress) {};
  223.  
  224.         /*Функція отримання адреси*/
  225.         string getAdress() {
  226.             return adress;
  227.         }
  228.  
  229.         /*Функція додавання даних до сервера*/
  230.         void addData(keyT key, dataT data) {
  231.             if (HashTable<keyT, dataT>::find(key) == NULL) {
  232.                 HashTable<keyT, dataT>::push(key, data);
  233.                 Interface<keyT, dataT>::sendAddInfo(key, adress);
  234.             }
  235.         }
  236.  
  237.         /*Функція отримання даних із сервера*/
  238.         Node<keyT, dataT>* getData(keyT key) {
  239.             Node<keyT, dataT>* node = HashTable<keyT, dataT>::find(key);
  240.  
  241.             if (node) {
  242.                 if (node->data[0] == ADDRESS_IND)
  243.                     return Interface<keyT, dataT>::sendGetInfo(key, node->data);
  244.                 return node;
  245.             }
  246.             return NULL;
  247.         }
  248.  
  249.         /*Функція видалення даних із сервера*/
  250.         void removeData(keyT key) {
  251.             Node<keyT, dataT>* node = HashTable<keyT, dataT>::find(key);
  252.  
  253.             if (node) {
  254.                 HashTable<keyT, dataT>::pop(key);
  255.                 Interface<keyT, dataT>::sendRemoveInfo(key);
  256.             }
  257.         }
  258. };
  259.  
  260. /*Клас розподіленої хеш таблиці*/
  261. template <typename keyT, typename dataT> class DHashTable {
  262.     private:
  263.         unsigned int serversCount;              //кількість серверів
  264.         unsigned int hashtableDataSize;         //розмір хеш таблиці для даних
  265.         unsigned int hashtableConnectionsSize;  //розмір хеш таблиці для адрес серверів
  266.         Server<keyT, dataT>** servers;          //набір серверів
  267.  
  268.     public:
  269.         DHashTable(int a, int b, int c, bool serversConnections[SERVERS_COUNT][SERVERS_COUNT]) : serversCount(a), hashtableDataSize(b), hashtableConnectionsSize(c) {
  270.             srand(time(NULL));
  271.  
  272.             servers = new Server<keyT, dataT>*[serversCount];
  273.  
  274.             for (int i = 0; i < serversCount; i++)
  275.                 servers[i] = new Server<keyT, dataT>(hashtableDataSize, hashtableConnectionsSize, ADDRESS_IND + to_string(i + 1));
  276.  
  277.             for (int i = 0; i < serversCount; i++)
  278.                 for (int j = 0; j < serversCount; j++)
  279.                     if (i != j && serversConnections[i][j])
  280.                         servers[i]->addConnection(servers[j]);
  281.         }
  282.  
  283.         /*Функція додавання даних до розподіленої хеш таблиці*/
  284.         void push(keyT key, dataT data) {
  285.             int adress = rand() % serversCount;
  286.  
  287.             servers[adress]->addData(key, data);
  288.         }
  289.  
  290.         /*Функція знаходження даних у розподіленій хеш таблиці*/
  291.         dataT find(keyT key) {
  292.             int adress = rand() % serversCount;
  293.  
  294.             Node<keyT, dataT>* node = servers[adress]->getData(key);
  295.  
  296.             if (node) return node->data;
  297.             return "None";
  298.         }
  299.  
  300.         /*Функція видалення даних із розподіленої хеш таблиці*/
  301.         void pop(keyT key) {
  302.             int adress = rand() % serversCount;
  303.  
  304.             servers[adress]->removeData(key);
  305.         }
  306.  
  307.         /*Функція друкування ключів розподіленої хеш таблиці*/
  308.         void printKeys() {
  309.             int adress = rand() % serversCount;
  310.  
  311.             servers[adress]->HashTable<keyT, dataT>::printKeys();
  312.         }
  313. };
  314.  
  315. /*Функція занесення початкових даних із файлу до розподіленої хеш таблиці*/
  316. void pushInputData(DHashTable<string, string>& dHashTable) {
  317.     ifstream ifs(INPUT_DATA_FILENAME);
  318.     int n;
  319.     string key, data;
  320.  
  321.     ifs >> n;
  322.     getline(ifs, key);
  323.  
  324.     for (int i = 0; i < n; i++) {
  325.         getline(ifs, key);
  326.         getline(ifs, data);
  327.         dHashTable.push(key, data);
  328.         ifs.clear();
  329.     }
  330. }
  331.  
  332. int main() {
  333.     DHashTable<string, string> dHashTable(SERVERS_COUNT, HASHTABLE_DATA_SIZE, HASHTABLE_CONNECTIONS_SIZE, serversConnections);
  334.  
  335.     pushInputData(dHashTable);
  336.  
  337.     string command, key, data;
  338.  
  339.     while (true) {
  340.         system("CLS");
  341.         cout << "=================================" << endl;
  342.         cout << "==directory=of=medicinal=plants==" << endl;
  343.         cout << "============based=on=============" << endl;
  344.         cout << "=====distributed=hash=table======" << endl;
  345.         cout << "=================================" << endl << endl;
  346.  
  347.         cout << "All plants in directory:" << endl;
  348.         dHashTable.printKeys();
  349.         cout << endl;
  350.  
  351.         cout << "To add new record:" << endl;
  352.         cout << "/add [name] [data]" << endl << endl;
  353.         cout << "To remove record:" << endl;
  354.         cout << "/remove [name]" << endl << endl;
  355.         cout << "To get info:" << endl;
  356.         cout << "/get [name]" << endl << endl;
  357.         cout << "@dhashtable: ";
  358.         cin >> command;
  359.  
  360.         if (command == "/add") {
  361.             cout << "Name:" << endl;
  362.             cin.ignore();
  363.             getline(cin, key);
  364.             cout << endl << "Data:" << endl;
  365.             getline(cin, data);
  366.  
  367.             dHashTable.push(key, data);
  368.  
  369.         } else if (command == "/remove") {
  370.             cout << "Name:" << endl;
  371.             cin.ignore();
  372.             getline(cin, key);
  373.             dHashTable.pop(key);
  374.  
  375.         } else if (command == "/get") {
  376.             cout << "Name:" << endl;
  377.             cin.ignore();
  378.             getline(cin, key);
  379.  
  380.             cout << endl << "Result data:" << endl;
  381.             cout << dHashTable.find(key) << endl;
  382.  
  383.         } else {
  384.             cout << endl << '"' << command << '"' << " is not recognized!" << endl;
  385.         }
  386.         cout << endl << "Press any key ..." << endl;
  387.         _getch();
  388.     }
  389.  
  390.     return 0;
  391. }
RAW Paste Data