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