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