Add hash table to dirpool for O(1) directory lookup
Profiling repo2solv with perf on a full primary+filelists workload
(Fedora 42, ~75K packages) revealed that dirpool_add_dir consumed
48.6% of all cycles and caused 92% of last-level cache misses.
The root cause: directories sharing a parent are stored across
multiple non-contiguous blocks in the dirs[] array, linked through
the dirtraverse[] auxiliary array. Looking up whether a (parent,
component) pair already exists required scanning every block for
that parent -- O(B*C) where B is the number of blocks and C the
average block size. Popular parents like /usr accumulate hundreds
of blocks from filelists data, causing cache-hostile pointer chasing
across scattered memory.
Replace the dirtraverse-based lookup with an open-addressed hash
table mapping (parent, comp) pairs to directory ids. The hash is
computed via relhash() (same scheme used for reldeps), and parent
is verified by a short backward walk to the block header -- always
within a few entries of the matched slot, so it stays in the same
cache line.
The hash table is built on demand and resized at 50% load factor.
The dirtraverse array is kept for dirpool_child/dirpool_sibling
traversal APIs but is no longer needed for the add_dir fast path.
Benchmark results (Fedora 42 metadata, 5 runs, median wall-clock):
primary + filelists: 10,256 ms vs 20,028 ms baseline (49% faster)
primary only: 2,629 ms vs 2,546 ms baseline (within noise)
perf profile after the change shows dirpool_add_dir dropped from
48.6% to 1.78% of cycles. Output is byte-identical to baseline.