From 8463f27d8cd09d54648de21c747f895cdb558f83 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Mon, 12 Dec 2005 18:24:42 +0000 Subject: * 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. --- src/libstore/db.hh | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/libstore/db.hh') diff --git a/src/libstore/db.hh b/src/libstore/db.hh index 76afc1d3b0e2..b7ebd446793d 100644 --- a/src/libstore/db.hh +++ b/src/libstore/db.hh @@ -64,7 +64,7 @@ public: void open(const string & path); void close(); - TableId openTable(const string & table); + TableId openTable(const string & table, bool sorted = false); bool queryString(const Transaction & txn, TableId table, const string & key, string & data); @@ -83,7 +83,7 @@ public: const string & key); void enumTable(const Transaction & txn, TableId table, - Strings & keys); + Strings & keys, const string & keyPrefix = ""); }; -- cgit 1.4.1