std::vector MaglevHashV2::generateHashRing()

in katran/lib/MaglevHashV2.cpp [20:71]

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

std::vector<int> MaglevHashV2::generateHashRing(
    std::vector<Endpoint> endpoints,
    const uint32_t ring_size) {
  std::vector<int> result(ring_size, -1);

  if (endpoints.size() == 0) {
    return result;
  } else if (endpoints.size() == 1) {
    for (auto& v : result) {
      v = endpoints[0].num;
    }
    return result;
  }

  auto max_weight = 0;
  for (const auto& endpoint : endpoints) {
    if (endpoint.weight > max_weight) {
      max_weight = endpoint.weight;
    }
  }

  uint32_t runs = 0;
  std::vector<uint32_t> permutation(endpoints.size() * 2, 0);
  std::vector<uint32_t> next(endpoints.size(), 0);
  std::vector<uint32_t> cum_weight(endpoints.size(), 0);

  for (int i = 0; i < endpoints.size(); i++) {
    genMaglevPermutation(permutation, endpoints[i], i, ring_size);
  }

  for (;;) {
    for (int i = 0; i < endpoints.size(); i++) {
      cum_weight[i] += endpoints[i].weight;
      if (cum_weight[i] >= max_weight) {
        cum_weight[i] -= max_weight;
        auto offset = permutation[2 * i];
        auto skip = permutation[2 * i + 1];
        auto cur = (offset + next[i] * skip) % ring_size;
        while (result[cur] >= 0) {
          next[i] += 1;
          cur = (offset + next[i] * skip) % ring_size;
        }
        result[cur] = endpoints[i].num;
        next[i] += 1;
        runs++;
        if (runs == ring_size) {
          return result;
        }
      }
    }
  }
}