#
#
# add_file "hybrid_map.hh"
#  content [2f538b4bd091d63a8b83d92025d60cc5c293d630]
# 
# patch "Makefile.am"
#  from [abadfd52468504cc0b30671984d43df3453f3532]
#    to [782c145b15c9cb84fe237260d7190fb8d9138649]
# 
# patch "roster.cc"
#  from [62f172da10ee678623d30fbdafd766f521e2fbc7]
#    to [6c1f08a21617cc9c626e06beffe52c5dbfe48430]
# 
# patch "roster.hh"
#  from [0df1174eb4998443af6c94143f46eb3f8b383f31]
#    to [58f56b5761388f0c4a35436532a64b6c7812b755]
#
============================================================
--- hybrid_map.hh	2f538b4bd091d63a8b83d92025d60cc5c293d630
+++ hybrid_map.hh	2f538b4bd091d63a8b83d92025d60cc5c293d630
@@ -0,0 +1,238 @@
+#ifndef __HYBRID_MAP_HH__
+#define __HYBRID_MAP_HH__
+
+#include "hash_map.hh"
+#include <map>
+
+template<typename Key, typename Val>
+class hybrid_map
+{
+  typedef std::map<Key, Val> omap;
+  typedef hashmap::hash_map<Key, Val> umap;
+  omap ordered;
+  umap unordered;
+public:
+  typedef typename omap::value_type value_type;
+  typedef typename omap::key_type key_type;
+  typedef typename omap::mapped_type mapped_type;
+  typedef typename omap::size_type size_type;
+  class const_iterator;
+  class iterator
+  {
+    friend class hybrid_map<Key, Val>;
+    bool ordered;
+    bool valid;
+    typename omap::iterator o;
+    typename umap::iterator u;
+    hybrid_map<Key, Val> * n;
+    friend class const_iterator;
+  public:
+    iterator(hybrid_map<Key, Val> * n, typename omap::iterator const & i)
+      : ordered(true), valid(i != n->ordered.end()), o(i), n(n)
+    {}
+    iterator(hybrid_map<Key, Val> * n, typename umap::iterator const & i)
+      : ordered(false), valid(i != n->unordered.end()), u(i), n(n)
+    {}
+    iterator()
+      : valid(false)
+    {}
+    iterator & operator++()
+    {
+      I(valid);
+      if (!ordered)
+        {
+          ordered = true;
+          o = n->ordered.find(u->first);
+        }
+      ++o;
+      valid = (o != n->ordered.end());
+      return *this;
+    }
+    iterator operator++(int)
+    {
+      iterator out = *this;
+      ++*this;
+      return out;
+    }
+    value_type & operator*()
+    {
+      I(valid);
+      if (ordered)
+        return *o;
+      else
+        return *u;
+    }
+    value_type const & operator*() const
+    {
+      I(valid);
+      if (ordered)
+        return *o;
+      else
+        return *u;
+    }
+    value_type * operator->()
+    {
+      I(valid);
+      if (ordered)
+        return o.operator->();
+      else
+        return u.operator->();
+    }
+    value_type const * operator->() const
+    {
+      I(valid);
+      if (ordered)
+        return o.operator->();
+      else
+        return u.operator->();
+    }
+    bool operator==(iterator const & other) const
+    {
+      return (valid == other.valid) && (!valid || (*this)->first == other->first);
+    }
+    bool operator!=(iterator const & other) const
+    {
+      return !(*this == other);
+    }
+  };
+  class const_iterator
+  {
+    friend class hybrid_map<Key, Val>;
+    bool ordered;
+    bool valid;
+    typename omap::const_iterator o;
+    typename umap::const_iterator u;
+    hybrid_map<Key, Val> const * n;
+  public:
+    const_iterator(hybrid_map<Key, Val> const * n,
+		   typename omap::const_iterator const & i)
+      : ordered(true), valid(i != n->ordered.end()), o(i), n(n)
+    {}
+    const_iterator(hybrid_map<Key, Val> const * n,
+		   typename umap::const_iterator const & i)
+      : ordered(false), valid(i != n->unordered.end()), u(i), n(n)
+    {}
+    const_iterator(iterator const & i)
+      : ordered(i.ordered), valid(i.valid), o(i.o), u(i.u), n(i.n)
+    {}
+    const_iterator()
+      : valid(false)
+    {}
+    const_iterator & operator++()
+    {
+      I(valid);
+      if (!ordered)
+        {
+          ordered = true;
+          o = n->ordered.find(u->first);
+        }
+      ++o;
+      valid = (o != n->ordered.end());
+      return *this;
+    }
+    const_iterator operator++(int)
+    {
+      const_iterator out = *this;
+      ++*this;
+      return out;
+    }
+    value_type const & operator*() const
+    {
+      I(valid);
+      if (ordered)
+        return *o;
+      else
+        return *u;
+    }
+    value_type const * operator->() const
+    {
+      I(valid);
+      if (ordered)
+        return o.operator->();
+      else
+        return u.operator->();
+    }
+    bool operator==(const_iterator const & other) const
+    {
+      return (valid == other.valid) && (!valid || (*this)->first == other->first);
+    }
+    bool operator!=(const_iterator const & other) const
+    {
+      return !(*this == other);
+    }
+  };
+  friend class iterator;
+  friend class const_iterator;
+  iterator begin()
+  {
+    return iterator(this, ordered.begin());
+  }
+  iterator end()
+  {
+    return iterator(this, ordered.end());
+  }
+  iterator find(key_type const & k)
+  {
+    return iterator(this, unordered.find(k));
+  }
+  const_iterator begin() const
+  {
+    return const_iterator(this, ordered.begin());
+  }
+  const_iterator end() const
+  {
+    return const_iterator(this, ordered.end());
+  }
+  const_iterator find(key_type const & k) const
+  {
+    return const_iterator(this, unordered.find(k));
+  }
+  size_t size() const
+  {
+    return ordered.size();
+  }
+  std::pair<iterator, bool> insert(value_type const & x)
+  {
+    std::pair<typename omap::iterator, bool> o = ordered.insert(x);
+    unordered.insert(x);
+    std::pair<iterator, bool> out;
+    out.first = iterator(this, o.first);
+    out.second = o.second;
+    return out;
+  }
+  iterator insert(iterator const & where, value_type const & what)
+  {
+    unordered.insert(what);
+    if (where.valid && where.ordered)
+      {
+        return iterator(this, ordered.insert(where.o, what));
+      }
+    else if (!where.valid)
+      {
+        return iterator(this, ordered.insert(ordered.end(), what));
+      }
+    else
+      {
+        std::pair<typename omap::iterator, bool> o = ordered.insert(what);
+        return iterator(this, o.first);
+      }
+  }
+  size_t erase(key_type const & x)
+  {
+    size_t out = ordered.erase(x);
+    unordered.erase(x);
+    return out;
+  }
+  bool empty() const
+  {
+    return ordered.empty();
+  }
+  void clear()
+  {
+    ordered.clear();
+    unordered.clear();
+  }
+};
+
+
+#endif
============================================================
--- Makefile.am	abadfd52468504cc0b30671984d43df3453f3532
+++ Makefile.am	782c145b15c9cb84fe237260d7190fb8d9138649
@@ -74,7 +74,7 @@ MOST_SOURCES = 								\
 	asciik.cc asciik.hh						\
 	dates.cc dates.hh						\
 									\
