#ifndef CHASH_HPP
#define CHASH_HPP

#include <cstdlib>
#include <memory>
#include <mutex>
#include <shared_mutex>
#include <vector>

template<typename Key, typename Value, typename Hash = std::hash<Key>>
class ConcurrentHash {
   private:
      class Bucket {
	 private:
	    struct Node {
	       Node(const Key& key, const Value& value) :
		     key(key), value(value), next(nullptr) {
	       }
	       std::shared_ptr<Node> next;
	       Key key;
	       Value value;
	    };
	    std::shared_ptr<Node> list;
	    mutable std::shared_mutex mutex;

	 public:
	    Bucket() : list(nullptr) {
	    }
	    void add_or_update(const Key& key, const Value& value) {
	       std::unique_lock<std::shared_mutex> lock(mutex);
	       std::shared_ptr<Node> ptr = list;
	       std::shared_ptr<Node> prev = nullptr;
	       while (ptr && ptr->key != key) {
		  prev = ptr; ptr = ptr->next;
	       }
	       if (ptr) {
		  ptr->value = value;
	       } else {
		  ptr = std::make_shared<Node>(key, value);
		  if (prev) {
		     prev->next = ptr;
		  } else {
		     list = ptr;
		  }
	       }
	    }
	    bool lookup(const Key& key, Value& value) const {
	       std::shared_lock<std::shared_mutex> lock(mutex);
	       std::shared_ptr<Node> 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<std::shared_mutex> lock(mutex);
	       std::shared_ptr<Node> ptr = list;
	       std::shared_ptr<Node> 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<Bucket> 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