Solo un poco de documentacion.

diff --git a/emufs/external_sort/bufford.c b/emufs/external_sort/bufford.c
index 8fea2cb9ab2c36448d72133fe0eb7717c7f2aca9..4f7135c79262c89bdad0fdf673d2aa10d86de935 100644 (file)
--- a/emufs/external_sort/bufford.c
+++ b/emufs/external_sort/bufford.c
@@ -1,22 +1,68 @@
+/* vim: set noexpandtab tabstop=4 shiftwidth=4 wrap:
+ *----------------------------------------------------------------------------
+ *                                  emufs
+ *----------------------------------------------------------------------------
+ * This file is part of emufs.
+ *
+ * emufs is free software; you can redistribute it and/or modify it under the
+ * terms of the GNU General Public License as published by the Free Software
+ * Foundation; either version 2 of the License, or (at your option) any later
+ * version.
+ *
+ * emufs is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with emufs; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA  02111-1307  USA
+ *----------------------------------------------------------------------------
+ * Creado:  mié may 26 19:46:31 ART 2004
+ * Autores: Leandro Lucarella <llucare@fi.uba.ar>
+ *----------------------------------------------------------------------------
+ *
+ * $Id: tipo1.c 548 2004-05-28 22:44:27Z llucare $
+ *
+ */
+
+/** \file
+ *
+ * Buffer ordenado.
+ * 
+ * Implementación de un buffer ordenado. Al obtener un dato del buffer, se
+ * obtiene de forma ordenada.
+ *
+ */

 
 #include "bufford.h"
 #include <malloc.h>
 #include <string.h>
 #include <assert.h>
 
 
 #include "bufford.h"
 #include <malloc.h>
 #include <string.h>
 #include <assert.h>
 

+/** Prueba si \c x es menor que \c y usando la función de comparación. */

 #define LT(b, x, y) (b->cmp(x, y) < 0)
 #define LT(b, x, y) (b->cmp(x, y) < 0)

+/** Prueba si \c x es mayor que \c y usando la función de comparación. */

 #define GT(b, x, y) (b->cmp(x, y) > 0)
 #define GT(b, x, y) (b->cmp(x, y) > 0)

+/** Prueba si \c x es igual a \c y usando la función de comparación. */

 #define EQ(b, x, y) (b->cmp(x, y) == 0)
 #define EQ(b, x, y) (b->cmp(x, y) == 0)

+/** Prueba si \c x es distinto a \c y usando la función de comparación. */

 #define NE(b, x, y) (b->cmp(x, y) != 0)
 #define NE(b, x, y) (b->cmp(x, y) != 0)

+/** Prueba si \c x es menor o igual a \c y usando la función de comparación. */

 #define LE(b, x, y) (b->cmp(x, y) <= 0)
 #define LE(b, x, y) (b->cmp(x, y) <= 0)

+/** Prueba si \c x es mayor o igual a \c y usando la función de comparación. */

 #define GE(b, x, y) (b->cmp(x, y) >= 0)
 
 #define GE(b, x, y) (b->cmp(x, y) >= 0)
 

+/** Crea un nuevo nodo, se guarda una copia del dato en el nodo. */

 static BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size);
 
 static BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size);
 

+/** Borra un nodo, liberando la memoria propia pero no la del dato. */

 static void bufford_node_delete(BUFFORD_NODE* node);
 
 static void bufford_node_delete(BUFFORD_NODE* node);
 

+/** Borra un nodo del buffer recursivamente, borrando sus hijos también. */

 static void bufford_clear_node_recursive(BUFFORD_NODE* node);
 
 static void bufford_clear_node_recursive(BUFFORD_NODE* node);
 

+/** Inserta un nodo en el buffer sin modificar el tamaño. */

 static void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node);
 
 BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size)
 static void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node);
 
 BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size)


@@ -173,7 +219,36 @@ int bufford_push(BUFFORD* buff, void* data)
        return 1; /* OK */
 }
 
        return 1; /* OK */
 }
 

-void* bufford_pop(BUFFORD* buff, void* min)
+void* bufford_pop_min(BUFFORD* buff)
+{
+       /* nodo iterador */
+       BUFFORD_NODE* curr = buff->root;
+       /* nodo previo al iterador */
+       BUFFORD_NODE* prev = 0;
+       /* valor mínimo encontrado, si se encontró */
+       void* min_found = 0;
+       assert(buff);
+       if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
+       /* buscamos el mínimo nodo */
+       while (curr->left) {
+               prev = curr;
+               curr = curr->left;
+       }
+       /* lo sacamos del árbol */
+       if (prev) { /* si tiene padre (no es el raíz) */
+               /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
+                * izquierda no tiene nada.*/
+               prev->left = curr->right;
+       } else { /* si es el raíz */
+               buff->root = curr->right; /* ponemos el nuevo raíz */
+       }
+       min_found = curr->data;
+       bufford_node_delete(curr);
+       buff->size--;
+       return min_found;
+}
+
+void* bufford_pop_next(BUFFORD* buff, void* min)

 {
        /* nodo iterador */
        BUFFORD_NODE* curr = buff->root;
 {
        /* nodo iterador */
        BUFFORD_NODE* curr = buff->root;


@@ -229,35 +304,6 @@ void* bufford_pop(BUFFORD* buff, void* min)
        return min_found;
 }
 
        return min_found;
 }
 

