Секция 2 из 2 - Предыдущая - Следующая

} tmpFileType;

static tmpFileType **file;      /* массив информации о временных файлах */
static int nTmpFiles;           /* количество временных файлов */
static char *ifName;            /* имя входного файла */
static char *ofName;            /* имя выходного файла */

static int level;               /* уровень проходов */
static int nNodes;              /* количество узлов для дерева выбора */

void deleteTmpFiles(void) {
    int i;

    /* удалить сливаемые файлы и освободить ресурсы */
    if (file) {
        for (i = 0; i < nTmpFiles; i++) {
            if (file[i]) {
                if (file[i]->fp) fclose(file[i]->fp);
                if (*file[i]->name) remove(file[i]->name);
                free (file[i]);
            }
        }
        free (file);
    }
}

void termTmpFiles(int rc) {

    /* очистить файлы */
    remove(ofName);
    if (rc == 0) {
        int fileT;

        /* file[T] содержит результаты */
        fileT = nTmpFiles - 1;
        fclose(file[fileT]->fp); file[fileT]->fp = NULL;
        if (rename(file[fileT]->name, ofName)) {
            perror("io1");
            deleteTmpFiles();
            exit(1);
        }
        *file[fileT]->name = 0;
    }
    deleteTmpFiles();
}

void cleanExit(int rc) {

    /* очистить временные файлы и выйти */
    termTmpFiles(rc);
    exit(rc);
}

void *safeMalloc(size_t size) {
    void *p;

    /* Безопасно выделить память и инициализоваться */
    if ((p = calloc(1, size)) == NULL) {
        printf("error: malloc failed, size = %d\n", size);
        cleanExit(1);
    }
    return p;
}

void initTmpFiles(void) {
    int i;
    tmpFileType *fileInfo;

    /* инициализовать файлы для слияния */
    if (nTmpFiles < 3) nTmpFiles = 3;
    file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
    fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
    for (i = 0; i < nTmpFiles; i++) {
        file[i] = fileInfo + i;
        sprintf(file[i]->name, FNAME, i);
        if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
            perror("io2");
            cleanExit(1);
        }
    }
}

recType *readRec(void) {

    typedef struct iNodeTag {   /* внутренний узел */
        struct iNodeTag *parent;/* предок внутреннего узла */
        struct eNodeTag *loser; /* внешний проигравший */
    } iNodeType;

    typedef struct eNodeTag {   /* внешний узел */
        struct iNodeTag *parent;/* предок внешнего узла */
        recType rec;            /* вводимая запись */
        int run;                /* номер прохода */
        bool valid;             /* вводимая запись годна */
    } eNodeType;

    typedef struct nodeTag {
        iNodeType i;            /* внутренний узел */
        eNodeType e;            /* внешний узел */
    } nodeType;

    static nodeType *node;      /* массив узлов дерева выбора */
    static eNodeType *win;      /* новый победитель */
    static FILE *ifp;           /* входной файл */
    static bool eof;            /* верно, если конец входного файла */
    static int maxRun;          /* максимальное число проходов */
    static int curRun;          /* номер текущего прохода */
    iNodeType *p;               /* указатель на внутренние узлы */
    static bool lastKeyValid;   /* верно, если lastKey годен */
    static keyType lastKey;     /* последний ключ lastKey записан */

    /* Прочитать следующую запись путем выбора с замещением */

    /* Проверка на первый выхов */
    if (node == NULL) {
        int i;

        if (nNodes < 2) nNodes = 2;
        node = safeMalloc(nNodes * sizeof(nodeType));
        for (i = 0; i < nNodes; i++) {
            node[i].i.loser = &node[i].e;
            node[i].i.parent = &node[i/2].i;
            node[i].e.parent = &node[(nNodes + i)/2].i;
            node[i].e.run = 0;
            node[i].e.valid = false;
        }
        win = &node[0].e;
        lastKeyValid = false;

        if ((ifp = fopen(ifName, "rb")) == NULL) {
            printf("error: file %s, unable to open\n", ifName);
            cleanExit(1);
        }
    }

    while (1) {

        /* заместить предыдущего победителя новой записью */
        if (!eof) {
            if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
                if ((!lastKeyValid || compLT(win->rec.key, lastKey))
                && (++win->run > maxRun))
                    maxRun = win->run;
                win->valid = true;
            } else if (feof(ifp)) {
                fclose(ifp);
                eof = true;
                win->valid = false;
                win->run = maxRun + 1;
            } else {
                perror("io4");
                cleanExit(1);
            }
        } else {
            win->valid = false;
            win->run = maxRun + 1;
        }

        /* привести в порядок предков победителя и проигравшего */
        p = win->parent;
        do {
            bool swap;
            swap = false;
            if (p->loser->run < win->run) {
                swap = true;
            } else if (p->loser->run == win->run) {
                if (p->loser->valid && win->valid) {
                    if (compLT(p->loser->rec.key, win->rec.key))
                        swap = true;
                } else {
                    swap = true;
                }
            }
            if (swap) {
                /* p должно быть победителем */
                eNodeType *t;

                t = p->loser;
                p->loser = win;
                win = t;
            }
            p = p->parent;
        } while (p != &node[0].i);

        /* конец прохода ? */
        if (win->run != curRun) {
            /* win->run = curRun + 1 */
            if (win->run > maxRun) {
                /* конец вывода */
                free(node);
                return NULL;
            }
            curRun = win->run;
        }

        /* вывести верх дерева */
        if (win->run) {
            lastKey = win->rec.key;
            lastKeyValid = true;
            return &win->rec;
        }
    }
}

