From: Leandro Lucarella Date: Fri, 28 May 2004 23:26:33 +0000 (+0000) Subject: Solo un poco de documentacion. X-Git-Tag: svn_import_r684~135 X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/f7050c8d6f2131342e60ceeafdfc2c9a3e09e746?ds=inline Solo un poco de documentacion. --- diff --git a/emufs/external_sort/bufford.c b/emufs/external_sort/bufford.c index 8fea2cb..4f7135c 100644 --- 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 + *---------------------------------------------------------------------------- + * + * $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 #include #include +/** 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) +/** 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) +/** 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) +/** 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) +/** 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) +/** 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) +/** 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); +/** Borra un nodo, liberando la memoria propia pero no la del dato. */ 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); +/** 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) @@ -173,7 +219,36 @@ int bufford_push(BUFFORD* buff, void* data) 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; @@ -229,35 +304,6 @@ void* bufford_pop(BUFFORD* buff, void* min) 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 */ diff --git a/emufs/external_sort/bufford.h b/emufs/external_sort/bufford.h index 47ffec9..1a3cd75 100644 --- 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 + *---------------------------------------------------------------------------- + * + * $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 +/** 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*); +/** Nodo del buffer ordenado (uso interno). */ 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; +/** Buffer ordenado. */ 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; +/** 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); +/** Borra un buffer ordenado liberando su memoria. */ void bufford_delete(BUFFORD* buff); +/** Limpia un buffer ordenado, borrando todos sus datos. */ void bufford_clear(BUFFORD* buff); +/** Indica si un buffer ordenado está lleno. */ int bufford_full(BUFFORD* buff); +/** Indica si un buffer ordenado está vacío. */ 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); -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); +/** 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); +/** 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); +#endif /* _EXTERNAL_SORT_BUFFORD_H_ */ + diff --git a/emufs/external_sort/bufford.txt b/emufs/external_sort/bufford.txt index 4efb0fb..acc5e87 100644 --- 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 +456 +7 624 +23 +5678 +2 45 282762 +34 +3 22 +6 77 +4 99 21 diff --git a/emufs/external_sort/bufford_test.c b/emufs/external_sort/bufford_test.c index f92916a..ba3ea96 100644 --- 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); - 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, ®)) { /* no hay más lugar */ @@ -71,7 +71,7 @@ int main(int argc, char* argv[]) { 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);