+/* 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>
+/** 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)
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;
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 */
+/* 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>
+/** 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_ */
+
projects / z.facultad / 75.06 / emufs.git / commitdiff