void makeRuns(void) {
    recType *win;       /* победитель */
    int fileT;          /* прошлый файл */
    int fileP;          /* следующий за прошлым файлом  */
    int j;              /* выбираем file[j] */


    /* Сделать инициализационные проходы через выбор с замещением.
     * Проходы напианы с использованием распределения Фибоначчи.
     */

    /* инициализовать файловые структуры */
    fileT = nTmpFiles - 1;
    fileP = fileT - 1;
    for (j = 0; j < fileT; j++) {
        file[j]->fib = 1;
        file[j]->dummy = 1;
    }
    file[fileT]->fib = 0;
    file[fileT]->dummy = 0;

    level = 1;
    j = 0;


    win = readRec();
    while (win) {
        bool anyrun;

        anyrun = false;
        for (j = 0; win && j <= fileP; j++) {
            bool run;

            run = false;
            if (file[j]->valid) {
                if (!compLT(win->key, file[j]->rec.key)) {
                    /* добавить к существующему проходу */
                    run = true;
                } else if (file[j]->dummy) {
                    /* начать новый проход */
                    file[j]->dummy--;
                    run = true;
                }
            } else {
                /* первый проход в файле */
                file[j]->dummy--;
                run = true;
            }

            if (run) {
                anyrun = true;

                /* полный проход */
                while(1) {
                    if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
                        perror("io3");
                        cleanExit(1);
                    }
                    file[j]->rec.key = win->key;
                    file[j]->valid = true;
                    if ((win = readRec()) == NULL) break;
                    if (compLT(win->key, file[j]->rec.key)) break;
                }
            }
        }

        /* Если нет места для проходов - вверх на уровень */
        if (!anyrun) {
            int t;
            level++;
            t = file[0]->fib;
            for (j = 0; j <= fileP; j++) {
                file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
                file[j]->fib = t + file[j+1]->fib;
            }
        }
    }
}

void rewindFile(int j) {
    /* Идти в начало file[j] и читать первую запись */
    file[j]->eor = false;
    file[j]->eof = false;
    rewind(file[j]->fp);
    if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
        if (feof(file[j]->fp)) {
            file[j]->eor = true;
            file[j]->eof = true;
        } else {
            perror("io5");
            cleanExit(1);
        }
    }
}

