Improve queuing for concurrent OSR.

src/utils.h

Index: src/utils.h
diff --git a/src/utils.h b/src/utils.h
index 4a08319044bf7f0768970f539a1a41ac3f298747..bcee634af88a5cddcf86b55621ccb7ea83631aa7 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -1139,6 +1139,126 @@ class BailoutId {
   int id_;
 };
 
+
+template <typename T>
+class CircularBuffer {

[titzer, 2013/10/10 09:41:57]

This class needs some unit tests.

+ public:
+  explicit CircularBuffer(int capacity) : capacity_(capacity), cursor_(0) {
+    ASSERT_LT(0, capacity);
+    buffer_ = NewArray<T>(capacity_);
+    for (int i = 0; i < capacity_; i++) buffer_[i] = NULL;
+  }
+
+  ~CircularBuffer() {
+#ifdef DEBUG
+    for (int i = 0; i < capacity_; i++) CHECK_EQ(NULL, buffer_[i]);
+#endif
+    DeleteArray(buffer_);
+    buffer_ = NULL;
+  }
+
+  T Get(int i) {
+    ASSERT_LE(0, i);
+    ASSERT_LT(i, capacity_);
+    return buffer_[i];
+  }
+
+  T Remove(int i) {
+    T evicted = buffer_[i];
+    buffer_[i] = NULL;
+    return evicted;
+  }
+
+  // Add an item to the cursor position and advance the cursor.  Return
+  // the object pointer being overwritten.
+  T Add(T item) {
+    T evicted = buffer_[cursor_];
+    buffer_[cursor_] = item;
+    AdvanceCursor();
+    return evicted;
+  }
+
+  T Current() {
+    return buffer_[cursor_];
+  }
+
+  void AdvanceCursor() {
+    cursor_ = (cursor_ + 1) % capacity_;
+  }
+
+  int capacity() { return capacity_; }
+
+ private:
+  int capacity_;
+  int cursor_;
+  T* buffer_;
+};
+
+
+template <typename T>
+class CircularQueue {

[titzer, 2013/10/10 09:41:57]

And this one too.

+ public:
+  explicit CircularQueue(int capacity)
+      : capacity_(capacity), length_(0), shift_(0) {
+    ASSERT_LT(0, capacity);
+    buffer_ = NewArray<T>(capacity_);
+#ifdef DEBUG
+    for (int i = 0; i < capacity_; i++) buffer_[i] = NULL;
+#endif  // DEBUG
+  }
+
+  ~CircularQueue() {
+    ASSERT_EQ(0, length_);
+    DeleteArray(buffer_);
+    buffer_ = NULL;
+  }
+
+  int length() { return length_; }
+  bool available() { return length_ < capacity_; }
+
+  void Enqueue(const T& item) {
+    ASSERT(available());
+    int index = ConvertIndex(length_);
+    buffer_[index] = item;
+    length_++;
+  }
+
+  void Prepend(const T& item) {
+    ASSERT(available());
+    int index = ConvertIndex(capacity_ - 1);  // Move shift_ back by one.
+    shift_ = index;
+    buffer_[index] = item;
+    length_++;
+  }
+
+  T Dequeue() {
+    ASSERT_LT(0, length_);
+    int index = ConvertIndex(0);
+    shift_ = ConvertIndex(1);
+    length_--;
+    T result = buffer_[index];
+#ifdef DEBUG
+    ASSERT_NE(NULL, result);
+    buffer_[index] = NULL;
+#endif  // DEBUG
+    return result;
+  }
+
+ private:
+  // Convert access index to backing store index.
+  int ConvertIndex(int i) {
+    int result = (i + shift_) % capacity_;
+    ASSERT_LE(0, result);
+    ASSERT_LT(result, capacity_);
+    return result;
+  }
+
+  int capacity_;
+  int length_;
+  int shift_;
+  T* buffer_;
+};
+
 } }  // namespace v8::internal
 
 #endif  // V8_UTILS_H_