apt/ftparchive/contents.cc, branch 3.3.0

ftparchive: contents: Avoid exponential complexity and overflows

2024-10-07T14:17:32Z

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

ftparchive: Mystrdup: Add safety check and bump buffer size

2024-10-07T14:02:06Z

Add a safety check to ensure that the block were are allocating actually fits the string we want to write. If it doesn't, abort the program. While we are here, bump the buffer size from 40 KiB to 4 MiB, because why bother with smaller buffers.

Modernize standard library includes

2024-02-20T12:49:04Z

This was automated with sed and git-clang-format, and then I had to fix up the top of policy.cc by hand as git-clang-format accidentally indented it by two spaces.

Apply various suggestions by cppcheck

2019-07-08T13:51:17Z

Reported-By: cppcheck

Remove obsolete RCS keywords

2018-05-07T11:41:31Z

Prompted-by: Jakub Wilk

fix various typos reported by spellintian

2017-01-19T14:59:38Z

Most of them in (old) code comments. The two instances of user visible string changes the po files of the manpages are fixed up as well. Gbp-Dch: Ignore Reported-By: spellintian

apply various suggestions made by cppcheck

2015-11-05T11:21:33Z

Reported-By: cppcheck Git-Dch: Ignore

rewrite all TFRewrite instances to use the new pkgTagSection::Write

2015-05-11T15:22:33Z

While it is mostly busywork to rewrite all instances it actually fixes bugs as the data storage used by the new method is std::string rather than a char*, the later mostly created by c_str() from a std::string which the caller has to ensure keeps in scope – something apt-ftparchive actually didn't ensure and relied on copy-on-write behavior instead which c++11 forbids and hence the new default gcc abi doesn't use it.

fix: warning: extra ‘;’ [-Wpedantic]

2014-09-26T22:11:15Z

Reported-By: gcc -Wpedantic Git-Dch: Ignore

use free() instead of delete() when realloc is used

2014-05-27T14:25:43Z

ContentsExtract::~ContentsExtract() needs to use free() because Data got allocated via realloc() Reported-By: clang -fsanitize=address -fno-omit-frame-pointer