]> git.ipfire.org Git - thirdparty/tar.git/commit
Avoid quadratic behavior with delayed links
authorPaul Eggert <eggert@cs.ucla.edu>
Mon, 15 Aug 2022 07:05:53 +0000 (00:05 -0700)
committerPaul Eggert <eggert@cs.ucla.edu>
Mon, 15 Aug 2022 07:07:39 +0000 (00:07 -0700)
commit258d1c44e5ee7c58b28bf0000e9d737df6081885
tree2f723b2cffb9068662e3e364b7faadf6a4a381cc
parente49537dcdf0b35f2425402f3b5d77669c9b4aed9
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.
src/extract.c