Use std::unordered_multimap for BindingHash (#357)

This change can't really be done in isolation, since once we add members
with constructors to a struct, it is no longer has a trivial
constructor. This propagates through all types that use it, etc.

There are a number of changes that are ugly, but hopefully reduced the
amount of code that needed to change. In particular, I changed some
union members to pointers so they would stay trivially constructible.

Another tricky change is the handling of duplicate bindings: previously
we just relied on the fact that our hash implementation would be
consistent. A nicer solution is to display the duplicated bindings in
source order. There's probably a nicer way to do this; bikeshedding
welcome. :-)

1 files changed, 34 insertions, 18 deletions

diff --git a/src/binding-hash.h b/src/binding-hash.h
index 57b5018c..92d43d86 100644
--- a/src/binding-hash.h
+++ b/src/binding-hash.h
@@ -18,34 +18,50 @@
 #define WABT_BINDING_HASH_H_
 
 #include "common.h"
-#include "vector.h"
+
+#include <string>
+#include <vector>
+#include <unordered_map>
 
 namespace wabt {
 
 struct Binding {
+  explicit Binding(int index) : index(index) {
+    WABT_ZERO_MEMORY(loc);
+  }
+  Binding(const Location& loc, int index) : loc(loc), index(index) {}
+
   Location loc;
-  StringSlice name;
   int index;
 };
 
-struct BindingHashEntry {
-  Binding binding;
-  struct BindingHashEntry* next;
-  struct BindingHashEntry* prev; /* only valid when this entry is unused */
-};
-WABT_DEFINE_VECTOR(binding_hash_entry, BindingHashEntry);
+// This class derives from a C++ container, which is usually not advisable
+// because they don't have virtual destructors. So don't delete a BindingHash
+// object through a pointer to std::unordered_multimap.
+class BindingHash : public std::unordered_multimap<std::string, Binding> {
+ public:
+  typedef void (*DuplicateCallback)(const value_type& a,
+                                    const value_type& b,
+                                    void* user_data);
 
-struct BindingHash {
-  BindingHashEntryVector entries;
-  BindingHashEntry* free_head;
-};
+  void find_duplicates(DuplicateCallback callback, void* user_data) const;
 
-Binding* insert_binding(BindingHash*, const StringSlice*);
-void remove_binding(BindingHash*, const StringSlice*);
-bool hash_entry_is_free(const BindingHashEntry*);
-/* returns -1 if the name is not in the hash */
-int find_binding_index_by_name(const BindingHash*, const StringSlice* name);
-void destroy_binding_hash(BindingHash*);
+  int find_index(const StringSlice& name) const {
+    auto iter = find(string_slice_to_string(name));
+    if (iter != end())
+      return iter->second.index;
+    return -1;
+  }
+
+ private:
+  typedef std::vector<const value_type*> ValueTypeVector;
+
+  void create_duplicates_vector(ValueTypeVector* out_duplicates) const;
+  void sort_duplicates_vector_by_location(ValueTypeVector* duplicates) const;
+  void call_callbacks(const ValueTypeVector& duplicates,
+                      DuplicateCallback callback,
+                      void* user_data) const;
+};
 
 }  // namespace wabt