Bugfix : Condición base para cortar la recursividad.

[z.facultad/75.52/treemulator.git] / src / btree.cpp

diff --git a/src/btree.cpp b/src/btree.cpp
index 66f4026fd556508ed1b49c953e08f942c3429544..a063befcafc4d49cfb9b2c5f8fc59e8711a122d5 100644 (file)
--- a/src/btree.cpp
+++ b/src/btree.cpp
@@ -45,14 +45,15 @@ void BTree::WriteFileHeader ()
 
 void BTree::WriteBlock (uchar *block, uint num)
 {
 
 void BTree::WriteBlock (uchar *block, uint num)
 {

-       fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
+       num++;
+       fseek (fp, num*header.block_size, SEEK_SET);

        fwrite (block, 1, header.block_size, fp);
 }
 
 void BTree::AddKey (const Clave &k)
 {
        uint left, right;
        fwrite (block, 1, header.block_size, fp);
 }
 
 void BTree::AddKey (const Clave &k)
 {
        uint left, right;

-       Clave *kout = AddKeyR (&k, 0, left, right);
+       Clave *kout = AddKeyR (k.Clone (), 0, left, right);

 
        if (kout) {
                unsigned short level;
 
        if (kout) {
                unsigned short level;


@@ -71,6 +72,7 @@ void BTree::AddKey (const Clave &k)
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, left);
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, left);

+               DeleteKeys (node_keys);

                delete [] node;
 
                /* Leo y actualizo la Raiz */
                delete [] node;
 
                /* Leo y actualizo la Raiz */


@@ -87,6 +89,8 @@ void BTree::AddKey (const Clave &k)
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, 0);
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, 0);

+               delete [] node;
+               DeleteKeys (node_keys);

                PrintNode (0);
        }
 }
                PrintNode (0);
        }
 }


@@ -132,6 +136,8 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, node_num);
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, node_num);

+               DeleteKeys (node_keys);
+               delete [] node;

 
                PrintNode (node_num);
        } else {
 
                PrintNode (node_num);
        } else {


@@ -208,6 +214,8 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint
                WriteKeys (new_node, new_node_header, new_node_keys);
                WriteNodoHeader (new_node, &new_node_header);
                WriteBlock (new_node, new_node_num);
                WriteKeys (new_node, new_node_header, new_node_keys);
                WriteNodoHeader (new_node, &new_node_header);
                WriteBlock (new_node, new_node_num);

+               DeleteKeys (old_node_keys);
+               DeleteKeys (new_node_keys);

 
                PrintNode (node_num);
                PrintNode (new_node_num);
 
                PrintNode (node_num);
                PrintNode (new_node_num);


@@ -256,9 +264,14 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin
        } else {
                k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child);
        }
        } else {
                k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child);
        }

+       DeleteKeys (node_keys);

 
        /* Nada que hacer */
 
        /* Nada que hacer */

-       if (!k) return NULL;
+       if (data) delete data;
+       if (!k) {
+               delete [] node;
+               return NULL;
+       }

 
        data = new BTreeData (k->Clone (), right_child);
 
 
        data = new BTreeData (k->Clone (), right_child);
 


@@ -278,6 +291,8 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, node_num);
                WriteKeys (node, node_header, node_keys);
                WriteNodoHeader (node, &node_header);
                WriteBlock (node, node_num);

