]> git.llucax.com Git - z.facultad/75.52/treemulator.git/blob - src/btree.cpp
Otro leak fixed.
[z.facultad/75.52/treemulator.git] / 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