1 /* Copyright (c) 2015, The Linux Foundation. All rights reserved. 2 * 3 * Redistribution and use in source and binary forms, with or without 4 * modification, are permitted provided that the following conditions are 5 * met: 6 * * Redistributions of source code must retain the above copyright 7 * notice, this list of conditions and the following disclaimer. 8 * * Redistributions in binary form must reproduce the above 9 * copyright notice, this list of conditions and the following 10 * disclaimer in the documentation and/or other materials provided 11 * with the distribution. 12 * * Neither the name of The Linux Foundation, nor the names of its 13 * contributors may be used to endorse or promote products derived 14 * from this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED 17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS 20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 23 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 25 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 26 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 */ 29 #ifndef __LOC_HEAP__ 30 #define __LOC_HEAP__ 31 32 #include <stddef.h> 33 #include <string.h> 34 35 // abstract class to be implemented by client to provide a rankable class 36 class LocRankable { 37 public: ~LocRankable()38 virtual inline ~LocRankable() {} 39 40 // method to rank objects of such type for sorting purposes. 41 // The pointer of the input node would be stored in the heap. 42 // >0 if ranks higher than the input; 43 // ==0 if equally ranks with the input; 44 // <0 if ranks lower than the input 45 virtual int ranks(LocRankable& rankable) = 0; 46 47 // convenient method to rank objects of such type for sorting purposes. outRanks(LocRankable & rankable)48 inline bool outRanks(LocRankable& rankable) { return ranks(rankable) > 0; } 49 }; 50 51 // opaque class to provide service implementation. 52 class LocHeapNode; 53 54 // a heap whose left and right children are not sorted. It is sorted only vertically, 55 // i.e. parent always ranks higher than children, if they exist. Ranking algorithm is 56 // implemented in Rankable. The reason that there is no sort between children is to 57 // help beter balance the tree with lower cost. When a node is pushed to the tree, 58 // it is guaranteed that the subtree that is smaller gets to have the new node. 59 class LocHeap { 60 protected: 61 LocHeapNode* mTree; 62 public: LocHeap()63 inline LocHeap() : mTree(NULL) {} 64 ~LocHeap(); 65 66 // push keeps the tree sorted by rank, it also tries to balance the 67 // tree by adding the new node to the smaller of the subtrees. 68 // node is reference to an obj that is managed by client, that client 69 // creates and destroyes. The destroy should happen after the 70 // node is popped out from the heap. 71 void push(LocRankable& node); 72 73 // Peeks the node data on tree top, which has currently the highest ranking 74 // There is no change the tree structure with this operation 75 // Returns NULL if the tree is empty, otherwise pointer to the node data of 76 // the tree top. 77 LocRankable* peek(); 78 79 // pop keeps the tree sorted by rank, but it does not try to balance 80 // the tree. 81 // Return - pointer to the node popped out, or NULL if heap is already empty 82 LocRankable* pop(); 83 84 // navigating through the tree and find the node that ranks the same 85 // as the input data, then remove it from the tree. Rank is implemented 86 // by rankable obj. 87 // returns the pointer to the node removed; or NULL (if failed). 88 LocRankable* remove(LocRankable& rankable); 89 90 #ifdef __LOC_UNIT_TEST__ 91 bool checkTree(); 92 uint32_t getTreeSize(); 93 #endif 94 }; 95 96 #endif //__LOC_HEAP__ 97