uint32_t weightedFurcHash()

in mcrouter/lib/fbi/WeightedFurcHash.cpp [117:184]

• 62 lines of code
• 12 McCabe index (conditional complexity)

uint32_t weightedFurcHash(
    folly::StringPiece key,
    folly::Range<const double*> weights,
    uint32_t maxRetries) {
  uint32_t m = weights.size();
  uint32_t num = m;
  uint32_t a;
  HashCache hash;

  if (m <= 1) {
    return 0;
  }

  uint32_t msb = folly::findLastSet(m - 1);
  uint32_t d = msb;
  uint32_t startIdx = 0;
  a = d;
  uint32_t old_ord = 0;
  uint32_t furcAttempt = 0;
  uint32_t overallAttempt = 0;
  uint32_t next32bits = 0;
  furcKickStartHash(key, hash);
  while (overallAttempt < maxRetries) {
    while (!furcGetBit(a, hash, old_ord)) {
      if (--d == startIdx) {
        num = 0;
        break;
      }
      a = d;
    }
    a += kFurcShift; // We should make progress even in the case of num == 0
    if (num != 0) { // It's not the all-zeros case where we set num = 0
      num = 1;
      for (uint32_t i = startIdx; i < d - 1; i++) {
        num = (num << 1) | furcGetBit(a, hash, old_ord);
        a += kFurcShift;
      }
      if (num >= m) {
        if (++furcAttempt == kMaxFurcRetries) { // Last attempt, default to 0
          num = 0;
        } else {
          num = m;
          continue;
        }
      }
    }
    assert(0 <= weights[num] && weights[num] <= 1.0);
    if (weights[num] == 1) {
      return num;
    }
    uint64_t weightAsInt = weights[num] * std::numeric_limits<uint32_t>::max();
    next32bits = furcGetNext32Bits(a, hash, old_ord);

    if (next32bits < weightAsInt) {
      return num;
    }

    furcAttempt = 0;
    startIdx = a;
    d = a + msb;
    a = d;
    num = m;
    overallAttempt++;
  }

  // Give up; distribute the result using the last peeked 32 bits.
  return next32bits % m;
}