summaryrefslogtreecommitdiff
path: root/gps/utils/LocHeap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gps/utils/LocHeap.cpp')
-rw-r--r--gps/utils/LocHeap.cpp354
1 files changed, 0 insertions, 354 deletions
diff --git a/gps/utils/LocHeap.cpp b/gps/utils/LocHeap.cpp
deleted file mode 100644
index d667f14..0000000
--- a/gps/utils/LocHeap.cpp
+++ /dev/null
@@ -1,354 +0,0 @@
-/* Copyright (c) 2015, The Linux Foundation. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are
- * met:
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above
- * copyright notice, this list of conditions and the following
- * disclaimer in the documentation and/or other materials provided
- * with the distribution.
- * * Neither the name of The Linux Foundation, nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
- * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
- * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
- * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
- * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- */
-#include <LocHeap.h>
-
-class LocHeapNode {
- friend class LocHeap;
-
- // size of of the subtree, excluding self, 1 if no subtree
- int mSize;
- LocHeapNode* mLeft;
- LocHeapNode* mRight;
- LocRankable* mData;
-public:
- inline LocHeapNode(LocRankable& data) :
- mSize(1), mLeft(NULL), mRight(NULL), mData(&data) {}
- ~LocHeapNode();
-
- // this only swaps the data of the two nodes, so no
- // detach / re-attached is necessary
- void swap(LocHeapNode& node);
-
- LocRankable* detachData();
-
- // push a node into the tree stucture, keeping sorted by rank
- void push(LocHeapNode& node);
-
- // pop the head node out of the tree stucture. keeping sorted by rank
- static LocHeapNode* pop(LocHeapNode*& top);
-
- // remove a specific node from the tree
- // returns the pointer to the node removed, which would be either the
- // same as input (if successfully removed); or NULL (if failed).
- static LocHeapNode* remove(LocHeapNode*& top, LocRankable& data);
-
- // convenience method to compare data ranking
- inline bool outRanks(LocHeapNode& node) { return mData->outRanks(*node.mData); }
- inline bool outRanks(LocRankable& data) { return mData->outRanks(data); }
-
- // checks if mSize is correct, AND this node is the highest ranking
- // of the entire subtree
- bool checkNodes();
-
- inline int getSize() { return mSize; }
-};
-
-inline
-LocHeapNode::~LocHeapNode() {
- if (mLeft) {
- delete mLeft;
- mLeft = NULL;
- }
- if (mRight) {
- delete mRight;
- mRight = NULL;
- }
- if (mData) {
- mData = NULL;
- }
-}
-
-inline
-void LocHeapNode::swap(LocHeapNode& node) {
- LocRankable* tmpData = node.mData;
- node.mData = mData;
- mData = tmpData;
-}
-
-inline
-LocRankable* LocHeapNode::detachData() {
- LocRankable* data = mData;
- mData = NULL;
- return data;
-}
-
-// push keeps the tree sorted by rank, it also tries to balance the
-// tree by adding the new node to the smaller of the subtrees.
-// The pointer to the tree and internal links never change. If the
-// mData of tree top ranks lower than that of the incoming node,
-// mData will be swapped with that of the incoming node to ensure
-// ranking, no restructuring the container nodes.
-void LocHeapNode::push(LocHeapNode& node) {
- // ensure the current node ranks higher than in the incoming one
- if (node.outRanks(*this)) {
- swap(node);
- }
-
- // now drop the new node (ensured lower than *this) into a subtree
- if (NULL == mLeft) {
- mLeft = &node;
- } else if (NULL == mRight) {
- mRight = &node;
- } else if (mLeft->mSize <= mRight->mSize) {
- mLeft->push(node);
- } else {
- mRight->push(node);
- }
- mSize++;
-}
-
-// pop keeps the tree sorted by rank, but it does not try to balance
-// the tree. It recursively swaps with the higher ranked top of the
-// subtrees.
-// The return is a popped out node from leaf level, that has the data
-// swapped all the way down from the top. The pinter to the tree and
-// internal links will not be changed or restructured, except for the
-// node that is popped out.
-// If the return pointer == this, this the last node in the tree.
-LocHeapNode* LocHeapNode::pop(LocHeapNode*& top) {
- // we know the top has the highest ranking at this point, else
- // the tree is broken. This top will be popped out. But we need
- // a node from the left or right child, whichever ranks higher,
- // to replace the current top. This then will need to be done
- // recursively to the leaf level. So we swap the mData of the
- // current top node all the way down to the leaf level.
- LocHeapNode* poppedNode = top;
- // top is losing a node in its subtree
- top->mSize--;
- if (top->mLeft || top->mRight) {
- // if mLeft is NULL, mRight for sure is NOT NULL, take that;
- // else if mRight is NULL, mLeft for sure is NOT, take that;
- // else we take the address of whatever has higher ranking mData
- LocHeapNode*& subTop = (NULL == top->mLeft) ? top->mRight :
- ((NULL == top->mRight) ? top->mLeft :
- (top->mLeft->outRanks(*(top->mRight)) ? top->mLeft : top->mRight));
- // swap mData, the tree top gets updated with the new data.
- top->swap(*subTop);
- // pop out from the subtree
- poppedNode = pop(subTop);
- } else {
- // if the top has only single node
- // detach the poppedNode from the tree
- // subTop is the reference of ether mLeft or mRight
- // NOT a local stack pointer. so it MUST be NULL'ed here.
- top = NULL;
- }
-
- return poppedNode;
-}
-
-// navigating through the tree and find the node that hass the input
-// data. Since this is a heap, we do recursive linear search.
-// returns the pointer to the node removed, which would be either the
-// same as input (if successfully removed); or NULL (if failed).
-LocHeapNode* LocHeapNode::remove(LocHeapNode*& top, LocRankable& data) {
- LocHeapNode* removedNode = NULL;
- // this is the node, by address
- if (&data == (LocRankable*)(top->mData)) {
- // pop this node out
- removedNode = pop(top);
- } else if (!data.outRanks(*top->mData)) {
- // subtrees might have this node
- if (top->mLeft) {
- removedNode = remove(top->mLeft, data);
- }
- // if we did not find in mLeft, and mRight is not empty
- if (!removedNode && top->mRight) {
- removedNode = remove(top->mRight, data);
- }
-
- // top lost a node in its subtree
- if (removedNode) {
- top->mSize--;
- }
- }
-
- return removedNode;
-}
-
-// checks if mSize is correct, AND this node is the highest ranking
-// of the entire subtree
-bool LocHeapNode::checkNodes() {
- // size of the current subtree
- int totalSize = mSize;
- if (mLeft) {
- // check the consistency of left subtree
- if (mLeft->outRanks(*this) || !mLeft->checkNodes()) {
- return false;
- }
- // subtract the size of left subtree (with subtree head)
- totalSize -= mLeft->mSize;
- }
-
- if (mRight) {
- // check the consistency of right subtree
- if (mRight->outRanks(*this) || !mRight->checkNodes()) {
- return false;
- }
- // subtract the size of right subtree (with subtree head)
- totalSize -= mRight->mSize;
- }
-
- // for the tree nodes to consistent, totalSize must be 1 now
- return totalSize == 1;
-}
-
-LocHeap::~LocHeap() {
- if (mTree) {
- delete mTree;
- }
-}
-
-void LocHeap::push(LocRankable& node) {
- LocHeapNode* heapNode = new LocHeapNode(node);
- if (!mTree) {
- mTree = heapNode;
- } else {
- mTree->push(*heapNode);
- }
-}
-
-LocRankable* LocHeap::peek() {
- LocRankable* top = NULL;
- if (mTree) {
- top = mTree->mData;
- }
- return top;
-}
-
-LocRankable* LocHeap::pop() {
- LocRankable* locNode = NULL;
- if (mTree) {
- // mTree may become NULL after this call
- LocHeapNode* heapNode = LocHeapNode::pop(mTree);
- locNode = heapNode->detachData();
- delete heapNode;
- }
- return locNode;
-}
-
-LocRankable* LocHeap::remove(LocRankable& rankable) {
- LocRankable* locNode = NULL;
- if (mTree) {
- // mTree may become NULL after this call
- LocHeapNode* heapNode = LocHeapNode::remove(mTree, rankable);
- if (heapNode) {
- locNode = heapNode->detachData();
- delete heapNode;
- }
- }
- return locNode;
-}
-
-#ifdef __LOC_UNIT_TEST__
-bool LocHeap::checkTree() {
- return ((NULL == mTree) || mTree->checkNodes());
-}
-uint32_t LocHeap::getTreeSize() {
- return (NULL == mTree) ? 0 : mTree->getSize();
-}
-#endif
-
-#ifdef __LOC_DEBUG__
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-class LocHeapDebug : public LocHeap {
-public:
- bool checkTree() {
- return ((NULL == mTree) || mTree->checkNodes());
- }
-
- uint32_t getTreeSize() {
- return (NULL == mTree) ? 0 : (mTree->getSize());
- }
-};
-
-class LocHeapDebugData : public LocRankable {
- const int mID;
-public:
- LocHeapDebugData(int id) : mID(id) {}
- inline virtual int ranks(LocRankable& rankable) {
- LocHeapDebugData* testData = dynamic_cast<LocHeapDebugData*>(&rankable);
- return testData->mID - mID;
- }
-};
-
-// For Linux command line testing:
-// 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
-// test: valgrind --leak-check=full ./a.out 100
-int main(int argc, char** argv) {
- srand(time(NULL));
- int tries = atoi(argv[1]);
- int checks = tries >> 3;
- LocHeapDebug heap;
- int treeSize = 0;
-
- for (int i = 0; i < tries; i++) {
- if (i % checks == 0 && !heap.checkTree()) {
- printf("tree check failed before %dth op\n", i);
- }
- int r = rand();
-
- if (r & 1) {
- LocHeapDebugData* data = new LocHeapDebugData(r >> 1);
- heap.push(dynamic_cast<LocRankable&>(*data));
- treeSize++;
- } else {
- LocRankable* rankable = heap.pop();
- if (rankable) {
- delete rankable;
- }
- treeSize ? treeSize-- : 0;
- }
-
- printf("%s: %d == %d\n", (r&1)?"push":"pop", treeSize, heap.getTreeSize());
- if (treeSize != heap.getTreeSize()) {
- printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n");
- tries = i+1;
- break;
- }
- }
-
- if (!heap.checkTree()) {
- printf("!!!!!!!!!!tree check failed at the end after %d ops!!!!!!!\n", tries);
- } else {
- printf("success!\n");
- }
-
- for (LocRankable* data = heap.pop(); NULL != data; data = heap.pop()) {
- delete data;
- }
-
- return 0;
-}
-
-#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 15:42:11 +0000