关于c++:Folly库代码赏析3AtomicUnorderedMap

1. 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);
      }
    }
  }