void mergeSort(void) {
    int fileT;
    int fileP;
    int j;
    tmpFileType *tfile;

    /* Многофазная сортировка слиянием */

    fileT = nTmpFiles - 1;
    fileP = fileT - 1;

    /* снабдить файлы информацией */
    for (j = 0; j < fileT; j++) {
        rewindFile(j);
    }

    /* Каждый проход по циклу сливает один проход */
    while (level) {
        while(1) {
            bool allDummies;
            bool anyRuns;

            /* сканировать на предмет проходов */
            allDummies = true;
            anyRuns = false;
            for (j = 0; j <= fileP; j++) {
                if (!file[j]->dummy) {
                    allDummies = false;
                    if (!file[j]->eof) anyRuns = true;
                }
            }

            if (anyRuns) {
                int k;
                keyType lastKey;

                /* слить 1 проход file[0]..file[P] --> в file[T] */

                while(1) {
                   /* Каждый проход по циклу записывает 1 запись в file[fileT]
*/

                    /* Найти наименьший ключ */
                    k = -1;
                    for (j = 0; j <= fileP; j++) {
                        if (file[j]->eor) continue;
                        if (file[j]->dummy) continue;
                        if (k < 0 ||
                        (k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
                            k = j;
                    }
                    if (k < 0) break;

                    /* записать record[k] в file[fileT] */
                    if (fwrite(&file[k]->rec, sizeof(recType), 1,
                            file[fileT]->fp) != 1) {
                        perror("io6");
                        cleanExit(1);
                    }

                    /* заменить record[k] */
                    lastKey = file[k]->rec.key;
                    if (fread(&file[k]->rec, sizeof(recType), 1,
                            file[k]->fp) == 1) {
                        /* проверить на предмет конца пробега file[s] */
                        if (compLT(file[k]->rec.key, lastKey))
                            file[k]->eor = true;
                    } else if (feof(file[k]->fp)) {
                        file[k]->eof = true;
                        file[k]->eor = true;
                    } else {
                        perror("io7");
                        cleanExit(1);
                    }
                }

                /* Подкорректировкать холостые */
                for (j = 0; j <= fileP; j++) {
                    if (file[j]->dummy) file[j]->dummy--;
                    if (!file[j]->eof) file[j]->eor = false;
                }

            } else if (allDummies) {
                for (j = 0; j <= fileP; j++)
                    file[j]->dummy--;
                file[fileT]->dummy++;
            }

            /* конец прохода */
            if (file[fileP]->eof && !file[fileP]->dummy) {
                /* completed a fibonocci-level */
                level--;
                if (!level) {
                    /* готово, file[fileT] содержит данные */
                    return;
                }

                /* fileP истощился, открываем новый такой же */
                fclose(file[fileP]->fp);
                if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
                        == NULL) {
                    perror("io8");
                    cleanExit(1);
                }
                file[fileP]->eof = false;
                file[fileP]->eor = false;

                rewindFile(fileT);

                /* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
                tfile = file[fileT];
                memmove(file + 1, file, fileT * sizeof(tmpFileType*));
                file[0] = tfile;

                /* начать новые проходы */
                for (j = 0; j <= fileP; j++)
                    if (!file[j]->eof) file[j]->eor = false;
            }
        }

    }
}


void extSort(void) {
    initTmpFiles();
    makeRuns();
    mergeSort();
    termTmpFiles(0);
}

int main(int argc, char *argv[]) {

    /* командная строка:
     *
     *   ext ifName ofName nTmpFiles nNodes
     *
     *   ext in.dat out.dat 5 2000
     *       читает in.dat, сортирует, используя 5 файлов и 2000 узлов,
     *        выводит в out.dat
     */
    if (argc != 5) {
        printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
        cleanExit(1);
    }

    ifName = argv[1];
    ofName = argv[2];
    nTmpFiles = atoi(argv[3]);
    nNodes = atoi(argv[4]);

    printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
        nTmpFiles, nNodes, sizeof(recType));

    extSort();

    return 0;
}

Секция 2 из 2 - Предыдущая - Следующая

© faqs.org.ru