emufs/external_sort/mergepool.c

   1 /* vim: set noexpandtab tabstop=4 shiftwidth=4 wrap:
   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:05:15 ART 2004
  22  * Autores: Leandro Lucarella <llucare@fi.uba.ar>
  23  *----------------------------------------------------------------------------
  24  *
  25  * $Id$
  26  *
  27  */
  28
  29 /** \file
  30  *
  31  * Pool de archivos temporales para hacer un ordenamiento externo.
  32  *
  33  * Implementación de un pool de archivos temporales para hacer un ordenamiento
  34  * externo.
  35  *
  36  */
  37
  38 #include "mergepool.h"
  39 #include <string.h>
  40 #include <malloc.h>
  41 #include <assert.h>
  42
  43 static int mergepool_switch_to_input(MERGEPOOL* mp);
  44
  45 MERGEPOOL* mergepool_new(size_t reg_size, CMP_FUNC cmp)
  46 {
  47         MERGEPOOL* mp = malloc(sizeof(MERGEPOOL));
  48         if (!mp) return 0; /* ERROR: no hay más memoria */
  49         mp->pool = 0;
  50         mp->size = 0;
  51         mp->mode = OUTPUT;
  52         mp->reg_size = reg_size;
  53         mp->cmp = cmp;
  54         return mp;
  55 }
  56
  57 void mergepool_delete(MERGEPOOL* mp)
  58 {
  59         int i;
  60         assert(mp);
  61         assert(mp->pool);
  62         for (i = 0; i < mp->size; i++) mergefile_delete(mp->pool[i]);
  63         free(mp->pool);
  64         free(mp);
  65 }
  66
  67 MERGEFILE* mergepool_add_file(MERGEPOOL* mp)
  68 {
  69         MERGEFILE** pool;
  70         MERGEFILE*  new_mf = mergefile_new(mp->reg_size);
  71         assert(mp);
  72         assert(mp->mode == OUTPUT);
  73         if (!new_mf) return 0;
  74         if (!(pool = realloc(mp->pool, sizeof(MERGEFILE*) * (mp->size+1)))) {
  75                 mergefile_delete(new_mf);
  76                 return 0;
  77         }
  78         mp->pool = pool;
  79         mp->pool[mp->size] = new_mf;
  80         return mp->pool[mp->size++];
  81 }
  82
  83 int mergepool_append_data(MERGEPOOL* mp, void* data)
  84 {
  85         assert(data);
  86         assert(mp);
  87         assert(mp->pool);
  88         assert(mp->pool[mp->size-1]);
  89         assert(mp->mode == OUTPUT);
  90         return mergefile_push(mp->pool[mp->size-1], data);
  91 }
  92
  93 void* mergepool_pop_min(MERGEPOOL* mp)
  94 {
  95         void* min;
  96         int i;
  97         int assigned = -1; /* no asignado */
  98         assert(mp);
  99         assert(mp->pool);
 100         assert(mp->size);
 101         /* si todavía está en modo OUTPUT, lo pasó a INPUT */
 102         if (mp->mode == OUTPUT) {
 103                 mergepool_switch_to_input(mp);
 104         }
 105         /* busco el mínimo */
 106         for (i = 0; i < mp->size; i++) {
 107                 if (mergefile_has_more(mp->pool[i])     &&
 108                                 ((assigned == -1) || LT(mp, mergefile_peek(mp->pool[i]), min))){
 109                         assigned = i; /* se asigno el valor del archivo i */
 110                         min = mergefile_peek(mp->pool[i]);
 111                 }
 112         }
 113         /* si fue asignado */
 114         if (assigned != -1) {
 115                         mergefile_pop(mp->pool[assigned]); /* lo saco del archivo */
 116                         return min; /* OK, se obtuvo un mínimo */
 117         }
 118         return 0; /* si no fue asignado es porque no hay más archivos con datos */
 119 }
 120
 121 int mergepool_switch_to_input(MERGEPOOL* mp)
 122 {
 123         int i;
 124         assert(mp);
 125         assert(mp->pool);
 126         for (i = 0; i < mp->size; i++) {
 127                 /* lo paso a modo INPUT y si hubo error salgo */
 128                 if (!mergefile_switch_to_input(mp->pool[i])) return 0; /* ERROR */
 129         }
 130         mp->mode = INPUT;
 131         return 1; /* OK */
 132 }
 133