src/btree.cpp

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