X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/56b4eba70b4efa0149bab92cfbe5e83ecfa5524b..a4c2bc5e5d6b2a6cfdae3ae0159535deaacd28f4:/src/btree.cpp diff --git a/src/btree.cpp b/src/btree.cpp index 1bbb755..a063bef 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -1,8 +1,9 @@ #include "btree.h" -BTree::BTree (const std::string &name, unsigned int block_size, bool create_new_file) +BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool create_new_file) { + key_type = kt; uchar *node; BTreeNodeHeader nh; @@ -44,14 +45,15 @@ void BTree::WriteFileHeader () 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; - Clave *kout = AddKeyR (&k, 0, left, right); + Clave *kout = AddKeyR (k.Clone (), 0, left, right); if (kout) { unsigned short level; @@ -70,6 +72,7 @@ void BTree::AddKey (const Clave &k) WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); WriteBlock (node, left); + DeleteKeys (node_keys); delete [] node; /* Leo y actualizo la Raiz */ @@ -86,6 +89,8 @@ void BTree::AddKey (const Clave &k) WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); WriteBlock (node, 0); + delete [] node; + DeleteKeys (node_keys); PrintNode (0); } } @@ -131,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); + DeleteKeys (node_keys); + delete [] node; PrintNode (node_num); } else { @@ -207,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); + DeleteKeys (old_node_keys); + DeleteKeys (new_node_keys); PrintNode (node_num); PrintNode (new_node_num); @@ -255,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); } + DeleteKeys (node_keys); /* Nada que hacer */ - if (!k) return NULL; + if (data) delete data; + if (!k) { + delete [] node; + return NULL; + } data = new BTreeData (k->Clone (), right_child); @@ -277,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); + DeleteKeys (node_keys); + delete [] node; PrintNode (node_num); } else { @@ -357,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); + DeleteKeys (old_node_keys); + DeleteKeys (new_node_keys); PrintNode (node_num); PrintNode (new_node_num); @@ -385,9 +403,14 @@ void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header) 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]; - 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; @@ -417,9 +440,9 @@ std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade /* TODO : Detectar si estoy en una hoja */ BTreeData *data; if (node_header.level == 0) { - data = new BTreeLeafData (node); + data = new BTreeLeafData (node, key_type); } else { - data = new BTreeData (node); + data = new BTreeData (node, key_type); } node += data->Size (); keys.push_back (data); @@ -439,7 +462,9 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listToArray(), 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++; @@ -470,6 +495,7 @@ void BTree::PrintNode (uint num) std::cout << std::endl; delete [] node; + DeleteKeys (node_keys); } uchar *BTree::NewBlock (uint &num) @@ -481,7 +507,7 @@ uchar *BTree::NewBlock (uint &num) 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); @@ -494,3 +520,67 @@ uchar *BTree::NewBlock (uint &num) return node; } +bool BTree::FindKey (const Clave &k) +{ + return FindKeyR (&k, 0); +} + +bool BTree::FindKeyR (const Clave *k, uint node_num) +{ + std::list 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::iterator it = node_keys.begin (); + std::list::iterator posterior; + std::list::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 &keys) +{ + std::list::iterator it = keys.begin (); + + while (it != keys.end ()) { + BTreeData *d = (*it); + delete d; + it++; + } +} +