Implement IdentityMap<V>, a robust, GC-safe object-identity HashMap.

src/heap/identity-map.h

Index: src/heap/identity-map.h
diff --git a/src/heap/identity-map.h b/src/heap/identity-map.h
new file mode 100644
index 0000000000000000000000000000000000000000..2effaeac8907b07efac34f6ccf70f61333629911
--- /dev/null
+++ b/src/heap/identity-map.h
@@ -0,0 +1,98 @@
+// Copyright 2015 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef V8_HEAP_IDENTITY_MAP_H_
+#define V8_HEAP_IDENTITY_MAP_H_
+
+#include "src/handles.h"
+
+namespace v8 {
+namespace internal {
+
+class Heap;
+
+// Base class of identity maps contains shared code for all template
+// instantions.
+class IdentityMapBase {
+ public:
+  // Enable or disable concurrent mode for this map. Concurrent mode implies
+  // taking the heap's relocation lock during most operations.
+  void SetConcurrent(bool concurrent) { concurrent_ = concurrent; }
+
+ protected:
+  // Allow Tester to access internals, including changing the address of objects
+  // within the {keys_} array in order to simulate a moving GC.
+  friend class IdentityMapTester;
+
+  typedef void** RawEntry;
+
+  IdentityMapBase(Heap* heap, Zone* zone)
+      : heap_(heap),
+        zone_(zone),
+        concurrent_(false),
+        gc_counter_(-1),
+        size_(0),
+        mask_(0),
+        keys_(nullptr),
+        values_(nullptr) {}
+  ~IdentityMapBase();
+
+  RawEntry GetEntry(Handle<Object> handle);
+  RawEntry FindEntry(Handle<Object> handle);
+
+ private:
+  // Internal implementation should not be called directly by subclasses.
+  int LookupIndex(Object* address);
+  int InsertIndex(Object* address);
+  void Rehash();
+  void Resize();
+  RawEntry Lookup(Handle<Object> handle);
+  RawEntry Insert(Handle<Object> handle);
+  int Hash(Object* address);
+
+  Heap* heap_;
+  Zone* zone_;
+  bool concurrent_;
+  int gc_counter_;
+  int size_;
+  int mask_;
+  Object** keys_;
+  void** values_;
+};
+
+// Implements an identity map from object addresses to a given value type {V}.
+// The value type {V} must be reinterpret_cast'able to void*.
+// The map is robust w.r.t. garbage collection through coordination with the
+// supplied {heap}.
+// Note that in general, SMIs are valid keys, but {SMI #0} is _not_ a valid key.

[Erik Corry, 2015/04/27 15:39:13]

This is a very strange API.  I would either ban SMIs altogether or move to a
tagged null pointer as the internal empty representation and allow all SMIs.

[titzer, 2015/04/27 16:36:48]

I could solve this with a special cell for SMI #0.

The intention was mostly to be useful for real heap objects, but it works with
SMIs too.

+template <typename V>
+class IdentityMap : public IdentityMapBase {
+ public:
+  IdentityMap(Heap* heap, Zone* zone) : IdentityMapBase(heap, zone) {}
+
+  // Searches this map for the given key using the object's address
+  // as the identity, returning:
+  //    found => a pointer to the storage location for the value
+  //    not found => a pointer to a new storage location for the value
+  V* Get(Handle<Object> handle) {
+    return reinterpret_cast<V*>(GetEntry(handle));
+  }
+
+  // Searches this map for the given key using the object's address
+  // as the identity, returning:
+  //    found => a pointer to the storage location for the value
+  //    not found => {nullptr}
+  V* Find(Handle<Object> handle) {

[Erik Corry, 2015/04/27 15:39:13]

Why does this not return a handle?

[titzer, 2015/04/27 16:36:48]

Because the value type V is not a heap object. E.g. we will use this in the
compiler for Node* pointers to canonicalize constants.

+    return reinterpret_cast<V*>(FindEntry(handle));
+  }
+
+  // Set the value for the given key.
+  void Set(Handle<Object> handle, V value) {

[Erik Corry, 2015/04/27 15:39:13]

handle should be called key?  Also several other places?

[titzer, 2015/04/27 16:36:48]

Done.

+    *(reinterpret_cast<V*>(GetEntry(handle))) = value;
+  }
+};
+}
+}  // namespace v8::internal
+
+#endif  // V8_HEAP_IDENTITY_MAP_H_