# 
# patch "ChangeLog"
#  from [0ad371d804e163ce4a6ecacd9cc48e44e4c262e9]
#    to [d2dc7bc076bc2b6df921fa0c48682335e984e896]
# 
# patch "change_set.cc"
#  from [0f26497e115e7818f164f2c3d9a469c6e784f742]
#    to [c9554a69662fecf70ead4b8fec54eab5c355118a]
# 
# patch "smap.hh"
#  from [bf2f49a88508bb21de8bc201c02e3050835a6d95]
#    to [8fb308c5059d3d572a078c96a6937ed989b425ec]
# 
# patch "tests/t_vcheck.at"
#  from [247f296fb06b33fb2609231c983517384b50a437]
#    to [8656291fbb8e643e82f3bfb8ffa5616346388cb6]
# 
--- ChangeLog
+++ ChangeLog
@@ -1,8 +1,19 @@
 2005-04-14  Matthew Gregan  <address@hidden>
 
 	* win32/process.cc: Fix build on MingW 3.2.0-rc[123] by adding
 	<sstream> include.
 
+2005-04-14  Matt Johnston  <address@hidden>
+
+	* change_set.cc (confirm_unique_entries_in_directories): use a
+	  std::vector rather than std::map for better performance (only sort
+	  once).
+	* smap.hh: an invariant
+
+2005-04-14  Nathaniel Smith  <address@hidden>
+
+	* tests/t_vcheck.at: Update notes.
+
 2005-04-14  Jeremy Cowgar  <address@hidden>
 
 	* monotone.texi (Making Changes): Fixed duplicate paragraph
--- change_set.cc
+++ change_set.cc
@@ -550,8 +550,8 @@
 
 static void
 confirm_unique_entries_in_directories(path_state const & ps)
-{  
-  std::map<std::pair<tid,path_component>, bool> entries;
+{
+  std::vector<std::pair<tid,path_component> > entries;
   for (path_state::const_iterator i = ps.begin(); i != ps.end(); ++i)
     {
       if (null_name(path_item_name(i->second)))
@@ -562,9 +562,27 @@
           
       std::pair<tid,path_component> p = std::make_pair(path_item_parent(i->second), 
                                                        path_item_name(i->second));
-      I(entries.find(p) == entries.end());
-      entries.insert(std::make_pair(p,true));
+      entries.push_back(p);
     }
+
+  // Now we check that entries is unique
+  if (entries.empty())
+      return;
+
+  std::sort(entries.begin(), entries.end());
+
+  std::vector<std::pair<tid,path_component> >::const_iterator leader, lagged;
+  leader = entries.begin();
+  lagged = entries.begin();
+
+  I(leader != entries.end());
+  ++leader;
+  while (leader != entries.end())
+  {
+    I(*leader != *lagged);
+    ++leader;
+    ++lagged;
+  }
 }
 
 static void
--- smap.hh
+++ smap.hh
@@ -88,6 +88,7 @@
         const_iterator leader, lagged;
         lagged = begin();
         leader = begin();
+        I(leader != end());
         ++leader;
         for (; leader != end(); ++lagged, ++leader)
           I(lagged->first != leader->first);
--- tests/t_vcheck.at
+++ tests/t_vcheck.at
@@ -19,10 +19,9 @@
 # The original 'vcheck' was ripped out when manifest and file certs
 # were removed, and never quite did the right thing anyway.  (It only
 # applied to manifests, in particular.)  It may be useful to reference
-# the code, though: see, say,
-# 727d28b35f1fcbc91c0183fca2a6cabbe7cf21d7, or t:monotone-0.16.  In
-# particular, mac.hh should be useful.  Note also the section
-# "Accidental collision" in monotone.texi.
+# the code, though: see t:monotone-0.16.  In particular, mac.hh should
+# be useful.  Note also the section "Accidental collision" in
+# monotone.texi.
 
 # There are a few ways to re-add this.  The simplest is probably to
 # have a cert on revisions that contains
@@ -36,6 +35,18 @@
 # This reduces space overhead, too, since certs's space usage adds up,
 # and does so for project members who aren't worried about SHA1
 # collisions too...
+#
+# an alternative approach would be to contain:
+#   - a salt/nonce
+#   - a MAC of (length-prefixed revision) + (length prefixed manifest)
+#     + (length prefixed versions of each file in the manifest, in manifest order)
+# this is small, and just as safe.  it is rather expensive to create
+# or check, though, since you have to load all that data, so maybe the
+# optimization above where you only hash mentioned files would be
+# good.  OTOH, if you hash everything, then you can use them
+# sparingly, and be sure that the versions so certed really are safe;
+# if you only hash some pieces, you have to cert your entire history
+# in order to "trust" any one snapshot at all.
 
 AT_CHECK(false)