bool ValueHistory::isConsistent()

in cachelib/cachebench/consistency/ValueHistory.cpp [215:285]
47 lines of code
18 McCabe index (conditional complexity)

bool ValueHistory::isConsistent(uint64_t endGetIdx, EventStream* es) const {
  // Given the idea of what values are considered "possible", described in the
  // header, detection is done with a simple algorithm
  // ("b" for "begin", "e" for "end"):
  //   * Find first "S"et [Sb, Se] such that it is before "G"et [Gb, Ge] and
  //     doesn't intersect it (if any) - "last inorder set".
  //   * All sets, that overlap with [Sb, Ge] (note Sb and Ge) are candidates.
  //   * As we go, we should track sets that come in order. Latest of them
  //     overrides earlier. We track it with @setIdxMin. Only sets outside
  //     of the current get can override others.
  //
  // Delete from this perspective identical to set, but without value to check.
  //
  // We analyze history in reverse chronological order. First pass we find last
  // inorder set. Second pass find all intersection with it and check if @value
  // equals to one of them (with inorder overrides tracking).

  const auto recEndGet = log_.getAt(endGetIdx);
  XDCHECK_EQ(toInt(recEndGet.event), toInt(Event::kEndGet));
  const auto beginGetIdx = recEndGet.other;
  const auto beginSetIdx = findInOrderSetBegin(endGetIdx);
  auto setIdxMin = log_.first();
  uint32_t counter = 0;
  for (uint64_t i = endGetIdx;
       i > log_.first() && (i > beginSetIdx || counter < openSetCount_);) {
    i--;
    const auto rec = log_.getAt(i);
    if (rec.event == Event::kBeginSet && rec.other == i) {
      counter++;
    }
    // Check if this is a completed operation (doesn't matter if one of SETs,
    // or GET) and skip if it is older than in order SET.
    if (i != rec.other && i < setIdxMin) {
      continue;
    }
    // Check only sets, everything else can be ignored
    if (rec.event == Event::kBeginSet || rec.event == Event::kEndSet) {
      // Set events contain a value. Check it.
      if (rec.value == recEndGet.value) {
        return true;
      }
    } else if (i == log_.first() &&
               (rec.event == Event::kBeginGet || rec.event == Event::kEndGet)) {
      return true;
    }
    if (isWriteEnd(rec.event) && i < beginGetIdx) {
      // If SET begins outside of the GET, do not consider SETs before
      // @setIdxMin - they are older in order SETs.
      setIdxMin = std::max<uint32_t>(setIdxMin, rec.other);
    }
  }
  if (es != nullptr) {
    // Find a log record @kHistoryContext from @beginSetIdx, not beyond the
    // first. Do not subtract from @beginSetIdx - it is unsigned.
    const auto historyBeginIdx =
        std::max<uint64_t>(beginSetIdx, log_.first() + kHistoryContext) -
        kHistoryContext;
    const auto numEvents = endGetIdx - historyBeginIdx;
    for (uint32_t i = 0; i <= numEvents; i++) {
      auto rec = log_.getAt(endGetIdx - i);
      es->event(i,
                endGetIdx - rec.other,
                toString(rec.event),
                isEnd(rec.event),
                hasValue(rec.event),
                rec.value,
                rec.getInfo());
    }
  }
  return false;
}