| 197 | } |
| 198 | }; |
| 199 | class Queue { |
| 200 | typedef bi::rbtree<SubQueue> SubQueues; |
| 201 | typedef typename SubQueues::iterator Sit; |
| 202 | SubQueues queues; |
| 203 | unsigned total_prio; |
| 204 | unsigned max_cost; |
| 205 | public: |
| 206 | Queue() : |
| 207 | total_prio(0), |
| 208 | max_cost(0) { |
| 209 | } |
| 210 | ~Queue() { |
| 211 | queues.clear_and_dispose(DelItem<SubQueue>()); |
| 212 | } |
| 213 | bool empty() const { |
| 214 | return queues.empty(); |
| 215 | } |
| 216 | void insert(unsigned p, K cl, unsigned cost, T&& item, bool front = false) { |
| 217 | typename SubQueues::insert_commit_data insert_data; |
| 218 | std::pair<typename SubQueues::iterator, bool> ret = |
| 219 | queues.insert_unique_check(p, MapKey<SubQueue, unsigned>(), insert_data); |
| 220 | if (ret.second) { |
| 221 | ret.first = queues.insert_unique_commit(*new SubQueue(p), insert_data); |
| 222 | total_prio += p; |
| 223 | } |
| 224 | ret.first->insert(cl, cost, std::move(item), front); |
| 225 | if (cost > max_cost) { |
| 226 | max_cost = cost; |
| 227 | } |
| 228 | } |
| 229 | T pop(bool strict = false) { |
| 230 | Sit i = --queues.end(); |
| 231 | if (strict) { |
| 232 | T ret = i->pop(); |
| 233 | if (i->empty()) { |
| 234 | queues.erase_and_dispose(i, DelItem<SubQueue>()); |
| 235 | } |
| 236 | return ret; |
| 237 | } |
| 238 | if (queues.size() > 1) { |
| 239 | while (true) { |
| 240 | // Pick a new priority out of the total priority. |
| 241 | unsigned prio = rand() % total_prio + 1; |
| 242 | unsigned tp = total_prio - i->key; |
| 243 | // Find the priority corresponding to the picked number. |
| 244 | // Subtract high priorities to low priorities until the picked number |
| 245 | // is more than the total and try to dequeue that priority. |
| 246 | // Reverse the direction from previous implementation because there is a higher |
| 247 | // chance of dequeuing a high priority op so spend less time spinning. |
| 248 | while (prio <= tp) { |
| 249 | --i; |
| 250 | tp -= i->key; |
| 251 | } |
| 252 | // Flip a coin to see if this priority gets to run based on cost. |
| 253 | // The next op's cost is multiplied by .9 and subtracted from the |
| 254 | // max cost seen. Ops with lower costs will have a larger value |
| 255 | // and allow them to be selected easier than ops with high costs. |
| 256 | if (max_cost == 0 || rand() % max_cost <= |