#include <dirent.h>
#include <errno.h>
#include <libgen.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include <unistd.h>

int badgrep(const char *file, int size, const char *pattern, int plen);
int KMP_index(const char *data, int dlen, const char *pattern, int plen);
void KMP_failure(const char *pattern, char *failure, int plen);
void ffail(const char *file);

char *prog_invoked;

int main(int argc, char const *argv[])
{
    prog_invoked = basename((char *)argv[0]);
    if (argc < 4) {
        fprintf(stderr, "%s: %s\n", prog_invoked, "Too few arguments");
        exit(EXIT_FAILURE);
    }

    char *dirpath = NULL;
    if ((dirpath = realpath(argv[1],dirpath)) == NULL) {
        ffail(argv[1]);
        exit(EXIT_FAILURE);
    }

    DIR *dir = NULL;
    if ((dir = opendir(dirpath)) == NULL) {
        ffail(dirpath);
        exit(EXIT_FAILURE);
    }

    struct dirent *item;
    int psize = strlen(argv[2]);

    int pid = 0;
    int status = 0;
    int max_active = atoi(argv[3]);
    int now_active = 0;

    chdir(argv[1]);
    int size = 0;
    char *rpath = NULL;

    /*  Spawn children, limiting to max_active  */
    for (; (item = readdir(dir)) != NULL; ++now_active) {
        for (; now_active >= max_active; --now_active)
            wait(&status);
        if ((item->d_name[0] == '.') || (item->d_type == 'd')) {
            --now_active;
            continue;
        }
        pid = fork();
        // Error
        if (pid < 0) {
            fprintf(stderr, "%s: %s\n", prog_invoked,strerror(errno));
            exit(EXIT_FAILURE);
        }
        // Child
        if (pid == 0) {
            if ((rpath = realpath(item->d_name,rpath)) == NULL) {
                ffail(item->d_name);
                exit(EXIT_FAILURE);
            }
            struct stat *st = (struct stat *)malloc(sizeof(struct stat));
            if (stat(rpath, st) == -1) {
                ffail(rpath);
                exit(EXIT_FAILURE);
            }
            size = (int)st->st_size;

            if (S_ISREG(st->st_mode))
            {
                int has;
                if ((has = badgrep(rpath, size, argv[2], psize)) > 0) {
                    printf("[%d] %s\t%d times in %d bytes\n", getpid(), rpath, has, size);
                }
            }
            free(st);
            free(rpath);

            exit(EXIT_SUCCESS);
        }
    }
    for (; now_active != 0; --now_active)
            wait(&status);
    closedir(dir);

    exit(EXIT_SUCCESS);
}

void ffail(const char *file)
{
  fprintf(stderr, "%s: %s: %s\n", prog_invoked, file, strerror(errno));
}

/*  The Knuth-Morris-Pratt algorithm  */
int KMP_index(const char *data, int dlen, const char *pattern, int plen)
{
    static int start = 0;
    char failure[plen];
    KMP_failure(pattern, failure, plen);

    int j = 0, i = 0;

    for (i = start; i < dlen; i++) {
        while ((j > 0) && pattern[j] != data[i]) {
            j = failure[j-1];
        }
        if (pattern[j] == data[i]) {
            j++;
        }
        if (j == plen) {
            start = i + plen;
            return i - plen + 1;
        }
    }
    return -1;
}
void KMP_failure(const char *pattern, char *failure, int plen)
{
    int j = 0, i = 0;
    for (i = 1; i < plen; i++) {
        while ((j > 0) && pattern[j] != pattern[i]) {
            j = failure[j - 1];
        }
        if (pattern[j] == pattern[i]) {
            j++;
        }
        failure[i] = j;
    }
}


/*  Quick n dirty search for pattern in file  */
int badgrep(const char *file, int size, const char *pattern, int plen)
{
    char *array = (char *)malloc(size);

    FILE *stream;
    if ((stream = fopen(file, "r")) == NULL) {
        ffail(file);
        return -1;
    }
    char c = 0;
    int i = 0;
    while ((c = fgetc(stream)) != EOF) {
        array[i++] = c;
    }
    if (ferror(stream)) {
        ffail(file);
        return -1;
    }
    fclose(stream);

    int count = 0;
    int pos = -1;
    while ((pos = KMP_index(array, size, pattern, plen)) > -1) {
        count++;
    }
    free(array);
    return count;
}