/*
The MIT License (MIT)

Copyright © 2020-2025 pacman64

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the “Software”), to deal
in the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/

/*
You can build this command-line app by running

cc -Wall -s -O3 -march=native -mtune=native -flto -o ./dedup ./dedup.c
*/

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#ifdef _WIN32
#include <fcntl.h>
#include <windows.h>
#endif

#ifdef RED_ERRORS
#define ERROR_STYLE "\x1b[38;2;204;0;0m"
#ifdef __APPLE__
#define ERROR_STYLE "\x1b[31m"
#endif
#define RESET_STYLE "\x1b[0m"
#else
#define ERROR_STYLE
#define RESET_STYLE
#endif

#define ERROR_LINE(MSG) (ERROR_STYLE MSG RESET_STYLE "\n")

#define SIMPLE_HASHING

#define BAD_ALLOC 2

const char* info = ""
"dedup [filepaths...]\n"
"\n"
"Deduplicate lines, ensuring each unique input line appears only once on the\n"
"output. Unlike the standard cmd-line app `uniq`, which only works correctly\n"
"when given sorted lines, this tool works correctly without any scrambling.\n"
"";

// set_growth is the growth factor to use when rehashing a set
const size_t set_growth = 2;

// prime numbers right under various binary-kb values:
// 16381, 32749, 65521, 131071

// slice is a growable region of bytes in memory
typedef struct slice {
    // ptr is the starting place of the region
    unsigned char* ptr;

    // len is how many bytes are currently being used
    size_t len;

    // cap is how many bytes the memory region has available
    size_t cap;
} slice;

// span is a slice without a capacity
typedef struct span {
    unsigned char* ptr;
    size_t len;
} span;

// string_bucket is any of the buckets used in struct string_set; these
// are supposed to be overallocated to fit the null-terminated string
// right after the official fields
typedef struct string_bucket {
    // len is how many bytes are in the string
    size_t len;

    // the null-terminated string follows the fields like a ghost,
    // as c89 doesn't support trailing fake-field arrays in a struct
} string_bucket;

// string_set is a hash-table with no associated values, thus acting as a set
typedef struct string_set {
    string_bucket** items;

    // count is how many items there are
    size_t count;

    // cap is how many spots there are
    size_t cap;
} string_set;

void init_string_set(string_set* set, size_t cap) {
    set->count = 0;
    set->items = malloc(sizeof(string_bucket*) * cap);
    if (set->items == NULL) {
        set->cap = 0;
        return;
    }
    set->cap = cap;

    for (size_t i = 0; i < cap; i++) {
        set->items[i] = NULL;
    }
}

void deallocate(string_set* set) {
    for (size_t i = 0; i < set->cap; i++) {
        free(set->items[i]);
    }
    free(set->items);
}

// djb2(33) http://www.cse.yorku.ca/~oz/hash.html
// size_t hash(const unsigned char* s) {
//     size_t hash = 5381;
//     for (size_t i = 0; s[i] != 0; i++) {
//         hash = (33 * hash) ^ s[i];
//     }
//     return hash;
// }

// sdbm(65599) http://www.cse.yorku.ca/~oz/hash.html
size_t hash(const unsigned char* s) {
    size_t hash = 0;
    for (size_t i = 0; s[i] != 0; i++) {
        hash = (65599 * hash) + s[i];
    }
    return hash;
}

size_t index_chain(const string_set* set, const unsigned char* s) {
    return hash(s) % set->cap;
}

unsigned char* get_string(const string_bucket* b) {
    return (unsigned char*)((size_t)b + sizeof(*b));
}

bool check(const string_bucket* b, const span s) {
    if (s.len != b->len) {
        return false;
    }

    size_t len = s.len;
    const unsigned char* x = s.ptr;
    const unsigned char* y = get_string(b);
    for (size_t i = 0; i < len; i++) {
        if (x[i] != y[i]) {
            return false;
        }
    }
    return true;
}

size_t find_spot(string_set* set, size_t start, const span s, bool* got);

bool rehash(string_set* set) {
    string_set larger;
    init_string_set(&larger, set_growth * set->cap);
    if (larger.items == NULL) {
        return false;
    }

    for (size_t i = 0; i < set->cap; i++) {
        string_bucket* b = set->items[i];
        if (b == NULL) {
            continue;
        }

        span s;
        s.ptr = get_string(b);
        s.len = b->len;
        bool already_there = false;

        const size_t start = index_chain(&larger, s.ptr);
        const size_t i = find_spot(&larger, start, s, &already_there);
        larger.items[i] = b;
    }

    free(set->items);
    set->items = larger.items;
    set->cap = larger.cap;
    return true;
}

size_t find_spot(string_set* set, size_t start, const span s, bool* got) {
    *got = false;

    for (size_t i = start; i < set->cap; i++) {
        const string_bucket* b = set->items[i];
        if (b == NULL) {
            return i;
        }

        if (check(b, s)) {
            *got = true;
            return i;
        }
    }

    for (size_t i = 0; i < start; i++) {
        const string_bucket* b = set->items[i];
        if (b == NULL) {
            return i;
        }

        if (check(b, s)) {
            *got = true;
            return i;
        }
    }

    // should never happen
    return 0;
}

