1.1 --- a/src/share/vm/utilities/taskqueue.hpp Wed Jun 30 11:52:10 2010 -0400
1.2 +++ b/src/share/vm/utilities/taskqueue.hpp Thu Jul 01 21:40:45 2010 -0700
1.3 @@ -1,5 +1,5 @@
1.4 /*
1.5 - * Copyright (c) 2001, 2009, Oracle and/or its affiliates. All rights reserved.
1.6 + * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved.
1.7 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.8 *
1.9 * This code is free software; you can redistribute it and/or modify it
1.10 @@ -109,8 +109,9 @@
1.11 public:
1.12 TaskQueueSuper() : _bottom(0), _age() {}
1.13
1.14 - // Return true if the TaskQueue contains any tasks.
1.15 - bool peek() { return _bottom != _age.top(); }
1.16 + // Return true if the TaskQueue contains/does not contain any tasks.
1.17 + bool peek() const { return _bottom != _age.top(); }
1.18 + bool is_empty() const { return size() == 0; }
1.19
1.20 // Return an estimate of the number of elements in the queue.
1.21 // The "careful" version admits the possibility of pop_local/pop_global
1.22 @@ -165,18 +166,16 @@
1.23
1.24 void initialize();
1.25
1.26 - // Push the task "t" on the queue. Returns "false" iff the queue is
1.27 - // full.
1.28 + // Push the task "t" on the queue. Returns "false" iff the queue is full.
1.29 inline bool push(E t);
1.30
1.31 - // If succeeds in claiming a task (from the 'local' end, that is, the
1.32 - // most recently pushed task), returns "true" and sets "t" to that task.
1.33 - // Otherwise, the queue is empty and returns false.
1.34 + // Attempts to claim a task from the "local" end of the queue (the most
1.35 + // recently pushed). If successful, returns true and sets t to the task;
1.36 + // otherwise, returns false (the queue is empty).
1.37 inline bool pop_local(E& t);
1.38
1.39 - // If succeeds in claiming a task (from the 'global' end, that is, the
1.40 - // least recently pushed task), returns "true" and sets "t" to that task.
1.41 - // Otherwise, the queue is empty and returns false.
1.42 + // Like pop_local(), but uses the "global" end of the queue (the least
1.43 + // recently pushed).
1.44 bool pop_global(E& t);
1.45
1.46 // Delete any resource associated with the queue.
1.47 @@ -198,7 +197,6 @@
1.48 template<class E, unsigned int N>
1.49 void GenericTaskQueue<E, N>::initialize() {
1.50 _elems = NEW_C_HEAP_ARRAY(E, N);
1.51 - guarantee(_elems != NULL, "Allocation failed.");
1.52 }
1.53
1.54 template<class E, unsigned int N>
1.55 @@ -289,7 +287,87 @@
1.56 FREE_C_HEAP_ARRAY(E, _elems);
1.57 }
1.58
1.59 -// Inherits the typedef of "Task" from above.
1.60 +// OverflowTaskQueue is a TaskQueue that also includes an overflow stack for
1.61 +// elements that do not fit in the TaskQueue.
1.62 +//
1.63 +// Three methods from super classes are overridden:
1.64 +//
1.65 +// initialize() - initialize the super classes and create the overflow stack
1.66 +// push() - push onto the task queue or, if that fails, onto the overflow stack
1.67 +// is_empty() - return true if both the TaskQueue and overflow stack are empty
1.68 +//
1.69 +// Note that size() is not overridden--it returns the number of elements in the
1.70 +// TaskQueue, and does not include the size of the overflow stack. This
1.71 +// simplifies replacement of GenericTaskQueues with OverflowTaskQueues.
1.72 +template<class E, unsigned int N = TASKQUEUE_SIZE>
1.73 +class OverflowTaskQueue: public GenericTaskQueue<E, N>
1.74 +{
1.75 +public:
1.76 + typedef GrowableArray<E> overflow_t;
1.77 + typedef GenericTaskQueue<E, N> taskqueue_t;
1.78 +
1.79 + OverflowTaskQueue();
1.80 + ~OverflowTaskQueue();
1.81 + void initialize();
1.82 +
1.83 + inline overflow_t* overflow_stack() const { return _overflow_stack; }
1.84 +
1.85 + // Push task t onto the queue or onto the overflow stack. Return true.
1.86 + inline bool push(E t);
1.87 +
1.88 + // Attempt to pop from the overflow stack; return true if anything was popped.
1.89 + inline bool pop_overflow(E& t);
1.90 +
1.91 + inline bool taskqueue_empty() const { return taskqueue_t::is_empty(); }
1.92 + inline bool overflow_empty() const { return overflow_stack()->is_empty(); }
1.93 + inline bool is_empty() const {
1.94 + return taskqueue_empty() && overflow_empty();
1.95 + }
1.96 +
1.97 +private:
1.98 + overflow_t* _overflow_stack;
1.99 +};
1.100 +
1.101 +template <class E, unsigned int N>
1.102 +OverflowTaskQueue<E, N>::OverflowTaskQueue()
1.103 +{
1.104 + _overflow_stack = NULL;
1.105 +}
1.106 +
1.107 +template <class E, unsigned int N>
1.108 +OverflowTaskQueue<E, N>::~OverflowTaskQueue()
1.109 +{
1.110 + if (_overflow_stack != NULL) {
1.111 + delete _overflow_stack;
1.112 + _overflow_stack = NULL;
1.113 + }
1.114 +}
1.115 +
1.116 +template <class E, unsigned int N>
1.117 +void OverflowTaskQueue<E, N>::initialize()
1.118 +{
1.119 + taskqueue_t::initialize();
1.120 + assert(_overflow_stack == NULL, "memory leak");
1.121 + _overflow_stack = new (ResourceObj::C_HEAP) GrowableArray<E>(10, true);
1.122 +}
1.123 +
1.124 +template <class E, unsigned int N>
1.125 +bool OverflowTaskQueue<E, N>::push(E t)
1.126 +{
1.127 + if (!taskqueue_t::push(t)) {
1.128 + overflow_stack()->push(t);
1.129 + }
1.130 + return true;
1.131 +}
1.132 +
1.133 +template <class E, unsigned int N>
1.134 +bool OverflowTaskQueue<E, N>::pop_overflow(E& t)
1.135 +{
1.136 + if (overflow_empty()) return false;
1.137 + t = overflow_stack()->pop();
1.138 + return true;
1.139 +}
1.140 +
1.141 class TaskQueueSetSuper: public CHeapObj {
1.142 protected:
1.143 static int randomParkAndMiller(int* seed0);
1.144 @@ -323,11 +401,11 @@
1.145
1.146 T* queue(uint n);
1.147
1.148 - // The thread with queue number "queue_num" (and whose random number seed
1.149 - // is at "seed") is trying to steal a task from some other queue. (It
1.150 - // may try several queues, according to some configuration parameter.)
1.151 - // If some steal succeeds, returns "true" and sets "t" the stolen task,
1.152 - // otherwise returns false.
1.153 + // The thread with queue number "queue_num" (and whose random number seed is
1.154 + // at "seed") is trying to steal a task from some other queue. (It may try
1.155 + // several queues, according to some configuration parameter.) If some steal
1.156 + // succeeds, returns "true" and sets "t" to the stolen task, otherwise returns
1.157 + // false.
1.158 bool steal(uint queue_num, int* seed, E& t);
1.159
1.160 bool peek();
1.161 @@ -507,7 +585,7 @@
1.162 uint localBot = _bottom;
1.163 // This value cannot be N-1. That can only occur as a result of
1.164 // the assignment to bottom in this method. If it does, this method
1.165 - // resets the size( to 0 before the next call (which is sequential,
1.166 + // resets the size to 0 before the next call (which is sequential,
1.167 // since this is pop_local.)
1.168 uint dirty_n_elems = dirty_size(localBot, _age.top());
1.169 assert(dirty_n_elems != N - 1, "Shouldn't be possible...");
1.170 @@ -533,8 +611,7 @@
1.171 }
1.172 }
1.173
1.174 -typedef oop Task;
1.175 -typedef GenericTaskQueue<Task> OopTaskQueue;
1.176 +typedef GenericTaskQueue<oop> OopTaskQueue;
1.177 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet;
1.178
1.179 #ifdef _MSC_VER
1.180 @@ -615,35 +692,8 @@
1.181 #pragma warning(pop)
1.182 #endif
1.183
1.184 -typedef GenericTaskQueue<StarTask> OopStarTaskQueue;
1.185 +typedef OverflowTaskQueue<StarTask> OopStarTaskQueue;
1.186 typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet;
1.187
1.188 -typedef size_t RegionTask; // index for region
1.189 -typedef GenericTaskQueue<RegionTask> RegionTaskQueue;
1.190 -typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet;
1.191 -
1.192 -class RegionTaskQueueWithOverflow: public CHeapObj {
1.193 - protected:
1.194 - RegionTaskQueue _region_queue;
1.195 - GrowableArray<RegionTask>* _overflow_stack;
1.196 -
1.197 - public:
1.198 - RegionTaskQueueWithOverflow() : _overflow_stack(NULL) {}
1.199 - // Initialize both stealable queue and overflow
1.200 - void initialize();
1.201 - // Save first to stealable queue and then to overflow
1.202 - void save(RegionTask t);
1.203 - // Retrieve first from overflow and then from stealable queue
1.204 - bool retrieve(RegionTask& region_index);
1.205 - // Retrieve from stealable queue
1.206 - bool retrieve_from_stealable_queue(RegionTask& region_index);
1.207 - // Retrieve from overflow
1.208 - bool retrieve_from_overflow(RegionTask& region_index);
1.209 - bool is_empty();
1.210 - bool stealable_is_empty();
1.211 - bool overflow_is_empty();
1.212 - uint stealable_size() { return _region_queue.size(); }
1.213 - RegionTaskQueue* task_queue() { return &_region_queue; }
1.214 -};
1.215 -
1.216 -#define USE_RegionTaskQueueWithOverflow
1.217 +typedef OverflowTaskQueue<size_t> RegionTaskQueue;
1.218 +typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet;
