Improve queuing for concurrent OSR.

src/utils.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1121 matching lines @@
 
   // Every FunctionState starts with this id.
   static const int kFirstUsableId = 4;
 
   // Every compiled stub starts with this id.
   static const int kStubEntryId = 5;
 
   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_