src/btree.cpp

   1
   2 #include "btree.h"
   3
   4 BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool create_new_file)
   5 {
   6         key_type = kt;
   7         uchar *node;
   8         BTreeNodeHeader nh;
   9
  10         fp = fopen (name.c_str(), "wb+");
  11         if (!fp) {
  12                 /* TODO : mandar una exception ? */
  13                 return;
  14         }
  15
  16         /* Nombre de archivo */
  17         filename = name;
  18
  19         /* Inicializo el header */
  20         header.block_size = block_size;
  21         WriteFileHeader ();
  22
  23         /* Creo el primer bloque vacio */
  24         node = new uchar[block_size];
  25         ReadNodoHeader (node, &nh);
  26         nh.level = 0;
  27         nh.free_space = block_size - sizeof (BTreeNodeHeader);
  28         nh.item_count = 0;
  29         WriteNodoHeader (node, &nh);
  30         WriteBlock (node, 0);
  31
  32         delete [] node;
  33 }
  34
  35 BTree::~BTree ()
  36 {
  37         fclose (fp);
  38 }
  39
  40 void BTree::WriteFileHeader ()
  41 {
  42         fseek (fp, 0L, SEEK_SET);
  43         fwrite (&header, 1, sizeof (BTreeFileHeader), fp);
  44 }
  45
  46 void BTree::WriteBlock (uchar *block, uint num)
  47 {
  48         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
  49         fwrite (block, 1, header.block_size, fp);
  50 }
  51
  52 void BTree::AddKey (const Clave &k)
  53 {
  54         uint left, right;
  55         Clave *kout = AddKeyR (&k, 0, left, right);
  56
  57         if (kout) {
  58                 unsigned short level;
  59                 /* Debo dejar la raiz en el nodo 0, por lo que paso el nodo
  60                  * que esta usando el hijo izquierdo a un nuevo nodo */
  61                 std::list<BTreeData *> node_keys;
  62                 BTreeNodeHeader node_header;
  63                 uchar *node = ReadBlock (left);
  64                 ReadNodoHeader (node, &node_header);
  65                 node_keys = ReadKeys (node, node_header);
  66                 level = node_header.level + 1;
  67
  68                 uchar *new_node = NewBlock (left);
  69                 delete [] new_node; /* No me interesa, voy a usar lo leio antes */
  70
  71                 WriteKeys (node, node_header, node_keys);
  72                 WriteNodoHeader (node, &node_header);
  73                 WriteBlock (node, left);
  74                 delete [] node;
  75
  76                 /* Leo y actualizo la Raiz */
  77                 node = ReadBlock (0);
  78                 ReadNodoHeader (node, &node_header);
  79                 node_keys = std::list<BTreeData *>();
  80
  81                 node_keys.push_back (new BTreeChildData (left));
  82                 node_keys.push_back (new BTreeData (kout, right));
  83
  84                 node_header.level = level;
  85                 node_header.item_count = 1;
  86
  87                 WriteKeys (node, node_header, node_keys);
  88                 WriteNodoHeader (node, &node_header);
  89                 WriteBlock (node, 0);
  90                 PrintNode (0);
  91         }
  92 }
  93
  94 Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
  95 {
  96         uchar *node = ReadBlock (node_num);
  97         BTreeNodeHeader node_header;
  98         ReadNodoHeader (node, &node_header);
  99         delete [] node;
 100
 101         if (node_header.level == 0)
 102                 return AddKeyLeafR (k, node_num, left_child, right_child);
 103
 104         return AddKeyOtherR (k, node_num, left_child, right_child);
 105 }
 106
 107 Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 108 {
 109         Clave *kout = NULL;
 110         std::list<BTreeData *> node_keys;
 111
 112         BTreeData *data = new BTreeLeafData (k->Clone ());
 113
 114         /* Leo el nodo raiz para empezar a agregar */
 115         uchar *node = ReadBlock (node_num);
 116         BTreeNodeHeader node_header;
 117         ReadNodoHeader (node, &node_header);
 118
 119         if (node_header.free_space > data->Size ()) {
 120                 BTreeData *datait;
 121                 node_keys = ReadKeys (node, node_header);
 122                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 123
 124                 while (it != node_keys.end ()) {
 125                         datait = (*it);
 126                         if ((*data) < (*datait))
 127                                 /* Me pase, lo agrego aca! */
 128                                 break;
 129                         it++;
 130                 }
 131                 node_keys.insert (it, data);
 132                 WriteKeys (node, node_header, node_keys);
 133                 WriteNodoHeader (node, &node_header);
 134                 WriteBlock (node, node_num);
 135
 136                 PrintNode (node_num);
 137         } else {
 138                 /* Split : Creo e inicializo el nuevo nodo */
 139                 std::list<BTreeData *> new_node_keys;
 140                 std::list<BTreeData *> old_node_keys;
 141                 BTreeNodeHeader new_node_header;
 142                 uint new_node_num;
 143                 uchar *new_node = NewBlock (new_node_num);
 144                 ReadNodoHeader (new_node, &new_node_header);
 145                 new_node_header.level = node_header.level;
 146
 147                 node_keys = ReadKeys (node, node_header);
 148                 new_node_keys = ReadKeys (new_node, new_node_header);
 149
 150                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 151                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 152                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 153
 154                 while (it != node_keys.end ()) {
 155                         BTreeData *datait;
 156                         datait = (*it);
 157                         if ((*data) < (*datait))
 158                                 /* Me pase, lo agrego aca! */
 159                                 break;
 160                         previt = it;
 161                         it++;
 162                 }
 163                 if (it != node_keys.end ())
 164                         node_keys.insert (it, data);
 165                 else
 166                         node_keys.push_back (data);
 167
 168                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 169                  * y subir la clave del medio */
 170                 node_header.item_count = 0;
 171                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 172
 173                 uint total_size = 0;
 174                 it = node_keys.begin ();
 175                 while (it != node_keys.end ()) {
 176                         BTreeData *datait;
 177                         datait = (*it);
 178                         total_size += datait->Size ();
 179                         it++;
 180                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 181                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 182                          * puede tener en el caso de claves de long. variable
 183                          */
 184                         if (it == node_keys.end ())
 185                                 total_size -= datait->Size ();
 186                 }
 187
 188                 it = node_keys.begin ();
 189                 uint used = 0;
 190                 while (used < total_size/2) {
 191                         BTreeData *d = (*it);
 192                         old_node_keys.push_back (d);
 193                         used += d->Size ();
 194                         it++;
 195                 }
 196                 kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue
 197
 198                 while (it != node_keys.end ()) {
 199                         BTreeData *d = (*it);
 200                         new_node_keys.push_back (d);
 201                         it++;
 202                 }
 203
 204                 /* Guardo */
 205                 WriteKeys (node, node_header, old_node_keys);
 206                 WriteNodoHeader (node, &node_header);
 207                 WriteBlock (node, node_num);
 208                 WriteKeys (new_node, new_node_header, new_node_keys);
 209                 WriteNodoHeader (new_node, &new_node_header);
 210                 WriteBlock (new_node, new_node_num);
 211
 212                 PrintNode (node_num);
 213                 PrintNode (new_node_num);
 214
 215                 /* Paso los hijos */
 216                 left_child = node_num;
 217                 right_child = new_node_num;
 218                 delete [] new_node;
 219                 delete [] node;
 220         }
 221
 222         return kout;
 223 }
 224
 225 Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 226 {
 227         Clave *kout = NULL;
 228         std::list<BTreeData *> node_keys;
 229
 230         BTreeData *data = new BTreeLeafData (k->Clone ());
 231
 232         /* Leo el nodo raiz para empezar a agregar */
 233         uchar *node = ReadBlock (node_num);
 234         BTreeNodeHeader node_header;
 235         ReadNodoHeader (node, &node_header);
 236
 237         node_keys = ReadKeys (node, node_header);
 238
 239         std::list<BTreeData *>::iterator it = node_keys.begin ();
 240         std::list<BTreeData *>::iterator posterior;
 241         std::list<BTreeData *>::iterator ultima;
 242
 243         /* Se supone que la primera es un hijo :) */
 244         BTreeData *lchild = (*it++);
 245         posterior = it;
 246
 247         while (it != node_keys.end ()) {
 248                 if ((*data) < (*(*it)))
 249                         break;
 250                 ultima = it;
 251                 it++;
 252         }
 253
 254         if (it == posterior) {
 255                 k = AddKeyR (k, lchild->getChild (), left_child, right_child);
 256         } else {
 257                 k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child);
 258         }
 259
 260         /* Nada que hacer */
 261         if (!k) return NULL;
 262
 263         data = new BTreeData (k->Clone (), right_child);
 264
 265         if (node_header.free_space > data->Size ()) {
 266                 BTreeData *datait;
 267                 node_keys = ReadKeys (node, node_header);
 268                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 269
 270                 while (it != node_keys.end ()) {
 271                         datait = (*it);
 272                         if ((*data) < (*datait))
 273                                 /* Me pase, lo agrego aca! */
 274                                 break;
 275                         it++;
 276                 }
 277                 node_keys.insert (it, data);
 278                 WriteKeys (node, node_header, node_keys);
 279                 WriteNodoHeader (node, &node_header);
 280                 WriteBlock (node, node_num);
 281
 282                 PrintNode (node_num);
 283         } else {
 284                 /* Split : Creo e inicializo el nuevo nodo */
 285                 std::list<BTreeData *> new_node_keys;
 286                 std::list<BTreeData *> old_node_keys;
 287                 BTreeNodeHeader new_node_header;
 288                 uint new_node_num;
 289                 uchar *new_node = NewBlock (new_node_num);
 290                 ReadNodoHeader (new_node, &new_node_header);
 291                 new_node_header.level = node_header.level;
 292
 293                 node_keys = ReadKeys (node, node_header);
 294                 new_node_keys = ReadKeys (new_node, new_node_header);
 295
 296                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 297                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 298                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 299
 300                 previt = ++it;
 301
 302                 while (it != node_keys.end ()) {
 303                         BTreeData *datait;
 304                         datait = (*it);
 305                         if ((*data) < (*datait))
 306                                 /* Me pase, lo agrego aca! */
 307                                 break;
 308                         previt = it;
 309                         it++;
 310                 }
 311                 if (it != node_keys.end ())
 312                         node_keys.insert (it, data);
 313                 else
 314                         node_keys.push_back (data);
 315
 316                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 317                  * y subir la clave del medio */
 318                 node_header.item_count = 0;
 319                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 320
 321                 uint total_size = 0;
 322                 it = node_keys.begin ();
 323                 while (it != node_keys.end ()) {
 324                         BTreeData *datait;
 325                         datait = (*it);
 326                         total_size += datait->Size ();
 327                         it++;
 328                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 329                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 330                          * puede tener en el caso de claves de long. variable
 331                          */
 332                         if (it == node_keys.end ())
 333                                 total_size -= datait->Size ();
 334                 }
 335
 336                 it = node_keys.begin ();
 337                 uint used = 0;
 338                 while (used < total_size/2) {
 339                         BTreeData *d = (*it);
 340                         old_node_keys.push_back (d);
 341                         used += d->Size ();
 342                         it++;
 343                 }
 344                 kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue
 345
 346                 new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ()));
 347                 it++;
 348                 while (it != node_keys.end ()) {
 349                         BTreeData *d = (*it);
 350                         new_node_keys.push_back (d);
 351                         it++;
 352                 }
 353
 354                 /* Guardo */
 355                 WriteKeys (node, node_header, old_node_keys);
 356                 WriteNodoHeader (node, &node_header);
 357                 WriteBlock (node, node_num);
 358                 WriteKeys (new_node, new_node_header, new_node_keys);
 359                 WriteNodoHeader (new_node, &new_node_header);
 360                 WriteBlock (new_node, new_node_num);
 361
 362                 PrintNode (node_num);
 363                 PrintNode (new_node_num);
 364
 365                 /* Paso los hijos */
 366                 left_child = node_num;
 367                 right_child = new_node_num;
 368                 delete [] new_node;
 369                 delete [] node;
 370         }
 371
 372         return kout;
 373 }
 374
 375 void BTree::DelKey (const Clave &k) {}
 376
 377 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
 378 {
 379         memcpy (header, node, sizeof (BTreeNodeHeader));
 380 }
 381
 382 void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
 383 {
 384         memcpy (node, header, sizeof (BTreeNodeHeader));
 385 }
 386
 387 uchar *BTree::ReadBlock (uint num)
 388 {
 389         uchar *out = new uchar[header.block_size];
 390
 391         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
 392         fread (out, 1, header.block_size, fp);
 393
 394         return out;
 395 }
 396
 397 std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header)
 398 {
 399         std::list<BTreeData *> keys;
 400         node += sizeof (BTreeNodeHeader);
 401         uint count = node_header.item_count;
 402
 403         if (node_header.item_count == 0) return keys;
 404
 405         if (node_header.level != 0) {
 406                 /* Si no es una hoja, lo primero que tengo es un BTreeChildData */
 407                 BTreeChildData *d = new BTreeChildData (node);
 408                 node += d->Size ();
 409                 keys.push_back (d);
 410                 count--;
 411         }
 412
 413         for (uint i=0; i<count; i++) {
 414                 /* TODO : El tipo de clave deberia ser usado
 415                  * dependiendo de algun dato en el header del
 416                  * arbol
 417                  */
 418                 /* TODO : Detectar si estoy en una hoja */
 419                 BTreeData *data;
 420                 if (node_header.level == 0) {
 421                         data = new BTreeLeafData (node, key_type);
 422                 } else {
 423                         data = new BTreeData (node, key_type);
 424                 }
 425                 node += data->Size ();
 426                 keys.push_back (data);
 427         }
 428
 429         return keys;
 430 }
 431
 432 void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys)
 433 {
 434         std::list<BTreeData *>::iterator it = keys.begin ();
 435
 436         node += sizeof (BTreeNodeHeader);
 437
 438         node_header.item_count = 0;
 439         node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 440
 441         while (it != keys.end ()) {
 442                 BTreeData *d = (*it);
 443                 memcpy (node, d->ToArray(), d->Size ());
 444                 node += d->Size ();
 445                 node_header.free_space -= d->Size ();
 446                 node_header.item_count++;
 447                 it++;
 448         }
 449
 450         /* TODO : incrementar node_header.item_count aca o fuera de este metodo? */
 451 }
 452
 453 void BTree::PrintNode (uint num)
 454 {
 455         uchar *node = ReadBlock (num);
 456         BTreeNodeHeader node_header;
 457         ReadNodoHeader (node, &node_header);
 458
 459         std::list<BTreeData *> node_keys = ReadKeys (node, node_header);
 460         std::list<BTreeData *>::iterator it = node_keys.begin ();
 461
 462         std::cout << "Nodo  : " << num << std::endl;
 463         std::cout << "Level : " << node_header.level << std::endl;
 464         std::cout << "Items : " << node_header.item_count << std::endl;
 465         std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
 466         while (it != node_keys.end ()) {
 467                 std::string s = *(*it);
 468                 std::cout << s << " ";
 469                 it++;
 470         }
 471         std::cout << std::endl;
 472
 473         delete [] node;
 474 }
 475
 476 uchar *BTree::NewBlock (uint &num)
 477 {
 478         long filelen;
 479         uchar *node;
 480         BTreeNodeHeader nh;
 481
 482         fseek (fp, 0, SEEK_END);
 483         filelen = ftell (fp);
 484
 485         num = (filelen - sizeof (BTreeFileHeader))/header.block_size;
 486
 487         node = new uchar[header.block_size];
 488         ReadNodoHeader (node, &nh);
 489         nh.level = 0;
 490         nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
 491         nh.item_count = 0;
 492         WriteNodoHeader (node, &nh);
 493         WriteBlock (node, num);
 494
 495         return node;
 496 }
 497