threadsafe lookup table,

[user555]

Hello, I am writing a threadsafe lookup table with buckets of linked lists and am running into a Access violation (line 113) which I have trouble understanding why it is happening.

#pragma once

#define NUM_BUCKETS 32

#include <functional>
#include <vector>
#include <mutex>
#include <condition_variable>

template <typename K, typename V>
class threadsafe_lookup_table
{

private:
	struct node {
		std::shared_ptr<K> key;
		std::shared_ptr<V> data;
		std::shared_ptr<node> next;
	};

	std::vector < std::shared_ptr<node> > buckets;
	std::vector < std::mutex > bucket_lock;

	std::mutex lock_read;
	std::mutex lock_write;

	int hash_func(const K &key)
	{
		//return key % NUM_BUCKETS;
		return 1;
	}

public:

	threadsafe_lookup_table()
	{
		buckets = std::vector < std::shared_ptr<node> >(NUM_BUCKETS);
		bucket_lock = std::vector<std::mutex>(NUM_BUCKETS);
	}

	threadsafe_lookup_table(const threadsafe_lookup_table<K,V> &other)
	{
		std::lock_guard < std::mutex > o_r;
		std::lock_guard < std::mutex > o_w;
		std::lock(o_r, o_w);

		buckets = other.buckets;
	}

	void add_or_update_mapping(const K &key, const V &val)
	{
		int idx = hash_func(key);
		std::lock_guard<std::mutex> bl(bucket_lock[idx]);

		// First element
		if (buckets[idx] == nullptr) {
			std::shared_ptr<node> cur = std::make_shared<node>();
			cur->key = std::make_shared<K>(key);
			cur->data = std::make_shared<V>(val);
			cur->next = nullptr;
			buckets[idx] = cur;
			return;
		}

		node* cur;
		cur = buckets[idx].get();

		while (cur->next != nullptr)
		{
			if (*cur->key == key) {
				// Update
				*cur->data = val;
				return;
			}
			*cur = *cur->next;
		}
		// cur->next is null, but cur is still not null. check a last time
		if (*cur->key == key) {
			// Update
			*cur->data = val;
			return;
		}
		// Else, we are at the end, cur is our tail and we just need to add a new node
		cur->next = std::make_shared<node>();
		(*cur->next).data = std::make_shared<V>(val);
		(*cur->next).key = std::make_shared<K>(key);
		(*cur->next).next = nullptr;
	}

	void remove_mapping(const K &key)
	{
		int idx = hash_func(key);
		if (buckets[idx] == nullptr)
			return;

		std::lock_guard<std::mutex> bl(bucket_lock[idx]);

		node* cur;
		cur = buckets[idx].get();

		if (*cur->key == key) {
			// Delete head
			buckets[idx] = cur->next;
			return;
		}

		while (cur->next != nullptr)
		{
			if (*cur->next->key == key) {
				// Delete cur->next

				// This is the version with the Access violation error.
				 *cur->next = *cur->next->next; //# <-- this is where the Access violation happened

				/* I tried this implementation instead, but it gives me different errors, where it fails to assign nullptr to the ->next variable
				if (*cur->next->next == nullptr)
					// if we delete our last element
					*cur->next = nullptr;
				else
					// if we delete within the chain
					*cur->next = *cur->next->next;
					*/

				return;
			}
			*cur = *cur->next;
		}
	}

	void value_for(const K &key, V &val)
	{
		int idx = hash_func(key);

		node* cur;
		cur = buckets[idx].get();

		while (cur != nullptr)
		{
			if (*cur->key == key) {
				val = *cur->data;
				return;
			}
			*cur = *cur->next;
		}
	}

};

I am testing the class as <int,std::string>, adding a few key/value pairs and then trying to remove an existing one that was last inserted (fails)

Any help would be appreciated.

[JLBorges]

#include <iostream>
#include <unordered_map>
#include <mutex>
#include <string>

template < typename K, typename V > struct threadsafe_lookup_table
{
    void add_or_update_mapping( const K& key, const V& val )
    {
        std::lock_guard<std::mutex> aquire(lock) ;
        map[key] = val ;
    }

    void remove_mapping( const K& key )
    {
        std::lock_guard<std::mutex> aquire(lock) ;
        map.erase(key) ;
    }

    bool value_for( const K& key, V& val )
    {
        std::lock_guard<std::mutex> aquire(lock) ;
        const auto iter = map.find(key) ;
        if( iter != map.end() )
        {
            val = iter->second ;
            return true ;
        }
        else
        {
            val = {} ;
            return false ;
        }
    }

    private:
        std::unordered_map<K,V> map ;
        std::mutex lock ;
};

int main()
{
    threadsafe_lookup_table< int, std::string > table ;

    table.add_or_update_mapping( 1, "abcd" ) ;
    table.add_or_update_mapping( 2, "efg" ) ;
    table.add_or_update_mapping( 3, "ijkl" ) ;
    table.add_or_update_mapping( 1, "mnopq" ) ;

    std::string str ;
    table.value_for( 1, str ) ;
    std::cout << str << '\n' ; // mnopq

    table.remove_mapping(1) ;
    if( table.value_for( 1, str ) ) std::cout << str << '\n' ;
    else std::cout << "*** no such key\n" ; // *** no such key
}

http://coliru.stacked-crooked.com/a/2693df036cd15f99