src/btree.cpp

   1
   2 #include "btree.h"
   3
   4 BTree::BTree (const std::string &name, unsigned int block_size, int tt, int kt, 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         header.tree_type = tt;
  21         header.key_type = kt;
  22         header.block_data_counter = 0;
  23         WriteFileHeader ();
  24
  25         /* Creo el primer bloque vacio */
  26         node = new uchar[block_size];
  27         ReadNodoHeader (node, &nh);
  28         nh.level = 0;
  29         nh.free_space = block_size - sizeof (BTreeNodeHeader);
  30         nh.item_count = 0;
  31         WriteNodoHeader (node, &nh);
  32         WriteBlock (node, 0);
  33
  34         delete [] node;
  35 }
  36
  37 BTree::BTree (const std::string &name)
  38 {
  39         /* Leo los bloques recuperables */
  40         std::string del = filename + ".del";
  41
  42         fp = fopen (del.c_str (), "wb");
  43         if (fp != NULL) {
  44                 uint i;
  45
  46                 while (fread (&i, 1, sizeof (uint), fp)) {
  47                         deleted_nodes.push_back (i);
  48                 }
  49
  50                 fclose (fp);
  51         }
  52
  53         del = filename + ".blockdel";
  54
  55         fp = fopen (del.c_str (), "wb");
  56         if (fp != NULL) {
  57                 uint i;
  58
  59                 while (fread (&i, 1, sizeof (uint), fp)) {
  60                         deleted_block_data.push_back (i);
  61                 }
  62
  63                 fclose (fp);
  64         }
  65
  66         fp = fopen (name.c_str(), "rb+");
  67         if (!fp) {
  68                 /* TODO : mandar una exception ? */
  69                 return;
  70         }
  71         ReadFileHeader ();
  72 }
  73
  74 BTree::~BTree ()
  75 {
  76         fclose (fp);
  77
  78         std::string del = filename + ".del";
  79
  80         fp = fopen (del.c_str (), "wb");
  81         std::list<uint>::iterator it = deleted_nodes.begin ();
  82
  83         while (it != deleted_nodes.end ()) {
  84                 uint i = *it;
  85                 fwrite (&i, 1, sizeof (uint), fp);
  86                 it++;
  87         }
  88
  89         del = filename + ".del";
  90
  91         fp = fopen (del.c_str (), "wb");
  92         it = deleted_block_data.begin ();
  93
  94         while (it != deleted_block_data.end ()) {
  95                 uint i = *it;
  96                 fwrite (&i, 1, sizeof (uint), fp);
  97                 it++;
  98         }
  99         fclose (fp);
 100 }
 101
 102 void BTree::ReadFileHeader ()
 103 {
 104         fseek (fp, 0L, SEEK_SET);
 105         fread (&header, 1, sizeof (BTreeFileHeader), fp);
 106 }
 107
 108 void BTree::WriteFileHeader ()
 109 {
 110         fseek (fp, 0L, SEEK_SET);
 111         fwrite (&header, 1, sizeof (BTreeFileHeader), fp);
 112 }
 113
 114 void BTree::WriteBlock (uchar *block, uint num)
 115 {
 116         num++;
 117         fseek (fp, num*header.block_size, SEEK_SET);
 118         fwrite (block, 1, header.block_size, fp);
 119 }
 120
 121 void BTree::AddKey (const Clave &k)
 122 {
 123         uint left, right;
 124         Clave *kout, *in;
 125
 126         in = k.Clone ();
 127         in->SetBlockData ( GetNextBlockData () );
 128
 129         try {
 130                 kout = AddKeyR (in->Clone (), 0, left, right);
 131         } catch (Exception *e) {
 132                 throw e;
 133         }
 134
 135         delete in;
 136
 137         if (kout) {
 138                 unsigned short level;
 139                 /* Debo dejar la raiz en el nodo 0, por lo que paso el nodo
 140                  * que esta usando el hijo izquierdo a un nuevo nodo */
 141                 std::list<BTreeData *> node_keys;
 142                 BTreeNodeHeader node_header;
 143                 uchar *node = ReadBlock (left);
 144                 ReadNodoHeader (node, &node_header);
 145                 node_keys = ReadKeys (node, node_header);
 146                 level = node_header.level + 1;
 147
 148                 uchar *new_node = NewBlock (left);
 149                 delete [] new_node; /* No me interesa, voy a usar lo leio antes */
 150
 151                 WriteKeys (node, node_header, node_keys);
 152                 WriteNodoHeader (node, &node_header);
 153                 WriteBlock (node, left);
 154                 DeleteKeys (node_keys);
 155                 delete [] node;
 156
 157                 /* Leo y actualizo la Raiz */
 158                 node = ReadBlock (0);
 159                 ReadNodoHeader (node, &node_header);
 160                 node_keys = std::list<BTreeData *>();
 161
 162                 node_keys.push_back (new BTreeChildData (left));
 163                 node_keys.push_back (new BTreeData (kout, right));
 164
 165                 node_header.level = level;
 166                 node_header.item_count = 1;
 167
 168                 WriteKeys (node, node_header, node_keys);
 169                 WriteNodoHeader (node, &node_header);
 170                 WriteBlock (node, 0);
 171                 delete [] node;
 172                 DeleteKeys (node_keys);
 173                 PrintNode (0);
 174         }
 175 }
 176
 177 Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 178 {
 179         uchar *node = ReadBlock (node_num);
 180         BTreeNodeHeader node_header;
 181         ReadNodoHeader (node, &node_header);
 182         delete [] node;
 183
 184         if (node_header.level == 0) {
 185                 try {
 186                         return AddKeyLeafR (k, node_num, left_child, right_child);
 187                 } catch (Exception *e) {
 188                         throw e;
 189                 }
 190         }
 191
 192         try {
 193                 return AddKeyOtherR (k, node_num, left_child, right_child);
 194         } catch (Exception *e) {
 195                 throw e;
 196         }
 197 }
 198
 199 Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 200 {
 201         Clave *kout = NULL;
 202         std::list<BTreeData *> node_keys;
 203
 204         BTreeData *data = new BTreeLeafData (k->Clone ());
 205
 206         /* Leo el nodo raiz para empezar a agregar */
 207         uchar *node = ReadBlock (node_num);
 208         BTreeNodeHeader node_header;
 209         ReadNodoHeader (node, &node_header);
 210
 211         if (node_header.free_space > data->Size ()) {
 212                 BTreeData *datait;
 213                 node_keys = ReadKeys (node, node_header);
 214                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 215
 216                 while (it != node_keys.end ()) {
 217                         datait = (*it);
 218                         if (header.tree_type == TYPE_IDENTIFICACION) {
 219                                 /* Verifico que la clave no existea ya en el arbol */
 220                                 if ((*data) == (*datait)) {
 221                                         throw new AddException ();
 222                                         return NULL;
 223                                 }
 224                         }
 225
 226                         if ((*data) < (*datait))
 227                                 /* Me pase, lo agrego aca! */
 228                                 break;
 229                         it++;
 230                 }
 231                 node_keys.insert (it, data);
 232                 WriteKeys (node, node_header, node_keys);
 233                 WriteNodoHeader (node, &node_header);
 234                 WriteBlock (node, node_num);
 235                 DeleteKeys (node_keys);
 236                 delete [] node;
 237
 238                 PrintNode (node_num);
 239         } else {
 240                 /* Split : Creo e inicializo el nuevo nodo */
 241                 std::list<BTreeData *> new_node_keys;
 242                 std::list<BTreeData *> old_node_keys;
 243                 BTreeNodeHeader new_node_header;
 244                 uint new_node_num;
 245                 uchar *new_node = NewBlock (new_node_num);
 246                 ReadNodoHeader (new_node, &new_node_header);
 247                 new_node_header.level = node_header.level;
 248
 249                 node_keys = ReadKeys (node, node_header);
 250                 new_node_keys = ReadKeys (new_node, new_node_header);
 251
 252                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 253                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 254                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 255
 256                 while (it != node_keys.end ()) {
 257                         BTreeData *datait;
 258                         datait = (*it);
 259                         if (header.tree_type == TYPE_IDENTIFICACION) {
 260                                 /* Verifico que la clave no existea ya en el arbol */
 261                                 if ((*data) == (*datait)) {
 262                                         throw new AddException ();
 263                                         return NULL;
 264                                 }
 265                         }
 266                         if ((*data) < (*datait))
 267                                 /* Me pase, lo agrego aca! */
 268                                 break;
 269                         previt = it;
 270                         it++;
 271                 }
 272                 if (it != node_keys.end ())
 273                         node_keys.insert (it, data);
 274                 else
 275                         node_keys.push_back (data);
 276
 277                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 278                  * y subir la clave del medio */
 279                 node_header.item_count = 0;
 280                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 281
 282                 uint total_size = 0;
 283                 it = node_keys.begin ();
 284                 while (it != node_keys.end ()) {
 285                         BTreeData *datait;
 286                         datait = (*it);
 287                         total_size += datait->Size ();
 288                         it++;
 289                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 290                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 291                          * puede tener en el caso de claves de long. variable
 292                          */
 293                         if (it == node_keys.end ())
 294                                 total_size -= datait->Size ();
 295                 }
 296
 297                 it = node_keys.begin ();
 298                 uint used = 0;
 299                 while (used < total_size/2) {
 300                         BTreeData *d = (*it);
 301                         old_node_keys.push_back (d);
 302                         used += d->Size ();
 303                         it++;
 304                 }
 305                 kout = (*it++)->GetKey (); // Esta se retorna al "padre" para que se la agregue
 306
 307                 while (it != node_keys.end ()) {
 308                         BTreeData *d = (*it);
 309                         new_node_keys.push_back (d);
 310                         it++;
 311                 }
 312
 313                 /* Guardo */
 314                 WriteKeys (node, node_header, old_node_keys);
 315                 WriteNodoHeader (node, &node_header);
 316                 WriteBlock (node, node_num);
 317                 WriteKeys (new_node, new_node_header, new_node_keys);
 318                 WriteNodoHeader (new_node, &new_node_header);
 319                 WriteBlock (new_node, new_node_num);
 320                 DeleteKeys (old_node_keys);
 321                 DeleteKeys (new_node_keys);
 322
 323                 PrintNode (node_num);
 324                 PrintNode (new_node_num);
 325
 326                 /* Paso los hijos */
 327                 left_child = node_num;
 328                 right_child = new_node_num;
 329                 delete [] new_node;
 330                 delete [] node;
 331         }
 332
 333         return kout;
 334 }
 335
 336 Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 337 {
 338         Clave *kout = NULL;
 339         std::list<BTreeData *> node_keys;
 340
 341         BTreeData *data = new BTreeLeafData (k->Clone ());
 342
 343         /* Leo el nodo raiz para empezar a agregar */
 344         uchar *node = ReadBlock (node_num);
 345         BTreeNodeHeader node_header;
 346         ReadNodoHeader (node, &node_header);
 347
 348         node_keys = ReadKeys (node, node_header);
 349
 350         std::list<BTreeData *>::iterator it = node_keys.begin ();
 351         std::list<BTreeData *>::iterator posterior;
 352         std::list<BTreeData *>::iterator ultima;
 353
 354         /* Se supone que la primera es un hijo :) */
 355         BTreeData *lchild = (*it++);
 356         posterior = it;
 357
 358         while (it != node_keys.end ()) {
 359                 if (header.tree_type == TYPE_IDENTIFICACION) {
 360                         /* Verifico que la clave no existea ya en el arbol */
 361                         if ((*data) == (*(*it))) {
 362                                 throw new AddException ();
 363                                 return NULL;
 364                         }
 365                 }
 366                 if ((*data) < (*(*it)))
 367                         break;
 368                 ultima = it;
 369                 it++;
 370         }
 371
 372         if (it == posterior) {
 373                 k = AddKeyR (k, lchild->GetChild (), left_child, right_child);
 374         } else {
 375                 k = AddKeyR (k, (*ultima)->GetChild (), left_child, right_child);
 376         }
 377         DeleteKeys (node_keys);
 378
 379         /* Nada que hacer */
 380         if (data) delete data;
 381         if (!k) {
 382                 delete [] node;
 383                 return NULL;
 384         }
 385
 386         data = new BTreeData (k->Clone (), right_child);
 387
 388         if (node_header.free_space > data->Size ()) {
 389                 BTreeData *datait;
 390                 node_keys = ReadKeys (node, node_header);
 391                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 392
 393                 while (it != node_keys.end ()) {
 394                         datait = (*it);
 395                         if (header.tree_type == TYPE_IDENTIFICACION) {
 396                                 /* Verifico que la clave no existea ya en el arbol */
 397                                 if ((*data) == (*datait)) {
 398                                         throw new AddException ();
 399                                         return NULL;
 400                                 }
 401                         }
 402                         if ((*data) < (*datait))
 403                                 /* Me pase, lo agrego aca! */
 404                                 break;
 405                         it++;
 406                 }
 407                 node_keys.insert (it, data);
 408                 WriteKeys (node, node_header, node_keys);
 409                 WriteNodoHeader (node, &node_header);
 410                 WriteBlock (node, node_num);
 411                 DeleteKeys (node_keys);
 412                 delete [] node;
 413
 414                 PrintNode (node_num);
 415         } else {
 416                 /* Split : Creo e inicializo el nuevo nodo */
 417                 std::list<BTreeData *> new_node_keys;
 418                 std::list<BTreeData *> old_node_keys;
 419                 BTreeNodeHeader new_node_header;
 420                 uint new_node_num;
 421                 uchar *new_node = NewBlock (new_node_num);
 422                 ReadNodoHeader (new_node, &new_node_header);
 423                 new_node_header.level = node_header.level;
 424
 425                 node_keys = ReadKeys (node, node_header);
 426                 new_node_keys = ReadKeys (new_node, new_node_header);
 427
 428                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 429                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 430                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 431
 432                 previt = ++it;
 433
 434                 while (it != node_keys.end ()) {
 435                         BTreeData *datait;
 436                         datait = (*it);
 437                         if (header.tree_type == TYPE_IDENTIFICACION) {
 438                                 /* Verifico que la clave no existea ya en el arbol */
 439                                 if ((*data) == (*datait)) {
 440                                         throw new AddException ();
 441                                         return NULL;
 442                                 }
 443                         }
 444                         if ((*data) < (*datait))
 445                                 /* Me pase, lo agrego aca! */
 446                                 break;
 447                         previt = it;
 448                         it++;
 449                 }
 450                 if (it != node_keys.end ())
 451                         node_keys.insert (it, data);
 452                 else
 453                         node_keys.push_back (data);
 454
 455                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 456                  * y subir la clave del medio */
 457                 node_header.item_count = 0;
 458                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 459
 460                 uint total_size = 0;
 461                 it = node_keys.begin ();
 462                 while (it != node_keys.end ()) {
 463                         BTreeData *datait;
 464                         datait = (*it);
 465                         total_size += datait->Size ();
 466                         it++;
 467                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 468                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 469                          * puede tener en el caso de claves de long. variable
 470                          */
 471                         if (it == node_keys.end ())
 472                                 total_size -= datait->Size ();
 473                 }
 474
 475                 it = node_keys.begin ();
 476                 uint used = 0;
 477                 while (used < total_size/2) {
 478                         BTreeData *d = (*it);
 479                         old_node_keys.push_back (d);
 480                         used += d->Size ();
 481                         it++;
 482                 }
 483                 kout = (*it)->GetKey (); // Esta se retorna al "padre" para que se la agregue
 484
 485                 new_node_keys.push_back ( new BTreeChildData ((*it)->GetChild ()));
 486                 it++;
 487                 while (it != node_keys.end ()) {
 488                         BTreeData *d = (*it);
 489                         new_node_keys.push_back (d);
 490                         it++;
 491                 }
 492
 493                 /* Guardo */
 494                 WriteKeys (node, node_header, old_node_keys);
 495                 WriteNodoHeader (node, &node_header);
 496                 WriteBlock (node, node_num);
 497                 WriteKeys (new_node, new_node_header, new_node_keys);
 498                 WriteNodoHeader (new_node, &new_node_header);
 499                 WriteBlock (new_node, new_node_num);
 500                 DeleteKeys (old_node_keys);
 501                 DeleteKeys (new_node_keys);
 502
 503                 PrintNode (node_num);
 504                 PrintNode (new_node_num);
 505
 506                 /* Paso los hijos */
 507                 left_child = node_num;
 508                 right_child = new_node_num;
 509                 delete [] new_node;
 510                 delete [] node;
 511         }
 512
 513         return kout;
 514 }
 515
 516 void BTree::DelKey (const Clave &k)
 517 {
 518         std::string s = k;
 519         std::cout << "========= Borrando " << s << " =================\n";
 520         BTreeData *b = new BTreeLeafData (k.Clone ());
 521         DelKeyR (b, 0, 0);
 522         delete b;
 523 }
 524
 525 void BTree::DelKeyR (BTreeData *k, uint node_num, uint padre)
 526 {
 527         std::list<BTreeData *> node_keys;
 528         BTreeNodeHeader node_header;
 529         uchar *node;
 530
 531         node = ReadBlock (node_num);
 532         ReadNodoHeader (node, &node_header);
 533         node_keys = ReadKeys (node, node_header);
 534
 535         std::list<BTreeData *>::iterator it = node_keys.begin ();
 536         std::list<BTreeData *>::iterator ultima;
 537         std::list<BTreeData *>::iterator posterior;
 538
 539         BTreeData *lchild;
 540         if (node_header.level != 0) {
 541                 lchild = (*it++);
 542         }
 543         posterior = it;
 544
 545         while (it != node_keys.end ()) {
 546                 if ((*k) == (*(*it))) {
 547                         /* La encontre!, retorno */
 548                         if (node_header.level == 0) {
 549                                 DelKeyFromLeaf (k->GetKey (), node_num, padre);
 550                         } else {
 551                                 uint left, right;
 552                                 if (it == posterior) {
 553                                         left = lchild->GetChild ();
 554                                         right = (*it)->GetChild ();
 555                                 } else {
 556                                         left = (*ultima)->GetChild ();
 557                                         right = (*it)->GetChild ();
 558                                 }
 559                                 std::cout << "Eliminar de Nodo con hijos : " << left << " y " << right << std::endl;
 560                                 DelKeyFromNode (k->GetKey (), node_num, padre, left, right);
 561                         }
 562                         DeleteKeys (node_keys);
 563                         delete [] node;
 564                         return;
 565                 }
 566
 567                 if ((*k) < (*(*it)))
 568                         break;
 569                 ultima = it;
 570                 it++;
 571         }
 572
 573         /* Si llego aca y estoy en nivel 0 (una hoja) quiere
 574          * decir que no lo encontre
 575          */
 576         if (node_header.level == 0) {
 577                 std::cout << "*** Clave no encontrada ***\n";
 578                 return;
 579         }
 580
 581         /* TODO: Aca faltaria liberar memoria */
 582         if (it == posterior) {
 583                 DelKeyR (k, lchild->GetChild (), node_num);
 584         } else {
 585                 DelKeyR (k, (*ultima)->GetChild (), node_num);
 586         }
 587 }
 588
 589 void BTree::DelKeyFromLeaf (Clave *k, uint node_num, uint padre)
 590 {
 591         BTreeData *data;
 592         uchar *node;
 593         BTreeNodeHeader node_header;
 594         std::list<BTreeData *> node_keys;
 595
 596         node = ReadBlock (node_num);
 597         ReadNodoHeader (node, &node_header);
 598         node_keys = ReadKeys (node, node_header);
 599
 600         data = new BTreeLeafData (k->Clone ());
 601
 602         std::list<BTreeData *>::iterator it;
 603         it = node_keys.begin ();
 604         while (it != node_keys.end ()) {
 605                 if ((*data) == (*(*it))) {
 606                         BTreeData *aborrar = (*it);
 607                         node_keys.erase (it);
 608                         deleted_block_data.push_back (aborrar->GetKey ()->GetBlockData ());
 609                         delete aborrar;
 610                         break;
 611                 }
 612                 it++;
 613         }
 614
 615         delete data;
 616
 617         WriteKeys (node, node_header, node_keys);
 618         WriteNodoHeader (node, &node_header);
 619         WriteBlock (node, node_num);
 620
 621         /* Veo si se cumple la condición de minimalidad */
 622         uint min_free = (header.block_size-sizeof(BTreeNodeHeader))/2;
 623         if ((node_header.free_space > min_free) && (node_num != 0)) {
 624                 /* Oops! Debo pedir prestada clave */
 625                 uint hi, hd;
 626                 Clave *pedida;
 627
 628                 FindBrothers (node_num, padre, hi, hd);
 629
 630                 if ((pedida = GetKey (hi, 1)) != NULL) {
 631                         std::string s = *pedida;
 632                         std::cout << "Clave Pedida : " << s << std::endl;
 633
 634                         pedida = ReplaceKeyInFather (node_num, padre, pedida);
 635
 636                         node_keys.insert (node_keys.begin (), new BTreeLeafData (pedida));
 637                 } else if ((pedida = GetKey (hd, 0)) != NULL) {
 638                         std::string s = *pedida;
 639                         std::cout << "Clave Pedida : " << s << std::endl;
 640
 641                         pedida = ReplaceKeyInFather (node_num, padre, pedida);
 642
 643                         node_keys.push_back (new BTreeLeafData (pedida));
 644                 } else {
 645                         std::cout << "NADIE ME PUEDE PRESTAR, FUNDIR NODOS\n";
 646                         uint join1, join2;
 647                         int tipoh;
 648                         if (hi != 0) {
 649                                 std::cout << "Join con Hermano Izquierdo\n";
 650                                 join1 = hi;
 651                                 join2 = node_num;
 652                                 tipoh = 0;
 653                         } else {
 654                                 std::cout << "Join con Hermano Derecho\n";
 655                                 join1 = node_num;
 656                                 join2 = hd;
 657                                 tipoh = 1;
 658                         }
 659
 660                         JoinNodes (join1, join2, padre, tipoh);
 661
 662                         DeleteKeys (node_keys);
 663                         delete [] node;
 664                         return;
 665                 }
 666
 667                 WriteKeys (node, node_header, node_keys);
 668                 WriteNodoHeader (node, &node_header);
 669                 WriteBlock (node, node_num);
 670         }
 671
 672         DeleteKeys (node_keys);
 673         delete [] node;
 674         std::cout << "Borrado de una hoja listo\n";
 675 }
 676
 677 void BTree::JoinNodes (uint node1, uint node2, uint padre, int tipohermano)
 678 {
 679         uchar *n1, *n2, *npadre;
 680         BTreeNodeHeader nh1, nh2, nhp;
 681         std::list<BTreeData *> nk1, nk2, nkpadre;
 682
 683         if (node1 == node2) {
 684                 std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n";
 685                 exit (1);
 686         }
 687         if (node1 == padre) {
 688                 std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n";
 689                 exit (1);
 690         }
 691         if (node2 == padre) {
 692                 std::cout << "PANIC : No puedo juntar el mismo nodo con si mismo!!\n";
 693                 exit (1);
 694         }
 695
 696         PrintNode (padre);
 697         PrintNode (node1);
 698         PrintNode (node2);
 699
 700         /* Leo los nodos */
 701         n1 = ReadBlock (node1);
 702         n2 = ReadBlock (node2);
 703         npadre = ReadBlock (padre);
 704
 705         ReadNodoHeader (n1, &nh1);
 706         ReadNodoHeader (n2, &nh2);
 707         ReadNodoHeader (npadre, &nhp);
 708
 709         /* Apunto de Unir */
 710         uint tmp = header.block_size - sizeof (BTreeNodeHeader);
 711         uint l = tmp - nh1.free_space;
 712         l += tmp - nh1.free_space;
 713         l += 4;
 714
 715         std::cout << "Espacio ocupado despues de unir : " << l << " de " << tmp << std::endl;
 716
 717         nk1 = ReadKeys (n1, nh1);
 718         nk2 = ReadKeys (n2, nh2);
 719         nkpadre = ReadKeys (npadre, nhp);
 720
 721         /* Busco la clave del padre a juntar con los nodos */
 722         std::list<BTreeData *>::iterator it = nkpadre.begin ();
 723         std::list<BTreeData *>::iterator borrar_padre;
 724         std::list<BTreeData *>::iterator sig;
 725         std::list<BTreeData *>::iterator anterior = it;
 726
 727         Clave *cpadre;
 728         BTreeData *lchild = (*it++);
 729
 730         if (lchild->GetChild () == node1) {
 731                 cpadre = (*it)->GetKey ();
 732                 borrar_padre = it;
 733         } else {
 734                 while (it != nkpadre.end ()) {
 735                         if (tipohermano == 0) {
 736                                 if ((*it)->GetChild () == node2)
 737                                         break;
 738                         } else {
 739                                 if ((*it)->GetChild () == node1)
 740                                         break;
 741                         }
 742                         anterior = it;
 743                         it++;
 744                 }
 745                 cpadre = (*it)->GetKey ();
 746                 borrar_padre = it;
 747         }
 748         if (it == nkpadre.end ()) {
 749                 std::cout << "PANIC : Me pase sin encontrar la clave!!\n";
 750                 exit(1);
 751         }
 752         it++;
 753         sig = it;
 754
 755         std::list<BTreeData *> newkeys;
 756         std::list<BTreeData *>::iterator i;
 757
 758         i = nk1.begin ();
 759         while (i != nk1.end ()) {
 760                 newkeys.push_back ( new BTreeLeafData ((*i)->GetKey ()->Clone ()));
 761                 i++;
 762         }
 763         //if (tipohermano == 0)
 764                 newkeys.push_back ( new BTreeLeafData (cpadre->Clone ()));
 765         i = nk2.begin ();
 766         while (i != nk2.end ()) {
 767                 newkeys.push_back ( new BTreeLeafData ((*i)->GetKey ()->Clone ()));
 768                 i++;
 769         }
 770
 771         std::cout << "Espacio ocupado por las nuevas claves : " << (newkeys.size()*4) << std::endl;
 772         if ((newkeys.size()*4) > tmp) {
 773                 std::cout << "PANIC : El nodo fundido no entra !!!\n";
 774                 exit (1);
 775         }
 776
 777         /* Para el padre, tener 2 items significa tener solo 1 clave, ya que
 778          * el otro item es el LeftChild!
 779          */
 780         if ((padre == 0) && (nhp.item_count == 2)) {
 781                 /* Si junte 2 nodos, cuyo padre era la raiz, y esta tenia
 782                  * solo una clave, quiere decir que lo que me queda
 783                  * es de nuevo solo una raiz con todas las claves
 784                  */
 785                 nhp.level = 0;
 786                 WriteKeys (npadre, nhp, newkeys);
 787                 WriteNodoHeader (npadre, &nhp);
 788                 WriteBlock (npadre, padre);
 789
 790                 deleted_nodes.push_back (node1);
 791                 deleted_nodes.push_back (node2);
 792         } else {
 793                 WriteKeys (n1, nh1, newkeys);
 794                 WriteNodoHeader (n1, &nh1);
 795                 WriteBlock (n1, node1);
 796
 797                 deleted_nodes.push_back (node2);
 798
 799                 /* Actualizo punero al padre */
 800                 (*anterior)->SetChild (node1);
 801
 802                 nkpadre.erase (borrar_padre);
 803                 WriteKeys (npadre, nhp, nkpadre);
 804                 WriteNodoHeader (npadre, &nhp);
 805                 WriteBlock (npadre, padre);
 806         }
 807
 808         std::cout << " ----- Luego de Fundir -----\n";
 809         PrintNode (node1);
 810         PrintNode (padre);
 811         std::cout << " ---------------------------\n";
 812
 813         DeleteKeys (nk1);
 814         DeleteKeys (nk2);
 815         DeleteKeys (nkpadre);
 816         DeleteKeys (newkeys);
 817
 818         delete [] n1;
 819         delete [] n2;
 820         delete [] npadre;
 821 }
 822
 823 Clave *BTree::GetKey (uint node_num, char maxmin)
 824 {
 825         if (node_num == 0) {
 826                 std::cout << "Nodo no me puede prestar ... es NULL\n";
 827                 return NULL;
 828         }
 829
 830         uchar *node;
 831         BTreeNodeHeader node_header;
 832         std::list<BTreeData *> node_keys;
 833
 834         node = ReadBlock (node_num);
 835         ReadNodoHeader (node, &node_header);
 836         node_keys = ReadKeys (node, node_header);
 837
 838         std::list<BTreeData *>::iterator it = node_keys.begin ();
 839
 840         if (node_header.level != 0) it++;
 841
 842         Clave *k;
 843         uint free = node_header.free_space; // + (*it)->Size ();
 844         uint min_free = (header.block_size - sizeof (BTreeNodeHeader))/2;
 845         if (free > min_free) {
 846                 std::cout << "No puedo prestar : Free = " << free << "  Minimo = " << min_free << std::endl;
 847                 PrintNode (node_num);
 848                 WriteKeys (node, node_header, node_keys);
 849                 WriteNodoHeader (node, &node_header);
 850                 WriteBlock (node, node_num);
 851                 DeleteKeys (node_keys);
 852
 853                 delete [] node;
 854
 855                 return NULL;
 856         }
 857
 858         if (maxmin == 0) {
 859                 k = (*it)->GetKey ()->Clone ();
 860                 node_keys.erase (it);
 861         } else {
 862                 it = node_keys.end ();
 863                 it--;
 864                 k = (*it)->GetKey ()->Clone ();
 865                 node_keys.erase (it);
 866         }
 867
 868         WriteKeys (node, node_header, node_keys);
 869         WriteNodoHeader (node, &node_header);
 870         WriteBlock (node, node_num);
 871         DeleteKeys (node_keys);
 872
 873         delete [] node;
 874
 875         return k;
 876 }
 877
 878 void BTree::FindBrothers (uint node_num, uint padre, uint &left, uint &right)
 879 {
 880         uchar *node;
 881         BTreeNodeHeader node_header;
 882         std::list<BTreeData *> node_keys;
 883
 884         node = ReadBlock (padre);
 885         ReadNodoHeader (node, &node_header);
 886         node_keys = ReadKeys (node, node_header);
 887
 888         std::list<BTreeData *>::iterator it = node_keys.begin ();
 889         std::list<BTreeData *>::iterator anterior = node_keys.begin ();
 890         std::list<BTreeData *>::iterator siguiente;
 891
 892         BTreeData *lchild = (*it++);
 893
 894         if (lchild->GetChild () == node_num) {
 895                 /* Solo tengo hermano derecho */
 896                 std::cout << "Hermano Izquierdo : NO TENGO" << std::endl;
 897                 left = 0;
 898                 std::cout << "Hermano Derecho   : " << (*it)->GetChild () << std::endl;
 899                 right = (*it)->GetChild ();
 900                 return;
 901         }
 902
 903         while (it != node_keys.end ()) {
 904                 if ((*it)->GetChild () == node_num)
 905                         break;
 906                 anterior = it;
 907                 it++;
 908         }
 909         siguiente = it++;
 910
 911         std::cout << "Hermano Izquierdo : " << (*anterior)->GetChild () << std::endl;
 912         left = (*anterior)->GetChild ();
 913         if (siguiente != node_keys.end ()) {
 914                 right = (*siguiente)->GetChild ();
 915                 std::cout << "Hermano Derecho   : " << (*siguiente)->GetChild () << std::endl;
 916         } else {
 917                 right = 0;
 918                 std::cout << "Hermano Derecho   : NO TENGO" << std::endl;
 919         }
 920 }
 921
 922 Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k)
 923 {
 924         uchar *node;
 925         BTreeNodeHeader node_header;
 926         std::list<BTreeData *> node_keys;
 927
 928         node = ReadBlock (padre);
 929         ReadNodoHeader (node, &node_header);
 930         node_keys = ReadKeys (node, node_header);
 931
 932         std::list<BTreeData *>::iterator it = node_keys.begin ();
 933         std::list<BTreeData *>::iterator anterior = node_keys.begin ();
 934         std::list<BTreeData *>::iterator siguiente;
 935
 936         BTreeData *lchild = (*it++);
 937
 938         if (lchild->GetChild () == node_num) {
 939                 Clave *ret = (*it)->GetKey ();
 940                 (*it)->SetKey (k);
 941
 942                 WriteKeys (node, node_header, node_keys);
 943                 WriteNodoHeader (node, &node_header);
 944                 WriteBlock (node, padre);
 945                 DeleteKeys (node_keys);
 946
 947                 delete [] node;
 948                 return ret;
 949         }
 950
 951         while (it != node_keys.end ()) {
 952                 if ((*it)->GetChild () == node_num)
 953                         break;
 954                 anterior = it;
 955                 it++;
 956         }
 957
 958         Clave *ret = (*it)->GetKey ();
 959         (*it)->SetKey (k);
 960
 961         WriteKeys (node, node_header, node_keys);
 962         WriteNodoHeader (node, &node_header);
 963         WriteBlock (node, padre);
 964         DeleteKeys (node_keys);
 965
 966         delete [] node;
 967         return ret;
 968 }
 969
 970 void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right)
 971 {
 972         uint padre_hijo;
 973         uchar *node;
 974         BTreeNodeHeader node_header;
 975         std::list<BTreeData *> node_keys;
 976
 977         node = ReadBlock (node_num);
 978         ReadNodoHeader (node, &node_header);
 979         node_keys = ReadKeys (node, node_header);
 980
 981         if (right != 0) {
 982                 std::cout << "Busco para la derecha y luego todo a la izquierda\n";
 983                 uchar *node_r;
 984                 BTreeNodeHeader node_hr;
 985                 std::list<BTreeData *> node_keyr;
 986
 987                 /* Busco la clave inmediatamente superior en el arbol */
 988                 padre_hijo = node_num;
 989                 do {
 990                         node_r = ReadBlock (right);
 991                         ReadNodoHeader (node_r, &node_hr);
 992                         if (node_hr.level != 0) {
 993                                 BTreeData *data_r;
 994                                 node_keyr = ReadKeys (node_r, node_hr);
 995                                 data_r = *(node_keyr.begin ());
 996                                 padre_hijo = right;
 997                                 right = data_r->GetChild ();
 998
 999                                 DeleteKeys (node_keyr);
1000                                 delete [] node_r;
1001                         }
1002                 } while (node_hr.level != 0);
1003
1004                 std::cout << "Voy a reemplazar en el nodo " << right << std::endl;
1005
1006                 /* Reemplazo la clave a borrar por la de la hoja */
1007                 node_keyr = ReadKeys (node_r, node_hr);
1008                 BTreeData *reemplazar = *(node_keyr.begin ());
1009
1010                 std::string ss = *reemplazar;
1011                 std::cout << "Voy a reemplazar por : " << ss << std::endl;
1012
1013                 BTreeData *data = new BTreeLeafData (k->Clone());
1014
1015                 std::list<BTreeData *>::iterator it = node_keys.begin ();
1016                 while (it != node_keys.end ()) {
1017                         std::string ss1, ss2;
1018                         ss1 = *data;
1019                         ss2 = *(*it);
1020                         std::cout << ss1 << " == " << ss2 << std::endl;
1021                         if ((*data) == (*(*it))) {
1022                                 break;
1023                         }
1024                         it++;
1025                 }
1026                 if (it == node_keys.end ()) {
1027                         std::cout << "PANIC : No encontre la clave en el nodo!!!!\n";
1028                         std::string s = *data;
1029                         std::cout << s << std::endl;
1030                         PrintNode (node_num);
1031                         exit (1);
1032                 }
1033                 (*it)->SetKey (reemplazar->GetKey ());
1034                 reemplazar->SetKey (k->Clone ());
1035
1036                 std::cout << "Tengo todo reemplazado ...\n";
1037
1038                 /* Grabo los nodos */
1039                 WriteKeys (node, node_header, node_keys);
1040                 WriteNodoHeader (node, &node_header);
1041                 WriteBlock (node, node_num);
1042                 DeleteKeys (node_keys);
1043                 delete [] node;
1044
1045                 WriteKeys (node_r, node_hr, node_keyr);
1046                 WriteNodoHeader (node_r, &node_hr);
1047                 WriteBlock (node_r, right);
1048                 DeleteKeys (node_keyr);
1049                 delete [] node_r;
1050
1051                 std::cout << "Grabe todo en disco ...\n";
1052                 PrintNode (node_num);
1053                 PrintNode (right);
1054                 /* Ahora debo eliminar la clave que puse en el nodo hoja */
1055                 std::cout << "Borro la clave desde la hoja!\n";
1056
1057                 DelKeyFromLeaf (k, right, padre_hijo);
1058
1059                 std::cout << "Listo, Listo!\n";
1060         } else if (left != 0) {
1061                 std::cout << "PANIC : Deberia poder reemplazar en la derecha!!!!!\n";
1062                 exit (1);
1063         } else {
1064                 std::cout << "PANIC : No tengo hijos para reemplazar!!!!\n";
1065                 exit (1);
1066         }
1067 }
1068
1069 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
1070 {
1071         memcpy (header, node, sizeof (BTreeNodeHeader));
1072 }
1073
1074 void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
1075 {
1076         memcpy (node, header, sizeof (BTreeNodeHeader));
1077 }
1078
1079 uchar *BTree::ReadBlock (uint num)
1080 {
1081         /* Como el bloque 0 se usa para el header, el Nodo "num"
1082          * está en el bloque "num+1"
1083          */
1084         num++;
1085
1086         uchar *out = new uchar[header.block_size];
1087
1088         fseek (fp, num*header.block_size, SEEK_SET);
1089         fread (out, 1, header.block_size, fp);
1090
1091         return out;
1092 }
1093
1094 std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header)
1095 {
1096         std::list<BTreeData *> keys;
1097         node += sizeof (BTreeNodeHeader);
1098         uint count = node_header.item_count;
1099
1100         if (node_header.item_count == 0) return keys;
1101
1102         if (node_header.level != 0) {
1103                 /* Si no es una hoja, lo primero que tengo es un BTreeChildData */
1104                 BTreeChildData *d = new BTreeChildData (node);
1105                 node += d->Size ();
1106                 keys.push_back (d);
1107                 count--;
1108         }
1109
1110         for (uint i=0; i<count; i++) {
1111                 BTreeData *data;
1112                 if (node_header.level == 0) {
1113                         data = new BTreeLeafData (node, header.key_type);
1114                 } else {
1115                         data = new BTreeData (node, header.key_type);
1116                 }
1117                 node += data->Size ();
1118                 keys.push_back (data);
1119         }
1120
1121         DeAbrevKey (keys);
1122         return keys;
1123 }
1124
1125 void BTree::AbrevKey (std::list<BTreeData *> &lst)
1126 {
1127         /* Claves Fijas No se abrevian */
1128         if (header.key_type == KEY_FIXED) return;
1129
1130         BTreeData *primera = NULL;
1131         std::list<BTreeData *>::iterator it = lst.begin ();
1132
1133         while (it != lst.end ()) {
1134                 if ((*it)->Abrev (primera) == false)
1135                         primera = (*it);
1136                 it++;
1137         }
1138 }
1139
1140 void BTree::DeAbrevKey (std::list<BTreeData *> &lst)
1141 {
1142         /* Claves Fijas No se abrevian */
1143         if (header.key_type == KEY_FIXED) return;
1144
1145         BTreeData *primera = NULL;
1146         std::list<BTreeData *>::iterator it = lst.begin ();
1147
1148         while (it != lst.end ()) {
1149                 if ((*it)->DesAbrev (primera) == false)
1150                         primera = (*it);
1151                 it++;
1152         }
1153 }
1154
1155 void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys)
1156 {
1157         AbrevKey (keys);
1158
1159         std::list<BTreeData *>::iterator it = keys.begin ();
1160
1161         node += sizeof (BTreeNodeHeader);
1162
1163         node_header.item_count = 0;
1164         node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
1165
1166         uint acumulado = 0;
1167         while (it != keys.end ()) {
1168                 BTreeData *d = (*it);
1169                 uchar *n = d->ToArray ();
1170                 acumulado += d->Size ();
1171                 //std::cout << "WriteKeys :: Acumulado = " << acumulado << std::endl;
1172                 memcpy (node, n, d->Size ());
1173                 delete [] n;
1174                 node += d->Size ();
1175                 node_header.free_space -= d->Size ();
1176                 node_header.item_count++;
1177                 it++;
1178         }
1179
1180         DeAbrevKey (keys);
1181 }
1182
1183 void BTree::PrintNode (uint num)
1184 {
1185         uchar *node = ReadBlock (num);
1186         BTreeNodeHeader node_header;
1187         ReadNodoHeader (node, &node_header);
1188
1189         std::list<BTreeData *> node_keys = ReadKeys (node, node_header);
1190         std::list<BTreeData *>::iterator it = node_keys.begin ();
1191
1192         std::cout << "Nodo  : " << num << std::endl;
1193         std::cout << "Level : " << node_header.level << std::endl;
1194         std::cout << "Items : " << node_header.item_count << std::endl;
1195         std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
1196         while (it != node_keys.end ()) {
1197                 std::string s = *(*it);
1198                 std::cout << s << " ";
1199                 it++;
1200         }
1201         std::cout << std::endl;
1202
1203         delete [] node;
1204         DeleteKeys (node_keys);
1205 }
1206
1207 uchar *BTree::NewBlock (uint &num)
1208 {
1209         long filelen;
1210         uchar *node;
1211         BTreeNodeHeader nh;
1212
1213         std::list<uint>::iterator it;
1214
1215         if (deleted_nodes.size ()) {
1216                 it = deleted_nodes.begin ();
1217                 num = *it;
1218                 deleted_nodes.erase (it);
1219         } else {
1220                 fseek (fp, 0, SEEK_END);
1221                 filelen = ftell (fp);
1222
1223                 num = filelen/header.block_size - 1;
1224         }
1225         node = new uchar[header.block_size];
1226         ReadNodoHeader (node, &nh);
1227         nh.level = 0;
1228         nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
1229         nh.item_count = 0;
1230         WriteNodoHeader (node, &nh);
1231         WriteBlock (node, num);
1232
1233         return node;
1234 }
1235
1236 BTreeFindResult *BTree::FindKey (const Clave &k)
1237 {
1238         return FindKeyR (&k, 0);
1239 }
1240
1241 BTreeFindResult *BTree::FindKeyR (const Clave *k, uint node_num)
1242 {
1243         std::list<BTreeData *> node_keys;
1244         BTreeNodeHeader node_header;
1245
1246         /* Leo el nodo raiz para empezar a agregar */
1247         uchar *node = ReadBlock (node_num);
1248         ReadNodoHeader (node, &node_header);
1249         node_keys = ReadKeys (node, node_header);
1250
1251         std::list<BTreeData *>::iterator it = node_keys.begin ();
1252         std::list<BTreeData *>::iterator posterior;
1253         std::list<BTreeData *>::iterator ultima;
1254
1255         /* Se supone que la primera es un hijo :) */
1256         BTreeData *lchild;
1257         if (node_header.level != 0) {
1258                 lchild = (*it++);
1259         }
1260         posterior = it;
1261
1262         BTreeData *data;
1263         if (node_header.level == 0)
1264                 data = new BTreeLeafData (k->Clone ());
1265         else
1266                 data = new BTreeData (k->Clone (), 0);
1267
1268         while (it != node_keys.end ()) {
1269                 if ((*data) == (*(*it))) {
1270                         /* La encontre!, retorno */
1271                         delete data;
1272                         delete [] node;
1273                         DeleteKeys (node_keys);
1274                         BTreeFindResult *result = new BTreeFindResult ();
1275                         result->node = node_num;
1276                         result->header = node_header;
1277
1278                         return result;
1279                 }
1280
1281                 if ((*data) < (*(*it)))
1282                         break;
1283                 ultima = it;
1284                 it++;
1285         }
1286
1287         delete data;
1288
1289         /* Si llego aca y estoy en nivel 0 (una hoja) quiere
1290          * decir que no lo encontré
1291          */
1292         if (node_header.level == 0) {
1293                 DeleteKeys (node_keys);
1294                 delete [] node;
1295                 return NULL;
1296         }
1297
1298         /* TODO: Aca faltaria liberar memoria */
1299         BTreeFindResult *ret;
1300         if (it == posterior)
1301                 ret = FindKeyR (k, lchild->GetChild ());
1302         else
1303                 ret = FindKeyR (k, (*ultima)->GetChild ());
1304
1305         DeleteKeys (node_keys);
1306         delete [] node;
1307         return ret;
1308 }
1309
1310 void BTree::DeleteKeys (std::list<BTreeData *> &keys)
1311 {
1312         std::list<BTreeData *>::iterator it = keys.begin ();
1313
1314         while (it != keys.end ()) {
1315                 BTreeData *d = (*it);
1316                 delete d;
1317                 it++;
1318         }
1319 }
1320
1321 int BTree::type () const
1322 {
1323         return header.key_type;
1324 }
1325
1326 uint BTree::GetNextBlockData ()
1327 {
1328         uint n;
1329         if (deleted_block_data.size ()) {
1330                 std::list<uint>::iterator it = deleted_block_data.begin ();
1331                 n = *it;
1332                 deleted_block_data.erase (it);
1333         } else {
1334                 n = header.block_data_counter++;
1335         }
1336
1337         return n;
1338 }
1339