AtomicUnorderedMap是一个不反对删除、反对高并发读写、反对自定义 K、V 的哈希表，只反对一个 findOrConstruct 操作。
template <typename Func>
std::pair<const_iterator, bool> findOrConstruct(const Key& key, Func&& func) {
// 依据哈希算法定位到索引
auto const slot = keyToSlotIdx(key);
auto prev = slots_[slot].headAndState_.load(std::memory_order_acquire);
// 遍历动态链表查找键是否存在
auto existing = find(key, slot);
if (existing != 0) {return std::make_pair(ConstIterator(*this, existing), false);
}
// 在左近找一个空 slot，同时设标记位为 CONSTRUCTING
auto idx = allocateNear(slot);
new (&slots_[idx].keyValue().first) Key(key);
func(static_cast<void*>(&slots_[idx].keyValue().second));
while (true) {slots_[idx].next_ = prev >> 2;
// we can merge the head update and the CONSTRUCTING -> LINKED update
// into a single CAS if slot == idx (which should happen often)
auto after = idx << 2;
// 第一次就查找到空 slot
if (slot == idx) {after += LINKED;} else {after += (prev & 3);
}
// 没有其他人读写原始 slot prev
if (slots_[slot].headAndState_.compare_exchange_strong(prev, after)) {
// success
if (idx != slot) {slots_[idx].stateUpdate(CONSTRUCTING, LINKED);
}
return std::make_pair(ConstIterator(*this, idx), true);
}
// compare_exchange_strong updates its first arg on failure, so
// there is no need to reread prev
// 原来的 slot 有变动，看看是不是其余线程进行了插入
existing = find(key, slot);
if (existing != 0) {
// our allocated key and value are no longer needed
slots_[idx].keyValue().first.~Key();
slots_[idx].keyValue().second.~Value();
slots_[idx].stateUpdate(CONSTRUCTING, EMPTY);
return std::make_pair(ConstIterator(*this, existing), false);
}
}
}