-void* bufford_pop_min(BUFFORD* buff)
-{
-       /* nodo iterador */
-       BUFFORD_NODE* curr = buff->root;
-       /* nodo previo al iterador */
-       BUFFORD_NODE* prev = 0;
-       /* valor mínimo encontrado, si se encontró */
-       void* min_found = 0;
-       assert(buff);
-       if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
-       /* buscamos el mínimo nodo */
-       while (curr->left) {
-               prev = curr;
-               curr = curr->left;
-       }
-       /* lo sacamos del árbol */
-       if (prev) { /* si tiene padre (no es el raíz) */
-               /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
-                * izquierda no tiene nada.*/
-               prev->left = curr->right;
-       } else { /* si es el raíz */
-               buff->root = curr->right; /* ponemos el nuevo raíz */
-       }
-       min_found = curr->data;
-       bufford_node_delete(curr);
-       buff->size--;
-       return min_found;
-}
-

 void* bufford_get_min(BUFFORD* buff)
 {
        /* nodo iterador */
 void* bufford_get_min(BUFFORD* buff)
 {
        /* nodo iterador */

diff --git a/emufs/external_sort/bufford.h b/emufs/external_sort/bufford.h
index 47ffec9a0811744c130191d448791609e89ee4b6..1a3cd751c1643882abd02bae38f6c3214092f706 100644 (file)
--- a/emufs/external_sort/bufford.h
+++ b/emufs/external_sort/bufford.h
@@ -1,43 +1,123 @@
+/* vim: set noexpandtab tabstop=4 shiftwidth=4:
+ *----------------------------------------------------------------------------
+ *                                  emufs
+ *----------------------------------------------------------------------------
+ * This file is part of emufs.
+ *
+ * emufs is free software; you can redistribute it and/or modify it under the
+ * terms of the GNU General Public License as published by the Free Software
+ * Foundation; either version 2 of the License, or (at your option) any later
+ * version.
+ *
+ * emufs is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with emufs; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA  02111-1307  USA
+ *----------------------------------------------------------------------------
+ * Creado:  mié may 26 19:59:28 ART 2004
+ * Autores: Leandro Lucarella <llucare@fi.uba.ar>
+ *----------------------------------------------------------------------------
+ *
+ * $Id: tipo1.h 542 2004-05-28 19:45:02Z rmarkie $
+ *
+ */
+
+/** \file
+ *
+ * Buffer ordenado.
+ * 
+ * Interfaz de un buffer ordenado. Al obtener un dato del buffer, se
+ * obtiene de forma ordenada.
+ *
+ */
+
+#ifndef _EXTERNAL_SORT_BUFFORD_H_
+#define _EXTERNAL_SORT_BUFFORD_H_

 
 #include <stdlib.h>
 
 
 #include <stdlib.h>
 

+/** Función utilizada para comparar al ordenar los datos.
+ *  \return 0 si son iguales, mayor que cero si el primer argumento es mayor y
+ *          menor que cero si el primer argumento es menor.
+ */

 typedef int (*CMP_FUNC)(void*, void*);
 
 typedef int (*CMP_FUNC)(void*, void*);
 

+/** Nodo del buffer ordenado (uso interno). */

 typedef struct _BUFFORD_NODE
 {
 typedef struct _BUFFORD_NODE
 {

-       void* data;
-       struct _BUFFORD_NODE* left;
-       struct _BUFFORD_NODE* right;
+       void* data; /**< Datos. */
+       struct _BUFFORD_NODE* left; /**< Hijo izquierdo. */
+       struct _BUFFORD_NODE* right; /**< Hijo derecho. */

 }
 BUFFORD_NODE;
 
 }
 BUFFORD_NODE;
 

+/** Buffer ordenado. */

 typedef struct
 {
 typedef struct
 {

-       CMP_FUNC cmp;
-       BUFFORD_NODE* root;
-       size_t size;
-       size_t max_size;
-       size_t reg_size;
+       CMP_FUNC cmp; /**< Función de comparación a usar. */
+       BUFFORD_NODE* root; /**< nodo raíz. */
+       size_t size; /**< Tamaño (cantidad de nodos). */
+       size_t max_size; /**< Cantidad máxima de registros que almacena. */
+       size_t reg_size; /**< Tamaño del registro. */

 }
 BUFFORD;
 
 }
 BUFFORD;
 

+/** Crea un nuevo buffer ordenado.
+ * 
+ * \param size Tamaño máximo (en bytes) del buffer.
+ * \param reg_size Tamaño del registro que almacena.
+ * \param cmp Función de comparación a usar.
+ * \return Nuevo buffer ordenado o 0 si no hay más memoria.
+ */

 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp);
 
 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp);
 

