From 0c66d96638808a1d1ce87701ef3f7980ccee3e22 Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sun, 30 May 2004 10:14:21 +0000 Subject: [PATCH] Se separa el manejo de archivos temporales como un pool. Se agregan keywords del svn. --- emufs/external_sort/Makefile | 2 +- emufs/external_sort/mergepool.c | 125 ++++++++++++++++++++++++++++++++ emufs/external_sort/mergepool.h | 62 ++++++++++++++++ emufs/external_sort/sort_test.c | 86 ++++++---------------- 4 files changed, 211 insertions(+), 64 deletions(-) create mode 100644 emufs/external_sort/mergepool.c create mode 100644 emufs/external_sort/mergepool.h diff --git a/emufs/external_sort/Makefile b/emufs/external_sort/Makefile index 7cc6c15..58ae406 100644 --- a/emufs/external_sort/Makefile +++ b/emufs/external_sort/Makefile @@ -25,7 +25,7 @@ CXXFLAGS = $(CFLAGS) -fno-inline all: $(TARGETS) bufford_test: bufford.o bufford_test.o -sort_test: bufford.o mergefile.o sort_test.o +sort_test: bufford.o mergefile.o mergepool.o sort_test.o clean: @$(RM) -fv *.o $(TARGETS) diff --git a/emufs/external_sort/mergepool.c b/emufs/external_sort/mergepool.c new file mode 100644 index 0000000..c60af02 --- /dev/null +++ b/emufs/external_sort/mergepool.c @@ -0,0 +1,125 @@ +/* vim: set noexpandtab tabstop=4 shiftwidth=4 wrap: + *---------------------------------------------------------------------------- + * emufs + *---------------------------------------------------------------------------- + * This file is part of emufs. + * + * emufs is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * emufs is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + * details. + * + * You should have received a copy of the GNU General Public License along + * with emufs; if not, write to the Free Software Foundation, Inc., 59 Temple + * Place, Suite 330, Boston, MA 02111-1307 USA + *---------------------------------------------------------------------------- + * Creado: dom may 30 07:05:15 ART 2004 + * Autores: Leandro Lucarella + *---------------------------------------------------------------------------- + * + * $Id$ + * + */ + +/** \file + * + * Pool de archivos temporales para hacer un ordenamiento externo. + * + * Implementación de un pool de archivos temporales para hacer un ordenamiento + * externo. + * + */ + +#include "mergepool.h" +#include +#include +#include + +static int mergepool_switch_to_input(MERGEPOOL* mp); + +MERGEPOOL* mergepool_new() +{ + MERGEPOOL* mp = malloc(sizeof(MERGEPOOL)); + if (!mp) return 0; /* ERROR: no hay más memoria */ + mp->pool = 0; + mp->size = 0; + mp->mode = OUTPUT; + return mp; +} + +void mergepool_delete(MERGEPOOL* mp) +{ + int i; + assert(mp); + assert(mp->pool); + for (i = 0; i < mp->size; i++) mergefile_delete(mp->pool[i]); + free(mp->pool); + free(mp); +} + +MERGEFILE* mergepool_add_file(MERGEPOOL* mp) +{ + MERGEFILE** pool; + MERGEFILE* new_mf = mergefile_new(); + assert(mp); + assert(mp->mode == OUTPUT); + if (!new_mf) return 0; + if (!(pool = realloc(mp->pool, sizeof(MERGEFILE*) * (mp->size+1)))) { + mergefile_delete(new_mf); + return 0; + } + mp->pool = pool; + mp->pool[mp->size] = new_mf; + return mp->pool[mp->size++]; +} + +int mergepool_append_data(MERGEPOOL* mp, int data) +{ + assert(mp); + assert(mp->pool); + assert(mp->pool[mp->size-1]); + assert(mp->mode == OUTPUT); + return mergefile_push(mp->pool[mp->size-1], data); +} + +int mergepool_pop_min(MERGEPOOL* mp, int* min) +{ + int i; + int assigned = -1; + assert(mp); + assert(mp->pool); + assert(mp->size); + if (mp->mode == OUTPUT) { + mergepool_switch_to_input(mp); + } + for (i = 0; i < mp->size; i++) { + if (mergefile_has_more(mp->pool[i]) + && ((assigned == -1) || mergefile_peek(mp->pool[i]) < *min)) { + assigned = i; + *min = mergefile_peek(mp->pool[i]); + } + } + if (assigned != -1) { + mergefile_pop(mp->pool[assigned]); /* lo saco del archivo */ + return 1; /* OK, se obtuvo un mínimo */ + } + return 0; /* No hay más */ +} + +int mergepool_switch_to_input(MERGEPOOL* mp) +{ + int i; + assert(mp); + assert(mp->pool); + for (i = 0; i < mp->size; i++) { + if (!mergefile_switch_to_input(mp->pool[i])) return 0; + } + mp->mode = INPUT; + return 1; /* OK */ +} + diff --git a/emufs/external_sort/mergepool.h b/emufs/external_sort/mergepool.h new file mode 100644 index 0000000..49dee6a --- /dev/null +++ b/emufs/external_sort/mergepool.h @@ -0,0 +1,62 @@ +/* vim: set noexpandtab tabstop=4 shiftwidth=4 wrap: + *---------------------------------------------------------------------------- + * emufs + *---------------------------------------------------------------------------- + * This file is part of emufs. + * + * emufs is free software; you can redistribute it and/or modify it under the + * terms of the GNU General Public License as published by the Free Software + * Foundation; either version 2 of the License, or (at your option) any later + * version. + * + * emufs is distributed in the hope that it will be useful, but WITHOUT ANY + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS + * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more + * details. + * + * You should have received a copy of the GNU General Public License along + * with emufs; if not, write to the Free Software Foundation, Inc., 59 Temple + * Place, Suite 330, Boston, MA 02111-1307 USA + *---------------------------------------------------------------------------- + * Creado: dom may 30 07:07:53 ART 2004 + * Autores: Leandro Lucarella + *---------------------------------------------------------------------------- + * + * $Id$ + * + */ + +/** \file + * + * Pool de archivos temporales para hacer un ordenamiento externo. + * + * Interfaz de un pool de archivos temporales para hacer un ordenamiento + * externo. + * + */ + +#ifndef _MERGEPOOL_H_ +#define _MERGEPOOL_H_ + +#include "mergefile.h" + +typedef struct +{ + MERGEFILE** pool; + size_t size; + enum { INPUT, OUTPUT } mode; +} +MERGEPOOL; + +MERGEPOOL* mergepool_new(); + +void mergepool_delete(MERGEPOOL* mp); + +MERGEFILE* mergepool_add_file(MERGEPOOL* mp); + +int mergepool_append_data(MERGEPOOL* mp, int data); + +int mergepool_pop_min(MERGEPOOL* mp, int* min); + +#endif /* _MERGEPOOL_H_ */ + diff --git a/emufs/external_sort/sort_test.c b/emufs/external_sort/sort_test.c index 234e571..0814e98 100644 --- a/emufs/external_sort/sort_test.c +++ b/emufs/external_sort/sort_test.c @@ -1,6 +1,6 @@ #include "bufford.h" -#include "mergefile.h" +#include "mergepool.h" #include #include #include @@ -35,15 +35,20 @@ void buffer_dump(BUFFORD* b) int main(int argc, char* argv[]) { - MERGEFILE** mfpool = 0; + MERGEPOOL* pool; FILE* fp; int i; BUFFORD* b = bufford_new(8, sizeof(int), &cmp); if (!b) return 1; - if (!(fp = fopen(argv[1], "r"))) { + if (!(pool = mergepool_new())) { bufford_delete(b); return 2; } + if (!(fp = fopen(argv[1], "r"))) { + mergepool_delete(pool); + bufford_delete(b); + return 12; + } /* lleno el buffer */ while (1) { int reg; @@ -58,41 +63,33 @@ int main(int argc, char* argv[]) while (!bufford_empty(b)) { int* c; int x; - MERGEFILE** mfpool_new = realloc(mfpool, sizeof(MERGEFILE) * (i+1)); - if (!mfpool_new) { - int j; - for (j = 0; j < i; j++) mergefile_delete(mfpool[j]); - free(mfpool); - bufford_delete(b); - return 3; - } else { - mfpool = mfpool_new; - } - if (!(mfpool[i] = mergefile_new())) { - int j; + printf("Creando lote %i:\n", i); + if (!mergepool_add_file(pool)) { fclose(fp); - for (j = 0; j < i; j++) mergefile_delete(mfpool[j]); - free(mfpool); + mergepool_delete(pool); bufford_delete(b); return 3; } - printf("Creando lote %i:\n", i); for (c = bufford_pop_min(b); c; c = bufford_pop_next(b, &x)) { /* si hay un valor en la entrada, lo inserto */ if (!feof(fp)) fscanf(fp, "%i", &x); if (!feof(fp) && !bufford_push(b, &x)) { /* ERROR: no se pudo insertar */ - int j; - for (j = 0; j < i+1; j++) mergefile_delete(mfpool[j]); - free(mfpool); fclose(fp); + mergepool_delete(pool); bufford_delete(b); return 4; } x = *c; free(c); printf("%- 8i\t", x); - if (!mergefile_push(mfpool[i], x)) printf("No se pudo escribir en el mergefile %i\n", i); + if (!mergepool_append_data(pool, x)) { + printf("No se pudo escribir en el mergefile %i\n", i); + fclose(fp); + mergepool_delete(pool); + bufford_delete(b); + return 4; + } buffer_dump(b); } printf("Lote %i finalizado!\n\n", i); @@ -101,53 +98,16 @@ int main(int argc, char* argv[]) fclose(fp); /* Mezclo lotes */ { - int n, min; - MERGEFILE* min_mf; + int min; FILE* fp = fopen("salida.txt", "w"); assert(fp); printf("Abriendo archivos y buscando mínimo...\n"); - for (n = 0; n < i; n++) { - if (!mergefile_switch_to_input(mfpool[n])) { - printf("No se pudo pasar a modo entrada el mfpool %i.\n", n); - return 15; - } - assert(mfpool[n]); - printf("Archivo %i: leído = %i\n", n, mergefile_peek(mfpool[n])); - if (!n || mergefile_peek(mfpool[n]) < min) { - min = mergefile_peek(mfpool[n]); - min_mf = mfpool[n]; - printf("min = %i\n", min); - } - } printf("Iterando...\n"); - while (1) { - int assigned = 0; - /* guardo el mínimo en el archivo de salida */ - fprintf(fp, "%i\n", min); - mergefile_pop(min_mf); /* lo saco del archivo */ - /* obtengo el próximo mínimo */ - for (n = 0; n < i; n++) { - if (mergefile_has_more(mfpool[n])) { - printf("Archivo %i: leído = %i\n", n, mergefile_peek(mfpool[n])); - } else { - printf("Archivo %i: No hay más datos\n", n); - } - if (mergefile_has_more(mfpool[n]) && (!assigned || mergefile_peek(mfpool[n]) < min)) { - assigned = 1; - min = mergefile_peek(mfpool[n]); - min_mf = mfpool[n]; - printf("min = %i\n", min); - } - } - /* si no hay más datos en los archivos, salimos */ - if (!assigned) break; - } + /* voy obteniendo el próximo mínimo y guardándolo en el archivo de salida */ + while (mergepool_pop_min(pool, &min)) fprintf(fp, "%i\n", min); fclose(fp); - for (n = 0; n < i; n++) { - mergefile_delete(mfpool[n]); - } - free(mfpool); } + mergepool_delete(pool); bufford_delete(b); return 0; } -- 2.43.0