X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/a7b40a39a402b6f4cbcf1b1a175c0e357704d43f..baff628083af0bab49fafdab5ed0445a6407f2de:/src/btree.cpp?ds=sidebyside diff --git a/src/btree.cpp b/src/btree.cpp index 874133c..2701b3a 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -1,9 +1,8 @@ #include "btree.h" -BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool create_new_file) +BTree::BTree (const std::string &name, unsigned int block_size, int tt, int kt, bool create_new_file) { - key_type = kt; uchar *node; BTreeNodeHeader nh; @@ -18,6 +17,11 @@ BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool cre /* Inicializo el header */ header.block_size = block_size; + header.tree_type = tt; + header.key_type = kt; + header.block_data_counter = 0; + strcpy (header.magic, "DILUMA"); + header.magic[6] = '\0'; WriteFileHeader (); /* Creo el primer bloque vacio */ @@ -32,9 +36,88 @@ BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool cre delete [] node; } +BTree* BTree::Open (const std::string &name) +{ + /* Leo los bloques recuperables */ + FILE *fp; + BTree *tree = new BTree (); + + std::string del = name + ".del"; + + fp = fopen (del.c_str (), "wb"); + if (fp != NULL) { + uint i; + + while (fread (&i, 1, sizeof (uint), fp)) { + tree->deleted_nodes.push_back (i); + } + + fclose (fp); + } + + del = name + ".blockdel"; + + fp = fopen (del.c_str (), "wb"); + if (fp != NULL) { + uint i; + + while (fread (&i, 1, sizeof (uint), fp)) { + tree->deleted_block_data.push_back (i); + } + + fclose (fp); + } + + tree->filename = name; + tree->fp = fopen (name.c_str(), "rb+"); + if (!fp) { + /* TODO : mandar una exception ? */ + delete tree; + return NULL; + } + tree->ReadFileHeader (); + + if (strcmp ("DILUMA", tree->header.magic)) { + /* Arbol no tiene magic!! */ + delete tree; + return NULL; + } + + return tree; +} + BTree::~BTree () { fclose (fp); + + std::string del = filename + ".del"; + + fp = fopen (del.c_str (), "wb"); + std::list::iterator it = deleted_nodes.begin (); + + while (it != deleted_nodes.end ()) { + uint i = *it; + fwrite (&i, 1, sizeof (uint), fp); + it++; + } + + del = filename + ".del"; + + fp = fopen (del.c_str (), "wb"); + it = deleted_block_data.begin (); + + while (it != deleted_block_data.end ()) { + uint i = *it; + fwrite (&i, 1, sizeof (uint), fp); + it++; + } + fclose (fp); +} + +void BTree::ReadFileHeader () +{ + fseek (fp, 0L, SEEK_SET); + fread (&header, 1, sizeof (BTreeFileHeader), fp); } void BTree::WriteFileHeader () @@ -53,7 +136,18 @@ void BTree::WriteBlock (uchar *block, uint num) void BTree::AddKey (const Clave &k) { uint left, right; - Clave *kout = AddKeyR (&k, 0, left, right); + Clave *kout, *in; + + in = k.Clone (); + in->SetBlockData ( GetNextBlockData () ); + + try { + kout = AddKeyR (in->Clone (), 0, left, right); + } catch (Exception *e) { + throw e; + } + + delete in; if (kout) { unsigned short level; @@ -102,10 +196,19 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri ReadNodoHeader (node, &node_header); delete [] node; - if (node_header.level == 0) - return AddKeyLeafR (k, node_num, left_child, right_child); + if (node_header.level == 0) { + try { + return AddKeyLeafR (k, node_num, left_child, right_child); + } catch (Exception *e) { + throw e; + } + } - return AddKeyOtherR (k, node_num, left_child, right_child); + try { + return AddKeyOtherR (k, node_num, left_child, right_child); + } catch (Exception *e) { + throw e; + } } Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child) @@ -127,6 +230,14 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint while (it != node_keys.end ()) { datait = (*it); + if (header.tree_type == TYPE_IDENTIFICACION) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } + if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -160,6 +271,13 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint while (it != node_keys.end ()) { BTreeData *datait; datait = (*it); + if (header.tree_type == TYPE_IDENTIFICACION) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -199,7 +317,7 @@ Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint used += d->Size (); it++; } - kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue + kout = (*it++)->GetKey (); // Esta se retorna al "padre" para que se la agregue while (it != node_keys.end ()) { BTreeData *d = (*it); @@ -253,6 +371,13 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin posterior = it; while (it != node_keys.end ()) { + if (header.tree_type == TYPE_IDENTIFICACION) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*(*it))) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*(*it))) break; ultima = it; @@ -260,9 +385,9 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin } if (it == posterior) { - k = AddKeyR (k, lchild->getChild (), left_child, right_child); + k = AddKeyR (k, lchild->GetChild (), left_child, right_child); } else { - k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child); + k = AddKeyR (k, (*ultima)->GetChild (), left_child, right_child); } DeleteKeys (node_keys); @@ -282,6 +407,13 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin while (it != node_keys.end ()) { datait = (*it); + if (header.tree_type == TYPE_IDENTIFICACION) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -317,6 +449,13 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin while (it != node_keys.end ()) { BTreeData *datait; datait = (*it); + if (header.tree_type == TYPE_IDENTIFICACION) { + /* Verifico que la clave no existea ya en el arbol */ + if ((*data) == (*datait)) { + throw new AddException (); + return NULL; + } + } if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; @@ -356,9 +495,9 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin used += d->Size (); it++; } - kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue + kout = (*it)->GetKey (); // Esta se retorna al "padre" para que se la agregue - new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ())); + new_node_keys.push_back ( new BTreeChildData ((*it)->GetChild ())); it++; while (it != node_keys.end ()) { BTreeData *d = (*it); @@ -422,18 +561,18 @@ void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) if ((*k) == (*(*it))) { /* La encontre!, retorno */ if (node_header.level == 0) { - DelKeyFromLeaf (k->getClave (), node_num, padre); + DelKeyFromLeaf (k->GetKey (), node_num, padre); } else { uint left, right; if (it == posterior) { - left = lchild->getChild (); - right = (*it)->getChild (); + left = lchild->GetChild (); + right = (*it)->GetChild (); } else { - left = (*ultima)->getChild (); - right = (*it)->getChild (); + left = (*ultima)->GetChild (); + right = (*it)->GetChild (); } std::cout << "Eliminar de Nodo con hijos : " << left << " y " << right << std::endl; - DelKeyFromNode (k->getClave (), node_num, padre, left, right); + DelKeyFromNode (k->GetKey (), node_num, padre, left, right); } DeleteKeys (node_keys); delete [] node; @@ -456,9 +595,9 @@ void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) /* TODO: Aca faltaria liberar memoria */ if (it == posterior) { - DelKeyR (k, lchild->getChild (), node_num); + DelKeyR (k, lchild->GetChild (), node_num); } else { - DelKeyR (k, (*ultima)->getChild (), node_num); + DelKeyR (k, (*ultima)->GetChild (), node_num); } } @@ -481,6 +620,7 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) if ((*data) == (*(*it))) { BTreeData *aborrar = (*it); node_keys.erase (it); + deleted_block_data.push_back (aborrar->GetKey ()->GetBlockData ()); delete aborrar; break; } @@ -489,9 +629,6 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) delete data; - /* TODO : que pasa cuando el nodo se queda vacio o con - * muy pocas claveS?? - */ WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); WriteBlock (node, node_num); @@ -605,22 +742,22 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano) Clave *cpadre; BTreeData *lchild = (*it++); - if (lchild->getChild () == node1) { - cpadre = (*it)->getClave (); + if (lchild->GetChild () == node1) { + cpadre = (*it)->GetKey (); borrar_padre = it; } else { while (it != nkpadre.end ()) { if (tipohermano == 0) { - if ((*it)->getChild () == node2) + if ((*it)->GetChild () == node2) break; } else { - if ((*it)->getChild () == node1) + if ((*it)->GetChild () == node1) break; } anterior = it; it++; } - cpadre = (*it)->getClave (); + cpadre = (*it)->GetKey (); borrar_padre = it; } if (it == nkpadre.end ()) { @@ -635,14 +772,14 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano) i = nk1.begin (); while (i != nk1.end ()) { - newkeys.push_back ( new BTreeLeafData ((*i)->getClave ()->Clone ())); + newkeys.push_back ( new BTreeLeafData ((*i)->GetKey ()->Clone ())); i++; } //if (tipohermano == 0) newkeys.push_back ( new BTreeLeafData (cpadre->Clone ())); i = nk2.begin (); while (i != nk2.end ()) { - newkeys.push_back ( new BTreeLeafData ((*i)->getClave ()->Clone ())); + newkeys.push_back ( new BTreeLeafData ((*i)->GetKey ()->Clone ())); i++; } @@ -665,15 +802,17 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano) WriteNodoHeader (npadre, &nhp); WriteBlock (npadre, padre); - /* TODO: Recuperar nodo1 y nodo2 */ + deleted_nodes.push_back (node1); + deleted_nodes.push_back (node2); } else { WriteKeys (n1, nh1, newkeys); WriteNodoHeader (n1, &nh1); WriteBlock (n1, node1); - /* TODO : Recuperar node2 */ + deleted_nodes.push_back (node2); + /* Actualizo punero al padre */ - (*anterior)->setChild (node1); + (*anterior)->SetChild (node1); nkpadre.erase (borrar_padre); WriteKeys (npadre, nhp, nkpadre); @@ -732,12 +871,12 @@ Clave *BTree::GetKey (uint node_num, char maxmin) } if (maxmin == 0) { - k = (*it)->getClave ()->Clone (); + k = (*it)->GetKey ()->Clone (); node_keys.erase (it); } else { it = node_keys.end (); it--; - k = (*it)->getClave ()->Clone (); + k = (*it)->GetKey ()->Clone (); node_keys.erase (it); } @@ -767,28 +906,28 @@ void BTree::FindBrothers (uint node_num, uint padre, uint &left, uint &right) BTreeData *lchild = (*it++); - if (lchild->getChild () == node_num) { + if (lchild->GetChild () == node_num) { /* Solo tengo hermano derecho */ std::cout << "Hermano Izquierdo : NO TENGO" << std::endl; left = 0; - std::cout << "Hermano Derecho : " << (*it)->getChild () << std::endl; - right = (*it)->getChild (); + std::cout << "Hermano Derecho : " << (*it)->GetChild () << std::endl; + right = (*it)->GetChild (); return; } while (it != node_keys.end ()) { - if ((*it)->getChild () == node_num) + if ((*it)->GetChild () == node_num) break; anterior = it; it++; } siguiente = it++; - std::cout << "Hermano Izquierdo : " << (*anterior)->getChild () << std::endl; - left = (*anterior)->getChild (); + std::cout << "Hermano Izquierdo : " << (*anterior)->GetChild () << std::endl; + left = (*anterior)->GetChild (); if (siguiente != node_keys.end ()) { - right = (*siguiente)->getChild (); - std::cout << "Hermano Derecho : " << (*siguiente)->getChild () << std::endl; + right = (*siguiente)->GetChild (); + std::cout << "Hermano Derecho : " << (*siguiente)->GetChild () << std::endl; } else { right = 0; std::cout << "Hermano Derecho : NO TENGO" << std::endl; @@ -811,9 +950,9 @@ Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k) BTreeData *lchild = (*it++); - if (lchild->getChild () == node_num) { - Clave *ret = (*it)->getClave (); - (*it)->setClave (k); + if (lchild->GetChild () == node_num) { + Clave *ret = (*it)->GetKey (); + (*it)->SetKey (k); WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); @@ -825,14 +964,14 @@ Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k) } while (it != node_keys.end ()) { - if ((*it)->getChild () == node_num) + if ((*it)->GetChild () == node_num) break; anterior = it; it++; } - Clave *ret = (*it)->getClave (); - (*it)->setClave (k); + Clave *ret = (*it)->GetKey (); + (*it)->SetKey (k); WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); @@ -870,7 +1009,7 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint node_keyr = ReadKeys (node_r, node_hr); data_r = *(node_keyr.begin ()); padre_hijo = right; - right = data_r->getChild (); + right = data_r->GetChild (); DeleteKeys (node_keyr); delete [] node_r; @@ -906,8 +1045,8 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint PrintNode (node_num); exit (1); } - (*it)->setClave (reemplazar->getClave ()); - reemplazar->setClave (k->Clone ()); + (*it)->SetKey (reemplazar->GetKey ()); + reemplazar->SetKey (k->Clone ()); std::cout << "Tengo todo reemplazado ...\n"; @@ -984,16 +1123,11 @@ std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade } for (uint i=0; iSize (); keys.push_back (data); @@ -1006,7 +1140,7 @@ std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade void BTree::AbrevKey (std::list &lst) { /* Claves Fijas No se abrevian */ - if (key_type == KEY_FIXED) return; + if (header.key_type == KEY_FIXED) return; BTreeData *primera = NULL; std::list::iterator it = lst.begin (); @@ -1021,7 +1155,7 @@ void BTree::AbrevKey (std::list &lst) void BTree::DeAbrevKey (std::list &lst) { /* Claves Fijas No se abrevian */ - if (key_type == KEY_FIXED) return; + if (header.key_type == KEY_FIXED) return; BTreeData *primera = NULL; std::list::iterator it = lst.begin (); @@ -1091,11 +1225,18 @@ uchar *BTree::NewBlock (uint &num) uchar *node; BTreeNodeHeader nh; - fseek (fp, 0, SEEK_END); - filelen = ftell (fp); + std::list::iterator it; - num = filelen/header.block_size - 1; + if (deleted_nodes.size ()) { + it = deleted_nodes.begin (); + num = *it; + deleted_nodes.erase (it); + } else { + fseek (fp, 0, SEEK_END); + filelen = ftell (fp); + num = filelen/header.block_size - 1; + } node = new uchar[header.block_size]; ReadNodoHeader (node, &nh); nh.level = 0; @@ -1172,9 +1313,9 @@ BTreeFindResult *BTree::FindKeyR (const Clave *k, uint node_num) /* TODO: Aca faltaria liberar memoria */ BTreeFindResult *ret; if (it == posterior) - ret = FindKeyR (k, lchild->getChild ()); + ret = FindKeyR (k, lchild->GetChild ()); else - ret = FindKeyR (k, (*ultima)->getChild ()); + ret = FindKeyR (k, (*ultima)->GetChild ()); DeleteKeys (node_keys); delete [] node; @@ -1191,3 +1332,23 @@ void BTree::DeleteKeys (std::list &keys) it++; } } + +int BTree::type () const +{ + return header.key_type; +} + +uint BTree::GetNextBlockData () +{ + uint n; + if (deleted_block_data.size ()) { + std::list::iterator it = deleted_block_data.begin (); + n = *it; + deleted_block_data.erase (it); + } else { + n = header.block_data_counter++; + } + + return n; +} +