diff options
| author | Paul Eggert <eggert@cs.ucla.edu> | 2022-08-15 00:05:53 -0700 |
|---|---|---|
| committer | Paul Eggert <eggert@cs.ucla.edu> | 2022-08-15 00:07:39 -0700 |
| commit | 258d1c44e5ee7c58b28bf0000e9d737df6081885 (patch) | |
| tree | 2f723b2cffb9068662e3e364b7faadf6a4a381cc /tests/testsuite.at | |
| parent | e49537dcdf0b35f2425402f3b5d77669c9b4aed9 (diff) | |
| download | tar-258d1c44e5ee7c58b28bf0000e9d737df6081885.tar.gz | |
Avoid quadratic behavior with delayed links
Do this by searching a hash table instead of a linked list.
Problem reported by Martin Dørum in https://mort.coffee/home/tar/
via Gavin Smith in:
https://lists.gnu.org/r/bug-tar/2022-07/msg00003.html
* src/extract.c: Include hash.h.
Improve performance a bit on non-birthtime hosts
(struct delayed_link.has_predecessor): New member.
(delayed_link_head): Remove, replacing with ...
(delayed_link_table): ... this new variable. All uses
of linked list replaced with hash table.
(dl_hash, dl_compare): New functions for hash table.
(create_placeholder_file): Initialize has_predecessor.
(apply_delayed_link): New function, with body taken from
most of the old apply_delayed_link.
(apply_delayed_links): Use it. Respect has_predecessor.
Don’t bother freeing as we are about to exit.
Diffstat (limited to 'tests/testsuite.at')
0 files changed, 0 insertions, 0 deletions