From 56b4eba70b4efa0149bab92cfbe5e83ecfa5524b Mon Sep 17 00:00:00 2001 From: Ricardo Markiewicz Date: Mon, 26 Sep 2005 04:30:48 +0000 Subject: [PATCH 1/1] BugFix : Agrego returns faltantes. --- src/btree.cpp | 180 ++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 144 insertions(+), 36 deletions(-) diff --git a/src/btree.cpp b/src/btree.cpp index 225d043..1bbb755 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -91,6 +91,19 @@ void BTree::AddKey (const Clave &k) } 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; @@ -102,49 +115,153 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri BTreeNodeHeader node_header; ReadNodoHeader (node, &node_header); - if (node_header.level != 0) { - std::cout << "Entrando nodo level = " << node_header.level << std::endl; - /* No estoy en una hoja, asi que tengo que buscar - * para donde moverme para agregar la clave - */ - std::cout << "Leo Claves" << std::endl; + 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); + + 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 posterior; - std::list::iterator ultima; - - /* Se supone que la primera es un hijo :) */ - BTreeData *lchild = (*it++); - posterior = it; + std::list::iterator previt = node_keys.begin (); while (it != node_keys.end ()) { - if ((*data) < (*(*it))) + BTreeData *datait; + datait = (*it); + if ((*data) < (*datait)) + /* Me pase, lo agrego aca! */ break; - ultima = it; + previt = it; it++; } + if (it != node_keys.end ()) + node_keys.insert (it, data); + else + node_keys.push_back (data); - if (it == posterior) { - std::cout << "==== Me voy al nodo " << lchild->getChild () << std::endl; - k = AddKeyR (k, lchild->getChild (), left_child, right_child); - } else { - std::cout << "==== Me voy al nodo " << (*ultima)->getChild () << std::endl; - k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child); + /* 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 (); } - if (k) { - data = new BTreeData (k->Clone (), right_child); + + 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); + + 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); + + 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); + } /* Nada que hacer */ if (!k) return NULL; - /* Estoy en una hoja, veo si lo puedo agregar */ + data = new BTreeData (k->Clone (), right_child); 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 (); @@ -163,7 +280,6 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri 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; @@ -180,11 +296,7 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri std::list::iterator it = node_keys.begin (); std::list::iterator previt = node_keys.begin (); - if (node_header.level != 0) { - /* La primera es ChildData */ - it++; - previt = it; - } + previt = ++it; while (it != node_keys.end ()) { BTreeData *datait; @@ -229,13 +341,9 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri it++; } kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue - if (node_header.level != 0) { - new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ())); - } - it++; - std::string s = *kout; - std::cout << "SPLIT Retorna : " << s << std::endl; + new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ())); + it++; while (it != node_keys.end ()) { BTreeData *d = (*it); new_node_keys.push_back (d); -- 2.43.0