From 6d220177b1e0e13ac9d16c7ca87ed2ded652a175 Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 10:33:32 +0100 Subject: server: add hashtable foundation --- src/server/hashtable.h | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) create mode 100644 src/server/hashtable.h (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h new file mode 100644 index 0000000..0fd0d2b --- /dev/null +++ b/src/server/hashtable.h @@ -0,0 +1,19 @@ +#pragma once + +#include +#include + +template +class HashTable { +public: + HashTable(size_t size) + : size { size } + , table(size) + { + } + +private: + size_t size; + + std::vector>> table; +}; -- cgit 1.4.1 From 8f0c081c188a526ff2bd7115b31e48c4ed5bd47d Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 10:35:43 +0100 Subject: server: add hashtable util functions --- src/server/hashtable.h | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h index 0fd0d2b..9d31cfc 100644 --- a/src/server/hashtable.h +++ b/src/server/hashtable.h @@ -1,5 +1,6 @@ #pragma once +#include #include #include @@ -16,4 +17,24 @@ private: size_t size; std::vector>> table; + + std::hash hash_function; + + auto bucket_find_key(std::list> list, K key) + { + return std::find_if(list.begin(), list.end(), [&key](const std::pair& pair) { + return pair.first == key; + }); + } + + bool bucket_contains_key(std::list> list, K key) + { + return bucket_find_key(list, key) != list.end(); + } + + std::list> get_bucket(K key) + { + size_t index = hash_function(key) % size; + return table.at(index); + } }; -- cgit 1.4.1 From 5f6896c62e382a930415514afce4c81c22346d1d Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 10:36:07 +0100 Subject: server: add hashtable insert --- src/server/hashtable.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h index 9d31cfc..9fd0752 100644 --- a/src/server/hashtable.h +++ b/src/server/hashtable.h @@ -13,6 +13,18 @@ public: { } + bool insert(K key, V value) + { + std::list> list = get_bucket(key); + + if (bucket_contains_key(list, key)) { + return false; + } + + list.insert(value); + return true; + } + private: size_t size; -- cgit 1.4.1 From 88cf221363433664d45d9431535934f28768166c Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 10:36:20 +0100 Subject: server: add hashtable get --- src/server/hashtable.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h index 9fd0752..735af26 100644 --- a/src/server/hashtable.h +++ b/src/server/hashtable.h @@ -25,6 +25,18 @@ public: return true; } + std::optional get(K key) + { + std::list> list = get_bucket(key); + + auto iter = bucket_find_key(list, key); + if (iter != list.end()) { + return std::optional((*iter).second); + } + + return std::optional(); + } + private: size_t size; -- cgit 1.4.1 From 5ffee8c7163e2324bd35b8d99fc69012c2f31578 Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 10:36:43 +0100 Subject: server: add hashtable removed --- src/server/hashtable.h | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h index 735af26..ad4882b 100644 --- a/src/server/hashtable.h +++ b/src/server/hashtable.h @@ -2,6 +2,7 @@ #include #include +#include #include template @@ -37,6 +38,19 @@ public: return std::optional(); } + bool remove(K key) + { + std::list> list = get_bucket(key); + + auto iter = bucket_find_key(list, key); + if (iter != list.end()) { + list.erase(iter); + return true; + } + + return false; + } + private: size_t size; -- cgit 1.4.1 From 4aebe4d2a16096bfbaf3e7c2726831db0e42a322 Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 12:03:53 +0100 Subject: server: add hashtable print method --- src/server/hashtable.h | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h index ad4882b..daca492 100644 --- a/src/server/hashtable.h +++ b/src/server/hashtable.h @@ -1,6 +1,7 @@ #pragma once #include +#include #include #include #include @@ -51,6 +52,18 @@ public: return false; } + void print() + { + size_t index { 0 }; + for (auto bucket : table) { + std::cout << "Bucket " << index++ << ": ["; + for (auto pair : bucket) { + std::cout << "(" << pair.first << ", " << pair.second << ")"; + } + std::cout << "]" << "\n"; + } + } + private: size_t size; -- cgit 1.4.1 From e8abcfc7425167e96bf00a8b79de9a30ee2e2800 Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 12:04:25 +0100 Subject: server: fix reference issues of hashtable --- src/server/hashtable.h | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) (limited to 'src/server') diff --git a/src/server/hashtable.h b/src/server/hashtable.h index daca492..0989a79 100644 --- a/src/server/hashtable.h +++ b/src/server/hashtable.h @@ -17,19 +17,20 @@ public: bool insert(K key, V value) { - std::list> list = get_bucket(key); + std::list>& list = get_bucket(key); if (bucket_contains_key(list, key)) { return false; } - list.insert(value); + list.push_back(std::pair(key, value)); + return true; } std::optional get(K key) { - std::list> list = get_bucket(key); + std::list>& list = get_bucket(key); auto iter = bucket_find_key(list, key); if (iter != list.end()) { @@ -41,7 +42,7 @@ public: bool remove(K key) { - std::list> list = get_bucket(key); + std::list>& list = get_bucket(key); auto iter = bucket_find_key(list, key); if (iter != list.end()) { @@ -71,19 +72,19 @@ private: std::hash hash_function; - auto bucket_find_key(std::list> list, K key) + auto bucket_find_key(std::list>& list, K key) { return std::find_if(list.begin(), list.end(), [&key](const std::pair& pair) { return pair.first == key; }); } - bool bucket_contains_key(std::list> list, K key) + bool bucket_contains_key(std::list>& list, K key) { - return bucket_find_key(list, key) != list.end(); + return list.begin() != list.end() && bucket_find_key(list, key) != list.end(); } - std::list> get_bucket(K key) + std::list>& get_bucket(K key) { size_t index = hash_function(key) % size; return table.at(index); -- cgit 1.4.1 From afbafc29ab11c17c2b90dd5e645f1943490c276a Mon Sep 17 00:00:00 2001 From: Christian Krinitsin Date: Thu, 20 Mar 2025 12:04:49 +0100 Subject: server: add a sample main function, which tests the hashtable --- server/src/main.cpp | 11 ----------- src/server/main.cpp | 30 ++++++++++++++++++++++++++++++ 2 files changed, 30 insertions(+), 11 deletions(-) delete mode 100644 server/src/main.cpp create mode 100644 src/server/main.cpp (limited to 'src/server') diff --git a/server/src/main.cpp b/server/src/main.cpp deleted file mode 100644 index 26bee21..0000000 --- a/server/src/main.cpp +++ /dev/null @@ -1,11 +0,0 @@ -#include - -int main(int argc, char* argv[]) -{ - if (argc != 2) { - std::printf("The size of the hash table is needed"); - return 1; - } - - return 0; -} diff --git a/src/server/main.cpp b/src/server/main.cpp new file mode 100644 index 0000000..de99edb --- /dev/null +++ b/src/server/main.cpp @@ -0,0 +1,30 @@ +#include + +#include "hashtable.h" + +int main(int argc, char* argv[]) +{ + HashTable hash_table { 5 }; + + std::cout << "Add various kv-pairs" << '\n'; + hash_table.insert(1, "1"); + hash_table.insert(2, "2"); + hash_table.insert(3, "3"); + hash_table.insert(4, "4"); + hash_table.insert(5, "5"); + hash_table.insert(6, "6"); + hash_table.insert(7, "7"); + + hash_table.print(); + + std::cout << '\n'; + + std::cout << "Value for key 8: " << hash_table.get(8).value_or("Key not found!") << '\n'; + std::cout << "Value for key 4: " << hash_table.get(4).value_or("Key not found!") << '\n'; + + std::cout << '\n'; + std::cout << "Remove pair with key 5" << '\n'; + hash_table.remove(5); + hash_table.print(); + +} -- cgit 1.4.1