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
36class LocRankable {
37public:
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.
48    inline bool outRanks(LocRankable& rankable) { return ranks(rankable) > 0; }
49};
50
51// opaque class to provide service implementation.
52class 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.
59class LocHeap {
60protected:
61    LocHeapNode* mTree;
62public:
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