X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/3a7aa16a342ce2cca383b3e118d4f41ef1c698a4..04db779a8aee626e80fb2d403cd22c7924babb44:/src/btree.cpp?ds=inline diff --git a/src/btree.cpp b/src/btree.cpp index 7a3daaf..8747177 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -391,6 +391,8 @@ Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uin void BTree::DelKey (const Clave &k) { + std::string s = k; + std::cout << "========= Borrando " << s << " =================\n"; DelKeyR (new BTreeLeafData (k.Clone ()), 0, 0); } @@ -444,7 +446,7 @@ void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) * decir que no lo encontre */ if (node_header.level == 0) { - std::cout << "Clave no encontrada\n"; + std::cout << "*** Clave no encontrada ***\n"; return; } @@ -489,7 +491,8 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) WriteBlock (node, node_num); /* Veo si se cumple la condición de minimalidad */ - if ((node_header.free_space <= ((header.block_size-sizeof(BTreeNodeHeader))/2)) && (node_num != 0)) { + uint min_free = (header.block_size-sizeof(BTreeNodeHeader))/2; + if ((node_header.free_space > min_free) && (node_num != 0)) { /* Oops! Debo pedir prestada clave */ uint hi, hd; Clave *pedida; @@ -513,15 +516,20 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) } else { std::cout << "NADIE ME PUEDE PRESTAR, FUNDIR NODOS\n"; uint join1, join2; + int tipoh; if (hi != 0) { + std::cout << "Join con Hermano Izquierdo\n"; join1 = hi; join2 = node_num; + tipoh = 0; } else { + std::cout << "Join con Hermano Derecho\n"; join1 = node_num; join2 = hd; + tipoh = 1; } - JoinNodes (join1, join2, padre); + JoinNodes (join1, join2, padre, tipoh); return; } @@ -535,12 +543,29 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) std::cout << "Borrado de una hoja listo\n"; } -void BTree::JoinNodes (uint node1, uint node2, uint padre) +void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano) { uchar *n1, *n2, *npadre; BTreeNodeHeader nh1, nh2, nhp; std::list nk1, nk2, nkpadre; + if (node1 == node2) { + std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n"; + exit (1); + } + if (node1 == padre) { + std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n"; + exit (1); + } + if (node2 == padre) { + std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n"; + exit (1); + } + + PrintNode (padre); + PrintNode (node1); + PrintNode (node2); + /* Leo los nodos */ n1 = ReadBlock (node1); n2 = ReadBlock (node2); @@ -550,30 +575,51 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) ReadNodoHeader (n2, &nh2); ReadNodoHeader (npadre, &nhp); + /* Apunto de Unir */ + uint tmp = header.block_size - sizeof (BTreeNodeHeader); + uint l = tmp - nh1.free_space; + l += tmp - nh1.free_space; + l += 4; + + std::cout << "Espacio ocupado despues de unir : " << l << " de " << tmp << std::endl; + nk1 = ReadKeys (n1, nh1); nk2 = ReadKeys (n2, nh2); nkpadre = ReadKeys (npadre, nhp); - /* Busco la clave a juntar con los nodos */ + /* Busco la clave del padre a juntar con los nodos */ std::list::iterator it = nkpadre.begin (); + std::list::iterator borrar_padre; std::list::iterator sig; + std::list::iterator anterior = it; Clave *cpadre; BTreeData *lchild = (*it++); if (lchild->getChild () == node1) { cpadre = (*it)->getClave (); - nkpadre.erase (it); + borrar_padre = it; } else { while (it != nkpadre.end ()) { - if ((*it)->getChild () == node1) - break; + if (tipohermano == 0) { + if ((*it)->getChild () == node2) + break; + } else { + if ((*it)->getChild () == node1) + break; + } + anterior = it; it++; } cpadre = (*it)->getClave (); - nkpadre.erase (it); + borrar_padre = it; + } + if (it == nkpadre.end ()) { + std::cout << "PANIC : Me pase sin encontrar la clave!!\n"; + exit(1); } - sig = it++; + it++; + sig = it; std::list newkeys; std::list::iterator i; @@ -583,7 +629,7 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) newkeys.push_back ( new BTreeLeafData ((*i)->getClave ()->Clone ())); i++; } - if (cpadre) + //if (tipohermano == 0) newkeys.push_back ( new BTreeLeafData (cpadre->Clone ())); i = nk2.begin (); while (i != nk2.end ()) { @@ -591,13 +637,26 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) i++; } - if (padre == 0) { + std::cout << "Espacio ocupado por las nuevas claves : " << (newkeys.size()*4) << std::endl; + if ((newkeys.size()*4) > tmp) { + std::cout << "PANIC : El nodo fundido no entra !!!\n"; + exit (1); + } + + /* Para el padre, tener 2 items significa tener solo 1 clave, ya que + * el otro item es el LeftChild! + */ + if ((padre == 0) && (nhp.item_count == 2)) { + /* Si junte 2 nodos, cuyo padre era la raiz, y esta tenia + * solo una clave, quiere decir que lo que me queda + * es de nuevo solo una raiz con todas las claves + */ nhp.level = 0; WriteKeys (npadre, nhp, newkeys); WriteNodoHeader (npadre, &nhp); WriteBlock (npadre, padre); - /* TODO: Recuperar nodo1 y nodo2 */ + /* TODO: Recuperar nodo1 y nodo2 */ } else { WriteKeys (n1, nh1, newkeys); WriteNodoHeader (n1, &nh1); @@ -605,12 +664,19 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) /* TODO : Recuperar node2 */ /* Actualizo punero al padre */ - (*sig)->setChild (node1); + (*anterior)->setChild (node1); + + nkpadre.erase (borrar_padre); WriteKeys (npadre, nhp, nkpadre); WriteNodoHeader (npadre, &nhp); WriteBlock (npadre, padre); } + std::cout << " ----- Luego de Fundir -----\n"; + PrintNode (node1); + PrintNode (padre); + std::cout << " ---------------------------\n"; + DeleteKeys (nk1); DeleteKeys (nk2); DeleteKeys (nkpadre); @@ -623,7 +689,10 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) Clave *BTree::GetKey (uint node_num, char maxmin) { - if (node_num == 0) return NULL; + if (node_num == 0) { + std::cout << "Nodo no me puede prestar ... es NULL\n"; + return NULL; + } uchar *node; BTreeNodeHeader node_header; @@ -638,8 +707,11 @@ Clave *BTree::GetKey (uint node_num, char maxmin) if (node_header.level != 0) it++; Clave *k; - uint free = node_header.free_space + (*it)->Size (); - if (free > ((header.block_size - sizeof (BTreeNodeHeader))/2)) { + uint free = node_header.free_space; // + (*it)->Size (); + uint min_free = (header.block_size - sizeof (BTreeNodeHeader))/2; + if (free > min_free) { + std::cout << "No puedo prestar : Free = " << free << " Minimo = " << min_free << std::endl; + PrintNode (node_num); WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); WriteBlock (node, node_num); @@ -769,7 +841,7 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint BTreeNodeHeader node_header; std::list node_keys; - node = ReadBlock (padre); + node = ReadBlock (node_num); ReadNodoHeader (node, &node_header); node_keys = ReadKeys (node, node_header); @@ -809,11 +881,22 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint std::list::iterator it = node_keys.begin (); while (it != node_keys.end ()) { + std::string ss1, ss2; + ss1 = *data; + ss2 = *(*it); + std::cout << ss1 << " == " << ss2 << std::endl; if ((*data) == (*(*it))) { break; } it++; } + if (it == node_keys.end ()) { + std::cout << "PANIC : No encontre la clave en el nodo!!!!\n"; + std::string s = *data; + std::cout << s << std::endl; + PrintNode (node_num); + exit (1); + } (*it)->setClave (reemplazar->getClave ()); reemplazar->setClave (k->Clone ()); @@ -822,7 +905,7 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint /* Grabo los nodos */ WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); - WriteBlock (node, padre); + WriteBlock (node, node_num); DeleteKeys (node_keys); delete [] node; @@ -833,7 +916,8 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint delete [] node_r; std::cout << "Grabe todo en disco ...\n"; - + PrintNode (node_num); + PrintNode (right); /* Ahora debo eliminar la clave que puse en el nodo hoja */ std::cout << "Borro la clave desde la hoja!\n"; @@ -841,8 +925,11 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint std::cout << "Listo, Listo!\n"; } else if (left != 0) { + std::cout << "PANIC : Deberia poder reemplazar en la derecha!!!!!\n"; + exit (1); } else { std::cout << "PANIC : No tengo hijos para reemplazar!!!!\n"; + exit (1); } } @@ -903,11 +990,44 @@ std::list 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); @@ -915,9 +1035,12 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listToArray (); + acumulado += d->Size (); + //std::cout << "WriteKeys :: Acumulado = " << acumulado << std::endl; memcpy (node, n, d->Size ()); delete [] n; node += d->Size (); @@ -926,7 +1049,7 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list