summaryrefslogtreecommitdiffstats
path: root/mtp/btree.cpp
diff options
context:
space:
mode:
authorthat <github@that.at>2014-10-08 00:01:24 +0200
committerDees Troy <dees_troy@teamw.in>2014-10-08 18:34:39 +0200
commit9e0593eaf6defb15761f41246093c0d3661b140d (patch)
treeb9c42ddb95087c735d50b8ce34b5aee529adc5cb /mtp/btree.cpp
parentUpdate RECOVERY_VARIANT blocking to use project-path-for (diff)
downloadandroid_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.tar
android_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.tar.gz
android_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.tar.bz2
android_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.tar.lz
android_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.tar.xz
android_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.tar.zst
android_bootable_recovery-9e0593eaf6defb15761f41246093c0d3661b140d.zip
Diffstat (limited to 'mtp/btree.cpp')
-rwxr-xr-xmtp/btree.cpp289
1 files changed, 30 insertions, 259 deletions
diff --git a/mtp/btree.cpp b/mtp/btree.cpp
index 7976ac325..3a5648db0 100755
--- a/mtp/btree.cpp
+++ b/mtp/btree.cpp
@@ -20,289 +20,60 @@
#include "MtpDebug.h"
// Constructor
-Tree::Tree() {
- root = NULL;
- count = 0;
+Tree::Tree(MtpObjectHandle handle, MtpObjectHandle parent, const std::string& name)
+ : Node(handle, parent, name), alreadyRead(false) {
}
// Destructor
Tree::~Tree() {
- freeNode(root);
-}
-
-// Free the node
-void Tree::freeNode(Node* leaf)
-{
- if ( leaf != NULL )
- {
- freeNode(leaf->Left());
- freeNode(leaf->Right());
- delete leaf;
- }
+ for (std::map<MtpObjectHandle, Node*>::iterator it = entries.begin(); it != entries.end(); ++it)
+ delete it->second;
}
int Tree::getCount(void) {
+ int count = entries.size();
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());
+void Tree::addEntry(Node* node) {
+ if (node->Mtpid() == 0) {
+ MTPE("Tree::addEntry: not adding node with 0 handle.\n");
+ return;
}
- else {
- return NULL;
+ if (node->Mtpid() == node->getMtpParentId()) {
+ MTPE("Tree::addEntry: not adding node with handle %u == parent.\n", node->Mtpid());
+ return;
}
- return NULL;
+ entries[node->Mtpid()] = node;
}
-void Tree::getmtpids(Node* node, std::vector<int>* mtpids)
-{
- if ( node )
+Node* Tree::findEntryByName(std::string name) {
+ for (std::map<MtpObjectHandle, Node*>::iterator it = entries.begin(); it != entries.end(); ++it)
{
- 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);
+ Node* node = it->second;
+ if (node->getName().compare(name) == 0 && node->Mtpid() > 0)
+ return node;
}
- 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());
+Node* Tree::findNode(MtpObjectHandle handle) {
+ std::map<MtpObjectHandle, Node*>::iterator it = entries.find(handle);
+ if (it != entries.end())
+ return it->second;
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::getmtpids(MtpObjectHandleList* mtpids) {
+ for (std::map<MtpObjectHandle, Node*>::iterator it = entries.begin(); it != entries.end(); ++it)
+ mtpids->push_back(it->second->Mtpid());
}
-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;
+void Tree::deleteNode(MtpObjectHandle handle) {
+ std::map<MtpObjectHandle, Node*>::iterator it = entries.find(handle);
+ if (it != entries.end()) {
+ delete it->second;
+ entries.erase(it);
}
}