svn.
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)
--- /dev/null
+/* 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 <llucare@fi.uba.ar>
+ *----------------------------------------------------------------------------
+ *
+ * $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 <string.h>
+#include <malloc.h>
+#include <assert.h>
+
+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 */
+}
+
--- /dev/null
+/* 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 <llucare@fi.uba.ar>
+ *----------------------------------------------------------------------------
+ *
+ * $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_ */
+
#include "bufford.h"
-#include "mergefile.h"
+#include "mergepool.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>
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;
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);
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;
}
projects / z.facultad / 75.06 / emufs.git / commitdiff