From 8699d7e1ccbda4282f8ba693422f337be31d100b Mon Sep 17 00:00:00 2001 From: Ricardo Markiewicz Date: Thu, 15 Sep 2005 04:17:51 +0000 Subject: [PATCH] Paso el uso de BTreeData a heap. Tambien se agrega logica de split de raiz entre otras cosas. --- src/btree.cpp | 127 +++++++++++++++++++++++++++++++-------------- src/btree.h | 4 +- src/btree_data.cpp | 4 +- src/btree_data.h | 6 +-- 4 files changed, 94 insertions(+), 47 deletions(-) diff --git a/src/btree.cpp b/src/btree.cpp index 81b2fc9..4d28e49 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -54,16 +54,48 @@ void BTree::AddKey (const Clave &k) Clave *kout = AddKeyR (&k, 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); + 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); + PrintNode (0); } } Clave* BTree::AddKeyR (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); @@ -75,21 +107,28 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri * para donde moverme para agregar la clave */ /* TODO :) */ + node_keys = ReadKeys (node, node_header); + std::list::iterator it = node_keys.begin (); + + /* Se supone que la primera es un hijo :) */ + //BTreeData *left_child = (*it); + PrintNode (node_num); + std::cout << "TODO!!" << std::endl; + return NULL; } /* Estoy en una hoja, veo si lo puedo agregar */ - if (node_header.free_space > data.Size ()) { + if (node_header.free_space > data->Size ()) { /* TODO : Insertar ordenado */ - BTreeData datait; - + 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++; @@ -103,8 +142,8 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri } 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); @@ -114,12 +153,12 @@ Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &ri 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 (); while (it != node_keys.end ()) { - BTreeData datait; + BTreeData *datait; datait = (*it); - if (data < datait) + if ((*data) < (*datait)) /* Me pase, lo agrego aca! */ break; it++; @@ -137,30 +176,29 @@ 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 while (it != node_keys.end ()) { - BTreeData d = (*it); + BTreeData *d = (*it); new_node_keys.push_back (d); it++; } @@ -208,32 +246,42 @@ 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); + 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); + } + 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 +289,10 @@ void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::listToArray(), d->Size ()); + node += d->Size (); + node_header.free_space -= d->Size (); node_header.item_count++; it++; } @@ -258,15 +306,16 @@ 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; diff --git a/src/btree.h b/src/btree.h index 14ef604..023c5d7 100644 --- a/src/btree.h +++ b/src/btree.h @@ -104,8 +104,8 @@ class BTree { void ReadNodoHeader (uchar *node, BTreeNodeHeader *header); void WriteNodoHeader (uchar *node, BTreeNodeHeader *header); - std::list ReadKeys (uchar *node, BTreeNodeHeader &node_header); - void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys); + std::list ReadKeys (uchar *node, BTreeNodeHeader &node_header); + void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys); std::string filename; BTreeFileHeader header; diff --git a/src/btree_data.cpp b/src/btree_data.cpp index b95b86a..46917d6 100644 --- a/src/btree_data.cpp +++ b/src/btree_data.cpp @@ -26,7 +26,7 @@ uint BTreeData::Size () const { uint s = sizeof (uint); if (clave) s += clave->Size (); - + else std::cout << "No tengo clave\n"; return s; } @@ -53,7 +53,6 @@ BTreeLeafData::~BTreeLeafData () uint BTreeLeafData::Size () const { - std::cout << "BTreeLeafData::Size()" << std::endl; if (!clave) { std::cout << "BTreeLeafData::Size : No tengo clave!" << std::endl; return 0; @@ -77,7 +76,6 @@ BTreeChildData::~BTreeChildData () uint BTreeChildData::Size () const { - std::cout << "BTreeChildData::Size()" << std::endl; return sizeof (uint); } diff --git a/src/btree_data.h b/src/btree_data.h index cfe6ef8..b07f6f5 100644 --- a/src/btree_data.h +++ b/src/btree_data.h @@ -24,8 +24,8 @@ class BTreeData { virtual operator std::string () const { std::string out = (*clave); std::stringstream ss; - ss << out << " "; - ss << hijo; + ss << "(" << out << ") "; + ss << "[" << hijo << "]"; ss >> out; return out; } @@ -62,7 +62,7 @@ class BTreeChildData:public BTreeData { virtual operator std::string () const { std::string out; std::stringstream ss; - ss << hijo; + ss << "|" << hijo << "|"; ss >> out; return out; } -- 2.43.0