Roy Want / Mbed OS beaconCompileReadyFork

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

source/EventQueue/PriorityQueue.h@0:ed0152b5c495, 2016-09-19 (annotated)

Committer:
roywant
Date:
Mon Sep 19 00:59:11 2016 +0000
Revision:
0:ed0152b5c495
Initial commit

Who changed what in which revision?

UserRevisionLine numberNew contents of line
roywant 0:ed0152b5c495 1 /*
roywant 0:ed0152b5c495 2 * Copyright (c) 2016, ARM Limited, All Rights Reserved
roywant 0:ed0152b5c495 3 * SPDX-License-Identifier: Apache-2.0
roywant 0:ed0152b5c495 4 *
roywant 0:ed0152b5c495 5 * Licensed under the Apache License, Version 2.0 (the "License"); you may
roywant 0:ed0152b5c495 6 * not use this file except in compliance with the License.
roywant 0:ed0152b5c495 7 * You may obtain a copy of the License at
roywant 0:ed0152b5c495 8 *
roywant 0:ed0152b5c495 9 * http://www.apache.org/licenses/LICENSE-2.0
roywant 0:ed0152b5c495 10 *
roywant 0:ed0152b5c495 11 * Unless required by applicable law or agreed to in writing, software
roywant 0:ed0152b5c495 12 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
roywant 0:ed0152b5c495 13 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
roywant 0:ed0152b5c495 14 * See the License for the specific language governing permissions and
roywant 0:ed0152b5c495 15 * limitations under the License.
roywant 0:ed0152b5c495 16 */
roywant 0:ed0152b5c495 17 #ifndef EVENTQUEUE_STACKPRIORITYQUEUE_H_
roywant 0:ed0152b5c495 18 #define EVENTQUEUE_STACKPRIORITYQUEUE_H_
roywant 0:ed0152b5c495 19
roywant 0:ed0152b5c495 20 #include <cstddef>
roywant 0:ed0152b5c495 21 #include "AlignedStorage.h"
roywant 0:ed0152b5c495 22
roywant 0:ed0152b5c495 23 namespace eq {
roywant 0:ed0152b5c495 24
roywant 0:ed0152b5c495 25 /**
roywant 0:ed0152b5c495 26 * Priority queue of Ts.
roywant 0:ed0152b5c495 27 * Ts are ordered from the smaller to the bigger ( < ).
roywant 0:ed0152b5c495 28 * Elements in the queue are mutable (this is a design choice).
roywant 0:ed0152b5c495 29 * After a mutation the function update should be called to ensure that the
roywant 0:ed0152b5c495 30 * queue is still properly sorted.
roywant 0:ed0152b5c495 31 * @tparam T type of elements in this queue
roywant 0:ed0152b5c495 32 * @param capacity Number of elements that this queue can contain
roywant 0:ed0152b5c495 33 */
roywant 0:ed0152b5c495 34 template<typename T, std::size_t Capacity>
roywant 0:ed0152b5c495 35 class PriorityQueue {
roywant 0:ed0152b5c495 36
roywant 0:ed0152b5c495 37 public:
roywant 0:ed0152b5c495 38 /**
roywant 0:ed0152b5c495 39 * Type of the nodes in this queue.
roywant 0:ed0152b5c495 40 */
roywant 0:ed0152b5c495 41 struct Node {
roywant 0:ed0152b5c495 42 AlignedStorage<T> storage; /// storage for the T
roywant 0:ed0152b5c495 43 Node* next; /// pointer to the next node
roywant 0:ed0152b5c495 44 };
roywant 0:ed0152b5c495 45
roywant 0:ed0152b5c495 46 /**
roywant 0:ed0152b5c495 47 * Iterator for elements of the queue.
roywant 0:ed0152b5c495 48 */
roywant 0:ed0152b5c495 49 class Iterator {
roywant 0:ed0152b5c495 50 friend PriorityQueue;
roywant 0:ed0152b5c495 51
roywant 0:ed0152b5c495 52 /// Construct an iterator from a Node.
roywant 0:ed0152b5c495 53 /// This constructor is private and can only be invoked from the PriorityQueue.
roywant 0:ed0152b5c495 54 Iterator(Node* current) :
roywant 0:ed0152b5c495 55 _current(current) {
roywant 0:ed0152b5c495 56 }
roywant 0:ed0152b5c495 57
roywant 0:ed0152b5c495 58 public:
roywant 0:ed0152b5c495 59
roywant 0:ed0152b5c495 60 /// Indirection operator.
roywant 0:ed0152b5c495 61 /// return a reference to the inner T
roywant 0:ed0152b5c495 62 T& operator*() {
roywant 0:ed0152b5c495 63 return _current->storage.get();
roywant 0:ed0152b5c495 64 }
roywant 0:ed0152b5c495 65
roywant 0:ed0152b5c495 66 /// Const version of indirection operator.
roywant 0:ed0152b5c495 67 /// return a reference to the inner T
roywant 0:ed0152b5c495 68 const T& operator*() const {
roywant 0:ed0152b5c495 69 return _current->storage.get();
roywant 0:ed0152b5c495 70 }
roywant 0:ed0152b5c495 71
roywant 0:ed0152b5c495 72 /// dereference operator.
roywant 0:ed0152b5c495 73 /// Will invoke the operation on the inner T
roywant 0:ed0152b5c495 74 T* operator->() {
roywant 0:ed0152b5c495 75 return &(_current->storage.get());
roywant 0:ed0152b5c495 76 }
roywant 0:ed0152b5c495 77
roywant 0:ed0152b5c495 78 /// const dereference operator.
roywant 0:ed0152b5c495 79 /// Will invoke the operation on the inner T
roywant 0:ed0152b5c495 80 const T* operator->() const {
roywant 0:ed0152b5c495 81 return &(_current->storage.get());
roywant 0:ed0152b5c495 82 }
roywant 0:ed0152b5c495 83
roywant 0:ed0152b5c495 84 /// pre incrementation to the next T in the list
roywant 0:ed0152b5c495 85 Iterator& operator++() {
roywant 0:ed0152b5c495 86 _current = _current->next;
roywant 0:ed0152b5c495 87 return *this;
roywant 0:ed0152b5c495 88 }
roywant 0:ed0152b5c495 89
roywant 0:ed0152b5c495 90 /// post incrementation to the next T in the list
roywant 0:ed0152b5c495 91 Iterator operator++(int) {
roywant 0:ed0152b5c495 92 Iterator tmp(*this);
roywant 0:ed0152b5c495 93 _current = _current->next;
roywant 0:ed0152b5c495 94 return tmp;
roywant 0:ed0152b5c495 95 }
roywant 0:ed0152b5c495 96
roywant 0:ed0152b5c495 97 /// Equality operator
roywant 0:ed0152b5c495 98 friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
roywant 0:ed0152b5c495 99 return lhs._current == rhs._current;
roywant 0:ed0152b5c495 100 }
roywant 0:ed0152b5c495 101
roywant 0:ed0152b5c495 102 /// Unequality operator
roywant 0:ed0152b5c495 103 friend bool operator!=(const Iterator& lhs, const Iterator& rhs) {
roywant 0:ed0152b5c495 104 return !(lhs == rhs);
roywant 0:ed0152b5c495 105 }
roywant 0:ed0152b5c495 106
roywant 0:ed0152b5c495 107 /// return the internal node.
roywant 0:ed0152b5c495 108 Node* get_node() {
roywant 0:ed0152b5c495 109 return _current;
roywant 0:ed0152b5c495 110 }
roywant 0:ed0152b5c495 111
roywant 0:ed0152b5c495 112 private:
roywant 0:ed0152b5c495 113 Node* _current;
roywant 0:ed0152b5c495 114 };
roywant 0:ed0152b5c495 115
roywant 0:ed0152b5c495 116 typedef Iterator iterator;
roywant 0:ed0152b5c495 117
roywant 0:ed0152b5c495 118 /// Construct an empty priority queue.
roywant 0:ed0152b5c495 119 PriorityQueue() : nodes(), free_nodes(NULL), head(NULL), used_nodes_count(0) {
roywant 0:ed0152b5c495 120 initialize();
roywant 0:ed0152b5c495 121 }
roywant 0:ed0152b5c495 122
roywant 0:ed0152b5c495 123 /// Copy construct a priority queue.
roywant 0:ed0152b5c495 124 /// The queue will have the same content has other.
roywant 0:ed0152b5c495 125 PriorityQueue(const PriorityQueue& other) :
roywant 0:ed0152b5c495 126 nodes(), free_nodes(NULL), head(NULL), used_nodes_count(0) {
roywant 0:ed0152b5c495 127 initialize();
roywant 0:ed0152b5c495 128 copy(other);
roywant 0:ed0152b5c495 129 }
roywant 0:ed0152b5c495 130
roywant 0:ed0152b5c495 131 /// destroy a priority queue.
roywant 0:ed0152b5c495 132 ~PriorityQueue() {
roywant 0:ed0152b5c495 133 clear();
roywant 0:ed0152b5c495 134 }
roywant 0:ed0152b5c495 135
roywant 0:ed0152b5c495 136 /// Copy assignemnent from another priority queue.
roywant 0:ed0152b5c495 137 /// The content of the queue will be destroyed then the content from
roywant 0:ed0152b5c495 138 /// other will be copied.
roywant 0:ed0152b5c495 139 PriorityQueue& operator=(const PriorityQueue& other) {
roywant 0:ed0152b5c495 140 if (&other == this) {
roywant 0:ed0152b5c495 141 return *this;
roywant 0:ed0152b5c495 142 }
roywant 0:ed0152b5c495 143 copy(other);
roywant 0:ed0152b5c495 144 return *this;
roywant 0:ed0152b5c495 145 }
roywant 0:ed0152b5c495 146
roywant 0:ed0152b5c495 147 /// Push a new element to the queue.
roywant 0:ed0152b5c495 148 /// It will be added before the first element p in the queue where
roywant 0:ed0152b5c495 149 /// element < p == true.
roywant 0:ed0152b5c495 150 /// @return An iterator to the inserted element.
roywant 0:ed0152b5c495 151 iterator push(const T& element) {
roywant 0:ed0152b5c495 152 if (full()) {
roywant 0:ed0152b5c495 153 return NULL;
roywant 0:ed0152b5c495 154 }
roywant 0:ed0152b5c495 155
roywant 0:ed0152b5c495 156 // get a free node
roywant 0:ed0152b5c495 157 Node* new_node = free_nodes;
roywant 0:ed0152b5c495 158 free_nodes = free_nodes->next;
roywant 0:ed0152b5c495 159 new_node->next = NULL;
roywant 0:ed0152b5c495 160
roywant 0:ed0152b5c495 161 ++used_nodes_count;
roywant 0:ed0152b5c495 162
roywant 0:ed0152b5c495 163 // copy content
roywant 0:ed0152b5c495 164 new (new_node->storage.get_storage()) T(element);
roywant 0:ed0152b5c495 165
roywant 0:ed0152b5c495 166 // if there is no node in the queue, just link the head
roywant 0:ed0152b5c495 167 // to the new node and return
roywant 0:ed0152b5c495 168 if (head == NULL) {
roywant 0:ed0152b5c495 169 head = new_node;
roywant 0:ed0152b5c495 170 return new_node;
roywant 0:ed0152b5c495 171 }
roywant 0:ed0152b5c495 172
roywant 0:ed0152b5c495 173 // if the new node has an higher priority than the node in head
roywant 0:ed0152b5c495 174 // just link it as the head
roywant 0:ed0152b5c495 175 if (element < head->storage.get()) {
roywant 0:ed0152b5c495 176 new_node->next = head;
roywant 0:ed0152b5c495 177 head = new_node;
roywant 0:ed0152b5c495 178 return new_node;
roywant 0:ed0152b5c495 179 }
roywant 0:ed0152b5c495 180
roywant 0:ed0152b5c495 181 // insert the node after head
roywant 0:ed0152b5c495 182 insert_after(head, new_node);
roywant 0:ed0152b5c495 183
roywant 0:ed0152b5c495 184 return new_node;
roywant 0:ed0152b5c495 185 }
roywant 0:ed0152b5c495 186
roywant 0:ed0152b5c495 187 /// pop the head of the queue.
roywant 0:ed0152b5c495 188 bool pop() {
roywant 0:ed0152b5c495 189 if (!head) {
roywant 0:ed0152b5c495 190 return false;
roywant 0:ed0152b5c495 191 }
roywant 0:ed0152b5c495 192
roywant 0:ed0152b5c495 193 Node* target = head;
roywant 0:ed0152b5c495 194 target->storage.get().~T();
roywant 0:ed0152b5c495 195 head = target->next;
roywant 0:ed0152b5c495 196 target->next = free_nodes;
roywant 0:ed0152b5c495 197 free_nodes = target;
roywant 0:ed0152b5c495 198 --used_nodes_count;
roywant 0:ed0152b5c495 199 return true;
roywant 0:ed0152b5c495 200 }
roywant 0:ed0152b5c495 201
roywant 0:ed0152b5c495 202 /// If the content of an element is updated is updated after the insertion
roywant 0:ed0152b5c495 203 /// then, the list can be in an unordered state.
roywant 0:ed0152b5c495 204 /// This function help; it update the position of an iterator in the list.
roywant 0:ed0152b5c495 205 void update(iterator it) {
roywant 0:ed0152b5c495 206 Node* target = it.get_node();
roywant 0:ed0152b5c495 207 Node* hint = head;
roywant 0:ed0152b5c495 208
roywant 0:ed0152b5c495 209 if (target == NULL) {
roywant 0:ed0152b5c495 210 return;
roywant 0:ed0152b5c495 211 }
roywant 0:ed0152b5c495 212
roywant 0:ed0152b5c495 213 // remove the node from the list
roywant 0:ed0152b5c495 214 if (target == head) {
roywant 0:ed0152b5c495 215 // if it is the only node in the list, just return
roywant 0:ed0152b5c495 216 // it is not needed to update its position
roywant 0:ed0152b5c495 217 if (target->next == NULL) {
roywant 0:ed0152b5c495 218 return;
roywant 0:ed0152b5c495 219 }
roywant 0:ed0152b5c495 220
roywant 0:ed0152b5c495 221 // if the order is already correct, just return
roywant 0:ed0152b5c495 222 if (target->storage.get() < target->next->storage.get()) {
roywant 0:ed0152b5c495 223 return;
roywant 0:ed0152b5c495 224 }
roywant 0:ed0152b5c495 225
roywant 0:ed0152b5c495 226 // otherwise remove the node from the list
roywant 0:ed0152b5c495 227 // and update the hint
roywant 0:ed0152b5c495 228 head = target->next;
roywant 0:ed0152b5c495 229 hint = head;
roywant 0:ed0152b5c495 230 } else {
roywant 0:ed0152b5c495 231 bool node_found = false;
roywant 0:ed0152b5c495 232 for (Node* current = head; current != NULL; current = current->next) {
roywant 0:ed0152b5c495 233 if (current->next == target) {
roywant 0:ed0152b5c495 234 // check if it is needed to move the node
roywant 0:ed0152b5c495 235 if (current->storage.get() < target->storage.get()) {
roywant 0:ed0152b5c495 236 if (target->next == NULL) {
roywant 0:ed0152b5c495 237 return;
roywant 0:ed0152b5c495 238 }
roywant 0:ed0152b5c495 239
roywant 0:ed0152b5c495 240 if (target->storage.get() < target->next->storage.get()) {
roywant 0:ed0152b5c495 241 return;
roywant 0:ed0152b5c495 242 }
roywant 0:ed0152b5c495 243
roywant 0:ed0152b5c495 244 // there is no need to iterate again the whole list
roywant 0:ed0152b5c495 245 // just mark the hint has the current node
roywant 0:ed0152b5c495 246 hint = current;
roywant 0:ed0152b5c495 247 }
roywant 0:ed0152b5c495 248
roywant 0:ed0152b5c495 249 // remove the node from the list and break out of the loop
roywant 0:ed0152b5c495 250 current->next = target->next;
roywant 0:ed0152b5c495 251 node_found = true;
roywant 0:ed0152b5c495 252 break;
roywant 0:ed0152b5c495 253 }
roywant 0:ed0152b5c495 254 }
roywant 0:ed0152b5c495 255
roywant 0:ed0152b5c495 256 // the node in parameter doesn't belong to this queue
roywant 0:ed0152b5c495 257 if (!node_found) {
roywant 0:ed0152b5c495 258 return;
roywant 0:ed0152b5c495 259 }
roywant 0:ed0152b5c495 260 }
roywant 0:ed0152b5c495 261
roywant 0:ed0152b5c495 262 // insert the node after hint
roywant 0:ed0152b5c495 263 insert_after(hint, target);
roywant 0:ed0152b5c495 264 }
roywant 0:ed0152b5c495 265
roywant 0:ed0152b5c495 266 /// return an iterator to the begining of the queue.
roywant 0:ed0152b5c495 267 iterator begin() {
roywant 0:ed0152b5c495 268 return head;
roywant 0:ed0152b5c495 269 }
roywant 0:ed0152b5c495 270
roywant 0:ed0152b5c495 271 /// return an iterator to the end of the queue.
roywant 0:ed0152b5c495 272 /// @note can't be dereferenced
roywant 0:ed0152b5c495 273 iterator end() {
roywant 0:ed0152b5c495 274 return NULL;
roywant 0:ed0152b5c495 275 }
roywant 0:ed0152b5c495 276
roywant 0:ed0152b5c495 277 /// erase an iterator from the list
roywant 0:ed0152b5c495 278 bool erase(iterator it) {
roywant 0:ed0152b5c495 279 return erase(it.get_node());
roywant 0:ed0152b5c495 280 }
roywant 0:ed0152b5c495 281
roywant 0:ed0152b5c495 282 /// erase a node from the list
roywant 0:ed0152b5c495 283 bool erase(Node* n) {
roywant 0:ed0152b5c495 284 if (n == NULL) {
roywant 0:ed0152b5c495 285 return false;
roywant 0:ed0152b5c495 286 }
roywant 0:ed0152b5c495 287
roywant 0:ed0152b5c495 288 if (head == n) {
roywant 0:ed0152b5c495 289 return pop();
roywant 0:ed0152b5c495 290 }
roywant 0:ed0152b5c495 291
roywant 0:ed0152b5c495 292 Node* current = head;
roywant 0:ed0152b5c495 293 while (current->next) {
roywant 0:ed0152b5c495 294 if (current->next == n) {
roywant 0:ed0152b5c495 295 current->next = n->next;
roywant 0:ed0152b5c495 296 n->storage.get().~T();
roywant 0:ed0152b5c495 297 n->next = free_nodes;
roywant 0:ed0152b5c495 298 free_nodes = n;
roywant 0:ed0152b5c495 299 --used_nodes_count;
roywant 0:ed0152b5c495 300 return true;
roywant 0:ed0152b5c495 301 }
roywant 0:ed0152b5c495 302 current = current->next;
roywant 0:ed0152b5c495 303 }
roywant 0:ed0152b5c495 304 return false;
roywant 0:ed0152b5c495 305 }
roywant 0:ed0152b5c495 306
roywant 0:ed0152b5c495 307 /**
roywant 0:ed0152b5c495 308 * Indicate if the queue is empty or not.
roywant 0:ed0152b5c495 309 * @return true if the queue is empty and false otherwise.
roywant 0:ed0152b5c495 310 * @invariant the queue remains untouched.
roywant 0:ed0152b5c495 311 */
roywant 0:ed0152b5c495 312 bool empty() const {
roywant 0:ed0152b5c495 313 return head == NULL;
roywant 0:ed0152b5c495 314 }
roywant 0:ed0152b5c495 315
roywant 0:ed0152b5c495 316 /**
roywant 0:ed0152b5c495 317 * Indicate if the true is full or not.
roywant 0:ed0152b5c495 318 * @return true if the queue is full and false otherwise.
roywant 0:ed0152b5c495 319 * @invariant the queue remains untouched.
roywant 0:ed0152b5c495 320 */
roywant 0:ed0152b5c495 321 bool full() const {
roywant 0:ed0152b5c495 322 return free_nodes == NULL;
roywant 0:ed0152b5c495 323 }
roywant 0:ed0152b5c495 324
roywant 0:ed0152b5c495 325 /**
roywant 0:ed0152b5c495 326 * Indicate the number of elements in the queue.
roywant 0:ed0152b5c495 327 * @return the number of elements currently held by the queue.
roywant 0:ed0152b5c495 328 * @invariant the queue remains untouched.
roywant 0:ed0152b5c495 329 */
roywant 0:ed0152b5c495 330 std::size_t size() const {
roywant 0:ed0152b5c495 331 return used_nodes_count;
roywant 0:ed0152b5c495 332 }
roywant 0:ed0152b5c495 333
roywant 0:ed0152b5c495 334 /**
roywant 0:ed0152b5c495 335 * Expose the capacity of the queue in terms of number of elements the
roywant 0:ed0152b5c495 336 * queue can hold.
roywant 0:ed0152b5c495 337 * @return the capacity of the queue.
roywant 0:ed0152b5c495 338 * @invariant this function should always return Capacity.
roywant 0:ed0152b5c495 339 */
roywant 0:ed0152b5c495 340 std::size_t capacity() const {
roywant 0:ed0152b5c495 341 return Capacity;
roywant 0:ed0152b5c495 342 }
roywant 0:ed0152b5c495 343
roywant 0:ed0152b5c495 344 /**
roywant 0:ed0152b5c495 345 * Clear the queue from all its elements.
roywant 0:ed0152b5c495 346 */
roywant 0:ed0152b5c495 347 void clear() {
roywant 0:ed0152b5c495 348 while (head) {
roywant 0:ed0152b5c495 349 head->storage.get().~T();
roywant 0:ed0152b5c495 350 Node* tmp = head;
roywant 0:ed0152b5c495 351 head = head->next;
roywant 0:ed0152b5c495 352 tmp->next = free_nodes;
roywant 0:ed0152b5c495 353 free_nodes = tmp;
roywant 0:ed0152b5c495 354 }
roywant 0:ed0152b5c495 355 used_nodes_count = 0;
roywant 0:ed0152b5c495 356 }
roywant 0:ed0152b5c495 357
roywant 0:ed0152b5c495 358 private:
roywant 0:ed0152b5c495 359 void initialize() {
roywant 0:ed0152b5c495 360 /// link all the nodes together
roywant 0:ed0152b5c495 361 for (std::size_t i = 0; i < (Capacity - 1); ++i) {
roywant 0:ed0152b5c495 362 nodes[i].next = &nodes[i + 1];
roywant 0:ed0152b5c495 363 }
roywant 0:ed0152b5c495 364 /// the last node does not have a next node
roywant 0:ed0152b5c495 365 nodes[Capacity - 1].next = NULL;
roywant 0:ed0152b5c495 366 /// set all the nodes as free
roywant 0:ed0152b5c495 367 free_nodes = nodes;
roywant 0:ed0152b5c495 368 }
roywant 0:ed0152b5c495 369
roywant 0:ed0152b5c495 370 void copy(const PriorityQueue& other) {
roywant 0:ed0152b5c495 371 if (empty() == false) {
roywant 0:ed0152b5c495 372 clear();
roywant 0:ed0152b5c495 373 }
roywant 0:ed0152b5c495 374
roywant 0:ed0152b5c495 375 Node *to_copy = other.head;
roywant 0:ed0152b5c495 376 Node *previous = NULL;
roywant 0:ed0152b5c495 377 while (to_copy) {
roywant 0:ed0152b5c495 378 // pick a free node
roywant 0:ed0152b5c495 379 Node* new_node = free_nodes;
roywant 0:ed0152b5c495 380 free_nodes = free_nodes->next;
roywant 0:ed0152b5c495 381 new_node->next = NULL;
roywant 0:ed0152b5c495 382
roywant 0:ed0152b5c495 383 // copy content
roywant 0:ed0152b5c495 384 new (new_node->storage.get_storage()) T(to_copy->storage.get());
roywant 0:ed0152b5c495 385
roywant 0:ed0152b5c495 386 // link into the queue or update head then update previous pointer
roywant 0:ed0152b5c495 387 if (previous) {
roywant 0:ed0152b5c495 388 previous->next = new_node;
roywant 0:ed0152b5c495 389 } else {
roywant 0:ed0152b5c495 390 head = new_node;
roywant 0:ed0152b5c495 391 }
roywant 0:ed0152b5c495 392 previous = new_node;
roywant 0:ed0152b5c495 393
roywant 0:ed0152b5c495 394 // update the node to copy
roywant 0:ed0152b5c495 395 to_copy = to_copy->next;
roywant 0:ed0152b5c495 396 }
roywant 0:ed0152b5c495 397 used_nodes_count = other.used_nodes_count;
roywant 0:ed0152b5c495 398 }
roywant 0:ed0152b5c495 399
roywant 0:ed0152b5c495 400 void insert_after(Node* prev, Node* to_insert) {
roywant 0:ed0152b5c495 401 for (; prev != NULL; prev = prev->next) {
roywant 0:ed0152b5c495 402 if (prev->next == NULL || to_insert->storage.get() < prev->next->storage.get()) {
roywant 0:ed0152b5c495 403 to_insert->next = prev->next;
roywant 0:ed0152b5c495 404 prev->next = to_insert;
roywant 0:ed0152b5c495 405 break;
roywant 0:ed0152b5c495 406 }
roywant 0:ed0152b5c495 407 }
roywant 0:ed0152b5c495 408 }
roywant 0:ed0152b5c495 409
roywant 0:ed0152b5c495 410 Node nodes[Capacity]; //< Nodes of the queue
roywant 0:ed0152b5c495 411 Node *free_nodes; //< entry point for the list of free nodes
roywant 0:ed0152b5c495 412 Node *head; //< head of the queue
roywant 0:ed0152b5c495 413 std::size_t used_nodes_count; // number of nodes used
roywant 0:ed0152b5c495 414 };
roywant 0:ed0152b5c495 415
roywant 0:ed0152b5c495 416 } // namespace eq
roywant 0:ed0152b5c495 417
roywant 0:ed0152b5c495 418 #endif /* EVENTQUEUE_STACKPRIORITYQUEUE_H_ */