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/store.hh | |
| 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/store.hh')
| -rw-r--r-- | src/libstore/store.hh | 5 |
1 files changed, 4 insertions, 1 deletions
diff --git a/src/libstore/store.hh b/src/libstore/store.hh index bcf11ce96318..2b83bd7fef04 100644 --- a/src/libstore/store.hh +++ b/src/libstore/store.hh @@ -9,7 +9,10 @@ using namespace std; -const int nixSchemaVersion = 2; +/* Nix store and database schema version. Version 1 (or 0) was Nix <= + 0.7. Version 2 was Nix 0.8 and 0.8. Version 3 is Nix 0.10 and + up. */ +const int nixSchemaVersion = 3; /* A substitute is a program invocation that constructs some store |