1f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// Copyright 2010 the V8 project authors. All rights reserved. 2f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// Redistribution and use in source and binary forms, with or without 3f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// modification, are permitted provided that the following conditions are 4f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// met: 5f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// 6f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// * Redistributions of source code must retain the above copyright 7f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// notice, this list of conditions and the following disclaimer. 8f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// * Redistributions in binary form must reproduce the above 9f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// copyright notice, this list of conditions and the following 10f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// disclaimer in the documentation and/or other materials provided 11f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// with the distribution. 12f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// * Neither the name of Google Inc. nor the names of its 13f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// contributors may be used to endorse or promote products derived 14f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// from this software without specific prior written permission. 15f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// 16f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 28f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke#ifndef V8_UNBOUND_QUEUE_ 29f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke#define V8_UNBOUND_QUEUE_ 30f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 31257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch#include "allocation.h" 32257744e915dfc84d6d07a6b2accf8402d9ffc708Ben Murdoch 33f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarkenamespace v8 { 34f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarkenamespace internal { 35f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 36f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 37f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// Lock-free unbound queue for small records. Intended for 38f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// transferring small records between a Single producer and a Single 39f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// consumer. Doesn't have restrictions on the number of queued 40f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// elements, so producer never blocks. Implemented after Herb 41f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// Sutter's article: 42f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// http://www.ddj.com/high-performance-computing/210604448 43f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarketemplate<typename Record> 44f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarkeclass UnboundQueue BASE_EMBEDDED { 45f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke public: 46f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke inline UnboundQueue(); 47f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke inline ~UnboundQueue(); 48f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 49f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke INLINE(void Dequeue(Record* rec)); 50f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke INLINE(void Enqueue(const Record& rec)); 51f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke INLINE(bool IsEmpty()) { return divider_ == last_; } 527f4d5bd8c03935e2c0cd412e561b8fc5a6a880aeBen Murdoch INLINE(Record* Peek()); 53f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 54f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke private: 55f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke INLINE(void DeleteFirst()); 56f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 57f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke struct Node; 58f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 59f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke Node* first_; 60f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke AtomicWord divider_; // Node* 61f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke AtomicWord last_; // Node* 62f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 63f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke DISALLOW_COPY_AND_ASSIGN(UnboundQueue); 64f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke}; 65f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 66f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 67f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke} } // namespace v8::internal 68f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke 69f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke#endif // V8_UNBOUND_QUEUE_ 70