#ifndef CHASH_HPP #define CHASH_HPP #include #include #include #include #include template> class ConcurrentHash { private: class Bucket { private: struct Node { Node(const Key& key, const Value& value) : key(key), value(value), next(nullptr) { } std::shared_ptr next; Key key; Value value; }; std::shared_ptr list; mutable std::shared_mutex mutex; public: Bucket() : list(nullptr) { } void add_or_update(const Key& key, const Value& value) { std::unique_lock lock(mutex); std::shared_ptr ptr = list; std::shared_ptr prev = nullptr; while (ptr && ptr->key != key) { prev = ptr; ptr = ptr->next; } if (ptr) { ptr->value = value; } else { ptr = std::make_shared(key, value); if (prev) { prev->next = ptr; } else { list = ptr; } } } bool lookup(const Key& key, Value& value) const { std::shared_lock lock(mutex); std::shared_ptr ptr = list; while (ptr && ptr->key != key) { ptr = ptr->next; } if (ptr) { value = ptr->value; return true; } else { return false; } } void remove(const Key& key) { std::unique_lock lock(mutex); std::shared_ptr ptr = list; std::shared_ptr prev = nullptr; while (ptr && ptr->key != key) { prev = ptr; ptr = ptr->next; } if (ptr) { if (prev) { prev->next = ptr->next; } else { list = ptr->next; } } } }; std::vector buckets; Hash hash; public: ConcurrentHash(std::size_t nofbuckets = 32) : buckets(nofbuckets) { } void add_or_update(const Key& key, const Value& value) { std::size_t index = hash(key) % buckets.size(); buckets[index].add_or_update(key, value); } void remove(const Key& key) { std::size_t index = hash(key) % buckets.size(); buckets[index].remove(key); } bool lookup(const Key& key, Value& value) const { std::size_t index = hash(key) % buckets.size(); return buckets[index].lookup(key, value); } }; #endif