src/btree.cpp

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