duke@435: /* xdono@1014: * Copyright 2001-2009 Sun Microsystems, Inc. All Rights Reserved. duke@435: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@435: * duke@435: * This code is free software; you can redistribute it and/or modify it duke@435: * under the terms of the GNU General Public License version 2 only, as duke@435: * published by the Free Software Foundation. duke@435: * duke@435: * This code is distributed in the hope that it will be useful, but WITHOUT duke@435: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@435: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@435: * version 2 for more details (a copy is included in the LICENSE file that duke@435: * accompanied this code). duke@435: * duke@435: * You should have received a copy of the GNU General Public License version duke@435: * 2 along with this work; if not, write to the Free Software Foundation, duke@435: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@435: * duke@435: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, duke@435: * CA 95054 USA or visit www.sun.com if you need additional information or duke@435: * have any questions. duke@435: * duke@435: */ duke@435: duke@435: class TaskQueueSuper: public CHeapObj { duke@435: protected: jcoomes@1342: // Internal type for indexing the queue; also used for the tag. jcoomes@1342: typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t; jcoomes@1342: jcoomes@1342: // The first free element after the last one pushed (mod N). ysr@976: volatile uint _bottom; duke@435: jcoomes@1342: enum { jcoomes@1342: N = 1 << NOT_LP64(14) LP64_ONLY(17), // Queue size: 16K or 128K jcoomes@1342: MOD_N_MASK = N - 1 // To compute x mod N efficiently. duke@435: }; duke@435: jcoomes@1342: class Age { jcoomes@1342: public: jcoomes@1342: Age(size_t data = 0) { _data = data; } jcoomes@1342: Age(const Age& age) { _data = age._data; } jcoomes@1342: Age(idx_t top, idx_t tag) { _fields._top = top; _fields._tag = tag; } duke@435: jcoomes@1342: Age get() const volatile { return _data; } jcoomes@1342: void set(Age age) volatile { _data = age._data; } duke@435: jcoomes@1342: idx_t top() const volatile { return _fields._top; } jcoomes@1342: idx_t tag() const volatile { return _fields._tag; } duke@435: jcoomes@1342: // Increment top; if it wraps, increment tag also. jcoomes@1342: void increment() { jcoomes@1342: _fields._top = increment_index(_fields._top); jcoomes@1342: if (_fields._top == 0) ++_fields._tag; jcoomes@1342: } duke@435: jcoomes@1342: Age cmpxchg(const Age new_age, const Age old_age) volatile { jcoomes@1342: return (size_t) Atomic::cmpxchg_ptr((intptr_t)new_age._data, jcoomes@1342: (volatile intptr_t *)&_data, jcoomes@1342: (intptr_t)old_age._data); duke@435: } jcoomes@1342: jcoomes@1342: bool operator ==(const Age& other) const { return _data == other._data; } jcoomes@1342: jcoomes@1342: private: jcoomes@1342: struct fields { jcoomes@1342: idx_t _top; jcoomes@1342: idx_t _tag; jcoomes@1342: }; jcoomes@1342: union { jcoomes@1342: size_t _data; jcoomes@1342: fields _fields; jcoomes@1342: }; duke@435: }; jcoomes@1342: jcoomes@1342: volatile Age _age; jcoomes@1342: jcoomes@1342: // These both operate mod N. jcoomes@1342: static uint increment_index(uint ind) { jcoomes@1342: return (ind + 1) & MOD_N_MASK; duke@435: } jcoomes@1342: static uint decrement_index(uint ind) { jcoomes@1342: return (ind - 1) & MOD_N_MASK; duke@435: } duke@435: jcoomes@1342: // Returns a number in the range [0..N). If the result is "N-1", it should be jcoomes@1342: // interpreted as 0. ysr@976: uint dirty_size(uint bot, uint top) { jcoomes@1342: return (bot - top) & MOD_N_MASK; duke@435: } duke@435: duke@435: // Returns the size corresponding to the given "bot" and "top". ysr@976: uint size(uint bot, uint top) { ysr@976: uint sz = dirty_size(bot, top); jcoomes@1342: // Has the queue "wrapped", so that bottom is less than top? There's a jcoomes@1342: // complicated special case here. A pair of threads could perform pop_local jcoomes@1342: // and pop_global operations concurrently, starting from a state in which jcoomes@1342: // _bottom == _top+1. The pop_local could succeed in decrementing _bottom, jcoomes@1342: // and the pop_global in incrementing _top (in which case the pop_global jcoomes@1342: // will be awarded the contested queue element.) The resulting state must jcoomes@1342: // be interpreted as an empty queue. (We only need to worry about one such jcoomes@1342: // event: only the queue owner performs pop_local's, and several concurrent jcoomes@1342: // threads attempting to perform the pop_global will all perform the same jcoomes@1342: // CAS, and only one can succeed.) Any stealing thread that reads after jcoomes@1342: // either the increment or decrement will see an empty queue, and will not jcoomes@1342: // join the competitors. The "sz == -1 || sz == N-1" state will not be jcoomes@1342: // modified by concurrent queues, so the owner thread can reset the state to jcoomes@1342: // _bottom == top so subsequent pushes will be performed normally. jcoomes@1342: return (sz == N - 1) ? 0 : sz; duke@435: } duke@435: duke@435: public: duke@435: TaskQueueSuper() : _bottom(0), _age() {} duke@435: duke@435: // Return "true" if the TaskQueue contains any tasks. duke@435: bool peek(); duke@435: duke@435: // Return an estimate of the number of elements in the queue. duke@435: // The "careful" version admits the possibility of pop_local/pop_global duke@435: // races. ysr@976: uint size() { jcoomes@1342: return size(_bottom, _age.top()); duke@435: } duke@435: ysr@976: uint dirty_size() { jcoomes@1342: return dirty_size(_bottom, _age.top()); duke@435: } duke@435: ysr@777: void set_empty() { ysr@777: _bottom = 0; jcoomes@1342: _age.set(0); ysr@777: } ysr@777: duke@435: // Maximum number of elements allowed in the queue. This is two less duke@435: // than the actual queue size, for somewhat complicated reasons. jcoomes@1342: uint max_elems() { return N - 2; } duke@435: }; duke@435: duke@435: template class GenericTaskQueue: public TaskQueueSuper { duke@435: private: duke@435: // Slow paths for push, pop_local. (pop_global has no fast path.) ysr@976: bool push_slow(E t, uint dirty_n_elems); ysr@976: bool pop_local_slow(uint localBot, Age oldAge); duke@435: duke@435: public: duke@435: // Initializes the queue to empty. duke@435: GenericTaskQueue(); duke@435: duke@435: void initialize(); duke@435: duke@435: // Push the task "t" on the queue. Returns "false" iff the queue is duke@435: // full. duke@435: inline bool push(E t); duke@435: duke@435: // If succeeds in claiming a task (from the 'local' end, that is, the duke@435: // most recently pushed task), returns "true" and sets "t" to that task. duke@435: // Otherwise, the queue is empty and returns false. duke@435: inline bool pop_local(E& t); duke@435: duke@435: // If succeeds in claiming a task (from the 'global' end, that is, the duke@435: // least recently pushed task), returns "true" and sets "t" to that task. duke@435: // Otherwise, the queue is empty and returns false. duke@435: bool pop_global(E& t); duke@435: duke@435: // Delete any resource associated with the queue. duke@435: ~GenericTaskQueue(); duke@435: ysr@777: // apply the closure to all elements in the task queue ysr@777: void oops_do(OopClosure* f); ysr@777: duke@435: private: duke@435: // Element array. duke@435: volatile E* _elems; duke@435: }; duke@435: duke@435: template duke@435: GenericTaskQueue::GenericTaskQueue():TaskQueueSuper() { jcoomes@1342: assert(sizeof(Age) == sizeof(size_t), "Depends on this."); duke@435: } duke@435: duke@435: template duke@435: void GenericTaskQueue::initialize() { jcoomes@1342: _elems = NEW_C_HEAP_ARRAY(E, N); duke@435: guarantee(_elems != NULL, "Allocation failed."); duke@435: } duke@435: duke@435: template ysr@777: void GenericTaskQueue::oops_do(OopClosure* f) { ysr@777: // tty->print_cr("START OopTaskQueue::oops_do"); ysr@976: uint iters = size(); ysr@976: uint index = _bottom; ysr@976: for (uint i = 0; i < iters; ++i) { ysr@777: index = decrement_index(index); ysr@777: // tty->print_cr(" doing entry %d," INTPTR_T " -> " INTPTR_T, ysr@777: // index, &_elems[index], _elems[index]); ysr@777: E* t = (E*)&_elems[index]; // cast away volatility ysr@777: oop* p = (oop*)t; ysr@777: assert((*t)->is_oop_or_null(), "Not an oop or null"); ysr@777: f->do_oop(p); ysr@777: } ysr@777: // tty->print_cr("END OopTaskQueue::oops_do"); ysr@777: } ysr@777: ysr@777: ysr@777: template ysr@976: bool GenericTaskQueue::push_slow(E t, uint dirty_n_elems) { jcoomes@1342: if (dirty_n_elems == N - 1) { duke@435: // Actually means 0, so do the push. ysr@976: uint localBot = _bottom; duke@435: _elems[localBot] = t; bobv@1459: OrderAccess::release_store(&_bottom, increment_index(localBot)); duke@435: return true; jcoomes@1342: } jcoomes@1342: return false; duke@435: } duke@435: duke@435: template duke@435: bool GenericTaskQueue:: ysr@976: pop_local_slow(uint localBot, Age oldAge) { duke@435: // This queue was observed to contain exactly one element; either this duke@435: // thread will claim it, or a competing "pop_global". In either case, duke@435: // the queue will be logically empty afterwards. Create a new Age value duke@435: // that represents the empty queue for the given value of "_bottom". (We duke@435: // must also increment "tag" because of the case where "bottom == 1", duke@435: // "top == 0". A pop_global could read the queue element in that case, duke@435: // then have the owner thread do a pop followed by another push. Without duke@435: // the incrementing of "tag", the pop_global's CAS could succeed, duke@435: // allowing it to believe it has claimed the stale element.) jcoomes@1342: Age newAge((idx_t)localBot, oldAge.tag() + 1); duke@435: // Perhaps a competing pop_global has already incremented "top", in which duke@435: // case it wins the element. duke@435: if (localBot == oldAge.top()) { duke@435: // No competing pop_global has yet incremented "top"; we'll try to duke@435: // install new_age, thus claiming the element. jcoomes@1342: Age tempAge = _age.cmpxchg(newAge, oldAge); duke@435: if (tempAge == oldAge) { duke@435: // We win. jcoomes@1342: assert(dirty_size(localBot, _age.top()) != N - 1, "sanity"); duke@435: return true; duke@435: } duke@435: } jcoomes@1342: // We lose; a completing pop_global gets the element. But the queue is empty jcoomes@1342: // and top is greater than bottom. Fix this representation of the empty queue jcoomes@1342: // to become the canonical one. jcoomes@1342: _age.set(newAge); jcoomes@1342: assert(dirty_size(localBot, _age.top()) != N - 1, "sanity"); duke@435: return false; duke@435: } duke@435: duke@435: template duke@435: bool GenericTaskQueue::pop_global(E& t) { jcoomes@1342: Age oldAge = _age.get(); ysr@976: uint localBot = _bottom; ysr@976: uint n_elems = size(localBot, oldAge.top()); duke@435: if (n_elems == 0) { duke@435: return false; duke@435: } jcoomes@1342: duke@435: t = _elems[oldAge.top()]; jcoomes@1342: Age newAge(oldAge); jcoomes@1342: newAge.increment(); jcoomes@1342: Age resAge = _age.cmpxchg(newAge, oldAge); jcoomes@1342: duke@435: // Note that using "_bottom" here might fail, since a pop_local might duke@435: // have decremented it. jcoomes@1342: assert(dirty_size(localBot, newAge.top()) != N - 1, "sanity"); jcoomes@1342: return resAge == oldAge; duke@435: } duke@435: duke@435: template duke@435: GenericTaskQueue::~GenericTaskQueue() { duke@435: FREE_C_HEAP_ARRAY(E, _elems); duke@435: } duke@435: duke@435: // Inherits the typedef of "Task" from above. duke@435: class TaskQueueSetSuper: public CHeapObj { duke@435: protected: duke@435: static int randomParkAndMiller(int* seed0); duke@435: public: duke@435: // Returns "true" if some TaskQueue in the set contains a task. duke@435: virtual bool peek() = 0; duke@435: }; duke@435: duke@435: template class GenericTaskQueueSet: public TaskQueueSetSuper { duke@435: private: ysr@976: uint _n; duke@435: GenericTaskQueue** _queues; duke@435: duke@435: public: duke@435: GenericTaskQueueSet(int n) : _n(n) { duke@435: typedef GenericTaskQueue* GenericTaskQueuePtr; duke@435: _queues = NEW_C_HEAP_ARRAY(GenericTaskQueuePtr, n); duke@435: guarantee(_queues != NULL, "Allocation failure."); duke@435: for (int i = 0; i < n; i++) { duke@435: _queues[i] = NULL; duke@435: } duke@435: } duke@435: ysr@976: bool steal_1_random(uint queue_num, int* seed, E& t); ysr@976: bool steal_best_of_2(uint queue_num, int* seed, E& t); ysr@976: bool steal_best_of_all(uint queue_num, int* seed, E& t); duke@435: ysr@976: void register_queue(uint i, GenericTaskQueue* q); duke@435: ysr@976: GenericTaskQueue* queue(uint n); duke@435: duke@435: // The thread with queue number "queue_num" (and whose random number seed duke@435: // is at "seed") is trying to steal a task from some other queue. (It duke@435: // may try several queues, according to some configuration parameter.) duke@435: // If some steal succeeds, returns "true" and sets "t" the stolen task, duke@435: // otherwise returns false. ysr@976: bool steal(uint queue_num, int* seed, E& t); duke@435: duke@435: bool peek(); duke@435: }; duke@435: duke@435: template ysr@976: void GenericTaskQueueSet::register_queue(uint i, GenericTaskQueue* q) { ysr@976: assert(i < _n, "index out of range."); duke@435: _queues[i] = q; duke@435: } duke@435: duke@435: template ysr@976: GenericTaskQueue* GenericTaskQueueSet::queue(uint i) { duke@435: return _queues[i]; duke@435: } duke@435: duke@435: template ysr@976: bool GenericTaskQueueSet::steal(uint queue_num, int* seed, E& t) { ysr@976: for (uint i = 0; i < 2 * _n; i++) duke@435: if (steal_best_of_2(queue_num, seed, t)) duke@435: return true; duke@435: return false; duke@435: } duke@435: duke@435: template ysr@976: bool GenericTaskQueueSet::steal_best_of_all(uint queue_num, int* seed, E& t) { duke@435: if (_n > 2) { duke@435: int best_k; ysr@976: uint best_sz = 0; ysr@976: for (uint k = 0; k < _n; k++) { duke@435: if (k == queue_num) continue; ysr@976: uint sz = _queues[k]->size(); duke@435: if (sz > best_sz) { duke@435: best_sz = sz; duke@435: best_k = k; duke@435: } duke@435: } duke@435: return best_sz > 0 && _queues[best_k]->pop_global(t); duke@435: } else if (_n == 2) { duke@435: // Just try the other one. duke@435: int k = (queue_num + 1) % 2; duke@435: return _queues[k]->pop_global(t); duke@435: } else { duke@435: assert(_n == 1, "can't be zero."); duke@435: return false; duke@435: } duke@435: } duke@435: duke@435: template ysr@976: bool GenericTaskQueueSet::steal_1_random(uint queue_num, int* seed, E& t) { duke@435: if (_n > 2) { ysr@976: uint k = queue_num; duke@435: while (k == queue_num) k = randomParkAndMiller(seed) % _n; duke@435: return _queues[2]->pop_global(t); duke@435: } else if (_n == 2) { duke@435: // Just try the other one. duke@435: int k = (queue_num + 1) % 2; duke@435: return _queues[k]->pop_global(t); duke@435: } else { duke@435: assert(_n == 1, "can't be zero."); duke@435: return false; duke@435: } duke@435: } duke@435: duke@435: template ysr@976: bool GenericTaskQueueSet::steal_best_of_2(uint queue_num, int* seed, E& t) { duke@435: if (_n > 2) { ysr@976: uint k1 = queue_num; duke@435: while (k1 == queue_num) k1 = randomParkAndMiller(seed) % _n; ysr@976: uint k2 = queue_num; duke@435: while (k2 == queue_num || k2 == k1) k2 = randomParkAndMiller(seed) % _n; duke@435: // Sample both and try the larger. ysr@976: uint sz1 = _queues[k1]->size(); ysr@976: uint sz2 = _queues[k2]->size(); duke@435: if (sz2 > sz1) return _queues[k2]->pop_global(t); duke@435: else return _queues[k1]->pop_global(t); duke@435: } else if (_n == 2) { duke@435: // Just try the other one. ysr@976: uint k = (queue_num + 1) % 2; duke@435: return _queues[k]->pop_global(t); duke@435: } else { duke@435: assert(_n == 1, "can't be zero."); duke@435: return false; duke@435: } duke@435: } duke@435: duke@435: template duke@435: bool GenericTaskQueueSet::peek() { duke@435: // Try all the queues. ysr@976: for (uint j = 0; j < _n; j++) { duke@435: if (_queues[j]->peek()) duke@435: return true; duke@435: } duke@435: return false; duke@435: } duke@435: ysr@777: // When to terminate from the termination protocol. ysr@777: class TerminatorTerminator: public CHeapObj { ysr@777: public: ysr@777: virtual bool should_exit_termination() = 0; ysr@777: }; ysr@777: duke@435: // A class to aid in the termination of a set of parallel tasks using duke@435: // TaskQueueSet's for work stealing. duke@435: jmasa@981: #undef TRACESPINNING jmasa@981: duke@435: class ParallelTaskTerminator: public StackObj { duke@435: private: duke@435: int _n_threads; duke@435: TaskQueueSetSuper* _queue_set; ysr@976: int _offered_termination; duke@435: jmasa@981: #ifdef TRACESPINNING jmasa@981: static uint _total_yields; jmasa@981: static uint _total_spins; jmasa@981: static uint _total_peeks; jmasa@981: #endif jmasa@981: duke@435: bool peek_in_queue_set(); duke@435: protected: duke@435: virtual void yield(); duke@435: void sleep(uint millis); duke@435: duke@435: public: duke@435: duke@435: // "n_threads" is the number of threads to be terminated. "queue_set" is a duke@435: // queue sets of work queues of other threads. duke@435: ParallelTaskTerminator(int n_threads, TaskQueueSetSuper* queue_set); duke@435: duke@435: // The current thread has no work, and is ready to terminate if everyone duke@435: // else is. If returns "true", all threads are terminated. If returns duke@435: // "false", available work has been observed in one of the task queues, duke@435: // so the global task is not complete. ysr@777: bool offer_termination() { ysr@777: return offer_termination(NULL); ysr@777: } ysr@777: jcoomes@1342: // As above, but it also terminates if the should_exit_termination() ysr@777: // method of the terminator parameter returns true. If terminator is ysr@777: // NULL, then it is ignored. ysr@777: bool offer_termination(TerminatorTerminator* terminator); duke@435: duke@435: // Reset the terminator, so that it may be reused again. duke@435: // The caller is responsible for ensuring that this is done duke@435: // in an MT-safe manner, once the previous round of use of duke@435: // the terminator is finished. duke@435: void reset_for_reuse(); duke@435: jmasa@981: #ifdef TRACESPINNING jmasa@981: static uint total_yields() { return _total_yields; } jmasa@981: static uint total_spins() { return _total_spins; } jmasa@981: static uint total_peeks() { return _total_peeks; } jmasa@981: static void print_termination_counts(); jmasa@981: #endif duke@435: }; duke@435: duke@435: template inline bool GenericTaskQueue::push(E t) { ysr@976: uint localBot = _bottom; jcoomes@1342: assert((localBot >= 0) && (localBot < N), "_bottom out of range."); jcoomes@1342: idx_t top = _age.top(); ysr@976: uint dirty_n_elems = dirty_size(localBot, top); jcoomes@1342: assert((dirty_n_elems >= 0) && (dirty_n_elems < N), "n_elems out of range."); duke@435: if (dirty_n_elems < max_elems()) { duke@435: _elems[localBot] = t; bobv@1459: OrderAccess::release_store(&_bottom, increment_index(localBot)); duke@435: return true; duke@435: } else { duke@435: return push_slow(t, dirty_n_elems); duke@435: } duke@435: } duke@435: duke@435: template inline bool GenericTaskQueue::pop_local(E& t) { ysr@976: uint localBot = _bottom; jcoomes@1342: // This value cannot be N-1. That can only occur as a result of duke@435: // the assignment to bottom in this method. If it does, this method duke@435: // resets the size( to 0 before the next call (which is sequential, duke@435: // since this is pop_local.) jcoomes@1342: uint dirty_n_elems = dirty_size(localBot, _age.top()); jcoomes@1342: assert(dirty_n_elems != N - 1, "Shouldn't be possible..."); duke@435: if (dirty_n_elems == 0) return false; duke@435: localBot = decrement_index(localBot); duke@435: _bottom = localBot; duke@435: // This is necessary to prevent any read below from being reordered duke@435: // before the store just above. duke@435: OrderAccess::fence(); duke@435: t = _elems[localBot]; duke@435: // This is a second read of "age"; the "size()" above is the first. duke@435: // If there's still at least one element in the queue, based on the duke@435: // "_bottom" and "age" we've read, then there can be no interference with duke@435: // a "pop_global" operation, and we're done. jcoomes@1342: idx_t tp = _age.top(); // XXX duke@435: if (size(localBot, tp) > 0) { jcoomes@1342: assert(dirty_size(localBot, tp) != N - 1, "sanity"); duke@435: return true; duke@435: } else { duke@435: // Otherwise, the queue contained exactly one element; we take the slow duke@435: // path. jcoomes@1342: return pop_local_slow(localBot, _age.get()); duke@435: } duke@435: } duke@435: duke@435: typedef oop Task; duke@435: typedef GenericTaskQueue OopTaskQueue; duke@435: typedef GenericTaskQueueSet OopTaskQueueSet; duke@435: coleenp@548: coleenp@548: #define COMPRESSED_OOP_MASK 1 coleenp@548: coleenp@548: // This is a container class for either an oop* or a narrowOop*. coleenp@548: // Both are pushed onto a task queue and the consumer will test is_narrow() coleenp@548: // to determine which should be processed. coleenp@548: class StarTask { coleenp@548: void* _holder; // either union oop* or narrowOop* coleenp@548: public: ysr@1280: StarTask(narrowOop* p) { ysr@1280: assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!"); ysr@1280: _holder = (void *)((uintptr_t)p | COMPRESSED_OOP_MASK); ysr@1280: } ysr@1280: StarTask(oop* p) { ysr@1280: assert(((uintptr_t)p & COMPRESSED_OOP_MASK) == 0, "Information loss!"); ysr@1280: _holder = (void*)p; ysr@1280: } coleenp@548: StarTask() { _holder = NULL; } coleenp@548: operator oop*() { return (oop*)_holder; } coleenp@548: operator narrowOop*() { coleenp@548: return (narrowOop*)((uintptr_t)_holder & ~COMPRESSED_OOP_MASK); coleenp@548: } coleenp@548: coleenp@548: // Operators to preserve const/volatile in assignments required by gcc coleenp@548: void operator=(const volatile StarTask& t) volatile { _holder = t._holder; } coleenp@548: coleenp@548: bool is_narrow() const { coleenp@548: return (((uintptr_t)_holder & COMPRESSED_OOP_MASK) != 0); coleenp@548: } coleenp@548: }; coleenp@548: duke@435: typedef GenericTaskQueue OopStarTaskQueue; duke@435: typedef GenericTaskQueueSet OopStarTaskQueueSet; duke@435: jcoomes@810: typedef size_t RegionTask; // index for region jcoomes@810: typedef GenericTaskQueue RegionTaskQueue; jcoomes@810: typedef GenericTaskQueueSet RegionTaskQueueSet; duke@435: jcoomes@810: class RegionTaskQueueWithOverflow: public CHeapObj { duke@435: protected: jcoomes@810: RegionTaskQueue _region_queue; jcoomes@810: GrowableArray* _overflow_stack; duke@435: duke@435: public: jcoomes@810: RegionTaskQueueWithOverflow() : _overflow_stack(NULL) {} duke@435: // Initialize both stealable queue and overflow duke@435: void initialize(); duke@435: // Save first to stealable queue and then to overflow jcoomes@810: void save(RegionTask t); duke@435: // Retrieve first from overflow and then from stealable queue jcoomes@810: bool retrieve(RegionTask& region_index); duke@435: // Retrieve from stealable queue jcoomes@810: bool retrieve_from_stealable_queue(RegionTask& region_index); duke@435: // Retrieve from overflow jcoomes@810: bool retrieve_from_overflow(RegionTask& region_index); duke@435: bool is_empty(); duke@435: bool stealable_is_empty(); duke@435: bool overflow_is_empty(); ysr@976: uint stealable_size() { return _region_queue.size(); } jcoomes@810: RegionTaskQueue* task_queue() { return &_region_queue; } duke@435: }; duke@435: jcoomes@810: #define USE_RegionTaskQueueWithOverflow