nlohmann / json / 37955575120

99%

Build Type

push

github

Committed by web-flow

Commit Message

Unflatten in time and memory linear in the pointer depth (#5793)

* Unflatten in time and memory linear in the pointer depth

#5443 made unflatten() decide between arrays and objects independently
of the iteration order by collecting the pointer prefixes that have a
reference token 0 below them in a std::set<std::vector<string_t>>.
Every such prefix was stored as a copy of all its reference tokens, and
get_and_create() compared whole prefix vectors at every step, so
unflattening a pointer of depth d took time and memory quadratic in d:
a 10,000-level array pointer took 18 s and 1.3 GB, a 100,000-level one
did not finish.

The prefixes are now numbered nodes of a tree, so each is stored once
and get_and_create() follows the tree token by token. The result is
unchanged, including its independence of the iteration order.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

* Initialize prefix_tree members to satisfy -Weffc++

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

* Move prefix_tree setup and child insertion into member functions

The constructor now creates the root node, add_child() inserts a
reference token below a prefix and returns the child's number, and
find_child() looks one up for get_and_create().

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

---------

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

Coverage Stats

3042 of 3240 branches covered (93.89%)

26 of 26 new or added lines in 1 file covered. (100.0%)

6 existing lines in 2 files now uncovered.

8805 of 8931 relevant lines covered (98.59%)

7300858.48 hits per line