From: Ricardo Markiewicz Date: Tue, 27 Sep 2005 15:32:59 +0000 (+0000) Subject: Agrego clave variable. X-Git-Tag: 1_0-pre1~84 X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/commitdiff_plain/2ab8041933e77875de62bc73e76febc528af258e?ds=sidebyside Agrego clave variable. --- diff --git a/src/Makefile b/src/Makefile index 208da31..2bcafd6 100644 --- a/src/Makefile +++ b/src/Makefile @@ -1,13 +1,16 @@ -TARGETS=btree libbtree.a +TARGETS=btree btree_variable libbtree.a 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) +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) diff --git a/src/btree.cpp b/src/btree.cpp index 1bbb755..66f4026 100644 --- a/src/btree.cpp +++ b/src/btree.cpp @@ -1,8 +1,9 @@ #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; @@ -417,9 +418,9 @@ std::list BTree::ReadKeys (uchar *node, BTreeNodeHeader &node_heade /* 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 { - data = new BTreeData (node); + data = new BTreeData (node, key_type); } node += data->Size (); keys.push_back (data); diff --git a/src/btree.h b/src/btree.h index 999d798..a67fa4c 100644 --- a/src/btree.h +++ b/src/btree.h @@ -50,6 +50,7 @@ #include "common.h" #include "clave.h" #include "clave_fija.h" +#include "clave_variable.h" #include "btree_data.h" /* alias para codear menos :) */ @@ -86,14 +87,22 @@ struct BTreeNodeHeader { */ 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 (); + /** 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); + 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 (); @@ -109,6 +118,7 @@ class BTree { std::string filename; BTreeFileHeader header; + int key_type; /** Apunta al archivo de datos, asi se abre solo 1 vez * diff --git a/src/btree_data.cpp b/src/btree_data.cpp index 7ba3448..a5d9b68 100644 --- a/src/btree_data.cpp +++ b/src/btree_data.cpp @@ -1,12 +1,16 @@ #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 */ - 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)); @@ -55,6 +59,14 @@ bool BTreeData::operator == (const BTreeData &data) const 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 () { } diff --git a/src/btree_data.h b/src/btree_data.h index db8ecc1..ca2cd4d 100644 --- a/src/btree_data.h +++ b/src/btree_data.h @@ -6,12 +6,13 @@ #include #include "clave.h" #include "clave_fija.h" +#include "clave_variable.h" /** 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 (); @@ -41,7 +42,7 @@ class BTreeData { 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; diff --git a/src/clave.h b/src/clave.h index 81e24db..e609bb0 100644 --- a/src/clave.h +++ b/src/clave.h @@ -6,12 +6,20 @@ #include "common.h" #include +/** Clave abstracta para manejo de Claves */ class Clave { public: virtual ~Clave () {} + /** Retorna el tamaño en bytes que ocupa la clave */ 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; + /** Retorna un clon de la clave actual */ 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 index 0000000..6534764 --- /dev/null +++ b/src/clave_variable.cpp @@ -0,0 +1,55 @@ + +#include +#include "clave_variable.h" +#include + +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 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 +#include + +/** 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 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; +} +