From 9e0593eaf6defb15761f41246093c0d3661b140d Mon Sep 17 00:00:00 2001 From: that Date: Wed, 8 Oct 2014 00:01:24 +0200 Subject: mtp: cleanup, fixes and performance improvements - use std::map instead of linked list - read directories on demand - fix writing zip files to storage root - fix creating directories - lots of minor fixes - simplify generation of storage IDs and make them spec compliant Change-Id: I2137c27549ddbdc58466f2e3aeda464fac70a3c5 --- mtp/btree.cpp | 289 ++++++---------------------------------------------------- 1 file changed, 30 insertions(+), 259 deletions(-) (limited to 'mtp/btree.cpp') 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::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* mtpids) -{ - if ( node ) +Node* Tree::findEntryByName(std::string name) { + for (std::map::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::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::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::iterator it = entries.find(handle); + if (it != entries.end()) { + delete it->second; + entries.erase(it); } } -- cgit v1.2.3