+               DeleteKeys (node_keys);
+               delete [] node;

 
                PrintNode (node_num);
        } else {
 
                PrintNode (node_num);
        } else {


@@ -358,6 +373,8 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin
                WriteKeys (new_node, new_node_header, new_node_keys);
                WriteNodoHeader (new_node, &new_node_header);
                WriteBlock (new_node, new_node_num);
                WriteKeys (new_node, new_node_header, new_node_keys);
                WriteNodoHeader (new_node, &new_node_header);
                WriteBlock (new_node, new_node_num);

+               DeleteKeys (old_node_keys);
+               DeleteKeys (new_node_keys);

 
                PrintNode (node_num);
                PrintNode (new_node_num);
 
                PrintNode (node_num);
                PrintNode (new_node_num);


@@ -386,9 +403,14 @@ void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
 
 uchar *BTree::ReadBlock (uint num)
 {
 
 uchar *BTree::ReadBlock (uint num)
 {

+       /* Como el bloque 0 se usa para el header, el Nodo "num"
+        * está en el bloque "num+1"
+        */
+       num++;
+

        uchar *out = new uchar[header.block_size];
 
        uchar *out = new uchar[header.block_size];
 

-       fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET); 
+       fseek (fp, num*header.block_size, SEEK_SET);    

        fread (out, 1, header.block_size, fp);
 
        return out;
        fread (out, 1, header.block_size, fp);
 
        return out;


@@ -440,7 +462,9 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTre
 
        while (it != keys.end ()) {
                BTreeData *d = (*it);
 
        while (it != keys.end ()) {
                BTreeData *d = (*it);

-               memcpy (node, d->ToArray(), d->Size ());
+               uchar *n = d->ToArray ();
+               memcpy (node, n, d->Size ());
+               delete [] n;

                node += d->Size ();
                node_header.free_space -= d->Size ();
                node_header.item_count++;
                node += d->Size ();
                node_header.free_space -= d->Size ();
                node_header.item_count++;


@@ -471,6 +495,7 @@ void BTree::PrintNode (uint num)
        std::cout << std::endl;
 
        delete [] node;
        std::cout << std::endl;
 
        delete [] node;

+       DeleteKeys (node_keys);

 }
 
 uchar *BTree::NewBlock (uint &num)
 }
 
 uchar *BTree::NewBlock (uint &num)


@@ -482,7 +507,7 @@ uchar *BTree::NewBlock (uint &num)
        fseek (fp, 0, SEEK_END);
        filelen = ftell (fp);
 
        fseek (fp, 0, SEEK_END);
        filelen = ftell (fp);
 

-       num = (filelen - sizeof (BTreeFileHeader))/header.block_size;
+       num = filelen/header.block_size - 1;

 
        node = new uchar[header.block_size];
        ReadNodoHeader (node, &nh);
 
        node = new uchar[header.block_size];
        ReadNodoHeader (node, &nh);


@@ -495,3 +520,67 @@ uchar *BTree::NewBlock (uint &num)
        return node;
 }
 
        return node;
 }
 

+bool BTree::FindKey (const Clave &k)
+{
+       return FindKeyR (&k, 0);
+}
+
+bool BTree::FindKeyR (const Clave *k, uint node_num)
+{
+       std::list<BTreeData *> node_keys;
+       BTreeNodeHeader node_header;
+
+       /* Leo el nodo raiz para empezar a agregar */
+       uchar *node = ReadBlock (node_num);
+       ReadNodoHeader (node, &node_header);
+       node_keys = ReadKeys (node, node_header);
+
+       std::list<BTreeData *>::iterator it = node_keys.begin ();
+       std::list<BTreeData *>::iterator posterior;
+       std::list<BTreeData *>::iterator ultima;
+       
+       /* Se supone que la primera es un hijo :) */
+       BTreeData *lchild;
+       if (node_header.level != 0) {
+               lchild = (*it++);
+       }
+       posterior = it;
+
+       BTreeData *data;
+       if (node_header.level == 0)
+               data = new BTreeLeafData ((Clave *)k);
+       else
+               data = new BTreeData ((Clave *)k, 0);
+
+       while (it != node_keys.end ()) {
+               if ((*data) == (*(*it))) {
+                       /* La encontre!, retorno */
+                       delete [] node;
+                       DeleteKeys (node_keys);
+                       return true;
+               }
+
+               if ((*data) < (*(*it)))
+                       break;
+               ultima = it;
+               it++;
+       }
+
+       /* TODO: Aca faltaria liberar memoria */
+       if (it == posterior)
+               return FindKeyR (k, lchild->getChild ());
+               
+       return FindKeyR (k, (*ultima)->getChild ());
+}
+
+void BTree::DeleteKeys (std::list<BTreeData *> &keys)
+{
+       std::list<BTreeData *>::iterator it = keys.begin ();
+
+       while (it != keys.end ()) {
+               BTreeData *d = (*it);
+               delete d;
+               it++;
+       }
+}
+