X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/6d948f6bdab2bb66cd5eb8046ec67ca9b3ab76c1..89e087a53e76331615252ec4e79830f755dbed6a:/src/btree.cpp diff --git a/src/btree.cpp b/src/btree.cpp index a285392..3027c9a 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -1,12 +1,13 @@ #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; - fp = fopen (name.c_str(), "wb"); + fp = fopen (name.c_str(), "wb+"); if (!fp) { /* TODO : mandar una exception ? */ return; @@ -17,7 +18,7 @@ BTree::BTree (const std::string &name, unsigned int block_size, bool create_new_ /* Inicializo el header */ header.block_size = block_size; - write_tree_header (); + WriteFileHeader (); /* Creo el primer bloque vacio */ node = new uchar[block_size]; @@ -26,7 +27,7 @@ BTree::BTree (const std::string &name, unsigned int block_size, bool create_new_ nh.free_space = block_size - sizeof (BTreeNodeHeader); nh.item_count = 0; WriteNodoHeader (node, &nh); - write_block (node, 0); + WriteBlock (node, 0); delete [] node; } @@ -36,35 +37,859 @@ BTree::~BTree () fclose (fp); } -void BTree::write_tree_header () +void BTree::WriteFileHeader () { fseek (fp, 0L, SEEK_SET); fwrite (&header, 1, sizeof (BTreeFileHeader), fp); } -void BTree::write_block (uchar *block, uint num) +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 (Clave &k) +void BTree::AddKey (const Clave &k) { + uint left, right; + Clave *kout = AddKeyR (k.Clone (), 0, left, right); + + if (kout) { + unsigned short level; + /* Debo dejar la raiz en el nodo 0, por lo que paso el nodo + * que esta usando el hijo izquierdo a un nuevo nodo */ + std::list node_keys; + BTreeNodeHeader node_header; + uchar *node = ReadBlock (left); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + level = node_header.level + 1; + + uchar *new_node = NewBlock (left); + delete [] new_node; /* No me interesa, voy a usar lo leio antes */ + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, left); + DeleteKeys (node_keys); + delete [] node; + + /* Leo y actualizo la Raiz */ + node = ReadBlock (0); + ReadNodoHeader (node, &node_header); + node_keys = std::list(); + + node_keys.push_back (new BTreeChildData (left)); + node_keys.push_back (new BTreeData (kout, right)); + + node_header.level = level; + node_header.item_count = 1; + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, 0); + delete [] node; + DeleteKeys (node_keys); + PrintNode (0); + } +} + +Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child) +{ + uchar *node = ReadBlock (node_num); + BTreeNodeHeader node_header; + ReadNodoHeader (node, &node_header); + delete [] node; + + if (node_header.level == 0) + return AddKeyLeafR (k, node_num, left_child, right_child); + + return AddKeyOtherR (k, node_num, left_child, right_child); +} + +Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child) +{ + Clave *kout = NULL; + std::list node_keys; + + BTreeData *data = new BTreeLeafData (k->Clone ()); + + /* Leo el nodo raiz para empezar a agregar */ + uchar *node = ReadBlock (node_num); + BTreeNodeHeader node_header; + ReadNodoHeader (node, &node_header); + + if (node_header.free_space > data->Size ()) { + BTreeData *datait; + node_keys = ReadKeys (node, node_header); + std::list::iterator it = node_keys.begin (); + + while (it != node_keys.end ()) { + datait = (*it); + if ((*data) < (*datait)) + /* Me pase, lo agrego aca! */ + break; + it++; + } + node_keys.insert (it, data); + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + DeleteKeys (node_keys); + delete [] node; + + PrintNode (node_num); + } else { + /* Split : Creo e inicializo el nuevo nodo */ + std::list new_node_keys; + std::list old_node_keys; + BTreeNodeHeader new_node_header; + uint new_node_num; + uchar *new_node = NewBlock (new_node_num); + ReadNodoHeader (new_node, &new_node_header); + new_node_header.level = node_header.level; + + node_keys = ReadKeys (node, node_header); + new_node_keys = ReadKeys (new_node, new_node_header); + + /* Agrego la clave en la lista que ya tengo de manera ordenada */ + std::list::iterator it = node_keys.begin (); + std::list::iterator previt = node_keys.begin (); + + while (it != node_keys.end ()) { + BTreeData *datait; + datait = (*it); + if ((*data) < (*datait)) + /* Me pase, lo agrego aca! */ + break; + previt = it; + it++; + } + if (it != node_keys.end ()) + node_keys.insert (it, data); + else + node_keys.push_back (data); + + /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo + * y subir la clave del medio */ + node_header.item_count = 0; + node_header.free_space = header.block_size - sizeof (BTreeNodeHeader); + + uint total_size = 0; + it = node_keys.begin (); + while (it != node_keys.end ()) { + BTreeData *datait; + datait = (*it); + total_size += datait->Size (); + it++; + /* Hack : Si me quedo con todas las claves, en el caso de ser + * del mismo tama#o se desbalancea. Hay que ver que efecto + * puede tener en el caso de claves de long. variable + */ + if (it == node_keys.end ()) + total_size -= datait->Size (); + } + + it = node_keys.begin (); + uint used = 0; + while (used < total_size/2) { + BTreeData *d = (*it); + old_node_keys.push_back (d); + used += d->Size (); + it++; + } + kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue + + while (it != node_keys.end ()) { + BTreeData *d = (*it); + new_node_keys.push_back (d); + it++; + } + + /* Guardo */ + WriteKeys (node, node_header, old_node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + 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); + + /* Paso los hijos */ + left_child = node_num; + right_child = new_node_num; + delete [] new_node; + delete [] node; + } + + return kout; +} + +Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child) +{ + Clave *kout = NULL; + std::list node_keys; + + BTreeData *data = new BTreeLeafData (k->Clone ()); + /* Leo el nodo raiz para empezar a agregar */ - uchar *root = ReadBlock (0); - BTreeNodeHeader root_header; - ReadNodoHeader (root, &root_header); + uchar *node = ReadBlock (node_num); + BTreeNodeHeader node_header; + 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 = (*it++); + posterior = it; + + while (it != node_keys.end ()) { + if ((*data) < (*(*it))) + break; + ultima = it; + it++; + } + + if (it == posterior) { + k = AddKeyR (k, lchild->getChild (), left_child, right_child); + } else { + k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child); + } + DeleteKeys (node_keys); + + /* Nada que hacer */ + if (data) delete data; + if (!k) { + delete [] node; + return NULL; + } + + data = new BTreeData (k->Clone (), right_child); + + if (node_header.free_space > data->Size ()) { + BTreeData *datait; + node_keys = ReadKeys (node, node_header); + std::list::iterator it = node_keys.begin (); + + while (it != node_keys.end ()) { + datait = (*it); + if ((*data) < (*datait)) + /* Me pase, lo agrego aca! */ + break; + it++; + } + node_keys.insert (it, data); + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + DeleteKeys (node_keys); + delete [] node; + + PrintNode (node_num); + } else { + /* Split : Creo e inicializo el nuevo nodo */ + std::list new_node_keys; + std::list old_node_keys; + BTreeNodeHeader new_node_header; + uint new_node_num; + uchar *new_node = NewBlock (new_node_num); + ReadNodoHeader (new_node, &new_node_header); + new_node_header.level = node_header.level; + + node_keys = ReadKeys (node, node_header); + new_node_keys = ReadKeys (new_node, new_node_header); + + /* Agrego la clave en la lista que ya tengo de manera ordenada */ + std::list::iterator it = node_keys.begin (); + std::list::iterator previt = node_keys.begin (); + + previt = ++it; + + while (it != node_keys.end ()) { + BTreeData *datait; + datait = (*it); + if ((*data) < (*datait)) + /* Me pase, lo agrego aca! */ + break; + previt = it; + it++; + } + if (it != node_keys.end ()) + node_keys.insert (it, data); + else + node_keys.push_back (data); + + /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo + * y subir la clave del medio */ + node_header.item_count = 0; + node_header.free_space = header.block_size - sizeof (BTreeNodeHeader); + + uint total_size = 0; + it = node_keys.begin (); + while (it != node_keys.end ()) { + BTreeData *datait; + datait = (*it); + total_size += datait->Size (); + it++; + /* Hack : Si me quedo con todas las claves, en el caso de ser + * del mismo tama#o se desbalancea. Hay que ver que efecto + * puede tener en el caso de claves de long. variable + */ + if (it == node_keys.end ()) + total_size -= datait->Size (); + } + + it = node_keys.begin (); + uint used = 0; + while (used < total_size/2) { + BTreeData *d = (*it); + old_node_keys.push_back (d); + used += d->Size (); + it++; + } + kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue + + new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ())); + it++; + while (it != node_keys.end ()) { + BTreeData *d = (*it); + new_node_keys.push_back (d); + it++; + } + + /* Guardo */ + WriteKeys (node, node_header, old_node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + 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); + + /* Paso los hijos */ + left_child = node_num; + right_child = new_node_num; + delete [] new_node; + delete [] node; + } + + return kout; +} + +void BTree::DelKey (const Clave &k) +{ + std::string s = k; + std::cout << "========= Borrando " << s << " =================\n"; + DelKeyR (new BTreeLeafData (k.Clone ()), 0, 0); +} + +void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre) +{ + std::list node_keys; + BTreeNodeHeader node_header; + uchar *node; + + node = ReadBlock (node_num); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + std::list::iterator it = node_keys.begin (); + std::list::iterator ultima; + std::list::iterator posterior; + + BTreeData *lchild; + if (node_header.level != 0) { + lchild = (*it++); + } + posterior = it; + + while (it != node_keys.end ()) { + if ((*k) == (*(*it))) { + /* La encontre!, retorno */ + if (node_header.level == 0) { + DelKeyFromLeaf (k->getClave (), node_num, padre); + } else { + uint left, right; + if (it == posterior) { + left = lchild->getChild (); + right = (*it)->getChild (); + } else { + 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); + } + return; + } + + if ((*k) < (*(*it))) + break; + ultima = it; + it++; + } + + /* Si llego aca y estoy en nivel 0 (una hoja) quiere + * decir que no lo encontre + */ + if (node_header.level == 0) { + std::cout << "*** Clave no encontrada ***\n"; + return; + } + + /* TODO: Aca faltaria liberar memoria */ + if (it == posterior) { + DelKeyR (k, lchild->getChild (), node_num); + } else { + DelKeyR (k, (*ultima)->getChild (), node_num); + } +} + +void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre) +{ + BTreeData *data; + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (node_num); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + data = new BTreeLeafData (k); + + std::list::iterator it; + it = node_keys.begin (); + while (it != node_keys.end ()) { + if ((*data) == (*(*it))) { + node_keys.erase (it); + break; + } + it++; + } + + 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); + + /* Veo si se cumple la condición de minimalidad */ + 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; + + FindBrothers (node_num, padre, hi, hd); + + if ((pedida = GetKey (hi, 1)) != NULL) { + std::string s = *pedida; + std::cout << "Clave Pedida : " << s << std::endl; + + pedida = ReplaceKeyInFather (node_num, padre, pedida); + + node_keys.insert (node_keys.begin (), new BTreeLeafData (pedida)); + } else if ((pedida = GetKey (hd, 0)) != NULL) { + std::string s = *pedida; + std::cout << "Clave Pedida : " << s << std::endl; + + pedida = ReplaceKeyInFather (node_num, padre, pedida); + + node_keys.push_back (new BTreeLeafData (pedida)); + } else { + 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; + } + + JoinNodes (join1, join2, padre); + return; + } + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + } + + DeleteKeys (node_keys); + delete [] node; + std::cout << "Borrado de una hoja listo\n"; +} + +void BTree::JoinNodes (uint node1, uint node2, uint padre) +{ + uchar *n1, *n2, *npadre; + BTreeNodeHeader nh1, nh2, nhp; + std::list nk1, nk2, nkpadre; + + /* Leo los nodos */ + n1 = ReadBlock (node1); + n2 = ReadBlock (node2); + npadre = ReadBlock (padre); + + ReadNodoHeader (n1, &nh1); + 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; + 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; + 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); + } + it++; + sig = it; + + std::list newkeys; + std::list::iterator i; + + i = nk1.begin (); + while (i != nk1.end ()) { + newkeys.push_back ( new BTreeLeafData ((*i)->getClave ()->Clone ())); + i++; + } + if (cpadre) + newkeys.push_back ( new BTreeLeafData (cpadre->Clone ())); + i = nk2.begin (); + while (i != nk2.end ()) { + newkeys.push_back ( new BTreeLeafData ((*i)->getClave ()->Clone ())); + i++; + } + + 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);*/ - if (root_header.free_space >= k.Size ()) { - std::cout << "Hay lugar para meter la clave" << std::endl; + /* TODO: Recuperar nodo1 y nodo2 */ +// } else { + WriteKeys (n1, nh1, newkeys); + WriteNodoHeader (n1, &nh1); + WriteBlock (n1, node1); + + /* 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); + DeleteKeys (nkpadre); + DeleteKeys (newkeys); + + delete [] n1; + delete [] n2; + delete [] npadre; +} + +Clave *BTree::GetKey (uint node_num, char maxmin) +{ + if (node_num == 0) { + std::cout << "Nodo no me puede prestar ... es NULL\n"; + return NULL; + } + + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (node_num); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + std::list::iterator it = node_keys.begin (); + + if (node_header.level != 0) it++; + + Clave *k; + 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); + DeleteKeys (node_keys); + + delete [] node; + + return NULL; + } + + if (maxmin == 0) { + k = (*it)->getClave ()->Clone (); + node_keys.erase (it); + } else { + it = node_keys.end (); + it--; + k = (*it)->getClave ()->Clone (); + node_keys.erase (it); + } + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, node_num); + DeleteKeys (node_keys); + + delete [] node; + + return k; +} + +void BTree::FindBrothers (uint node_num, uint padre, uint &left, uint &right) +{ + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (padre); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + std::list::iterator it = node_keys.begin (); + std::list::iterator anterior = node_keys.begin (); + std::list::iterator siguiente; + + BTreeData *lchild = (*it++); + + 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 (); + return; + } + + while (it != node_keys.end ()) { + if ((*it)->getChild () == node_num) + break; + anterior = it; + it++; + } + siguiente = it++; + + 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; } else { - std::cout << "__NO__ hay lugar para meter la clave" << std::endl; + right = 0; + std::cout << "Hermano Derecho : NO TENGO" << std::endl; + } +} + +Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k) +{ + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (padre); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + std::list::iterator it = node_keys.begin (); + std::list::iterator anterior = node_keys.begin (); + std::list::iterator siguiente; + + BTreeData *lchild = (*it++); + + if (lchild->getChild () == node_num) { + Clave *ret = (*it)->getClave (); + (*it)->setClave (k); + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, padre); + DeleteKeys (node_keys); + + delete [] node; + return ret; + } + + while (it != node_keys.end ()) { + if ((*it)->getChild () == node_num) + break; + anterior = it; + it++; } - delete [] root; + Clave *ret = (*it)->getClave (); + (*it)->setClave (k); + + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, padre); + DeleteKeys (node_keys); + + delete [] node; + return ret; } -void BTree::DelKey (Clave &k) {} +void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right) +{ + uint padre_hijo; + uchar *node; + BTreeNodeHeader node_header; + std::list node_keys; + + node = ReadBlock (padre); + ReadNodoHeader (node, &node_header); + node_keys = ReadKeys (node, node_header); + + if (right != 0) { + std::cout << "Busco para la derecha y luego todo a la izquierda\n"; + uchar *node_r; + BTreeNodeHeader node_hr; + std::list node_keyr; + + /* Busco la clave inmediatamente superior en el arbol */ + padre_hijo = node_num; + do { + node_r = ReadBlock (right); + ReadNodoHeader (node_r, &node_hr); + if (node_hr.level != 0) { + BTreeData *data_r; + node_keyr = ReadKeys (node_r, node_hr); + data_r = *(node_keyr.begin ()); + padre_hijo = right; + right = data_r->getChild (); + + DeleteKeys (node_keyr); + delete [] node_r; + } + } while (node_hr.level != 0); + + std::cout << "Voy a reemplazar en el nodo " << right << std::endl; + + /* Reemplazo la clave a borrar por la de la hoja */ + node_keyr = ReadKeys (node_r, node_hr); + BTreeData *reemplazar = *(node_keyr.begin ()); + + std::string ss = *reemplazar; + std::cout << "Voy a reemplazar por : " << ss << std::endl; + + BTreeData *data = new BTreeLeafData (k->Clone()); + + std::list::iterator it = node_keys.begin (); + while (it != node_keys.end ()) { + 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 ()); + + std::cout << "Tengo todo reemplazado ...\n"; + + /* Grabo los nodos */ + WriteKeys (node, node_header, node_keys); + WriteNodoHeader (node, &node_header); + WriteBlock (node, padre); + DeleteKeys (node_keys); + delete [] node; + + WriteKeys (node_r, node_hr, node_keyr); + WriteNodoHeader (node_r, &node_hr); + WriteBlock (node_r, right); + DeleteKeys (node_keyr); + delete [] node_r; + + std::cout << "Grabe todo en disco ...\n"; + + /* Ahora debo eliminar la clave que puse en el nodo hoja */ + std::cout << "Borro la clave desde la hoja!\n"; + + DelKeyFromLeaf (k, right, padre_hijo); + + 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); + } +} void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header) { @@ -78,11 +903,189 @@ 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; } +std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header) +{ + std::list keys; + node += sizeof (BTreeNodeHeader); + uint count = node_header.item_count; + + if (node_header.item_count == 0) return keys; + + if (node_header.level != 0) { + /* Si no es una hoja, lo primero que tengo es un BTreeChildData */ + BTreeChildData *d = new BTreeChildData (node); + node += d->Size (); + keys.push_back (d); + count--; + } + + for (uint i=0; iSize (); + keys.push_back (data); + } + + return keys; +} + +void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys) +{ + std::list::iterator it = keys.begin (); + + node += sizeof (BTreeNodeHeader); + + node_header.item_count = 0; + node_header.free_space = header.block_size - sizeof (BTreeNodeHeader); + + uint acumulado = 0; + while (it != keys.end ()) { + BTreeData *d = (*it); + uchar *n = d->ToArray (); + acumulado += d->Size (); + //std::cout << "WriteKeys :: Acumulado = " << acumulado << std::endl; + memcpy (node, n, d->Size ()); + delete [] n; + node += d->Size (); + node_header.free_space -= d->Size (); + node_header.item_count++; + it++; + } + + /* TODO : incrementar node_header.item_count aca o fuera de este metodo? */ +} + +void BTree::PrintNode (uint num) +{ + uchar *node = ReadBlock (num); + BTreeNodeHeader node_header; + ReadNodoHeader (node, &node_header); + + std::list node_keys = ReadKeys (node, node_header); + std::list::iterator it = node_keys.begin (); + + std::cout << "Nodo : " << num << std::endl; + std::cout << "Level : " << node_header.level << std::endl; + std::cout << "Items : " << node_header.item_count << std::endl; + std::cout << "Free : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl; + while (it != node_keys.end ()) { + std::string s = *(*it); + std::cout << s << " "; + it++; + } + std::cout << std::endl; + + delete [] node; + DeleteKeys (node_keys); +} + +uchar *BTree::NewBlock (uint &num) +{ + long filelen; + uchar *node; + BTreeNodeHeader nh; + + 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; + nh.free_space = header.block_size - sizeof (BTreeNodeHeader); + nh.item_count = 0; + WriteNodoHeader (node, &nh); + WriteBlock (node, num); + + return node; +} + +BTreeFindResult *BTree::FindKey (const Clave &k) +{ + return FindKeyR (&k, 0); +} + +BTreeFindResult *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); + BTreeFindResult *result = new BTreeFindResult (); + result->node = node_num; + result->header = node_header; + return result; + } + + 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++; + } +}