* Main the `substitutes-rev' table again, but now in a way that

  doesn't take \Theta(n^2) space/time complexity.

2 files changed, 36 insertions, 20 deletions

diff --git a/src/libstore/store.cc b/src/libstore/store.cc
index fdd22c3b8..110ec2b48 100644
--- a/src/libstore/store.cc
+++ b/src/libstore/store.cc
@@ -322,29 +322,44 @@ static void writeSubstitutes(const Transaction & txn,
 }
 
 
-void registerSubstitute(const Transaction & txn,
-    const Path & srcPath, const Substitute & sub)
+typedef map<Path, Paths> SubstitutesRev;
+
+
+void registerSubstitutes(const Transaction & txn,
+    const SubstitutePairs & subPairs)
 {
-    assertStorePath(srcPath);
-    assertStorePath(sub.storeExpr);
+    SubstitutesRev revMap;
     
-    Substitutes subs = readSubstitutes(txn, srcPath);
-
-    if (find(subs.begin(), subs.end(), sub) != subs.end()) {
-        /* Nothing to do if the substitute is already known. */
-        return;
-    }
-    subs.push_front(sub); /* new substitutes take precedence */
+    for (SubstitutePairs::const_iterator i = subPairs.begin();
+         i != subPairs.end(); ++i)
+    {
+        const Path & srcPath(i->first);
+        const Substitute & sub(i->second);
 
-    writeSubstitutes(txn, srcPath, subs);
+        assertStorePath(srcPath);
+        assertStorePath(sub.storeExpr);
     
-    Paths revs;
-    nixDB.queryStrings(txn, dbSubstitutesRev, sub.storeExpr, revs);
-    if (find(revs.begin(), revs.end(), srcPath) == revs.end())
-        revs.push_back(srcPath);
+        Substitutes subs = readSubstitutes(txn, srcPath);
+
+        /* New substitutes take precedence over old ones.  If the
+           substitute is already present, it's moved to the front. */
+        remove(subs.begin(), subs.end(), sub);
+        subs.push_front(sub);
+        
+        writeSubstitutes(txn, srcPath, subs);
+
+        Paths & revs = revMap[sub.storeExpr];
+        if (revs.empty())
+            nixDB.queryStrings(txn, dbSubstitutesRev, sub.storeExpr, revs);
+        if (find(revs.begin(), revs.end(), srcPath) == revs.end())
+            revs.push_back(srcPath);
+    }
 
-    // !!! O(n^2) complexity in building this
-    //    nixDB.setStrings(txn, dbSubstitutesRev, sub.storeExpr, revs);
+    /* Re-write the reverse mapping in one go to prevent Theta(n^2)
+       performance.  (This would occur because the data fields of the
+       `substitutes-rev' table are lists). */
+    for (SubstitutesRev::iterator i = revMap.begin(); i != revMap.end(); ++i)
+        nixDB.setStrings(txn, dbSubstitutesRev, i->first, i->second);
 }
 
 
diff --git a/src/libstore/store.hh b/src/libstore/store.hh
index 68f7d6190..10d2890b8 100644
--- a/src/libstore/store.hh
+++ b/src/libstore/store.hh
@@ -66,8 +66,9 @@ bool querySuccessor(const Path & srcPath, Path & sucPath);
 Paths queryPredecessors(const Path & sucPath);
 
 /* Register a substitute. */
-void registerSubstitute(const Transaction & txn,
-    const Path & srcPath, const Substitute & sub);
+typedef list<pair<Path, Substitute> > SubstitutePairs;
+void registerSubstitutes(const Transaction & txn,
+    const SubstitutePairs & subPairs);
 
 /* Return the substitutes expression for the given path. */
 Substitutes querySubstitutes(const Path & srcPath);