# # # add_file "vocab_hash.hh" # content [19693ab649648e77ea6fa4fe241566c55d30960f] # # patch "Makefile.am" # from [f9035e38a9a2f131a3b5baf347b1171a4804fcac] # to [abadfd52468504cc0b30671984d43df3453f3532] # # patch "graph.cc" # from [8c67407d007b2849a6f287d086d0a82bd885329b] # to [986d52f599f774e88c0943af5322d972eff31542] # ============================================================ --- vocab_hash.hh 19693ab649648e77ea6fa4fe241566c55d30960f +++ vocab_hash.hh 19693ab649648e77ea6fa4fe241566c55d30960f @@ -0,0 +1,47 @@ +#ifndef __VOCAB_HASH_HH__ +#define __VOCAB_HASH_HH__ + +#include "vocab.hh" +#include "hash_map.hh" + +#define ENCODING(enc) \ + namespace hashmap { \ + template \ + struct hash > \ + { \ + size_t operator()(enc const & t) const \ + { \ + return hash()(t()); \ + } \ + }; \ + } + +#define DECORATE(dec) \ + namespace hashmap { \ + template \ + struct hash > \ + { \ + size_t operator()(dec const & t) const \ + { \ + return hash()(t.inner()); \ + } \ + }; \ + } + +#define ATOMIC(ty) \ + namespace hashmap { \ + template<> \ + struct hash \ + { \ + size_t operator()(ty const & t) const \ + { \ + return hash()(t()); \ + } \ + }; \ + } + +#define ATOMIC_NOVERIFY(ty) ATOMIC(ty) + +#include "vocab_terms.hh" + +#endif ============================================================ --- Makefile.am f9035e38a9a2f131a3b5baf347b1171a4804fcac +++ Makefile.am abadfd52468504cc0b30671984d43df3453f3532 @@ -16,7 +16,7 @@ LUAEXT_SOURCES = \ LUAEXT_SOURCES = \ vocab.hh vocab.cc vocab_terms.hh vocab_macros.hh vocab_cast.hh \ charset.cc charset.hh paths.cc paths.hh \ - interner.hh hash_map.hh \ + interner.hh hash_map.hh vocab_hash.hh \ luaext_mkstemp.cc luaext_parse_basic_io.cc \ luaext_guess_binary.cc luaext_platform.cc luaext_globish.cc \ lua.cc lua.hh mkstemp.cc mkstemp.hh file_io.cc file_io.hh \ ============================================================ --- graph.cc 8c67407d007b2849a6f287d086d0a82bd885329b +++ graph.cc 986d52f599f774e88c0943af5322d972eff31542 @@ -7,6 +7,8 @@ #include "graph.hh" #include "safe_map.hh" #include "numeric_vocab.hh" +#include "hash_map.hh" +#include "vocab_hash.hh" using boost::shared_ptr; using std::string; @@ -18,6 +20,8 @@ using std::list; using std::make_pair; using std::list; +using hashmap::hash_set; + void get_reconstruction_path(std::string const & start, reconstruction_graph const & graph, @@ -281,37 +285,28 @@ static void typedef std::pair height_rev_pair; static void -do_step_ancestor(set & this_frontier, - set & this_seen, - set const & other_seen, - set & this_uncommon_ancs, +advance_frontier(set & frontier, + hash_set & seen, rev_graph const & rg) { - const height_rev_pair h_node = *this_frontier.rbegin(); + const height_rev_pair h_node = *frontier.rbegin(); const revision_id & node(h_node.second); - this_frontier.erase(h_node); - if (other_seen.find(node) == other_seen.end()) - { - this_uncommon_ancs.insert(node); - } - - // extend the frontier with parents + frontier.erase(h_node); set parents; rg.get_parents(node, parents); for (set::const_iterator r = parents.begin(); r != parents.end(); r++) { - if (this_seen.find(*r) == this_seen.end()) + if (seen.find(*r) == seen.end()) { rev_height h; rg.get_height(*r, h); - this_frontier.insert(make_pair(h, *r)); - this_seen.insert(*r); + frontier.insert(make_pair(h, *r)); + seen.insert(*r); } } } - void get_uncommon_ancestors(revision_id const & a, revision_id const & b, @@ -328,7 +323,7 @@ get_uncommon_ancestors(revision_id const // any common ancestor will have been 'seen' by both sides // before it is traversed. - set a_frontier, b_frontier; + set a_frontier, b_frontier, common_frontier; { rev_height h; rg.get_height(a, h); @@ -337,48 +332,58 @@ get_uncommon_ancestors(revision_id const b_frontier.insert(make_pair(h, b)); } - set a_seen, b_seen; + hash_set a_seen, b_seen, common_seen; a_seen.insert(a); b_seen.insert(b); while (!a_frontier.empty() || !b_frontier.empty()) { - // We take the leaf-most (ie highest) height entry from either - // a_frontier or b_frontier. - // If one of them is empty, we take entries from the other. - bool step_a; - if (a_frontier.empty()) - { - step_a = false; - } - else - { - if (!b_frontier.empty()) + // We take the leaf-most (ie highest) height entry from any frontier. + // Note: the default height is the lowest possible. + rev_height a_height, b_height, common_height; + if (!a_frontier.empty()) + a_height = a_frontier.rbegin()->first; + if (!b_frontier.empty()) + b_height = b_frontier.rbegin()->first; + if (!common_frontier.empty()) + common_height = common_frontier.rbegin()->first; + + if (a_height > b_height && a_height > common_height) { + a_uncommon_ancs.insert(a_frontier.rbegin()->second); + advance_frontier(a_frontier, a_seen, rg); + } + else if (b_height > a_height && b_height > common_height) + { + b_uncommon_ancs.insert(b_frontier.rbegin()->second); + advance_frontier(b_frontier, b_seen, rg); + } + else if (common_height > a_height && common_height > b_height) + { + advance_frontier(common_frontier, common_seen, rg); + } + else if (a_height == b_height) // may or may not also == common_height + { + // if both frontiers are the same, then we can safely say that + // we've found all uncommon ancestors. This stopping condition + // can result in traversing more nodes than required, but is simple. if (a_frontier == b_frontier) - { - // if both frontiers are the same, then we can safely say that - // we've found all uncommon ancestors. This stopping condition - // can result in traversing more nodes than required, but is simple. break; - } - step_a = (*a_frontier.rbegin() > *b_frontier.rbegin()); + + common_frontier.insert(*a_frontier.rbegin()); + a_frontier.erase(*a_frontier.rbegin()); + b_frontier.erase(*b_frontier.rbegin()); } - else + else if (a_height == common_height) { - // b is empty - step_a = true; + a_frontier.erase(*a_frontier.rbegin()); } - } - - if (step_a) - { - do_step_ancestor(a_frontier, a_seen, b_seen, a_uncommon_ancs, rg); - } + else if (b_height == common_height) + { + b_frontier.erase(*b_frontier.rbegin()); + } else - { - do_step_ancestor(b_frontier, b_seen, a_seen, b_uncommon_ancs, rg); - } + I(false); } }