1e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti/* Copyright (c) 2015, The Linux Foundation. All rights reserved. 2e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * 3e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * Redistribution and use in source and binary forms, with or without 4e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * modification, are permitted provided that the following conditions are 5e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * met: 6e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * * Redistributions of source code must retain the above copyright 7e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * notice, this list of conditions and the following disclaimer. 8e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * * Redistributions in binary form must reproduce the above 9e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * copyright notice, this list of conditions and the following 10e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * disclaimer in the documentation and/or other materials provided 11e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * with the distribution. 12e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * * Neither the name of The Linux Foundation, nor the names of its 13e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * contributors may be used to endorse or promote products derived 14e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * from this software without specific prior written permission. 15e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * 16e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED 17e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 18e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT 19e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS 20e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 23e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 24e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 25e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 26e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti * 28e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti */ 29e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#include <LocHeap.h> 30e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 31e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleticlass LocHeapNode { 32e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti friend class LocHeap; 33e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 34e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // size of of the subtree, excluding self, 1 if no subtree 35e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti int mSize; 36e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* mLeft; 37e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* mRight; 38e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* mData; 39e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletipublic: 40e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti inline LocHeapNode(LocRankable& data) : 41e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mSize(1), mLeft(NULL), mRight(NULL), mData(&data) {} 42e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti ~LocHeapNode(); 43e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 44e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // this only swaps the data of the two nodes, so no 45e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // detach / re-attached is necessary 46e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti void swap(LocHeapNode& node); 47e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 48e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* detachData(); 49e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 50e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // push a node into the tree stucture, keeping sorted by rank 51e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti void push(LocHeapNode& node); 52e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 53e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // pop the head node out of the tree stucture. keeping sorted by rank 54e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti static LocHeapNode* pop(LocHeapNode*& top); 55e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 56e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // remove a specific node from the tree 57e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // returns the pointer to the node removed, which would be either the 58e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // same as input (if successfully removed); or NULL (if failed). 59e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti static LocHeapNode* remove(LocHeapNode*& top, LocRankable& data); 60e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 61e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // convenience method to compare data ranking 62e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti inline bool outRanks(LocHeapNode& node) { return mData->outRanks(*node.mData); } 63e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti inline bool outRanks(LocRankable& data) { return mData->outRanks(data); } 64e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 65e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // checks if mSize is correct, AND this node is the highest ranking 66e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // of the entire subtree 67e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti bool checkNodes(); 68e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 69e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti inline int getSize() { return mSize; } 70e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti}; 71e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 72e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletiinline 73e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocHeapNode::~LocHeapNode() { 74e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mLeft) { 75e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete mLeft; 76e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mLeft = NULL; 77e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 78e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mRight) { 79e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete mRight; 80e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mRight = NULL; 81e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 82e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mData) { 83e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mData = NULL; 84e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 85e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 86e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 87e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletiinline 88e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletivoid LocHeapNode::swap(LocHeapNode& node) { 89e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* tmpData = node.mData; 90e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti node.mData = mData; 91e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mData = tmpData; 92e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 93e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 94e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletiinline 95e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocRankable* LocHeapNode::detachData() { 96e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* data = mData; 97e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mData = NULL; 98e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return data; 99e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 100e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 101e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// push keeps the tree sorted by rank, it also tries to balance the 102e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// tree by adding the new node to the smaller of the subtrees. 103e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// The pointer to the tree and internal links never change. If the 104e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// mData of tree top ranks lower than that of the incoming node, 105e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// mData will be swapped with that of the incoming node to ensure 106e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// ranking, no restructuring the container nodes. 107e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletivoid LocHeapNode::push(LocHeapNode& node) { 108e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // ensure the current node ranks higher than in the incoming one 109e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (node.outRanks(*this)) { 110e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti swap(node); 111e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 112e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 113e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // now drop the new node (ensured lower than *this) into a subtree 114e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (NULL == mLeft) { 115e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mLeft = &node; 116e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else if (NULL == mRight) { 117e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mRight = &node; 118e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else if (mLeft->mSize <= mRight->mSize) { 119e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mLeft->push(node); 120e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else { 121e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mRight->push(node); 122e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 123e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mSize++; 124e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 125e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 126e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// pop keeps the tree sorted by rank, but it does not try to balance 127e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// the tree. It recursively swaps with the higher ranked top of the 128e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// subtrees. 129e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// The return is a popped out node from leaf level, that has the data 130e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// swapped all the way down from the top. The pinter to the tree and 131e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// internal links will not be changed or restructured, except for the 132e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// node that is popped out. 133e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// If the return pointer == this, this the last node in the tree. 134e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocHeapNode* LocHeapNode::pop(LocHeapNode*& top) { 135e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // we know the top has the highest ranking at this point, else 136e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // the tree is broken. This top will be popped out. But we need 137e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // a node from the left or right child, whichever ranks higher, 138e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // to replace the current top. This then will need to be done 139e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // recursively to the leaf level. So we swap the mData of the 140e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // current top node all the way down to the leaf level. 141e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* poppedNode = top; 142e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // top is losing a node in its subtree 143e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti top->mSize--; 144e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (top->mLeft || top->mRight) { 145e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // if mLeft is NULL, mRight for sure is NOT NULL, take that; 146e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // else if mRight is NULL, mLeft for sure is NOT, take that; 147e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // else we take the address of whatever has higher ranking mData 148e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode*& subTop = (NULL == top->mLeft) ? top->mRight : 149e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti ((NULL == top->mRight) ? top->mLeft : 150e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti (top->mLeft->outRanks(*(top->mRight)) ? top->mLeft : top->mRight)); 151e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // swap mData, the tree top gets updated with the new data. 152e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti top->swap(*subTop); 153e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // pop out from the subtree 154e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti poppedNode = pop(subTop); 155e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else { 156e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // if the top has only single node 157e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // detach the poppedNode from the tree 158e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // subTop is the reference of ether mLeft or mRight 159e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // NOT a local stack pointer. so it MUST be NULL'ed here. 160e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti top = NULL; 161e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 162e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 163e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return poppedNode; 164e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 165e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 166e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// navigating through the tree and find the node that hass the input 167e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// data. Since this is a heap, we do recursive linear search. 168e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// returns the pointer to the node removed, which would be either the 169e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// same as input (if successfully removed); or NULL (if failed). 170e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocHeapNode* LocHeapNode::remove(LocHeapNode*& top, LocRankable& data) { 171e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* removedNode = NULL; 172e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // this is the node, by address 173e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (&data == (LocRankable*)(top->mData)) { 174e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // pop this node out 175e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti removedNode = pop(top); 176e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else if (!data.outRanks(*top->mData)) { 177e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // subtrees might have this node 178e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (top->mLeft) { 179e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti removedNode = remove(top->mLeft, data); 180e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 181e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // if we did not find in mLeft, and mRight is not empty 182e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (!removedNode && top->mRight) { 183e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti removedNode = remove(top->mRight, data); 184e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 185e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 186e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // top lost a node in its subtree 187e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (removedNode) { 188e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti top->mSize--; 189e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 190e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 191e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 192e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return removedNode; 193e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 194e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 195e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// checks if mSize is correct, AND this node is the highest ranking 196e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// of the entire subtree 197e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletibool LocHeapNode::checkNodes() { 198e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // size of the current subtree 199e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti int totalSize = mSize; 200e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mLeft) { 201e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // check the consistency of left subtree 202e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mLeft->outRanks(*this) || !mLeft->checkNodes()) { 203e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return false; 204e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 205e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // subtract the size of left subtree (with subtree head) 206e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti totalSize -= mLeft->mSize; 207e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 208e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 209e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mRight) { 210e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // check the consistency of right subtree 211e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mRight->outRanks(*this) || !mRight->checkNodes()) { 212e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return false; 213e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 214e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // subtract the size of right subtree (with subtree head) 215e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti totalSize -= mRight->mSize; 216e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 217e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 218e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // for the tree nodes to consistent, totalSize must be 1 now 219e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return totalSize == 1; 220e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 221e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 222e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocHeap::~LocHeap() { 223e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mTree) { 224e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete mTree; 225e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 226e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 227e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 228e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletivoid LocHeap::push(LocRankable& node) { 229e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* heapNode = new LocHeapNode(node); 230e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (!mTree) { 231e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mTree = heapNode; 232e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else { 233e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti mTree->push(*heapNode); 234e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 235e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 236e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 237e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocRankable* LocHeap::peek() { 238e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* top = NULL; 239e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mTree) { 240e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti top = mTree->mData; 241e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 242e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return top; 243e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 244e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 245e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocRankable* LocHeap::pop() { 246e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* locNode = NULL; 247e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mTree) { 248e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // mTree may become NULL after this call 249e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* heapNode = LocHeapNode::pop(mTree); 250e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti locNode = heapNode->detachData(); 251e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete heapNode; 252e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 253e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return locNode; 254e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 255e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 256e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore PasupuletiLocRankable* LocHeap::remove(LocRankable& rankable) { 257e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* locNode = NULL; 258e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (mTree) { 259e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti // mTree may become NULL after this call 260e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapNode* heapNode = LocHeapNode::remove(mTree, rankable); 261e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (heapNode) { 262e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti locNode = heapNode->detachData(); 263e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete heapNode; 264e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 265e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 266e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return locNode; 267e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 268e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 269e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#ifdef __LOC_UNIT_TEST__ 270e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletibool LocHeap::checkTree() { 271e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return ((NULL == mTree) || mTree->checkNodes()); 272e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 273e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletiuint32_t LocHeap::getTreeSize() { 274e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return (NULL == mTree) ? 0 : mTree->getSize(); 275e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 276e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#endif 277e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 278e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#ifdef __LOC_DEBUG__ 279e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 280e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#include <stdio.h> 281e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#include <stdlib.h> 282e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#include <time.h> 283e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 284e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleticlass LocHeapDebug : public LocHeap { 285e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletipublic: 286e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti bool checkTree() { 287e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return ((NULL == mTree) || mTree->checkNodes()); 288e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 289e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 290e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti uint32_t getTreeSize() { 291e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return (NULL == mTree) ? 0 : (mTree->getSize()); 292e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 293e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti}; 294e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 295e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleticlass LocHeapDebugData : public LocRankable { 296e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti const int mID; 297e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletipublic: 298e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapDebugData(int id) : mID(id) {} 299e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti inline virtual int ranks(LocRankable& rankable) { 300e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapDebugData* testData = dynamic_cast<LocHeapDebugData*>(&rankable); 301e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return testData->mID - mID; 302e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 303e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti}; 304e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 305e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// For Linux command line testing: 306e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// compilation: g++ -D__LOC_HOST_DEBUG__ -D__LOC_DEBUG__ -g -I. -I../../../../vendor/qcom/proprietary/gps-internal/unit-tests/fakes_for_host -I../../../../system/core/include LocHeap.cpp 307e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti// test: valgrind --leak-check=full ./a.out 100 308e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuletiint main(int argc, char** argv) { 309e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti srand(time(NULL)); 310e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti int tries = atoi(argv[1]); 311e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti int checks = tries >> 3; 312e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapDebug heap; 313e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti int treeSize = 0; 314e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 315e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti for (int i = 0; i < tries; i++) { 316e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (i % checks == 0 && !heap.checkTree()) { 317e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti printf("tree check failed before %dth op\n", i); 318e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 319e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti int r = rand(); 320e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 321e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (r & 1) { 322e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocHeapDebugData* data = new LocHeapDebugData(r >> 1); 323e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti heap.push(dynamic_cast<LocRankable&>(*data)); 324e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti treeSize++; 325e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else { 326e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti LocRankable* rankable = heap.pop(); 327e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (rankable) { 328e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete rankable; 329e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 330e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti treeSize ? treeSize-- : 0; 331e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 332e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 333e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti printf("%s: %d == %d\n", (r&1)?"push":"pop", treeSize, heap.getTreeSize()); 334e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (treeSize != heap.getTreeSize()) { 335e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n"); 336e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti tries = i+1; 337e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti break; 338e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 339e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 340e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 341e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti if (!heap.checkTree()) { 342e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti printf("!!!!!!!!!!tree check failed at the end after %d ops!!!!!!!\n", tries); 343e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } else { 344e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti printf("success!\n"); 345e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 346e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 347e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti for (LocRankable* data = heap.pop(); NULL != data; data = heap.pop()) { 348e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti delete data; 349e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti } 350e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 351e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti return 0; 352e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti} 353e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti 354e7c98642e1e156ea6cde1238cd0006f669cfb696Uday Kishore Pasupuleti#endif 355