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$
  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 _EXTSORT_BUFFORD_H_
  39 #define _EXTSORT_BUFFORD_H_
  40
  41 #include "base.h"
  42 #include <stdlib.h>
  43
  44 /** Nodo del buffer ordenado (uso interno). */
  45 typedef struct _BUFFORD_NODE
  46 {
  47         void* data; /**< Datos. */
  48         struct _BUFFORD_NODE* left; /**< Hijo izquierdo. */
  49         struct _BUFFORD_NODE* right; /**< Hijo derecho. */
  50 }
  51 BUFFORD_NODE;
  52
  53 /** Buffer ordenado. */
  54 typedef struct
  55 {
  56         CMP_FUNC cmp; /**< Función de comparación a usar. */
  57         BUFFORD_NODE* root; /**< nodo raíz. */
  58         size_t size; /**< Tamaño (cantidad de nodos). */
  59         size_t max_size; /**< Cantidad máxima de registros que almacena. */
  60         size_t reg_size; /**< Tamaño del registro. */
  61 }
  62 BUFFORD;
  63
  64 /** Crea un nuevo buffer ordenado con una cantidad máxima de registros.
  65  *
  66  * \param size Tamaño máximo (en cantidad de registros) del buffer.
  67  * \param reg_size Tamaño del registro que almacena.
  68  * \param cmp Función de comparación a usar.
  69  * \return Nuevo buffer ordenado o 0 si no hay más memoria.
  70  */
  71 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp);
  72
  73 /** Crea un nuevo buffer ordenado con una cantidad máxima de memoria a usar.
  74  *
  75  * \param size Tamaño máximo (en bytes) del buffer.
  76  * \param reg_size Tamaño del registro que almacena.
  77  * \param cmp Función de comparación a usar.
  78  * \return Nuevo buffer ordenado o 0 si no hay más memoria.
  79  */
  80 BUFFORD* bufford_new_bytes_size(size_t size, size_t reg_size, CMP_FUNC cmp);
  81
  82 /** Borra un buffer ordenado liberando su memoria. */
  83 void bufford_delete(BUFFORD* buff);
  84
  85 /** Limpia un buffer ordenado, borrando todos sus datos. */
  86 void bufford_clear(BUFFORD* buff);
  87
  88 /** Indica si un buffer ordenado está lleno. */
  89 int bufford_full(BUFFORD* buff);
  90
  91 /** Indica si un buffer ordenado está vacío. */
  92 int bufford_empty(BUFFORD* buff);
  93
  94 /** Agrega un nuevo dato al buffer ordenado.
  95  *
  96  * \return 0 si hubo error o está lleno el buffer.
  97  */
  98 int bufford_push(BUFFORD* buff, void* data);
  99
 100 /** Obtiene el menor dato del buffer ordenado.
 101  *  Si el buffer está vacío, se devuelve 0. El dato obtenido es eliminado del
 102  *  buffer (por lo que debe ser liberado al terminar de usarlo).
 103  */
 104 void* bufford_pop_min(BUFFORD* buff);
 105
 106 /** Obtiene el menor dato mayor a \c min del buffer ordenado.
 107  *  Si no llegara a haber un dato que cumpla esas características o el buffer
 108  *  está vacío, se devuelve 0. El dato obtenido es eliminado del buffer (por lo
 109  *  que debe ser liberado al terminar de usarlo).
 110  */
 111 void* bufford_pop_next(BUFFORD* buff, void* min);
 112
 113 /** Obtiene el menor dato del buffer ordenado (para debug).
 114  *  Si el buffer está vacío, se devuelve 0. El dato obtenido \b no es eliminado
 115  *  del buffer (por lo que \b no debe ser liberado).
 116  */
 117 void* bufford_get_min(BUFFORD* buff);
 118
 119 /** Obtiene el menor dato mayor a \c min del buffer ordenado (para debug).
 120  *  Si no llegara a haber un dato que cumpla esas características o el buffer
 121  *  está vacío, se devuelve 0. El dato obtenido \b no es eliminado del buffer
 122  *  (por lo que \b no debe ser liberado).es eliminado del buffer.
 123  */
 124 void* bufford_get_next(BUFFORD* buff, void* min);
 125
 126 #endif /*  _EXTSORT_BUFFORD_H_ */
 127