diff options
| author | Eelco Dolstra <e.dolstra@tudelft.nl> | 2005-12-12T18·24+0000 |
|---|---|---|
| committer | Eelco Dolstra <e.dolstra@tudelft.nl> | 2005-12-12T18·24+0000 |
| commit | 8463f27d8cd09d54648de21c747f895cdb558f83 (patch) | |
| tree | 75bb48b23486d01c8891e8b259b344dbdafc6b86 /src/libstore/derivations-ast.def | |
| parent | 18bbcb1214caf75c0190e610d7eb34e971366c7c (diff) | |
* Fix NIX-23: quadratic complexity in maintaining the referers
mapping. The referer table is replaced by a referrer table (note
spelling fix) that stores each referrer separately. That is,
instead of having
referer[P] = {Q_1, Q_2, Q_3, ...}
we store
referer[(P, Q_1)] = ""
referer[(P, Q_2)] = ""
referer[(P, Q_3)] = ""
...
To find the referrers of P, we enumerate over the keys with a value
lexicographically greater than P. This requires the referrer table
to be stored as a B-Tree rather than a hash table.
(The tuples (P, Q) are stored as P + null-byte + Q.)
Old Nix databases are upgraded automatically to the new schema.
Diffstat (limited to 'src/libstore/derivations-ast.def')
0 files changed, 0 insertions, 0 deletions