-	lru_writeback_cache.hh						\
+	lru_writeback_cache.hh hybrid_map.hh				\
 									\
 	cleanup.hh unit_tests.hh					\
 	cycle_detector.hh randomfile.hh adler32.hh			\
============================================================
--- roster.cc	62f172da10ee678623d30fbdafd766f521e2fbc7
+++ roster.cc	6c1f08a21617cc9c626e06beffe52c5dbfe48430
@@ -1191,8 +1191,8 @@ namespace
   {
     // left and right should be equal, except that each may have some attr
     // corpses that the other does not
-    map<node_id, node_t>::const_iterator left_i = left.all_nodes().begin();
-    map<node_id, node_t>::const_iterator right_i = right.all_nodes().begin();
+    node_map::const_iterator left_i = left.all_nodes().begin();
+    node_map::const_iterator right_i = right.all_nodes().begin();
     while (left_i != left.all_nodes().end() || right_i != right.all_nodes().end())
       {
         I(left_i->second->self == right_i->second->self);
@@ -1550,10 +1550,8 @@ mark_merge_roster(roster_t const & left_
        i != merge.all_nodes().end(); ++i)
     {
       node_t const & n = i->second;
-      // SPEEDUP?: instead of using find repeatedly, iterate everything in
-      // parallel
-      map<node_id, node_t>::const_iterator lni = left_roster.all_nodes().find(i->first);
-      map<node_id, node_t>::const_iterator rni = right_roster.all_nodes().find(i->first);
+      node_map::const_iterator lni = left_roster.all_nodes().find(i->first);
+      node_map::const_iterator rni = right_roster.all_nodes().find(i->first);
 
       bool exists_in_left = (lni != left_roster.all_nodes().end());
       bool exists_in_right = (rni != right_roster.all_nodes().end());
============================================================
--- roster.hh	0df1174eb4998443af6c94143f46eb3f8b383f31
+++ roster.hh	58f56b5761388f0c4a35436532a64b6c7812b755
@@ -15,6 +15,7 @@
 #include <boost/shared_ptr.hpp>
 
 #include "cset.hh"
+#include "hybrid_map.hh"
 #include "numeric_vocab.hh"
 #include "paths.hh"
 #include "sanity.hh"
@@ -49,7 +50,7 @@ typedef std::map<path_component, node_t>
 // "undefined" value).
 typedef std::map<attr_key, std::pair<bool, attr_value> > full_attr_map_t;
 typedef std::map<path_component, node_t> dir_map;
-typedef std::map<node_id, node_t> node_map;
+typedef hybrid_map<node_id, node_t> node_map;
 
 template <> void dump(full_attr_map_t const & val, std::string & out);