// add returns null only when an allocation failed
string_bucket* add(string_set* set, const span s, bool* already_there) {
    size_t start = index_chain(set, s.ptr);
    size_t i = find_spot(set, start, s, already_there);
    if (*already_there) {
        return set->items[i];
    }

    string_bucket* b = malloc(sizeof(string_bucket) + s.len + 1);
    if (b == NULL) {
        return NULL;
    }

    memcpy(get_string(b), s.ptr, s.len);
    b->len = s.len;
    set->count++;

    if (3 * set->count > 4 * set->cap) {
        if (!rehash(set)) {
            free(b);
            return NULL;
        }
    }
    return b;
}

bool handle_reader(FILE* w, FILE* r, slice* line, string_set* seen) {
    if (line->ptr == NULL || seen->items == NULL) {
        return false;
    }

    for (size_t i = 0; !feof(w); i++) {
        ssize_t len = getline((char**)&line->ptr, &line->cap, r);
        if (line->ptr == NULL) {
            fprintf(stderr, "\n");
            fprintf(stderr, ERROR_LINE("out of memory"));
            exit(BAD_ALLOC);
        }

        if (len < 0) {
            break;
        }

        // ignore trailing line-feeds: all output lines end with one anyway
        const unsigned char* p = line->ptr;
        if (len > 0 && p[len - 1] == '\n') {
            len--;
        }
        line->len = len;

        span s;
        s.ptr = line->ptr;
        s.len = len;
        bool already_there = false;

        if (add(seen, s, &already_there) == NULL) {
            fprintf(stderr, ERROR_LINE("out of memory"));
            exit(BAD_ALLOC);
            return false;
        }

        // ignore already-seen lines
        if (already_there) {
            continue;
        }

        // emit each distinct line only once, the first time it's seen
        fwrite(line->ptr, 1, line->len, w);
        fputc('\n', w);
    }

    return true;
}

// handle_file handles data from the filename given; returns false only when
// the file can't be opened
bool handle_file(FILE* w, const char* path, slice* line, string_set* seen) {
    FILE* f = fopen(path, "rb");
    if (f == NULL) {
        fprintf(stderr, ERROR_LINE("can't open file named '%s'"), path);
        return false;
    }

    const bool ok = handle_reader(w, f, line, seen);
    fclose(f);
    return ok;
}

// run returns the number of errors
int run(int argc, char** argv, FILE* w) {
    size_t start = 1;
    if (start < argc && strcmp(argv[start], "--") == 0) {
        start++;
    }

    slice line;
    line.len = 0;
    line.cap = 32 * 1024;
    line.ptr = malloc(line.cap);
    if (line.ptr == NULL) {
        fprintf(stderr, ERROR_LINE("out of memory"));
        exit(BAD_ALLOC);
    }

    string_set files;
    init_string_set(&files, argc - start);
    if (files.items == NULL) {
        fprintf(stderr, ERROR_LINE("out of memory"));
        exit(BAD_ALLOC);
    }

    string_set seen;
    init_string_set(&seen, 64 * 1024);
    if (seen.items == NULL) {
        fprintf(stderr, ERROR_LINE("out of memory"));
        exit(BAD_ALLOC);
    }

    size_t errors = 0;
    bool already_opened = false;

    for (int i = start; i < argc && !feof(w); i++) {
        span s;
        s.ptr = (unsigned char*)argv[i];
        s.len = strlen(argv[i]);

        if (add(&files, s, &already_opened) == NULL) {
            fprintf(stderr, ERROR_LINE("out of memory"));
            exit(BAD_ALLOC);
            return 1;
        }

        // avoid reopening the same files, as all lines will be ignored anyway
        if (already_opened) {
            continue;
        }

        if (strcmp(argv[i], "-") == 0) {
            if (!handle_reader(w, stdin, &line, &seen)) {
                errors++;
            }
            continue;
        }

        if (!handle_file(w, argv[i], &line, &seen)) {
            errors++;
        }
    }

    // use stdin when not given any filepaths
    if (argc <= 1) {
        handle_reader(w, stdin, &line, &seen);
    }

    // don't bother deallocating things, since the app is done
    exit(errors == 0 ? 0 : 1);
    return errors;
}

int main(int argc, char** argv) {
#ifdef _WIN32
    setmode(fileno(stdin), O_BINARY);
    // ensure output lines end in LF instead of CRLF on windows
    setmode(fileno(stdout), O_BINARY);
    setmode(fileno(stderr), O_BINARY);
#endif

    if (argc > 1) {
        if (
            strcmp(argv[1], "-h") == 0 ||
            strcmp(argv[1], "-help") == 0 ||
            strcmp(argv[1], "--h") == 0 ||
            strcmp(argv[1], "--help") == 0
        ) {
            fprintf(stdout, "%s", info);
            return 0;
        }
    }

    const bool live_lines = lseek(fileno(stdout), 0, SEEK_CUR) != 0;
    if (live_lines) {
        setvbuf(stdout, NULL, _IOLBF, 0);
    } else {
        setvbuf(stdout, NULL, _IOFBF, 0);
    }
    return run(argc, argv, stdout) == 0 ? 0 : 1;
}