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