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