Skip to main content

2022-07-26

Personal Research

Intracranial

Better Obsidian

Coding Tests

Today's Hacker News

The tar archive format, its extensions, and why GNU tar extracts in quadratic time - Mort's Ramblings

  • That means, every time GNU tar wants to create a hard link, it first has to walk the entire linked list of delayed links and see if the target is a delayed link. The new link must also be delayed if the target is a delayed link.
  • Your time complexity alarm bells should be starting to ring now. For every hard link, we walk the list of all delayed links. But it gets worse; for reasons I don't quite understand yet, tar will go through the entire list of delayed links again if it finds out that it can create the connection immediately. So, all "normal" hard links must go through the entire linked list of delayed links twice.