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