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, 354 insertions, 0 deletions
diff --git a/gps/utils/LocHeap.cpp b/gps/utils/LocHeap.cpp
new file mode 100644
index 0000000..d667f14
--- /dev/null
+++ b/gps/utils/LocHeap.cpp
@@ -0,0 +1,354 @@
+/* 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 17:02:57 +0000