src/btree.cpp

   1
   2 #include "btree.h"
   3
   4 BTree::BTree (const std::string &name, unsigned int block_size, bool create_new_file)
   5 {
   6         uchar *node;
   7         BTreeNodeHeader nh;
   8
   9         fp = fopen (name.c_str(), "wb+");
  10         if (!fp) {
  11                 /* TODO : mandar una exception ? */
  12                 return;
  13         }
  14
  15         /* Nombre de archivo */
  16         filename = name;
  17
  18         /* Inicializo el header */
  19         header.block_size = block_size;
  20         WriteFileHeader ();
  21
  22         /* Creo el primer bloque vacio */
  23         node = new uchar[block_size];
  24         ReadNodoHeader (node, &nh);
  25         nh.level = 0;
  26         nh.free_space = block_size - sizeof (BTreeNodeHeader);
  27         nh.item_count = 0;
  28         WriteNodoHeader (node, &nh);
  29         WriteBlock (node, 0);
  30
  31         delete [] node;
  32 }
  33
  34 BTree::~BTree ()
  35 {
  36         fclose (fp);
  37 }
  38
  39 void BTree::WriteFileHeader ()
  40 {
  41         fseek (fp, 0L, SEEK_SET);
  42         fwrite (&header, 1, sizeof (BTreeFileHeader), fp);
  43 }
  44
  45 void BTree::WriteBlock (uchar *block, uint num)
  46 {
  47         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
  48         fwrite (block, 1, header.block_size, fp);
  49 }
  50
  51 void BTree::AddKey (const Clave &k)
  52 {
  53         uint left, right;
  54         Clave *kout = AddKeyR (&k, 0, left, right);
  55
  56         if (kout) {
  57                 unsigned short level;
  58                 /* Debo dejar la raiz en el nodo 0, por lo que paso el nodo
  59                  * que esta usando el hijo izquierdo a un nuevo nodo */
  60                 std::list<BTreeData *> node_keys;
  61                 BTreeNodeHeader node_header;
  62                 uchar *node = ReadBlock (left);
  63                 ReadNodoHeader (node, &node_header);
  64                 node_keys = ReadKeys (node, node_header);
  65                 level = node_header.level + 1;
  66
  67                 uchar *new_node = NewBlock (left);
  68                 delete [] new_node; /* No me interesa, voy a usar lo leio antes */
  69
  70                 WriteKeys (node, node_header, node_keys);
  71                 WriteNodoHeader (node, &node_header);
  72                 WriteBlock (node, left);
  73                 delete [] node;
  74
  75                 /* Leo y actualizo la Raiz */
  76                 node = ReadBlock (0);
  77                 ReadNodoHeader (node, &node_header);
  78                 node_keys = std::list<BTreeData *>();
  79
  80                 node_keys.push_back (new BTreeChildData (left));
  81                 node_keys.push_back (new BTreeData (kout, right));
  82
  83                 node_header.level = level;
  84                 node_header.item_count = 1;
  85
  86                 WriteKeys (node, node_header, node_keys);
  87                 WriteNodoHeader (node, &node_header);
  88                 WriteBlock (node, 0);
  89                 PrintNode (0);
  90         }
  91 }
  92
  93 Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
  94 {
  95         Clave *kout = NULL;
  96         std::list<BTreeData *> node_keys;
  97
  98         BTreeData *data = new BTreeLeafData (k->Clone ());
  99
 100         /* Leo el nodo raiz para empezar a agregar */
 101         uchar *node = ReadBlock (node_num);
 102         BTreeNodeHeader node_header;
 103         ReadNodoHeader (node, &node_header);
 104
 105         if (node_header.level != 0) {
 106                 /* No estoy en una hoja, asi que tengo que buscar
 107                  * para donde moverme para agregar la clave
 108                  */
 109                 /* TODO :) */
 110                 node_keys = ReadKeys (node, node_header);
 111                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 112
 113                 /* Se supone que la primera es un hijo :) */
 114                 //BTreeData *left_child = (*it);
 115                 PrintNode (node_num);
 116                 std::cout << "TODO!!" << std::endl;
 117                 return NULL;
 118         }
 119
 120
 121         /* Estoy en una hoja, veo si lo puedo agregar */
 122
 123         if (node_header.free_space > data->Size ()) {
 124                 /* TODO : Insertar ordenado */
 125                 BTreeData *datait;
 126                 node_keys = ReadKeys (node, node_header);
 127                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 128
 129                 while (it != node_keys.end ()) {
 130                         datait = (*it);
 131                         if ((*data) < (*datait))
 132                                 /* Me pase, lo agrego aca! */
 133                                 break;
 134                         it++;
 135                 }
 136                 node_keys.insert (it, data);
 137                 WriteKeys (node, node_header, node_keys);
 138                 WriteNodoHeader (node, &node_header);
 139                 WriteBlock (node, node_num);
 140
 141                 PrintNode (node_num);
 142         } else {
 143                 std::cout << "=============== SPLIT ================" << std::endl;
 144                 /* Split : Creo e inicializo el nuevo nodo */
 145                 std::list<BTreeData *> new_node_keys;
 146                 std::list<BTreeData *> old_node_keys;
 147                 BTreeNodeHeader new_node_header;
 148                 uint new_node_num;
 149                 uchar *new_node = NewBlock (new_node_num);
 150                 ReadNodoHeader (new_node, &new_node_header);
 151
 152                 node_keys = ReadKeys (node, node_header);
 153                 new_node_keys = ReadKeys (new_node, new_node_header);
 154
 155                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 156                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 157
 158                 while (it != node_keys.end ()) {
 159                         BTreeData *datait;
 160                         datait = (*it);
 161                         if ((*data) < (*datait))
 162                                 /* Me pase, lo agrego aca! */
 163                                 break;
 164                         it++;
 165                 }
 166                 if (it != node_keys.end ())
 167                         node_keys.insert (it, data);
 168                 else
 169                         node_keys.push_back (data);
 170
 171                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 172                  * y subir la clave del medio */
 173                 node_header.item_count = 0;
 174                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 175
 176                 uint total_size = 0;
 177                 it = node_keys.begin ();
 178                 while (it != node_keys.end ()) {
 179                         BTreeData *datait;
 180                         datait = (*it);
 181                         total_size += datait->Size ();
 182                         it++;
 183                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 184                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 185                          * puede tener en el caso de claves de long. variable
 186                          */
 187                         if (it == node_keys.end ())
 188                                 total_size -= datait->Size ();
 189                 }
 190
 191                 it = node_keys.begin ();
 192                 uint used = 0;
 193                 while (used < total_size/2) {
 194                         BTreeData *d = (*it);
 195                         old_node_keys.push_back (d);
 196                         used += d->Size ();
 197                         it++;
 198                 }
 199                 kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue
 200                 while (it != node_keys.end ()) {
 201                         BTreeData *d = (*it);
 202                         new_node_keys.push_back (d);
 203                         it++;
 204                 }
 205
 206                 /* Guardo */
 207                 WriteKeys (node, node_header, old_node_keys);
 208                 WriteNodoHeader (node, &node_header);
 209                 WriteBlock (node, node_num);
 210                 WriteKeys (new_node, new_node_header, new_node_keys);
 211                 WriteNodoHeader (new_node, &new_node_header);
 212                 WriteBlock (new_node, new_node_num);
 213
 214                 PrintNode (node_num);
 215                 PrintNode (new_node_num);
 216
 217                 /* Paso los hijos */
 218                 left_child = node_num;
 219                 right_child = new_node_num;
 220                 delete [] new_node;
 221                 delete [] node;
 222         }
 223
 224         return kout;
 225 }
 226
 227 void BTree::DelKey (const Clave &k) {}
 228
 229 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
 230 {
 231         memcpy (header, node, sizeof (BTreeNodeHeader));
 232 }
 233
 234 void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
 235 {
 236         memcpy (node, header, sizeof (BTreeNodeHeader));
 237 }
 238
 239 uchar *BTree::ReadBlock (uint num)
 240 {
 241         uchar *out = new uchar[header.block_size];
 242
 243         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
 244         fread (out, 1, header.block_size, fp);
 245
 246         return out;
 247 }
 248
 249 std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header)
 250 {
 251         std::list<BTreeData *> keys;
 252         node += sizeof (BTreeNodeHeader);
 253         uint count = node_header.item_count;
 254
 255         if (node_header.item_count == 0) return keys;
 256
 257         if (node_header.level != 0) {
 258                 /* Si no es una hoja, lo primero que tengo es un BTreeChildData */
 259                 BTreeChildData *d = new BTreeChildData (node);
 260                 node += d->Size ();
 261                 keys.push_back (d);
 262                 count--;
 263         }
 264
 265         for (uint i=0; i<count; i++) {
 266                 /* TODO : El tipo de clave deberia ser usado
 267                  * dependiendo de algun dato en el header del
 268                  * arbol
 269                  */
 270                 /* TODO : Detectar si estoy en una hoja */
 271                 BTreeData *data;
 272                 if (node_header.level == 0) {
 273                         data = new BTreeLeafData (node);
 274                 } else {
 275                         data = new BTreeData (node);
 276                 }
 277                 node += data->Size ();
 278                 keys.push_back (data);
 279         }
 280
 281         return keys;
 282 }
 283
 284 void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys)
 285 {
 286         std::list<BTreeData *>::iterator it = keys.begin ();
 287
 288         node += sizeof (BTreeNodeHeader);
 289
 290         node_header.item_count = 0;
 291         node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 292
 293         while (it != keys.end ()) {
 294                 BTreeData *d = (*it);
 295                 memcpy (node, d->ToArray(), d->Size ());
 296                 node += d->Size ();
 297                 node_header.free_space -= d->Size ();
 298                 node_header.item_count++;
 299                 it++;
 300         }
 301
 302         /* TODO : incrementar node_header.item_count aca o fuera de este metodo? */
 303 }
 304
 305 void BTree::PrintNode (uint num)
 306 {
 307         uchar *node = ReadBlock (num);
 308         BTreeNodeHeader node_header;
 309         ReadNodoHeader (node, &node_header);
 310
 311         std::list<BTreeData *> node_keys = ReadKeys (node, node_header);
 312         std::list<BTreeData *>::iterator it = node_keys.begin ();
 313
 314         std::cout << "Nodo  : " << num << std::endl;
 315         std::cout << "Level : " << node_header.level << std::endl;
 316         std::cout << "Items : " << node_header.item_count << std::endl;
 317         std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
 318         while (it != node_keys.end ()) {
 319                 std::string s = *(*it);
 320                 std::cout << s << " ";
 321                 it++;
 322         }
 323         std::cout << std::endl;
 324
 325         delete [] node;
 326 }
 327
 328 uchar *BTree::NewBlock (uint &num)
 329 {
 330         long filelen;
 331         uchar *node;
 332         BTreeNodeHeader nh;
 333
 334         fseek (fp, 0, SEEK_END);
 335         filelen = ftell (fp);
 336
 337         num = (filelen - sizeof (BTreeFileHeader))/header.block_size;
 338
 339         node = new uchar[header.block_size];
 340         ReadNodoHeader (node, &nh);
 341         nh.level = 0;
 342         nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
 343         nh.item_count = 0;
 344         WriteNodoHeader (node, &nh);
 345         WriteBlock (node, 0);
 346
 347         return node;
 348 }
 349