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         key_type = kt;
   7         tree_type = tt;
   8         uchar *node;
   9         BTreeNodeHeader nh;
  10
  11         fp = fopen (name.c_str(), "wb+");
  12         if (!fp) {
  13                 /* TODO : mandar una exception ? */
  14                 return;
  15         }
  16
  17         /* Nombre de archivo */
  18         filename = name;
  19
  20         /* Inicializo el header */
  21         header.block_size = block_size;
  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 (tree_type == TYPE_UNIQUE) {
 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 (tree_type == TYPE_UNIQUE) {
 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 (tree_type == TYPE_UNIQUE) {
 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 (tree_type == TYPE_UNIQUE) {
 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 (tree_type == TYPE_UNIQUE) {
 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          /* TODO: Recuperar nodo1 y nodo2 */
 718         } else {
 719                 WriteKeys (n1, nh1, newkeys);
 720                 WriteNodoHeader (n1, &nh1);
 721                 WriteBlock (n1, node1);
 722
 723                 /* TODO : Recuperar node2 */
 724                 /* Actualizo punero al padre */
 725                 (*anterior)->SetChild (node1);
 726
 727                 nkpadre.erase (borrar_padre);
 728                 WriteKeys (npadre, nhp, nkpadre);
 729                 WriteNodoHeader (npadre, &nhp);
 730                 WriteBlock (npadre, padre);
 731         }
 732
 733         std::cout << " ----- Luego de Fundir -----\n";
 734         PrintNode (node1);
 735         PrintNode (padre);
 736         std::cout << " ---------------------------\n";
 737
 738         DeleteKeys (nk1);
 739         DeleteKeys (nk2);
 740         DeleteKeys (nkpadre);
 741         DeleteKeys (newkeys);
 742
 743         delete [] n1;
 744         delete [] n2;
 745         delete [] npadre;
 746 }
 747
 748 Clave *BTree::GetKey (uint node_num, char maxmin)
 749 {
 750         if (node_num == 0) {
 751                 std::cout << "Nodo no me puede prestar ... es NULL\n";
 752                 return NULL;
 753         }
 754
 755         uchar *node;
 756         BTreeNodeHeader node_header;
 757         std::list<BTreeData *> node_keys;
 758
 759         node = ReadBlock (node_num);
 760         ReadNodoHeader (node, &node_header);
 761         node_keys = ReadKeys (node, node_header);
 762
 763         std::list<BTreeData *>::iterator it = node_keys.begin ();
 764
 765         if (node_header.level != 0) it++;
 766
 767         Clave *k;
 768         uint free = node_header.free_space; // + (*it)->Size ();
 769         uint min_free = (header.block_size - sizeof (BTreeNodeHeader))/2;
 770         if (free > min_free) {
 771                 std::cout << "No puedo prestar : Free = " << free << "  Minimo = " << min_free << std::endl;
 772                 PrintNode (node_num);
 773                 WriteKeys (node, node_header, node_keys);
 774                 WriteNodoHeader (node, &node_header);
 775                 WriteBlock (node, node_num);
 776                 DeleteKeys (node_keys);
 777
 778                 delete [] node;
 779
 780                 return NULL;
 781         }
 782
 783         if (maxmin == 0) {
 784                 k = (*it)->GetKey ()->Clone ();
 785                 node_keys.erase (it);
 786         } else {
 787                 it = node_keys.end ();
 788                 it--;
 789                 k = (*it)->GetKey ()->Clone ();
 790                 node_keys.erase (it);
 791         }
 792
 793         WriteKeys (node, node_header, node_keys);
 794         WriteNodoHeader (node, &node_header);
 795         WriteBlock (node, node_num);
 796         DeleteKeys (node_keys);
 797
 798         delete [] node;
 799
 800         return k;
 801 }
 802
 803 void BTree::FindBrothers (uint node_num, uint padre, uint &left, uint &right)
 804 {
 805         uchar *node;
 806         BTreeNodeHeader node_header;
 807         std::list<BTreeData *> node_keys;
 808
 809         node = ReadBlock (padre);
 810         ReadNodoHeader (node, &node_header);
 811         node_keys = ReadKeys (node, node_header);
 812
 813         std::list<BTreeData *>::iterator it = node_keys.begin ();
 814         std::list<BTreeData *>::iterator anterior = node_keys.begin ();
 815         std::list<BTreeData *>::iterator siguiente;
 816
 817         BTreeData *lchild = (*it++);
 818
 819         if (lchild->GetChild () == node_num) {
 820                 /* Solo tengo hermano derecho */
 821                 std::cout << "Hermano Izquierdo : NO TENGO" << std::endl;
 822                 left = 0;
 823                 std::cout << "Hermano Derecho   : " << (*it)->GetChild () << std::endl;
 824                 right = (*it)->GetChild ();
 825                 return;
 826         }
 827
 828         while (it != node_keys.end ()) {
 829                 if ((*it)->GetChild () == node_num)
 830                         break;
 831                 anterior = it;
 832                 it++;
 833         }
 834         siguiente = it++;
 835
 836         std::cout << "Hermano Izquierdo : " << (*anterior)->GetChild () << std::endl;
 837         left = (*anterior)->GetChild ();
 838         if (siguiente != node_keys.end ()) {
 839                 right = (*siguiente)->GetChild ();
 840                 std::cout << "Hermano Derecho   : " << (*siguiente)->GetChild () << std::endl;
 841         } else {
 842                 right = 0;
 843                 std::cout << "Hermano Derecho   : NO TENGO" << std::endl;
 844         }
 845 }
 846
 847 Clave *BTree::ReplaceKeyInFather (uint node_num, uint padre, Clave *k)
 848 {
 849         uchar *node;
 850         BTreeNodeHeader node_header;
 851         std::list<BTreeData *> node_keys;
 852
 853         node = ReadBlock (padre);
 854         ReadNodoHeader (node, &node_header);
 855         node_keys = ReadKeys (node, node_header);
 856
 857         std::list<BTreeData *>::iterator it = node_keys.begin ();
 858         std::list<BTreeData *>::iterator anterior = node_keys.begin ();
 859         std::list<BTreeData *>::iterator siguiente;
 860
 861         BTreeData *lchild = (*it++);
 862
 863         if (lchild->GetChild () == node_num) {
 864                 Clave *ret = (*it)->GetKey ();
 865                 (*it)->SetKey (k);
 866
 867                 WriteKeys (node, node_header, node_keys);
 868                 WriteNodoHeader (node, &node_header);
 869                 WriteBlock (node, padre);
 870                 DeleteKeys (node_keys);
 871
 872                 delete [] node;
 873                 return ret;
 874         }
 875
 876         while (it != node_keys.end ()) {
 877                 if ((*it)->GetChild () == node_num)
 878                         break;
 879                 anterior = it;
 880                 it++;
 881         }
 882
 883         Clave *ret = (*it)->GetKey ();
 884         (*it)->SetKey (k);
 885
 886         WriteKeys (node, node_header, node_keys);
 887         WriteNodoHeader (node, &node_header);
 888         WriteBlock (node, padre);
 889         DeleteKeys (node_keys);
 890
 891         delete [] node;
 892         return ret;
 893 }
 894
 895 void BTree::DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right)
 896 {
 897         uint padre_hijo;
 898         uchar *node;
 899         BTreeNodeHeader node_header;
 900         std::list<BTreeData *> node_keys;
 901
 902         node = ReadBlock (node_num);
 903         ReadNodoHeader (node, &node_header);
 904         node_keys = ReadKeys (node, node_header);
 905
 906         if (right != 0) {
 907                 std::cout << "Busco para la derecha y luego todo a la izquierda\n";
 908                 uchar *node_r;
 909                 BTreeNodeHeader node_hr;
 910                 std::list<BTreeData *> node_keyr;
 911
 912                 /* Busco la clave inmediatamente superior en el arbol */
 913                 padre_hijo = node_num;
 914                 do {
 915                         node_r = ReadBlock (right);
 916                         ReadNodoHeader (node_r, &node_hr);
 917                         if (node_hr.level != 0) {
 918                                 BTreeData *data_r;
 919                                 node_keyr = ReadKeys (node_r, node_hr);
 920                                 data_r = *(node_keyr.begin ());
 921                                 padre_hijo = right;
 922                                 right = data_r->GetChild ();
 923
 924                                 DeleteKeys (node_keyr);
 925                                 delete [] node_r;
 926                         }
 927                 } while (node_hr.level != 0);
 928
 929                 std::cout << "Voy a reemplazar en el nodo " << right << std::endl;
 930
 931                 /* Reemplazo la clave a borrar por la de la hoja */
 932                 node_keyr = ReadKeys (node_r, node_hr);
 933                 BTreeData *reemplazar = *(node_keyr.begin ());
 934
 935                 std::string ss = *reemplazar;
 936                 std::cout << "Voy a reemplazar por : " << ss << std::endl;
 937
 938                 BTreeData *data = new BTreeLeafData (k->Clone());
 939
 940                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 941                 while (it != node_keys.end ()) {
 942                         std::string ss1, ss2;
 943                         ss1 = *data;
 944                         ss2 = *(*it);
 945                         std::cout << ss1 << " == " << ss2 << std::endl;
 946                         if ((*data) == (*(*it))) {
 947                                 break;
 948                         }
 949                         it++;
 950                 }
 951                 if (it == node_keys.end ()) {
 952                         std::cout << "PANIC : No encontre la clave en el nodo!!!!\n";
 953                         std::string s = *data;
 954                         std::cout << s << std::endl;
 955                         PrintNode (node_num);
 956                         exit (1);
 957                 }
 958                 (*it)->SetKey (reemplazar->GetKey ());
 959                 reemplazar->SetKey (k->Clone ());
 960
 961                 std::cout << "Tengo todo reemplazado ...\n";
 962
 963                 /* Grabo los nodos */
 964                 WriteKeys (node, node_header, node_keys);
 965                 WriteNodoHeader (node, &node_header);
 966                 WriteBlock (node, node_num);
 967                 DeleteKeys (node_keys);
 968                 delete [] node;
 969
 970                 WriteKeys (node_r, node_hr, node_keyr);
 971                 WriteNodoHeader (node_r, &node_hr);
 972                 WriteBlock (node_r, right);
 973                 DeleteKeys (node_keyr);
 974                 delete [] node_r;
 975
 976                 std::cout << "Grabe todo en disco ...\n";
 977                 PrintNode (node_num);
 978                 PrintNode (right);
 979                 /* Ahora debo eliminar la clave que puse en el nodo hoja */
 980                 std::cout << "Borro la clave desde la hoja!\n";
 981
 982                 DelKeyFromLeaf (k, right, padre_hijo);
 983
 984                 std::cout << "Listo, Listo!\n";
 985         } else if (left != 0) {
 986                 std::cout << "PANIC : Deberia poder reemplazar en la derecha!!!!!\n";
 987                 exit (1);
 988         } else {
 989                 std::cout << "PANIC : No tengo hijos para reemplazar!!!!\n";
 990                 exit (1);
 991         }
 992 }
 993
 994 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
 995 {
 996         memcpy (header, node, sizeof (BTreeNodeHeader));
 997 }
 998
 999 void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
1000 {
1001         memcpy (node, header, sizeof (BTreeNodeHeader));
1002 }
1003
1004 uchar *BTree::ReadBlock (uint num)
1005 {
1006         /* Como el bloque 0 se usa para el header, el Nodo "num"
1007          * está en el bloque "num+1"
1008          */
1009         num++;
1010
1011         uchar *out = new uchar[header.block_size];
1012
1013         fseek (fp, num*header.block_size, SEEK_SET);
1014         fread (out, 1, header.block_size, fp);
1015
1016         return out;
1017 }
1018
1019 std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header)
1020 {
1021         std::list<BTreeData *> keys;
1022         node += sizeof (BTreeNodeHeader);
1023         uint count = node_header.item_count;
1024
1025         if (node_header.item_count == 0) return keys;
1026
1027         if (node_header.level != 0) {
1028                 /* Si no es una hoja, lo primero que tengo es un BTreeChildData */
1029                 BTreeChildData *d = new BTreeChildData (node);
1030                 node += d->Size ();
1031                 keys.push_back (d);
1032                 count--;
1033         }
1034
1035         for (uint i=0; i<count; i++) {
1036                 BTreeData *data;
1037                 if (node_header.level == 0) {
1038                         data = new BTreeLeafData (node, key_type);
1039                 } else {
1040                         data = new BTreeData (node, key_type);
1041                 }
1042                 node += data->Size ();
1043                 keys.push_back (data);
1044         }
1045
1046         DeAbrevKey (keys);
1047         return keys;
1048 }
1049
1050 void BTree::AbrevKey (std::list<BTreeData *> &lst)
1051 {
1052         /* Claves Fijas No se abrevian */
1053         if (key_type == KEY_FIXED) return;
1054
1055         BTreeData *primera = NULL;
1056         std::list<BTreeData *>::iterator it = lst.begin ();
1057
1058         while (it != lst.end ()) {
1059                 if ((*it)->Abrev (primera) == false)
1060                         primera = (*it);
1061                 it++;
1062         }
1063 }
1064
1065 void BTree::DeAbrevKey (std::list<BTreeData *> &lst)
1066 {
1067         /* Claves Fijas No se abrevian */
1068         if (key_type == KEY_FIXED) return;
1069
1070         BTreeData *primera = NULL;
1071         std::list<BTreeData *>::iterator it = lst.begin ();
1072
1073         while (it != lst.end ()) {
1074                 if ((*it)->DesAbrev (primera) == false)
1075                         primera = (*it);
1076                 it++;
1077         }
1078 }
1079
1080 void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys)
1081 {
1082         AbrevKey (keys);
1083
1084         std::list<BTreeData *>::iterator it = keys.begin ();
1085
1086         node += sizeof (BTreeNodeHeader);
1087
1088         node_header.item_count = 0;
1089         node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
1090
1091         uint acumulado = 0;
1092         while (it != keys.end ()) {
1093                 BTreeData *d = (*it);
1094                 uchar *n = d->ToArray ();
1095                 acumulado += d->Size ();
1096                 //std::cout << "WriteKeys :: Acumulado = " << acumulado << std::endl;
1097                 memcpy (node, n, d->Size ());
1098                 delete [] n;
1099                 node += d->Size ();
1100                 node_header.free_space -= d->Size ();
1101                 node_header.item_count++;
1102                 it++;
1103         }
1104
1105         DeAbrevKey (keys);
1106 }
1107
1108 void BTree::PrintNode (uint num)
1109 {
1110         uchar *node = ReadBlock (num);
1111         BTreeNodeHeader node_header;
1112         ReadNodoHeader (node, &node_header);
1113
1114         std::list<BTreeData *> node_keys = ReadKeys (node, node_header);
1115         std::list<BTreeData *>::iterator it = node_keys.begin ();
1116
1117         std::cout << "Nodo  : " << num << std::endl;
1118         std::cout << "Level : " << node_header.level << std::endl;
1119         std::cout << "Items : " << node_header.item_count << std::endl;
1120         std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
1121         while (it != node_keys.end ()) {
1122                 std::string s = *(*it);
1123                 std::cout << s << " ";
1124                 it++;
1125         }
1126         std::cout << std::endl;
1127
1128         delete [] node;
1129         DeleteKeys (node_keys);
1130 }
1131
1132 uchar *BTree::NewBlock (uint &num)
1133 {
1134         long filelen;
1135         uchar *node;
1136         BTreeNodeHeader nh;
1137
1138         fseek (fp, 0, SEEK_END);
1139         filelen = ftell (fp);
1140
1141         num = filelen/header.block_size - 1;
1142
1143         node = new uchar[header.block_size];
1144         ReadNodoHeader (node, &nh);
1145         nh.level = 0;
1146         nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
1147         nh.item_count = 0;
1148         WriteNodoHeader (node, &nh);
1149         WriteBlock (node, num);
1150
1151         return node;
1152 }
1153
1154 BTreeFindResult *BTree::FindKey (const Clave &k)
1155 {
1156         return FindKeyR (&k, 0);
1157 }
1158
1159 BTreeFindResult *BTree::FindKeyR (const Clave *k, uint node_num)
1160 {
1161         std::list<BTreeData *> node_keys;
1162         BTreeNodeHeader node_header;
1163
1164         /* Leo el nodo raiz para empezar a agregar */
1165         uchar *node = ReadBlock (node_num);
1166         ReadNodoHeader (node, &node_header);
1167         node_keys = ReadKeys (node, node_header);
1168
1169         std::list<BTreeData *>::iterator it = node_keys.begin ();
1170         std::list<BTreeData *>::iterator posterior;
1171         std::list<BTreeData *>::iterator ultima;
1172
1173         /* Se supone que la primera es un hijo :) */
1174         BTreeData *lchild;
1175         if (node_header.level != 0) {
1176                 lchild = (*it++);
1177         }
1178         posterior = it;
1179
1180         BTreeData *data;
1181         if (node_header.level == 0)
1182                 data = new BTreeLeafData (k->Clone ());
1183         else
1184                 data = new BTreeData (k->Clone (), 0);
1185
1186         while (it != node_keys.end ()) {
1187                 if ((*data) == (*(*it))) {
1188                         /* La encontre!, retorno */
1189                         delete data;
1190                         delete [] node;
1191                         DeleteKeys (node_keys);
1192                         BTreeFindResult *result = new BTreeFindResult ();
1193                         result->node = node_num;
1194                         result->header = node_header;
1195
1196                         return result;
1197                 }
1198
1199                 if ((*data) < (*(*it)))
1200                         break;
1201                 ultima = it;
1202                 it++;
1203         }
1204
1205         delete data;
1206
1207         /* Si llego aca y estoy en nivel 0 (una hoja) quiere
1208          * decir que no lo encontré
1209          */
1210         if (node_header.level == 0) {
1211                 DeleteKeys (node_keys);
1212                 delete [] node;
1213                 return NULL;
1214         }
1215
1216         /* TODO: Aca faltaria liberar memoria */
1217         BTreeFindResult *ret;
1218         if (it == posterior)
1219                 ret = FindKeyR (k, lchild->GetChild ());
1220         else
1221                 ret = FindKeyR (k, (*ultima)->GetChild ());
1222
1223         DeleteKeys (node_keys);
1224         delete [] node;
1225         return ret;
1226 }
1227
1228 void BTree::DeleteKeys (std::list<BTreeData *> &keys)
1229 {
1230         std::list<BTreeData *>::iterator it = keys.begin ();
1231
1232         while (it != keys.end ()) {
1233                 BTreeData *d = (*it);
1234                 delete d;
1235                 it++;
1236         }
1237 }