emufs/external_sort/extsort.c

   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:  dom may 30 07:48:10 ART 2004
  22  * Autores: Leandro Lucarella <llucare@fi.uba.ar>
  23  *----------------------------------------------------------------------------
  24  *
  25  * $Id: bufford.h 609 2004-05-30 10:14:21Z llucare $
  26  *
  27  */
  28
  29 /** \file
  30  *
  31  * Algoritmo de ordenamiento externo.
  32  *
  33  * Implementación del algoritmo de ordenamiento externo.
  34  *
  35  */
  36
  37 #include "extsort.h"
  38 #include "bufford.h"
  39 #include "mergepool.h"
  40 #include <string.h>
  41 #include <assert.h>
  42
  43 static int extsort_fill_buffer(BUFFORD* bo, size_t reg_size, FILE* fp);
  44
  45 static int extsort_make_pool(BUFFORD* bo, MERGEPOOL* pool, size_t reg_size,
  46                 FILE* fp);
  47
  48 static int extsort_merge_pool(MERGEPOOL* pool, size_t reg_size,
  49                 const char* filename);
  50
  51 int extsort(const char* filename, size_t buf_size, size_t reg_size,
  52                 CMP_FUNC cmp)
  53 {
  54         return extsort_safe(filename, 0, buf_size, reg_size, cmp);
  55 }
  56
  57 int extsort_safe(const char* filename, const char* new_filename,
  58                 size_t buf_size, size_t reg_size, CMP_FUNC cmp)
  59 {
  60         BUFFORD* bo;
  61         MERGEPOOL* pool;
  62         FILE* fp;
  63         assert(filename);
  64         assert(reg_size);
  65         assert(buf_size);
  66         assert(cmp);
  67         /* creo buffer ordenado */
  68         if (!(bo = bufford_new_bytes_size(buf_size, reg_size, cmp))) {
  69                 return 0; /* ERROR */
  70         }
  71         /* creo pool de archivos temporales ordenados */
  72         if (!(pool = mergepool_new(reg_size, cmp))) {
  73                 bufford_delete(bo);
  74                 return 0; /* ERROR */
  75         }
  76         /* abro archivo a ordenar */
  77         if (!(fp = fopen(filename, "r"))) {
  78                 mergepool_delete(pool);
  79                 bufford_delete(bo);
  80                 return 0; /* ERROR */
  81         }
  82         /* lleno el buffer */
  83         if (!extsort_fill_buffer(bo, reg_size, fp)) {
  84                 fclose(fp);
  85                 mergepool_delete(pool);
  86                 bufford_delete(bo);
  87                 return 0; /* ERROR */
  88         }
  89         /* creo archivos temporales ordenados usando el buffer */
  90         if (!extsort_make_pool(bo, pool, reg_size, fp)) {
  91                 fclose(fp);
  92                 mergepool_delete(pool);
  93                 bufford_delete(bo);
  94                 return 0; /* ERROR */
  95         }
  96         fclose(fp);
  97         /* Mezclo lotes */
  98         if (!extsort_merge_pool(pool, reg_size,
  99                                 new_filename ? new_filename : filename)) {
 100                 mergepool_delete(pool);
 101                 bufford_delete(bo);
 102                 return 0; /* ERROR */
 103         }
 104         mergepool_delete(pool);
 105         bufford_delete(bo);
 106         return 1; /* OK */
 107 }
 108
 109 int extsort_fill_buffer(BUFFORD* bo, size_t reg_size, FILE* fp)
 110 {
 111         void* reg;
 112         /* aloco registro de uso genérico */
 113         if (!(reg = malloc(reg_size))) {
 114                 return 0; /* ERROR */
 115         }
 116         while (!bufford_full(bo)) {
 117                 if (!fread(reg, reg_size, 1, fp)) {
 118                         break; /* EOF */
 119                 }
 120                 bufford_push(bo, reg);
 121         }
 122         free(reg);
 123         return 1; /* OK */
 124 }
 125
 126 int extsort_make_pool(BUFFORD* bo, MERGEPOOL* pool, size_t reg_size, FILE* fp)
 127 {
 128         void* reg;
 129         /* aloco registro de uso genérico */
 130         if (!(reg = malloc(reg_size))) {
 131                 return 0; /* ERROR */
 132         }
 133         while (!bufford_empty(bo)) {
 134                 void* tmp;
 135                 /* agrego un nuevo archivo temporal al pool */
 136                 if (!mergepool_add_file(pool)) {
 137                         free(reg);
 138                         return 0; /* ERROR */
 139                 }
 140                 /* lleno el archivo temporal ordenadamente usando el buffer */
 141                 for (tmp = bufford_pop_min(bo); tmp; tmp = bufford_pop_next(bo, reg)) {
 142                         /* si hay un valor en la entrada, lo inserto */
 143                         if (fread(reg, reg_size, 1, fp) && !bufford_push(bo, reg)) {
 144                                 /* ERROR: no se pudo insertar */
 145                                 free(reg);
 146                                 return 0; /* ERROR */
 147                         }
 148                         memcpy(reg, tmp, reg_size);
 149                         free(tmp);
 150                         /* Agrego el dato al último archivo temporal */
 151                         if (!mergepool_append_data(pool, reg)) {
 152                                 free(reg);
 153                                 return 0; /* ERROR */
 154                         }
 155                 }
 156         }
 157         free(reg);
 158         return 1;
 159 }
 160
 161 int extsort_merge_pool(MERGEPOOL* pool, size_t reg_size, const char* filename)
 162 {
 163         FILE* fp;
 164         void* min = 0;
 165         if (!(fp = fopen(filename, "w"))) {
 166                 return 0; /* ERROR */
 167         }
 168         /* obtengo próximo mínimo y lo guardo en el archivo de salida */
 169         while ((min = mergepool_pop_min(pool))) {
 170                 fwrite(min, reg_size, 1, fp);
 171                 free(min);
 172         }
 173         /* libero todos los recursos */
 174         fclose(fp);
 175         return 1; /* OK */
 176 }
 177