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 int extsort(const char* filename, size_t buf_size, size_t reg_size, CMP_FUNC cmp)
  44 {
  45         BUFFORD* b;
  46         MERGEPOOL* pool;
  47         FILE* fp;
  48         int min;
  49         assert(filename);
  50         assert(reg_size);
  51         assert(buf_size);
  52         assert(cmp);
  53         /* creo buffer ordenado */
  54         if (!(b = bufford_new_bytes_size(buf_size, reg_size, cmp))) {
  55                 return 0; /* ERROR */
  56         }
  57         /* creo pool de archivos temporales ordenados */
  58         if (!(pool = mergepool_new())) {
  59                 bufford_delete(b);
  60                 return 0; /* ERROR */
  61         }
  62         /* abro archivo a ordenar */
  63         if (!(fp = fopen(filename, "r"))) {
  64                 mergepool_delete(pool);
  65                 bufford_delete(b);
  66                 return 0; /* ERROR */
  67         }
  68         /* lleno el buffer */
  69         while (1) {
  70                 int reg;
  71                 if (fscanf(fp, "%i", &reg) < 1) break; /* EOF */
  72                 if (!bufford_push(b, &reg)) break; /* buffer lleno */
  73         }
  74         /* creo archivos temporales ordenados usando el buffer */
  75         while (!bufford_empty(b)) {
  76                 int* c;
  77                 int x;
  78                 /* agrego un nuevo archivo temporal al pool */
  79                 if (!mergepool_add_file(pool)) {
  80                         fclose(fp);
  81                         mergepool_delete(pool);
  82                         bufford_delete(b);
  83                         return 0; /* ERROR */
  84                 }
  85                 /* lleno el archivo temporal ordenadamente usando el buffer */
  86                 for (c = bufford_pop_min(b); c; c = bufford_pop_next(b, &x)) {
  87                         /* si hay un valor en la entrada, lo inserto */
  88                         if ((fscanf(fp, "%i", &x) > 0) && !bufford_push(b, &x)) {
  89                                 /* ERROR: no se pudo insertar */
  90                                 fclose(fp);
  91                                 mergepool_delete(pool);
  92                                 bufford_delete(b);
  93                                 return 0; /* ERROR */
  94                         }
  95                         x = *c;
  96                         free(c);
  97                         /* Agrego el dato al último archivo temporal */
  98                         if (!mergepool_append_data(pool, x)) {
  99                                 fclose(fp);
 100                                 mergepool_delete(pool);
 101                                 bufford_delete(b);
 102                                 return 0; /* ERROR */
 103                         }
 104                 }
 105         }
 106         fclose(fp);
 107         /* Mezclo lotes */
 108         if (!(fp = fopen(filename, "w"))) {
 109                 mergepool_delete(pool);
 110                 bufford_delete(b);
 111         }
 112         /* obtengo próximo mínimo y lo guardo en el archivo de salida */
 113         while (mergepool_pop_min(pool, &min)) fprintf(fp, "%i\n", min);
 114         /* libero todos los recursos */
 115         fclose(fp);
 116         mergepool_delete(pool);
 117         bufford_delete(b);
 118         return 1; /* OK */
 119 }
 120