PriorityQueue.h

00001 /*
00002  * Copyright (c) 2016, ARM Limited, All Rights Reserved
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License"); you may
00006  * not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  * http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00013  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 #ifndef EVENTQUEUE_STACKPRIORITYQUEUE_H_
00018 #define EVENTQUEUE_STACKPRIORITYQUEUE_H_
00019 
00020 #include <cstddef>
00021 #include "AlignedStorage.h"
00022 
00023 namespace eq {
00024 
00025 /**
00026  * Priority queue of Ts.
00027  * Ts are ordered from the smaller to the bigger ( < ).
00028  * Elements in the queue are mutable (this is a design choice).
00029  * After a mutation the function update should be called to ensure that the
00030  * queue is still properly sorted.
00031  * @tparam T type of elements in this queue
00032  * @param capacity Number of elements that this queue can contain
00033  */
00034 template<typename T, std::size_t Capacity>
00035 class PriorityQueue {
00036 
00037 public:
00038     /**
00039      * Type of the nodes in this queue.
00040      */
00041     struct Node {
00042         AlignedStorage<T> storage;      /// storage for the T
00043         Node* next;                     /// pointer to the next node
00044     };
00045 
00046     /**
00047      * Iterator for elements of the queue.
00048      */
00049     class Iterator {
00050         friend PriorityQueue;
00051 
00052         /// Construct an iterator from a Node.
00053         /// This constructor is private and can only be invoked from the PriorityQueue.
00054         Iterator(Node* current) :
00055             _current(current) {
00056         }
00057 
00058     public:
00059 
00060         /// Indirection operator.
00061         /// return a reference to the inner T
00062         T& operator*() {
00063             return _current->storage.get();
00064         }
00065 
00066         /// Const version of indirection operator.
00067         /// return a reference to the inner T
00068         const T& operator*() const {
00069             return _current->storage.get();
00070         }
00071 
00072         /// dereference operator.
00073         /// Will invoke the operation on the inner T
00074         T* operator->() {
00075             return &(_current->storage.get());
00076         }
00077 
00078         /// const dereference operator.
00079         /// Will invoke the operation on the inner T
00080         const T* operator->() const {
00081             return &(_current->storage.get());
00082         }
00083 
00084         /// pre incrementation to the next T in the list
00085         Iterator& operator++() {
00086             _current = _current->next;
00087             return *this;
00088         }
00089 
00090         /// post incrementation to the next T in the list
00091         Iterator operator++(int) {
00092             Iterator tmp(*this);
00093             _current = _current->next;
00094             return tmp;
00095         }
00096 
00097         /// Equality operator
00098         friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
00099             return lhs._current == rhs._current;
00100         }
00101 
00102         /// Unequality operator
00103         friend bool operator!=(const Iterator& lhs, const Iterator& rhs) {
00104             return !(lhs == rhs);
00105         }
00106 
00107         /// return the internal node.
00108         Node* get_node() {
00109             return _current;
00110         }
00111 
00112     private:
00113         Node* _current;
00114     };
00115 
00116     typedef Iterator iterator;
00117 
00118     /// Construct an empty priority queue.
00119     PriorityQueue() : nodes(), free_nodes(NULL), head(NULL), used_nodes_count(0) {
00120         initialize();
00121     }
00122 
00123     /// Copy construct a priority queue.
00124     /// The queue will have the same content has other.
00125     PriorityQueue(const PriorityQueue& other) :
00126         nodes(), free_nodes(NULL), head(NULL), used_nodes_count(0) {
00127         initialize();
00128         copy(other);
00129     }
00130 
00131     /// destroy a priority queue.
00132     ~PriorityQueue() {
00133         clear();
00134     }
00135 
00136     /// Copy assignemnent from another priority queue.
00137     /// The content of the queue will be destroyed then the content from
00138     /// other will be copied.
00139     PriorityQueue& operator=(const PriorityQueue& other) {
00140         if (&other == this) {
00141             return *this;
00142         }
00143         copy(other);
00144         return *this;
00145     }
00146 
00147     /// Push a new element to the queue.
00148     /// It will be added before the first element p in the queue where
00149     /// element < p == true.
00150     /// @return An iterator to the inserted element.
00151     iterator push(const T& element) {
00152         if (full()) {
00153             return NULL;
00154         }
00155 
00156         // get a free node
00157         Node* new_node = free_nodes;
00158         free_nodes = free_nodes->next;
00159         new_node->next = NULL;
00160 
00161         ++used_nodes_count;
00162 
00163         // copy content
00164         new (new_node->storage.get_storage()) T(element);
00165 
00166         // if there is no node in the queue, just link the head
00167         // to the new node and return
00168         if (head == NULL) {
00169             head = new_node;
00170             return new_node;
00171         }
00172 
00173         // if the new node has an higher priority than the node in head
00174         // just link it as the head
00175         if (element < head->storage.get()) {
00176             new_node->next = head;
00177             head = new_node;
00178             return new_node;
00179         }
00180 
00181         // insert the node after head
00182         insert_after(head, new_node);
00183 
00184         return new_node;
00185     }
00186 
00187     /// pop the head of the queue.
00188     bool pop() {
00189         if (!head) {
00190             return false;
00191         }
00192 
00193         Node* target = head;
00194         target->storage.get().~T();
00195         head = target->next;
00196         target->next = free_nodes;
00197         free_nodes = target;
00198         --used_nodes_count;
00199         return true;
00200     }
00201 
00202     /// If the content of an element is updated is updated after the insertion
00203     /// then, the list can be in an unordered state.
00204     /// This function help; it update the position of an iterator in the list.
00205     void update(iterator it) {
00206         Node* target = it.get_node();
00207         Node* hint = head;
00208 
00209         if (target == NULL) {
00210             return;
00211         }
00212 
00213         // remove the node from the list
00214         if (target == head) {
00215             // if it is the only node in the list, just return
00216             // it is not needed to update its position
00217             if (target->next == NULL) {
00218                 return;
00219             }
00220 
00221             // if the order is already correct, just return
00222             if (target->storage.get() < target->next->storage.get()) {
00223                 return;
00224             }
00225 
00226             // otherwise remove the node from the list
00227             // and update the hint
00228             head = target->next;
00229             hint = head;
00230         } else {
00231             bool node_found = false;
00232             for (Node* current = head; current != NULL; current = current->next) {
00233                 if (current->next == target) {
00234                     // check if it is needed to move the node
00235                     if (current->storage.get() < target->storage.get()) {
00236                         if (target->next == NULL) {
00237                             return;
00238                         }
00239 
00240                         if (target->storage.get() < target->next->storage.get()) {
00241                             return;
00242                         }
00243 
00244                         // there is no need to iterate again the whole list
00245                         // just mark the hint has the current node
00246                         hint = current;
00247                     }
00248 
00249                     // remove the node from the list and break out of the loop
00250                     current->next = target->next;
00251                     node_found = true;
00252                     break;
00253                 }
00254             }
00255 
00256             // the node in parameter doesn't belong to this queue
00257             if (!node_found) {
00258                 return;
00259             }
00260         }
00261 
00262         // insert the node after hint
00263         insert_after(hint, target);
00264     }
00265 
00266     /// return an iterator to the begining of the queue.
00267     iterator begin() {
00268         return head;
00269     }
00270 
00271     /// return an iterator to the end of the queue.
00272     /// @note can't be dereferenced
00273     iterator end() {
00274         return NULL;
00275     }
00276 
00277     /// erase an iterator from the list
00278     bool erase(iterator it) {
00279         return erase(it.get_node());
00280     }
00281 
00282     /// erase a node from the list
00283     bool erase(Node* n) {
00284         if (n == NULL) {
00285             return false;
00286         }
00287 
00288         if (head == n) {
00289             return pop();
00290         }
00291 
00292         Node* current = head;
00293         while (current->next) {
00294             if (current->next == n) {
00295                 current->next = n->next;
00296                 n->storage.get().~T();
00297                 n->next = free_nodes;
00298                 free_nodes = n;
00299                 --used_nodes_count;
00300                 return true;
00301             }
00302             current = current->next;
00303         }
00304         return false;
00305     }
00306 
00307     /**
00308      * Indicate if the queue is empty or not.
00309      * @return true if the queue is empty and false otherwise.
00310      * @invariant the queue remains untouched.
00311      */
00312     bool empty() const {
00313         return head == NULL;
00314     }
00315 
00316     /**
00317      * Indicate if the true is full or not.
00318      * @return true if the queue is full and false otherwise.
00319      * @invariant the queue remains untouched.
00320      */
00321     bool full() const {
00322         return free_nodes == NULL;
00323     }
00324 
00325     /**
00326      * Indicate the number of elements in the queue.
00327      * @return the number of elements currently held by the queue.
00328      * @invariant the queue remains untouched.
00329      */
00330     std::size_t size() const {
00331         return used_nodes_count;
00332     }
00333 
00334     /**
00335      * Expose the capacity of the queue in terms of number of elements the
00336      * queue can hold.
00337      * @return the capacity of the queue.
00338      * @invariant this function should always return Capacity.
00339      */
00340     std::size_t capacity() const {
00341         return Capacity;
00342     }
00343 
00344     /**
00345      * Clear the queue from all its elements.
00346      */
00347     void clear() {
00348         while (head) {
00349             head->storage.get().~T();
00350             Node* tmp = head;
00351             head = head->next;
00352             tmp->next = free_nodes;
00353             free_nodes = tmp;
00354         }
00355         used_nodes_count = 0;
00356     }
00357 
00358 private:
00359     void initialize() {
00360         /// link all the nodes together
00361         for (std::size_t i = 0; i < (Capacity - 1); ++i) {
00362             nodes[i].next = &nodes[i + 1];
00363         }
00364         /// the last node does not have a next node
00365         nodes[Capacity - 1].next = NULL;
00366         /// set all the nodes as free
00367         free_nodes = nodes;
00368     }
00369 
00370     void copy(const PriorityQueue& other) {
00371         if (empty() == false) {
00372             clear();
00373         }
00374 
00375         Node *to_copy = other.head;
00376         Node *previous = NULL;
00377         while (to_copy) {
00378             // pick a free node
00379             Node* new_node = free_nodes;
00380             free_nodes = free_nodes->next;
00381             new_node->next = NULL;
00382 
00383             // copy content
00384             new (new_node->storage.get_storage()) T(to_copy->storage.get());
00385 
00386             // link into the queue or update head then update previous pointer
00387             if (previous) {
00388                 previous->next = new_node;
00389             } else {
00390                 head = new_node;
00391             }
00392             previous = new_node;
00393 
00394             // update the node to copy
00395             to_copy = to_copy->next;
00396         }
00397         used_nodes_count = other.used_nodes_count;
00398     }
00399 
00400     void insert_after(Node* prev, Node* to_insert) {
00401         for (; prev != NULL; prev = prev->next) {
00402             if (prev->next == NULL || to_insert->storage.get() < prev->next->storage.get()) {
00403                 to_insert->next = prev->next;
00404                 prev->next = to_insert;
00405                 break;
00406             }
00407         }
00408     }
00409 
00410     Node nodes[Capacity];         //< Nodes of the queue
00411     Node *free_nodes;             //< entry point for the list of free nodes
00412     Node *head;                   //< head of the queue
00413     std::size_t used_nodes_count; // number of nodes used
00414 };
00415 
00416 } // namespace eq
00417 
00418 #endif /* EVENTQUEUE_STACKPRIORITYQUEUE_H_ */