Method Append

cpp/src/arrow/util/trie.cc:150–206

}

Status TrieBuilder::Append(std::string_view s, bool allow_duplicate) {
  // Find or create node for string
  fast_index_type node_index = 0;
  fast_index_type pos = 0;
  fast_index_type remaining = static_cast<fast_index_type>(s.length());

  while (true) {
    Trie::Node* node = &trie_.nodes_[node_index];
    const auto substring_length = node->substring_length();
    const auto substring_data = node->substring_data();

    for (fast_index_type i = 0; i < substring_length; ++i) {
      if (remaining == 0) {
        // New string too short => need to split node
        RETURN_NOT_OK(SplitNode(node_index, i));
        // Current node matches exactly
        node = &trie_.nodes_[node_index];
        node->found_index_ = trie_.size_++;
        return Status::OK();
      }
      if (s[pos] != substring_data[i]) {
        // Mismatching substring => need to split node
        RETURN_NOT_OK(SplitNode(node_index, i));
        // Create new node for mismatching char
        node = &trie_.nodes_[node_index];
        return CreateChildNode(node, s[pos], s.substr(pos + 1));
      }
      ++pos;
      --remaining;
    }
    if (remaining == 0) {
      // Node matches exactly
      if (node->found_index_ >= 0) {
        if (allow_duplicate) {
          return Status::OK();
        } else {
          return Status::Invalid("Duplicate entry in trie");
        }
      }
      node->found_index_ = trie_.size_++;
      return Status::OK();
    }
    // Lookup child using next input character
    if (node->child_lookup_ == -1) {
      // Need to extend lookup table for this node
      RETURN_NOT_OK(ExtendLookupTable(&node->child_lookup_));
    }
    auto c = static_cast<uint8_t>(s[pos++]);
    --remaining;
    node_index = trie_.lookup_table_[node->child_lookup_ * 256 + c];
    if (node_index == -1) {
      // Child not found => need to create child node
      return CreateChildNode(node, c, s.substr(pos));
    }
    node = &trie_.nodes_[node_index];
  }
}