void GeneralTrieImpl::TraverseAllMatchingStrings()

in sql_utils/base/general_trie.h [619:684]

• 42 lines of code
• 14 McCabe index (conditional complexity)

void GeneralTrieImpl<T, NullValuePolicy>::TraverseAllMatchingStrings(
    absl::string_view key, Traverser* traverser, int depth,
    bool preorder) const {
  // first try to match the input string in its entirety
  const NodeT* node = this;
  int next_pos = 0;  // next position in s
  int brkpt = 0;     // next position in "node"

  // if we find a mismatch, we return emptyhanded.
  // if we find a match, we break out of the loop with
  // node set to the portion of the tree that has all
  // the matches for 's'.
  while (node) {
    if (next_pos >= key.length()) {
      // done with input string. Note: empty input string
      // matches everything in the trie. A break here means
      // brkpt == 0 which is what we want (the entire
      // comppath_ at this node is a suffix).
      break;
    }

    const int len_to_compare =
        std::min(node->comppath_.size(), (key.length() - next_pos));
    if (memcmp(node->comppath_.data(), key.data() + next_pos, len_to_compare) !=
        0) {
      // mismatch found
      return;
    }

    if ((key.length() - next_pos) <= node->comppath_.size()) {
      // found a match (prefix of comppath_)
      brkpt = len_to_compare;
      break;
    }

    // follow first char after comppath
    next_pos += len_to_compare;
    node = node->Next(key[next_pos]);
    ++next_pos;
  }

  // if we got here with node == nullptr, we have no matches.
  if (node == nullptr) return;

  // we got here => we have one or more matches
  std::string buf(key);  // all of the input string
  if (node->data_ != null_value_instance_ && brkpt == 0 && preorder) {
    // this node is a full match by itself
    traverser->Process(buf, node->data_);
  }

  buf.append(node->comppath_.data() + brkpt, node->comppath_.size() - brkpt);
  for (int i = node->min_next_; i < node->max_next_; i++) {
    NodeT* child = node->Next(i);

    if (child != nullptr) {
      buf.append(1, static_cast<char>(i));
      child->Traverse(traverser, &buf, depth, preorder);
      buf.erase(buf.size() - 1);
    }
  }
  if (node->data_ != null_value_instance_ && brkpt == 0 && !preorder) {
    // this node is a full match by itself
    traverser->Process(buf, node->data_);
  }
}