Object ID Ring with tests

runtime/vm/object_id_ring.h

Index: runtime/vm/object_id_ring.h
diff --git a/runtime/vm/object_id_ring.h b/runtime/vm/object_id_ring.h
new file mode 100644
index 0000000000000000000000000000000000000000..f03097cfb10cd71e5bd47c4443d71d7618f46aa1
--- /dev/null
+++ b/runtime/vm/object_id_ring.h
@@ -0,0 +1,54 @@
+// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+#ifndef VM_OBJECT_ID_RING_H_
+#define VM_OBJECT_ID_RING_H_
+
+namespace dart {
+
+// Forward declarations.
+class RawObject;
+class Isolate;
+
+// A ring buffer of object pointers that have been given an id. An object
+// may be pointed to by multiple ids. Objects contained in the ring will
+// be preserved across scavenges but not old space collections.
+// When the ring buffer wraps around older objects will be replaced and their
+// ids will be invalidated.
+class ObjectIdRing {
+ public:
+  static const intptr_t kInvalidId = -1;
+  static const intptr_t kDefaultCapacity = 1024;
+
+  static void Init(Isolate* isolate, intptr_t capacity = kDefaultCapacity);
+
+  ~ObjectIdRing();
+
+  intptr_t GetIdForObject(RawObject* raw_obj);
+  RawObject* GetObjectForId(intptr_t id);
+
+ private:
+  friend class Isolate;
+  friend class ObjectIdRingTestHelper;
+
+  ObjectIdRing(Isolate* isolate, intptr_t capacity);
+  Isolate* isolate_;
+  RawObject** table_;
+  intptr_t max_serial_;
+  intptr_t capacity_;
+  intptr_t serial_num_;
+  bool wrapped_;
+
+  intptr_t NextSerial();
+  intptr_t AllocateNewId(RawObject* object);
+  intptr_t IndexOfId(intptr_t id);
+  bool IsValidContiguous(intptr_t id);
+  bool IsValidId(intptr_t id);
+
+  DISALLOW_COPY_AND_ASSIGN(ObjectIdRing);
+};
+
+}  // namespace dart
+
+#endif  // VM_OBJECT_ID_RING_H_