+/** Borra un buffer ordenado liberando su memoria. */

 void bufford_delete(BUFFORD* buff);
 
 void bufford_delete(BUFFORD* buff);
 

+/** Limpia un buffer ordenado, borrando todos sus datos. */

 void bufford_clear(BUFFORD* buff);
 
 void bufford_clear(BUFFORD* buff);
 

+/** Indica si un buffer ordenado está lleno. */

 int bufford_full(BUFFORD* buff);
 
 int bufford_full(BUFFORD* buff);
 

+/** Indica si un buffer ordenado está vacío. */

 int bufford_empty(BUFFORD* buff);
 
 int bufford_empty(BUFFORD* buff);
 

+/** Agrega un nuevo dato al buffer ordenado.
+ *
+ * \return 0 si hubo error o está lleno el buffer.
+ */

 int bufford_push(BUFFORD* buff, void* data);
 
 int bufford_push(BUFFORD* buff, void* data);
 

-void* bufford_pop(BUFFORD* buff, void* min);
-
+/** Obtiene el menor dato del buffer ordenado.
+ *  Si el buffer está vacío, se devuelve 0. El dato obtenido es eliminado del
+ *  buffer (por lo que debe ser liberado al terminar de usarlo).
+ */

 void* bufford_pop_min(BUFFORD* buff);
 
 void* bufford_pop_min(BUFFORD* buff);
 

+/** Obtiene el menor dato mayor a \c min del buffer ordenado.
+ *  Si no llegara a haber un dato que cumpla esas características o el buffer
+ *  está vacío, se devuelve 0. El dato obtenido es eliminado del buffer (por lo
+ *  que debe ser liberado al terminar de usarlo).
+ */
+void* bufford_pop_next(BUFFORD* buff, void* min);
+
+/** Obtiene el menor dato del buffer ordenado (para debug).
+ *  Si el buffer está vacío, se devuelve 0. El dato obtenido \b no es eliminado
+ *  del buffer (por lo que \b no debe ser liberado).
+ */

 void* bufford_get_min(BUFFORD* buff);
 
 void* bufford_get_min(BUFFORD* buff);
 

+/** Obtiene el menor dato mayor a \c min del buffer ordenado (para debug).
+ *  Si no llegara a haber un dato que cumpla esas características o el buffer
+ *  está vacío, se devuelve 0. El dato obtenido \b no es eliminado del buffer
+ *  (por lo que \b no debe ser liberado).es eliminado del buffer.
+ */

 void* bufford_get_next(BUFFORD* buff, void* min);
 
 void* bufford_get_next(BUFFORD* buff, void* min);
 

+#endif /*  _EXTERNAL_SORT_BUFFORD_H_ */
+

diff --git a/emufs/external_sort/bufford.txt b/emufs/external_sort/bufford.txt
index 4efb0fb6093893feae03cbd026d4a091b7bb4e30..acc5e8737f809ac1fd85a6980f33211925f3c0bd 100644 (file)
--- a/emufs/external_sort/bufford.txt
+++ b/emufs/external_sort/bufford.txt
@@ -1,19 +1,19 @@
-2
-456
-7
-3
-23
-4
-6
-34
-5678

 56
 89
 26
 56
 89
 26

+456
+7

 624
 624

+23
+5678
+2

 45
 282762
 45
 282762

+34
+3

 22
 22

+6

 77
 77

+4

 99
 21
 99
 21

diff --git a/emufs/external_sort/bufford_test.c b/emufs/external_sort/bufford_test.c
index f92916a533458d8b428c9631054dab7de1198c22..ba3ea9697f9fcc88f385082b7abe797ff478c668 100644 (file)
--- a/emufs/external_sort/bufford_test.c
+++ b/emufs/external_sort/bufford_test.c
@@ -50,7 +50,7 @@ int main(int argc, char* argv[])
                                int* poped;
                                printf("Debe sacar algún valor: ");
                                scanf("%i", &new_reg);
                                int* poped;
                                printf("Debe sacar algún valor: ");
                                scanf("%i", &new_reg);

-                               if ((poped = bufford_pop(b, &new_reg))) {
+                               if ((poped = bufford_pop_next(b, &new_reg))) {

                                        printf("Se sacó el valor %i con éxito!\n", *poped);
                                        free(poped);
                                        if (!bufford_push(b, &reg)) { /* no hay más lugar */
                                        printf("Se sacó el valor %i con éxito!\n", *poped);
                                        free(poped);
                                        if (!bufford_push(b, &reg)) { /* no hay más lugar */


@@ -71,7 +71,7 @@ int main(int argc, char* argv[])
        {
                int* c;
                int x;
        {
                int* c;
                int x;

-               for (c = bufford_pop_min(b); c; c = bufford_pop(b, &x)) {
+               for (c = bufford_pop_min(b); c; c = bufford_pop_next(b, &x)) {

                        x = *c;
                        free(c);
                        printf("Se sacó el valor %i con éxito!\n", x);
                        x = *c;
                        free(c);
                        printf("Se sacó el valor %i con éxito!\n", x);