X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/52d9e098f15ad0ca70f11b4549f3d55f55a22a83..aaa9a007ee4af6b40d2eefef15bccc51f92e17d9:/src/btree.cpp diff --git a/src/btree.cpp b/src/btree.cpp index 81b2fc9..ae98139 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -1,8 +1,9 @@ #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; @@ -51,45 +52,236 @@ 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 = AddKeyR (k.Clone (), 0, left, right); if (kout) { - std::cout << "Raiz fue spliteada!!" << std::endl; + 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; + std::list node_keys; - BTreeLeafData data (k->Clone ()); + 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.level != 0) { - /* No estoy en una hoja, asi que tengo que buscar - * para donde moverme para agregar la clave - */ - /* TODO :) */ + 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 *node = ReadBlock (node_num); + BTreeNodeHeader node_header; + ReadNodoHeader (node, &node_header); + + node_keys = ReadKeys (node, node_header); - /* Estoy en una hoja, veo si lo puedo agregar */ + 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; + } - if (node_header.free_space > data.Size ()) { - /* TODO : Insertar ordenado */ - BTreeData datait; + 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 (); + std::list::iterator it = node_keys.begin (); while (it != node_keys.end ()) { datait = (*it); - if (data < datait) + if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; it++; @@ -98,30 +290,36 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri WriteKeys (node, node_header, node_keys); WriteNodoHeader (node, &node_header); WriteBlock (node, node_num); + DeleteKeys (node_keys); + delete [] node; PrintNode (node_num); } else { - std::cout << "=============== SPLIT ================" << std::endl; /* Split : Creo e inicializo el nuevo nodo */ - std::list new_node_keys; - std::list old_node_keys; + 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 it = node_keys.begin (); + std::list::iterator previt = node_keys.begin (); + previt = ++it; + while (it != node_keys.end ()) { - BTreeData datait; + BTreeData *datait; datait = (*it); - if (data < datait) + if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; + previt = it; it++; } if (it != node_keys.end ()) @@ -137,30 +335,32 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri uint total_size = 0; it = node_keys.begin (); while (it != node_keys.end ()) { - BTreeData datait; + BTreeData *datait; datait = (*it); - total_size += datait.Size (); + 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 (); + total_size -= datait->Size (); } it = node_keys.begin (); uint used = 0; while (used < total_size/2) { - BTreeData d = (*it); - std::cout << used << " " << total_size << std::endl; + BTreeData *d = (*it); old_node_keys.push_back (d); - used += d.Size (); + used += d->Size (); it++; } - kout = (*it++).getClave (); // Esta se retorna al "padre" para que se la agregue + 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); + BTreeData *d = (*it); new_node_keys.push_back (d); it++; } @@ -172,6 +372,8 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri 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); @@ -208,32 +410,44 @@ uchar *BTree::ReadBlock (uint num) return out; } -std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header) +std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header) { - std::list keys; + std::list keys; node += sizeof (BTreeNodeHeader); + uint count = node_header.item_count; + + if (node_header.item_count == 0) return keys; - for (uint i=0; iSize (); + 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) +void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys) { - std::list::iterator it = keys.begin (); + std::list::iterator it = keys.begin (); node += sizeof (BTreeNodeHeader); @@ -241,10 +455,12 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listToArray (); + memcpy (node, n, d->Size ()); + delete [] n; + node += d->Size (); + node_header.free_space -= d->Size (); node_header.item_count++; it++; } @@ -258,20 +474,22 @@ void BTree::PrintNode (uint num) BTreeNodeHeader node_header; ReadNodoHeader (node, &node_header); - std::list node_keys = ReadKeys (node, node_header); - std::list::iterator it = node_keys.begin (); + 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 << ") "; + std::string s = *(*it); + std::cout << s << " "; it++; } std::cout << std::endl; delete [] node; + DeleteKeys (node_keys); } uchar *BTree::NewBlock (uint &num) @@ -291,8 +509,72 @@ uchar *BTree::NewBlock (uint &num) nh.free_space = header.block_size - sizeof (BTreeNodeHeader); nh.item_count = 0; WriteNodoHeader (node, &nh); - WriteBlock (node, 0); + WriteBlock (node, num); return node; } +bool BTree::FindKey (const Clave &k) +{ + return FindKeyR (&k, 0); +} + +bool 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); + return true; + } + + 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++; + } +} +