void rehashImpl()

in folly/container/detail/F14Table.h [1784:1915]
117 lines of code
17 McCabe index (conditional complexity)

  void rehashImpl(
      std::size_t origSize,
      std::size_t origChunkCount,
      std::size_t origCapacityScale,
      std::size_t newChunkCount,
      std::size_t newCapacityScale) {
    auto origChunks = chunks_;
    auto origCapacity = computeCapacity(origChunkCount, origCapacityScale);
    auto origAllocSize = chunkAllocSize(origChunkCount, origCapacityScale);
    auto newCapacity = computeCapacity(newChunkCount, newCapacityScale);
    auto newAllocSize = chunkAllocSize(newChunkCount, newCapacityScale);

    BytePtr rawAllocation;
    auto undoState = this->beforeRehash(
        origSize, origCapacity, newCapacity, newAllocSize, rawAllocation);
    chunks_ = initializeChunks(rawAllocation, newChunkCount, newCapacityScale);

    FOLLY_SAFE_DCHECK(
        newChunkCount < std::numeric_limits<InternalSizeType>::max(), "");
    chunkMask_ = static_cast<InternalSizeType>(newChunkCount - 1);

    bool success = false;
    SCOPE_EXIT {
      // this SCOPE_EXIT reverts chunks_ and chunkMask_ if necessary
      BytePtr finishedRawAllocation = nullptr;
      std::size_t finishedAllocSize = 0;
      if (LIKELY(success)) {
        if (origCapacity > 0) {
          finishedRawAllocation = std::pointer_traits<BytePtr>::pointer_to(
              *static_cast<uint8_t*>(static_cast<void*>(&*origChunks)));
          finishedAllocSize = origAllocSize;
        }
      } else {
        finishedRawAllocation = rawAllocation;
        finishedAllocSize = newAllocSize;
        chunks_ = origChunks;
        FOLLY_SAFE_DCHECK(
            origChunkCount < std::numeric_limits<InternalSizeType>::max(), "");
        chunkMask_ = static_cast<InternalSizeType>(origChunkCount - 1);
        F14LinkCheck<getF14IntrinsicsMode()>::check();
      }

      this->afterRehash(
          std::move(undoState),
          success,
          origSize,
          origCapacity,
          newCapacity,
          finishedRawAllocation,
          finishedAllocSize);
    };

    if (origSize == 0) {
      // nothing to do
    } else if (origChunkCount == 1 && newChunkCount == 1) {
      // no mask, no chunk scan, no hash computation, no probing
      auto srcChunk = origChunks;
      auto dstChunk = chunks_;
      std::size_t srcI = 0;
      std::size_t dstI = 0;
      while (dstI < origSize) {
        if (LIKELY(srcChunk->occupied(srcI))) {
          dstChunk->setTag(dstI, srcChunk->tag(srcI));
          this->moveItemDuringRehash(
              dstChunk->itemAddr(dstI), srcChunk->item(srcI));
          ++dstI;
        }
        ++srcI;
      }
      if (kEnableItemIteration) {
        sizeAndPackedBegin_.packedBegin() = ItemIter{dstChunk, dstI - 1}.pack();
      }
    } else {
      // 1 byte per chunk means < 1 bit per value temporary overhead
      std::array<uint8_t, 256> stackBuf;
      uint8_t* fullness;
      if (newChunkCount <= stackBuf.size()) {
        fullness = stackBuf.data();
      } else {
        ByteAlloc a{this->alloc()};
        // may throw
        fullness =
            &*std::allocator_traits<ByteAlloc>::allocate(a, newChunkCount);
      }
      std::memset(fullness, '\0', newChunkCount);
      SCOPE_EXIT {
        if (newChunkCount > stackBuf.size()) {
          ByteAlloc a{this->alloc()};
          std::allocator_traits<ByteAlloc>::deallocate(
              a,
              std::pointer_traits<typename std::allocator_traits<
                  ByteAlloc>::pointer>::pointer_to(*fullness),
              newChunkCount);
        }
      };

      auto srcChunk = origChunks + origChunkCount - 1;
      std::size_t remaining = origSize;
      while (remaining > 0) {
        auto iter = srcChunk->occupiedIter();
        if (prefetchBeforeRehash()) {
          for (auto piter = iter; piter.hasNext();) {
            this->prefetchValue(srcChunk->item(piter.next()));
          }
        }
        while (iter.hasNext()) {
          --remaining;
          auto srcI = iter.next();
          Item& srcItem = srcChunk->item(srcI);
          auto hp = splitHash(
              this->computeItemHash(const_cast<Item const&>(srcItem)));
          FOLLY_SAFE_CHECK(hp.second == srcChunk->tag(srcI), "");

          auto dstIter = allocateTag(fullness, hp);
          this->moveItemDuringRehash(dstIter.itemAddr(), srcItem);
        }
        --srcChunk;
      }

      if (kEnableItemIteration) {
        // this code replaces size invocations of adjustSizeAndBeginAfterInsert
        std::size_t i = chunkMask_;
        while (fullness[i] == 0) {
          --i;
        }
        sizeAndPackedBegin_.packedBegin() =
            ItemIter{chunks_ + i, std::size_t{fullness[i]} - 1}.pack();
      }
    }

    success = true;
  }