std::pair next()

in glean/interprocess/cpp/worklist.cpp [100:147]

• 30 lines of code
• 7 McCabe index (conditional complexity)

  std::pair<worklist::Counter::Value, size_t> next(size_t worker) noexcept {
    auto victim = worker;
    auto value = unpack(counters[worker].fetch_add(1));
    if (value.empty()) {
      // NOTE: We assume that other workers will only steal from us, never give
      // us things to do.
      bool done = false;

      // The basic idea is to find the worker with the most work and steal half
      // of it. We do this in a loop until success because we want a lock-free
      // algorithm.
      while (!done) {
        worklist::Counter::Value other = value;

        // Find the worker with the most work.
        for (size_t i = (worker+1) % size; i != worker; i = (i+1) % size) {
          auto x = get(i);
          if (x.size() > other.size()) {
            other = x;
            victim = i;
          }
        }

        if (!other.empty()) {
          // If we found a worker which has some work left, steal half of it.
          uint32_t split = other.start + other.size() / 2;
          auto expected = pack(other);

          // To steal, just update their start/end pair provided it hasn't
          // changed. If it has, we'll do the whole thing again.
          if (counters[victim].compare_exchange_strong(
                expected, pack({other.start, split}))) {
            // We've stolen work, now set our start/end pair. We know it hasn't
            // changed because we have no more work left so nobody else is going
            // to update it.
            value = {split, other.end};
            counters[worker].store(pack({split+1, other.end}));
            done = true;
          }
        } else {
          // Nobody has any work left. We've already set the start/end outputs
          // when we were fetching our own counter.
          done = true;
        }
      }
    }
    return {value, victim};
  }