1 /* Copyright (c) 2015, 2020 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 namespace loc_util { 36 37 // abstract class to be implemented by client to provide a rankable class 38 class LocRankable { 39 public: ~LocRankable()40 virtual inline ~LocRankable() {} 41 42 // method to rank objects of such type for sorting purposes. 43 // The pointer of the input node would be stored in the heap. 44 // >0 if ranks higher than the input; 45 // ==0 if equally ranks with the input; 46 // <0 if ranks lower than the input 47 virtual int ranks(LocRankable& rankable) = 0; 48 49 // convenient method to rank objects of such type for sorting purposes. outRanks(LocRankable & rankable)50 inline bool outRanks(LocRankable& rankable) { return ranks(rankable) > 0; } 51 }; 52 53 // opaque class to provide service implementation. 54 class LocHeapNode; 55 56 // a heap whose left and right children are not sorted. It is sorted only vertically, 57 // i.e. parent always ranks higher than children, if they exist. Ranking algorithm is 58 // implemented in Rankable. The reason that there is no sort between children is to 59 // help beter balance the tree with lower cost. When a node is pushed to the tree, 60 // it is guaranteed that the subtree that is smaller gets to have the new node. 61 class LocHeap { 62 protected: 63 LocHeapNode* mTree; 64 public: LocHeap()65 inline LocHeap() : mTree(NULL) {} 66 ~LocHeap(); 67 68 // push keeps the tree sorted by rank, it also tries to balance the 69 // tree by adding the new node to the smaller of the subtrees. 70 // node is reference to an obj that is managed by client, that client 71 // creates and destroyes. The destroy should happen after the 72 // node is popped out from the heap. 73 void push(LocRankable& node); 74 75 // Peeks the node data on tree top, which has currently the highest ranking 76 // There is no change the tree structure with this operation 77 // Returns NULL if the tree is empty, otherwise pointer to the node data of 78 // the tree top. 79 LocRankable* peek(); 80 81 // pop keeps the tree sorted by rank, but it does not try to balance 82 // the tree. 83 // Return - pointer to the node popped out, or NULL if heap is already empty 84 LocRankable* pop(); 85 86 // navigating through the tree and find the node that ranks the same 87 // as the input data, then remove it from the tree. Rank is implemented 88 // by rankable obj. 89 // returns the pointer to the node removed; or NULL (if failed). 90 LocRankable* remove(LocRankable& rankable); 91 92 #ifdef __LOC_UNIT_TEST__ 93 bool checkTree(); 94 uint32_t getTreeSize(); 95 #endif 96 }; 97 98 } // namespace loc_util 99 100 #endif //__LOC_HEAP__ 101