add mtp responder to TWRP.
Big thanks to Dees_Troy for helping with the implementation.
Change-Id: I6c9c522b9c9de5dc139e2ecb0141008182ba07f0
diff --git a/mtp/btree.cpp b/mtp/btree.cpp
new file mode 100755
index 0000000..7976ac3
--- /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 <iostream>
+#include <utils/threads.h>
+#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<int>* 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;
+ }
+}