Object ID Ring with tests

runtime/vm/object_id_ring.cc

Index: runtime/vm/object_id_ring.cc
diff --git a/runtime/vm/object_id_ring.cc b/runtime/vm/object_id_ring.cc
new file mode 100644
index 0000000000000000000000000000000000000000..024d0a04f9204b231baab7dcf8a438f66fd68f92
--- /dev/null
+++ b/runtime/vm/object_id_ring.cc
@@ -0,0 +1,152 @@
+// 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.
+
+#include "platform/assert.h"
+#include "vm/dart_api_state.h"
+#include "vm/object_id_ring.h"
+
+namespace dart {
+
+
+void ObjectIdRing::Init(Isolate* isolate, intptr_t capacity) {
+  ObjectIdRing* ring = new ObjectIdRing(isolate, capacity);
+  if (isolate != NULL) {
+    isolate->set_object_id_ring(ring);
+  }
+}
+
+
+ObjectIdRing::~ObjectIdRing() {
+  ASSERT(table_ != NULL);
+  free(table_);
+  table_ = NULL;
+  if (isolate_ != NULL) {
+    isolate_->set_object_id_ring(NULL);
+    isolate_ = NULL;
+  }
+}
+
+
+intptr_t ObjectIdRing::GetIdForObject(RawObject* object) {
+  return AllocateNewId(object);
+}
+
+
+RawObject* ObjectIdRing::GetObjectForId(intptr_t id) {
+  intptr_t index = IndexOfId(id);
+  if (index == kInvalidId) {
+    return Object::null();

[Ivan Posva, 2013/07/10 01:10:13]

We might want to return an object that is known to have been collected on the
other side of the protocol. For example an object marked as invalid.

[Cutch, 2013/07/10 17:23:10]

Do we want to distinguish between the following two cases?

#1 Object was GC'd
#2 ID is no longer (or never was) valid

+  }
+  ASSERT(index >= 0);
+  ASSERT(index < capacity_);
+  return table_[index];
+}
+
+
+ObjectIdRing::ObjectIdRing(Isolate* isolate, intptr_t capacity) {
+  ASSERT(capacity > 0);
+  isolate_ = isolate;
+  capacity_ = capacity;
+  serial_num_ = 0;
+  wrapped_ = false;
+  RawObject* sizer = NULL;
+  const size_t table_size = sizeof(sizer)*capacity_;
+  table_ = reinterpret_cast<RawObject**>(malloc(table_size));
+  for (int i = 0; i < capacity_; i++) {
+    table_[i] = Object::null();
+  }
+  // The maximum serial number is a multiple of the capacity, so that when
+  // the serial number wraps, the index into table_ wraps with it.
+  max_serial_ = INTPTR_MAX - (INTPTR_MAX % capacity_);
+}
+
+
+intptr_t ObjectIdRing::NextSerial() {
+  intptr_t r = serial_num_;
+  serial_num_++;
+  if (serial_num_ >= max_serial_) {
+    serial_num_ = 0;
+    wrapped_ = true;
+  }
+  return r;
+}
+
+
+intptr_t ObjectIdRing::AllocateNewId(RawObject* raw_obj) {
+  ASSERT(raw_obj->IsHeapObject());

[Ivan Posva, 2013/07/10 01:10:13]

How do you intend to represent Smis on the wire?

[Cutch, 2013/07/10 17:23:10]

When sending objects as JSON there is always a "type" field. For numbers a
message would look like this:

{
"type": "Integer",
"value": 99
}

{
"type": "Double",
"value": 3.14159
}

When referencing an object the type is prefixed with an "@", for example:

{
"type": "@String",
"id": 3
}

If we then requested the String with id three the response would look like:

{
"type": "String",
"value": "Hello World!"
}

Code that serializes objects into JSON should not request an ID for simple
scalar types (e.g. bool, int, double, Float32x4, and Uint32x4) and instead
always send the value.

+  intptr_t id = NextSerial();
+  ASSERT(id != kInvalidId);
+  intptr_t cursor = IndexOfId(id);
+  ASSERT(cursor != kInvalidId);
+  if (table_[cursor] != Object::null()) {
+    // Free old handle.
+    table_[cursor] = Object::null();
+  }
+  ASSERT(table_[cursor] == Object::null());
+  table_[cursor] = raw_obj;
+  return id;
+}
+
+
+intptr_t ObjectIdRing::IndexOfId(intptr_t id) {
+  if (!IsValidId(id)) {
+    return kInvalidId;
+  }
+  ASSERT((id >= 0) && (id < max_serial_));
+  return id % capacity_;
+}
+
+
+bool ObjectIdRing::IsValidContiguous(intptr_t id) {
+  ASSERT(id != kInvalidId);
+  ASSERT((id >= 0) && (id < max_serial_));
+  if (id >= serial_num_) {
+    // Too large.
+    return false;
+  }
+  intptr_t bottom = 0;
+  if (serial_num_ >= capacity_) {
+    bottom = serial_num_ - capacity_;
+  }
+  return id >= bottom;
+}
+
+
+bool ObjectIdRing::IsValidId(intptr_t id) {
+  if (id == kInvalidId) {
+    return false;
+  }
+  if (id >= max_serial_) {
+    return false;
+  }
+  ASSERT((id >= 0) && (id < max_serial_));
+  if (wrapped_) {
+    // Serial number has wrapped around to 0.
+    if (serial_num_ >= capacity_) {
+      // Serial number is larger than capacity, the serial
+      // numbers are contiguous again.
+      wrapped_ = false;
+      return IsValidContiguous(id);
+    } else {
+      // When the serial number first wraps, the valid serial number range
+      // spans two intervals:
+      // #1 [0, serial_num_)
+      // #2 [max_serial_ - (capacity_ - serial_num), max_serial_)
+      //
+      // Check for both.
+      if (id < serial_num_) {
+        // Interval #1
+        return true;
+      }
+      // Interval #2
+      const intptr_t max_serial_num = max_serial_;
+      const intptr_t bottom = max_serial_num - (capacity_ - serial_num_);
+      return id >= bottom && bottom < max_serial_num;
+    }
+  }
+  ASSERT(wrapped_ == false);
+  return IsValidContiguous(id);
+}
+
+}  // namespace dart