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 /blacklisting | |
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 'blacklisting')
0 files changed, 0 insertions, 0 deletions