emufs/external_sort/bufford.h

   1 /* vim: set noexpandtab tabstop=4 shiftwidth=4:
   2  *----------------------------------------------------------------------------
   3  *                                  emufs
   4  *----------------------------------------------------------------------------
   5  * This file is part of emufs.
   6  *
   7  * emufs is free software; you can redistribute it and/or modify it under the
   8  * terms of the GNU General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option) any later
  10  * version.
  11  *
  12  * emufs is distributed in the hope that it will be useful, but WITHOUT ANY
  13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
  15  * details.
  16  *
  17  * You should have received a copy of the GNU General Public License along
  18  * with emufs; if not, write to the Free Software Foundation, Inc., 59 Temple
  19  * Place, Suite 330, Boston, MA  02111-1307  USA
  20  *----------------------------------------------------------------------------
  21  * Creado:  mié may 26 19:59:28 ART 2004
  22  * Autores: Leandro Lucarella <llucare@fi.uba.ar>
  23  *----------------------------------------------------------------------------
  24  *
  25  * $Id: tipo1.h 542 2004-05-28 19:45:02Z rmarkie $
  26  *
  27  */
  28
  29 /** \file
  30  *
  31  * Buffer ordenado.
  32  *
  33  * Interfaz de un buffer ordenado. Al obtener un dato del buffer, se
  34  * obtiene de forma ordenada.
  35  *
  36  */
  37
  38 #ifndef _EXTERNAL_SORT_BUFFORD_H_
  39 #define _EXTERNAL_SORT_BUFFORD_H_
  40
  41 #include <stdlib.h>
  42
  43 /** Función utilizada para comparar al ordenar los datos.
  44  *  \return 0 si son iguales, mayor que cero si el primer argumento es mayor y
  45  *          menor que cero si el primer argumento es menor.
  46  */
  47 typedef int (*CMP_FUNC)(void*, void*);
  48
  49 /** Nodo del buffer ordenado (uso interno). */
  50 typedef struct _BUFFORD_NODE
  51 {
  52         void* data; /**< Datos. */
  53         struct _BUFFORD_NODE* left; /**< Hijo izquierdo. */
  54         struct _BUFFORD_NODE* right; /**< Hijo derecho. */
  55 }
  56 BUFFORD_NODE;
  57
  58 /** Buffer ordenado. */
  59 typedef struct
  60 {
  61         CMP_FUNC cmp; /**< Función de comparación a usar. */
  62         BUFFORD_NODE* root; /**< nodo raíz. */
  63         size_t size; /**< Tamaño (cantidad de nodos). */
  64         size_t max_size; /**< Cantidad máxima de registros que almacena. */
  65         size_t reg_size; /**< Tamaño del registro. */
  66 }
  67 BUFFORD;
  68
  69 /** Crea un nuevo buffer ordenado con una cantidad máxima de registros.
  70  *
  71  * \param size Tamaño máximo (en cantidad de registros) del buffer.
  72  * \param reg_size Tamaño del registro que almacena.
  73  * \param cmp Función de comparación a usar.
  74  * \return Nuevo buffer ordenado o 0 si no hay más memoria.
  75  */
  76 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp);
  77
  78 /** Crea un nuevo buffer ordenado con una cantidad máxima de memoria a usar.
  79  *
  80  * \param size Tamaño máximo (en bytes) del buffer.
  81  * \param reg_size Tamaño del registro que almacena.
  82  * \param cmp Función de comparación a usar.
  83  * \return Nuevo buffer ordenado o 0 si no hay más memoria.
  84  */
  85 BUFFORD* bufford_new_bytes_size(size_t size, size_t reg_size, CMP_FUNC cmp);
  86
  87 /** Borra un buffer ordenado liberando su memoria. */
  88 void bufford_delete(BUFFORD* buff);
  89
  90 /** Limpia un buffer ordenado, borrando todos sus datos. */
  91 void bufford_clear(BUFFORD* buff);
  92
  93 /** Indica si un buffer ordenado está lleno. */
  94 int bufford_full(BUFFORD* buff);
  95
  96 /** Indica si un buffer ordenado está vacío. */
  97 int bufford_empty(BUFFORD* buff);
  98
  99 /** Agrega un nuevo dato al buffer ordenado.
 100  *
 101  * \return 0 si hubo error o está lleno el buffer.
 102  */
 103 int bufford_push(BUFFORD* buff, void* data);
 104
 105 /** Obtiene el menor dato del buffer ordenado.
 106  *  Si el buffer está vacío, se devuelve 0. El dato obtenido es eliminado del
 107  *  buffer (por lo que debe ser liberado al terminar de usarlo).
 108  */
 109 void* bufford_pop_min(BUFFORD* buff);
 110
 111 /** Obtiene el menor dato mayor a \c min del buffer ordenado.
 112  *  Si no llegara a haber un dato que cumpla esas características o el buffer
 113  *  está vacío, se devuelve 0. El dato obtenido es eliminado del buffer (por lo
 114  *  que debe ser liberado al terminar de usarlo).
 115  */
 116 void* bufford_pop_next(BUFFORD* buff, void* min);
 117
 118 /** Obtiene el menor dato del buffer ordenado (para debug).
 119  *  Si el buffer está vacío, se devuelve 0. El dato obtenido \b no es eliminado
 120  *  del buffer (por lo que \b no debe ser liberado).
 121  */
 122 void* bufford_get_min(BUFFORD* buff);
 123
 124 /** Obtiene el menor dato mayor a \c min del buffer ordenado (para debug).
 125  *  Si no llegara a haber un dato que cumpla esas características o el buffer
 126  *  está vacío, se devuelve 0. El dato obtenido \b no es eliminado del buffer
 127  *  (por lo que \b no debe ser liberado).es eliminado del buffer.
 128  */
 129 void* bufford_get_next(BUFFORD* buff, void* min);
 130
 131 #endif /*  _EXTERNAL_SORT_BUFFORD_H_ */
 132