found_entry->second = value;
}
}
void remove_mapping(Key const& key) {
std::unique_lock(5)
bucket_iterator const found_entry = find_entry_for(key);
if (found_entry != data.end()) {
data.erase(found_entry);
}
}
};
std::vector(6)
Hash hasher;
bucket_type& get_bucket(Key const& key) const {← (7)
std::size_t const bucket_index = hasher(key)%buckets.size();
return *buckets[bucket_index];
}
public:
typedef Key key_type;
typedef Value mapped_type;
typedef Hash hash_type;
threadsafe_lookup_table(
unsigned num_buckets = 19,
Hash const& hasher_ = Hash()):
buckets(num_buckets), hasher(hasher_) {
for (unsigned i = 0; i < num_buckets; ++i) {
buckets[i].reset(new bucket_type);
}
}
threadsafe_lookup_table(
threadsafe_lookup_table const& other) = delete;
threadsafe_lookup_table& operator=(
threadsafe_lookup_table const& other) = delete;
Value value_for(Key const& key,
Value const& default_value = Value()) const {
return get_bucket(key).value_for(key, default_value);←(8)
}
void add_or_update_mapping(Key const& key,Value const& value) {
get_bucket(key).add_or_update_mapping(key, value);←(9)
}
void remove_mapping(Key const& key) {
get_bucket(key).remove_mapping(key);←(10)
}
};
В этой реализации для хранения кластеров используется вектор std::vector (6), это позволяет задавать число кластеров в конструкторе. По умолчанию оно равно 19 (произвольно выбранное простое число); оптимальные показатели работы хеш-таблиц достигаются, когда имеется простое число кластеров. Каждый кластер защищен мьютексом типа boost::shared_mutex (1), который позволяет нескольким потокам одновременно читать, но только одному обращаться к любой из функций модификации
Поскольку количество кластеров фиксировано, функцию get_bucket() (7) можно вызывать вообще без блокировки (8), (9), (10), а затем захватить мьютекс кластера для совместного (только для чтения) (3) или монопольного (чтение/запись) (4), (5) владения — в зависимости от вызывающей функции.
Во всех трех функциях используется функция-член кластера find_entry_for() (2), которая определяет, есть ли в данном кластере указанный ключ. Каждый кластер содержит всего лишь список std::list<> пар ключ/значение, поэтому добавлять и удалять элементы легко.
Я уже рассматривал это решение с точки зрения распараллеливания, и мы убедились, что все надежно защищено мьютексами. Но как обстоит дело с безопасностью относительно исключений? Функция value_for ничего не изменяет, поэтому с ней проблем нет: если она и возбудит исключение, то на структуру данных это не повлияет.
Функция remove_mapping модифицирует список, обращаясь к его функции-члену erase, которая гарантированно не возбуждает исключений, так что здесь тоже всё безопасно. Остается функция add_or_update_mapping, которая может возбуждать исключения в обеих ветвях if. Функция push_back безопасна относительно исключений, то есть в случае исключения оставляет список в исходном состоянии, так что с этой ветвью всё хорошо. Единственная проблема — присваивание в случае замены существующего значения; если оператор присваивания возбуждает исключение, то мы полагаемся на то, что он оставляет исходный объект неизмененным. Однако это не влияет на структуру данных в целом и является свойством пользовательского типа, так что пускай пользователь и решает эту проблему.
