From c7eee6fef0263ed4eb5aa0d934a0a8c972d41b30 Mon Sep 17 00:00:00 2001 From: bigbiff bigbiff Date: Tue, 2 Sep 2014 18:59:01 -0400 Subject: add mtp responder to TWRP. Big thanks to Dees_Troy for helping with the implementation. Change-Id: I6c9c522b9c9de5dc139e2ecb0141008182ba07f0 --- mtp/btree.cpp | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 308 insertions(+) create mode 100755 mtp/btree.cpp (limited to 'mtp/btree.cpp') diff --git a/mtp/btree.cpp b/mtp/btree.cpp new file mode 100755 index 000000000..7976ac325 --- /dev/null +++ b/mtp/btree.cpp @@ -0,0 +1,308 @@ +/* + * Copyright (C) 2014 TeamWin - bigbiff and Dees_Troy mtp database conversion to C++ + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include +#include "btree.hpp" +#include "MtpDebug.h" + +// Constructor +Tree::Tree() { + root = NULL; + count = 0; +} + +// Destructor +Tree::~Tree() { + freeNode(root); +} + +// Free the node +void Tree::freeNode(Node* leaf) +{ + if ( leaf != NULL ) + { + freeNode(leaf->Left()); + freeNode(leaf->Right()); + delete leaf; + } +} + +int Tree::getCount(void) { + MTPD("node count: %d\n", count); + return count; +} + +Node* Tree::addNode(int mtpid, std::string path) +{ + MTPD("root: %d\n", root); + // No elements. Add the root + if ( root == NULL ) { + Node* n = new Node(); + count++; + MTPD("node count: %d\n", count); + MTPD("adding node address: %d\n", n); + MTPD("adding mtpid: %d\n", mtpid); + n->setMtpid(mtpid); + n->setPath(path); + root = n; + MTPD("set root to %d\n", root); + return n; + } + else { + count++; + MTPD("node count: %d\n", count); + MTPD("adding new child node\n"); + return addNode(mtpid, root, path); + } +} + +// Add a node (private) +Node* Tree::addNode(int mtpid, Node* leaf, std::string path) { + Node* n; + if ( mtpid <= leaf->Mtpid() ) + { + if ( leaf->Left() != NULL ) + return addNode(mtpid, leaf->Left(), path); + else { + n = new Node(); + MTPD("adding mtpid: %d node: %d\n", mtpid, n); + n->setMtpid(mtpid); + n->setPath(path); + n->setParent(leaf); + leaf->setLeft(n); + } + } + else + { + if ( leaf->Right() != NULL ) + return addNode(mtpid, leaf->Right(), path); + else { + n = new Node(); + MTPD("adding mtpid: %d node: %d\n", mtpid, n); + n->setMtpid(mtpid); + n->setPath(path); + n->setParent(leaf); + leaf->setRight(n); + } + } + return n; +} + +void Tree::setMtpParentId(int mtpparentid, Node* node) { + node->setMtpParentId(mtpparentid); +} + +std::string Tree::getPath(Node* node) { + return node->getPath(); +} + +int Tree::getMtpParentId(Node* node) { + return node->getMtpParentId(); +} + +Node* Tree::findNodePath(std::string path, Node* node) { + Node* n; + if ( node == NULL ) { + return NULL; + } + if ( node->getPath().compare(path) == 0 && node->Mtpid() > 0) { + return node; + } + else { + n = findNodePath(path, node->Left()); + if (n) + return n; + n = findNodePath(path, node->Right()); + if (n) + return n; + } + return NULL; +} + +Node* Tree::getNext(Node *node) { + if (node == NULL) + return NULL; + else { + if (node->Left() != NULL) + return node->Left(); + if (node->Right() != NULL) + return node->Right(); + } + return NULL; +} + +Node* Tree::findNode(int key, Node* node) { + //MTPD("key: %d\n", key); + //MTPD("node: %d\n", node); + if ( node == NULL ) { + return NULL; + } + else if ( node->Mtpid() == key ) { + return node; + } + else if ( key <= node->Mtpid() ) { + return findNode(key, node->Left()); + } + else if ( key > node->Mtpid() ) { + return findNode(key, node->Right()); + } + else { + return NULL; + } + return NULL; +} + +void Tree::getmtpids(Node* node, std::vector* mtpids) +{ + if ( node ) + { + MTPD("node: %d\n", node->Mtpid()); + mtpids->push_back(node->Mtpid()); + if (node->Left()) + getmtpids(node->Left(), mtpids); + if (node->Right()) + getmtpids(node->Right(), mtpids); + } else { + mtpids->push_back(0); + } + return; +} + +// Find the node with min key +// Traverse the left sub-tree recursively +// till left sub-tree is empty to get min +Node* Tree::min(Node* node) +{ + if ( node == NULL ) + return NULL; + + if ( node->Left() ) + min(node->Left()); + else + return node; + return NULL; +} + +// Find the node with max key +// Traverse the right sub-tree recursively +// till right sub-tree is empty to get max +Node* Tree::max(Node* node) +{ + if ( node == NULL ) + return NULL; + + if ( node->Right() ) + max(node->Right()); + else + return node; + return NULL; +} + +// Find successor to a node +// Find the node, get the node with max value +// for the right sub-tree to get the successor +Node* Tree::successor(int key, Node *node) +{ + Node* thisKey = findNode(key, node); + if ( thisKey ) + return max(thisKey->Right()); + return NULL; +} + +// Find predecessor to a node +// Find the node, get the node with max value +// for the left sub-tree to get the predecessor +Node* Tree::predecessor(int key, Node *node) +{ + Node* thisKey = findNode(key, node); + if ( thisKey ) + return max(thisKey->Left()); + return NULL; +} + +void Tree::deleteNode(int key) +{ + // Find the node. + Node* thisKey = findNode(key, root); + MTPD("Tree::deleteNode found node: %d\n", thisKey); + MTPD("handle: %d\n", thisKey->Mtpid()); + + if (thisKey == root) { + if (thisKey->Right()) { + root = thisKey->Right(); + root->setParent(NULL); + return; + } + if (thisKey->Left()) { + root = thisKey->Left(); + root->setParent(NULL); + return; + } + root = NULL; + delete thisKey; + return; + } + + if ( thisKey->Left() == NULL && thisKey->Right() == NULL ) + { + if ( thisKey->Mtpid() > thisKey->Parent()->Mtpid() ) { + thisKey->Parent()->setRight(NULL); + } + else { + thisKey->Parent()->setLeft(NULL); + } + delete thisKey; + return; + } + + if ( thisKey->Left() == NULL && thisKey->Right() != NULL ) + { + if ( thisKey->Mtpid() > thisKey->Parent()->Mtpid() ) + thisKey->Parent()->setRight(thisKey->Right()); + else + thisKey->Parent()->setLeft(thisKey->Right()); + thisKey->Right()->setParent(thisKey->Parent()); + delete thisKey; + return; + } + if ( thisKey->Left() != NULL && thisKey->Right() == NULL ) + { + if ( thisKey->Mtpid() > thisKey->Parent()->Mtpid() ) + thisKey->Parent()->setRight(thisKey->Left()); + else + thisKey->Parent()->setLeft(thisKey->Left()); + thisKey->Left()->setParent(thisKey->Parent()); + delete thisKey; + return; + } + + if ( thisKey->Left() != NULL && thisKey->Right() != NULL ) + { + Node* sub = predecessor(thisKey->Mtpid(), thisKey); + if ( sub == NULL ) + sub = successor(thisKey->Mtpid(), thisKey); + + if ( sub->Parent()->Mtpid() <= sub->Mtpid() ) + sub->Parent()->setRight(sub->Right()); + else + sub->Parent()->setLeft(sub->Left()); + + thisKey->setMtpid(sub->Mtpid()); + delete sub; + return; + } +} -- cgit v1.2.3