X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/e8d57487222c69de978d1fd09b6791ae0e4d02ef..eabe0084451a515b80a7fd462c71b4bb2f8dd7bd:/src/btree.cpp diff --git a/src/btree.cpp b/src/btree.cpp index c0e72a3..5b1c36d 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -53,7 +53,7 @@ void BTree::WriteBlock (uchar *block, uint num) void BTree::AddKey (const Clave &k) { uint left, right; - Clave *kout = AddKeyR (k.Clone (), 0, left, right); + Clave *kout = AddKeyR (&k, 0, left, right); if (kout) { unsigned short level; @@ -199,7 +199,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); @@ -260,9 +260,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); @@ -356,9 +356,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); @@ -393,7 +393,9 @@ void BTree::DelKey (const Clave &k) { std::string s = k; std::cout << "========= Borrando " << s << " =================\n"; - DelKeyR (new BTreeLeafData (k.Clone ()), 0, 0); + BTreeData *b = new BTreeLeafData (k.Clone ()); + DelKeyR (b, 0, 0); + delete b; } void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) @@ -420,19 +422,21 @@ 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; return; } @@ -452,9 +456,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); } } @@ -469,13 +473,15 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) ReadNodoHeader (node, &node_header); node_keys = ReadKeys (node, node_header); - data = new BTreeLeafData (k); + data = new BTreeLeafData (k->Clone ()); std::list::iterator it; it = node_keys.begin (); while (it != node_keys.end ()) { if ((*data) == (*(*it))) { + BTreeData *aborrar = (*it); node_keys.erase (it); + delete aborrar; break; } it++; @@ -483,9 +489,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); @@ -530,6 +533,9 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) } JoinNodes (join1, join2, padre, tipoh); + + DeleteKeys (node_keys); + delete [] node; return; } @@ -596,22 +602,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 ()) { @@ -626,14 +632,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++; } @@ -664,7 +670,7 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano) /* TODO : Recuperar node2 */ /* Actualizo punero al padre */ - (*anterior)->setChild (node1); + (*anterior)->SetChild (node1); nkpadre.erase (borrar_padre); WriteKeys (npadre, nhp, nkpadre); @@ -723,12 +729,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); } @@ -758,28 +764,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; @@ -802,9 +808,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); @@ -816,14 +822,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); @@ -861,7 +867,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; @@ -897,8 +903,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"; @@ -975,11 +981,6 @@ std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade } for (uint i=0; i BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade keys.push_back (data); } + DeAbrevKey (keys); return keys; } +void BTree::AbrevKey (std::list &lst) +{ + /* Claves Fijas No se abrevian */ + if (key_type == KEY_FIXED) return; + + BTreeData *primera = NULL; + std::list::iterator it = lst.begin (); + + while (it != lst.end ()) { + if ((*it)->Abrev (primera) == false) + primera = (*it); + it++; + } +} + +void BTree::DeAbrevKey (std::list &lst) +{ + /* Claves Fijas No se abrevian */ + if (key_type == KEY_FIXED) return; + + BTreeData *primera = NULL; + std::list::iterator it = lst.begin (); + + while (it != lst.end ()) { + if ((*it)->DesAbrev (primera) == false) + primera = (*it); + it++; + } +} + void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys) { + AbrevKey (keys); + std::list::iterator it = keys.begin (); node += sizeof (BTreeNodeHeader); @@ -1016,7 +1050,7 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listClone ()); else - data = new BTreeData ((Clave *)k, 0); + data = new BTreeData (k->Clone (), 0); while (it != node_keys.end ()) { if ((*data) == (*(*it))) { /* La encontre!, retorno */ + delete data; delete [] node; DeleteKeys (node_keys); BTreeFindResult *result = new BTreeFindResult (); result->node = node_num; result->header = node_header; + return result; } @@ -1114,11 +1150,27 @@ BTreeFindResult *BTree::FindKeyR (const Clave *k, uint node_num) it++; } + delete data; + + /* Si llego aca y estoy en nivel 0 (una hoja) quiere + * decir que no lo encontré + */ + if (node_header.level == 0) { + DeleteKeys (node_keys); + delete [] node; + return NULL; + } + /* TODO: Aca faltaria liberar memoria */ + BTreeFindResult *ret; if (it == posterior) - return FindKeyR (k, lchild->getChild ()); - - return FindKeyR (k, (*ultima)->getChild ()); + ret = FindKeyR (k, lchild->GetChild ()); + else + ret = FindKeyR (k, (*ultima)->GetChild ()); + + DeleteKeys (node_keys); + delete [] node; + return ret; } void BTree::DeleteKeys (std::list &keys)