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);
 	}
 }