Agrego clave variable.

diff --git a/src/Makefile b/src/Makefile
index 208da3198cdfeaab2f7bc2a8f469c81667f64e99..2bcafd625ba327d23a9cd1d82f31765491e13282 100644 (file)
--- a/src/Makefile
+++ b/src/Makefile
@@ -1,13 +1,16 @@
-TARGETS=btree libbtree.a
+TARGETS=btree btree_variable libbtree.a

 CXXFLAGS=-Wall -g
 
 CXXFLAGS=-Wall -g
 

-BTREE_COMMON=btree.o clave_fija.o btree_data.o
+BTREE_COMMON=btree.o clave_fija.o btree_data.o clave_variable.o

 
 all: $(TARGETS)
 
 btree: main.o $(BTREE_COMMON)
        g++ -o btree main.o $(BTREE_COMMON)
 
 
 all: $(TARGETS)
 
 btree: main.o $(BTREE_COMMON)
        g++ -o btree main.o $(BTREE_COMMON)
 

+btree_variable: main_variable.o $(BTREE_COMMON)
+       g++ -o btree_variable main_variable.o $(BTREE_COMMON)
+

 libbtree.a: $(BTREE_COMMON)
        $(AR) cru libbtree.a $(BTREE_COMMON)
 
 libbtree.a: $(BTREE_COMMON)
        $(AR) cru libbtree.a $(BTREE_COMMON)
 

diff --git a/src/btree.cpp b/src/btree.cpp
index 1bbb7555ec825556713a9e728f6aef14d4059908..66f4026fd556508ed1b49c953e08f942c3429544 100644 (file)
--- a/src/btree.cpp
+++ b/src/btree.cpp
@@ -1,8 +1,9 @@
 
 #include "btree.h"
 
 
 #include "btree.h"
 

