1edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// Copyright 2010 the V8 project authors. All rights reserved. 2edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// Redistribution and use in source and binary forms, with or without 3edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// modification, are permitted provided that the following conditions are 4edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// met: 5edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 6edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// * Redistributions of source code must retain the above copyright 7edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// notice, this list of conditions and the following disclaimer. 8edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// * Redistributions in binary form must reproduce the above 9edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// copyright notice, this list of conditions and the following 10edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// disclaimer in the documentation and/or other materials provided 11edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// with the distribution. 12edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// * Neither the name of Google Inc. nor the names of its 13edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// contributors may be used to endorse or promote products derived 14edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// from this software without specific prior written permission. 15edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// 16edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171c8e95cf86f2182986385bc1ee85f13f425f3a3aJamie Gennis// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181c8e95cf86f2182986385bc1ee85f13f425f3a3aJamie Gennis// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2363f165fd6b86d04be94d4023e845e98560504a96Keun young Park// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 28edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#ifndef V8_UNBOUND_QUEUE_ 29edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project#define V8_UNBOUND_QUEUE_ 30edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 31c5b2c0bf8007562536b822eb060fc54a01f8e08bMathias Agopian#include "allocation.h" 32c5b2c0bf8007562536b822eb060fc54a01f8e08bMathias Agopian 337303c6bf1a8b00a0e7d8165d774a1f259b4ccda9Mathias Agopiannamespace v8 { 3499b49840d309727678b77403d6cc9f920111623fMathias Agopiannamespace internal { 357303c6bf1a8b00a0e7d8165d774a1f259b4ccda9Mathias Agopian 36c666cae2d5995097ec49a87e375e2afdd92802b7Mathias Agopian 37c666cae2d5995097ec49a87e375e2afdd92802b7Mathias Agopian// Lock-free unbound queue for small records. Intended for 38921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian// transferring small records between a Single producer and a Single 391a4d883dcc1725892bfb5c28dec255a233186524Jamie Gennis// consumer. Doesn't have restrictions on the number of queued 404803b74e2a12a508f7bbfde6f6a962fe3299c61cAndy McFadden// elements, so producer never blocks. Implemented after Herb 411a4d883dcc1725892bfb5c28dec255a233186524Jamie Gennis// Sutter's article: 42e3c697fb929c856b59fa56a8e05a2a7eba187c3dMathias Agopian// http://www.ddj.com/high-performance-computing/210604448 43392edd88cb63d71a21a86a02cf9c56ac97637128Jamie Gennistemplate<typename Record> 44921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopianclass UnboundQueue BASE_EMBEDDED { 45921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian public: 46921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian inline UnboundQueue(); 474803b74e2a12a508f7bbfde6f6a962fe3299c61cAndy McFadden inline ~UnboundQueue(); 48d0566bc26fcf6ca396118701fa11900b627f2c09Mathias Agopian 49cde87a3b9d3f8dc15232d927b56ee9e5e520f58dMathias Agopian INLINE(bool Dequeue(Record* rec)); 50edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project INLINE(void Enqueue(const Record& rec)); 51edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project INLINE(bool IsEmpty() const); 52edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project INLINE(Record* Peek() const); 531c8e95cf86f2182986385bc1ee85f13f425f3a3aJamie Gennis 54edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project private: 55921e6ac4b7610a178285898d191eb0e3afe906c0Mathias Agopian INLINE(void DeleteFirst()); 56ca08833d5ea99130797e10ad68a651b50e99da74Mathias Agopian 57edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project struct Node; 583e25fd8609b100a75721be82d1d499f0ae9083cbMathias Agopian 59edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project Node* first_; 603e25fd8609b100a75721be82d1d499f0ae9083cbMathias Agopian AtomicWord divider_; // Node* 6190ac799241f077a7b7e6c1875fd933864c8dd2a7Mathias Agopian AtomicWord last_; // Node* 620f2f5ff75b7b48ceb64270655ee6b62d09bf4d00Mathias Agopian 63d0566bc26fcf6ca396118701fa11900b627f2c09Mathias Agopian DISALLOW_COPY_AND_ASSIGN(UnboundQueue); 641f7bec634f19c123410a5155c8d282e177c01930Mathias Agopian}; 65edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 66edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 67edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project} } // namespace v8::internal 68edbf3b6af777b721cd2a1ef461947e51e88241e1The Android Open Source Project 69a49126087b4494f4ef50873f3a3f6727265f6621Mathias Agopian#endif // V8_UNBOUND_QUEUE_ 70a350ff98692b3a50cad5cc93f9f83221242ca86aMathias Agopian