* 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.

1 files changed, 2 insertions, 2 deletions

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 = "");
 };