X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/3a7aa16a342ce2cca383b3e118d4f41ef1c698a4..89e087a53e76331615252ec4e79830f755dbed6a:/src/btree.cpp diff --git a/src/btree.cpp b/src/btree.cpp index 7a3daaf..3027c9a 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; @@ -514,9 +517,11 @@ void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) std::cout << "NADIE ME PUEDE PRESTAR, FUNDIR NODOS\n"; uint join1, join2; if (hi != 0) { + std::cout << "Join con Hermano Izquierdo\n"; join1 = hi; join2 = node_num; } else { + std::cout << "Join con Hermano Derecho\n"; join1 = node_num; join2 = hd; } @@ -550,12 +555,21 @@ 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 */ std::list::iterator it = nkpadre.begin (); + std::list::iterator borrar_padre; std::list::iterator sig; Clave *cpadre; @@ -563,7 +577,8 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) if (lchild->getChild () == node1) { cpadre = (*it)->getClave (); - nkpadre.erase (it); + //nkpadre.erase (it); + borrar_padre = it; } else { while (it != nkpadre.end ()) { if ((*it)->getChild () == node1) @@ -571,9 +586,15 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) it++; } cpadre = (*it)->getClave (); - nkpadre.erase (it); + //nkpadre.erase (it); + borrar_padre = it; } - sig = it++; + if (it == nkpadre.end ()) { + std::cout << "PANIC : Me pase sin encontrar la clave!!\n"; + exit(1); + } + it++; + sig = it; std::list newkeys; std::list::iterator i; @@ -591,14 +612,20 @@ 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); + } + +/* if (padre == 0) { nhp.level = 0; WriteKeys (npadre, nhp, newkeys); WriteNodoHeader (npadre, &nhp); - WriteBlock (npadre, padre); + WriteBlock (npadre, padre);*/ - /* TODO: Recuperar nodo1 y nodo2 */ - } else { + /* TODO: Recuperar nodo1 y nodo2 */ +// } else { WriteKeys (n1, nh1, newkeys); WriteNodoHeader (n1, &nh1); WriteBlock (n1, node1); @@ -606,10 +633,12 @@ void BTree::JoinNodes (uint node1, uint node2, uint padre) /* TODO : Recuperar node2 */ /* Actualizo punero al padre */ (*sig)->setChild (node1); + + nkpadre.erase (borrar_padre); WriteKeys (npadre, nhp, nkpadre); WriteNodoHeader (npadre, &nhp); WriteBlock (npadre, padre); - } + //} DeleteKeys (nk1); DeleteKeys (nk2); @@ -623,7 +652,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 +670,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); @@ -814,6 +849,13 @@ void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint } 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 ()); @@ -841,8 +883,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); } } @@ -915,9 +960,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 ();