X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/113597e3c369b18fa4e73a0b9744398a0e9e0a79..52d9e098f15ad0ca70f11b4549f3d55f55a22a83:/src/btree.cpp diff --git a/src/btree.cpp b/src/btree.cpp index d1fbab3..81b2fc9 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -6,7 +6,7 @@ BTree::BTree (const std::string &name, unsigned int block_size, bool create_new_ 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 +17,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 +26,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,13 +36,13 @@ 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); fwrite (block, 1, header.block_size, fp); @@ -50,23 +50,140 @@ void BTree::write_block (uchar *block, uint num) void BTree::AddKey (const Clave &k) { - std::list node_keys; + uint left, right; + Clave *kout = AddKeyR (&k, 0, left, right); + + if (kout) { + std::cout << "Raiz fue spliteada!!" << std::endl; + } +} + +Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child) +{ + Clave *kout = NULL; + std::list node_keys; + + BTreeLeafData data (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 (root, root_header); - std::cout << node_keys.size () << std::endl; - - if (root_header.free_space >= k.Size ()) { - std::cout << "Hay lugar para meter la clave" << std::endl; + if (node_header.level != 0) { + /* No estoy en una hoja, asi que tengo que buscar + * para donde moverme para agregar la clave + */ + /* TODO :) */ + } + + + /* Estoy en una hoja, veo si lo puedo agregar */ + + if (node_header.free_space > data.Size ()) { + /* TODO : Insertar ordenado */ + 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); + + PrintNode (node_num); } else { - std::cout << "__NO__ hay lugar para meter la clave" << std::endl; + std::cout << "=============== SPLIT ================" << std::endl; + /* 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); + + 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 (); + + while (it != node_keys.end ()) { + BTreeData datait; + datait = (*it); + if (data < datait) + /* Me pase, lo agrego aca! */ + break; + 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); + std::cout << used << " " << total_size << std::endl; + 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); + + PrintNode (node_num); + PrintNode (new_node_num); + + /* Paso los hijos */ + left_child = node_num; + right_child = new_node_num; + delete [] new_node; + delete [] node; } - delete [] root; + return kout; } void BTree::DelKey (const Clave &k) {} @@ -91,9 +208,9 @@ 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); for (uint i=0; i BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header) * dependiendo de algun dato en el header del * arbol */ - ClaveFija *k = new ClaveFija (node); - node += k->Size (); - keys.push_back (k); + /* TODO : Detectar si estoy en una hoja */ + BTreeData data; + if (node_header.level == 0) + data = BTreeLeafData (node); + else + data = BTreeData (node); + node += data.Size (); + 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); + + while (it != keys.end ()) { + BTreeData d = (*it); + memcpy (node, d.ToArray(), d.Size ()); + 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 << "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; +} + +uchar *BTree::NewBlock (uint &num) +{ + long filelen; + uchar *node; + BTreeNodeHeader nh; + + fseek (fp, 0, SEEK_END); + filelen = ftell (fp); + + num = (filelen - sizeof (BTreeFileHeader))/header.block_size; + + 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, 0); + + return node; +} +