about summary refs log tree commit diff
path: root/src/libstore/db.hh
diff options
context:
space:
mode:
authorEelco Dolstra <e.dolstra@tudelft.nl>2005-12-12T18·24+0000
committerEelco Dolstra <e.dolstra@tudelft.nl>2005-12-12T18·24+0000
commit8463f27d8cd09d54648de21c747f895cdb558f83 (patch)
tree75bb48b23486d01c8891e8b259b344dbdafc6b86 /src/libstore/db.hh
parent18bbcb1214caf75c0190e610d7eb34e971366c7c (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/db.hh')
-rw-r--r--src/libstore/db.hh4
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 = "");
 };