uchar *node;
BTreeNodeHeader nh;
- fp = fopen (name.c_str(), "wb");
+ fp = fopen (name.c_str(), "wb+");
if (!fp) {
/* TODO : mandar una exception ? */
return;
void BTree::AddKey (const Clave &k)
{
- AddKeyR (&k, 0);
+ 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)
+Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
{
Clave *kout = NULL;
std::list<BTreeData> node_keys;
+ BTreeLeafData data (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);
-
- if (node_header.free_space >= k->Size ()) {
+ 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 */
- /* Siempre se agrega en una hoja */
- node_keys.push_back (BTreeLeafData (k->Clone ()));
+ BTreeData datait;
+
+ node_keys = ReadKeys (node, node_header);
+ std::list<BTreeData>::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);
- delete [] node;
+
+ PrintNode (node_num);
} else {
- /* Split */
- /* Lo que debe pasar :
- * 1) Separar N/2 claves en "nodo"
- * 2) Separar N/2-1 claves en un nuevo nodo
- * 3) kout = clave del medio y mandarla al padre
- */
- std::cout << "SPLIT" << std::endl;
+ std::cout << "=============== SPLIT ================" << std::endl;
+ /* Split : Creo e inicializo el nuevo nodo */
+ std::list<BTreeData> new_node_keys;
+ std::list<BTreeData> 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<BTreeData>::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;
}
return kout;
* arbol
*/
/* TODO : Detectar si estoy en una hoja */
- BTreeData data(node);
+ BTreeData data;
+ if (node_header.level == 0)
+ data = BTreeLeafData (node);
+ else
+ data = BTreeData (node);
node += data.Size ();
keys.push_back (data);
}
/* 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<BTreeData> node_keys = ReadKeys (node, node_header);
+ std::list<BTreeData>::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;
+}
+
projects / z.facultad / 75.52 / treemulator.git / blobdiff