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         Clave *kout = NULL;
  96         std::list<BTreeData *> node_keys;
  97
  98         BTreeData *data = new BTreeLeafData (k->Clone ());
  99
 100         /* Leo el nodo raiz para empezar a agregar */
 101         uchar *node = ReadBlock (node_num);
 102         BTreeNodeHeader node_header;
 103         ReadNodoHeader (node, &node_header);
 104
 105         if (node_header.level != 0) {
 106                 std::cout << "Entrando nodo level = " << node_header.level << std::endl;
 107                 /* No estoy en una hoja, asi que tengo que buscar
 108                  * para donde moverme para agregar la clave
 109                  */
 110                 std::cout << "Leo Claves" << std::endl;
 111                 node_keys = ReadKeys (node, node_header);
 112
 113                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 114                 std::list<BTreeData *>::iterator posterior;
 115                 std::list<BTreeData *>::iterator ultima;
 116
 117                 /* Se supone que la primera es un hijo :) */
 118                 BTreeData *lchild = (*it++);
 119                 posterior = it;
 120
 121                 while (it != node_keys.end ()) {
 122                         if ((*data) < (*(*it)))
 123                                 break;
 124                         ultima = it;
 125                         it++;
 126                 }
 127
 128                 if (it == posterior) {
 129                         std::cout << "==== Me voy al nodo " << lchild->getChild () << std::endl;
 130                         k = AddKeyR (k, lchild->getChild (), left_child, right_child);
 131                 } else {
 132                         std::cout << "==== Me voy al nodo " << (*ultima)->getChild () << std::endl;
 133                         k = AddKeyR (k, (*ultima)->getChild (), left_child, right_child);
 134                 }
 135                 if (k) {
 136                         data = new BTreeData (k->Clone (), right_child);
 137                 }
 138         }
 139
 140
 141         /* Nada que hacer */
 142         if (!k) return NULL;
 143
 144         /* Estoy en una hoja, veo si lo puedo agregar */
 145
 146         if (node_header.free_space > data->Size ()) {
 147                 /* TODO : Insertar ordenado */
 148                 BTreeData *datait;
 149                 node_keys = ReadKeys (node, node_header);
 150                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 151
 152                 while (it != node_keys.end ()) {
 153                         datait = (*it);
 154                         if ((*data) < (*datait))
 155                                 /* Me pase, lo agrego aca! */
 156                                 break;
 157                         it++;
 158                 }
 159                 node_keys.insert (it, data);
 160                 WriteKeys (node, node_header, node_keys);
 161                 WriteNodoHeader (node, &node_header);
 162                 WriteBlock (node, node_num);
 163
 164                 PrintNode (node_num);
 165         } else {
 166                 std::cout << "=============== SPLIT ================" << std::endl;
 167                 /* Split : Creo e inicializo el nuevo nodo */
 168                 std::list<BTreeData *> new_node_keys;
 169                 std::list<BTreeData *> old_node_keys;
 170                 BTreeNodeHeader new_node_header;
 171                 uint new_node_num;
 172                 uchar *new_node = NewBlock (new_node_num);
 173                 ReadNodoHeader (new_node, &new_node_header);
 174                 new_node_header.level = node_header.level;
 175
 176                 node_keys = ReadKeys (node, node_header);
 177                 new_node_keys = ReadKeys (new_node, new_node_header);
 178
 179                 /* Agrego la clave en la lista que ya tengo de manera ordenada */
 180                 std::list<BTreeData *>::iterator it = node_keys.begin ();
 181                 std::list<BTreeData *>::iterator previt = node_keys.begin ();
 182
 183                 if (node_header.level != 0) {
 184                         /* La primera es ChildData */
 185                         it++;
 186                         previt = it;
 187                 }
 188
 189                 while (it != node_keys.end ()) {
 190                         BTreeData *datait;
 191                         datait = (*it);
 192                         if ((*data) < (*datait))
 193                                 /* Me pase, lo agrego aca! */
 194                                 break;
 195                         previt = it;
 196                         it++;
 197                 }
 198                 if (it != node_keys.end ())
 199                         node_keys.insert (it, data);
 200                 else
 201                         node_keys.push_back (data);
 202
 203                 /* Tengo que guardar claves hasta ocupar nodo size/2 en cada nodo
 204                  * y subir la clave del medio */
 205                 node_header.item_count = 0;
 206                 node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 207
 208                 uint total_size = 0;
 209                 it = node_keys.begin ();
 210                 while (it != node_keys.end ()) {
 211                         BTreeData *datait;
 212                         datait = (*it);
 213                         total_size += datait->Size ();
 214                         it++;
 215                         /* Hack : Si me quedo con todas las claves, en el caso de ser
 216                          * del mismo tama#o se desbalancea. Hay que ver que efecto
 217                          * puede tener en el caso de claves de long. variable
 218                          */
 219                         if (it == node_keys.end ())
 220                                 total_size -= datait->Size ();
 221                 }
 222
 223                 it = node_keys.begin ();
 224                 uint used = 0;
 225                 while (used < total_size/2) {
 226                         BTreeData *d = (*it);
 227                         old_node_keys.push_back (d);
 228                         used += d->Size ();
 229                         it++;
 230                 }
 231                 kout = (*it)->getClave (); // Esta se retorna al "padre" para que se la agregue
 232                 if (node_header.level != 0) {
 233                         new_node_keys.push_back ( new BTreeChildData ((*it)->getChild ()));
 234                 }
 235                 it++;
 236
 237                 std::string s = *kout;
 238                 std::cout << "SPLIT Retorna : " << s << std::endl;
 239                 while (it != node_keys.end ()) {
 240                         BTreeData *d = (*it);
 241                         new_node_keys.push_back (d);
 242                         it++;
 243                 }
 244
 245                 /* Guardo */
 246                 WriteKeys (node, node_header, old_node_keys);
 247                 WriteNodoHeader (node, &node_header);
 248                 WriteBlock (node, node_num);
 249                 WriteKeys (new_node, new_node_header, new_node_keys);
 250                 WriteNodoHeader (new_node, &new_node_header);
 251                 WriteBlock (new_node, new_node_num);
 252
 253                 PrintNode (node_num);
 254                 PrintNode (new_node_num);
 255
 256                 /* Paso los hijos */
 257                 left_child = node_num;
 258                 right_child = new_node_num;
 259                 delete [] new_node;
 260                 delete [] node;
 261         }
 262
 263         return kout;
 264 }
 265
 266 void BTree::DelKey (const Clave &k) {}
 267
 268 void BTree::ReadNodoHeader (uchar *node, BTreeNodeHeader *header)
 269 {
 270         memcpy (header, node, sizeof (BTreeNodeHeader));
 271 }
 272
 273 void BTree::WriteNodoHeader (uchar *node, BTreeNodeHeader *header)
 274 {
 275         memcpy (node, header, sizeof (BTreeNodeHeader));
 276 }
 277
 278 uchar *BTree::ReadBlock (uint num)
 279 {
 280         uchar *out = new uchar[header.block_size];
 281
 282         fseek (fp, num*header.block_size + sizeof (BTreeFileHeader), SEEK_SET);
 283         fread (out, 1, header.block_size, fp);
 284
 285         return out;
 286 }
 287
 288 std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_header)
 289 {
 290         std::list<BTreeData *> keys;
 291         node += sizeof (BTreeNodeHeader);
 292         uint count = node_header.item_count;
 293
 294         if (node_header.item_count == 0) return keys;
 295
 296         if (node_header.level != 0) {
 297                 /* Si no es una hoja, lo primero que tengo es un BTreeChildData */
 298                 BTreeChildData *d = new BTreeChildData (node);
 299                 node += d->Size ();
 300                 keys.push_back (d);
 301                 count--;
 302         }
 303
 304         for (uint i=0; i<count; i++) {
 305                 /* TODO : El tipo de clave deberia ser usado
 306                  * dependiendo de algun dato en el header del
 307                  * arbol
 308                  */
 309                 /* TODO : Detectar si estoy en una hoja */
 310                 BTreeData *data;
 311                 if (node_header.level == 0) {
 312                         data = new BTreeLeafData (node);
 313                 } else {
 314                         data = new BTreeData (node);
 315                 }
 316                 node += data->Size ();
 317                 keys.push_back (data);
 318         }
 319
 320         return keys;
 321 }
 322
 323 void BTree::WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys)
 324 {
 325         std::list<BTreeData *>::iterator it = keys.begin ();
 326
 327         node += sizeof (BTreeNodeHeader);
 328
 329         node_header.item_count = 0;
 330         node_header.free_space = header.block_size - sizeof (BTreeNodeHeader);
 331
 332         while (it != keys.end ()) {
 333                 BTreeData *d = (*it);
 334                 memcpy (node, d->ToArray(), d->Size ());
 335                 node += d->Size ();
 336                 node_header.free_space -= d->Size ();
 337                 node_header.item_count++;
 338                 it++;
 339         }
 340
 341         /* TODO : incrementar node_header.item_count aca o fuera de este metodo? */
 342 }
 343
 344 void BTree::PrintNode (uint num)
 345 {
 346         uchar *node = ReadBlock (num);
 347         BTreeNodeHeader node_header;
 348         ReadNodoHeader (node, &node_header);
 349
 350         std::list<BTreeData *> node_keys = ReadKeys (node, node_header);
 351         std::list<BTreeData *>::iterator it = node_keys.begin ();
 352
 353         std::cout << "Nodo  : " << num << std::endl;
 354         std::cout << "Level : " << node_header.level << std::endl;
 355         std::cout << "Items : " << node_header.item_count << std::endl;
 356         std::cout << "Free  : " << node_header.free_space << " (" << (header.block_size - sizeof (BTreeNodeHeader)) << ")" << std::endl;
 357         while (it != node_keys.end ()) {
 358                 std::string s = *(*it);
 359                 std::cout << s << " ";
 360                 it++;
 361         }
 362         std::cout << std::endl;
 363
 364         delete [] node;
 365 }
 366
 367 uchar *BTree::NewBlock (uint &num)
 368 {
 369         long filelen;
 370         uchar *node;
 371         BTreeNodeHeader nh;
 372
 373         fseek (fp, 0, SEEK_END);
 374         filelen = ftell (fp);
 375
 376         num = (filelen - sizeof (BTreeFileHeader))/header.block_size;
 377
 378         node = new uchar[header.block_size];
 379         ReadNodoHeader (node, &nh);
 380         nh.level = 0;
 381         nh.free_space = header.block_size - sizeof (BTreeNodeHeader);
 382         nh.item_count = 0;
 383         WriteNodoHeader (node, &nh);
 384         WriteBlock (node, 0);
 385
 386         return node;
 387 }
 388