emufs/external_sort/bufford_test_sort.c

   1
   2 #include "bufford.h"
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include <assert.h>
   6
   7 /*
   8 typedef struct
   9 {
  10         int id;
  11         int estado;
  12         int nrofac;
  13 }
  14 RECORD;
  15 */
  16
  17 #define MERGEFILE_TEMPLATE "sorted_chunk.%i"
  18
  19 typedef struct
  20 {
  21         FILE* fp;
  22         char* filename;
  23         int   next;
  24         int   more;
  25 }
  26 MERGEFILE;
  27
  28 char* mergefile_makefilename(int i)
  29 {
  30         size_t size = sizeof(MERGEFILE_TEMPLATE) + 8; /* 8 más para el int */
  31         char* filename = malloc(size);
  32         if (!filename) return 0;
  33         /* Hasta que me de la memoria para crear el nombre del archivo */
  34         while (snprintf(filename, size, MERGEFILE_TEMPLATE, i) >= size) {
  35                 char* new;
  36                 size += 8;
  37                 new = realloc(filename, size);
  38                 if (new) {
  39                         filename = new;
  40                 } else {
  41                         free(filename);
  42                         return 0;
  43                 }
  44         }
  45         return filename;
  46 }
  47
  48 MERGEFILE* mergefile_new(int i)
  49 {
  50         MERGEFILE* mf = malloc(sizeof(MERGEFILE));
  51         if (!mf) {
  52                 return 0;
  53         }
  54         /* asigno el nombre de archivo */
  55         if (!(mf->filename = mergefile_makefilename(i))) {
  56                 free(mf);
  57                 return 0;
  58         }
  59         /* abre archivo */
  60         if (!(mf->fp = fopen(mf->filename, "rb"))) {
  61                 free(mf->filename);
  62                 free(mf);
  63                 return 0;
  64         }
  65         /* obtiene dato */
  66         if (fscanf(mf->fp, "%i", &(mf->next)) <= 0) {
  67                 fclose(mf->fp);
  68                 free(mf->filename);
  69                 free(mf);
  70                 return 0;
  71         }
  72         mf->more = 1;
  73         return mf;
  74 }
  75
  76 void mergefile_delete(MERGEFILE* mf)
  77 {
  78         assert(mf);
  79         assert(mf->fp);
  80         assert(mf->filename);
  81         fclose(mf->fp);
  82         remove(mf->filename);
  83         free(mf->filename);
  84         free(mf);
  85 }
  86
  87 int mergefile_peek_next(MERGEFILE* mf)
  88 {
  89         assert(mf);
  90         assert(mf->fp);
  91         assert(mf->more);
  92         return mf->next;
  93 }
  94
  95 int mergefile_pop_next(MERGEFILE* mf)
  96 {
  97         int ret;
  98         assert(mf);
  99         assert(mf->fp);
 100         assert(mf->more);
 101         ret = mf->next;
 102         /* obtiene dato, si no hay más, se activa el flag */
 103         if (fscanf(mf->fp, "%i", &(mf->next)) <= 0) mf->more = 0;
 104         return ret;
 105 }
 106
 107 int mergefile_has_more(MERGEFILE* mf)
 108 {
 109         assert(mf);
 110         assert(mf->fp);
 111         return mf->more;
 112 }
 113
 114 int cmp(void* x, void* y)
 115 {
 116         int xx = *(int*)x;
 117         int yy = *(int*)y;
 118         if (xx > yy) return 1;
 119         if (xx < yy) return -1;
 120         return 0;
 121 }
 122
 123 void buffer_dump(BUFFORD* b)
 124 {
 125         int* c;
 126         printf("Buffer: ");
 127         for (c = bufford_get_min(b); c; c = bufford_get_next(b, c))
 128                 printf("%i ", *c);
 129         printf("\n");
 130 }
 131
 132 int main(int argc, char* argv[])
 133 {
 134         FILE* fp;
 135         int i;
 136         BUFFORD* b = bufford_new(8, sizeof(int), &cmp);
 137         if (!b) return 1;
 138         if (!(fp = fopen(argv[1], "r"))) {
 139                 bufford_delete(b);
 140                 return 2;
 141         }
 142         /* lleno el buffer */
 143         while (1) {
 144                 int reg;
 145                 fscanf(fp, "%i", &reg);
 146                 if (feof(fp)) break;
 147                 if (!bufford_push(b, &reg)) break;
 148         }
 149         printf("Buffer lleno, hago el primer lote...\n");
 150         buffer_dump(b);
 151         /* Hago lotes */
 152         i = 0;
 153         while (!bufford_empty(b)) {
 154                 int* c;
 155                 int x;
 156                 FILE* fpo;
 157                 char filename[32];
 158                 snprintf(filename, sizeof(filename), "sorted_chunk.%i", i);
 159                 if (!(fpo = fopen(filename, "w"))) {
 160                         fclose(fp);
 161                         bufford_delete(b);
 162                         return 3;
 163                 }
 164                 printf("Creando lote %i:\n", i);
 165                 for (c = bufford_pop_min(b); c; c = bufford_pop_next(b, &x)) {
 166                         /* si hay un valor en la entrada, lo inserto */
 167                         if (!feof(fp)) fscanf(fp, "%i", &x);
 168                         if (!feof(fp) && !bufford_push(b, &x)) {
 169                                 /* ERROR: no se pudo insertar */
 170                                 fclose(fpo);
 171                                 fclose(fp);
 172                                 bufford_delete(b);
 173                                 return 4;
 174                         }
 175                         x = *c;
 176                         free(c);
 177                         printf("%- 8i\t", x);
 178                         fprintf(fpo, "%i\n", x);
 179                         buffer_dump(b);
 180                 }
 181                 printf("Lote %i finalizado!\n\n", i);
 182                 i++;
 183                 fclose(fpo);
 184         }
 185         fclose(fp);
 186         /* Mezclo lotes */
 187         {
 188         int n, min;
 189         MERGEFILE** mfpool = malloc(sizeof(MERGEFILE) * i);
 190         MERGEFILE* min_mf;
 191         FILE* fp = fopen("salida.txt", "w");
 192         assert(fp);
 193         assert(mfpool);
 194         printf("Abriendo archivos y buscando mínimo...\n");
 195         for (n = 0; n < i; n++) {
 196                 mfpool[n] = mergefile_new(n);
 197                 assert(mfpool[n]);
 198                 printf("Archivo %i: leído = %i\n", n, mergefile_peek_next(mfpool[n]));
 199                 if (!n || mergefile_peek_next(mfpool[n]) < min) {
 200                         min = mergefile_peek_next(mfpool[n]);
 201                         min_mf = mfpool[n];
 202                         printf("min = %i\n", min);
 203                 }
 204         }
 205         printf("Iterando...\n");
 206         while (1) {
 207                 int assigned = 0;
 208                 /* guardo el mínimo en el archivo de salida */
 209                 fprintf(fp, "%i\n", min);
 210                 mergefile_pop_next(min_mf); /* lo saco del archivo */
 211                 /* obtengo el próximo mínimo */
 212                 for (n = 0; n < i; n++) {
 213                         if (mergefile_has_more(mfpool[n])) {
 214                                 printf("Archivo %i: leído = %i\n", n, mergefile_peek_next(mfpool[n]));
 215                         } else {
 216                                 printf("Archivo %i: No hay más datos\n", n);
 217                         }
 218                         if (mergefile_has_more(mfpool[n]) && (!assigned || mergefile_peek_next(mfpool[n]) < min)) {
 219                                 assigned = 1;
 220                                 min = mergefile_peek_next(mfpool[n]);
 221                                 min_mf = mfpool[n];
 222                                 printf("min = %i\n", min);
 223                         }
 224                 }
 225                 /* si no hay más datos en los archivos, salimos */
 226                 if (!assigned) break;
 227         }
 228         fclose(fp);
 229         for (n = 0; n < i; n++) {
 230                 mergefile_delete(mfpool[n]);
 231         }
 232         free(mfpool);
 233         }
 234         bufford_delete(b);
 235         return 0;
 236 }
 237