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..a3f1921ebccf2d43a1813f38021b7676ea8a09cf
--- /dev/null
+++ b/src/heap/identity-map.h
@@ -0,0 +1,115 @@
+// 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) {

[Benedikt Meurer, 2015/04/27 04:04:18]

Style nit: Since these methods are private, and all call sites are in the .cc
file anyway, there's probably no reason to have them in the .h file. Can you
move them to the .cc file as well?

[titzer, 2015/04/27 10:43:03]

Done.

+    AllowHandleDereference for_lookup;
+    int index = LookupIndex(*handle);

[Benedikt Meurer, 2015/04/27 04:04:18]

How about size_t here, and check for index < size_ instead of index >= 0?

[titzer, 2015/04/27 10:43:03]

I think int works better here, since we are using as an index, and negative for
out-of-bounds is a pretty clear indication.

+    return index >= 0 ? &values_[index] : nullptr;
+  }
+
+  RawEntry Insert(Handle<Object> handle) {

[Benedikt Meurer, 2015/04/27 04:04:17]

Style nit: Since these methods are private, and all call sites are in the .cc
file anyway, there's probably no reason to have them in the .h file. Can you
move them to the .cc file as well?

[titzer, 2015/04/27 10:43:03]

Done.

+    AllowHandleDereference for_lookup;
+    int index = InsertIndex(*handle);
+    DCHECK_GE(index, 0);
+    return &values_[index];
+  }
+
+  int Hash(Object* address) {

[Benedikt Meurer, 2015/04/27 04:04:18]

Style nit: Since these methods are private, and all call sites are in the .cc
file anyway, there's probably no reason to have them in the .h file. Can you
move them to the .cc file as well?

[titzer, 2015/04/27 10:43:03]

Done.

+    uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
+    CHECK_NE(0, raw_address);  // cannot store Smi 0 as a key here, sorry.
+    // xor some of the upper bits, since the lower 2 or 3 are usually aligned.
+    return static_cast<int>((raw_address >> 11) ^ raw_address);

[Benedikt Meurer, 2015/04/27 04:04:17]

Down casting to int looks wrong here. How about using uintptr_t here? Or even
better use size_t?

[Sven Panne, 2015/04/27 06:26:47]

Veto from the *San sheriff, too: This line is causing implementation-defined
behavior...

[titzer, 2015/04/27 07:57:51]

This is the computation of a hashcode from an address and is inherently
implementation-dependent. This is not _undefined_ behavior.

[titzer, 2015/04/27 10:43:03]

size_t isn't any safer than int. As per below comment, both are
implementation-dependent, but this is a hash operation, so it doesn't matter.

+  }
+
+  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.
+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) {
+    return reinterpret_cast<V*>(FindEntry(handle));
+  }
+
+  // Set the value for the given key.
+  void Set(Handle<Object> handle, V value) {
+    *(reinterpret_cast<V*>(GetEntry(handle))) = value;
+  }
+};
+}
+}  // namespace v8::internal
+
+#endif  // V8_HEAP_IDENTITY_MAP_H_