void insert()

in glean/rts/ownership/triearray.h [43:125]
59 lines of code
12 McCabe index (conditional complexity)

  void insert(const OwnershipUnit::Ids *start, const OwnershipUnit::Ids *finish, Get&& get) {
    if (start == finish) {
      return;
    }

    minkey_ = std::min(minkey_, start->start.toWord());
    maxkey_ = std::max(maxkey_, finish[-1].finish.toWord());

    // only 32-bit keys are supported; this property is assumed later
    CHECK(maxkey_ <= std::numeric_limits<uint32_t>::max());

    // Algorithm:
    //
    // - Collect previously existing values in `values`.
    // - When we see a value for the first time, set its `link` field to point
    //   to the first `Tree` that contains it and add it to `values`.
    // - When we see a value again, temporarily make the current `Tree` point
    //   to the previous tree that contained the value (from the value's `link`)
    //   and update the value's `link` to point to the current tree. This
    //   effectively maintains a linked list of trees which contain a value,
    //   with the value's `link` being the root.
    // - Do the same for newly inserted trees which don't have a previous value
    //   via `null_link`.
    // - Once we've collected everything, for each value in `values` compute the
    //   new value via `get` and then traverse the linked list of trees, storing
    //   a pointer to the new value in each one.
    // - Do the same for `null_link`.
    std::vector<T*> values;
    Tree *null_link = nullptr;

    while (start != finish) {
      const auto [first_id, last_id] = *start++;
      if (first_id <= last_id) {
        traverse(
          first_id.toWord(),
          last_id.toWord() - first_id.toWord() + 1,
          [&](Tree& tree, uint64_t key, uint64_t size, size_t block) {
            if (size == block) {
              if (const auto value = tree.value()) {
                const auto prev = static_cast<Tree *>(value->link());
                value->link(&tree);
                tree = Tree::link(prev);
                if (prev == nullptr) {
                  values.push_back(value);
                } else {
                  value->use(-1);
                }
              } else {
                tree = Tree::link(null_link);
                null_link = &tree;
              }
            } else {
              if (auto value = tree.value()) {
                value->use(FANOUT-1);
              }
              tree = Tree::forest(pool_.alloc(tree));
            }
          });
      }
    }

    const auto unlink = [&](Tree *tree, T * FOLLY_NULLABLE value) {
      auto upd = get(value, 1);
      uint32_t refs = 0;
      while (tree != nullptr) {
        auto next = tree->link();
        *tree = Tree::value(upd);
        tree = next;
        ++refs;
      }
      upd->use(refs-1);
    };

    if (null_link) {
      unlink(null_link, nullptr);
    }

    for (auto value : values) {
      Tree *tree = static_cast<Tree*>(value->link());
      value->link(nullptr);
      unlink(tree, value);
    }
  }