ftparchive: contents: Avoid exponential complexity and overflows

Wstored directory entries as a binary tree, but we did not balance it,
leading to exponential complexity on insertion and potentially
exponential levels of stack recursion in DoPrint(), causing overflows.

Simply use an std::set storing pairs of (path, package) instead,
this is very simple, and handles aspects such as ordering or the
same package appearing multiple times correctly.

Iteration becomes a bit tricky: After seeing (file1, pkg1) when
we see (file1, pkg2) we need to append pkg2 to the current line;
once we see (file2, anything), we need write out the line and
start a new one.

For memory optimization, we use a new class StringInBlock to handle
the block-managed C strings generated by Mystrdup() in a type-safe
manner. This ensures proper lifetime of objects and no accidental
conversions to std::string. This saves a significant amount of
space (a pair of std::string is 64-byte large; a pair of pointers
is 16 byte large, a 48 byte saving per entry); reproducing the Contents
file of Ubuntu 24.10, using straight-forward std::string resulted in
GB of memory usage, whereas the C-style string only uses 1.35 GB.

As a side effect of the patch we also remove arbitrary 1024-byte
buffer sizes. There also is a change in output: The package names
are now sorted alphabetically, instead of being in visit order.

LP: #2083697

0 files changed, 0 insertions, 0 deletions