src/btree.cpp

   1
   2 #include "btree.h"
   3
   4 BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool create_new_file)
   5 {
   6         key_type = kt;
   7         uchar *node;
   8         BTreeNodeHeader nh;
   9
  10         fp = fopen (name.c_str(), "wb+");
  11         if (!fp) {
  12                 /* TODO : mandar una exception ? */
  13                 return;
  14         }
  15
  16         /* Nombre de archivo */
  17         filename = name;
  18
  19         /* Inicializo el header */
  20         header.block_size = block_size;
  21         WriteFileHeader ();
  22
  23         /* Creo el primer bloque vacio */
  24         node = new uchar[block_size];
  25         ReadNodoHeader (node, &nh);
  26         nh.level = 0;
  27         nh.free_space = block_size - sizeof (BTreeNodeHeader);
  28         nh.item_count = 0;
  29         WriteNodoHeader (node, &nh);
  30         WriteBlock (node, 0);
  31
  32         delete [] node;
  33 }
  34
  35 BTree::~BTree ()
  36 {
  37         fclose (fp);
  38 }
  39
  40 void BTree::WriteFileHeader ()
  41 {
  42         fseek (fp, 0L, SEEK_SET);
  43         fwrite (&header, 1, sizeof (BTreeFileHeader), fp);
  44 }
  45
  46 void BTree::WriteBlock (uchar *block, uint num)
  47 {
  48         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
  49         fwrite (block, 1, header.block_size, fp);
  50 }
  51
  52 void BTree::AddKey (const Clave &k)
  53 {
  54         uint left, right;
  55         Clave *kout = AddKeyR (k.Clone (), 0, left, right);
  56
  57         if (kout) {
  58                 unsigned short level;
  59                 /* Debo dejar la raiz en el nodo 0, por lo que paso el nodo
  60                  * que esta usando el hijo izquierdo a un nuevo nodo */
  61                 std::list<BTreeData *> node_keys;
  62                 BTreeNodeHeader node_header;
  63                 uchar *node = ReadBlock (left);
  64                 ReadNodoHeader (node, &node_header);
  65                 node_keys = ReadKeys (node, node_header);
  66                 level = node_header.level + 1;
  67
  68                 uchar *new_node = NewBlock (left);
  69                 delete [] new_node; /* No me interesa, voy a usar lo leio antes */
  70
  71                 WriteKeys (node, node_header, node_keys);
  72                 WriteNodoHeader (node, &node_header);
  73                 WriteBlock (node, left);
  74                 DeleteKeys (node_keys);
  75                 delete [] node;
  76
  77                 /* Leo y actualizo la Raiz */
  78                 node = ReadBlock (0);
  79                 ReadNodoHeader (node, &node_header);
  80                 node_keys = std::list<BTreeData *>();
  81
  82                 node_keys.push_back (new BTreeChildData (left));
  83                 node_keys.push_back (new BTreeData (kout, right));
  84
  85                 node_header.level = level;
  86                 node_header.item_count = 1;
  87
  88                 WriteKeys (node, node_header, node_keys);
  89                 WriteNodoHeader (node, &node_header);
  90                 WriteBlock (node, 0);
  91                 delete [] node;
  92                 DeleteKeys (node_keys);
  93                 PrintNode (0);
  94         }
  95 }
  96
  97 Clave* BTree::AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
  98 {
  99         uchar *node = ReadBlock (node_num);
 100         BTreeNodeHeader node_header;
 101         ReadNodoHeader (node, &node_header);
 102         delete [] node;
 103
 104         if (node_header.level == 0)
 105                 return AddKeyLeafR (k, node_num, left_child, right_child);
 106
 107         return AddKeyOtherR (k, node_num, left_child, right_child);
 108 }
 109
 110 Clave* BTree::AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 111 {
 112         Clave *kout = NULL;
 113         std::list<BTreeData *> node_keys;
 114
 115         BTreeData *data = new BTreeLeafData (k->Clone ());
 116
 117         /* Leo el nodo raiz para empezar a agregar */
 118         uchar *node = ReadBlock (node_num);
 119         BTreeNodeHeader node_header;
 120         ReadNodoHeader (node, &node_header);
 121
 122         if (node_header.free_space > data->Size ()) {
 123                 BTreeData *datait;
 124                 node_keys = ReadKeys (node, node_header);
 125                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 126
 127                 while (it != node_keys.end ()) {
 128                         datait = (*it);
 129                         if ((*data) < (*datait))
 130                                 /* Me pase, lo agrego aca! */
 131                                 break;
 132                         it++;
 133                 }
 134                 node_keys.insert (it, data);
 135                 WriteKeys (node, node_header, node_keys);
 136                 WriteNodoHeader (node, &node_header);
 137                 WriteBlock (node, node_num);
 138                 DeleteKeys (node_keys);
 139                 delete [] node;
 140
 141                 PrintNode (node_num);
 142         } else {
 143                 /* Split : Creo e inicializo el nuevo nodo */
 144                 std::list<BTreeData *> new_node_keys;
 145                 std::list<BTreeData *> old_node_keys;
 146                 BTreeNodeHeader new_node_header;
 147                 uint new_node_num;
 148                 uchar *new_node = NewBlock (new_node_num);
 149                 ReadNodoHeader (new_node, &new_node_header);
 150                 new_node_header.level = node_header.level;
 151
 152                 node_keys = ReadKeys (node, node_header);
 153                 new_node_keys = ReadKeys (new_node, new_node_header);
 154
 155                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 156                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 157                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 158
 159                 while (it != node_keys.end ()) {
 160                         BTreeData *datait;
 161                         datait = (*it);
 162                         if ((*data) < (*datait))
 163                                 /* Me pase, lo agrego aca! */
 164                                 break;
 165                         previt = it;
 166                         it++;
 167                 }
 168                 if (it != node_keys.end ())
 169                         node_keys.insert (it, data);
 170                 else
 171                         node_keys.push_back (data);
 172
 173                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 174                  * y subir la clave del medio */
 175                 node_header.item_count = 0;
 176                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 177
 178                 uint total_size = 0;
 179                 it = node_keys.begin ();
 180                 while (it != node_keys.end ()) {
 181                         BTreeData *datait;
 182                         datait = (*it);
 183                         total_size += datait->Size ();
 184                         it++;
 185                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 186                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 187                          * puede tener en el caso de claves de long. variable
 188                          */
 189                         if (it == node_keys.end ())
 190                                 total_size -= datait->Size ();
 191                 }
 192
 193                 it = node_keys.begin ();
 194                 uint used = 0;
 195                 while (used < total_size/2) {
 196                         BTreeData *d = (*it);
 197                         old_node_keys.push_back (d);
 198                         used += d->Size ();
 199                         it++;
 200                 }
 201                 kout = (*it++)->getClave (); // Esta se retorna al "padre" para que se la agregue
 202
 203                 while (it != node_keys.end ()) {
 204                         BTreeData *d = (*it);
 205                         new_node_keys.push_back (d);
 206                         it++;
 207                 }
 208
 209                 /* Guardo */
 210                 WriteKeys (node, node_header, old_node_keys);
 211                 WriteNodoHeader (node, &node_header);
 212                 WriteBlock (node, node_num);
 213                 WriteKeys (new_node, new_node_header, new_node_keys);
 214                 WriteNodoHeader (new_node, &new_node_header);
 215                 WriteBlock (new_node, new_node_num);
 216                 DeleteKeys (old_node_keys);
 217                 DeleteKeys (new_node_keys);
 218
 219                 PrintNode (node_num);
 220                 PrintNode (new_node_num);
 221
 222                 /* Paso los hijos */
 223                 left_child = node_num;
 224                 right_child = new_node_num;
 225                 delete [] new_node;
 226                 delete [] node;
 227         }
 228
 229         return kout;
 230 }
 231
 232 Clave* BTree::AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child)
 233 {
 234         Clave *kout = NULL;
 235         std::list<BTreeData *> node_keys;
 236
 237         BTreeData *data = new BTreeLeafData (k->Clone ());
 238
 239         /* Leo el nodo raiz para empezar a agregar */
 240         uchar *node = ReadBlock (node_num);
 241         BTreeNodeHeader node_header;
 242         ReadNodoHeader (node, &node_header);
 243
 244         node_keys = ReadKeys (node, node_header);
 245
 246         std::list<BTreeData *>::iterator it = node_keys.begin ();
 247         std::list<BTreeData *>::iterator posterior;
 248         std::list<BTreeData *>::iterator ultima;
 249
 250         /* Se supone que la primera es un hijo :) */
 251         BTreeData *lchild = (*it++);
 252         posterior = it;
 253
 254         while (it != node_keys.end ()) {
 255                 if ((*data) < (*(*it)))
 256                         break;
 257                 ultima = it;
 258                 it++;
 259         }
 260
 261         if (it == posterior) {
 262                 k = AddKeyR (k, lchild->getChild (), left_child, right_child);
 263         } else {
 264                 k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child);
 265         }
 266         DeleteKeys (node_keys);
 267
 268         /* Nada que hacer */
 269         if (data) delete data;
 270         if (!k) {
 271                 delete [] node;
 272                 return NULL;
 273         }
 274
 275         data = new BTreeData (k->Clone (), right_child);
 276
 277         if (node_header.free_space > data->Size ()) {
 278                 BTreeData *datait;
 279                 node_keys = ReadKeys (node, node_header);
 280                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 281
 282                 while (it != node_keys.end ()) {
 283                         datait = (*it);
 284                         if ((*data) < (*datait))
 285                                 /* Me pase, lo agrego aca! */
 286                                 break;
 287                         it++;
 288                 }
 289                 node_keys.insert (it, data);
 290                 WriteKeys (node, node_header, node_keys);
 291                 WriteNodoHeader (node, &node_header);
 292                 WriteBlock (node, node_num);
 293                 DeleteKeys (node_keys);
 294                 delete [] node;
 295
 296                 PrintNode (node_num);
 297         } else {
 298                 /* Split : Creo e inicializo el nuevo nodo */
 299                 std::list<BTreeData *> new_node_keys;
 300                 std::list<BTreeData *> old_node_keys;
 301                 BTreeNodeHeader new_node_header;
 302                 uint new_node_num;
 303                 uchar *new_node = NewBlock (new_node_num);
 304                 ReadNodoHeader (new_node, &new_node_header);
 305                 new_node_header.level = node_header.level;
 306
 307                 node_keys = ReadKeys (node, node_header);
 308                 new_node_keys = ReadKeys (new_node, new_node_header);
 309
 310                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 311                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 312                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 313
 314                 previt = ++it;
 315
 316                 while (it != node_keys.end ()) {
 317                         BTreeData *datait;
 318                         datait = (*it);
 319                         if ((*data) < (*datait))
 320                                 /* Me pase, lo agrego aca! */
 321                                 break;
 322                         previt = it;
 323                         it++;
 324                 }
 325                 if (it != node_keys.end ())
 326                         node_keys.insert (it, data);
 327                 else
 328                         node_keys.push_back (data);
 329
 330                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 331                  * y subir la clave del medio */
 332                 node_header.item_count = 0;
 333                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 334
 335                 uint total_size = 0;
 336                 it = node_keys.begin ();
 337                 while (it != node_keys.end ()) {
 338                         BTreeData *datait;
 339                         datait = (*it);
 340                         total_size += datait->Size ();
 341                         it++;
 342                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 343                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 344                          * puede tener en el caso de claves de long. variable
 345                          */
 346                         if (it == node_keys.end ())
 347                                 total_size -= datait->Size ();
 348                 }
 349
 350                 it = node_keys.begin ();
 351                 uint used = 0;
 352                 while (used < total_size/2) {
 353                         BTreeData *d = (*it);
 354                         old_node_keys.push_back (d);
 355                         used += d->Size ();
 356                         it++;
 357                 }
 358                 kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue
 359
 360                 new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ()));
 361                 it++;
 362                 while (it != node_keys.end ()) {
 363                         BTreeData *d = (*it);
 364                         new_node_keys.push_back (d);
 365                         it++;
 366                 }
 367
 368                 /* Guardo */
 369                 WriteKeys (node, node_header, old_node_keys);
 370                 WriteNodoHeader (node, &node_header);
 371                 WriteBlock (node, node_num);
 372                 WriteKeys (new_node, new_node_header, new_node_keys);
 373                 WriteNodoHeader (new_node, &new_node_header);
 374                 WriteBlock (new_node, new_node_num);
 375                 DeleteKeys (old_node_keys);
 376                 DeleteKeys (new_node_keys);
 377
 378                 PrintNode (node_num);
 379                 PrintNode (new_node_num);
 380
 381                 /* Paso los hijos */
 382                 left_child = node_num;
 383                 right_child = new_node_num;
 384                 delete [] new_node;
 385                 delete [] node;
 386         }
 387
 388         return kout;
 389 }
 390
 391 void BTree::DelKey (const Clave &k) {}
 392
 393 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
 394 {
 395         memcpy (header, node, sizeof (BTreeNodeHeader));
 396 }
 397
 398 void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
 399 {
 400         memcpy (node, header, sizeof (BTreeNodeHeader));
 401 }
 402
 403 uchar *BTree::ReadBlock (uint num)
 404 {
 405         uchar *out = new uchar[header.block_size];
 406
 407         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
 408         fread (out, 1, header.block_size, fp);
 409
 410         return out;
 411 }
 412
 413 std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header)
 414 {
 415         std::list<BTreeData *> keys;
 416         node += sizeof (BTreeNodeHeader);
 417         uint count = node_header.item_count;
 418
 419         if (node_header.item_count == 0) return keys;
 420
 421         if (node_header.level != 0) {
 422                 /* Si no es una hoja, lo primero que tengo es un BTreeChildData */
 423                 BTreeChildData *d = new BTreeChildData (node);
 424                 node += d->Size ();
 425                 keys.push_back (d);
 426                 count--;
 427         }
 428
 429         for (uint i=0; i<count; i++) {
 430                 /* TODO : El tipo de clave deberia ser usado
 431                  * dependiendo de algun dato en el header del
 432                  * arbol
 433                  */
 434                 /* TODO : Detectar si estoy en una hoja */
 435                 BTreeData *data;
 436                 if (node_header.level == 0) {
 437                         data = new BTreeLeafData (node, key_type);
 438                 } else {
 439                         data = new BTreeData (node, key_type);
 440                 }
 441                 node += data->Size ();
 442                 keys.push_back (data);
 443         }
 444
 445         return keys;
 446 }
 447
 448 void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys)
 449 {
 450         std::list<BTreeData *>::iterator it = keys.begin ();
 451
 452         node += sizeof (BTreeNodeHeader);
 453
 454         node_header.item_count = 0;
 455         node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 456
 457         while (it != keys.end ()) {
 458                 BTreeData *d = (*it);
 459                 uchar *n = d->ToArray ();
 460                 memcpy (node, n, d->Size ());
 461                 delete [] n;
 462                 node += d->Size ();
 463                 node_header.free_space -= d->Size ();
 464                 node_header.item_count++;
 465                 it++;
 466         }
 467
 468         /* TODO : incrementar node_header.item_count aca o fuera de este metodo? */
 469 }
 470
 471 void BTree::PrintNode (uint num)
 472 {
 473         uchar *node = ReadBlock (num);
 474         BTreeNodeHeader node_header;
 475         ReadNodoHeader (node, &node_header);
 476
 477         std::list<BTreeData *> node_keys = ReadKeys (node, node_header);
 478         std::list<BTreeData *>::iterator it = node_keys.begin ();
 479
 480         std::cout << "Nodo  : " << num << std::endl;
 481         std::cout << "Level : " << node_header.level << std::endl;
 482         std::cout << "Items : " << node_header.item_count << std::endl;
 483         std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
 484         while (it != node_keys.end ()) {
 485                 std::string s = *(*it);
 486                 std::cout << s << " ";
 487                 it++;
 488         }
 489         std::cout << std::endl;
 490
 491         delete [] node;
 492         DeleteKeys (node_keys);
 493 }
 494
 495 uchar *BTree::NewBlock (uint &num)
 496 {
 497         long filelen;
 498         uchar *node;
 499         BTreeNodeHeader nh;
 500
 501         fseek (fp, 0, SEEK_END);
 502         filelen = ftell (fp);
 503
 504         num = (filelen - sizeof (BTreeFileHeader))/header.block_size;
 505
 506         node = new uchar[header.block_size];
 507         ReadNodoHeader (node, &nh);
 508         nh.level = 0;
 509         nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
 510         nh.item_count = 0;
 511         WriteNodoHeader (node, &nh);
 512         WriteBlock (node, num);
 513
 514         return node;
 515 }
 516
 517 bool BTree::FindKey (const Clave &k)
 518 {
 519         return FindKeyR (&k, 0);
 520 }
 521
 522 bool BTree::FindKeyR (const Clave *k, uint node_num)
 523 {
 524         std::list<BTreeData *> node_keys;
 525         BTreeNodeHeader node_header;
 526
 527         /* Leo el nodo raiz para empezar a agregar */
 528         uchar *node = ReadBlock (node_num);
 529         ReadNodoHeader (node, &node_header);
 530         node_keys = ReadKeys (node, node_header);
 531
 532         std::list<BTreeData *>::iterator it = node_keys.begin ();
 533         std::list<BTreeData *>::iterator posterior;
 534         std::list<BTreeData *>::iterator ultima;
 535
 536         /* Se supone que la primera es un hijo :) */
 537         BTreeData *lchild;
 538         if (node_header.level != 0) {
 539                 lchild = (*it++);
 540         }
 541         posterior = it;
 542
 543         BTreeData *data;
 544         if (node_header.level == 0)
 545                 data = new BTreeLeafData ((Clave *)k);
 546         else
 547                 data = new BTreeData ((Clave *)k, 0);
 548
 549         while (it != node_keys.end ()) {
 550                 if ((*data) == (*(*it))) {
 551                         /* La encontre!, retorno */
 552                         delete [] node;
 553                         DeleteKeys (node_keys);
 554                         return true;
 555                 }
 556
 557                 if ((*data) < (*(*it)))
 558                         break;
 559                 ultima = it;
 560                 it++;
 561         }
 562
 563         /* TODO: Aca faltaria liberar memoria */
 564         if (it == posterior)
 565                 return FindKeyR (k, lchild->getChild ());
 566
 567         return FindKeyR (k, (*ultima)->getChild ());
 568 }
 569
 570 void BTree::DeleteKeys (std::list<BTreeData *> &keys)
 571 {
 572         std::list<BTreeData *>::iterator it = keys.begin ();
 573
 574         while (it != keys.end ()) {
 575                 BTreeData *d = (*it);
 576                 delete d;
 577                 it++;
 578         }
 579 }
 580