-BTree::BTree (const std::string &name, unsigned int block_size, bool create_new_file)
+BTree::BTree (const std::string &name, unsigned int block_size, int kt, bool create_new_file)

 {
 {

+       key_type = kt;

        uchar *node;
        BTreeNodeHeader nh;
 
        uchar *node;
        BTreeNodeHeader nh;
 


@@ -417,9 +418,9 @@ std::list<BTreeData *> BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade
                /* TODO : Detectar si estoy en una hoja */
                BTreeData *data;
                if (node_header.level == 0) {
                /* TODO : Detectar si estoy en una hoja */
                BTreeData *data;
                if (node_header.level == 0) {

-                       data = new BTreeLeafData (node);
+                       data = new BTreeLeafData (node, key_type);

                } else {
                } else {

-                       data = new BTreeData (node);
+                       data = new BTreeData (node, key_type);

                }
                node += data->Size ();
                keys.push_back (data);
                }
                node += data->Size ();
                keys.push_back (data);

diff --git a/src/btree.h b/src/btree.h
index 999d7987439274d58bce11bfa26ee854314e471b..a67fa4c4b9d1e086458f80e2cd367869411f448d 100644 (file)
--- a/src/btree.h
+++ b/src/btree.h
@@ -50,6 +50,7 @@
 #include "common.h"
 #include "clave.h"
 #include "clave_fija.h"
 #include "common.h"
 #include "clave.h"
 #include "clave_fija.h"

+#include "clave_variable.h"

 #include "btree_data.h"
 
 /* alias para codear menos :) */
 #include "btree_data.h"
 
 /* alias para codear menos :) */


@@ -86,14 +87,22 @@ struct BTreeNodeHeader {
  */
 class BTree {
        public:
  */
 class BTree {
        public:

-               BTree (const std::string &filename, unsigned int block_size, bool create_new_file = false);
+               BTree (const std::string &filename, unsigned int block_size, int k_t = KEY_FIXED, bool create_new_file = false);

                ~BTree ();
 
                ~BTree ();
 

+               /** Tipos de clave a usar */
+               enum {
+                       KEY_FIXED,
+                       KEY_VARIABLE
+               };
+

                void AddKey (const Clave &k);
                void DelKey (const Clave &k);
 
        protected:
                Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
                void AddKey (const Clave &k);
                void DelKey (const Clave &k);
 
        protected:
                Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);

+               Clave* AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+               Clave* AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child);

 
                void WriteFileHeader ();
 
 
                void WriteFileHeader ();
 


@@ -109,6 +118,7 @@ class BTree {
 
                std::string filename;
                BTreeFileHeader header;
 
                std::string filename;
                BTreeFileHeader header;

+               int key_type;

 
                /** Apunta al archivo de datos, asi se abre solo 1 vez
                 *
 
                /** Apunta al archivo de datos, asi se abre solo 1 vez
                 *

diff --git a/src/btree_data.cpp b/src/btree_data.cpp
index 7ba3448c1d17b01ab52f48582386587c4cba8f9f..a5d9b6805706311ca288279c5030f83f582adb22 100644 (file)
--- a/src/btree_data.cpp
+++ b/src/btree_data.cpp
@@ -1,12 +1,16 @@
 
 #include "btree_data.h"
 
 #include "btree_data.h"

+#include "btree.h"

 
 

-BTreeData::BTreeData (uchar *node)
+BTreeData::BTreeData (uchar *node, int tree_type)

 {
        /* TODO : Aca deberia detectar el tipo de clave (necesito
         * info desde el arbol
         */
 {
        /* TODO : Aca deberia detectar el tipo de clave (necesito
         * info desde el arbol
         */

-       clave = new ClaveFija (node);
+       if (tree_type == BTree::KEY_FIXED)
+               clave = new ClaveFija (node);
+       else
+               clave = new ClaveVariable (node);

        node += clave->Size ();
 
        memcpy (&hijo, node, sizeof (uint));
        node += clave->Size ();
 
        memcpy (&hijo, node, sizeof (uint));


@@ -55,6 +59,14 @@ bool BTreeData::operator == (const BTreeData &data) const
        return (*clave) == (*(data.clave));
 }
 
        return (*clave) == (*(data.clave));
 }
 

+BTreeLeafData::BTreeLeafData (uchar *node, int key_type)
+{
+       if (key_type == BTree::KEY_FIXED)
+               clave = new ClaveFija (node);
+       else
+               clave = new ClaveVariable (node);
+}
+

 BTreeLeafData::~BTreeLeafData ()
 {
 }
 BTreeLeafData::~BTreeLeafData ()
 {
 }

diff --git a/src/btree_data.h b/src/btree_data.h
index db8ecc180a318834906762505a294b9d42e65aed..ca2cd4dc2e0526fcd1d5adef1f9a52ee6e84d41c 100644 (file)
--- a/src/btree_data.h
+++ b/src/btree_data.h
@@ -6,12 +6,13 @@
 #include <stdlib.h>
 #include "clave.h"
 #include "clave_fija.h"
 #include <stdlib.h>
 #include "clave.h"
 #include "clave_fija.h"

+#include "clave_variable.h"

 
 /** Dato a guardar en los nodos */
 class BTreeData {
        public:
                BTreeData () {}
 
 /** Dato a guardar en los nodos */
 class BTreeData {
        public:
                BTreeData () {}

-               BTreeData (uchar *node);
+               BTreeData (uchar *node, int tree_type);

                BTreeData (Clave *k, uint child);
                virtual ~BTreeData ();
 
                BTreeData (Clave *k, uint child);
                virtual ~BTreeData ();
 


@@ -41,7 +42,7 @@ class BTreeData {
 class BTreeLeafData:public BTreeData {
        public:
                BTreeLeafData (Clave *k) { clave = k; }
 class BTreeLeafData:public BTreeData {
        public:
                BTreeLeafData (Clave *k) { clave = k; }

-               BTreeLeafData (uchar *node) { clave = new ClaveFija (node); }
+               BTreeLeafData (uchar *node, int key_type);

                virtual ~BTreeLeafData ();
 
                virtual uint Size () const;
                virtual ~BTreeLeafData ();
 
                virtual uint Size () const;

diff --git a/src/clave.h b/src/clave.h
index 81e24dbe594ff01027d6631cd6a8011ebdaaee56..e609bb02d37797d22556b25b83a52c4a2d1566c0 100644 (file)
--- a/src/clave.h
+++ b/src/clave.h
@@ -6,12 +6,20 @@
 #include "common.h"
 #include <string>
 
 #include "common.h"
 #include <string>
 

+/** Clave abstracta para manejo de Claves */

 class Clave {
        public:
                virtual ~Clave () {}
 
 class Clave {
        public:
                virtual ~Clave () {}
 

+               /** Retorna el tamaño en bytes que ocupa la clave */

                virtual uint Size () const = 0;
                virtual uint Size () const = 0;

+               /** Retorna un array de bytes de Size() de longitud.
+                * 
+                *  El contenido del array es la clave en formato RAW
+                *  para guardar en disco.
+                */

                virtual uchar *ToArray () const = 0;
                virtual uchar *ToArray () const = 0;

+               /** Retorna un clon de la clave actual */

                virtual Clave *Clone () const = 0;
 
                virtual bool operator < (const Clave &k) const = 0;
                virtual Clave *Clone () const = 0;
 
                virtual bool operator < (const Clave &k) const = 0;

diff --git a/src/clave_variable.cpp b/src/clave_variable.cpp
new file mode 100644 (file)
index 0000000..6534764
--- /dev/null
+++ b/src/clave_variable.cpp
@@ -0,0 +1,55 @@
+
+#include <string>
+#include "clave_variable.h"
+#include <iostream>
+
+ClaveVariable::ClaveVariable (const std::string &s)
+{
+       data = s;
+}
+
+ClaveVariable::ClaveVariable (uchar *n)
+{
+       uint len;
+
+       memcpy (&len, n, sizeof (uint));
+       uchar *str = new uchar[len+1];
+       n += sizeof (uint);
+       memcpy (str, n, sizeof (uchar)*len);
+       str[len] = '\0';
+       data = std::string ((const char *)(str));
+       std::cout << "CREE : " << data << std::endl;
+       delete [] str;
+}
+
+uint ClaveVariable::Size () const
+{
+       return data.size ()+sizeof (uint);
+}
+
+uchar *ClaveVariable::ToArray () const
+{
+       uchar *out;
+       uint len = data.size ();
+       out = new uchar[Size ()];
+       memcpy (out, &len, sizeof (uint));
+       memcpy (out+sizeof(uint), data.c_str (), data.size ());
+       return out;
+}
+
+Clave *ClaveVariable::Clone () const
+{
+       ClaveVariable *k = new ClaveVariable (*this);
+       return k;
+}
+
+bool ClaveVariable::operator < (const Clave &c) const
+{
+       return data < ((ClaveVariable&)c).data;
+}
+
+bool ClaveVariable::operator == (const Clave &c) const
+{
+       return data == ((ClaveVariable&)c).data;
+}
+

diff --git a/src/clave_variable.h b/src/clave_variable.h
new file mode 100644 (file)
index 0000000..fbe5011
--- /dev/null
+++ b/src/clave_variable.h
@@ -0,0 +1,37 @@
+
+#ifndef _CLAVE_VARIABLE_H_
+#define _CLAVE_VARIABLE_H_
+
+#include "clave.h"
+#include <string>
+#include <sstream>
+
+/** Representa una clave de longitud variable.
+ *
+ *  \TODO Usar abreviaciones
+ */
+class ClaveVariable : public Clave {
+       public :
+               ClaveVariable (uchar *n);
+               ClaveVariable (const std::string &s);
+               virtual ~ClaveVariable () {}
+
+               uint Size () const;
+               uchar *ToArray () const;
+               Clave *Clone () const;
+
+               virtual bool operator < (const Clave &c) const;
+               virtual bool operator == (const Clave &c) const;
+               virtual operator std::string () const {
+                       std::string out;
+                       std::stringstream ss;
+                       ss << data;
+                       ss >> out;
+                       return out;
+               }
+       private:
+               std::string data;
+};
+
+#endif
+

diff --git a/src/main_variable.cpp b/src/main_variable.cpp
new file mode 100644 (file)
index 0000000..9828e4e
--- /dev/null
+++ b/src/main_variable.cpp
@@ -0,0 +1,41 @@
+
+
+#include "btree.h"
+#include "clave_variable.h"
+
+int main  (int argc, char *argv[])
+{
+       BTree tree ("test.idx", 128, BTree::KEY_VARIABLE);
+       
+       if (argc != 2) {
+               printf ("Falta parametro cantidad de elementos a agregar\n");
+               return 1;
+       }
+
+       for (int i=0; i<=atoi(argv[1]); i++) {
+               std::stringstream ss;
+               std::string s;
+               ss << i;
+               ss >> s;
+               ClaveVariable c(s);
+
+               std::cout << "Agregando " << i << std::endl;
+               tree.AddKey (c);
+       }
+       
+       for (int i=0; i<=atoi(argv[1]); i++) {
+               std::stringstream ss;
+               std::string s;
+               ss << i;
+               ss >> s;
+               ClaveVariable c(s);
+
+               if (tree.FindKey (c))
+                       std::cout << i << " encontrada\n";
+               else
+                       std::cout << i << " NO encontrada\n";
+       }
+
+       return 0;
+}
+